PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching

Yunsheng Bai, Hao Ding, Yizhou Sun, Wei Wang

arXiv:1809.04440v2cs.LGstat.ML

TL;DR

Exact graph similarity measures are NP-hard to compute, and graph-level embeddings can miss differences across graph sizes and fine-grained structures. GRAPHSIM directly matches node embeddings through pairwise similarity scores, achieving the best reported performance in six of eight settings across four datasets.

  • Problem

    Exact graph similarity computation is NP-hard, and fixed-dimensional graph embeddings may fail to capture size variation and fine-grained structural differences.

    Source: §1 · pp. 1–2

  • Method

    GRAPHSIM forms pairwise node-node similarity scores from two sets of node embeddings and processes their similarity matrix instead of representing each graph by one fixed-dimensional vector.

    Source: §1 · p. 2

  • Results

    GRAPHSIM achieves the best reported results in six of eight settings across four graph-similarity datasets.

    Source: §1 · p. 2, Effectiveness · p. 5

  • Takeaways & Limitations

    The method can be combined with existing node-embedding approaches and learns interpretable similarity patterns in input graph pairs.

    Source: §1 · p. 2, §6 · p. 7

    Reducing the computational time complexity of node-node similarity computation remains a future direction.

    Source: §6 · p. 7

Abstract

from arXiv · show

Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a trade-off between accuracy and speed. Recently, several data-driven approaches based on neural networks have been proposed, most of which model the graph-graph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixed-dimensional embedding per graph may fail to fully capture graphs in varying sizes and link structures, a limitation that is especially problematic for the task of graph similarity computation, where the goal is to find the fine-grained difference between two graphs. In this paper, we address the problem of graph similarity computation from another perspective, by directly matching two sets of node embeddings without the need to use fixed-dimensional vectors to represent whole graphs for their similarity computation. The model, GraphSim, achieves the state-of-the-art performance on four real-world graph datasets under six out of eight settings (here we count a specific dataset and metric combination as one setting), compared to existing popular methods for approximate Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) computation.

1 Introduction

Graph similarity supports graph-based applications, but exact measures are computationally difficult and graph-level embeddings may miss size variation and fine-grained structural differences. GRAPHSIM instead compares node embeddings directly, with reported improvements across most benchmark settings.

1 Introduction

  • Graph similarity is a core operation in graph applications, while exact GED and MCS computation is NP-hard.Approximate methods include traditional heuristics and neural approaches trained on ground-truth similarity scores for fast test-time estimates.Source: §1 · p. 1
  • Fixed-length graph-level vectors may miss differences across graph sizes and small local structures, limiting fine-grained node correspondence.The paper notes this limitation is especially relevant for more structurally varied graphs.Source: §1 · pp. 1–2
  • GRAPHSIM avoids graph-level embeddings by building pairwise node-node similarity scores from the two sets of node embeddings.The resulting similarity matrix is designed to encode graph-pair similarity patterns for neural processing.Source: §1 · p. 2
  • The approach must address permutation invariance, spatial locality preservation, fixed-length CNN inputs, and patterns at multiple structural scales.These are identified as challenges for applying CNNs to graph similarity.Source: §1 · p. 2
  • Six of eight settings show improved performance for GRAPHSIM across four graph-similarity datasets, and the model learns interpretable similarity patterns.The reported settings cover GED and MCS evaluation.Source: §1 · p. 2

2 Related Work

Prior graph representation work includes node and graph embedding methods, while neural graph matching mostly relies on graph-level representations. The related methods differ in how much node-node similarity information they use before producing a graph-level comparison.

2 Related Work

  • Node embedding methods include neighbor-aggregation approaches such as GCN, GraphSAGE, and GIN, which are permutation-invariant.The passage situates these methods within broader work on node and graph representation learning.Source: §2 · p. 2
  • Neural graph matching remains relatively unexplored, and most methods first form one graph embedding before comparing graphs.The paper connects its direct node-embedding matching motivation to successful sequence matching with word embeddings.Source: §2 · p. 2
  • SMPNN sums node-node similarity scores, SIMGNN uses their histogram features, and GMN adds cross-graph attention; these methods still rely substantially on graph-level embeddings.GCNMEAN and GCNMAX use graph coarsening to generate graph-level embeddings.Source: §2 · p. 2

3 Problem Definition

The paper defines graph similarity computation as learning a neural function that maps two input graphs to a chosen similarity score. It describes GED and connected MCS as alternative target measures and confines the studied graphs to undirected, unweighted forms.

