morning everyone a um i'm sort from a little way

many many jacob chicken as K

i we present thing my work about the estimating uh functions on social graphs what the function represents

uh and the preferences of the social network members

for a specific multimedia content and that is how much should

the social network members this like or like that particular content item

i was start with a little bit of uh background and motivation

uh to they we are aware that social a networking some we present on the web

when the we show photos

in the joe cells in creating user generated in content or

discover cover or all the

a high school friends

with tend to carry out all these activities to

the social networking sites that to happen

a as part of this activity is

you express our opinion of certain multimedia i

for example we may yeah

say how much we like up certain picture that the supposed to there or

we may score uh

a a specific movie

in uh in addition with

we tend to also

leave such information is part of our user profile

no is you can imagine that is the range of applications that can profit

from knowing this user preferences

and for instance uh

when we do online shopping

oh

for a smart homes uh uh uh for entertainment targeted advertising

uh a you a need to also that is there's is a range of applications information retrieval and search data

mining and so forth

for the more the data networks could also profit from knowing this information

and in addition to for collaborative talks knowing go

which person prefers uh

has a prefers different types of uh

uh task so could also be uh exploit

so the high level uh

abstraction of the problem that to look at

is uh that of data very uh recovery where would have a function

associated to

with a small subset of the nodes are telling us how much these nodes the like a specific video for

example

and then we are interested in that term mean

how much the other nodes texture like or these like this uh this specific item and

mm

the what we tend to exploit here is the

phenomenon called a of philly which means that

we tend to associate or conjugate with similar miller on there's

so he is the roadmap for the rest of the talk

uh we are close to being a social graph

which uh can in addition uh carry out the set the weights describing the fee it is between the users

how how much we are

a similar of this email that with

our specific neighbours see within the social network

and then as a mentioned we we will assume that we know this preference of what a small subset of

nodes

now to estimate the the the missing um

a preference is we will uh designed to algorithms one it's a descent L one

and is base a message passing and

it comprises two steps as people are familiar with the

centre as algorithms were the first one is the bit take a local expectation

in our own a but with and then we chain they uh and uh and information that is computed with

our neighbours

and then uh we also present uh

a algorithm that lies in the class of sparse construction

uh where a contrary to conventional a sparse reconstruction where we

ten to

i assist

where we tend to a um

constraint

uh

the form of the solution

with some regularization term now we will have like multiple a regularization terms bold

on the on the transform

or the signal

as well as in the signal domain which are described with these two summation

and then we all that uh a problem with um at total file to make in the direction of multiple

in this is with respect to related work this a been recent interest in the computer science community

of of uh uh the turning this a user preferences

and from the few words that to of a so far it's uh site it's to

to represent once here

but the or to simpler network or a correlation model the describes

the correlation in user preferences between any two members of the network

and then the odours also compute a certain set of features from the data

that to together with the machine lower algorithm in this uh a network for to correlation model

tries to compute the estimated the the um the missing preference

i will be if show a comparison with this works it the end and talk about the

the performance differences

and and the related to

direction of work is that on on opinion mining and sentiment analysis

oh which also lies in the computer science community

and now algorithms lie

which in the brother field of

a graphical models the descent of this algorithm that of present

and uh i also cited one reference your and sparse the construction

okay

so with respect to the first algorithm is a mentioned that comprise two steps

but the nose starts from an initial estimate bit could be an uninformed guess and so or

and then the the notes uh

to compute and

normalized expectation

using this weight it's um

from the previous estimates of the neighbours

so it's quite straightforward

and there's we going to see to it actually works quite well

uh a one analyse the performance of a good some really you use the

a C N

all the of the of the graph

uh and then lisa goes as false

oh we

we compute the low class and the matrix

is the difference between this may takes the in a where a represents the the weighted adjacency matrix of the

social graph

and these simply the uh

and they are gonna make takes way H and they are gonna and three she's is the

the some of the vertex decrease of each note

and uh of

i will i will need to be brief on these but

so spectrogram could have to T we know that they will be as a set of eigenvalues associated with the

solar plus and tricks

and we study the convergence of a algorithm to equivalent to the markov chain

that france on the graph

and

uh whose transition matrix a

is given of this expression

and it could be shown that oops

i'm sorry

um

and that the the this transition matrix is a the related to the lip loss of the graph

so that uh we was start the approximation that or or when we try to estimate the missing see is

using this algorithm

uh using this analysis of each uh iteration K

we could show that the the error or the total variation at or of the

oh the approximation is related to the

i so the lip plus in matrix

using this term

and with some work we could show that the this error is is bounded

but this exponential term

uh times these uh ratio

all of the maximum versus the meeting a node degree

all of the of the graph

where these uh

lamb the subscript E

um could be either the second smallest uh like a like in value or the

be related to this

the largest eigenvalue of a a class and matrix

or or or or a as an alternative but they will not go in detail here we could the

sure convergence analysis of this method

using the uh the power matter at the which is you

used to be totally compute

and in the composition of a matrix

now just an illustration of how does this work in terms of convergence rate

i will show you we here uh uh to gauss

uh which uh illustrate the the convergence of the algorithm

as a function of the of the density of the matrix that is the

well the that's it but graph as i'm sorry as a function of number of edges

and um as a great no of core were just we have the the total variation distance on the X

and we could show that uh your

we observe the same slope

uh is a function of these uh

eigenvalue eigenvalue

a a the sub E

all the log option

and i she show to good a house

which uh

or to by using

a different threshold value at which point algorithm stops computing you words when the total the distance

is below ten to the minus to for example

we stop and then receive

the is uh threshold is increase then we need the

