Research map / Graph learning / GNN architectures
Unifews: You Need Fewer Operations for Efficient 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.
Proposes Unifews, an entry-wise joint sparsification of graph edges and weight matrices for GNNs with a spectral-smoothing approximation bound, reporting large FLOP reductions and up to ~100x speedup on graphs up to billion edges.
Problem
GNN training and inference are expensive due to graph-scale propagation and weight transformation; prior graph or weight sparsification is static, layer-agnostic, or lacks theoretical treatment of multi-layer effects.
Approach
Treat graph propagation and feature transformation as entry-wise matrix operations and prune individual messages (edges) and weights by magnitude thresholds on the fly, with progressively increasing sparsity across layers, and bound the error via spectral similarity to graph Laplacian smoothing.
Key results
- On papers100M, Unifews gives about 85-100x propagation time improvement over the backbone and about 9x over NIGCN.
- Unifews reaches over 90% joint sparsity with comparable or better accuracy; e.g., SGC accuracy on citeseer rises by about 2% (from 67.7 to 69.4 on arxiv for SGC is reported as +5.3).
- Operation reduction of 10-20x (over 20x joint reduction on arxiv for decoupled models with L=20).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply 50% graph sparsification with Unifews | SGC · cora | accuracy: 85.8 -> 86.0 | Helped |
| apply 50% graph sparsification with Unifews | SGC · citeseer | accuracy: 67.7 -> 73.0 | Helped |
| apply 50% graph sparsification with Unifews | SGC · pubmed | accuracy: 83.0 -> 83.0 | No clear effect |
| apply 50% graph sparsification with Unifews | SGC · arxiv | accuracy: 68.8 -> 69.4 | Helped |
| apply 50% graph sparsification with Unifews | SGC · products | accuracy: 79.1 -> 78.5 | Hurt |
| apply 50% graph sparsification with Unifews | SGC · papers100m | accuracy: 63.3 -> 63.1 | Hurt |
| apply 50% graph sparsification with Unifews | APPNP · cora | accuracy: 86.2 -> 86.5 | Helped |
| apply 50% graph sparsification with Unifews | APPNP · citeseer | accuracy: 71.6 -> 73.7 | Helped |
| apply 50% graph sparsification with Unifews | APPNP · pubmed | accuracy: 87.6 -> 88.0 | Helped |
| apply 50% graph sparsification with Unifews | APPNP · arxiv | accuracy: 64.8 -> 65.0 | Helped |
| apply 50% graph sparsification with Unifews | APPNP · products | accuracy: 72.5 -> 76.9 | Helped |
| apply 50% graph sparsification with Unifews | APPNP · papers100m | accuracy: 60.9 -> 62.8 | Helped |
Surprising findings
- Pruning can improve accuracy over the dense backbone at moderate sparsity, attributed to mitigating over-smoothing.
- Random entry-wise removal is competitive with dedicated methods at small sparsity ratios.
Limitations
- Assumes graph homophily; messages with large magnitudes may be harmful under heterophily.
- Theoretical bound relies on assumptions (scale-free degree distribution, Gaussian embeddings).
Experimental setup
Datasets: cora citeseer pubmed physics arxiv products papers100m
Benchmarks: cora citeseer pubmed arxiv products papers100m
Metrics: accuracy propagation time FLOPs edge sparsity weight sparsity
Baselines: GLT GEBT CGP DSpar NDLS NIGCN RAN
Builds on: GCN SGC APPNP graph lottery ticket spectral sparsification
Closest papers by meaning
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.87)
- Graph Sparsification via Mixture of Graphs (ICLR 2025 · similarity 0.87)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.87)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.87)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 2024 · similarity 0.87)
- Rethinking Propagation for Unsupervised Graph Domain Adaptation (AAAI 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.