PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Matching Networks for Learning the Similarity of Graph Structured Objects

Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, Pushmeet Kohli

arXiv:1904.12787v2cs.LGstat.ML

TL;DR

Graph similarity retrieval requires models that reason over both structure and semantics, but existing graph methods do not directly provide learned similarity for this setting. The paper learns graph embeddings with GNNs and introduces Graph Matching Networks using cross-graph attention; across evaluated tasks, these approaches outperform established and structure-agnostic baselines. GMNs are more expressive but costlier, so the paper recommends them for pairwise comparison or reranking filtered candidates.

  • Problem

    Graph similarity learning supports retrieval tasks such as binary function vulnerability search, where similarity depends on both graph structure and semantics.

  • Method

    The paper trains GNNs to embed graphs for vector-space similarity and introduces Graph Matching Networks that compute pairwise similarity through cross-graph attention.

  • Results

    Across graph edit-distance learning, binary function similarity search, and mesh retrieval, the proposed models outperform established baselines and structure-agnostic models; GMNs also outperform graph embeddings and Siamese networks.

  • Takeaways & Limitations

    Graph Matching Networks provide a stronger similarity model by comparing graph pairs throughout computation, while graph embeddings remain useful for efficient indexing and filtering.

  • Takeaways & Limitations

    GMNs require at least O(|V1||V2|) time for cross-graph attention and cannot directly index large graph databases, motivating filtering followed by reranking.

Abstract

from arXiv · show

This paper addresses the challenging problem of retrieval and matching of graph structured objects, and makes two key contributions. First, we demonstrate how Graph Neural Networks (GNN), which have emerged as an effective model for various supervised prediction problems defined on structured data, can be trained to produce embedding of graphs in vector spaces that enables efficient similarity reasoning. Second, we propose a novel Graph Matching Network model that, given a pair of graphs as input, computes a similarity score between them by jointly reasoning on the pair through a new cross-graph attention-based matching mechanism. We demonstrate the effectiveness of our models on different domains including the challenging problem of control-flow-graph based function similarity search that plays an important role in the detection of vulnerabilities in software systems. The experimental analysis demonstrates that our models are not only able to exploit structure in the context of similarity learning but they can also outperform domain-specific baseline systems that have been carefully hand-engineered for these problems.

1. Introduction

The paper studies graph similarity learning for retrieval, using GNN embeddings and a pairwise Graph Matching Network that reasons across graphs. Across synthetic and real-world tasks, the proposed models outperform established and structure-agnostic baselines.

  • Graph Embeddings: GNNs propagate local structural information into node representations that can be pooled into graph vectors for downstream learning.The paper investigates training these representations so similar graphs are close and dissimilar graphs are far apart in vector space.
  • Motivation: Graph similarity learning must capture both graph structure and semantics, as structurally different graphs can be similar while subtle differences can change meaning.Binary function similarity search illustrates this challenge because control-flow graphs may represent the same function despite compiler-induced differences.
  • Graph Embeddings: Precomputed graph embeddings can be indexed with fast nearest-neighbor structures, enabling efficient retrieval from large databases.The passage names k-d trees and locality-sensitive hashing as example indexing methods.
  • Graph Matching Networks: Graph Matching Networks compute similarity through cross-graph attention, associating nodes and identifying differences while jointly representing both graphs.Unlike independent graph embeddings, the matching computation depends on the input pair and offers an accuracy-computation trade-off.
  • Evaluation: The models are evaluated on graph edit-distance learning, binary function similarity search, and mesh retrieval.The real-world tasks require reasoning about both structural and semantic similarity.
  • Results: On all tasks, the proposed approaches outperform established baselines and structure-agnostic models, while Graph Matching Networks outperform graph embeddings and Siamese networks in ablations.The contribution summary also reports strong performance across applications against hand-engineered baselines.

2. Related Work

Related work spans GNN representation learning, graph similarity search, graph kernels, metric learning, and Siamese networks. The paper positions its contribution as learned similarity for graphs rather than graph identity testing or efficiency-focused non-learning methods.

  • Graph Neural Networks and Graph Representation Learning: GNN research uses propagation processes and modern neural components to learn node and graph representations for structured data.Related work also studies GNN discriminative power relative to the Weisfeiler-Lehman algorithm.
  • Graph Similarity Search and Graph Kernels: Graph similarity search commonly uses exact matching or structural measures such as graph edit distance, with many approaches prioritizing efficiency rather than learning.These methods include full-graph and subgraph isomorphism approaches.
  • Graph Similarity Search and Graph Kernels: Graph kernels measure similarity through walks, paths, or bounded-size substructures for use in kernel-based learning methods.The cited families include walk/path kernels and subtree-based kernels.
  • Distance Metric Learning: Metric learning traditionally learns distances in vector spaces, often using a linear metric to group similar examples and separate dissimilar ones.The paper extends the similarity-learning perspective to graph-structured inputs.
  • Siamese Networks: Siamese networks independently encode two inputs with shared parameters before fusing their representations to compute similarity.The paper contrasts this late fusion with graph matching models that perform cross-graph computations earlier.

