1. Decision Framework
Ask these questions in order:
- Is there relational structure? If rows are independent (customer churn with no links), use XGBoost/MLP first.
- Do labels depend on neighbors? If yes (homophily or structured heterophily), GNN is a strong candidate.
- Do you have node features? Structure-only → random walk embeddings or label propagation may suffice.
- Graph size? Small → full-batch GCN. Large → GraphSAGE + neighbor sampling.
- Dynamic? Static → standard GNN. Streaming edges → TGN.
- Multiple types? Heterogeneous → R-GCN/HGT.
- Text on nodes? Consider LLM embeddings + GNN, or GraphRAG - see GNNs & LLMs.
2. When NOT to Use GNNs
- i.i.d. tabular data with no meaningful edges (invented k-NN graphs often hurt)
- Tiny graphs (< 50 nodes) - not enough data to learn message passing
- Noisy/random graphs - structure is meaningless
- Strict latency + huge graphs - 2-hop sampling on 100M nodes is hard; consider embeddings + MLP
- When a simpler baseline wins - if label propagation matches your GNN, ship the simpler model
Rule of thumb: Always run an MLP on node features and label propagation on edges. Your GNN must beat both to justify complexity.
3. GNN vs MLP vs LLM
| Approach | Wins when | Loses when |
|---|---|---|
| MLP / XGBoost | Features carry most signal, no neighbor effect | Structure is key (citations, molecules) |
| GNN | Local structure predicts labels, inductive generalization on graphs | Long text reasoning, no graph |
| LLM alone | Text-heavy, few-shot reasoning, no reliable graph | Large structured graphs, combinatorial structure |
| LLM + GNN | Text-attributed graphs, KG + language queries | Simple homophilous node cls with bag-of-words features |
4. Metrics
| Task | Metrics |
|---|---|
| Node classification | Accuracy, F1 (macro for imbalanced), AUC-ROC |
| Link prediction | AUC-ROC, AP, MRR, Hits@10, Hits@50 |
| Graph classification | Accuracy, F1, AUC |
| Graph regression | MAE, RMSE, $R^2$ |
Hits@K: fraction of true edges where the correct target ranks in top $K$ predictions.
5. Baselines You Must Beat
- MLP: node features only, no graph
- Label propagation: spread labels along edges (semi-supervised classic)
- Node2Vec / DeepWalk: random walk embeddings + logistic regression
- Logistic regression on hand features (degree, clustering coeff)
6. OGB and Fair Comparison
Open Graph Benchmark provides fixed splits, evaluators, and leaderboards. Use their splits - do not invent your own when comparing to published numbers.
Report: mean ± std over multiple seeds (at least 3, preferably 10).
7. Ablation Studies
Test what actually matters:
- Remove edge features - how much do they help?
- Replace GNN with MLP - does structure help?
- 1 vs 2 vs 3 layers
- With vs without positional encodings
- Different aggregators (mean vs sum vs attention)