Speech Transcript - CONTENT PREFERENCE ESTIMATION IN ONLINE SOCIAL NETWORKS: MESSAGE PASSING VERSUS SPARSE RECONSTRUCTION ON GRAPHS

0:00:14	morning everyone a um i'm sort from a little way
0:00:17	many many jacob chicken as K
0:00:19	i we present thing my work about the estimating uh functions on social graphs what the function represents
0:00:25	uh and the preferences of the social network members
0:00:29	for a specific multimedia content and that is how much should
0:00:32	the social network members this like or like that particular content item
0:00:37	i was start with a little bit of uh background and motivation
0:00:41	uh to they we are aware that social a networking some we present on the web
0:00:45	when the we show photos
0:00:47	in the joe cells in creating user generated in content or
0:00:51	discover cover or all the
0:00:53	a high school friends
0:00:54	with tend to carry out all these activities to
0:00:57	the social networking sites that to happen
0:01:02	a as part of this activity is
0:01:04	you express our opinion of certain multimedia i
0:01:08	for example we may yeah
0:01:10	say how much we like up certain picture that the supposed to there or
0:01:14	we may score uh
0:01:15	a a specific movie
0:01:18	in uh in addition with
0:01:20	we tend to also
0:01:21	leave such information is part of our user profile
0:01:26	no is you can imagine that is the range of applications that can profit
0:01:31	from knowing this user preferences
0:01:34	and for instance uh
0:01:36	when we do online shopping
0:01:37	oh
0:01:38	for a smart homes uh uh uh for entertainment targeted advertising
0:01:44	uh a you a need to also that is there's is a range of applications information retrieval and search data
0:01:50	mining and so forth
0:01:52	for the more the data networks could also profit from knowing this information
0:01:57	and in addition to for collaborative talks knowing go
0:02:01	which person prefers uh
0:02:03	has a prefers different types of uh
0:02:05	uh task so could also be uh exploit
0:02:11	so the high level uh
0:02:13	abstraction of the problem that to look at
0:02:16	is uh that of data very uh recovery where would have a function
0:02:20	associated to
0:02:21	with a small subset of the nodes are telling us how much these nodes the like a specific video for
0:02:27	example
0:02:28	and then we are interested in that term mean
0:02:30	how much the other nodes texture like or these like this uh this specific item and
0:02:35	mm
0:02:36	the what we tend to exploit here is the
0:02:38	phenomenon called a of philly which means that
0:02:41	we tend to associate or conjugate with similar miller on there's
0:02:46	so he is the roadmap for the rest of the talk
0:02:49	uh we are close to being a social graph
0:02:51	which uh can in addition uh carry out the set the weights describing the fee it is between the users
0:02:57	how how much we are
0:02:59	a similar of this email that with
0:03:01	our specific neighbours see within the social network
0:03:04	and then as a mentioned we we will assume that we know this preference of what a small subset of
0:03:09	nodes
0:03:10	now to estimate the the the missing um
0:03:14	a preference is we will uh designed to algorithms one it's a descent L one
0:03:18	and is base a message passing and
0:03:21	it comprises two steps as people are familiar with the
0:03:24	centre as algorithms were the first one is the bit take a local expectation
0:03:29	in our own a but with and then we chain they uh and uh and information that is computed with
0:03:34	our neighbours
0:03:35	and then uh we also present uh
0:03:39	a algorithm that lies in the class of sparse construction
0:03:43	uh where a contrary to conventional a sparse reconstruction where we
0:03:47	ten to
0:03:49	i assist
0:03:52	where we tend to a um
0:03:54	constraint
0:03:56	uh
0:03:57	the form of the solution
0:03:59	with some regularization term now we will have like multiple a regularization terms bold
0:04:04	on the on the transform
0:04:06	or the signal
0:04:07	as well as in the signal domain which are described with these two summation
0:04:14	and then we all that uh a problem with um at total file to make in the direction of multiple
0:04:21	in this is with respect to related work this a been recent interest in the computer science community
0:04:26	of of uh uh the turning this a user preferences
0:04:29	and from the few words that to of a so far it's uh site it's to
0:04:33	to represent once here
0:04:35	but the or to simpler network or a correlation model the describes
0:04:39	the correlation in user preferences between any two members of the network
0:04:43	and then the odours also compute a certain set of features from the data
0:04:48	that to together with the machine lower algorithm in this uh a network for to correlation model
0:04:52	tries to compute the estimated the the um the missing preference
0:04:56	i will be if show a comparison with this works it the end and talk about the
0:05:01	the performance differences
0:05:03	and and the related to
0:05:05	direction of work is that on on opinion mining and sentiment analysis
0:05:10	oh which also lies in the computer science community
0:05:13	and now algorithms lie
0:05:15	which in the brother field of
0:05:17	a graphical models the descent of this algorithm that of present
0:05:21	and uh i also cited one reference your and sparse the construction
0:05:27	okay
0:05:28	so with respect to the first algorithm is a mentioned that comprise two steps
0:05:32	but the nose starts from an initial estimate bit could be an uninformed guess and so or
0:05:37	and then the the notes uh
0:05:39	to compute and
0:05:40	normalized expectation
0:05:43	using this weight it's um
0:05:45	from the previous estimates of the neighbours
0:05:47	so it's quite straightforward
0:05:50	and there's we going to see to it actually works quite well
0:05:53	uh a one analyse the performance of a good some really you use the
0:05:58	a C N
0:05:59	all the of the of the graph
0:06:01	uh and then lisa goes as false
0:06:04	oh we
0:06:06	we compute the low class and the matrix
0:06:08	is the difference between this may takes the in a where a represents the the weighted adjacency matrix of the
0:06:14	social graph
0:06:15	and these simply the uh
0:06:18	and they are gonna make takes way H and they are gonna and three she's is the
0:06:22	the some of the vertex decrease of each note
0:06:25	and uh of
0:06:26	i will i will need to be brief on these but
0:06:28	so spectrogram could have to T we know that they will be as a set of eigenvalues associated with the
0:06:33	solar plus and tricks
0:06:34	and we study the convergence of a algorithm to equivalent to the markov chain
0:06:38	that france on the graph
0:06:40	and
0:06:41	uh whose transition matrix a
0:06:43	is given of this expression
0:06:45	and it could be shown that oops
0:06:47	i'm sorry
0:06:48	um
0:06:49	and that the the this transition matrix is a the related to the lip loss of the graph
0:06:57	so that uh we was start the approximation that or or when we try to estimate the missing see is
0:07:02	using this algorithm
0:07:03	uh using this analysis of each uh iteration K
0:07:07	we could show that the the error or the total variation at or of the
0:07:12	oh the approximation is related to the
0:07:15	i so the lip plus in matrix
0:07:17	using this term
0:07:19	and with some work we could show that the this error is is bounded
0:07:24	but this exponential term
0:07:26	uh times these uh ratio
0:07:29	all of the maximum versus the meeting a node degree
0:07:33	all of the of the graph
0:07:35	where these uh
0:07:37	lamb the subscript E
0:07:39	um could be either the second smallest uh like a like in value or the
0:07:45	be related to this
0:07:47	the largest eigenvalue of a a class and matrix
0:07:49	or or or or a as an alternative but they will not go in detail here we could the
0:07:55	sure convergence analysis of this method
0:07:57	using the uh the power matter at the which is you
0:08:00	used to be totally compute
0:08:02	and in the composition of a matrix
0:08:06	now just an illustration of how does this work in terms of convergence rate
0:08:10	i will show you we here uh uh to gauss
0:08:13	uh which uh illustrate the the convergence of the algorithm
0:08:18	as a function of the of the density of the matrix that is the
0:08:22	well the that's it but graph as i'm sorry as a function of number of edges
0:08:25	and um as a great no of core were just we have the the total variation distance on the X
0:08:31	and we could show that uh your
0:08:34	we observe the same slope
0:08:36	uh is a function of these uh
0:08:39	eigenvalue eigenvalue
0:08:40	a a the sub E
0:08:42	all the log option
0:08:43	and i she show to good a house
0:08:46	which uh
0:08:48	or to by using
0:08:49	a different threshold value at which point algorithm stops computing you words when the total the distance
0:08:56	is below ten to the minus to for example
0:08:58	we stop and then receive
0:09:01	the is uh threshold is increase then we need the
0:09:04	more iterations to converge
0:09:07	i i for me to to mention that i'm sorry that we are using
0:09:11	uh a small dog from the house which are typically encountered thirteen
0:09:15	in uh examples also shown that networks
0:09:19	one another interesting graph off is a how do we do
0:09:22	with respect to a running the same algorithm one no one a random graph
0:09:26	and it's interesting to show that uh when the graph is not so dance on the beginning
0:09:31	we actually on the in terms of convergence speed and that is because
0:09:34	small world graphs um
0:09:37	uh
0:09:38	we exhibit a
0:09:40	but different uh
0:09:41	a non uniform distribution of the node degree so that
0:09:45	that G a small uh a large on the beginning we have a a number of know that have like
0:09:49	a small number of neighbours
0:09:51	and then that they actually
0:09:53	a affect the convergence one i'll go is that not only for them but for for the neighbour says well
0:09:57	now is the as density increases then
0:10:00	things set down so we convert to almost as fast as running running the looks them the on a on
0:10:04	them graph
0:10:06	now with respect to sparse reconstruction
0:10:09	a a as i mentioned conventionally
0:10:11	uh when you try to estimate uh a function where that this function
0:10:17	a a has the only a small number of file is that we know of
0:10:21	we tend to put some regularization constraint on the solution
0:10:25	to make life easier
0:10:26	now
0:10:28	this uh approach doesn't take into account that sometimes the solution to can
0:10:35	candes it
0:10:36	can require the shown
0:10:38	number of constraints for instance here we would be to crowd is this
0:10:41	content preferences
0:10:43	sum up to one
0:10:45	and to to all these we we generalise this approach by proposing is uh compound multi regularized the reconstruction
0:10:54	well we place a number of additional a regularization terms boat
0:10:59	on the solution itself that is in the signal the main and also on the
0:11:04	on that the small value or that signal
0:11:07	well these uh functions five i or
0:11:09	for equalisation functions
0:11:11	which are related to the constraints two additional constraint that we want to impose an solution
0:11:17	now the them is quite good a complicated to
0:11:21	to solve for X uh and i will briefly outline it here without going to the details
0:11:27	uh what we to to to solve this problem
0:11:30	of uh finding
0:11:32	and
0:11:32	but to minimize this so
0:11:35	expression
0:11:36	he's is uh
0:11:38	a design all the algorithm based on alternating direction of multiple as
0:11:42	where we do variable splitting
0:11:44	and then alternating optimization and then re to to converges
0:11:48	so they will be the three terms that they reader you'd update it
0:11:51	and one is the the solution sell the other one is to the uh
0:11:55	and the other two are related to the
0:11:57	do dual variables that the used
0:12:03	and
0:12:04	specifically we could show that uh
0:12:06	C is that to a first line
0:12:08	related to we X
0:12:09	he's is um
0:12:12	a quadratic expression
0:12:15	we could the we could do explicitly small with using the in the first uh expression on top here
0:12:20	and then the second expression where we so for the
0:12:24	for the you you for the dual variables that to introduce take actually
0:12:28	that second line here
0:12:30	it can be sure on it's in the paper
0:12:32	decompose is into uh
0:12:34	a set of independent the problems which could be sold in low
0:12:41	unfortunately uh
0:12:43	even with uh with the additional uh um
0:12:46	and to go terms we don't do that well and this graph off loose raise that
0:12:51	where on the x-axis axis showed the node in next we look at the fifteen a graph
0:12:56	and then the y-axis a show these a function of the to you we are trying to estimate so the
0:13:00	little but the red red to represent the know
0:13:03	the getting the value that blue value what is and um
0:13:07	the estimated value sort of function
0:13:10	if you don't put any additional a constraint
0:13:13	and uh a good red you represent the proposed solution where we can see that this function list can go
0:13:19	a non-negative
0:13:20	and you know they can sum up to one where
0:13:23	uh we can see that that we have multiple uh
0:13:26	content items of interest so we our preference actually present probabilities
0:13:30	or or these a set of uh a content items tense
0:13:34	so we can show that for some values
0:13:36	we are we are doing well and we we we could be estimate the with the the function close we
0:13:41	but for some well as we seem under perform significantly
0:13:45	and even more
0:13:46	noticeably is the fact that uh for example is a out line you of it
0:13:50	this uh uh a conventional at the legalisation doesn't what because the
0:13:55	without the extra constraints we could the estimate you one right is that the negative
0:14:00	uh a as a transform here we use the graph a with transform uh uh from this uh paper or
0:14:06	site each year
0:14:08	we assume that to we on know the function value of twenty five percent of the nodes
0:14:12	and then the rest of the nose do not have this function ready available
0:14:17	but this is expected to because the
0:14:19	you do doing these um the caff transform based estimation uh um there is an underlying assumption the spectrum of
0:14:26	the function on the graph is moot
0:14:29	that means that is a small number of coefficient that are significant and then the five
0:14:33	the function of decays as a function of the coefficient index
0:14:37	which is shown here
0:14:38	so
0:14:40	if you show the uh
0:14:41	um a reconstructed value of the function using this graph based methods
0:14:46	because see that the spectrum is quite small but we actually if little that they a look at the actual
0:14:50	value
0:14:51	well the spectrum
0:14:52	uh it doesn't follow that behaviour so
0:14:55	using all the shelf off graph transforms um
0:14:59	doesn't provide a
0:15:00	a can solution for this problem and i a thing is that the
0:15:04	function is sent in the estimation is sensitive to the
0:15:08	a choice of this subset V sub sub zero and that's because the function is of to normal and is
0:15:12	not a redundant
0:15:14	so down that line assumption that this uh a good off of let then any like a after as one
0:15:19	uh uh uh price to takes a uh into account is that the function is node
0:15:26	so i was like to conclude at this point
0:15:28	um
0:15:29	stating that i have presented to uh two algorithms for and uh recovery of signals some social and that also
0:15:35	uh with a variety of implications
0:15:37	i mentioned that uh will but a if you about how do we do compared to
0:15:41	state-of-the-art in the computer science community
0:15:44	uh we observe that the
0:15:48	we do a twenty two eighty percent better
0:15:50	in terms of break addiction error or and of a a a a at are forty yeah
0:15:53	and the variation of that there
0:15:55	relative to those works uh
0:15:58	which has the set of features and use the net autocorrelation correlation model and we believe the that's due to
0:16:03	two reasons
0:16:04	the first one is the
0:16:06	then to
0:16:07	can see the the social influences the fact of all them with
0:16:11	if liz
0:16:12	is a factor
0:16:13	um
0:16:15	of of all the members of the social community
0:16:17	which
0:16:18	we believe can into use a certain amount of noise you know where estimation where is to if we do
0:16:23	things locally
0:16:24	which in each neighbourhood
0:16:25	and computing features is not always easy and um
0:16:29	i we i why believe that it is in flames alters of
0:16:32	buying the performance so their algorithm to much to the the specific date that the the use
0:16:37	in our case the conversion of while got them is uh simply in but the social good of that is
0:16:42	it's spectrum
0:16:43	a unfortunately this or when we do a sparse reconstruction and
0:16:46	coming from the goal compressed sensing community
0:16:50	we we are still lacking uh um a good graph transform
0:16:54	to to do so this type of estimation and the we also need to figure out how to better map
0:17:00	this function on the graph
0:17:01	the take
0:17:02	take for but the advantage of though that graph transform
0:17:07	so i will conclude with the sum
0:17:08	i the management
0:17:09	thank you
0:17:21	a
0:17:23	no from
0:17:26	oh
0:17:28	i'm so
0:17:31	i
0:17:33	yes
0:17:34	i
0:17:36	yes
0:17:37	i
0:17:38	a
0:17:41	oh yes
0:17:42	yes
0:17:44	yes at each iteration
0:17:50	a
0:17:53	i
0:17:54	yes
0:18:01	um um but uh uh it's it's normal to want so like uh uh i i take their preferences
0:18:06	and i you know i say my but if an it's the like by to the preferences of my neighbours
0:18:11	and there are also proportional to this way describing house see and we are or not
0:18:17	no no no no no no i'm sorry i didn't yes
0:18:20	yes
0:18:21	yeah really matter okay

CONTENT PREFERENCE ESTIMATION IN ONLINE SOCIAL NETWORKS: MESSAGE PASSING VERSUS SPARSE RECONSTRUCTION ON GRAPHS

Distributed and Collaborative Signal Processing

Presented by: Jacob Chakareski, Author(s): Jacob Chakareski, Ecole Polytechnique Fédérale de Lausanne, Switzerland