PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Subgraph Matching

Rex, Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec

arXiv:2007.03092v2cs.LGstat.ML

TL;DR

Subgraph matching matters across biology, social networks, and knowledge graphs, but existing approaches struggle with large query and target graphs. NeuroMatch embeds overlapping subgraphs using a GNN and geometric constraints, and the paper reports faster matching than exact combinatorial approaches alongside improved AUROC over neural graph-matching methods.

  • Problem

    Existing subgraph-matching approaches struggle to scale to large problems: combinatorial methods face NP-completeness, while preprocessing-based methods have difficulty decomposing queries beyond a few tens of nodes.

    Source: §1 · p. 1

  • Method

    NeuroMatch embeds overlapping target and query neighborhoods with a GNN and trains geometric order constraints to represent subgraph relations for matching in embedding space.

    Source: §1 · p. 1

  • Results

    Two orders of magnitude faster than exact combinatorial approaches, NeuroMatch improves AUROC by 18% over neural graph-matching methods adapted to subgraph matching.

    Source: §1 · p. 2

  • Takeaways & Limitations

    NeuroMatch demonstrates the potential of GNNs and geometric embeddings for predicting subgraph relationships.

    Source: §4 · p. 8, §6 · p. 8

    The approach remains subject to GNN expressive-power limitations, which it alleviates by distinguishing anchor nodes through node features.

    Source: §4 · p. 8

Abstract

from arXiv · show

Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.

1. INTRODUCTION

NeuroMatch addresses the difficulty of matching large query and target graphs by embedding overlapping subgraphs and encoding their containment relationships geometrically. The paper reports faster matching than exact combinatorial approaches and higher AUROC than neural graph-matching methods.

1. INTRODUCTION

  • Subgraph matching is important across biology, social networks, and knowledge graphs, but existing approaches struggle to scale to large problems.Combinatorial methods are limited by NP-completeness; preprocessing-based methods decompose queries into small components, and queries above a few tens of nodes make that decomposition difficult.Source: §1 · p. 1
  • NeuroMatch embeds small overlapping subgraphs from both target and query graphs with a GNN, then compares node embeddings to determine subgraph relations.The target graph is decomposed into k-hop neighborhoods around each node, and query-node embeddings are compared against target-node embeddings.Source: §1 · p. 1
  • NeuroMatch trains an embedding space whose geometric partial order reflects subgraph containment, drawing on order embeddings.This structure supplies inductive biases and simplifies querying; order embeddings also support navigation for subgraphs and supergraphs.Source: §1 · pp. 1–2
  • The embedding stage can run offline, while geometric constraints make querying linear in the sizes of the query and target graphs.The approach also supports categorical node and edge features and multiple target graphs.Source: §1 · p. 2
  • Two orders of magnitude faster than exact combinatorial approaches, NeuroMatch also improves AUROC by 18% over neural graph-matching methods adapted to subgraph matching.The reported comparisons include state-of-the-art exact and approximate methods and recent neural methods adapted for the task.Source: §1 · p. 2

2. NEUROMATCH ARCHITECTURE

NeuroMatch represents target and query neighborhoods with GNN embeddings, then uses geometric order constraints and neighborhood comparisons to predict subgraph matches. Its training combines sampled examples and a curriculum, while its query-stage work scales with the product of the graph sizes.

2.1. PROBLEM SETUP

  • NeuroMatch frames matching as finding query-isomorphic subgraphs in a target graph, requiring node and edge features to match when present.The paper focuses on the more general edge-induced matching formulation, while noting that the method can also be applied to node-induced matching.Source: §2.1 · pp. 2–3

2.2. OVERVIEW OF NEUROMATCH

  • The two-stage architecture embeds each target node’s k-hop neighborhood and compares query-node embeddings against target-node embeddings to form an alignment matrix and predict matches.The method assumes k is at least the query diameter; experiments report peak voting performance at k = 10 on many real-world graphs.Source: §2.2 · p. 3

2.3. SUBGRAPH PREDICTION FUNCTION f(zq, zu)

  • Order embeddings encode neighborhood containment geometrically: a query neighborhood’s embedding must lie below its target neighborhood’s embedding, and training penalizes violations.The max-margin loss minimizes order violations for positive pairs and requires negative pairs to violate the constraint by at least α.Source: §2.3 · p. 4

