[MUSIC]. 
And so, the final category of graphing 
all these tasks are these 
pattern-matching tasks. 
And this is where we want to maybe spend 
a little bit of time, especially because 
they're somewhat relevant in the news 
lately with this prison system. 
And I'll try to touch on that in a bit. 
Okay. 
So, here are the ideas to find all 
instances of a particular sub graph 
pattern. 
And so, a very simple sub graph here is 
two [INAUDIBLE] vertices that both 
connect to each other. 
Okay. 
And so, here you may have conditions on 
the vertex labels or on the edge labels 
in order to more precisely specify the 
exact pattern you're looking for. 
But you're looking for all instances of 
this pattern across the graph. 
Okay? 
So, how many times has this pattern 
appeared in this graph, or what are all 
the instances in this graph. 
How can you instantiate this pattern, 
there. 
Well, here is one from A to B, you 
instantiate $x equals a and $y equals b. 
And that seems to fit. 
And then, g to c seems to fit. 
$x equals c and $y equals g. 
And then actually, if we're not careful, 
you have, or perhaps this is what you 
want, but generally you don't, you'll 
have duplicates of this where $x can be 
b, and $y will be a. 
Whoops. 
[UNKNOWN] will be a, and $x will be g. 
And $y will be c. 
So, there'll be four instances of this 
pattern, only two of which are in some 
sense unique. 
So, popular pattern matching problem is 
to find the triangles in a graph. 
And so, triangle is a sequence of 
vertices that are connected to each 
other. 
So a connects to b, b connects to c, and 
c connects back to a. 
And so, the total number of triangles is 
a measure of connectedness. 
There's lots of algorithms to compute 
this measure to count the number of 
triangles. 
And it's a popular challenge problem, 
kind of benchmark for computer scientists 
to compare different systems and compare 
different algorithms. 
It's utility in practice as far as 
actually analyzing you know, getting 
information out of a graph is not been 
made so clear to me when, when I talk to 
people who compute this. 
This seems to be more of a again a good 
benchmark problem for systems as opposed 
to a actual informative measure for a 
social network analysis. 
But, that doesn't mean, that's not to say 
that it's not used ever. 
So, I'm not going to, for that reason I'm 
not going to go into a lot of detail in 
the algorithms here. 
But a key idea to remember here is that, 
is that a naive algorithm will actually 
find the same triangle three times. 
Right? 
A connects to b, b connects to c, and c 
connects back a, and then bcab and then 
cabc. 
are all logically the same triangle in 
that they involves the same nodes, but if 
you're not careful you'll find these, all 
of these. 
And so, this gives an opportunity to have 
come up with much faster algotirhtms. 
I think the other reason it's studied in 
a lot of detail is that it's the 
simplest, perhaps the simplest possible 
pattern you can find. 
So, it's a good starting point to do more 
complicated pattern analysis. 
And in fact, the pattern analysis problem 
in general is a very difficult problem. 
It's a very expensive problem, which 
leads to a bunch of approximation 
techniques. 
And if i did it for triangles, there is a 
variety of algorithms that don't count 
the exact number of triangles, but give 
you a good approximation with certain 
bounds. 
Okay. 
So, this is a very rich area of research. 
But I, I think probably you'd be more 
interested in the pattern matching 
problem in general. 
Okay. 
And also maybe I'll point out that you 
can extend this notion to cycles that 
involve more than four vertices, more 
than three vertices. 
and things change a little bit, but some 
of the techniques stay the same. 
So, let's look at another pattern 
matching example. 
This one's a simplified version of a real 
example that comes from work with some of 
our collaborators. 
Okay. 
So, here, you know, given a graph with 
edge labels is the extension we're 
going to make, instead of just source 
node, source vertex and target vertex. 
We're going to assume that there's going 
to be an, a label on that edge as well. 
So, a third attribute in this table if 
you will. 
And we're going to be looking at rela, 
what this label represents is 
relationships like an object. 
You know, someone knows someone else, and 
in this case, drug x interferes with drug 
y. 
And so, that label is interferes. 
So, you sort of know what the 
relationship is, instead of it being a 
big anonymous relationships. 
Or say in the case of Twitter, where you 
assume that all relationships are the 
same, it's just follows. 
Or in Facebook, every relationship is 
just friends. 
Or in the web, every relationship is just 
links to. 
This one now there are multiple different 
relationships being encoded in the same 
graph. 
Okay. 
And so, this is a slightly more realistic 
case when you're trying to do real data 
analysis. 
Alright. 
So, here we might say that drug x 
interferes with drug y, and drug y, y 
regulates the expression of gene Z, and 
gene Z is associated with disease w. 
And so, now, maybe a co, one pattern that 
we want to look for is, find all drugs 
that interfere with some other drug that 
is involved in the treatment of some 
disease. 
Okay. 
And of course, you could put other 
restrictions on here, too. 
Or maybe you're looking for a specific 
disease, or you're looking for a specific 
drug, but now we're just looking for all 
patterns of this type. 
Okay. 
So, pictorially, the query may look like 
this where you know, we want to find an 
edge linking two vertices that's labeled 
with interferes with. 
That's then connected one of the out 
going edges y is connected to vertex Z 
through an edge labeled with regulates. 
And then that vertex Z is connected with 
a vertex w through an edge labeled with 
associated_with. 
Okay. 
And we want to find all instantiations of 
this pattern, alright. 
So, I'm not going to yet talk about 
algorithms to do this, I want to talk 
more about languages to express this 
pattern. 
And some of you with a database 
background may already be thinking about 
how you might view this in SQL, and 
that's one of the examples I want to 
show. 
So, the first pattern language I want to 
consider is SPARQL, which is a query 
language derived, sort of Sequel-like 
derived in association with this resource 
description framework. 
And you've worked with some of this data 
in the elastic MapReduce assignment if 
you completed it. 
So, Resource Description Framework, RDF 
defines a formal data model around the 
idea of triples, which are really just 
edges in a graph, labeled edges in a 
graph. 
And so, you logically you can think about 
a table with three columns: subject, 
predicate and object. 
And the subject column refers to vertices 
in the graph and the object column refers 
to vertices in the graph, and the 
predicate is the edge label, okay. 
And so, there's a lot of work that went 
into the formal model to define this, but 
I think it's most useful to just think of 
it as a labelled graph. 
Alright. 
And so, the query language ends up 
looking like this, where you can say 
select variable names where, and then 
define these triple patterns. 
And in this case all the triple patterns 
look similar, in that they all 
instantiate the predicate with a actual 
literal and all the vertices are 
variables. 
But you don't have to do this. 
You could have a variable in place of the 
predicate, and you can could have 
literals in the place of the vertex 
representations as well. 
Okay. 
So, this says, give me all the x's such 
that x interferes with y, y regulates z, 
and z is associated with w. 
And so, if this was actually our data 
set, then we might return this invented 
drug named terazine because we can trace 
a path. 
Terazine interferes with betamin, betamin 
regulates this gene, and this gene is 
associated with this disease. 
Okay. 
And there might be you know, billions of 
these triples. 
Let me give you another example of a 
pattern expression language that comes up 
in database courses in computer science, 
but is less often seen in industry. 
Although, it's starting to make a 
comeback, which is one of the reasons I 
want to mention it to you to make sure 
that you're aware of it. 
Okay. 
So it's called datalog. 
And it's based on a logic programming 
sort of paradigm but simpler than general 
purpose logic programming language such 
as prolog. 
Okay. 
So, here to express our query in datalog, 
we assume a relation R, which is just the 
same structure as the triple table we saw 
on the first article. 
Okay. 
And I'll show you another formulation in 
the next slide. 
So, here the pattern, the syntax here 
looks not all that different than 
Sparkle. 
For each, predicate we, we have an 
instance of R, and we are looking for, 
give me all the x's such that x 
interferes with y. 
Y regulates z and z is associated with w. 
And we use three instances of this 
relation R. 
And it's essentially going to be 
interpreted as a join. 
That's liter, that's literally how it's 
going to be implemented in most data log 
systems. 
Okay. 
So, you're going to join R on y equals y. 
Join R again on z equals z. 
And then returns the instatiations of the 
variable z. 
Now, so, you've got a relation r with 
three attributes you know, why can't you 
query this in SQL, and there's no reason, 
you can query in SQL. 
So, you can imagine loading this table 
into a database and rewriting this query 
like this, where you say. 
[UNKNOWN] three way join on the relation 
R and I've given them aliases here: i for 
interfused with r for regulation a for 
associated with. 
Then for each one of these relations make 
sure you filter to the tuples that 
coorespond to the predicate that you're 
interested in. 
So make sure the i tuples are only those 
tuples that have the predicate equal 
interferes with, and so on for regulates 
and so on for associated with. 
And then you have to add a couple 
conditions for the join. 
Make sure that the object of the i 
relation is equal to the subject of the 
regulates relation. 
And make sure that the object of the 
regulates relation is equal to the 
subject of the associated with relation. 
And then finally just return the subject 
of interferes, relation. 
So, all these things are equivalent, and 
that's, one of the points I want to make, 
but I'll come back to that in a minute.