PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Graph Matching Consensus

Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, Nils M. Kriege

arXiv:2001.09621v1cs.LGstat.ML

TL;DR

Graph matching must establish structural correspondences while handling the computational limits and local ambiguities of existing methods. The paper proposes a two-stage neural architecture that initializes soft matches from local embeddings and iteratively refines them through neighborhood consensus. It reports consistent state-of-the-art improvements on real-world tasks, with local sparsity-aware processing that scales to large inputs.

  • Problem

    Graph matching requires structural correspondences, but classical methods are NP-hard and existing neural approaches can be inefficient or inconsistent when relying on localized information.

  • Method

    A two-stage architecture computes initial soft correspondences from localized GNN embeddings and iteratively re-ranks them using synchronous message passing and neighborhood consensus.

  • Results

    The method consistently improves upon the state-of-the-art on real-world computer-vision and knowledge-graph entity-alignment applications.

  • Takeaways & Limitations

    Purely local, sparsity-aware consensus refinement can scale to large inputs while recovering global correspondences consistently.

  • Takeaways & Limitations

    The method generally inherits Weisfeiler–Lehman limitations and may fail to converge when nodes receive identical WL colors, although real-world feature noise makes this unlikely.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Graph matching seeks meaningful node correspondences using both node and edge similarities, but existing approaches face scalability, adaptability, and consistency limitations. The proposed fully differentiable, local, sparsity-aware procedure targets neighborhood consensus and improves state-of-the-art results on real-world applications.

  • Graph matching establishes structural node correspondences using both node similarities and pairwise edge similarities.
  • Classical graph-edit, common-subgraph, and quadratic-assignment formulations are NP-hard and may be impractical for large real-world instances.These approaches also often omit continuous node embeddings and adaptation to data distributions.
  • Existing neural methods may produce whole-graph similarities, require inefficient global matching, or rely inconsistently on localized embeddings.
  • The proposed fully differentiable procedure reaches data-driven neighborhood consensus without solving an optimization problem during inference.It operates on fixed-size neighborhoods, accounts for sparsity, and supports end-to-end training.
  • The approach scales to large input domains and improves upon the state-of-the-art in computer vision and knowledge-graph entity alignment.

2 PROBLEM DEFINITION

The paper formalizes graphs, neighborhoods, node colorings, and injective correspondence matrices for graph matching. It frames neighborhood consensus as an edge-preserving condition and considers supervised and semi-supervised settings.

  • A graph comprises nodes, an adjacency matrix, node features, and optional sparse edge features; T-hop neighborhoods contain nodes within shortest-path distance T.A node coloring assigns each node an element of an arbitrary codomain.
  • Graph matching seeks a binary correspondence matrix satisfying one-to-one constraints, inducing an injective mapping from source nodes to target nodes.
  • Traditional graph matching is commonly formulated as an edge-preserving quadratic assignment problem.
  • Neighborhood consensus requires every source neighbor of a matched node to correspond to some neighbor of its target.
  • The work addresses supervised matching with pairwise ground truth and semi-supervised matching with labels for only a small subset of nodes.In the semi-supervised setting, complete graph structures remain available.

3 METHODOLOGY

The method first computes local embedding-based soft correspondences, then iteratively refines them by measuring neighborhood consensus with synchronous message passing. Local operators, trainable updates, and sparse correspondence handling support scalable end-to-end matching.

  • 3 METHODOLOGY: The architecture combines local feature matching with iterative refinement using synchronous message passing and a differentiable graph-isomorphism validator.The methodology also introduces a scaling procedure for large real-world inputs.
  • 3.1 LOCAL FEATURE MATCHING: A shared GNN computes localized, permutation-equivariant node embeddings for the source and target graphs to initialize correspondence scores.
  • 3.1 LOCAL FEATURE MATCHING: Sinkhorn normalization produces rectangular doubly-stochastic correspondence matrices satisfying the target-side one-to-one constraints.
  • 3.2 SYNCHRONOUS MESSAGE PASSING FOR NEIGHBORHOOD CONSENSUS: Purely local embeddings can create false correspondences when different nodes have similar local structure.
  • 3.2 SYNCHRONOUS MESSAGE PASSING FOR NEIGHBORHOOD CONSENSUS: The refinement stage iteratively updates soft correspondences by mapping node functions across graphs and detecting neighborhood-consensus violations.Updates begin from S(0) and proceed through S(l) for l from 0 to L.
  • 3.2 SYNCHRONOUS MESSAGE PASSING FOR NEIGHBORHOOD CONSENSUS: An injective source-node coloring is transferred through S, distributed by a shared GNN, and compared to obtain a consensus measure for each node pair.
  • 3.3 ITERATIVE REFINEMENT: The trainable update network refines correspondence scores from pairwise color differences, while the combined objective supports end-to-end optimization.The consensus stage resolves first-stage ambiguities using local operators and extends graduated assignment with trainable networks.
  • 3.4 SCALING TO LARGE INPUT: Sparsifying initial correspondences reduces memory from O(|Vs||Vt|) to O(k|Vs|) and refinement time from O(|Vs||Vt| + |Es| + |Et|) to O(k|Vs| + |Es| + |Et|).This assumes the correct correspondence appears among the top k candidates for each source node.

