Research map / Graph learning / Knowledge and temporal graphs
Charting the Design Space of Neural Graph Representations for Subgraph Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Systematically explores a unified design space (relevance distance, early vs. late interaction, injective vs. non-injective alignment, interaction non-linearity, node vs. edge granularity) for neural subgraph matching and proposes best-performing combinations.
Problem
Neural subgraph matching models for graph retrieval occupy only a few isolated points in a large design space; it is unclear which combinations of design choices matter for retrieving corpus graphs that contain a query graph as a subgraph.
Approach
Refactors existing neural subgraph matching models (IsoNet, GMN, NeuroMatch, SimGNN, ERIC, GotSim, etc.) into a unified framework with five axes and evaluates all combinations, finding that early interaction with set alignment, injective (Sinkhorn) alignment, hinge non-linearity and edge granularity yields the best model.
Key results
- The best early-interaction configuration (set alignment, injective Sinkhorn, hinge, edge granularity) reaches 0.817 MAP on AIDS vs 0.704 for IsoNet, and ranks first on nine of ten datasets.
- The best late-interaction configuration reaches 0.712 MAP on AIDS and 0.643 on NCI1, outperforming IsoNet (0.704, 0.615).
- Early interaction generally outperforms late interaction, and set alignment (EMD-style) outperforms aggregated single-vector distances in most settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace late interaction with early interaction (ablation) | Graph matching models · AIDS and NCI | MAP: 0.557 → 0.726; 0.529 → 0.624 | Helped |
| Use edge rather than node interaction (ablation) | Graph matching models · AIDS and NCI | MAP: 0.557 → 0.635; 0.529 → 0.569 | Mixed |
| Replace aggregated hinge distance with set alignment (ablation) | Late-interaction graph matching models · AIDS and NCI | MAP: 0.557 → 0.664; 0.529 → 0.625 | Helped |
| Replace aggregated hinge distance with set alignment (ablation) | Early-interaction graph matching models · AIDS and NCI | MAP: 0.726 → 0.734; 0.624 → 0.654 | Mixed |
| Use early interaction rather than late interaction (ablation) | Graph matching models · Across the ten datasets | MAP | Helped |
| Use edge rather than node granularity (ablation) | Graph matching models · Across the ten datasets | MAP | Helped |
| Use set alignment rather than aggregated graph distance (ablation) | Graph matching models · Across the ten datasets | MAP | Helped |
| Use injective rather than non-injective alignment (ablation) | Graph matching models · Across the ten datasets | MAP | Helped |
| Use hinge rather than neural or dot-product interaction nonlinearity (ablation) | Graph matching models · Across the ten datasets | MAP | Helped |
| Change interaction nonlinearity from dot product to hinge (ablation) | GMN* · Across the ten datasets | MAP | Helped |
| Change interaction granularity from node to edge (ablation) | GMN* · Across the ten datasets | MAP | Mixed |
| Change interaction structure from non-injective to injective (ablation) | GMN* · Across the ten datasets | MAP | Mixed |
Surprising findings
- Late-interaction IsoNet outperforms early-interaction GMN in prior work, but upgrading GMN with set alignment, injective mapping, hinge non-linearity or edge granularity lets it surpass IsoNet.
- Combining hinge non-linearity with set alignment reduces performance for GMN* because its non-injective mapping is incompatible with hinge.
Limitations
- Does not account for 3D graph topology relevant to applications like ligand screening.
- Robustness to noise and out-of-distribution performance of the design choices is untested.
- Evaluated only on TUDatasets with featureless (constant) node features and synthetic query sampling via BFS.
Experimental setup
Datasets: AIDS MUTAG PTC-FM NCI1 MOLT-4 PTC-FR PTC-MM PTC-MR MCF-7 MSRC-21
Benchmarks: AIDS MUTAG PTC-FM NCI1 MOLT-4 PTC-FR PTC-MM PTC-MR MCF-7 MSRC-21
Metrics: MAP
Baselines: SimGNN GraphSim GotSim ERIC EGSC GREED NeuroMatch IsoNet HMN GMN-Match
Builds on: IsoNet GMN NeuroMatch SimGNN Sinkhorn iterations
Closest papers by meaning
- Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval (NeurIPS 2024 · similarity 0.90)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.88)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.88)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.88)
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering (NeurIPS 2024 · similarity 0.87)
- EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.