# Find graph links given random groups of node pairs

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?

• +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? – dontloo Oct 27 '16 at 8:26
• 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. – 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$).
$$p(X | A) = \prod_k \prod_i \sum_j p(X_{ijk} | A)$$