Research map / Graph learning / GNN architectures
Learning on Large Graphs using Intersecting Communities
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.
Approximates large non-sparse graphs by intersecting community graphs (ICGs) fitted via Frobenius-norm gradient descent, enabling O(N) learning (ICG-NN) with one-off O(E) preprocessing.
Problem
Message-passing GNNs require memory and time linear in the number of edges, which becomes prohibitive for large non-sparse graphs.
Approach
Approximate the graph by a low-rank intersecting community graph (linear combination of soft community indicators) with a constructive weak regularity lemma showing Frobenius-norm minimization guarantees small cut-metric error; then run neural networks on nodes and community features so complexity is linear in nodes.
Key results
- On METR-LA and PEMS-BAY, ICG_u-NN reaches MAE 3.12 and 1.56, competitive with GraphWaveNet (3.05, 1.56) and better than DCRNN and AGCRN.
- ICG_u-NN forward-pass runtime scales with a square-root relationship relative to GCN runtime on dense Erdos-Renyi graphs up to 7k nodes.
- On tolokers, performance degrades by only 2.8% when a small number of nodes is removed during subgraph SGD, and stops degrading beyond 10% removal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use unconstrained trainable community features instead of community features produced by a neural network (ablation) | ICG-NN · METR-LA | MAE: 3.42 -> 3.12 | Helped |
| Use unconstrained trainable community features instead of community features produced by a neural network (ablation) | ICG-NN · PEMS-BAY | MAE: 1.76 -> 1.56 | Helped |
| Use ICG_u-NN instead of GraphWaveNet | Traffic forecasting · METR-LA | MAE: 3.05 -> 3.12 | Hurt |
| Use ICG_u-NN instead of GraphWaveNet | Traffic forecasting · PEMS-BAY | MAE: 1.56 -> 1.56 | No clear effect |
| Use ICG-NN instead of GraphWaveNet | Traffic forecasting · METR-LA | MAE: 3.05 -> 3.42 | Hurt |
| Use ICG-NN instead of GraphWaveNet | Traffic forecasting · PEMS-BAY | MAE: 1.56 -> 1.76 | Hurt |
| Remove a small number of graph nodes during subgraph sampling (ablation) | ICG_u-NN · tolokers | ROC AUC: 2.8% | Hurt |
| Remove more than 10% of graph nodes during subgraph sampling (ablation) | ICG_u-NN · tolokers | ROC AUC | No clear effect |
Surprising findings
- Performance remains stable on tolokers when more than 10% of nodes are removed under subgraph SGD.
Limitations
- ICG-NN is fitted to a specific ICG and does not transfer across different ICGs of different graphs.
- ICG construction is limited to undirected graphs.
- The constructive lemma is only semi-constructive since gradient descent does not guarantee a global Frobenius minimizer.
Experimental setup
Datasets: tolokers Flickr Reddit METR-LA PEMS-BAY
Benchmarks: tolokers Flickr Reddit METR-LA PEMS-BAY
Metrics: ROC AUC MAE forward pass runtime
Baselines: GCN MLP DCRNN GraphWaveNet AGCRN T&S-IMP TTS-IMP T&S-AMP TTS-AMP
Builds on: Weak Regularity Lemma Message passing neural networks GCN BigCLAM
Closest papers by meaning
- Efficient Learning on Large Graphs using a Densifying Regularity Lemma (ICLR 2026 · similarity 0.93)
- NLGT: Neighborhood-based and Label-enhanced Graph Transformer Framework for Node Classification (AAAI 2025 · similarity 0.87)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.87)
- Cooperative Graph Neural Networks (ICML 2024 · similarity 0.87)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.87)
- Towards Dynamic Message Passing on Graphs (NeurIPS 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.