1
00:00:00,330 --> 00:00:04,700
So now, we will start talking about
how to combat the web spam, and

2
00:00:04,700 --> 00:00:07,930
the method we will talk
about is called TrustRank.

3
00:00:07,930 --> 00:00:11,090
So, as we mentioned before,
there are two types of web spam.

4
00:00:11,090 --> 00:00:13,630
There is the term spam and
there is the link spam.

5
00:00:13,630 --> 00:00:17,630
Term spam, you can think of it as it's
very similar to the email spam filtering.

6
00:00:17,630 --> 00:00:18,137
All right.

7
00:00:18,137 --> 00:00:22,217
Basically, it would like to identify what
are the terms, what are the words that

8
00:00:22,217 --> 00:00:26,117
correspond to spam and for every webpage,
we would like to automatically say

9
00:00:26,117 --> 00:00:29,550
whether it contains a set of those
words and filter out the webpage.

10
00:00:31,100 --> 00:00:36,190
Combating link spam however, is, is more,
more, more expensive, or more tricky.

11
00:00:36,190 --> 00:00:39,940
The idea here is basically that
we would want to detect or

12
00:00:39,940 --> 00:00:44,940
blacklist a set of graph structures
on the web that look like spam farms.

13
00:00:44,940 --> 00:00:49,160
In particular what is the problem
here is that kind of this links,

14
00:00:49,160 --> 00:00:52,335
this leads to another war where
if we would have such a filter,

15
00:00:52,335 --> 00:00:55,680
that would try to identify structures
that look like spams farms,

16
00:00:55,680 --> 00:00:57,870
is that then spammers would
try to hide themselves.

17
00:00:57,870 --> 00:01:00,030
And, we would have to update them back,
blacklist, and

18
00:01:00,030 --> 00:01:01,680
everything would go back and forth.

19
00:01:01,680 --> 00:01:04,240
So, we need a more universal solution.

20
00:01:04,240 --> 00:01:07,620
So, the more universal
solution is called TrustRank.

21
00:01:07,620 --> 00:01:10,370
And, in its basic idea, TrustRank is

22
00:01:10,370 --> 00:01:15,960
simply a topic-specific PageRank with
a teleport set to a trusted set of pages.

23
00:01:15,960 --> 00:01:17,040
Right?
So, when I say for

24
00:01:17,040 --> 00:01:21,050
example trusted set of web pages,
this would be web pages to which,

25
00:01:21,050 --> 00:01:24,160
to which we trust, and that are not
likely to be hacked or farmed.

26
00:01:24,160 --> 00:01:26,570
So, for example, .edu domains.

27
00:01:26,570 --> 00:01:30,570
Or, from non-US schools would be such a,

28
00:01:30,570 --> 00:01:35,970
such a way to identify a good
set of trust web pages.

29
00:01:35,970 --> 00:01:40,470
So, let's think about this a bit,
a bit more and see what is the idea.

30
00:01:40,470 --> 00:01:42,250
So basically, the, the idea becau,

31
00:01:42,250 --> 00:01:45,880
behind the TrustRank is this is
the notion of approximate isolation,

32
00:01:45,880 --> 00:01:50,200
where the idea is that it's rare for
a good page to point to a bad page.

33
00:01:50,200 --> 00:01:55,910
Right, it's very rare that a good
legitimate page would point to spam.

34
00:01:55,910 --> 00:02:00,280
So, the idea is that we want to select
a set of seed pages from the web that we

35
00:02:00,280 --> 00:02:01,940
trust that they are good.

36
00:02:01,940 --> 00:02:06,490
And then, we would want to compute some
kind of similarity, or importance of

37
00:02:06,490 --> 00:02:11,210
proximity of all the webpages on
the web to this, to this trusted set.

38
00:02:11,210 --> 00:02:14,500
And now, if a,
some other webpage is legitimate,

39
00:02:14,500 --> 00:02:18,150
then it will be close to
the trusted set of webpages.

40
00:02:18,150 --> 00:02:22,725
Of course, what we are depending on
here is that we have some oracle,

41
00:02:22,725 --> 00:02:27,030
right.Some human to identify good
trustworthy set of webpages.

42
00:02:27,030 --> 00:02:29,480
And and of course,

43
00:02:29,480 --> 00:02:33,990
that the idea is that web spam page
are not is this web, in this set.

