1
23:59:59,962 --> 00:00:05,475
[MUSIC]. 

2
00:00:05,475 --> 00:00:07,807
And so, the final category of graphing 
all these tasks are these 

3
00:00:07,807 --> 00:00:10,903
pattern-matching tasks. 
And this is where we want to maybe spend 

4
00:00:10,903 --> 00:00:14,003
a little bit of time, especially because 
they're somewhat relevant in the news 

5
00:00:14,003 --> 00:00:18,980
lately with this prison system. 
And I'll try to touch on that in a bit. 

6
00:00:18,980 --> 00:00:20,681
Okay. 
So, here are the ideas to find all 

7
00:00:20,681 --> 00:00:23,510
instances of a particular sub graph 
pattern. 

8
00:00:23,510 --> 00:00:27,292
And so, a very simple sub graph here is 
two [INAUDIBLE] vertices that both 

9
00:00:27,292 --> 00:00:29,838
connect to each other. 
Okay. 

10
00:00:29,838 --> 00:00:33,678
And so, here you may have conditions on 
the vertex labels or on the edge labels 

11
00:00:33,678 --> 00:00:39,040
in order to more precisely specify the 
exact pattern you're looking for. 

12
00:00:39,040 --> 00:00:41,992
But you're looking for all instances of 
this pattern across the graph. 

13
00:00:41,992 --> 00:00:44,465
Okay? 
So, how many times has this pattern 

14
00:00:44,465 --> 00:00:47,320
appeared in this graph, or what are all 
the instances in this graph. 

15
00:00:47,320 --> 00:00:50,881
How can you instantiate this pattern, 
there. 

16
00:00:50,881 --> 00:01:00,500
Well, here is one from A to B, you 
instantiate $x equals a and $y equals b. 

17
00:01:00,500 --> 00:01:06,296
And that seems to fit. 
And then, g to c seems to fit. 

18
00:01:06,296 --> 00:01:18,748
$x equals c and $y equals g. 
And then actually, if we're not careful, 

19
00:01:18,748 --> 00:01:23,832
you have, or perhaps this is what you 
want, but generally you don't, you'll 

20
00:01:23,832 --> 00:01:30,704
have duplicates of this where $x can be 
b, and $y will be a. 

21
00:01:30,704 --> 00:01:35,540
Whoops. 
[UNKNOWN] will be a, and $x will be g. 

22
00:01:37,970 --> 00:01:42,232
And $y will be c. 
So, there'll be four instances of this 

23
00:01:42,232 --> 00:01:46,400
pattern, only two of which are in some 
sense unique. 

24
00:01:48,280 --> 00:01:51,871
So, popular pattern matching problem is 
to find the triangles in a graph. 

25
00:01:51,871 --> 00:01:54,664
And so, triangle is a sequence of 
vertices that are connected to each 

26
00:01:54,664 --> 00:01:56,942
other. 
So a connects to b, b connects to c, and 

27
00:01:56,942 --> 00:02:00,818
c connects back to a. 
And so, the total number of triangles is 

28
00:02:00,818 --> 00:02:04,820
a measure of connectedness. 
There's lots of algorithms to compute 

29
00:02:04,820 --> 00:02:06,971
this measure to count the number of 
triangles. 

30
00:02:06,971 --> 00:02:09,691
And it's a popular challenge problem, 
kind of benchmark for computer scientists 

31
00:02:09,691 --> 00:02:13,530
to compare different systems and compare 
different algorithms. 

32
00:02:13,530 --> 00:02:16,290
It's utility in practice as far as 
actually analyzing you know, getting 

33
00:02:16,290 --> 00:02:19,142
information out of a graph is not been 
made so clear to me when, when I talk to 

34
00:02:19,142 --> 00:02:23,060
people who compute this. 
This seems to be more of a again a good 

35
00:02:23,060 --> 00:02:26,162
benchmark problem for systems as opposed 
to a actual informative measure for a 

36
00:02:26,162 --> 00:02:30,712
social network analysis. 
But, that doesn't mean, that's not to say 

37
00:02:30,712 --> 00:02:33,479
that it's not used ever. 
So, I'm not going to, for that reason I'm 

38
00:02:33,479 --> 00:02:36,751
not going to go into a lot of detail in 
the algorithms here. 

39
00:02:36,751 --> 00:02:40,001
But a key idea to remember here is that, 
is that a naive algorithm will actually 

40
00:02:40,001 --> 00:02:42,890
find the same triangle three times. 
Right? 