more iterations to converge

i i for me to to mention that i'm sorry that we are using

uh a small dog from the house which are typically encountered thirteen

in uh examples also shown that networks

one another interesting graph off is a how do we do

with respect to a running the same algorithm one no one a random graph

and it's interesting to show that uh when the graph is not so dance on the beginning

we actually on the in terms of convergence speed and that is because

small world graphs um

uh

we exhibit a

but different uh

a non uniform distribution of the node degree so that

that G a small uh a large on the beginning we have a a number of know that have like

a small number of neighbours

and then that they actually

a affect the convergence one i'll go is that not only for them but for for the neighbour says well

now is the as density increases then

things set down so we convert to almost as fast as running running the looks them the on a on

them graph

now with respect to sparse reconstruction

a a as i mentioned conventionally

uh when you try to estimate uh a function where that this function

a a has the only a small number of file is that we know of

we tend to put some regularization constraint on the solution

to make life easier

now

this uh approach doesn't take into account that sometimes the solution to can

candes it

can require the shown

number of constraints for instance here we would be to crowd is this

content preferences

sum up to one

and to to all these we we generalise this approach by proposing is uh compound multi regularized the reconstruction

well we place a number of additional a regularization terms boat

on the solution itself that is in the signal the main and also on the

on that the small value or that signal

well these uh functions five i or

for equalisation functions

which are related to the constraints two additional constraint that we want to impose an solution

now the them is quite good a complicated to

to solve for X uh and i will briefly outline it here without going to the details

uh what we to to to solve this problem

of uh finding

and

but to minimize this so

expression

he's is uh

a design all the algorithm based on alternating direction of multiple as

where we do variable splitting

and then alternating optimization and then re to to converges

so they will be the three terms that they reader you'd update it

and one is the the solution sell the other one is to the uh

and the other two are related to the

do dual variables that the used

and

specifically we could show that uh

C is that to a first line

related to we X

he's is um

a quadratic expression

we could the we could do explicitly small with using the in the first uh expression on top here

and then the second expression where we so for the

for the you you for the dual variables that to introduce take actually

that second line here

it can be sure on it's in the paper

decompose is into uh

a set of independent the problems which could be sold in low

unfortunately uh

even with uh with the additional uh um

and to go terms we don't do that well and this graph off loose raise that

where on the x-axis axis showed the node in next we look at the fifteen a graph

and then the y-axis a show these a function of the to you we are trying to estimate so the

little but the red red to represent the know

the getting the value that blue value what is and um

the estimated value sort of function

if you don't put any additional a constraint

and uh a good red you represent the proposed solution where we can see that this function list can go

a non-negative

and you know they can sum up to one where

uh we can see that that we have multiple uh

content items of interest so we our preference actually present probabilities

or or these a set of uh a content items tense

so we can show that for some values

we are we are doing well and we we we could be estimate the with the the function close we

but for some well as we seem under perform significantly

and even more

noticeably is the fact that uh for example is a out line you of it

this uh uh a conventional at the legalisation doesn't what because the

without the extra constraints we could the estimate you one right is that the negative

uh a as a transform here we use the graph a with transform uh uh from this uh paper or

site each year

we assume that to we on know the function value of twenty five percent of the nodes

and then the rest of the nose do not have this function ready available

but this is expected to because the

you do doing these um the caff transform based estimation uh um there is an underlying assumption the spectrum of

the function on the graph is moot

that means that is a small number of coefficient that are significant and then the five

the function of decays as a function of the coefficient index

which is shown here

so

if you show the uh

um a reconstructed value of the function using this graph based methods

because see that the spectrum is quite small but we actually if little that they a look at the actual

value

well the spectrum

uh it doesn't follow that behaviour so

using all the shelf off graph transforms um

doesn't provide a

a can solution for this problem and i a thing is that the

function is sent in the estimation is sensitive to the

a choice of this subset V sub sub zero and that's because the function is of to normal and is

not a redundant

so down that line assumption that this uh a good off of let then any like a after as one

uh uh uh price to takes a uh into account is that the function is node

so i was like to conclude at this point

um

stating that i have presented to uh two algorithms for and uh recovery of signals some social and that also

uh with a variety of implications

i mentioned that uh will but a if you about how do we do compared to

state-of-the-art in the computer science community

uh we observe that the

we do a twenty two eighty percent better

in terms of break addiction error or and of a a a a at are forty yeah

and the variation of that there

relative to those works uh

which has the set of features and use the net autocorrelation correlation model and we believe the that's due to

two reasons

the first one is the

then to

can see the the social influences the fact of all them with

if liz

is a factor

um

of of all the members of the social community

which

we believe can into use a certain amount of noise you know where estimation where is to if we do

things locally

which in each neighbourhood

and computing features is not always easy and um

i we i why believe that it is in flames alters of

buying the performance so their algorithm to much to the the specific date that the the use

in our case the conversion of while got them is uh simply in but the social good of that is

it's spectrum

a unfortunately this or when we do a sparse reconstruction and

coming from the goal compressed sensing community

we we are still lacking uh um a good graph transform

to to do so this type of estimation and the we also need to figure out how to better map

this function on the graph

the take

take for but the advantage of though that graph transform

so i will conclude with the sum

i the management

thank you

a

no from

oh

i'm so

i

yes

i

yes

i

a

oh yes

yes

yes at each iteration

a

i

yes

um um but uh uh it's it's normal to want so like uh uh i i take their preferences

and i you know i say my but if an it's the like by to the preferences of my neighbours

and there are also proportional to this way describing house see and we are or not

no no no no no no i'm sorry i didn't yes

yes

yeah really matter okay