Geometric Graph Matching with Message Passing Neural Networks

3292 

Contributed Abstract 

Paper 

Suqi Liu (1), Tianxi Cai (1), Morgane Austern (1)

(1) Harvard University, United States

Tianxi Cai  
Harvard University

Morgane Austern  
Harvard University

Suqi Liu  
Harvard University

Suqi Liu  
Harvard University

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

Foundations of Machine Learning