41
00:02:42,890 --> 00:02:46,610
A connects to b, b connects to c, and c 
connects back a, and then bcab and then 

42
00:02:46,610 --> 00:02:51,345
cabc. 
are all logically the same triangle in 

43
00:02:51,345 --> 00:02:54,726
that they involves the same nodes, but if 
you're not careful you'll find these, all 

44
00:02:54,726 --> 00:02:58,128
of these. 
And so, this gives an opportunity to have 

45
00:02:58,128 --> 00:03:02,190
come up with much faster algotirhtms. 
I think the other reason it's studied in 

46
00:03:02,190 --> 00:03:05,190
a lot of detail is that it's the 
simplest, perhaps the simplest possible 

47
00:03:05,190 --> 00:03:09,012
pattern you can find. 
So, it's a good starting point to do more 

48
00:03:09,012 --> 00:03:13,110
complicated pattern analysis. 
And in fact, the pattern analysis problem 

49
00:03:13,110 --> 00:03:16,241
in general is a very difficult problem. 
It's a very expensive problem, which 

50
00:03:16,241 --> 00:03:18,670
leads to a bunch of approximation 
techniques. 

51
00:03:18,670 --> 00:03:21,368
And if i did it for triangles, there is a 
variety of algorithms that don't count 

52
00:03:21,368 --> 00:03:23,838
the exact number of triangles, but give 
you a good approximation with certain 

53
00:03:23,838 --> 00:03:25,910
bounds. 
Okay. 

54
00:03:25,910 --> 00:03:31,500
So, this is a very rich area of research. 
But I, I think probably you'd be more 

55
00:03:31,500 --> 00:03:34,715
interested in the pattern matching 
problem in general. 

56
00:03:34,715 --> 00:03:37,631
Okay. 
And also maybe I'll point out that you 

57
00:03:37,631 --> 00:03:40,214
can extend this notion to cycles that 
involve more than four vertices, more 

58
00:03:40,214 --> 00:03:44,168
than three vertices. 
and things change a little bit, but some 

59
00:03:44,168 --> 00:03:48,642
of the techniques stay the same. 
So, let's look at another pattern 

60
00:03:48,642 --> 00:03:51,518
matching example. 
This one's a simplified version of a real 

61
00:03:51,518 --> 00:03:55,495
example that comes from work with some of 
our collaborators. 

62
00:03:55,495 --> 00:03:57,118
Okay. 
So, here, you know, given a graph with 

63
00:03:57,118 --> 00:03:59,728
edge labels is the extension we're 
going to make, instead of just source 

64
00:03:59,728 --> 00:04:03,949
node, source vertex and target vertex. 
We're going to assume that there's going 

65
00:04:03,949 --> 00:04:07,799
to be an, a label on that edge as well. 
So, a third attribute in this table if 

66
00:04:07,799 --> 00:04:10,877
you will. 
And we're going to be looking at rela, 

67
00:04:10,877 --> 00:04:16,030
what this label represents is 
relationships like an object. 

68
00:04:16,030 --> 00:04:20,032
You know, someone knows someone else, and 
in this case, drug x interferes with drug 

69
00:04:20,032 --> 00:04:22,760
y. 
And so, that label is interferes. 

70
00:04:22,760 --> 00:04:24,905
So, you sort of know what the 
relationship is, instead of it being a 

71
00:04:24,905 --> 00:04:28,106
big anonymous relationships. 
Or say in the case of Twitter, where you 

72
00:04:28,106 --> 00:04:31,572
assume that all relationships are the 
same, it's just follows. 

73
00:04:31,572 --> 00:04:34,049
Or in Facebook, every relationship is 
just friends. 

74
00:04:34,049 --> 00:04:36,526
Or in the web, every relationship is just 
links to. 

75
00:04:36,526 --> 00:04:39,769
This one now there are multiple different 
relationships being encoded in the same 

76
00:04:39,769 --> 00:04:40,919
graph. 
Okay. 

77
00:04:40,919 --> 00:04:43,955
And so, this is a slightly more realistic 
case when you're trying to do real data 

78
00:04:43,955 --> 00:04:45,762
analysis. 
Alright. 

79
00:04:45,762 --> 00:04:50,074
So, here we might say that drug x 
interferes with drug y, and drug y, y 

80
00:04:50,074 --> 00:04:57,740
regulates the expression of gene Z, and 
gene Z is associated with disease w. 

