Geometric Graph Matching with Message Passing Neural Networks

Oregon Convention Center 

We study matching random graphs with geometric structure using graph neural networks. To this end, we consider a special family of random geometric graphs where two vertices are connected if the overlap in their binary features surpasses a fixed threshold. For two such graphs, we have access to a random subset of edges together with noisy observations of their underlying vertex features. Our goal is to recover an unknown vertex alignment from the noisy and incomplete information.
We show that solving a linear assignment problem with only noisy vertex features fails in certain parameter regimes. In contrast, if the features are passed through a specially designed message passing neural network, we can achieve perfect recovery with high probability. We also show that the bound for perfect recovery is tight up to logarithmic factors.
Finally, we apply the algorithm to aligning medical concepts from different coding systems (e.g., codified and NLP) with their genetic associations and demonstrate that better alignment accuracy can be achieved with the help of the medical knowledge graph.

random geometric graph

graph neural network

entity alignment

linear assignment problem

graph matching

random intersection graph 

IMS