3. Deep Graph Similarity Learning

The paper develops independent graph embeddings and pair-dependent Graph Matching Networks for graph similarity learning. GMNs use cross-graph attention to compare nodes and identify differences, trading additional computation for stronger matching, while training supports vector- and binary-based retrieval.

  • Graph Embedding Models: Graph embedding models encode each graph independently into a vector, then compute similarity using a metric such as Euclidean, cosine, or Hamming distance.The GNN embedding model consists of an encoder, propagation layers, and an aggregator.
  • Graph Embedding Models: The encoder maps node and edge features through separate MLPs, while propagation layers iteratively aggregate local neighborhood information.Node and edge features are transformed into initial representations before message passing across edges.
  • Graph Embedding Models: The aggregator transforms node representations and uses gated weighted sums to filter irrelevant information when producing a graph-level representation.The weighted sum is reported to work better empirically than a simple sum.
  • Graph Matching Networks: Graph Matching Networks jointly process a graph pair through cross-graph attention that associates nodes and measures how well nodes match across graphs.GMNs modify each propagation layer to incorporate cross-graph matching vectors alongside within-graph edge messages.
  • Graph Matching Networks: Cross-graph attention costs O(|V1||V2|) per operation, compared with O(|V| + |E|) per propagation round for the GNN embedding model.The paper presents this extra computation as the source of GMNs’ additional power and as an accuracy-computation trade-off.
  • Graph Matching Networks: Unlike embedding models, GMNs can change each graph’s representation based on the graph it is compared with, making mismatches more distinct.The matching vectors capture cross-graph differences, which are amplified through propagation.
  • Learning: The models can be trained with pairwise or triplet objectives that encourage similar graphs to be closer than dissimilar graphs by a margin.Pairwise training uses similar/dissimilar labels, whereas triplet training uses relative similarity among three graphs.
  • Learning: Binary graph representations enable fast retrieval and indexing through Hamming distance, but restrict vectors from freely occupying the Euclidean space.The paper uses tanh-transformed representations and reports bounded losses that push positive and negative pairs toward opposite Hamming similarities.

4. Experiments

The experiments evaluate graph embedding and matching models across synthetic graph-edit-distance learning and real-world retrieval tasks. GMNs consistently outperform embedding models and baselines, while cross-graph attention aligns or differentiates graph nodes.

  • GMNs consistently outperform graph embedding models and established baselines across synthetic graph-edit-distance learning, binary function similarity search, and mesh retrieval tasks.The experiments include one structural-similarity task and two tasks requiring structural and semantic similarity.
  • 4.1. Learning Graph Edit Distances: Graph edit distance measures the minimum number of node and edge edits needed to transform one graph into another, but computing it is NP-hard in general.The synthetic task tests whether models can learn structural similarity despite this computational challenge.
  • 4.1. Learning Graph Edit Distances: On graphs sampled from specific distributions, GMNs outperform GNN embedding models and generic baselines when learning similarity from positive and negative edge-substitution examples.Positive pairs use fewer substituted edges than negative pairs, with kp < kn; symmetry and isomorphism can make actual edit distances smaller than the substitution counts.
  • 4.2. Control Flow Graph based Binary Function Similarity Search: Cross-graph attention aligns nodes well when graphs match and focuses on higher-degree nodes when they do not, although its patterns are less interpretable than standard attention.The visualization uses attention weights after five propagation layers, with weight magnitude represented by green-edge transparency.
  • 4.2. Control Flow Graph based Binary Function Similarity Search: In binary function similarity search, graph embedding and matching performance improves with more propagation steps, and matching models outperform embedding models across settings.The models are trained on CFGs generated from ffmpeg compiled with different compilers and optimization levels; the WL kernel achieves 0.619 AUC and 24.5% triplet accuracy.
  • 4.3. More Baselines and Ablation Studies: Table 2 compares additional results for function similarity search and the COIL-DEL dataset, while ablations compare GNN, GCN, Siamese, and GMN alternatives.The reported comparisons examine whether graph convolutions, learned similarity over graph vectors, and early cross-graph communication affect performance.

5. Conclusions and Discussion

The paper studies graph similarity learning with GNNs and introduces matching models that compare graph pairs directly. Matching improves expressivity but adds computational costs that constrain large-scale retrieval use.

  • Similarity learning can accommodate datasets with many classes and few examples per class, unlike a classification formulation tied to predefined classes.
  • Graph Matching Networks compare graphs at all levels in addition to embedding computation, allowing the model to allocate capacity between both components.
  • Full cross-graph attention requires at least O(|V1||V2|) time, which may be expensive for large graphs.
  • Matching models cannot directly index and search large graph databases because they operate on graph pairs.
  • For retrieval, the paper recommends using a faster embedding or graph-search model to filter candidates before matching-model reranking.
  • Improving matching efficiency, adapting GNN capacity to graph sizes, and extending applications remain open challenges.

A. Extra Details on Model Architectures

