Research map / Graph learning / Graph algorithms and clustering
TREE-G: Decision Trees Contesting 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.
Introduces TREE-G, a decision tree whose split function propagates vertex features over graph walks restricted to dynamically generated vertex subsets (chosen via pointers to ancestor splits), and uses it as a weak learner in gradient boosted trees for graph and vertex prediction.
Problem
Decision trees are strong on tabular data but do not natively handle graph-structured data, where split decisions must combine vertex features with topology and be invariant/equivariant to vertex ordering.
Approach
A split function that propagates a vertex feature through walks of length d (A^d f_k), masked to a subset of vertices; subsets are generated at each split node by partitioning an ancestor's subset, and a pointer to an ancestor selects which subset a node uses, so the splits adapt to each graph without enumerating subsets.
Key results
- TREE-G outperforms all tree-based baselines (XGraphBoost, BGNN, ablation a=0) on all 17 tasks and beats graph kernels on 9 of 10 graph classification tasks.
- On IMDb-M, TREE-G exceeds the best GNN by more than 6.4 percentage points (56.4 vs about 50.0 for GCN).
- TREE-G reaches 91.1% on Mutag and 83.0% on Mutagenicity, the best scores among reported methods on these datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the subset mechanism to TREE-G (ablation) | TREE-G · All 17 graph and node prediction tasks | accuracy or AUC (Country: RMSE) | Helped |
| Add graph topology and subset-based propagation (instead of d=0, a=0) (ablation) | TREE-G · Graph and node prediction benchmarks | accuracy or AUC | Mixed |
| Use TREE-G rather than the strongest listed baseline | Graph classification · Mutag | accuracy: 91.1 $\pm$ 3.5 vs 86.1 $\pm$ 3.8 | Helped |
| Use TREE-G rather than the strongest listed baseline | Graph classification · NCI1 | accuracy: 75.9 $\pm$ 1.5 vs 82.5 $\pm$ 3.1 | Hurt |
| Use TREE-G rather than the strongest listed baseline | Graph classification · IMDb-M | accuracy: 56.4 $\pm$ 0.9 vs 50.9 $\pm$ 3.8 | Helped |
| Use TREE-G rather than the strongest listed baseline | Node classification · Actor | accuracy: 37.0 $\pm$ 0.4 vs 34.2 $\pm$ 1.9 | Helped |
Surprising findings
- A standard-tree ablation (d=0, a=0) with no graph topology already matches or beats several GNNs on some tasks such as Mutag (86.1) and Cornell-like heterophilic tasks.
- On molHIV the ablation without topology (70.1 AUC) is far below GNNs, while the full TREE-G reaches 83.5, showing the topology propagation matters strongly there.
Limitations
- Greedy tree training with grid search over d, k, pointers and thresholds adds running-time overhead relative to standard trees.
- Edge features are ignored in the main method (handled only via extensions/line graphs in the appendix).
Experimental setup
Datasets: Proteins Mutag D&D NCI1 PTC Enzymes Mutagenicity IMDb-B IMDb-M molHIV Cora Citeseer
Benchmarks: Proteins Mutag D&D NCI1 PTC Enzymes Mutagenicity IMDb-B IMDb-M molHIV Cora Citeseer
Metrics: accuracy ROC-AUC RMSE
Baselines: XGraphBoost BGNN GCN GIN GAT GATv2 GraphSAGE WL kernel random walk kernel
Builds on: Set-Trees gradient boosted trees XGBoost BGNN Weisfeiler-Lehman graph kernel
Closest papers by meaning
- Neural Trees for Learning on Graphs (NeurIPS 2021 · similarity 0.91)
- GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries (ICLR 2024 · similarity 0.90)
- GOAt: Explaining Graph Neural Networks via Graph Output Attribution (ICLR 2024 · similarity 0.87)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.87)
- From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks (ICLR 2025 · similarity 0.86)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 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.