1
00:00:00,450 --> 00:00:05,310
So now that we have defined our relaxed
version of affiliation graph model,

2
00:00:05,310 --> 00:00:08,540
now the whole trick is to say,
okay, how do we go and

3
00:00:08,540 --> 00:00:11,870
find our community affiliation matrix F,
right?

4
00:00:11,870 --> 00:00:13,550
This is the matrix where, for

5
00:00:13,550 --> 00:00:18,860
every node, we know what are the
communities that a given node belongs to.

6
00:00:18,860 --> 00:00:20,650
So how do we go do this?

7
00:00:20,650 --> 00:00:22,330
Right, here is out task.

8
00:00:22,330 --> 00:00:25,730
Given a network G we want to estimate F,

9
00:00:25,730 --> 00:00:30,000
and we want to find F in such a way
that it maximizes the, the likelihood.

10
00:00:30,000 --> 00:00:34,950
Right, i maximizes the probability
that F generated our graph G.

11
00:00:34,950 --> 00:00:37,370
So we have exactly what we had before.

12
00:00:37,370 --> 00:00:43,570
We want to find F that maximizes the
probability of the graph where of course

13
00:00:43,570 --> 00:00:48,940
these hatch probabilities are computed
based on, based on our matrix F.

14
00:00:48,940 --> 00:00:51,880
Right?
So probability of an edge is simply 1

15
00:00:51,880 --> 00:00:59,890
minus the exp raised to the power of
minus given two rows one for node u and

16
00:00:59,890 --> 00:01:05,410
one from node v in our matrix, rather
than working with this expression here,

17
00:01:05,410 --> 00:01:09,360
which is called the likelihood, we would
like to work with a log likelihood.

18
00:01:09,360 --> 00:01:11,680
So, basically we take
the logarithm of the.

19
00:01:13,300 --> 00:01:16,550
likelihood, and the reason why we
take the logarithm is because then

20
00:01:16,550 --> 00:01:18,510
all the products become summations.

21
00:01:18,510 --> 00:01:19,720
Right.

22
00:01:19,720 --> 00:01:22,090
If we take,
if we have a product of terms, and

23
00:01:22,090 --> 00:01:27,690
we take the logarithm then, that
simplifies to To a sum of the logarithm.

24
00:01:27,690 --> 00:01:29,890
Right?
And this is good for two reasons.

25
00:01:29,890 --> 00:01:33,400
First, it's kind of analytically nice
to work with log-likelihood, and

26
00:01:33,400 --> 00:01:37,450
second, kind of more important reason,
is that multiplying small

27
00:01:37,450 --> 00:01:42,490
numbers the numerical errors start
to add up and start to propagate.

28
00:01:42,490 --> 00:01:45,950
If we are summing together
small numbers the errors are,

29
00:01:45,950 --> 00:01:47,930
the numerical errors are not so serious.

30
00:01:47,930 --> 00:01:51,980
So working with log likelihood is
always preferred over working with

31
00:01:51,980 --> 00:01:52,930
the raw likelihoods.

32
00:01:52,930 --> 00:01:56,700
So rather than with, working with
probability of a graph given F,

33
00:01:56,700 --> 00:01:59,900
we will work with the logarithm
of that probability, and

34
00:01:59,900 --> 00:02:03,590
given that logarithm is a monotone
function, everything is still the same.

35
00:02:03,590 --> 00:02:04,150
Okay.

36
00:02:04,150 --> 00:02:07,010
So now we know what our goal is, right?

37
00:02:07,010 --> 00:02:10,760
Our goal is to find F that
maximizes the log likelihood.

38
00:02:10,760 --> 00:02:12,160
What is the log likelihood?

39
00:02:12,160 --> 00:02:18,570
The log likelihood is simply the logarithm
of of this expression up here.

40
00:02:18,570 --> 00:02:22,350
So, if I write it out, right, I have
a summation over all the edges before I

41
00:02:22,350 --> 00:02:24,120
had a product, now I have a summation.

42
00:02:24,120 --> 00:02:29,400
This is probability of an edge u,
v, and here in the second part,

43
00:02:29,400 --> 00:02:34,320
I have the probability of not seeing an
edge, and what is nice is that minus ones

44
00:02:34,320 --> 00:02:39,860
cancel, so all I, all I'm left with is
the product of the two factors, right?

45
00:02:39,860 --> 00:02:42,040
So now we know the optimization problem.

46
00:02:42,040 --> 00:02:45,875
Our goal is to find factor matrix
F that maxes the following

47
00:02:45,875 --> 00:02:47,790
log-like equid, equation.

48
00:02:49,180 --> 00:02:55,550
Now how do we go and find the matrix
f that maximizes the likelihood?

49
00:02:55,550 --> 00:03:00,150
What we can do is similar to what we
have already seen in the class is to

50
00:03:00,150 --> 00:03:03,760
basically go and, and
use optimization methods.

51
00:03:03,760 --> 00:03:08,470
In particular we can think of this whole
problem as being continuous optimization

52
00:03:08,470 --> 00:03:14,070
problem, and one of the beth mat,
best methods to, to use when solving