3 Problem Definition

  • Graphs are defined by a node set V and edge set E, and this study considers undirected, unweighted graphs.The authors state that extending GRAPHSIM to other graph types is not difficult.Source: §3 · p. 2
  • GED counts the edit operations in an optimal alignment that transforms one graph into another.Allowed operations include node or edge insertion or deletion and node relabeling; the paper maps GED to a similarity score between 0 and 1.Source: §3 · p. 3
  • The paper uses connected MCS: the largest-node subgraph common to both graphs, scored by its number of nodes.Figure 1 illustrates an example with MCS size 4.Source: §3 · p. 3, Figure 1 · p. 3
  • The learning objective is a neural function that takes two graphs and predicts the chosen similarity score, including for unseen test pairs.The later method connects this objective to set matching.Source: §3 · p. 3

4 The Proposed Approach: GRAPHSIM

GRAPHSIM computes graph similarity directly from multi-scale node embeddings, using node-pair similarity matrices rather than fixed-size graph representations. CNNs learn matching patterns from these matrices to predict a graph-pair score.

4 The Proposed Approach: GRAPHSIM

  • GRAPHSIM generates multi-scale node embeddings, forms pairwise similarity matrices, and uses CNN and fully connected layers to predict graph-pair similarity.The framework can use GCNs or successors such as GraphSAGE and GIN.Source: §4 · p. 3, Multi-Scale Neighbor Aggregation · p. 3

Multi-Scale Neighbor Aggregation

  • Stacked GCN layers aggregate each node’s neighbors and itself, while using outputs from multiple layers captures different neighborhood scales and helps retain subtle local patterns.The neighbor-aggregation approach generates node embeddings from local substructure information and applies to unseen nodes.Source: Multi-Scale Neighbor Aggregation · p. 3

Similarity Matrix Generation

  • BFS ordering places nearby nodes close together; max padding preserves size differences, and bilinear resizing produces fixed M × M matrices with information loss controlled by M.The padding scheme adds zero rows to the smaller graph’s embedding matrix before resizing.Source: Similarity Matrix Generation · pp. 4–5

CNN Based Similarity Score Computation

  • Parallel CNN channels process the similarity matrices, concatenate their outputs, and feed fully connected layers trained by mean squared error against metric-derived similarity scores.GED distances are mapped to similarity scores; for MCS, the normalized MCS size is used.Source: CNN Based Similarity Score Computation · p. 5

5 Experiments

The experiments assess GRAPHSIM’s accuracy and speed against existing methods, then examine its components and the interpretations supported by its similarity matrices.

5 Experiments

  • Across four datasets, the evaluation compares GRAPHSIM with state-of-the-art GED/MCS methods and neural baselines using accuracy and ranking metrics.Datasets are split 6:2:2 for training, validation, and testing; metrics include MSE, Spearman’s ρ, Kendall’s τ, and precision at k.Source: §5 · p. 5

Effectiveness

  • GRAPHSIM achieves the best results across all reported metrics, datasets, and GED/MCS tasks, with the strongest performance in six of eight dataset-metric settings.The evaluation covers four datasets; Table 1 reports GED effectiveness and Table 2 reports MCS effectiveness.Source: Effectiveness · p. 5, Table 1 · p. 6, Table 2 · p. 6

Efficiency

  • Neural models are generally much faster than exact solvers, while EMBAVG is fastest but performs poorly and BEAM and HUNGARIAN scale poorly on IMDB.MCSPLIT runs faster than the exact GED solver A* on all datasets; runtime comparisons average across queries and use a log-scale axis.Source: Efficiency · pp. 5–6, Figure 3 · p. 6

Analysis of Various Proposed Techniques in GRAPHSIM

  • Max padding and resizing reduce approximation error most on IMDB and PTC, while multi-scale comparison and BFS ordering also improve performance.The reported explanation for the larger IMDB and PTC gains is their larger average graph size and graph-size variance.Source: Analysis of Various Proposed… · p. 6, Table 3 · p. 7

Analysis of Similarity “Images” in GRAPHSIM

Case Studies

  • In four example queries, GRAPHSIM retrieves graphs similar to each query; for LINUX, its top six results are isomorphic to the query.The examples include one query from each dataset, with returned graphs ranked by the model.Source: Case Studies · p. 7

6 Conclusion

GRAPHSIM uses a CNN-based method and existing node-embedding methods to improve graph similarity computation on GED and MCS. The conclusion identifies computational efficiency and extensions to other graph-matching tasks as future directions.

6 Conclusion

  • GRAPHSIM combines a CNN-based graph-similarity method with existing node-embedding methods to improve performance on GED and MCS.The reported improvements span several datasets.Source: §6 · p. 7
  • The authors identify hierarchical graph representations as a future direction for reducing the time complexity of node-node similarity computation.Source: §6 · p. 7
  • They also propose extending CNN-based graph matching to network alignment and generating explicit GED edit sequences or MCS node correspondences.Source: §6 · p. 7

Supplementary Material

The supplementary material connects GRAPHSIM to graph kernels and bipartite matching, then frames it as a trainable, multi-scale set-matching approach. These connections distinguish its learnable mapping and inference procedure from assignment-based methods.

