  Consider two data holders, ABC and XYZ, with graph data (e.g., social
networks, e-commerce, telecommunication, and bio-informatics). ABC can see that
node A is linked to node B, and XYZ can see node B is linked to node C. Node B
is the common neighbour of A and C but neither network can discover this fact
on their own. In this paper, we provide a two party computation that ABC and
XYZ can run to discover the common neighbours in the union of their graph data,
however neither party has to reveal their plaintext graph to the other. Based
on private set intersection, we implement our solution, provide measurements,
and quantify partial leaks of privacy. We also propose a heavyweight solution
that leaks zero information based on additively homomorphic encryption.
