Showing posts with label gSpan. Show all posts
Showing posts with label gSpan. Show all posts

Saturday, April 25, 2015

How to Mine Frequent Patterns in Graphs with gSpan including a Walk-thru Example

In this blog post, I'm going to explain how the gSpan algorithm works for mining frequent patterns in graphs.  If you haven't already read my introductory post on this subject, please click HERE to read the post that lays the foundation for what will be described in this post.

Getting Started
To explain how this algorithm works, we're going to work through a simplified data set so that we can see each step and understand what is going on.  Suppose that you have 5 graphs that look like this

Don't get confused by the greek characters here.  I used random symbols to show that this method can be used for any type of graph (chemicals, internet web diagrams, etc.) even something completely made up like what I did above.  The first thing we need to do with this graph data set is count how many vertices and edges we have of each type.  I count 7 alpha(α) vertices, 8 beta(β) vertices, and 14 lambda(λ) vertices.  There are 15 edges that are solid blue, 13 that are double red, and 8 that are dotted green.  Now that we have these counts we need to order the original labels for vertices and edges into a code that will help us prioritize our search later.  To do this we create a code that starts with the vertices and edges with the highest counts and then descends like this


We could have used numbers instead of letters here, it doesn't really matter as long as you can keep track of the symbols' order based on frequency. If you relabel the graphs with this order you get something like this
You can see that the vertex labels now have A, B, C and each edge is labelled a, b, or c to match the new label legend we created.

Finding Frequent Edges
For this example we will assume that we have a minimum support frequency of 3 (i.e. 3 of the 5 graphs have to have the pattern for us to consider it important).  We start by looking at individual edges (e.g. A,b,A) and see if they meet this minimum support threshold.  I'll start by looking at the first graph at the top.  There is an edge that is (B,a,C) and I need to count how many of the graphs have an edge like this.  I can find it in the 1st graph, 2nd graph, 3rd graph, and 4th graph so it has support of 4; we'll keep that one.  Also notice that I had the option of writing that edge as (C,a,B) as well, but chose to write it with B as the starting vertex, because of the order we established above.  We move on a little and check (A,a,C) and find that it can only be found in the first graph; it gets dropped.  We check (A,c,C) and find it in the first 4 graphs as well; keep it.  If we continue going through all of the graphs being careful not to repeat any edge definitions we'll get a list of frequent single edges that looks like this

You can see that we only have 3 edges that are frequent (this will simplify our lives in this example greatly).  We need to sort the edges that are still frequent in DFS lexicographic order (See prior blog post for explanation of this).  After sorting we end up with this list of edges to consider going forward


Pay attention to the fact that I added the "0,1" to the beginning of these edge definitions.  These are the starting and ending points of the edges.  We'll "grow" the rest of the frequent sub-graphs from these edges in a way similar to the method described in my prior blog post on this subject.

gSpan starts with the "minimum" edge, in this case (0,1,A,b,B), and then tries to grow that edge as far as it can while looking for frequent sub-graphs.  Once we can't find any larger frequent sub-graphs that include that first edge, then we move on to the 2nd edge in the list above (0,1,A,c,C) and grow it looking for frequent sub-graphs.  One of the advantages of this is that we won't have to consider sub-graphs that include the first edge (0,1,A,b,B) once we've moved on to our 2nd edge because all of the sub-graphs with the first edge will have already been explored.  If you didn't follow that logic, it's OK; you'll see what I mean as we continue the example.

You might notice that the last graph in our set of graphs doesn't have any edges that are frequent.  When we're starting with edge (A,b,B) we keep track of which graphs have that edge present.  In our example that's graphs 1, 2, 3, & 4.  Now that we have that "recorded" we start the growth from (0,1,A,b,B) by generating all of the potential children off of the 'B' vertex.

Growing from the 1st Edge
Before we grow our first edge, you need to understand how gSpan prioritizes growth.  Let's assume that we have a generic subgraph that looks like this already (don't worry about how we got it yet, it will be come clear in a second)

