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 |