Research map / Graph learning / GNN architectures
On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks
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.
Derives VC-dimension and covering-number sample complexity bounds for GNNs with node individualization schemes, proposes the Tinhofer and TinhoferW schemes and the EGONN architecture for substructure identification.
Problem
How many training samples GNNs with node individualization (random noise, relational pooling, canonical orderings, positional encodings) need to generalize, given they are maximally expressive; existing bounds don't cover individualized GNNs.
Approach
Relate VC dimension of individualized GNNs to the number of WL-isomorphism classes of the relabeled dataset, showing that equivariant deterministic schemes (Tinhofer) lower sample complexity; add a covering-number bound for Lipschitz GNNs and a weak Tinhofer scheme that relabels only non-singleton color classes; and an ego-net GNN (EGONN) with lower VC dimension for substructure identification.
Key results
- On substructure identification (3-regular graphs), EGONN with Tinhofer individualization reaches 99.6% test accuracy on C4 and 100% on C3 and K2,3, versus at most 62% for plain GNN with RP or Tinhofer.
- Tinhofer-individualized 1-layer GNN converges faster and more stably than 5-9 layer GNNs on Cycles-pin, CSL-pin, MCF-7 and Peptides-func.
- Across NCI1, Mutagenicity, IMDB-b and COLLAB-b, the empirical covering-number ratio correlates with the generalization gap; TinhoferW yields lower covering numbers and smaller gaps than RP/RNI.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Tinhofer individualization to EGONN ego-nets (ablation) | EGONN · C4, C5, and K2,3 induced-subgraph identification on 3-regular graphs | test accuracy: 73.6 ±10.2 -> 99.6 ±0.5; 89.4 ±1.5 -> 99.6 ±0.8; 74.2 ±2.2 -> 100.0 ±0.0 | Helped |
| add RP individualization to EGONN ego-nets (ablation) | EGONN · C4 and K2,3 induced-subgraph identification on 3-regular graphs | test accuracy: 73.6 ±10.2 -> 93.2 ±2.1; 74.2 ±2.2 -> 71.6 ±1.9 | Mixed |
| add RP individualization to EGONN ego-nets (ablation) | EGONN · C5 induced-subgraph identification on 3-regular graphs | test accuracy: 89.4 ±1.5 -> 90.6 ±1.0 | Helped |
| add RP individualization to EGONN ego-nets (ablation) | EGONN · C3 induced-subgraph identification on 3-regular graphs | test accuracy: 100.0 ±0.0 -> 100.0 ±0.0 | No clear effect |
| add Tinhofer individualization to EGONN ego-nets (ablation) | EGONN · C3 induced-subgraph identification on 3-regular graphs | test accuracy: 100.0 ±0.0 -> 100.0 ±0.0 | No clear effect |
| add weak Tinhofer individualization (ablation) | GNN5 · COLLAB-b | test accuracy: 56.1 ±3.1 -> 79.5 ±2.6 | Helped |
| add weak Tinhofer individualization (ablation) | GNN2 · COLLAB-b | test accuracy: 75.3 ±1.1 -> 80.8 ±1.9 | Helped |
| add weak Tinhofer individualization (ablation) | GNN5 · NCI1, Mutagenicity, and IMDB-b | test accuracy: 83.8 ±0.5 -> 81.9 ±1.2; 83.0 ±2.6 -> 82.6 ±1.4; 71.8 ±5.0 -> 67.8 ±4.0 | Hurt |
| add weak Tinhofer individualization (ablation) | GNN2 · NCI1, Mutagenicity, and IMDB-b | test accuracy: 81.8 ±1.4 -> 81.8 ±2.3; 81.5 ±1.3 -> 81.2 ±1.7; 71.4 ±3.9 -> 69.4 ±3.4 | Mixed |
| replace ordinary GNN with EGONN without ego-net individualization | GNNK · C3, C4, C5, and K2,3 induced-subgraph identification on 3-regular graphs | test accuracy: 49.0 ±0.0 -> 100.0 ±0.0; 45.0 ±0.0 -> 73.6 ±10.2; 49.0 ±0.0 -> 89.4 ±1.5; 50.0 ±0.0 -> 74.2 ±2.2 | Helped |
Surprising findings
- Individualization schemes do not help on molecular datasets easily recognized by 1-WL, while they help on unlabeled datasets such as COLLAB-b.
- Randomized individualizations (RNI, RP) require many resampled copies to generalize, with a sizable train-test gap, while the canonical Tinhofer scheme learns CSL from a single copy.
Limitations
- Covering-number bounds assume GNNs are Lipschitz with respect to a graph pseudometric, a strong assumption.
- VC bounds for maximally expressive GNNs require K = n_max layers and yield bounds that are vacuous unless all individualized graphs are observed.
- Theory for randomized individualization schemes with resampling per epoch is left open.
Experimental setup
Datasets: CSL 3-regular graphs Cycles-pin CSL-pin MCF-7 Peptides-func NCI1 Mutagenicity IMDB-b COLLAB-b
Benchmarks: CSL 3-regular graphs Cycles-pin CSL-pin MCF-7 Peptides-func NCI1 Mutagenicity IMDB-b COLLAB-b
Metrics: train accuracy test accuracy train-test accuracy gap covering number ratio
Baselines: GNN without individualization RNI RP Tinhofer LPE GNN with Laplacian positional encoding
Builds on: Relational Pooling Random Node Initializations CLIP Tinhofer algorithm Lipschitz covering bound Pollard's bound
Closest papers by meaning
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
- Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization (NeurIPS 2025 · similarity 0.90)
- Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.89)
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.89)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.88)
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.