I have removed the colors and labels from the diagram above to explain how gSpan grows without confusing you with labels.  The numbers represent the order the vertices were added.  If you are at this point in the algorithm, you will try to grow this graph in the following order of priority.


So the first priority is always to link the current end vertex back to the first vertex (the one labelled 0).  If that's not possible, we see if we can link it back to the 2nd vertex (the one labelled 1).  If we had a bigger sub-graph, we would continue trying to link to the 3rd, 4th, etc. if it's possible.  If none of those are possible then our next (3rd) priority is to grow from the vertex we're at (labelled 4 above), and grow the chain longer.  If that doesn't work, we go back to the most recent fork, take another step back and then try to grow from there (see how 5 is growing from vertex labelled 1 in the 4th priority).  If that doesn't work, then we take another step up the chain and try to grow from there (5th example above).  The 4th and 5th examples above also generalize for longer chains.  If there were several vertices above the closest fork in the chain, you would progressively try to grow off of each of those vertices until you get back to the root (vertex labelled '0').

With that understanding in mind, we can finally start growing from our first edge.  Our first edge is (0,1,A,b,B).  If we look at the priority explanation above, we can tell that the 1st and 2nd growth priorities are not really options, so we take the 3rd priority and try to grow from vertex 1, or the B vertex in our example.  Since we only have 2 frequent edges that have 'B' vertices in them our two options are as follows:

Option 1           Option 2
(0,1,A,b,B)       (0,1,A,b,B)
(1,2,B,b,A)       (1,2,B,a,C)

Now we are going to check for support of these 2 options.  We only need to look in the graphs that we determined contain the frequent edges as described earlier.  When we look for Option 1 we find it in the following graphs left that we're considering:


Notice that we can find the first option in 3 different places in the first graph, but we can't find it in any of the other graphs, so the support is only 1.  That's a dead end, so we check option 2


