Abstract
Graph matching is a fundamental problem in computer vision and network analysis, traditionally addressed by learning node representations via Graph Neural Networks (GNNs). However, supervised GNNs suffer from high annotation costs and significant computational overhead. This paper introduces Training Free Graph Matching (TFGM), a framework that leverages the inherent inductive biases of GNN architectures to perform matching without any parameter training. By removing non-essential components like non-linearities and weights, and incorporating multi-order structural information, TFGM achieves state-of-the-art performance while being orders of magnitude faster than trained counterparts.
Introduction
Graph matching aims to identify correspondence between nodes in two or more graphs. It is a critical task in various domains, from aligning keypoints in images to identifying identical users across social platforms. While GNNs have significantly advanced the state-of-the-art by learning structural embeddings, they are often bottlenecked by the need for large-scale annotated datasets and the high cost of the training process itself.
The central question posed by this research is: Is training truly necessary for graph matching? The authors hypothesize that the effectiveness of GNNs in this context stems primarily from their architectural design—specifically their ability to aggregate neighborhood information—rather than the specific weights learned during training.
The TFGM Framework
The proposed Training Free Graph Matching (TFGM) framework shifts the focus from learning weights to handcrafting matching priors into the GNN architecture. This approach is built upon four key design principles:
- Multi-order Information (P1): Instead of relying solely on the final layer's output, TFGM concatenates normalized embeddings from all layers. This ensures the model captures both local 1-hop neighborhoods and more global multi-hop structures.
- Leveraging Annotations (P2): When training data is available, TFGM utilizes a k-Nearest Neighbor (kNN) search to generate label-discriminative features. This allows the model to benefit from existing annotations without undergoing a formal training phase.
- Weight-Free Architecture (P3): The authors observe that random weights can introduce unnecessary noise. By removing weights and non-linear activations (like ReLU), the GNN acts as an unbiased estimator of structural compatibility.
- Powerful Operators (P4): TFGM can be integrated with advanced graph operators, such as those found in SplineCNN or DGMC, to further enhance its inductive bias.
Mathematically, TFGM can be viewed as a linear relaxation of the Quadratic Assignment Problem (QAP). By transforming the NP-hard combinatorial QAP into a linear problem, TFGM enables efficient, polynomial-time solutions for graph matching.
Experimental Setup
The framework was rigorously evaluated across three distinct scenarios:
- Supervised Keypoint Matching: Using the PascalVOC dataset with Berkeley annotations to match object parts.
- Semi-supervised Entity Alignment: Using the DBP15k dataset to align entities across cross-lingual Knowledge Graphs.
- Unsupervised Network Alignment: Using Protein-Protein Interaction (PPI) networks to match proteins across species.
Key Results and Discussion
The results demonstrate that TFGM is not only a viable alternative to trained models but often superior. On the PascalVOC benchmark, TFGM combined with the DGMC architecture achieved a mean accuracy of 74.7%, surpassing the fully trained version's 73.0%.
Beyond accuracy, the computational efficiency of TFGM is remarkable. In unsupervised settings on the PPI dataset, TFGM was approximately 5,000 times faster than the leading baseline, MAGNA++. In supervised settings, it maintained a 7-8x speedup over trained models. Furthermore, TFGM exhibited high robustness to noise, outperforming traditional algorithms like GHOST and KerGM on datasets with random rewiring or low-confidence edges.
Conclusion
TFGM challenges the prevailing paradigm that GNNs must be trained to be effective. By demonstrating that architectural inductive bias is the primary driver of performance in graph matching, this work opens new avenues for efficient, training-free graph analysis. While the kNN search in supervised settings introduces some overhead, the overall gains in speed and simplicity make TFGM a powerful tool for large-scale graph matching tasks.
Summary updated