The supplementary architecture details describe message, node-update, aggregation, and attention components used in the embedding and matching models.

  • Sharing parameters across propagation layers is available as an inductive-bias choice.
  • Message propagation uses a one-hidden-layer MLP with ReLU, while GRUs generally outperform one-hidden-layer MLPs as node-update modules.The reported models use GRUs for node updates.
  • Embedding-model node updates receive summed edge messages, whereas matching-model updates receive concatenated cross-graph attention messages.
  • The aggregator uses linear node-transformation and gating layers, followed by a same-size hidden-layer MLP with ReLU.
  • Matching attention weights are computed for cross-graph node associations, using a specified node similarity function.The text lists Euclidean and dot-product similarities as alternatives.
  • The compared node-state vectors have similar performance without a significant difference.

B. Extra Experiment Details

The experiments fix model dimensionalities across graph-edit-distance and binary-function-similarity tasks, while noting both overfitting and possible gains from larger models.

  • Node states are fixed at dimension 32 and graph vectors at dimension 128 for both graph-edit-distance learning and binary-function-similarity search.
  • Larger models perform better than smaller models on function similarity search, but increasing model size leads to overfitting there.
  • The same dimensionality setting is used for edit-distance learning without further tuning, although larger models may improve performance on that task.

B.1. Learning Graph Edit Distances

The supplementary experiments examine architecture choices and generalization for graph edit-distance learning. Models trained on small graphs can generalize to larger graphs, while performance depends on graph representation capacity and training distributions.

  • Pair training performs slightly better than triplet training, and increasing propagation depth consistently helps.
  • The Weisfeiler-Lehman kernel represents graphs through iteratively updated node-pattern histograms and compares the resulting graph vectors by dot product.
  • The supplementary section presents additional tests of the proposed models' generalization capabilities.
  • Graph similarity-learning models trained on graphs with n from 20 to 50 generalize to evaluation graphs with n equal to 100 or 200.The experiment varies edge density between 0.2 and 0.5.
  • The fixed-size graph vector partly contributes to weaker performance than the Weisfeiler-Lehman kernel, which has more effective features for similarity computation.
  • Training on kp = 2, kn = 3 produces better performance on kp = 1, kn = 2 than training directly on the latter setting.The passage describes this result as surprising and attributes value to good training data.

B.2. Binary Function Similarity Search

This section reports implementation choices and training findings for binary function similarity search, including strong performance on a small supplementary dataset but limited reliability there.

  • Model and data: Binary-function graphs incorporate assembly-instruction features at each node alongside graph structure.The extracted operator types from assembly instructions are embedded for use in similarity learning.
  • Model and data: The study searches over training objective, learning rate, propagation depth, parameter sharing, and node-update architecture.The compared choices include triplet versus pair training, learning rates of 10^-3 and 10^-4, shared versus separate propagation parameters, and GRUs versus one-layer MLPs.
  • Training findings: Triplet training, more propagation layers, separate propagation parameters, and GRUs generally perform better, while the smaller learning rate is more stable.These are aggregate findings across the tested hyperparameters; both learning rates can work.
  • Limitations: The supplementary unrar dataset contains around 400 functions, making overfitting a major problem and rendering its results unreliable for drawing conclusions.The dataset was created by compiling unrar with different compilers and optimization levels.
  • Visualizations: Figure 5 provides additional control-flow-graph examples, while Figure 6 shows the training-set graph-size distribution sorted by graph size.Each Figure 6 point represents one graph’s size.

C. Extra Attention Visualizations

The extra visualizations examine how cross-graph attention evolves across propagation steps for isomorphic graphs, symmetric chains, and graphs one edit apart. They also show example control-flow graphs and the training-set graph-size distribution.

  • Attention dynamics: The attention visualizations unroll a five-layer shared-parameter matching model for up to nine propagation steps, with sensible maps even beyond training depth.The model was trained with five propagation layers, while evaluation uses up to nine unrolled steps.
  • Limitations: Attention maps need not become sharply peaked because node states simultaneously carry propagation information and drive attention.The paper suggests separate key, query, and value vectors as a possible improvement.
  • Attention dynamics: In-graph symmetries can leave attention unpeaked while producing zero cross-graph communication vectors and identical graph representations.Thus, diffuse attention can still preserve identical representations for symmetric isomorphic graphs.
  • Control-flow graphs: Figure 5 shows the same binary function compiled with different compilers and optimization levels, with assembly instructions attached to graph nodes.The leftmost example uses clang and the others use gcc; learned similarity features also use the node instructions.
  • Control-flow graphs: Figure 6 sorts training graphs by size along the x axis, with each plotted point representing one graph’s size.The passage describes the encoding but does not report a numerical distribution.
  • Attention dynamics: For isomorphic chains with in-graph symmetries, final attention assigns equal weight to corresponding nodes except at the chain center, which has one match.The visualized matching concentrates substantially on correct correspondences.
  • Attention dynamics: For isomorphic graphs with edit distance 0, the visualizations track cross-graph attention changes across propagation layers.The figure specifically uses a pair of isomorphic graphs with graph edit distance 0.
  • Attention dynamics: For graphs with edit distance 1, the visualizations likewise show how cross-graph attention changes over propagation layers.The figure isolates a pair whose edit distance is one.
Loading 1904.12787v2…