Research map / Graph learning / Graph self-supervised learning
Automated Loss function Search for Class-imbalanced Node Classification
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 AutoLINC, an MCTS-based automated loss function search over a grammar of primitive operators (with class counts as input) plus check strategies, to discover loss functions for class-imbalanced node classification that outperform hand-designed losses on GCN/GAT/SAGE.
Problem
Class-imbalanced semi-supervised node classification, where GNNs are biased toward majority classes and hand-designed loss functions depend on expert knowledge and transfer poorly across tasks.
Approach
Searches expression-tree loss functions generated by a context-free grammar with MCTS (UCT selection, random simulation), using class node counts as an input, and speeds up search with a basic check (formula/gradient equivalence reuse) and an early rejection strategy (monotonicity and poor-performance rejection) on a proxy task.
Key results
- On Cora with GCN at imbalance ratio 10, AutoLINC reaches 70.21 bAcc versus 69.17 for BalancedSoftmax+TAM, the strongest baseline.
- On GAT with CiteSeer (ratio 10), AutoLINC reaches 58.48 bAcc versus 54.14 for BalancedSoftmax+TAM.
- Basic Check accelerates search about 5.7x and Early Rejection about 7.8x in valid loss functions explored within 12 hours.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | GCN · Cora, CiteSeer, PubMed, and Amazon-photo (ρ=10) | bAcc: 69.17$\pm$0.77 -> 70.21$\pm$0.67; 55.65$\pm$1.19 -> 56.56$\pm$1.97; 72.15$\pm$1.08 -> 72.43$\pm$1.03; 82.50$\pm$0.79 -> | Helped |
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | GCN · Amazon-computers (ρ=10) | bAcc: 85.10$\pm$0.06 -> 83.23$\pm$0.23 | Hurt |
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | GAT · Cora, CiteSeer, and Amazon-computers (ρ=10) | bAcc: 67.27$\pm$0.67 -> 70.63$\pm$1.01; 54.14$\pm$1.31 -> 58.48$\pm$1.57; 75.66$\pm$0.62 -> 78.86$\pm$0.59 | Helped |
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | GAT · PubMed and Amazon-photo (ρ=10) | bAcc: 72.49$\pm$0.62 -> 72.57$\pm$0.88; 66.49$\pm$1.39 -> 74.41$\pm$0.69 | Helped |
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | SAGE · Cora, CiteSeer, Amazon-computers, and Amazon-photo (ρ=10) | bAcc: 66.54$\pm$0.49 -> 68.51$\pm$1.02; 52.46$\pm$1.23 -> 56.78$\pm$1.27; 78.11$\pm$0.77 -> 80.02$\pm$0.68; 69.45$\pm$2.01 -> | Helped |
| Use AutoLINC-discovered loss functions instead of the strongest listed loss-function baseline | SAGE · PubMed (ρ=10) | bAcc: 71.38$\pm$0.77 -> 70.97$\pm$1.04 | Hurt |
| Add Basic Check Strategy (ablation) | AutoLINC search on Cora-GCN · 12-hour search | valid loss functions explored: $8.3\times10^4$ -> $4.8\times10^5$ | Helped |
| Add Early Rejection Strategy to Basic Check Strategy (ablation) | AutoLINC search on Cora-GCN · 12-hour search | valid loss functions explored: $4.8\times10^5$ -> $6.5\times10^5$ | Helped |
| Transfer loss functions found at ρ=10 to ρ=5 | AutoLINC · same-type graph datasets | classification performance | Mixed |
| Transfer loss functions across graph types | AutoLINC · citation networks to Amazon co-purchase networks | classification performance | Hurt |
Surprising findings
- Discovered loss functions transfer well between datasets of the same type (citation or Amazon) but degrade across types, which the authors attribute to homophily.
- AutoLINC gains are moderate on PubMed, attributed to its high topology imbalance.
Limitations
- Transferability diminishes across heterogeneous graph types (citation vs Amazon).
- Possible overfitting to the validation set when validation is small, with mixed evidence.
- Search is time-intensive; AutoLINC has the highest runtime among compared methods.
Experimental setup
Datasets: Cora CiteSeer PubMed Amazon-computers Amazon-photo
Benchmarks: Cora CiteSeer PubMed Amazon-computers Amazon-photo
Metrics: bAcc F1
Baselines: Cross-entropy Re-Weight Balanced Softmax PC Softmax ReNode TAM GraphSMOTE GraphENS GraphSHA Autoloss-Zero
Builds on: Autoloss-Zero TAM ReNode Balanced Softmax
Closest papers by meaning
- Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition (NeurIPS 2023 · similarity 0.89)
- Class-Imbalanced Graph Learning without Class Rebalancing (ICML 2024 · similarity 0.87)
- Rethinking Independent Cross-Entropy Loss For Graph-Structured Data (ICML 2024 · similarity 0.86)
- Improving Distinguishability of Class for Graph Neural Networks (AAAI 2024 · similarity 0.85)
- Cluster-guided Contrastive Class-imbalanced Graph Classification (AAAI 2025 · similarity 0.85)
- IGL-Bench: Establishing the Comprehensive Benchmark for Imbalanced Graph Learning (ICLR 2025 · similarity 0.85)
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.