44
00:02:33,990 --> 00:02:38,050
Of course, this is a very expensive
task because a user would have to go, or

45
00:02:38,050 --> 00:02:41,540
a human would have to go through,
and do this do these labors.

46
00:02:41,540 --> 00:02:42,450
So, in some sense,

47
00:02:42,450 --> 00:02:46,760
we want to make this set of seed
trusted webpages as small as possible.

48
00:02:47,840 --> 00:02:49,790
So, the idea is the following.

49
00:02:49,790 --> 00:02:53,600
What basically, we'll be doing is,
we are doing the trust propagation.

50
00:02:53,600 --> 00:02:58,760
So basically, we have a subset of good
seed pages that we identify as good as,

51
00:02:58,760 --> 00:03:00,680
we will call them trusted pages.

52
00:03:00,680 --> 00:03:02,755
And then, we perform,
as I mentioned before,

53
00:03:02,755 --> 00:03:08,200
topic-sensitive PageRank with
a teleport set to the trusted pages.

54
00:03:08,200 --> 00:03:10,200
What this really means
is that now basically,

55
00:03:10,200 --> 00:03:13,490
we are propagating trust
across the links of the graph.

56
00:03:13,490 --> 00:03:14,760
Right?
And, the trust can

57
00:03:14,760 --> 00:03:18,840
take value between zero and one,
the same way as the as the PageRank score.

58
00:03:18,840 --> 00:03:22,640
So, one possible way to identify
spam would be the following.

59
00:03:22,640 --> 00:03:28,700
We take the set of trusted web pages, we
compute the personalized or topic-specific

60
00:03:28,700 --> 00:03:33,620
PageRank score with the teleport set
being the set of trusted web pages.

61
00:03:33,620 --> 00:03:36,800
And now, what we do is we compute
the PageRank score of all,

62
00:03:36,800 --> 00:03:38,600
every other page on the graph.

63
00:03:38,600 --> 00:03:41,420
And, if the,
if the PageRank score of some page on the,

64
00:03:41,420 --> 00:03:44,240
on the web graph is smaller
than some given threshold.

65
00:03:44,240 --> 00:03:48,940
Then, we go and cut that page
away from the, from our data set.

66
00:03:48,940 --> 00:03:51,490
And, we say that that corresponds to SPAM.

67
00:03:51,490 --> 00:03:55,630
The problem with this method though,
is that basically we go and cut away all

68
00:03:55,630 --> 00:04:00,440
the web pages that have low PageRank
scores with respect to the trusted set.

69
00:04:00,440 --> 00:04:03,225
And now, of course,
some web page on the web can have a low

70
00:04:03,225 --> 00:04:07,840
PageRank score because this web page
is new, and has just been born.

71
00:04:07,840 --> 00:04:12,370
Or, this webpage can have a low tr,
PageRank score because it's spam.

72
00:04:12,370 --> 00:04:15,990
So, the question is, can we,
why is this a good idea and maybe,

73
00:04:15,990 --> 00:04:17,870
can we later improve on this idea?

74
00:04:17,870 --> 00:04:23,220
So, let's first talk about why is this
idea of personalized PageRank score fr er,

75
00:04:23,220 --> 00:04:27,310
from a given trusted set of webpages
a good idea to detect link spam.

76
00:04:27,310 --> 00:04:30,040
So, first is,
notion is that we have this notion of

77
00:04:30,040 --> 00:04:33,140
trust attenuation where
the degree of trust conferred by

78
00:04:33,140 --> 00:04:37,160
a trusted page decreases with
the distance from that page in the graph.

79
00:04:37,160 --> 00:04:37,740
Right?
So, kind of

80
00:04:37,740 --> 00:04:42,860
farther away a given page is from the,
from the trusted set of pages, the lower,

81
00:04:42,860 --> 00:04:45,020
the lower the trust it receives will be.

82
00:04:45,020 --> 00:04:48,730
And, another important notion that also
works in our favor is the notion of

83
00:04:48,730 --> 00:04:49,570
trust splitting.

84
00:04:49,570 --> 00:04:51,645
Right?
Where the larger the number of

85
00:04:51,645 --> 00:04:56,380
out-links from a page, the less scrutiny
a page author gives to each out-link.

86
00:04:56,380 --> 00:05:00,010
In a sense, what this means is that,
if a page has lots of trust, but

