Training Free Graph Neural Networks for Graph Matching

Zhiyuan Liu, Yixin Cao, Fuli Feng, Xiang Wang, Xindi Shang, Jie Tang, Kenji Kawaguchi, Tat-Seng ChuaarXiv 2022 · arXiv

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Generating label-discriminative features via kNN search in the training dataset.

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%.

Performance comparison on PascalVOC dataset across different categories.

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

Abstract

We present a framework of Training Free Graph Matching (TFGM) to boost the performance of Graph Neural Networks (GNNs) based graph matching, providing a fast promising solution without training (training-free). TFGM provides four widely applicable principles for designing training-free GNNs and is generalizable to supervised, semi-supervised, and unsupervised graph matching. The keys are to handcraft the matching priors, which used to be learned by training, into GNN's architecture and discard the components inessential under the training-free setting. Further analysis shows that TFGM is a linear relaxation to the quadratic assignment formulation of graph matching and generalizes TFGM to a broad set of GNNs. Extensive experiments show that GNNs with TFGM achieve comparable (if not better) performances to their fully trained counterparts, and demonstrate TFGM's superiority in the unsupervised setting. Our code is available at https://github.com/acharkq/Training-Free-Graph-Matching.
BibTeX
@misc{liu2022training,
  author = {Zhiyuan Liu and Yixin Cao and Fuli Feng and Xiang Wang and Xindi Shang and Jie Tang and Kenji Kawaguchi and Tat-Seng Chua},
  title = {{Training Free Graph Neural Networks for Graph Matching}},
  year = {2022},
  eprint = {2201.05349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2201.05349},
}
Figure