Source-linked AI summary
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, Wei Wang
TL;DR
Graph similarity computation is central to graph search and other applications but is costly, especially for GED and MCS. SimGNN learns similarity scores from graph pairs using attention-based graph embeddings and pairwise node comparisons, achieving competitive accuracy and fast computation in GED experiments. The approach remains scoped by its inability to process edge features and by uncertainty about generalization to large graphs trained on small-graph GEDs.
Problem
Exact graph similarity computation, including GED and MCS, is costly and difficult, with exact GED impractical for larger graphs and existing approximations relying on complex search.
Method
SimGNN learns a neural-network function for graph-pair similarity using attention-based graph embeddings supplemented by pairwise node comparisons.
Results
SimGNN achieves smaller error and substantial time reduction than approximate GED algorithms and graph neural network baselines on three real graph datasets.
Takeaways & Limitations
The results support neural-network-based graph similarity computation as a fast approach with competitive accuracy for GED.
Takeaways & Limitations
The model cannot process edge features, and its generalization to large graphs remains open because training uses exact GEDs between small graphs.
Abstract
from arXiv · showhide
Graph similarity search is among the most important graph-based applications, e.g. finding the chemical compounds that are most similar to a query compound. Graph similarity computation, such as Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), is the core operation of graph similarity search and many other applications, but very costly to compute in practice. Inspired by the recent success of neural network approaches to several graph applications, such as node or graph classification, we propose a novel neural network based approach to address this classic yet challenging graph problem, aiming to alleviate the computational burden while preserving a good performance. The proposed approach, called SimGNN, combines two strategies. First, we design a learnable embedding function that maps every graph into a vector, which provides a global summary of a graph. A novel attention mechanism is proposed to emphasize the important nodes with respect to a specific similarity metric. Second, we design a pairwise node comparison method to supplement the graph-level embeddings with fine-grained node-level information. Our model achieves better generalization on unseen graphs, and in the worst case runs in quadratic time with respect to the number of nodes in two graphs. Taking GED computation as an example, experimental results on three real graph datasets demonstrate the effectiveness and efficiency of our approach. Specifically, our model achieves smaller error rate and great time reduction compared against a series of baselines, including several approximation algorithms on GED computation, and many existing graph neural network based models. To the best of our knowledge, we are among the first to adopt neural networks to explicitly model the similarity between two graphs, and provide a new direction for future research on graph similarity computation and graph similarity search.
1 INTRODUCTION
Graph similarity search depends on graph-distance computations that are computationally difficult, motivating SimGNN’s learning-based approach to fast similarity estimation. SimGNN combines similarity-aware graph embeddings with pairwise node comparisons and demonstrates effectiveness on GED.
- Exact GED and MCS computation is NP-complete, and exact GED is impractical within reasonable time for graphs exceeding 16 nodes.
- Existing remedies either prune exact computations through indexing or approximate graph distances using discrete optimization and combinatorial search.
- SimGNN reframes graph similarity computation as a learnable neural-network function that maps graph pairs to similarity scores trained against ground-truth scores.
- The model is designed to be representation-invariant, inductive on unseen graphs, and learnable for different similarity metrics.
- SimGNN combines attention-based graph-level embeddings with pairwise node comparisons that add fine-grained information to coarse fixed-length representations.
- Experiments on GED across three real graph datasets report smaller error and substantial time reduction against approximate GED algorithms and graph neural network baselines.
2 PRELIMINARIES
The preliminaries define GED as the minimum edit-operation cost for transforming one graph into another and describe GCNs as inductive, representation-invariant node-embedding models. SimGNN uses these node embeddings in both graph-level aggregation and pairwise comparison.
- GED is the minimum number or cost of vertex and edge insertions, deletions, and vertex relabelings needed to transform one graph into another.
- In the example, GED equals 3 because the transformation requires one edge deletion, one edge insertion, and one node relabeling.
- Identical or isomorphic graphs have GED 0, and the distance can be transformed into a similarity score between 0 and 1.
- SimGNN computes node embeddings with GCNs, whose graph convolution aggregates features from each node’s first-order neighbors and the node itself.
3 THE PROPOSED APPROACH: SIMGNN
SimGNN maps graph pairs to similarity scores by combining attention-based graph-level embeddings with fine-grained pairwise node comparisons. Histogram features preserve representation invariance, while the combined model retains global and node-level comparison information with worst-case quadratic complexity.
- Overall architecture: SimGNN transforms each graph's nodes into vectors, then combines graph-level embedding interaction and pairwise node-embedding comparison to predict similarity.The two strategies feed a fully connected network that produces the final graph-pair similarity score.
- Strategy 1: Graph-level embeddings: Attention weights are learned from a global graph context so nodes relevant to the chosen similarity metric receive greater emphasis.The context is computed from averaged node embeddings and transformed nonlinearly; the resulting weighted sum forms the graph embedding.
- Strategy 1: Graph-level embeddings: The graph-level strategy uses Neural Tensor Networks to model interactions between two graph embeddings and produces multiple similarity scores before dimensionality reduction.The hyperparameter K controls the number of interaction scores generated for each graph-embedding pair.
- Strategy 2: Pairwise node comparison: Histogramming pairwise node-comparison scores avoids dependence on arbitrary node ordering while supplementing coarse graph-level features with fine-grained information.The normalized histogram is concatenated with graph-level interaction scores and passed through fully connected layers.
- Strategy 2: Pairwise node comparison: Strategy 1 is primary because histogram features are nondifferentiable, whereas Strategy 2 supplements graph-level features and provides extra performance gain.The model therefore relies on Strategy 1 to update weights and uses Strategy 2 as an auxiliary source of information.
- Efficiency: The model has worst-case quadratic time in the numbers of nodes, with Strategy 2 more time-consuming but GPU acceleration limiting its runtime increase experimentally.Embedding computation is performed once per graph, while pairwise similarity computation is performed for each graph pair.
4 EXPERIMENTS
Experiments use three real-world graph datasets to evaluate GED similarity prediction, with exact ground truth for small graphs and approximate ground truth for larger graphs.
- Datasets: 700 AIDS, 1000 LINUX, and 1500 IMDB graphs are used, with datasets covering chemical compounds, program dependence graphs, and movie-actor ego-networks.AIDS and LINUX graphs contain at most 10 nodes; IMDB uses the full dataset.
- Evaluation protocol: Graphs are split into 60% training, 20% validation, and 20% testing, with each test graph queried against every database graph.Database graphs are ranked by predicted similarity.
- Ground truth: A* computes exact GED for AIDS and LINUX, whereas IMDB ground truth uses the smallest distance from Beam, Hungarian, and VJ.The IMDB procedure is used because exact GED computation is impractical for larger graphs.
- Similarity targets: GEDs are normalized by the average graph size and transformed with e^-x into similarity scores in (0, 1].The transformation preserves a one-to-one mapping between GED and similarity.
4.3 Baseline Methods
The baselines comprise fast approximate GED algorithms and neural network models, while SimGNN combines attention-based graph embeddings with pairwise node comparison.
- Approximate GED methods: Baseline methods include Beam, Hungarian, and VJ as approximate GED computation algorithms.Beam is sub-exponential, while Hungarian and VJ are cubic-time methods based on bipartite matching algorithms.
- Neural baselines: Neural baselines include mean-pooling, graph-coarsening, and node-attention architectures.The listed models include SimpleMean, HierarchicalMean, HierarchicalMax, and attention-based variants.
- SimGNN: SimGNN combines the best of AttLearnableGC with the pairwise node-comparison strategy.This combination is the model evaluated against both approximate GED algorithms and neural baselines.
4.4 Parameter Settings
The experiments compare effectiveness, ranking quality, runtime, and attention behavior across AIDS, LINUX, and IMDB datasets.
- Effectiveness: SimGNN achieves the best or second-best performance on all metrics across all three datasets and the best results among neural models.The results suggest that its learned embedding function generalizes to unseen test graphs.
- Effectiveness: Beam attains the best precision at 10 on AIDS and LINUX, plausibly because GED distributions are imbalanced.The paper attributes this to training pairs containing relatively few very similar examples.
- Effectiveness: AttDegree performs relatively well on IMDB but not on AIDS or LINUX, while AttLearnableGC adapts to GED through learnable global context.Combining AttLearnableGC with Strategy 2 yields further performance gains.
- Attention analysis: Attention visualizations emphasize high-degree hubs, rare labels, and nodes in special substructures.The paper presents these patterns as consistent with the proposed attention mechanism.
- Efficiency: Neural network models consistently achieve the best runtime across the three datasets.The runtime comparison includes the time required for graph embedding.
- Efficiency: 2174 times faster on AIDS and 212 times faster on LINUX, SimGNN outpaces exact A*; Beam remains 46 times slower on IMDB.Precomputing graph embeddings would reduce SimGNN’s measured runtime further.
4.7 Parameter Sensitivity
Parameter sensitivity is assessed using mean squared error on AIDS by varying graph-embedding dimensions and histogram-bin counts.
- Embedding dimensions: Larger graph-level embedding dimensions improve performance on AIDS.The paper associates this improvement with greater representational capacity.
- Histogram bins: Performance is relatively insensitive to the number of histogram bins in Strategy 2.The evaluation varies histogram-bin counts while reporting mean squared error on AIDS.
4.8 Case Studies
SimGNN retrieves graphs similar to a query in three example case studies, matching the top six LINUX results to isomorphic graphs.
- SimGNN retrieves graphs similar to each query in demonstrations drawn from three datasets.The examples appear in Figures 8, 9, and 10, with ground-truth rankings compared against model-returned graphs.
- In the LINUX case study, the top 6 retrieved results are exactly isomorphic to the query.
5 RELATED WORK
The related work spans node and graph representation learning, graph similarity metrics, and database techniques for graph similarity search. SimGNN is positioned against approximate pairwise GED computation rather than database-level acceleration of exact GED.
- Node-level and graph-level embedding: Prior node representation methods include matrix factorization, skip-gram, autoencoder, and neighbor-aggregation approaches.Examples include NetMF, DeepWalk, Node2Vec, LINE, SDNE, GCN, and GraphSAGE.
- Node-level and graph-level embedding: Graph-level embeddings can be generated by aggregating node-level embeddings into one representation per graph.
- Graph distance/similarity metrics: GED is the minimum-cost sequence of graph edit operations transforming one graph into another, while MCS is equivalent to GED under a certain cost function.
- Graph distance/similarity search: Database graph-similarity studies accelerate querying around exact GED computations, whereas SimGNN is more comparable to approximate pairwise GED algorithms.
6 DISCUSSIONS AND FUTURE DIRECTIONS
The paper identifies three future directions: incorporating edge features, improving top-k precision, and testing generalization to large graphs trained from small-graph GEDs.
- Model scope: SimGNN handles node types but cannot process edge features, limiting applicability to graphs with labeled edges such as chemical compounds.
- Precision: Top-k precision is not preserved well, mainly because the training dataset has a skewed similarity distribution.
- Scalability: Generalization to large graphs remains an open direction because exact GEDs for large graphs cannot be computed and training uses small-graph GEDs.
7 CONCLUSION
The conclusion presents SimGNN as a neural-network bridge between graph deep learning and graph search for graph similarity computation. The model is representation-invariant, inductive, metric-adaptive, fast, and competitively accurate against approximate GED algorithms.
- SimGNN learns a function that takes two graphs as input and outputs their similarity score.
- The learned function is designed to be representation-invariant, inductive, and adaptive to the specific similarity metric.
- SimGNN runs very fast compared with classic algorithms for approximate GED computation and achieves competitive accuracy.