# Merging two disconnected graphs

Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's.

I have two disconnected, directed graphs that I am attempting to merge together. Each node in the graph represents a set of data. Each edge is a member of the data set that is used by the kernel.

For each node in DG1 I am comparing it to each node in DG2 into graph DG3. I compare the data sets of the node via a kernel and determine a similarity confidence. Beyond a given confidence I can merge the two nodes into DG3.

The issue that I'm having is, let's consider two sets of nodes in each of DG1 and DG2 such that:

DG1,N1 -> DG1,N2 (Node1 of Disconnected Graph 1 connects to Node2 of Disconnected Graph 1)

DG2,N1 -> DG2,N2

When trying to determine if DG1,N1 and DG2,N1 are similar, I need to take into account their connections. If DG1,N2 and DG2,N2 are to be merged (or similar enough), then that makes it more likely that DG1,N1 and DG2,N1 are similar. If DG1,N2 and DG2,N2 are not similar, then it makes it less likely that DG1,N1 and DG2,N1 are similar.

If this is the only connection it's relatively trivial. If the kernel is a function the ratio of the sum the similarities for each property in each node to the sum of all properties in both nodes, then I can just add the resulting value of kernel(<DG1,N2> ,<DG2,N2>) (where '1' would be the result if they are identical).

The problem that I have is (and I bet this is a common one), what to do with cycles? In this instance, where:

DG1,N2 -> DG1,N1

DG2,N2 -> DG2,N1

I've considered simply ignoring the edges (subtracting the value both from the sum of similarities and sum of every property), calculating a similarity, putting this value into the kernel and re-applying. This sounds to me like it could be represented as something similar to a Markov chain, in which I continually reapply this method to itself until it converges.

So I guess my question boils down to: Is there a way of determining a convergent probability that two nodes are similar? Is there a simple way this can be represented/calculated, possibly by something similar to a Markov chain?

• Is clustering (cf Wikipedia) what you are trying to do? – Raphael Oct 27 '14 at 18:23
• "Each node in the graph represents a set of data. Each vertex is a one-way connection from one set of data to another." Node and vertex are synonyms. Do you mean that each edge (aka arc) is a one-way connection? – David Richerby Oct 27 '14 at 18:39
• Sorry, yes edge. And I'm not necessarily trying to cluster them, though the more I research the more it could be seen that way. What I'm really trying to do is create clusters of maximum size 2 which contain at most one item from each graph. Then, combining those clusters into a single node. The problem is that the calculation for this clustering can rely on clustering already have been done (in the case of a cycle), so I need to know how best to find a convergent similarity measure which takes into account clusters that have already been created. – Nate Diamond Oct 27 '14 at 18:53
• I think the first step of the algorithm will likely be pruning and combining "easy" targets which are not part of cycles, then processing each cycle independently. – Nate Diamond Oct 27 '14 at 18:54
• Currently I'm reading this paper, as I think that it can be related to synonym extraction. If you consider each directed graph as a lexicon, then two nodes being similar is equal to saying that they are synonymous. This also means that the default "one-synonym" implementation is possibly exactly what I need. After reading a bit more it seems that this is based on pathing which seems more optimized for lexical evaluation. It still looks like a good starting point. – Nate Diamond Oct 27 '14 at 19:12