81
00:04:57,740 --> 00:05:00,654
And so, now, maybe a co, one pattern that 
we want to look for is, find all drugs 

82
00:05:00,654 --> 00:05:03,662
that interfere with some other drug that 
is involved in the treatment of some 

83
00:05:03,662 --> 00:05:07,430
disease. 
Okay. 

84
00:05:07,430 --> 00:05:09,110
And of course, you could put other 
restrictions on here, too. 

85
00:05:09,110 --> 00:05:11,991
Or maybe you're looking for a specific 
disease, or you're looking for a specific 

86
00:05:11,991 --> 00:05:15,343
drug, but now we're just looking for all 
patterns of this type. 

87
00:05:15,343 --> 00:05:16,872
Okay. 
So, pictorially, the query may look like 

88
00:05:16,872 --> 00:05:19,407
this where you know, we want to find an 
edge linking two vertices that's labeled 

89
00:05:19,407 --> 00:05:22,208
with interferes with. 
That's then connected one of the out 

90
00:05:22,208 --> 00:05:25,390
going edges y is connected to vertex Z 
through an edge labeled with regulates. 

91
00:05:34,680 --> 00:05:38,515
And then that vertex Z is connected with 
a vertex w through an edge labeled with 

92
00:05:38,515 --> 00:05:40,970
associated_with. 
Okay. 

93
00:05:40,970 --> 00:05:46,143
And we want to find all instantiations of 
this pattern, alright. 

94
00:05:46,143 --> 00:05:48,838
So, I'm not going to yet talk about 
algorithms to do this, I want to talk 

95
00:05:48,838 --> 00:05:51,733
more about languages to express this 
pattern. 

96
00:05:51,733 --> 00:05:54,673
And some of you with a database 
background may already be thinking about 

97
00:05:54,673 --> 00:05:57,417
how you might view this in SQL, and 
that's one of the examples I want to 

98
00:05:57,417 --> 00:06:01,024
show. 
So, the first pattern language I want to 

99
00:06:01,024 --> 00:06:04,930
consider is SPARQL, which is a query 
language derived, sort of Sequel-like 

100
00:06:04,930 --> 00:06:10,090
derived in association with this resource 
description framework. 

101
00:06:10,090 --> 00:06:12,928
And you've worked with some of this data 
in the elastic MapReduce assignment if 

102
00:06:12,928 --> 00:06:16,160
you completed it. 
So, Resource Description Framework, RDF 

103
00:06:16,160 --> 00:06:19,616
defines a formal data model around the 
idea of triples, which are really just 

104
00:06:19,616 --> 00:06:23,019
edges in a graph, labeled edges in a 
graph. 

105
00:06:23,019 --> 00:06:26,529
And so, you logically you can think about 
a table with three columns: subject, 

106
00:06:26,529 --> 00:06:30,397
predicate and object. 
And the subject column refers to vertices 

107
00:06:30,397 --> 00:06:33,691
in the graph and the object column refers 
to vertices in the graph, and the 

108
00:06:33,691 --> 00:06:38,586
predicate is the edge label, okay. 
And so, there's a lot of work that went 

109
00:06:38,586 --> 00:06:42,338
into the formal model to define this, but 
I think it's most useful to just think of 

110
00:06:42,338 --> 00:06:46,366
it as a labelled graph. 
Alright. 

111
00:06:46,366 --> 00:06:50,600
And so, the query language ends up 
looking like this, where you can say 

112
00:06:50,600 --> 00:06:56,588
select variable names where, and then 
define these triple patterns. 

113
00:06:56,588 --> 00:07:00,938
And in this case all the triple patterns 
look similar, in that they all 

114
00:07:00,938 --> 00:07:05,513
instantiate the predicate with a actual 
literal and all the vertices are 

115
00:07:05,513 --> 00:07:09,282
variables. 
But you don't have to do this. 

116
00:07:09,282 --> 00:07:12,271
You could have a variable in place of the 
predicate, and you can could have 

117
00:07:12,271 --> 00:07:16,475
literals in the place of the vertex 
representations as well. 

118
00:07:16,475 --> 00:07:21,117
Okay. 
So, this says, give me all the x's such 

119
00:07:21,117 --> 00:07:27,090
that x interferes with y, y regulates z, 
and z is associated with w. 

120
00:07:27,090 --> 00:07:30,933
And so, if this was actually our data 
set, then we might return this invented 

