Research map / Graph learning / GNN architectures
Can Graph Neural Networks Count Substructures?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LRP with depth-1 egonets for substructure counting | LRP · Synthetic graphs, radius-1 patterns | normalized test MSE: 1.56E-4 (triangle) and 2.17E-5 (3-star) on Erdős-Renyi; 2.47E-4 (triangle) and 1.88E-6 (3-star) on Random Regular | Helped |
| Use LRP-1-3 instead of PPGN | Synthetic random graphs · Triangle induced-subgraph-count | normalized test MSE: 5.08E-8 vs 1.56E-4 (Erdős-Renyi); 1.40E-6 vs 2.47E-4 (Random Regular) | Mixed |
| Use Deep LRP-1-3 with early stopping | Deep LRP-1-3 · ogbg-molhiv test | ROC-AUC (%): 76.87$\pm$1.80 -> 77.19$\pm$\textbf{1.40} | Helped |
| Use Deep LRP-5-1 instead of MPNN | QM9 · ε_homo test | MAE: 0.00541 -> 0.00254 | Helped |
| Use Deep LRP-5-1 instead of MPNN | QM9 · ε_lumo test | MAE: 0.00623 -> 0.00277 | Helped |
| Use Deep LRP-5-1 instead of MPNN | QM9 · Δε test | MAE: 0.0066 -> 0.00353 | Helped |
| Use Deep LRP-7-1 instead of GatedGCN-E-PE without feature augmentation | ZINC · ZINC test | MAE: 0.214 $\pm$ 0.013 -> 0.223 $\pm$ 0.008 | Hurt |
| Use Deep LRP-5-1 instead of PPGN | QM9 · Total loss | Loss: 0.0512 -> 0.0567 | Hurt |
| Use MPNNs or 2-IGNs to count connected induced patterns with at least 3 nodes | MPNNs and 2-IGNs · Attributed graphs, connected patterns with 3 or more nodes | induced-subgraph-count expressivity | Hurt |
| Use MPNNs or 2-IGNs to count star-shaped subgraphs | MPNNs and 2-IGNs · Attributed graphs, star-shaped patterns | subgraph-count expressivity | Helped |
| Increase tuple order to k for counting patterns of size at most k | k-WL and k-IGN · Attributed graphs, patterns of at most k nodes | subgraph and induced-subgraph count expressivity | Helped |
| Limit k-WL to T iterations | k-WL · Path patterns with (k+1)2^T or more nodes | induced-subgraph-count expressivity: (k+1)2^T or more nodes | Hurt |
Closest papers by meaning
- Graph Neural Networks Can (Often) Count Substructures (ICLR 2025 · similarity 0.96)
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.93)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.88)
- On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters (ICLR 2024 · similarity 0.88)
- Deep Homomorphism Networks (NeurIPS 2024 · similarity 0.88)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 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.