87
00:05:00,010 --> 00:05:02,910
then has lots of out-links,
then this trust kind of gets

88
00:05:02,910 --> 00:05:08,170
split into these small chunks and
distributed over, over the target pages.

89
00:05:08,170 --> 00:05:08,750
Right?
And,

90
00:05:08,750 --> 00:05:12,540
this is exactly what is happening
in the topic specific PageRank,

91
00:05:12,540 --> 00:05:17,440
with trust trusted set of
webpages being the teleport set.

92
00:05:17,440 --> 00:05:22,200
So now, let's quickly discuss how do
we go in practice to pick a seed set.

93
00:05:22,200 --> 00:05:25,250
Picking a seed set, we have kind
of two conflicting considerations.

94
00:05:25,250 --> 00:05:29,160
In some sense, we would want to make
the seed set to be as small as possible.

95
00:05:29,160 --> 00:05:30,488
Why as small as possible?

96
00:05:30,488 --> 00:05:37,020
Because human labeling webpages are,
are trusted or not, is very expensive.

97
00:05:37,020 --> 00:05:39,890
So, we want to use as little
of human time as possible.

98
00:05:39,890 --> 00:05:42,240
On the other hand,
we would like in some sense,

99
00:05:42,240 --> 00:05:44,610
to be the seed set to
be as big as possible.

100
00:05:44,610 --> 00:05:48,280
Because we want to cover all
the good pages on the web.

101
00:05:48,280 --> 00:05:52,990
So, in, in a sense ideally we would
like to put every non-spam page into our

102
00:05:52,990 --> 00:05:53,660
seed set.

103
00:05:53,660 --> 00:05:55,880
But, that would mean the seed set is,
is huge.

104
00:05:55,880 --> 00:05:59,780
So, the question is, how do we balance
out these two kind of competing or

105
00:05:59,780 --> 00:06:01,690
con, conflicting, goals?

106
00:06:02,700 --> 00:06:04,520
The idea is the following, right?

107
00:06:05,650 --> 00:06:09,220
For example, imagine that we want
to select the seed set of k pages.

108
00:06:09,220 --> 00:06:10,559
One idea would be, for

109
00:06:10,559 --> 00:06:14,801
example, that we pick the k pages on
the web according to the PageRank.

110
00:06:14,801 --> 00:06:19,154
And, the hope is that this, the top,
small fraction of webpages pages on

111
00:06:19,154 --> 00:06:22,700
the web are really the,
the truly import pages on the web.

112
00:06:22,700 --> 00:06:25,510
And, we label those as the seed set.

113
00:06:25,510 --> 00:06:29,490
Another, another idea that I briefly
mentioned before is that we use a set of

114
00:06:29,490 --> 00:06:33,210
trusted domains whose menmership
is controlled by some

115
00:06:34,220 --> 00:06:35,270
that are set organizations.

116
00:06:35,270 --> 00:06:40,100
So, for example, .edu, .mil, or
.gov domains, these are the,

117
00:06:40,100 --> 00:06:43,060
these are the domains that not
just everyone can, can register.

118
00:06:43,060 --> 00:06:46,420
So, all the pages in these domains we
would trust them to be good pages and

119
00:06:46,420 --> 00:06:50,270
that are not spammy and don't spam,
don't, don't point to other spammy pages.

120
00:06:50,270 --> 00:06:54,170
So, one way to create a trusted
set of webpages would simply be to

121
00:06:54,170 --> 00:06:57,150
take all the web pages of these domains.

122
00:06:57,150 --> 00:07:00,170
What is also interesting now is
that we can actually take our

123
00:07:00,170 --> 00:07:04,260
initial idea of identifying web spam and
extend it a bit.

124
00:07:04,260 --> 00:07:09,490
And, we will extend it by creating
this notion of spam mass, right?

125
00:07:09,490 --> 00:07:11,490
So, the idea is the following.

126
00:07:11,490 --> 00:07:14,210
We will use the TrustRank as a model, and

127
00:07:14,210 --> 00:07:19,390
start with a good, a set of good
trusted pages, and propagate the trust.

128
00:07:19,390 --> 00:07:23,040
But now, we will flip our reasoning and

129
00:07:23,040 --> 00:07:27,070
we will kind of view,
use two complimentary views.