121
00:07:30,933 --> 00:07:34,904
drug named terazine because we can trace 
a path. 

122
00:07:34,904 --> 00:07:39,392
Terazine interferes with betamin, betamin 
regulates this gene, and this gene is 

123
00:07:39,392 --> 00:07:42,515
associated with this disease. 
Okay. 

124
00:07:42,515 --> 00:07:45,515
And there might be you know, billions of 
these triples. 

125
00:07:45,515 --> 00:07:49,805
Let me give you another example of a 
pattern expression language that comes up 

126
00:07:49,805 --> 00:07:55,750
in database courses in computer science, 
but is less often seen in industry. 

127
00:07:55,750 --> 00:07:57,490
Although, it's starting to make a 
comeback, which is one of the reasons I 

128
00:07:57,490 --> 00:07:59,797
want to mention it to you to make sure 
that you're aware of it. 

129
00:07:59,797 --> 00:08:01,233
Okay. 
So it's called datalog. 

130
00:08:01,233 --> 00:08:05,787
And it's based on a logic programming 
sort of paradigm but simpler than general 

131
00:08:05,787 --> 00:08:10,135
purpose logic programming language such 
as prolog. 

132
00:08:10,135 --> 00:08:12,424
Okay. 
So, here to express our query in datalog, 

133
00:08:12,424 --> 00:08:16,243
we assume a relation R, which is just the 
same structure as the triple table we saw 

134
00:08:16,243 --> 00:08:19,664
on the first article. 
Okay. 

135
00:08:19,664 --> 00:08:22,060
And I'll show you another formulation in 
the next slide. 

136
00:08:22,060 --> 00:08:26,028
So, here the pattern, the syntax here 
looks not all that different than 

137
00:08:26,028 --> 00:08:29,708
Sparkle. 
For each, predicate we, we have an 

138
00:08:29,708 --> 00:08:34,163
instance of R, and we are looking for, 
give me all the x's such that x 

139
00:08:34,163 --> 00:08:41,230
interferes with y. 
Y regulates z and z is associated with w. 

140
00:08:41,230 --> 00:08:43,130
And we use three instances of this 
relation R. 

141
00:08:43,130 --> 00:08:46,070
And it's essentially going to be 
interpreted as a join. 

142
00:08:46,070 --> 00:08:48,800
That's liter, that's literally how it's 
going to be implemented in most data log 

143
00:08:48,800 --> 00:08:50,160
systems. 
Okay. 

144
00:08:50,160 --> 00:08:55,651
So, you're going to join R on y equals y. 
Join R again on z equals z. 

145
00:08:55,651 --> 00:09:01,382
And then returns the instatiations of the 
variable z. 

146
00:09:01,382 --> 00:09:04,070
Now, so, you've got a relation r with 
three attributes you know, why can't you 

147
00:09:04,070 --> 00:09:07,460
query this in SQL, and there's no reason, 
you can query in SQL. 

148
00:09:07,460 --> 00:09:13,268
So, you can imagine loading this table 
into a database and rewriting this query 

149
00:09:13,268 --> 00:09:18,430
like this, where you say. 
[UNKNOWN] three way join on the relation 

150
00:09:18,430 --> 00:09:21,680
R and I've given them aliases here: i for 
interfused with r for regulation a for 

151
00:09:21,680 --> 00:09:25,890
associated with. 
Then for each one of these relations make 

152
00:09:25,890 --> 00:09:28,060
sure you filter to the tuples that 
coorespond to the predicate that you're 

153
00:09:28,060 --> 00:09:31,000
interested in. 
So make sure the i tuples are only those 

154
00:09:31,000 --> 00:09:34,250
tuples that have the predicate equal 
interferes with, and so on for regulates 

155
00:09:34,250 --> 00:09:37,967
and so on for associated with. 
And then you have to add a couple 

156
00:09:37,967 --> 00:09:40,908
conditions for the join. 
Make sure that the object of the i 

157
00:09:40,908 --> 00:09:45,280
relation is equal to the subject of the 
regulates relation. 

158
00:09:45,280 --> 00:09:48,122
And make sure that the object of the 
regulates relation is equal to the 

159
00:09:48,122 --> 00:09:54,468
subject of the associated with relation. 
And then finally just return the subject 

160
00:09:54,468 --> 00:09:59,214
of interferes, relation. 
So, all these things are equivalent, and 

161
00:09:59,214 --> 00:10:02,750
that's, one of the points I want to make, 
but I'll come back to that in a minute.