So now that we have defined our relaxed
version of affiliation graph model,
now the whole trick is to say,
okay, how do we go and
find our community affiliation matrix F,
right?
This is the matrix where, for
every node, we know what are the
communities that a given node belongs to.
So how do we go do this?
Right, here is out task.
Given a network G we want to estimate F,
and we want to find F in such a way
that it maximizes the, the likelihood.
Right, i maximizes the probability
that F generated our graph G.
So we have exactly what we had before.
We want to find F that maximizes the
probability of the graph where of course
these hatch probabilities are computed
based on, based on our matrix F.
Right?
So probability of an edge is simply 1
minus the exp raised to the power of
minus given two rows one for node u and
one from node v in our matrix, rather
than working with this expression here,
which is called the likelihood, we would
like to work with a log likelihood.
So, basically we take
the logarithm of the.
likelihood, and the reason why we
take the logarithm is because then
all the products become summations.
Right.
If we take,
if we have a product of terms, and
we take the logarithm then, that
simplifies to To a sum of the logarithm.
Right?
And this is good for two reasons.
First, it's kind of analytically nice
to work with log-likelihood, and
second, kind of more important reason,
is that multiplying small
numbers the numerical errors start
to add up and start to propagate.
If we are summing together
small numbers the errors are,
the numerical errors are not so serious.
So working with log likelihood is
always preferred over working with
the raw likelihoods.
So rather than with, working with
probability of a graph given F,
we will work with the logarithm
of that probability, and
given that logarithm is a monotone
function, everything is still the same.
Okay.
So now we know what our goal is, right?
Our goal is to find F that
maximizes the log likelihood.
What is the log likelihood?
The log likelihood is simply the logarithm
of of this expression up here.
So, if I write it out, right, I have
a summation over all the edges before I
had a product, now I have a summation.
This is probability of an edge u,
v, and here in the second part,
I have the probability of not seeing an
edge, and what is nice is that minus ones
cancel, so all I, all I'm left with is
the product of the two factors, right?
So now we know the optimization problem.
Our goal is to find factor matrix
F that maxes the following
log-like equid, equation.
Now how do we go and find the matrix
f that maximizes the likelihood?
What we can do is similar to what we
have already seen in the class is to
basically go and, and
use optimization methods.
In particular we can think of this whole
problem as being continuous optimization
problem, and one of the beth mat,
best methods to, to use when solving
optimization problems that are continuous
is to use the notion of gradient.
Right?
To think of this as a gradient descent
type of problem, where basically what we,
what we want to do is we, we,
we think of our function as having
some kind of convex, smooth shape.
And what we would like to do is we would
like to Compute the value of the gradient
at a given starting point, and then
move into the direction of the gradient.
So as you kind of ski
down the slope to get,
to reach the minimum of that function.
In our case,
we are not doing minimization, but
we are doing maximization, because we
want to find the most likely or the best,
the matrix F with the highest likelihood.
So the, our picture looks like that.
So, but everything still applies.
We have just kind of walking up to here.
Right?
If you want to
reach the mountain you will, you,
would, one way to reach the top of
the mountain is just to always walk up and
eventually you will be on the top.
So that's kind of our strategy.
So in order to say what is the slope
at a given point we need to
compute a gradient or the derivative
of the log likelihood, simply so
here is the derivative of the log
likelihood with respect to a given node.
This is now with respect to a given
row and it's very simple right.
I have a summation over
the neighbors of a given node and
a summation over the non-neighbors
of a given node,
and computing the derivative
of the first part.
Gives us the following expression and
then computing the derivative of
the second part of
the summation is even easier.
It's basically just
the Fv that is surviving.
One important thing here is N of u
is simply the set of
neighbors of a given node u.
So what.
We could do now is to say simply, right
how do we solve this optimization problem.
We can simply integrate over
the rows of our matrix cell for
every row we can compute the gradient
of the log likelihood, and
then we just update that
given row by moving for
a small direction in a given in
the direction of the increased slop.
Right.
So the idea is that basically.
We compute the radiant,
we compute the slope and
moving the direction of the slope, one,
one little here is that sometimes what can
happen is the dismembership strands can
become negative if the membership strand
is kind of becomes less than zero we just
reset it back to zero and, you know,
we keep iterating this untill
the method stops changing f
which means we have converged to the,
to the top.
What is important here to know though,
is that this is very slow.
Why is it slow is,
is because computing the gradient for
a given node takes linear time.
Meaning we have to go over all the data,
and the reason for that is
that we have this summation here that goes
over all non neighbours of a given node.
So what this means is we have to go and
we have to iterate.
Every, every node in the network to
estimate the second part of the summation.
So what we would rather do is to say okay.
Is there a better way to est, to compute,
a faster way to compute this second part
of the summation so that the whole
approach can be much faster?
So here is kind of a version
2.0 of this approach.
What we notice is that,
the summation over all the non-members.
Right?
This is kind of the part that takes very
long, because we have to go over everyone
who is not friend with our node, U and
sum over their factors.
What we note is this, is the following.
We can say.
The value of this expression is simply
a summation over all the nodes,
neighbors and non-neighbors,
let's sum them together but
now because we summed too many things
together we have to subtract the F for
the node U and we also have to subtract
the F for the neighbors of U, and whatever
is left are exactly the sum of the factors
of nodes that are non-neighbors.
Why is this a big win?
The, this is a big win because all we need
to do is kind of compute this ahead of
time, right?
We compute this slow
summation ahead of time and
then whenever we need to estimate the sum
over the known neighbors for a given node,
all we have to do is subtract F
of u from it, and then subtract.
The sum of Fs of the neighbors
of a give node, right?
So this means that rather, rather than,
than taking time linear in the size of
the data, we need time linear
in the degree of a given node.
And in networks nodes usually have
relatively small degree or, or
they connect to a small fraction of nodes.
In the total network.
So this makes our method much faster
than the previous approach, but
everything is still the same.
The idea was we computed the gradient.
Now that we have the gradient we can
do a simple gradient update to move
up the hill and
find the maximum likelihood solution.
Which is our matrix F, and
what the matrix set has in itself.
It basically tells us what every node what
communities the given node belongs to.
Just to show you how good this method is,
here I'm showing you a graph where
the xx is the size of the network.,
yx is the computation time.
Here are some examples of other
methods that, that are used today.
And you see how badly
they scale right after,
after a few thousands of nodes basically
that on times go very quickly increase.
While, for example, the method I was
talking to you today, the BigClam method,
you see that its run times increases much,
much more slowly with
the size of the network.
So, for example, in five minutes.
We can process a network
of around 300,000 nodes.
If you want a network of hundred million
edges, you need to wait a day or
so, and, also, what it turns out is that
the method, works great in practice.
This is some of our latest research.
So here is a set papers, kind of follow-up
works, that you need to know and
understand more details about
this particular method, and,
in particular, the paper that we talked
about is the paper here on the top, and
here's kind of more details about the,
the way actually documentation procedure
works and how we arrived to it.