53
00:03:14,070 --> 00:03:17,990
optimization problems that are continuous
is to use the notion of gradient.

54
00:03:17,990 --> 00:03:20,000
Right?
To think of this as a gradient descent

55
00:03:20,000 --> 00:03:24,010
type of problem, where basically what we,
what we want to do is we, we,

56
00:03:24,010 --> 00:03:29,560
we think of our function as having
some kind of convex, smooth shape.

57
00:03:29,560 --> 00:03:34,010
And what we would like to do is we would
like to Compute the value of the gradient

58
00:03:34,010 --> 00:03:37,650
at a given starting point, and then
move into the direction of the gradient.

59
00:03:37,650 --> 00:03:40,190
So as you kind of ski
down the slope to get,

60
00:03:40,190 --> 00:03:42,350
to reach the minimum of that function.

61
00:03:42,350 --> 00:03:45,140
In our case,
we are not doing minimization, but

62
00:03:45,140 --> 00:03:49,980
we are doing maximization, because we
want to find the most likely or the best,

63
00:03:49,980 --> 00:03:52,180
the matrix F with the highest likelihood.

64
00:03:52,180 --> 00:03:54,840
So the, our picture looks like that.

65
00:03:54,840 --> 00:03:56,650
So, but everything still applies.

66
00:03:56,650 --> 00:03:58,430
We have just kind of walking up to here.

67
00:03:58,430 --> 00:03:59,090
Right?
If you want to

68
00:03:59,090 --> 00:04:02,330
reach the mountain you will, you,
would, one way to reach the top of

69
00:04:02,330 --> 00:04:06,460
the mountain is just to always walk up and
eventually you will be on the top.

70
00:04:06,460 --> 00:04:08,250
So that's kind of our strategy.

71
00:04:08,250 --> 00:04:11,850
So in order to say what is the slope
at a given point we need to

72
00:04:11,850 --> 00:04:16,670
compute a gradient or the derivative
of the log likelihood, simply so

73
00:04:16,670 --> 00:04:20,570
here is the derivative of the log
likelihood with respect to a given node.

74
00:04:20,570 --> 00:04:24,960
This is now with respect to a given
row and it's very simple right.

75
00:04:24,960 --> 00:04:28,310
I have a summation over
the neighbors of a given node and

76
00:04:28,310 --> 00:04:30,980
a summation over the non-neighbors
of a given node,

77
00:04:30,980 --> 00:04:35,940
and computing the derivative
of the first part.

78
00:04:35,940 --> 00:04:39,790
Gives us the following expression and
then computing the derivative of

79
00:04:39,790 --> 00:04:41,980
the second part of
the summation is even easier.

80
00:04:41,980 --> 00:04:45,530
It's basically just
the Fv that is surviving.

81
00:04:45,530 --> 00:04:48,310
One important thing here is N of u

82
00:04:48,310 --> 00:04:52,230
is simply the set of
neighbors of a given node u.

83
00:04:52,230 --> 00:04:53,720
So what.

84
00:04:53,720 --> 00:04:57,910
We could do now is to say simply, right
how do we solve this optimization problem.

85
00:04:57,910 --> 00:05:01,660
We can simply integrate over
the rows of our matrix cell for

86
00:05:01,660 --> 00:05:04,990
every row we can compute the gradient
of the log likelihood, and

87
00:05:04,990 --> 00:05:09,160
then we just update that
given row by moving for

88
00:05:09,160 --> 00:05:14,080
a small direction in a given in
the direction of the increased slop.

89
00:05:14,080 --> 00:05:15,800
Right.
So the idea is that basically.

90
00:05:15,800 --> 00:05:17,960
We compute the radiant,
we compute the slope and

91
00:05:17,960 --> 00:05:23,790
moving the direction of the slope, one,
one little here is that sometimes what can

92
00:05:23,790 --> 00:05:27,650
happen is the dismembership strands can
become negative if the membership strand

93
00:05:27,650 --> 00:05:31,860
is kind of becomes less than zero we just
reset it back to zero and, you know,

94
00:05:31,860 --> 00:05:35,700
we keep iterating this untill
the method stops changing f

95
00:05:35,700 --> 00:05:38,390
which means we have converged to the,
to the top.

96
00:05:39,420 --> 00:05:43,320
What is important here to know though,
is that this is very slow.

97
00:05:43,320 --> 00:05:44,450
Why is it slow is,

98
00:05:44,450 --> 00:05:49,680
is because computing the gradient for
a given node takes linear time.

99
00:05:49,680 --> 00:05:53,430
Meaning we have to go over all the data,
and the reason for that is

100
00:05:53,430 --> 00:05:58,390
that we have this summation here that goes
over all non neighbours of a given node.

101
00:05:58,390 --> 00:06:01,310
So what this means is we have to go and
we have to iterate.

102
00:06:01,310 --> 00:06:06,440
Every, every node in the network to
estimate the second part of the summation.

103
00:06:06,440 --> 00:06:08,870
So what we would rather do is to say okay.

