Abstract
Graph distance metric learning serves as the foundation for many graph learning problems, e.g., graph clustering, graph classification and graph matching. Existing research works on graph distance metric (or graph kernels) learning fail to maintain the basic properties of such metrics, e.g., non-negative, identity of indiscernibles, symmetry and triangle inequality, respectively. In this paper, we will introduce a new graph neural network based distance metric learning approaches, namely GB-DISTANCE (GRAPH-BERT based Neural Distance). Solely based on the attention mechanism, GB-DISTANCE can learn graph instance representations effectively based on a pre-trained GRAPH-BERT model. Different from the existing supervised/unsupervised metrics, GB-DISTANCE can be learned effectively in a semi-supervised manner. In addition, GB-DISTANCE can also maintain the distance metric basic properties mentioned above. Extensive experiments have been done on several benchmark graph datasets, and the results demonstrate that GB-DISTANCE can out-perform the existing baseline methods, especially the recent graph neural network model based graph metrics, with a significant gap in computing the graph distance.
Introduction
Measuring the distance between two graphs—whether they represent molecular compounds, program control-flow graphs, or social networks—is a fundamental task in graph learning. Traditional methods like Graph Edit Distance (GED) are considered the gold standard but suffer from NP-completeness, making them computationally prohibitive for large-scale applications. While recent Graph Neural Network (GNN) approaches offer speed improvements, they often struggle with node-order sensitivity and, crucially, fail to satisfy the mathematical requirements of a true distance metric: non-negativity, symmetry, identity of indiscernibles, and the triangle inequality.
The GB-DISTANCE Framework
To address these challenges, the authors propose GB-DISTANCE (GRAPH-BERT based Neural Distance). This framework leverages a BERT-style attention mechanism to learn robust graph representations while explicitly enforcing metric properties.
Methodology Overview
- Graph-Bert Backbone: Unlike standard convolutional GNNs, GB-DISTANCE uses an attention-only architecture. It achieves node-order invariance by incorporating Weisfeiler-Lehman (WL) role embeddings and positional encodings.
- Metric-Aware Inference: The model ensures symmetry by calculating the entry-wise square of the difference between graph vectors $(z^{(i)} - z^{(j)})^2$. Non-negativity is maintained via an exponential output function ($1 - \exp(-x)$).
- Triangle Inequality Enforcement: A novel Triangle-Fixing algorithm is employed as a post-processing step to iteratively adjust predicted distances, ensuring they satisfy the triangle inequality ($d(A,C) \leq d(A,B) + d(B,C)$).
- Semi-Supervised Learning: A "Masked Loss Function" allows the model to learn from both labeled and unlabeled graph pairs, enhancing its flexibility in data-scarce environments.
Experimental Results
The model was evaluated on three benchmark datasets: AIDS (molecular compounds), LINUX (program control-flow), and IMDB (social ego-networks). Performance was measured using Spearman’s rank correlation ($\rho$), Kendall’s rank correlation ($\tau$), and Precision@10 (p@10).
Key Findings
- Superior Accuracy: GB-DISTANCE significantly outperformed GNN baselines. For instance, on the AIDS dataset, it achieved a Spearman’s correlation of 0.618, compared to roughly 0.50 for GCN-based methods.
- The Impact of Triangle Fixing: Explicitly enforcing the triangle inequality acted as a structural regularizer, notably boosting performance on the AIDS and LINUX datasets.
- Efficiency via Pre-training: By utilizing a pre-trained Graph-Bert backbone, the model achieves high accuracy more rapidly than models trained from scratch on pairwise distances.
Conclusion
GB-DISTANCE represents a significant step forward in graph distance learning by combining the representational power of attention mechanisms with the mathematical rigor of metric learning. While the current triangle-fixing step is a post-processing algorithm, future work may explore integrating these constraints directly into a fully differentiable end-to-end training pipeline.
Summary updated