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