130
00:07:27,070 --> 00:07:28,730
Our goal will kind of be to ask,

131
00:07:28,730 --> 00:07:33,010
what fraction of page's PageRank
comes from the spam pages?

132
00:07:33,010 --> 00:07:34,000
Right?
So, what we would like to

133
00:07:34,000 --> 00:07:39,000
do is not to ask how, what is your
proximity to the trusted part of the web,

134
00:07:39,000 --> 00:07:41,900
but we would like to say what fraction or
estimate.

135
00:07:41,900 --> 00:07:46,320
What fraction of page rank score of
a given page comes from the spam?

136
00:07:47,490 --> 00:07:49,330
Right?
So, in practice we don't know

137
00:07:49,330 --> 00:07:53,440
the answer to this question,
but we need to estimate it.

138
00:07:53,440 --> 00:07:56,140
So, the way we can think about this
is the following we can think that we

139
00:07:56,140 --> 00:08:00,340
have our webpage that we are interested
in here as our F circle.

140
00:08:00,340 --> 00:08:04,270
We have a trusted set of webpages,
and we have the full web.

141
00:08:04,270 --> 00:08:08,650
And, our goal is to estimate
what fraction of page rank

142
00:08:08,650 --> 00:08:12,480
score of our red node here
comes from the spam pages.

143
00:08:12,480 --> 00:08:15,820
So, what we can do is proceed as follows.

144
00:08:15,820 --> 00:08:21,130
We can first go and compute r sub p,
where p is our red node,

145
00:08:21,130 --> 00:08:23,590
where r sub p is simply
the PageRank of our node p.

146
00:08:23,590 --> 00:08:26,750
And then,
we can also compute the r plus of p,

147
00:08:26,750 --> 00:08:29,000
which is the page rank of the same node.

148
00:08:29,000 --> 00:08:33,140
Where the teleport was done to
the trusted set of web pages.

149
00:08:33,140 --> 00:08:34,260
Right?

150
00:08:34,260 --> 00:08:39,570
And now, we can say that the spam mass
of a given web page is simply r p

151
00:08:39,570 --> 00:08:42,620
minus r, r plus p.

152
00:08:42,620 --> 00:08:46,740
What does this mean basically, is we say
we will compute the PageRank score of

153
00:08:46,740 --> 00:08:51,770
a page using the simple PageRank
where the teleportation is uniform.

154
00:08:51,770 --> 00:08:55,290
We will also compute the PageRank
score of a page where,

155
00:08:55,290 --> 00:08:58,950
where we always travel from
the trusted set of webpages.

156
00:08:58,950 --> 00:09:03,230
And now, with our webpage is, is really
spam, then this difference will be high.

157
00:09:03,230 --> 00:09:05,160
Right?
Basically, there is a lot of other web

158
00:09:05,160 --> 00:09:10,250
pages on the web that we don't trust that
reboost the importance of that page.

159
00:09:10,250 --> 00:09:15,510
So, this way, we can come, we can define
the notion of a spam mass of a, of a page,

160
00:09:15,510 --> 00:09:20,080
which is simply the ratio of the overall
PageRank score of the page and the,

161
00:09:20,080 --> 00:09:24,060
the amount of spam mass that
that page will receives.

162
00:09:24,060 --> 00:09:25,990
And, this way, we would, we could go and

163
00:09:25,990 --> 00:09:29,220
all the pages that have this spam mass,
fraction high.

164
00:09:29,220 --> 00:09:35,650
We would proclaim these pages as spam and
remove them from the, from our web corpus.

165
00:09:35,650 --> 00:09:39,690
And, this idea is, is better than
the first solution to our problem.

166
00:09:39,690 --> 00:09:43,630
Because here, the,
the question whether a, a page is spam or

167
00:09:43,630 --> 00:09:47,070
not, does not depend on the absolute
value of its PageRank score.

168
00:09:47,070 --> 00:09:50,810
But, kind of, it depends on the relative
value, when we compare how much Page Rank

169
00:09:50,810 --> 00:09:53,780
score of a page comes from
the trusted part of the web.

170
00:09:53,780 --> 00:09:57,730
And, how much of it's PageRank comes
from the un-trusted part of the web.

171
00:09:57,730 --> 00:10:00,930
And, the ratio between these two
quantities is tell us how spammy

172
00:10:00,930 --> 00:10:01,830
is a web page.