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