4 EXPERIMENTS

Experiments evaluate the architecture on synthetic graph matching, supervised keypoint matching, geometric feature matching, and knowledge graph alignment. Across these settings, iterative consensus refinement improves matching beyond initial or competing methods while remaining scalable through local, sparse processing.

  • Experimental scope: The study evaluates the method on synthetic graphs, natural-image keypoints, geometric keypoints, and semi-supervised cross-lingual knowledge graph alignment.Experiments include synthetic ablations and real-world computer-vision and entity-alignment tasks.
  • Synthetic graph ablation: Synthetic experiments show that two-stage refinement recovers all correspondences despite increasing structural noise, unlike purely local or globally normalized initial matching.The result holds for both the Sinkhorn and row-wise softmax variants.
  • Synthetic graph ablation: Test-time refinement can converge even when training has not reached convergence by increasing the number of refinement iterations.The test error is evaluated while varying L(test).
  • Synthetic graph ablation: Sparsified top-k refinement converges to Hits@1 ≈ Hits@k when the correct match is included initially, supporting scalability to large graphs.Increasing k recovers most correct correspondences.
  • Supervised keypoint matching: On supervised keypoint matching, refinement significantly outperforms competing and non-refined methods, reducing WILLOW-OBJECTCLASS error by at least half across categories.With a weaker MLP initial matcher, improvements reach up to 14 percentage points on PASCALVOC.
  • Geometric keypoint matching: On PASCALPF geometric matching, the consensus architecture improves state-of-the-art results on almost all categories despite using only point coordinates and no visual features.The L = 0 baseline is weaker than the prior method, isolating the benefit of consensus refinement.

5 LIMITATIONS

The method generally inherits the expressive limitations of graph neural networks related to the Weisfeiler–Leman heuristic. In particular, identical WL color assignments can produce indistinguishable updates and possible non-convergence, although real-world feature noise makes this unlikely.

  • The approach generally inherits the power and limitations of GNNs associated with the WL heuristic for graph isomorphism testing.
  • Nodes assigned the same WL color may remain indistinguishable to the method.
  • Identical neighborhoods can produce identical distributed functions and correspondence updates for different nodes.
  • Identical updates can lead to non-convergence during correspondence refinement.
  • Real-world feature noise generally makes this ambiguous, non-convergent scenario unlikely.

6 RELATED WORK

Graph node-correspondence problems are studied across several established research areas, including maximum common subgraph, network alignment, graph edit distance, and graph matching.

  • Node correspondence between graphs has been studied extensively across multiple domains.
  • Related problem formulations include maximum common subgraph, network alignment, graph edit distance, and graph matching.
  • The paper directs readers to Appendix F for a detailed discussion of related work.

7 CONCLUSION

The paper presents a two-stage architecture for learning and iteratively refining graph-node correspondences toward neighborhood consensus. The optimized algorithm uses localized embeddings, sparse candidate correspondences, synchronous refinement, and normalization, and consistently improves upon the state of the art on real-world datasets.

  • 7 CONCLUSION: The architecture learns node correspondences in supervised or semi-supervised settings and iteratively resolves violations of neighborhood consensus.
  • 7 CONCLUSION: The approach includes enhancements for scaling to large input domains and consistently improves upon the state of the art on real-world datasets.
  • 7 CONCLUSION: The optimized procedure computes node embeddings for both graphs and initializes soft correspondences through local feature matching.
  • 7 CONCLUSION: The algorithm sparsifies each source node's candidates to the top k scores before running L consensus iterations.
  • 7 CONCLUSION: Each refinement iteration maps and distributes random node functions across both graphs, computes neighborhood consensus, updates correspondences, and normalizes scores.

B PROOF FOR THEOREM 1