You can see that we can find this pattern in multiple places in all of the 4 graphs we have left (I didn't show all of the places it is found in the first graph).  The support for this sub-graph is 4 so it's a keeper.  Also, all 4 graphs we looked at have this sub-graph present so we keep those too.  That ends that round of edge growth so we take option 2 from above and try to grow from it.  Remembering the priorities of growth, we know we need to try to connect the last vertex (2 or 'C' in our example) to the root (0 or 'A' in our example) if we can.  If we look at the list of frequent edges to choose from, we see an edge that is (A,c,C) which could be written as (2,0,C,c,A).  This would make the connection we need.  None of the other frequent edges meet this criteria, so we check to see if (0,1,A,b,B); (1,2,B,a,C); (2,0,C,c,A) is frequent


This time this sub-graphs occurs twice in the 1st, 2nd and 4th graph.  It only occurs once in the 3rd graph.  Regardless, the support count for this sub-graph is still 4 so we've got a keeper again.  Now we have a graph that looks something like this.


Since we have already connected the last vertex ('C') to the root ('A') and to the vertex after it ('B'), our next priority is to grow from the last vertex we created.  The frequent edges we can try to add onto 'C' are (B,a,C) and (A,c,C).  However, since we're working from 'C' they would be better written this way: (2,3,C,a,B) and (2,3,C,c,A).  We'll start by checking if adding (2,3,C,a,B) works because it is the lowest in terms of DFS lexicographic order.  Here's what we find.


As it turns out, this 4 edge pattern can only be found in 2 of the 4 graphs we have left so that doesn't work.  Now we'll check if (2,3,C,c,A) works out.


Nope, that's only in the first graph so it's not frequent either.  Since neither of these worked out, we need to go to our next priority (4th) which is growing from the vertex a step up from the last attempted branch.  When you look at the sub-graph we've grown so far you can tell we need to try to grow from 'B' now.  That being said, we take a look at our options for frequent edges that contain 'B' vertices and we see that we should try to add (B,a,C) or (B,b,A).  Here's what trying to add (B,a,C) looks like in this scenario

Let's see if we can find that in any of the graphs


 As it turns out, we CAN find this sub-graph in 3 of the 4 graphs we have left so that's a keeper.  At this point in time I want you to notice that I am going to ignore the other edge that could grow from 'B' until later.  This is because gSpan is a depth first algorithm, so once you get success you try to go deeper.  When we hit a dead end, we will come back to all of these straggling options to see if they actually work.  If you're familiar with computer programming, this type of algorithm is implemented with recursion.  Our next step based on our priority rules is going to be to try to link our vertex 3 ('C') to the root, or the 'A'.  Again the only frequent edge we can choose from to do this is (C,c,A).  This option would look like this


At this point, remember that the last sub-graph that we found that was frequent could only be found in the first 3 graphs in our set, so now we only have to look for this new graph in those three graphs


This only exists in one of our graphs, so we go to our next growth priority.  Since there is already a link between our 'C' at vertex 3 and the 'B' and vertex 1, the 2nd priority isn't an option, so we try to grow/extend from the 'C' at vertex 3 again.  We can either add (C,a,B) or (C,c,A).  Adding (C,a,B) would look like this

If we look in the 3 graphs we have left we find this


That's a dead end because we only have 1 graph with this 5 edge sub-graph.  We back up and try adding (C,c,A) instead.  I'm not going to do the visuals for this, but it can't be found in any of the graphs we have left either.  Since we hit a dead end again here, we go to to our 5th priority growth option: growing from the root again.  If we try to grow from the root 'A' we can either use (A,b,B) or (A,c,C).  Starting with (A,b,B) we would get a sub-graph that looks like this


This can't be found in any of our graphs, so we try adding (A,c,C) as our last ditch effort


This can't be found either, so we have reached the end of this depth first search.  Now we need to go back and take care of the straggler options that we didn't pursue because we were going for depth first.  The last straggling option we left was when we were considering adding (B,b,A) to vertex 1.


Remember, at that point in time, we were still looking at 4 of the 5 original graphs so when we look for this sub-graph in those 4 graphs this is what we find.


We only find it in one graph, so that turns into a dead end too.

This Section Until "2nd Edge (A,c,C)" is a Correction (Thanks to Elife Öztürk) 
If we look back further in our algorithm we find that we also haven't checked all of the growth priorities off of the first frequent edge (0,1,A,b,B).  Our first growth came from using the 3rd priority growth strategy, but we haven't checked the 4th/5th priority grown strategies there yet.  If we do, we can see that it might be possible to make a link like (0,1,A,b,B) and (0,2,A,c,C).  Let's see if we can find that in the graphs



We can see that in all four of our remaining graphs so we'll keep this sub-graph.


Our first priority for growth on this sub-graph would be to connect back to the root, but we don't have any double bonds (sorry for the chemistry reference) in our example so that won't work.  The 2nd priority is also impossible, so let's check the 3rd.  Can we grow an edge off of the C node?  Our 2 options would be (2,3,C,a,B) and (2,3,C,c,A).  Adding (2,3,C,a,B) looks like this.



When we search through the graphs, we find this in 2 places

Notice that I'm not counting the instances in the 2nd and 3rd graphs.  This is because the only way you can get find this subgraph in those graphs is to wrap the graph such that the 1 B node is the same as the 3 B node.  The reason why we number the nodes is to make sure they're unique, plus we already found the sub-graph that creates that ABC triangle previously...thus the beauty of the algorithm :).  Since there are only 2 graphs with this sub-graph, the minimum support of 3 is not met.

So now let's check for the other growth option (2,3,C,c,A)

That can only be found in one of the graphs

So now we've exhausted our growth options off of the first edge (A,b,B).

2nd Edge (A,c,C)
Before you go crazy thinking that the other 2 edges we need to check will take just as long, let me tell you that we have already done WAY more than half of the work on this problem.  Now that we have exhaustively checked all of the graphs for frequent sub-graphs that contain the edge (A,b,B), we can trim down our search space significantly.  What I mean is we can delete edges in graphs that contain (A,b,B) and only look for frequent patterns in what is left.  If we do this, we get 4 graphs (remember we already got rid of graph 5 because it contained no frequent edges) that look like this.


