Deep Graph Matching Consensus

Abstract

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.

Published as a conference paper at ICLR 2020

References in corpus (11)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Geometric deep learning: going beyond Euclidean data
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Fast Graph Representation Learning with PyTorch Geometric
• Ranking via Sinkhorn Propagation
• Convolutional Set Matching for Graph Similarity
• Graph Neural Networks for User Identity Linkage
• Multi-Channel Graph Neural Network for Entity Alignment
• Self-supervised Learning of Dense Shape Correspondence
• A Family of Tractable Graph Distances
• KerGM: Kernelized Graph Matching

Cited by in corpus (21)

• A comprehensive survey on point cloud registration
• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Neural Subgraph Matching
• Hierarchical Inter-Message Passing for Learning on Molecular Graphs
• Boost then Convolve: Gradient Boosting Meets Graph Neural Networks
• Optimal Transport Graph Neural Networks
• Deep Graph Similarity Learning: A Survey
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• A contribution to Optimal Transport on incomparable spaces
• Correspondence Learning via Linearly-invariant Embedding
• Are Negative Samples Necessary in Entity Alignment? An Approach with High Performance, Scalability and Robustness
• Convolutional Hough Matching Networks for Robust and Efficient Visual Correspondence
• Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
• High-Order Relation Construction and Mining for Graph Matching
• Towards Entity Alignment in the Open World: An Unsupervised Approach
• Knowing the No-match: Entity Alignment with Dangling Cases
• Combinatorial Learning of Graph Edit Distance via Dynamic Embedding
• Experiments with graph convolutional networks for solving the vertex $p$-center problem
• From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment
• Operator Autoencoders: Learning Physical Operations on Encoded Molecular Graphs
• Convolutional Hough Matching Networks