The proof connects message-passing representations and injective node colorings to local graph isomorphisms, while experiments show that trainable refinement improves over a fixed message-passing scheme.

  • B PROOF FOR THEOREM 1: Permutation equivariance implies that corresponding relabeled graphs receive correspondingly relabeled message-passing outputs.
  • B PROOF FOR THEOREM 1: Matching neighborhoods with compatible representations imply labeled graph isomorphisms between the corresponding T-hop subgraphs.
  • B PROOF FOR THEOREM 1: A message-passing network as powerful as WL can distinguish structures under injective node colorings.
  • B PROOF FOR THEOREM 1: Injectivity prevents two source nodes from mapping to the same target node under the theorem's assumptions, yielding a permutation matrix describing an isomorphism.
  • B PROOF FOR THEOREM 1: Trainable refinement consistently outperforms the fixed one-layer message-passing scheme because it can learn how to use node and edge features.

E ROBUSTNESS TOWARDS NODE ADDITION OR REMOVAL

Synthetic experiments evaluate robustness to noisy node additions across graph sizes, densities, and addition rates. The consensus refinement remains robust where initial feature matching struggles.

  • Results: Figure 3 reports Hits@1 across source sizes, edge probabilities, and noisy-node addition rates.The evaluated addition rates are q ∈ {0.0, 0.1, 0.2, 0.3, 0.4, 0.5}.
  • Results: The consensus stage is extremely robust to node addition or removal, whereas the initial feature-matching stage has major difficulty finding the correct matching.This comparison is the central qualitative finding of the synthetic robustness experiments.
  • Mechanism: Unmatched nodes do not affect neighborhood-consensus error because they receive no color from the functional map defined by S.The refinement stage can therefore detect and gradually reduce false-positive influence from unmatched nodes.
  • Context: Classical graph-matching formulations based on graph edit distance, maximum common subgraph, or quadratic assignment are NP-hard and may be intractable at large scale.These combinatorial approaches also do not adapt to the given data distribution.

G RELATED WORK II

Related work spans deep graph matching, network alignment, functional maps, and neighborhood-consistency methods from image matching. The paper distinguishes its fully learnable, local, sparsity-aware refinement from global or computationally expensive alternatives.

  • Deep graph matching: Existing approaches include cross-graph embeddings, optimal transport and Gromov–Wasserstein objectives, nearest-neighbor embedding alignment, and topology-preservation tasks.These methods address graph matching or network alignment from different learned or optimization-based perspectives.
  • Deep graph matching: Prior deep graph-matching methods use supervised displacement or combinatorial objectives, while this paper presents a fully learnable matching procedure.Zanfir and Sminchisescu use a differentiable but unlearnable spectral solver; the proposed procedure is described as fully learnable.
  • Intra- and inter-graph message passing: Some graph neural approaches enhance node embeddings with information from similar nodes in the other graph through cross-graph matching procedures.This line of work includes intra- and inter-graph message passing.
  • Neighborhood consensus for image matching: Image-matching neighborhood consensus improves local feature matching, but direct 4D-convolution transfer to graphs would require a product graph with O(n^2) nodes and O(n^4) edges.The proposed algorithm performs analogous sparse-product-graph error inference while computing on the original graphs.
  • Functional maps: Functional-map methods focus on global correspondences through truncated graph-Laplacian bases but can fail on partial matchings and require approximate basis computation for large inputs.Their domain-dependent eigenbases create an inherent disadvantage for partial matching.

H DATASET STATISTICS

The paper provides detailed descriptions of all datasets used in its experiments, with further information in Tables 7–10.

  • Detailed descriptions of all experimental datasets are provided in Tables 7, 8, 9, and 10.

I QUALITATIVE KEYPOINT MATCHING RESULTS

Qualitative WILLOW-OBJECTCLASS examples compare initial feature matching with the refined correspondences. Refinement recovers successful matches in difficult cases and resolves a rare many-to-one violation, although mislabeled target keypoints create apparent errors.

  • Successful refinement: In three examples, initial feature matching fails but refinement successfully recovers all correspondences.These are the examples shown in Figure 4(a), (b), and (c).
  • Failure case: In a rare failure case, refinement resolves the initial mapping of most keypoints to the same target keypoint.The refined strategy successfully resolves this one-to-many violation in the displayed example.
  • Annotation caveat: Some mappings are mistakenly judged wrong because the target image contains incorrect keypoint labels, including the duck’s eye.The apparent errors reflect annotation problems rather than only matching behavior.
  • Figure layout: Figure 4 compares source and target images while visualizing initial scores S(0) above and refined scores S(L) below.The figure presents qualitative keypoint-matching examples from WILLOW-OBJECTCLASS.
Loading 2001.09621v1…