I have a large dataset where each item contains a small set of random pairs of connected nodes (say 3), however I do not know the links. For example, you might be given ABC & XYZ, but you don't know if A connects to X, Y, or Z, etc. But you do know that there are three pairs, each with distinct nodes. The correct links in this case might be A->X, B->Z, C->Y.

Now if each node can only form one link, finding the links becomes trivial, by simply finding the highest correlation between nodes over time. My problem is that each node can form links with multiple nodes.

Is there any algorithm for finding the adjacency matrix given data in this way? Or does anyone have any suggestions for how to solve this?

  • $\begingroup$ +1 for the question, seems like its impossible to solve this exactly, since a complete graph is going to match any observations. So probably just assume a link between points with high correlations? $\endgroup$ – dontloo Oct 27 '16 at 8:26
  • $\begingroup$ I have tried simply looking for high correlations, but that can yield incorrect edges in certain cases. I have improved it a bit by penalising edge probabilities when neighbours report high probabilities themselves. If I get a solid solution working, i'll post more details. $\endgroup$ – Matt Way Oct 27 '16 at 11:33

You might try expectation maximization to solve this problem. I am not totaly sure about the details but I am confident that is does capture the specifics of the problem. It can deal with the idea that only one connection between the possible pairs of connected nodes (e.g. AX, AY or AZ) explains the data.

The maximization step calculates the parameters of the model (probabilistic adjacency matrix) that best explain the data. You could model the data as $X_{ijk}$ where $X_{ijk} = 1$ if and only if the $k$'th pair possibly connects $i$ and $j$. The adjacency matrix should then maximize the probability that each $i$ in pair $k$ is at connected to a $j$ (marginalize over $j$).

The expectation step calculates the likelihood of the data given the model. It something like:

$$ p(X | A) = \prod_k \prod_i \sum_j p(X_{ijk} | A) $$

Probably you need to do a lot of thinking to get this to work.

  • $\begingroup$ I was going to write my attempt should no answers arrive, but I essentially ended up doing exactly what you have written above. My attempt raises the probability of correlated edges while penalising edges whose neighbours have higher probabilities. The devil is still in the details, but I'll mark this as correct. Thanks. $\endgroup$ – Matt Way Nov 1 '16 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.