2.4. MATCHING NODES VIA VOTING

  • Voting improves anchor-node matching by checking whether each query-neighborhood node can match a node in the target anchor’s neighborhood.The stated constraint allows the corresponding target node to lie within an l-hop neighborhood for l ≤ k.Source: §2.4 · pp. 4–5

2.5. TRAINING NEUROMATCH

  • Training samples positive neighborhood pairs by random BFS and creates negatives both by choosing unrelated nodes and by perturbing queries out of containment.A curriculum starts with one-hop queries and increases query complexity and batch size when training performance plateaus; sampled queries grow in diameter and node count across levels.Source: §2.5 · p. 5, Figure 2 · p. 5
  • NeuroMatch generalizes to test queries sampled by random BFS, random walk with restart, and degree-weighted sampling.The degree-weighted strategy is used in the MFinder motif-mining algorithm.Source: §2.5 · p. 5

2.6. RUNTIME COMPLEXITY

  • Embedding costs O(K(|ET|+|EQ|)), while query matching computes O(|VT||VQ|) scores; exact methods grow exponentially with graph size.For new queries, target-node embeddings can be precomputed in advance, leaving query embedding and embedding comparisons for inference.Source: §2.6 · p. 5

3. EXPERIMENTS

Experiments evaluate NeuroMatch on synthetic and varied real-world graph data for accuracy, runtime, and generalization. The reported results include higher query-to-target AUROC than heuristic baselines and faster inference than exact methods.

3.1. DATASETS AND BASELINES

  • Experiments used synthetic graphs and real-world datasets spanning chemistry, biology, image processing, point clouds, and knowledge graphs, with VF2, RI, FastPFP, IsoRankN, GMNN, and RDGCN as baselines.Evaluation was intended to probe data efficiency and generalization as well as adaptation to real-world graph structures.Source: §3 · pp. 5–6, §3.1 · p. 6

3.2. RESULTS

  • Median AUROC was 95.5 for neighborhood matching, 20% higher than neural baselines.This local prediction task tests whether a query node's neighborhood is a subgraph of a target node's neighborhood, a subroutine for checking query presence in a large graph.Source: Table 1 · p. 6, §3.2 · p. 6
  • NeuroMatch outperformed the ablation variants; box embeddings cannot guarantee intersection between graphs, and variable target sizes made the NTN variant hard to learn.Curriculum training increased performance by an average of 6%, reduced performance variance, and increased convergence speed; the authors relate this benefit to the task's compositional nature.Source: §3.2 · pp. 6–7
  • 18.4% average AUROC improvement over FastPFP and IsoRankN was reported across datasets for query-to-target matching.Table 2 evaluates binary query-in-target prediction in AUROC.Source: §3.2 · p. 7, Table 2 · p. 7
  • Query graphs averaged 51% of target-graph size, which the authors interpret as evidence that the model learns subgraph matching rather than graph isomorphism.Source: §3.2 · p. 7
  • NeuroMatch generalized to queries generated with different sampling strategies, with little performance change; random BFS was the most robust training strategy among those tested.Table 3 reports AUROC for MSRC, with training strategies in rows and test strategies in columns.Source: §3.2 · p. 7, Table 3 · p. 7
  • When trained on synthetic data, NeuroMatch was reported to generalize to test queries from different real-world datasets without fine-tuning.Source: §3.2 · p. 7
  • NeuroMatch ran 100 times faster than exact methods, whose runtime grew exponentially with query size while NeuroMatch's grew linearly.Exact methods were counted as unsuccessful after 10 minutes; NeuroMatch was also reported as 10 times more efficient than NM-MLP and GMNN.Source: §3.2 · p. 8

4. LIMITATIONS

The discussion identifies expressive-power limits of GNNs and describes how NeuroMatch addresses them while allowing future backbone changes.

4. LIMITATIONS

  • NeuroMatch distinguishes anchor nodes through node features to alleviate GNN expressive-power limitations associated with the WL graph-isomorphism test.The paper identifies this limitation in prior work.Source: §4 · p. 8
  • Future work is needed to explore neural approaches to this NP-complete problem.Source: §4 · p. 8
  • NeuroMatch does not explicitly rely on a GNN backbone, so more expressive GNNs can be applied to it directly.Source: §4 · p. 8

5. RELATED WORK

Prior subgraph-matching methods address structure, sometimes categorical node features, or approximate matching. Neural graph-matching methods face a correspondence mismatch with subgraph isomorphism.

