Research map / Graph learning / GNN architectures
Rethinking Independent Cross-Entropy Loss For Graph-Structured Data
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 joint-cluster supervised learning, which replaces independent per-node cross-entropy with a joint loss over each node and its METIS cluster's averaged label, improving GNN and MLP node classification and adversarial robustness.
Problem
Standard GNN node classification trains with independent per-node cross-entropy, ignoring label dependencies among connected nodes, which leads to over-confidence, poor generalization, and vulnerability to adversarial attacks.
Approach
Model the joint distribution of each training node's label and its METIS cluster's average label (conditioned on node and cluster representations) via a c×c joint-label classifier, train with a joint-cluster cross-entropy, and infer node labels by marginalizing over the cluster-label dimension.
Key results
- Joint-cluster loss improves GCN, SGC, SAGE, GAT accuracy on class-balanced small datasets by about 1.2-1.5% on average, and MLP by about 10.5%.
- Under metattack at 5-25% perturbation, JC improves over CE by 2.2% to 8.9% absolute on Cora for GCN.
- On heterophilic graphs, GCN with JC improves Chameleon accuracy from 59.25% to 68.87%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace independent CE with joint-cluster loss | GCN · Cora, CiteSeer, PubMed, DBLP, Facebook | accuracy: 81.70_{\pm0.65} -> 83.51_{\pm 0.35}; 71.43_{\pm0.47} -> 72.97_{\pm 0.55}; 79.06_{\pm0.32} -> 79.80_{\pm 0.19}; 74.30_{\p | Helped |
| Replace independent CE with joint-cluster loss | GCN · LastFMAsia | F1-micro: 84.91_{\pm 0.74} -> 85.92_{\pm 0.41} | Helped |
| Replace independent CE with joint-cluster loss | GCN · ogbn-arxiv | F1-micro: 71.74_{\pm 0.29} -> 72.17_{ \pm 0.24} | Helped |
| Replace independent CE with joint-cluster loss | GCN · Chameleon, Squirrel, Wisconsin | accuracy: 59.25_{\pm 2.81} -> 68.87_{\pm 2.55}; 48.93_{\pm 2.21} -> 56.76_{\pm 1.43}; 49.22_{\pm 3.77} -> 50.39_{\pm 4.53} | Helped |
| Replace independent CE with joint-cluster loss | GraphSAGE · Yelp and Amazon | micro-F1: 63.67_{\pm 0.38} -> 63.99_{\pm 0.46}; 75.65_{\pm 0.16} -> 76.14_{\pm 0.29} | Helped |
| Replace independent CE with joint-cluster loss | SIGN · Amazon | micro-F1: 80.22_{\pm 0.04} -> 80.09_{\pm 0.05} | Hurt |
| Replace independent CE with joint-cluster loss under metattack | GCN · Cora, 15% perturbation | accuracy: 64.21_{\pm 1.92} -> 72.24_{\pm 0.67} | Helped |
| Replace independent CE with joint-cluster loss | MLP · Cora | accuracy: 58.65_{ \pm 0.97} -> 67.19_{ \pm 0.62} | Helped |
| Use joint-cluster loss rather than in-context learning | GCN · Cora | accuracy: 81.56_{\pm0.25} -> 83.51_{\pm 0.35} | Helped |
| Add C&S post-processing to MLP trained with JC rather than CE | MLP · Cora and CiteSeer versus PubMed, DBLP, Facebook, LastFMAsia, Arxiv | accuracy: 80.05_{\pm0.46} vs 77.37_{\pm0.65}; 70.36_{\pm0.44} vs 69.01_{\pm0.93}; 77.08_{\pm0.26} vs 77.91_{\pm0.43}; 71.19_{\pm2. | Mixed |
| Add independent CE training on cluster-mixup samples | GCN · Cora | accuracy: 81.70_{\pm 0.65} -> 82.43_{\pm 0.44} | Helped |
| Use joint-cluster loss instead of independent CE cluster-mixup training | GCN · Cora | accuracy: 82.43_{\pm 0.44} -> 83.51_{\pm 0.35} | Helped |
Surprising findings
- The in-context learning variant (IC) often underperforms standard cross-entropy, e.g., GCN on CiteSeer drops from 71.43% to 70.08%.
- Stacking C&S with the joint-cluster loss degrades performance on small datasets such as Cora and CiteSeer.
Limitations
- Clustering is done with METIS for small graphs and random cluster assignment for large sampled batches, so the joint structure is only approximate for mini-batch methods.
- GAT incurs notably higher memory overhead (up to 1.70x) under the joint-cluster loss.
- Cluster label and representation are simple averages of training nodes, not learned; performance may suffer when batch sizes are too small to form good cluster statistics (e.g., SIGN on Amazon).
Experimental setup
Datasets: Cora CiteSeer PubMed DBLP Facebook LastFMAsia ogbn-arxiv Chameleon Squirrel Wisconsin Yelp Amazon
Benchmarks: Cora CiteSeer PubMed DBLP Facebook LastFMAsia ogbn-arxiv Chameleon Squirrel Wisconsin Yelp Amazon
Metrics: accuracy micro-F1 macro-F1 weighted-F1 training time inference time memory
Baselines: cross-entropy loss in-context learning CGNF CRF-GCN SPN C&S mixup
Builds on: GCN SGC GAT GraphSAGE METIS Cluster-GCN C&S
Closest papers by meaning
- Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning (NeurIPS 2021 · similarity 0.87)
- Unsupervised Adversarially Robust Representation Learning on Graphs (AAAI 2022 · similarity 0.87)
- Combining Label Propagation and Simple Models out-performs Graph Neural Networks (ICLR 2021 · similarity 0.87)
- Integrating Co-Training with Edge Discrimination to Enhance Graph Neural Networks Under Heterophily (AAAI 2025 · similarity 0.87)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.86)
- Improving Distinguishability of Class for Graph Neural Networks (AAAI 2024 · similarity 0.86)
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.