These graphs are much simpler.  I also wanted to point out that I removed any edges from these graphs that were not frequent.  We could (should) have done this earlier when we were doing our search on the first edge, but I didn't want to complicate things at that time.  Now, much like last time, we start with edge (0,1,A,c,C) and try to grow from 'C'.  We can either use (1,2,C,a,B) or (1,2,C,c,A).  If we add (1,2,C,a,B) we can find that sub-graph in the following places


All 4 graphs have this sub-graphs, so it's a keeper and we'll go with it (remember we haven't checked adding (1,2,C,c,A) yet.  The next step is to try to grow from the last vertex back to the root.  If we did this we would have to use the edge (B,b,A), but that edge has been removed from all of our graphs because we have already mined all of the frequent sub-graphs with (A,b,B) in them.  So, our only other growth option is to try to extend the chain from 'B'.  The only option left to grow from 'B' is (B,a,C) because (B,b,A) has already been checked.  So we get a sub-graph like this.


This can be found in the following graphs


That's 3 out of the 4 graphs, which meets our support requirement so we'll keep it.  Our first growth priority from here is to link node 3 ('C') back to the root.  That would be adding a (3,0,C,_,A) link.  The only link possible for this in our data set is (3,0,C,c,A) which would give us this subgraph to look for

The only place this subgraph is found is in our 2nd example:

So, that's a dead end.  If we back up, our next growth priority would be to connect the C at node 3 back to the C at node 1.  A quick look at the graphs we have tells me that's not going to work.  The next priority after that is to add another node after node 3.  We could look for a subgraph with C,a,B added to the end that looks like this.


However, that subgraph is only found here:


So, we back up again and try our 4th priority, which is growing a link off of the B at node 2.  A quick look at the graphs above show that won't work.  Lastly, we'll try to grow further up the graph, like a new node coming off the C at node 2 or a new node off the A at node 0.  There's a couple options for growth off of node 2, but I can tell it's only supported by our first graph.  There are no additional options for growth from the root node 'A'. so we're done exploring this graph branch.

Now we need to step back to when we had the graph (0,1,A,c,C), (1,2,C,a,B) and try to grow again from there.  The last priority for growth for this subgraph is to grow from the root.  The only way we can grow from the root is to add (A,c,c), which would look like this.

Checking the four graphs we have left, we only find this sub-graph in our 2nd graph


Since this is only found in one place, it's a dead end and we need to backtrack to other options we didn't pursue earlier.  We only had one of those when we were adding our 2nd edge to (A,c,C).  So when we go back and try to add (1,2,C,c,A) to (0,1,A,c,C) we look at our graphs and find that it is only present in 2 of our graphs


As it turns out these are all of our options starting with edge (A,c,C).  See, I told you the 2nd edge would go faster than the first.

3rd Edge (B,a,C)
Now we have to check the last of our frequent edges to see if there is any way that we can grow a frequent sub-graph with just this edge.  Let's start by removing all of the (A,c,C) edges from our graphs to see what we're left with.


I could go through all of the same procedure I have been using for these remaining graphs, but it gets so simple at this point that there really isn't a reason to.  If you're using a program runing the gSpan algorithm, it will be disciplined and do the whole search though.  From what is left, we can see that (0,1,B,a,C); (0,2,B,a,C) is frequent, but anything larger doesn't work out.  We hit our last dead end and now we can report all of the sub-graphs that we found that were frequent.



I have them organized by the edge they were grown from.  The last thing we have to do is translate our DFS codes back to the original symbols.  This is easy enough and the user would get an output like this.


That's all there is to it.  I know that this post got a little long, but for me, being able to see the whole problem worked out helps me learn a TON.  I hope it helps somebody else out there too.  I did gloss over some details of the programming, etc. but this is essentially what's happening in gSpan.  Let me know if you have any additional questions.

Saturday, March 21, 2015

Graph Pattern Mining (gSpan) - Introduction

For those of you out there that follow this blog fairly regulary, you may have noticed that there has been a lull in the amount of posts recently.  This is not because I have not been working on my next post, it is because it has taken me quite some time to understand the topic described in this post.  That being said, I'm assuming (yes I know what happens when people assume) that for many of you out there, this topic would drain several precious hours of your life to understand as well.  So, I'm going to share what I've learned about the gSpan algorithm.  In this post I will lay the foundation by describing how data scientists create some sort of order out of all of the different possible graph configurations that can exist.  In my gSpan algorithm post, I'll describe how the information presented in this post is used to find frequent graph patterns.  The information in this post is based on "gSpan: Graph-Based Substructure Pattern Mining" by Xifeng Yan and Jiawei Han, September 3, 2002.

Graphs and why they're tricky to pattern mine
First of all, let's start SUPER simple.  What do people mean when they talk about finding patterns in graphs?  Let's just say that they aren't talking about something like this:


They are actually talking about some sort of visual representation of something, like this:


I have no idea what the graph above represents...I totally made it up.  But, it could look like a chemical composition diagram to some of you out there, or maybe a social network diagram, a family history tree...whatever.  Essentially, graphs are systems that have nodes (the A, B and C in the picture above) and connections between them (solid, dashed and double lines above).  In graph mining terminology they call a node a vertex and a connection an edge.  If you ask me why, I have no idea, but that random knowledge might help you if you ever decide to pick up a technical paper on the subject.

Now, if you have followed some of my previous posts on pattern mining (Apriori Basket Analysis, or Generalized Sequential Pattern Mining) you might look at that graph above and ask yourself, where do I start with that thing?  This is a major question that have vexed many mathematicians and data scientists.  Let's just start by stating the fact that, in general, when we're dealing with graphs, we don't really care about the orientation of the graph, or the how it "looks" per se; we really only care about what vertices are connected to each other and how.  As an example here's that first graph again, with some other equivalent graphs. 


You'll notice the term "Isomorphism" in that picture.  That's just a fancy way of saying those graphs are essentially the same as graph 1 if you only consider the vertices and edges, but rearranged to look different.  Since what we really want, is to be able to look for sub-graphs (or small subsets of the graphs in our database) and see if they are frequent, we would love to be able to create some sort of order for the graphs so we could kind of treat them like a sequential pattern.  In sequential pattern mining we represent patterns something like this <A,(B,C)D,E,(E,F)>.  There's a chronological order there: first A, then B and C, then D, then E, then E and F.  But with a graph, where do you start??? For example, I can number the vertices of graph 1 several different ways


First of all, make a note that the numbering starts with the number 0; this is referred to as the root.  Two of the variations above start at the C at the top (but is that really the "top"?)  One starts at the A in the lower left corner, and the last one starts at the B.  The order that the nodes are numbered can create a LOT of numbered graphs, but they're all different versions of the same thing.  What a data miner really needs is a way to create some sort of sequential order so that we always number graph nodes/vertices the same way and therefore don't waste a whole bunch of time dealing with graphs that might be numbered differently, but represent the same thing we already have.  Since, I'm focusing on the gSpan algorithm, I'm going to describe how DFS codes solve this problem.

DFS in DFS code stands for depth first search.  When we get into the gSpan algorithm, the reason for this will become more apparent, but for now just go with it.  A DFS code is just a way of documenting the vertices and edges of a graph in tabular form, but with special rules.   We'll represent each edge by defining 5 things.  Do do this, first we need to create codes for the features in our graphs.

With this coding system, we can turn the green edge in the 1st graph above into (0,1,C,c,B).  The 0 is for the starting vertex; the 1 is for the ending vertex; 'C' is for the starting vertex label/type; 'c' is for the edge label/type; and 'B' is for the ending vertex label/type.  The reason for having a code for both the vertex number and the vertex label is that if you're analysing a graph for frequent patterns, the vertex number doesn't give you much information about patterns, but we need it to keep track of where we are in the graph.  If you finish coding all of the edges in that first graph you might come up with something that looks like this.

Since you don't have any rules at this point to guide you, you could have just as easily come up with DFS codes that look like any of the DFS codes below...or more

All of these examples start from 0 in the lower left corner, but are very different.  It becomes obvious that we need to come up with a standardized way to order our graphs for several reasons; (1) so that we don't drive ourselves crazy comparing codes like the ones above only to realize they're the same graph, (2) to make is easier to find a subgraph we might think is frequent in many different graphs that will likely have very different configurations.  One of the things required to solve these problems is a set of rules called "Neighborhood Restriction"that limit the ways that we can create these lists of connections in our graphs.  These rules govern the order that you add edges to the list when you're creating codes for a graph.  The simplified English version of the rules listed in the technical paper go something like this.


  • If the first vertex of the current edge is less than the 2nd vertex of the current edge (forward edge)
    • If the first vertex of the next edge is less than the 2nd vertex of the next edge (forward edge)
      • If the first vertex of the next edge is less than or equal to the 2nd vertex of the current edge
      • AND If the 2nd vertex of the next edge is equal to the 2nd vertex of the current edge plus one this is an acceptable next edge
      • Otherwise the next edge being considered isn't valid
    • Otherwise (next edge is a backward edge)
      • If the first vertex of the next edge is equal to the 2nd vertex of the current edge
      • AND If the 2nd vertex of the next edge is less than the 1st vertex of the current edge this is an acceptable next edge
      • Otherwise the next edge being considered isn't valid
  • Otherwise (the current edge is a backward edge
    • If the first vertex of the next edge is less than the 2nd vertex of the next edge (forward edge)
      • If the first vertex of the next edge is less than or equal to the 1st vertex of the current edge
      • AND If the 2nd vertex of the next edge is equal to the 1st vertex of the current edge plus one this is an acceptable next edge
      • Otherwise the next edge being considered isn't valid
    • Otherwise (next edge is a backward edge)
      • If the first vertex of the next edge is equal to the 1st vertex of the current edge
      • AND If the 2nd vertex of the current edge is less than the 2nd vertex of the next edge this is an acceptable next edge
      • Otherwise the next edge being considered isn't valid
I know that's hard to follow, I'll walk you through one and give you the answers to a couple more of these.  It just so happens that Example 1 above meets all of these criteria. So, for (0,1,C,c,B) to (1,2,B,a,A) we see that 0,1 is a forward edge, and 1,2 is a forward edge.  so we need to make sure that the 1 in (1,2,B,a,A) is less than or equal to the 1 in (0,1,C,c,B)...check; AND, we need to make sure that the 2 in (1,2,B,a,A) is equal to the 1 in  (0,1,C,c,B) +1; 2 = 1+1...check. so the step from edge 0 to edge 1 is valid.

Let's do another one.  In example 1 still, (1,2,B,a,A) is a forward edge because 1 is less than 2 and (2,0,A,b,C) is a backward edge because 2 is greater than 0.  So we check if the 2 in (2,0,A,b,C) is equal to the 2 in (1,2,B,a,A)...check; AND we check if the 0 in (2,0,A,b,C) is less than the 1 in (1,2,B,a,A)...check.

If you keep going through Example 1, and the rest of the examples above, you'll see how hard it might be to create this type of order at random


I created example 1 to fit the rules on purpose.  Examples 2, 3 and 4 were created at random.  I was surprised to see how many edge steps I accidentally got right for those 3.

If you take some time and are careful, you can create several different DFS codes like example 1 that meet the neighborhood restriction rules, but are different from example 1.  Below are 3 examples (1, 5, and 6) that meet the rules.  To get these 2 other examples, I started at different locations in the graph.  The easiest way to get these patterns (and the method that is actually used in gSpan) is to do the following:  First you take a step forward, then try to make any backward connections possible connecting from smallest to largest (e.g. 3,0 comes before 3,1 if applicable).  Then, you take another step forward (e.g. 3,4) and repeat until you're done with the graph.


So, it appears we've gotten closer to figuring out the 1 way we should represent a graph, but we're not quite there.  To fix this problem the creators of the gSpan algorithm have an ordering system that will allow us to figure out if example 1 is "less than" example 5, or if example 5 is "less than" example 6.  This ordering system is great because once we have this, we just define THE representation of the graph (the one we'll be using in the gSpan algorithm) as the minimum DFS code possible.  This order is called DFS Lexicographic Order.  You may remember from other posts that lexicographic is just a fancy way of saying the order is going from smallest to largest (e.g. 1,2,3 or A, B, C...).  To do this we also make use of the fact that we have given codes to our vertex types and edge types.  Remember how the blue circles in our examples are 'A', and the dotted green lines are 'c'?  'A' is a vertex label and 'c' is an edge label.  Here's the rules that govern this order that will help us get our "minimum" DFS code; I'm going to write it in a very simplified pseudo-code format.

Let X be the one version of the graph's DFS code Y be another version for the same graph
Assume that X > Y to start
Start by comparing the first edge (edge 0) of both DFS codes
Start a loop for comparisons going through all the edges
   
   Check each of the following rules; if one applies, set X < Y and exit the loop

  1. Is X a backward edge and Y a forward edge?
  2. Is X a backward edge, Y a backward edge, and the 2nd vertex of X < 2nd vertex of Y?
  3. Is X a backward edge, Y a backward edge, 2nd vertex of X = 2nd vertex of Y, and the edge label of X is less than the edge label of Y?
  4. Is X a forward edge, Y a forward edge, the 1st vertex of Y < the 1st vertex of X
  5. Is X a forward edge, Y a forward edge, the 1st vertex of X = the 1st vertex of Y, and the label for the first vertex of X is less than the label for the first vertex of Y?
  6. Is X a forward edge, Y a forward edge, the 1st vertex of X = the 1st vertex of Y, the first vertex label of X = the first vertex label of Y, and the edge label for X is less than the edge label for Y?
  7. Is X a forward edge, Y a forward edge, the 1st vertex of X = the 1st vertex of Y, the first vertex label of X = the first vertex label of Y, the edge label for X = the edge label for Y, and the 2nd vertex label of X < the 2nd vertex label of Y?

   If you've made it to this section of code, you haven't proven that A is less than B yet
   If there's another edge left in the graph to check, increment up one edge (e.g. go from edge 0 to 1)
   
End Loop

Again, like a lot of things in data mining, this might look complex, but when you see it in a couple of examples it is pretty easy to follow.  If we apply this to Example 1, 5, and 6 above you'll see what I mean.

Let's let example 1 be DFS code X and example 5 be DFS code Y in the code above.  For the first edge, they are both forward edges with 0,1.  So, rules 1 through 4 in the code don't apply.  When we look at rule 5, we see that the 'C' in (0,1,C,c,B) is "greater than" the 'A' in (0,1,A,a,B) so rule 5 doesn't apply either.  Because the first vertex label 'C' and 'A' aren't equal, rules 6 & 7 don't apply.  So, comparing the first edge (edge 0) didn't give us the answer.  We move on to the next edge (edge 1).  For X we have (1,2,B,a,A) and for Y we have (1,2,B,c,C).  The first two items match and they're forward edges so we jump all the way down to rule 5.  We see that the first vertex labels match too so we go to rule 6.  When we look at rule 6 we see that the edge 'a' is "less than" the edge 'c' so we get to say that X<Y, or Example 1 is "less than" Example 5.  We don't have to check the rest of the edges because we break out of the loop once we find just one example of one of the 7 rules being met.

Let's compare example 5 (X) and example 6 (Y).  Starting at edge 0, we see that they're both forward edges with (0,1,...), so rules 1-4 don't apply.  When we look at rule 5 we see that the 'A' from (0,1,A,a,B) is "less than" the 'B' from (0,1,B,c,C) which satisfies rule 5.  This makes example 5 "less than" example 6; the loop breaks and we have our answer.

So, for our 3 examples, we know that example 1 < example 5 and example 5 < example 6.  Just like other places where inequalities are used, this information tells us that example 1 < example 6, or to be complete example 1 < example 5 < example 6.

With the information and understanding we've covered in this post we are armed to tackle the gSpan algorithm itself.  When I complete that blog post, I'll add a link to it right HERE.  Hope this helps somebody out there!