Deep Graph Matching Consensus
This work addresses the challenge of graph matching, which is crucial for applications like computer vision and knowledge graph alignment, by providing a scalable and effective solution, though it is incremental as it builds on existing graph neural network and message passing techniques.
The paper tackles the problem of learning structural correspondences between graphs by introducing a two-stage neural architecture that first uses graph neural networks for initial node embeddings and then employs synchronous message passing for iterative re-ranking to achieve matching consensus. The method improves state-of-the-art results on real-world tasks in computer vision and knowledge graph entity alignment, with demonstrated scalability to large inputs.
This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re-rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re-ranking process. Our purely local and sparsity-aware architecture scales well to large, real-world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state-of-the-art. Our source code is available under https://github.com/rusty1s/ deep-graph-matching-consensus.