Connection with Optimal Assignment Kernels

  • Unlike the EMD kernel, GRAPHSIM jointly learns its mapping and node embeddings for graph-distance approximation; its convolution runs in O(max(N1, N2)^2) time versus O(N^3logN) for the kernel's best average assignment solver.The EMD kernel treats graphs as bags of non-trainable node embeddings and computes an optimal travel cost.Source: Connection with Optimal Assignment… · p. 10

Connection with Bipartite Graph Matching

  • Exact bipartite assignment yields GED but is NP-complete; GRAPHSIM uses exact assignment solutions during training and approximates GED in quadratic time without solving an optimization problem for each new pair.Source: Connection with Bipartite Graph Matching · p. 11

A Convolutional Set Matching

Set Matching Based Graph Similarity Computation

B Datasets

The experiments use four real-world graph datasets spanning chemical compounds, program-dependence graphs, and actor collaboration networks. Dataset sizes and pair counts vary substantially.

B Datasets

  • AIDS and PTC are chemical-compound datasets, LINUX contains program-dependence graphs, and IMDB contains actor collaboration ego-networks.AIDS has 700 selected graphs, LINUX 1,000, IMDB 1,500, and PTC 344.Source: B Datasets · p. 11
  • The datasets differ in graph characteristics: AIDS nodes have 29 labels, while LINUX, IMDB, and PTC nodes are unlabeled.Source: B Datasets · p. 11
  • The experiments evaluate 490K AIDS, 1M LINUX, 2.25M IMDB, and 118K PTC graph pairs across three domains.Source: B Datasets · p. 11

C Data Preprocessing

The supplementary experiments describe preprocessing and model settings, compare GRAPHSIM with baselines, and examine scalability and parameter sensitivity. Results include a REDDIT12K comparison, while ablations and analyses discuss what distinguishes the matching approach.

C Data Preprocessing; D Model Configurations

  • A* supplies GED labels for AIDS and LINUX, IMDB uses the minimum distance from BEAM, HUNGARIAN, and VJ, and MCS labels come from MCSPLIT; the shared architecture uses three GCN layers except for GMN.Testing graphs are queried against training and validation graphs after a random 60/20/20 split.Source: C Data Preprocessing · pp. 11–12, D Model Configurations · p. 12

Approximate GED algorithms

SMPNN; EMBAVG, GCNMEAN and GCNMAX

SIMGNN

  • SIMGNN's histogram features are non-differentiable and ignore node positions, whereas GRAPHSIM uses node ordering to preserve position information.Source: SIMGNN · p. 13

GMN

  • On AIDS, GRAPHSIM with GMN node embeddings performs better than either model alone on MCS, although GMN alone outperforms GRAPHSIM on that metric.Source: GMN · p. 13

F Theoretical Time Complexity

  • GRAPHSIM inference has O(max(N1, N2)^2) time complexity, the same as SIMGNN and GMN, with GPU acceleration available for dense matrix multiplication.The method's multi-scale node-embedding generation is O(|E|).Source: F Theoretical Time Complexity · pp. 13–14

G Scalability Study

  • On REDDIT12K, GRAPHSIM-W/GMN achieves the best effectiveness and is faster than most approximate GED and MCS algorithms, though slower than EMBAVG.It is also reported as more effective than the simpler methods.Source: G Scalability Study · p. 14

H Parameter Sensitivity

  • On AIDS, CNN depth mattered more than the other tested parameters: performance improved with more CNN layers but changed little beyond five, while additional GCN layers had little effect.Figure 6 reports mean squared error for the tested dimensions and layer counts.Source: H Parameter Sensitivity · p. 14, Figure 6 · p. 14

Related Task 1: Graph Database Search

Graph database search uses filtering and verification to reduce exact GED computations, while this work takes a different approach to obtaining ground truth for relatively large graphs; combining the approaches is proposed as future work.

Related Task 1: Graph Database Search

Related Task 2: Graph Alignment

Graph alignment focuses on node correspondences, whereas graph similarity computation focuses on graph-level similarity; GraphSim learns from general similarity metrics, and extension to node-level alignment remains future work.

Related Task 2: Graph Alignment

  • Graph alignment concerns node-level mappings, while graph similarity computation concerns graph-level similarity.Both fall under the broader category of graph matching.Source: Related Task 2: Graph Alignment · pp. 14–15
  • Unlike the isomorphic-graph and edge-removal setup described by Heimann et al. (2018), GraphSim can learn from metrics such as GED or MCS when their true scores are provided.The cited alignment setup permutes node IDs and randomly removes edges without disconnecting nodes; GraphSim accommodates broader graph transformations, including node deletion.Source: Related Task 2: Graph Alignment · p. 15
  • Extending GraphSim to graph alignment is a proposed future direction requiring finer, node-level comparisons.Source: Related Task 2: Graph Alignment · p. 15
Loading 1809.04440v2…