Research map / Graph learning / GNN architectures
TEDDY: Trimming Edges with Degree-based Discrimination Strategy
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 TEDDY, a one-shot edge sparsification method that scores edges by multi-hop degree statistics, combined with distillation and single-training l0-ball projected gradient descent for parameter sparsity, to find graph lottery tickets.
Problem
Finding graph lottery tickets (sparse subgraph plus sparse GNN) usually requires iterative pruning, which is slow, and existing methods largely ignore graph structure such as edge degree.
Approach
Score edges by a multi-level (2-hop-aware) degree statistic computed via edge-centric message passing with g(v)=1/sqrt(deg(v)), prune in one shot, and sparsify weights with PGD onto an l0 ball in a single training run with logit distillation from the dense model.
Key results
- On GAT at maximum graph sparsity, TEDDY improves performance by 12.8% to 20.4% over the best baseline.
- GIN on Citeseer reaches 73.20% accuracy at graph sparsity 43.12%, a 5.4% gain over vanilla.
- On Reddit with SAGE, TEDDY reaches 82.72% at graph sparsity 40%, 7.4% above vanilla SAGE and 12.4% above UGS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multi-level degree information in edge-centric message passing instead of only direct node-pair degrees (ablation) | TEDDY · Cora, GAT | accuracy | Helped |
| Add distillation loss to the sparse-graph training objective (ablation) | TEDDY · Cora, GAT | accuracy | Helped |
| Add distillation loss to UGS (ablation) | UGS · Cora, Citeseer, Pubmed | accuracy | Helped |
| Replace magnitude-based weight-mask pruning with projected gradient descent on the ℓ0 ball (ablation) | TEDDY · Cora, Citeseer, Pubmed | accuracy | Mixed |
| Use ℓ0-based projected gradient descent for parameter pruning (ablation) | UGS · Cora, Citeseer, Pubmed | accuracy | Hurt |
| Prune low-degree rather than high-degree edges (ablation) | GCN, GAT, and GIN · Cora, Citeseer, Pubmed | accuracy | Hurt |
| Use multi-level degree-based edge scoring rather than 1-hop degree scoring (ablation) | TEDDY · Cora, GAT | accuracy | Helped |
| Increase graph and weight sparsity using TEDDY | GIN · Pubmed | accuracy: 77.90 ± 0.14 -> 80.98 ± 0.42 | Helped |
| Use TEDDY instead of Vanilla GIN at the 20-th simulation | GIN · Cora | accuracy: 76.34 ± 0.79 -> 76.20 ± 0.69 | No clear effect |
| Use TEDDY instead of Vanilla GIN at the 25-th simulation | GIN · Citeseer | accuracy: 68.10 ± 0.77 -> 70.58 ± 1.43 | Helped |
| Use TEDDY instead of Vanilla GIN at the 40-th simulation | GIN · Pubmed | accuracy: 77.90 ± 0.14 -> 80.98 ± 0.42 | Helped |
Surprising findings
- One-shot edge pruning using only graph structure (no node features) outperforms iterative baselines that use features.
- Pruning low-degree edges degrades performance more than pruning high-degree edges, contrary to the common intuition of removing hubs.
Limitations
- Node features are not used in edge sparsification, which the authors identify as future work.
- Theoretical properties of the method are not analyzed.
- Baselines WD-GLT and UGS are infeasible on some graph transformers due to O(N^3) eigen-decomposition backprop, so comparisons are partial.
Experimental setup
Datasets: Cora Citeseer Pubmed ogbn-arxiv Reddit
Benchmarks: Cora Citeseer Pubmed ogbn-arxiv Reddit
Metrics: classification accuracy MACs wall-clock pruning time
Baselines: UGS WD-GLT DropEdge Vanilla GNN
Builds on: graph lottery ticket hypothesis (UGS) lottery ticket hypothesis GCN GAT GIN
Closest papers by meaning
- A Unified Lottery Ticket Hypothesis for Graph Neural Networks (ICML 2021 · similarity 0.92)
- Searching Lottery Tickets in Graph Neural Networks: A Dual Perspective (ICLR 2023 · similarity 0.92)
- Fast Track to Winning Tickets: Repowering One-Shot Pruning for Graph Neural Networks (AAAI 2025 · similarity 0.92)
- Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win (ICML 2025 · similarity 0.87)
- Find A Winning Sign: Sign Is All We Need to Win the Lottery (ICLR 2025 · similarity 0.87)
- Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness (ICML 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.