  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.