104
00:06:08,870 --> 00:06:13,500
Is there a better way to est, to compute,
a faster way to compute this second part

105
00:06:13,500 --> 00:06:17,730
of the summation so that the whole
approach can be much faster?

106
00:06:17,730 --> 00:06:20,930
So here is kind of a version
2.0 of this approach.

107
00:06:20,930 --> 00:06:25,710
What we notice is that,
the summation over all the non-members.

108
00:06:25,710 --> 00:06:28,950
Right?
This is kind of the part that takes very

109
00:06:28,950 --> 00:06:34,610
long, because we have to go over everyone
who is not friend with our node, U and

110
00:06:34,610 --> 00:06:36,430
sum over their factors.

111
00:06:36,430 --> 00:06:37,910
What we note is this, is the following.

112
00:06:37,910 --> 00:06:38,980
We can say.

113
00:06:38,980 --> 00:06:42,350
The value of this expression is simply
a summation over all the nodes,

114
00:06:42,350 --> 00:06:45,500
neighbors and non-neighbors,
let's sum them together but

115
00:06:45,500 --> 00:06:51,680
now because we summed too many things
together we have to subtract the F for

116
00:06:51,680 --> 00:06:56,760
the node U and we also have to subtract
the F for the neighbors of U, and whatever

117
00:06:56,760 --> 00:07:02,060
is left are exactly the sum of the factors
of nodes that are non-neighbors.

118
00:07:02,060 --> 00:07:04,480
Why is this a big win?

119
00:07:04,480 --> 00:07:08,500
The, this is a big win because all we need
to do is kind of compute this ahead of

120
00:07:08,500 --> 00:07:09,240
time, right?

121
00:07:09,240 --> 00:07:11,330
We compute this slow
summation ahead of time and

122
00:07:11,330 --> 00:07:15,430
then whenever we need to estimate the sum
over the known neighbors for a given node,

123
00:07:15,430 --> 00:07:19,660
all we have to do is subtract F
of u from it, and then subtract.

124
00:07:19,660 --> 00:07:23,500
The sum of Fs of the neighbors
of a give node, right?

125
00:07:23,500 --> 00:07:28,300
So this means that rather, rather than,
than taking time linear in the size of

126
00:07:28,300 --> 00:07:32,510
the data, we need time linear
in the degree of a given node.

127
00:07:32,510 --> 00:07:36,330
And in networks nodes usually have
relatively small degree or, or

128
00:07:36,330 --> 00:07:39,800
they connect to a small fraction of nodes.

129
00:07:39,800 --> 00:07:40,970
In the total network.

130
00:07:40,970 --> 00:07:46,500
So this makes our method much faster
than the previous approach, but

131
00:07:46,500 --> 00:07:47,950
everything is still the same.

132
00:07:47,950 --> 00:07:50,550
The idea was we computed the gradient.

133
00:07:50,550 --> 00:07:55,460
Now that we have the gradient we can
do a simple gradient update to move

134
00:07:55,460 --> 00:07:58,380
up the hill and
find the maximum likelihood solution.

135
00:07:58,380 --> 00:08:03,520
Which is our matrix F, and
what the matrix set has in itself.

136
00:08:03,520 --> 00:08:08,750
It basically tells us what every node what
communities the given node belongs to.

137
00:08:08,750 --> 00:08:10,950
Just to show you how good this method is,

138
00:08:10,950 --> 00:08:14,780
here I'm showing you a graph where
the xx is the size of the network.,

139
00:08:14,780 --> 00:08:16,670
yx is the computation time.

140
00:08:17,800 --> 00:08:23,270
Here are some examples of other
methods that, that are used today.

141
00:08:23,270 --> 00:08:25,770
And you see how badly
they scale right after,

142
00:08:25,770 --> 00:08:31,330
after a few thousands of nodes basically
that on times go very quickly increase.

143
00:08:31,330 --> 00:08:35,130
While, for example, the method I was
talking to you today, the BigClam method,

144
00:08:35,130 --> 00:08:37,200
you see that its run times increases much,

145
00:08:37,200 --> 00:08:39,650
much more slowly with
the size of the network.

146
00:08:39,650 --> 00:08:41,180
So, for example, in five minutes.

147
00:08:41,180 --> 00:08:44,150
We can process a network
of around 300,000 nodes.

148
00:08:44,150 --> 00:08:48,190
If you want a network of hundred million
edges, you need to wait a day or

149
00:08:48,190 --> 00:08:53,910
so, and, also, what it turns out is that
the method, works great in practice.

150
00:08:53,910 --> 00:08:55,960
This is some of our latest research.

151
00:08:55,960 --> 00:09:00,669
So here is a set papers, kind of follow-up
works, that you need to know and

152
00:09:00,669 --> 00:09:04,238
understand more details about
this particular method, and,

153
00:09:04,238 --> 00:09:08,679
in particular, the paper that we talked
about is the paper here on the top, and

154
00:09:08,679 --> 00:09:10,968
here's kind of more details about the,

155
00:09:10,968 --> 00:09:15,185
the way actually documentation procedure
works and how we arrived to it.