5. RELATED WORK

  • Conventional algorithms focus on graph structure, while other methods also account for categorical node features; NeuroMatch supports both settings.The cited examples include Ullmann (1976) and Aleman-Meza et al. (2005) and Coffman et al. (2004).Source: §5 · p. 8
  • Approximate subgraph-matching methods include Christmas et al. (1995) and Umeyama (1988), while NeuroMatch is a machine-learning-based approximate algorithm.Source: §5 · p. 8
  • Graph-isomorphism neural methods lack a direct subgraph-isomorphism application because query and target graphs have no one-to-one node correspondence.NeuroMatch uses node-based representations and order embeddings; discrete matching-correspondence methods are described as complementary.Source: §5 · p. 8

6. CONCLUSION

The conclusion presents NeuroMatch as a neural subgraph-matching algorithm that learns subgraph relationships with GNNs and geometric embeddings. It identifies order embeddings as a natural fit and reports advantages over adapted graph-isomorphism architectures and heuristic algorithms.

6. CONCLUSION

  • NeuroMatch uses graph neural networks and geometric embeddings to learn subgraph relationships.Source: §6 · p. 8
  • Order embeddings are a natural fit for modeling subgraph relationships in embedding space.Source: §6 · p. 8
  • NeuroMatch outperforms adapted graph-isomorphism architectures and shows advantages and potential compared with heuristic algorithms.Source: §6 · p. 8

A. PROOFS OF SUBGRAPH PROPERTIES

The appendix relates subgraph properties to order embeddings, describes conditions under which GNN aggregation preserves order constraints, and explains the rationale and distance caveat for voting.

A. PROOFS OF SUBGRAPH PROPERTIES

B. ORDER EMBEDDING COMPOSITION

  • With sum-based neighborhood aggregation, order constraints at layer k −1 carry to layer k, assuming embeddings satisfy those constraints after transformation.The paper notes that other GNN architectures do not necessarily have this property; this alignment motivates curriculum learning.Source: B. ORDER EMBEDDING COMPOSITION · pp. 11–12

C. VOTING PROCEDURE

  • Voting raises confidence in anchor-node matches by checking whether nearby query nodes have corresponding matches in target neighborhoods.Source: C. VOTING PROCEDURE · p. 12
  • A matched query path has a corresponding target path, but target-graph shortcuts can make the corresponding shortest paths unequal in length.Source: C. VOTING PROCEDURE · p. 12

D. TRAINING DETAILS AND HYPERPARAMETERS

The section reports training and evaluation choices for NeuroMatch, including curriculum sampling, model design, and score aggregation. It also identifies implementation settings and baseline hyperparameters.

D. TRAINING DETAILS AND HYPERPARAMETERS

  • Training samples one query per target graph per epoch, with at least 64 iterations and a 3:1 negative-to-positive example ratio.Ten percent of negative examples are hard negatives; the rest are split between the same and different target graphs.Source: D. TRAINING DETAILS AND HYPERPARAMETERS · p. 12
  • Curriculum training starts with one target graph and radius 1, then increases radius and target-graph count when performance plateaus.The radius rises to at most 4 before the number of target graphs doubles, up to 256; the dataset is regenerated every 50 epochs.Source: D. TRAINING DETAILS AND HYPERPARAMETERS · pp. 12–13
  • The model uses Adam with a 1 × 10−3 learning rate and cosine annealing with restarts every 100 epochs.Models were trained on one GeForce RTX 2080 GPU; baselines used an Intel Xeon E7-8890 v3 CPU, with ISORANKN and FASTPFP hyperparameters specified.Source: D. TRAINING DETAILS AND HYPERPARAMETERS · pp. 12–13
  • Table 5 reports an average confusion matrix for matching queries of size ≤7 to all node neighborhoods in the DD dataset.Source: Table 5 · p. 13
  • Sum aggregation usually performs best; LeakyReLU gives slight improvement, dropout has no significant impact, and structural features improve convergence speed.Source: D. TRAINING DETAILS AND HYPERPARAMETERS · p. 13
  • For binary query-to-target prediction, the mean alignment-matrix score outperformed the Hungarian algorithm; the method remains agnostic to downstream alignment processing.FASTPFP uses a separate score based on topology and node labels, adapted to varying query and target sizes.Source: D. TRAINING DETAILS AND HYPERPARAMETERS · p. 13

E.1. DATASETS

The evaluation spans biological, chemical, social, image, and point-cloud graph datasets. The section describes transfer and in-domain evaluation, graph statistics, and label imbalance.

