Research map / Graph learning / Graph algorithms and clustering
Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval
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.
Proposes IsoNet++, an early-interaction GNN for subgraph-isomorphism graph retrieval that iteratively refines injective (Gumbel-Sinkhorn) node/edge alignments over lazy rounds and uses node-pair partner interaction.
Problem
Graph retrieval based on subgraph isomorphism: given a query graph, rank corpus graphs that contain a subgraph isomorphic to it. Prior late-interaction (IsoNet) models lack explicit consistent alignments, and early-interaction models (GMN) produce non-injective, oversmoothed attention alignments.
Approach
Early-interaction GNN that maintains an explicit doubly-stochastic (injective) node or edge alignment, held fixed during each round of K GNN layers and refined at the end of each round via a Gumbel-Sinkhorn aligner; messages are passed over node pairs (node-pair partner interaction) rather than single-node partners.
Key results
- IsoNet++ (Edge) reaches MAP 0.847 on AIDS and 0.902 on PTC-MM and PTC-MR, beating the best baseline IsoNet (edge) at 0.690 on AIDS and 0.774 on PTC-MR.
- IsoNet++ (Node) reaches MAP 0.825 on AIDS vs 0.659 for IsoNet (node); lazy multi-round updates beat eager multi-layer updates on all six datasets (e.g. 0.825 vs 0.756 on AIDS).
- Learned alignments move closer to gold alignments as rounds increase, with multi-round refinement reported as about twice as fast as multi-layer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use IsoNet++ (Edge) instead of IsoNet++ (Node) | IsoNet++ · AIDS, MUTAG, PTC-FM, PTC-FR, PTC-MM, PTC-MR | MAP: 0.825 -> 0.847; 0.851 -> 0.858; 0.888 -> 0.902; 0.855 -> 0.875; 0.838 -> 0.902; 0.874 -> 0.902 | Helped |
| replace eager multi-layer updates with lazy multi-round updates (ablation) | IsoNet++ (Node) and IsoNet++ (Edge) · AIDS, MUTAG, PTC-FM, PTC-FR, PTC-MM, PTC-MR | MAP: Node: 0.756 -> 0.825, 0.81 -> 0.851, 0.859 -> 0.888, 0.802 -> 0.855, 0.827 -> 0.838, 0.841 -> 0.874; Edge: 0.795 -> 0.84 | Helped |
| add node-pair partner interaction instead of node partner interaction (ablation) | IsoNet++ (Node), lazy updates · AIDS, MUTAG, PTC-FM, PTC-FR, PTC-MM, PTC-MR | MAP: 0.776 -> 0.825; 0.829 -> 0.851; 0.851 -> 0.888; 0.819 -> 0.855; 0.844 -> 0.838; 0.84 -> 0.874 | Helped |
Surprising findings
- The eager multi-layer variant achieves its highest accuracy at K=8 on AIDS despite GNN oversmoothing concerns, which the authors attribute to alignment-based convolution acting as a filter.
- GMN is outperformed by the late-interaction IsoNet because its attention-based alignment is non-injective.
Limitations
- Hashing for fast retrieval is not designed for early-interaction models.
- Model does not handle node or edge labels/class constraints on alignments.
- Inference cost grows with rounds and layers compared with late-interaction models.
Experimental setup
Datasets: AIDS MUTAG PTC-FM PTC-FR PTC-MM PTC-MR
Benchmarks: AIDS MUTAG PTC-FM PTC-FR PTC-MM PTC-MR
Metrics: MAP HITS@20
Baselines: GraphSim GOTSim SimGNN EGSC H2MN NeuroMatch GREED GEN GMN IsoNet (node) IsoNet (edge)
Builds on: IsoNet GMN Gumbel-Sinkhorn NeuroMatch
Closest papers by meaning
- Interpretable Neural Subgraph Matching for Graph Retrieval (AAAI 2022 · similarity 0.92)
- Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks (NeurIPS 2022 · similarity 0.91)
- Charting the Design Space of Neural Graph Representations for Subgraph Matching (ICLR 2025 · similarity 0.90)
- Chaining 2-FWL GNNs for Combinatorial Graph Alignment (NeurIPS 2026 · similarity 0.88)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.87)
- RAGraph: A General Retrieval-Augmented Graph Learning Framework (NeurIPS 2024 · similarity 0.86)
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.