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
DG2,N1 are similar, I need to take into account their connections. If
DG2,N2 are to be merged (or similar enough), then that makes it more likely that
DG2,N1 are similar. If
DG2,N2 are not similar, then it makes it less likely that
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?