E.1. DATASETS

  • COX2 and DD are molecule datasets, while the protein-structure and PPI datasets represent protein graphs and tissue interaction networks.COX2 has 467 graphs averaging 41 nodes and 44 edges; DD has 1,178 graphs averaging 284 nodes and 716 edges. PPI comprises 24 tissue networks with 56,944 nodes and 818,716 edges, without node features.Source: §E.1 · pp. 13–14
  • Table 6 compares transfer from synthetic training with in-domain training on real datasets, reporting AUROC in units of 0.01.Source: Table 6 · p. 14
  • Table 7 reports target- and query-graph statistics for Problem 1 evaluation.Source: Table 7 · p. 14
  • MSRC_21 contains 563 image graphs, and FIRSTMMDB contains 41 household-object point-cloud graphs.Their graphs average 78 nodes and 199 edges for MSRC_21, and 1,377 nodes and 3,074 edges for FIRSTMMDB.Source: §E.1 · p. 14
  • The DD confusion-matrix experiment finds extreme label imbalance, with subgraphs rare.It averages results across test queries for matching queries of size ≤7.Source: §E.1 · p. 14

F.1. PRETRAINING ON SYNTHETIC DATASET

The authors test whether training only on synthetic data transfers to real-world datasets. Performance drops, but the model generalizes across several domains; feature-aware matching remains outside this transfer setting.

F.1. PRETRAINING ON SYNTHETIC DATASET

  • Training only on synthetic data generalizes to biology, chemistry, and social-network matching, sometimes outperforming baselines trained on the real datasets.Performance is lower than when training and testing on the same dataset.Source: §F.1 · p. 14
  • Synthetic-data transfer supports only feature-agnostic matching because the synthetic data lack node features and real datasets have varying feature dimensions.Incorporating features into transfer learning remains an open problem.Source: §F.1 · p. 14

G.1. EXACT HEURISTICS METHODS

NeuroMatch is compared with exact matching heuristics and related approximate methods. It is substantially faster than exact baselines, while the discussion distinguishes its larger-graph matching focus from small-motif enumeration.

G.1. EXACT HEURISTICS METHODS

  • VF2 and RI guarantee correct predictions, but can take hours, making them unsuitable when online or high-throughput efficiency is the priority.Source: §G.1 · pp. 14–15
  • NeuroMatch is about 100× faster than exact alternatives; VF2 and RI success rates fall below 60% for queries larger than 30, while NeuroMatch finishes under 0.1 second.Figure 4 reports 100% NeuroMatch success within 20 seconds; Table 8 compares average runtime for query sizes up to 50.Source: §G.1 · p. 15, Table 8 · p. 15, Figure 4 · p. 15
  • Synthetic pretraining with optional brief real-data fine-tuning makes training on a new dataset negligible, but cannot account for categorical node features.Source: §G.1 · p. 15

G.2. APPROXIMATE HEURISTICS METHODS

  • Motif-counting heuristics such as Rand-ESU, MFinder, Motivo, and ORCA target small motifs, typically under six nodes, unlike the larger graphs studied here.This work does not focus on enumerating motifs of a specified size.Source: §G.2 · p. 15
  • Graph-matching methods seek explicit query-to-target isomorphism mappings; convex-relaxation and spectral approaches are heuristic because subgraph matching is hard to approximate.Source: §G.2 · p. 15

H. GNN EXPRESSIVE POWER

Message-passing GNNs can fail to distinguish regular graphs when their computational graphs are identical. NeuroMatch uses anchor-node identification, while evaluating more expressive GNNs for subgraph mining remains future work.

H. GNN EXPRESSIVE POWER

  • NeuroMatch distinguishes an anchor node from other neighborhood nodes using one-hot encoding, addressing a known GNN difficulty with regular graphs.The passage relates this idea to concurrent work on ID-GNNs.Source: H. GNN EXPRESSIVE POWER · p. 15
  • Investigating recently proposed more expressive GNNs for subgraph mining remains future work, although NeuroMatch can use any GNN in its decoder.The framework could benefit from more expressive GNNs.Source: H. GNN EXPRESSIVE POWER · p. 15
  • Standard GNNs can assign identical embeddings to nodes that need different labels when their computational graphs are identical, including in regular-graph examples.ID-GNNs distinguish anchor nodes via one-hot encoding, producing different computational graphs for 3-cycle and 4-cycle examples.Source: H. GNN EXPRESSIVE POWER · p. 15, Figure 5 · p. 16
Loading 2007.03092v2…