Abstract
Deep graph matching techniques have shown promising results in recent years. In this work, we cast deep graph matching as a contrastive learning task and introduce a new objective function for contrastive mapping to exploit the relationships between matches and non-matches. To this end, we develop a hardness attention mechanism to select negative samples which captures the relatedness and informativeness of positive and negative samples. Further, we propose a novel deep graph matching framework, Stable Graph Matching (StableGM), which incorporates Sinkhorn ranking into a stable marriage algorithm to efficiently compute one-to-one node correspondences between graphs. We prove that the proposed objective function for contrastive matching is both positive and negative informative, offering theoretical guarantees to achieve dual-optimality in graph matching. We empirically verify the effectiveness of our proposed approach by conducting experiments on standard graph matching benchmarks.
Introduction
Graph matching—finding the best node-to-node correspondences between two graphs—is a cornerstone of computer vision and bioinformatics. However, finding the optimal matching is computationally NP-hard. Modern deep learning approaches attempt to solve this by learning "soft" matches using cross-entropy losses.
A significant limitation of existing methods is that cross-entropy loss penalizes errors element-wise, ignoring the global relationship between matches and non-matches. This often leads to class imbalance—since most node pairs are not matches—and numerical instability. Furthermore, many models struggle to strictly enforce the "one-to-one" constraint during the learning process, which is essential for many real-world applications.
The StableGM Framework
The authors introduce StableGM, a framework that reimagines supervised graph matching as a contrastive learning problem. The architecture consists of three main stages:
- Graph Affinity Encoding: Neural Networks (such as SplineCNN or GNNs) extract node features to compute an initial affinity matrix between the source and target graphs.
- Sinkhorn Ranking: The Sinkhorn operator transforms affinities into a "doubly stochastic" matrix. In this context, the values are treated as a "preference ranking" where each node ranks potential partners in the other graph.
- Stable Matching Algorithm: Instead of the computationally expensive Hungarian algorithm ($O(N^3)$), StableGM adapts the Gale-Shapley (Stable Marriage) algorithm. This ensures a stable, one-to-one mapping with a better time complexity of $O(N^2 \log N)$.
Contrastive Innovation: Hardness Attention
The core of the training process is a new Contrastive Matching Loss powered by Hardness Attention. This mechanism identifies "hard negatives"—non-matching node pairs that the model currently finds confusing. By focusing the loss on these difficult cases, the framework captures the structural nuances of the graphs more effectively than standard cross-entropy.
The paper provides a theoretical proof that this contrastive loss is both "positive-informative" and "negative-informative," guaranteeing "dual-optimality." This ensures that the matching is optimal from the perspective of both the source and target graphs simultaneously.
Experimental Results
StableGM was evaluated on major benchmarks including Pascal VOC Keypoint, SPair-71k, Willow ObjectClass, and Protein-Protein Interaction (PPI) networks.
Key findings include:
- State-of-the-Art Performance: StableGM-v2 achieved a mean accuracy of 83.48% on SPair-71k, outperforming the previous best model, GCAN (81.90%).
- Efficiency and Scalability: The Stable Matching algorithm proved significantly faster and more scalable than the traditional Hungarian algorithm used in most deep graph matching pipelines.
- Robustness: On biological PPI networks with 5% noise, StableGM achieved 86.1% accuracy, a notable improvement over the baseline SIGMA (84.7%).
Conclusion
By framing graph matching through the lens of the Stable Marriage problem and utilizing contrastive learning with hardness attention, StableGM addresses the limitations of traditional supervised matching. While performance can degrade on inconsistently annotated data (e.g., the "sofa" and "table" classes in Pascal VOC), the framework provides a powerful, efficient, and theoretically grounded approach to graph correspondence. Future work will focus on improving robustness to structural noise and extending the framework to multi-graph matching.
Summary updated