Graph Label Alignment: A Diagnostic Atlas for Graph Classification
Organizations: Department of Mathematical Sciences, University of Texas at Dallas, Richardson, TX 75080 · Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080 · Department of Computer Science, Virginia Tech, Blacksburg, VA 24061
Abstract
Graph classification benchmarks vary widely in difficulty: some are solved by simple pooled baselines, while others remain challenging for GNNs and graph transformers. We take a data-centric view and ask whether benchmark success is driven by genuine structure--feature reasoning or by label signal already accessible from restricted marginal views. We introduce graph label alignment, a lightweight diagnostic that measures label accessibility through two supervised probes computed without training a graph encoder: structural label alignment (SLA), based on permutation-invariant topological and spectral summaries, and feature label alignment (FLA), based on pooled node features with edges removed. Across real graph classification benchmarks and multiple pooled backbones, the resulting SLA--FLA plane strongly organizes test accuracy, with low-alignment datasets forming a consistent regime where standard pooled pipelines struggle. To probe what lies beyond marginal accessibility, we introduce controlled interaction-dominated stress tests, including heterophilic ego-graphs and synthetic Twins tasks whose structural and feature marginals are matched across classes but whose role--feature couplings differ. These results show that high alignment explains much of easy benchmark performance, while low alignment reveals regimes where success requires preserving structure--feature correspondence beyond standard pooled representations.
Figures & tables
| Alignment | GCN | SAGE | GAT | GPS |
|---|---|---|---|---|
| SLA | 0.935 ∗∗∗ | 0.802 ∗∗∗ | 0.941 ∗∗∗ | 0.835 ∗∗∗ |
| FLA | 0.928 ∗∗∗ | 0.715 ∗∗∗ | 0.961 ∗∗∗ | 0.759 ∗∗∗ |
| AlignAvg | 0.944 ∗∗∗ | 0.769 ∗∗∗ | 0.962 ∗∗∗ | 0.808 ∗∗∗ |
| Dataset | GCN | SAGE | GAT | GPS | SLA | FLA | AlignAvg |
|---|---|---|---|---|---|---|---|
| AIDS | 98.40 0.30 | 98.30 0.51 | 95.95 1.04 | 98.85 0.30 | 99.51 | 96.85 | 98.18 |
| MOLTOX21 | 73.45 0.41 | 73.63 0.53 | 71.95 0.40 | 73.70 1.01 | 84.35 | 88.71 | 86.53 |
| MUTAG | 71.28 5.48 | 69.74 4.10 | 67.18 5.48 | 70.77 7.36 | 86.69 | 69.65 | 78.17 |
| DD | 70.30 2.06 | 70.55 3.08 | 69.03 3.36 | 71.90 2.65 | 76.81 | 72.45 | 74.63 |
| BZR | 81.48 3.58 | 80.00 3.61 | 83.46 4.66 | 83.21 4.39 | 77.28 | 71.63 | 74.46 |
| PROTEINS_full | 71.07 3.16 | 71.70 3.73 | 73.84 1.64 | 74.11 2.06 | 73.56 | 73.99 | 73.78 |
| Binary | Triclass | |||||||||
| Linear | Radial | PageRank | Eigen | Lin & Rad | Lin & PR | Lin & Eigen | Rad & PR | Rad & Eigen | PR & Eigen | |
| FLA | 24.73 | 24.73 | 24.73 | 24.73 | 12.02 | 12.02 | 12.02 | 12.02 | 12.02 | 12.02 |
| SLA | 27.27 | 27.27 | 27.27 | 27.27 | 14.11 | 14.11 | 14.11 | 14.11 | 14.11 | 14.11 |
| GCN | 46.92 | 46.92 | 46.17 | 49.83 | 30.67 | 30.44 | 31.06 | 32.44 | 31.33 | 32.00 |
| SAGE | 49.50 | 48.50 | 48.67 | 49.50 | 33.11 | 32.39 | 31.56 | 32.00 | 33.00 | 33.11 |
| GAT | 47.92 | 45.58 | 44.00 | 46.83 | 31.78 | 28.56 | 31.00 | 31.06 | 31.39 | 31.33 |
Appendix figures & tables23 assets
Supplementary material from the paper’s appendix.
Appendix
| Group | Dataset | #Graphs | Av.Nodes | Av.Edges | # Feat. | #Classes |
|---|---|---|---|---|---|---|
| Molecular | AIDS | 2000 | 15.69 | 32.39 | 42 | 2 |
| BACE | 1513 | 34.09 | 73.72 | 9 | 2 | |
| BZR | 405 | 35.75 | 76.72 | 56 | 2 | |
| COX2 | 467 | 41.22 | 86.89 | 38 | 2 | |
| DD | 1178 | 284.32 | 1431.32 | 89 | 2 | |
| ENZYMES | 600 | 32.60 | 124.27 | 21 | 6 |
| Dataset | PH (20d) | Spectral (8d) | Stats (20d) | PH+Spec (28d) | PH+Stats (40d) | Spec+Stats (28d) | Full (48d) |
| AIDS | 99.39 | 99.62 | 99.50 | 99.59 | 99.44 | 99.55 | 99.53 |
| MUTAG | 86.70 | 87.61 | 86.50 | 86.38 | 86.39 | 86.13 | 86.49 |
| DD | 73.11 | 75.37 | 76.92 | 75.77 | 76.55 | 77.53 | 76.85 |
| BZR | 70.41 | 77.09 | 71.32 | 75.68 | 75.07 | 76.86 | 77.34 |
| PROTEINS_full | 69.41 | 73.67 | 73.32 | 72.63 | 72.72 | 73.83 | 73.53 |
| PROTEINS | 69.41 | 73.66 | 73.32 | 72.57 | 72.72 | 73.83 | 73.48 |
| Blocks | Dim | Avg SLA | SLA | AlignAvg | Pearson (GCN) | Regime agr. (%) |
|---|---|---|---|---|---|---|
| PH | 20 | 56.88 | 0.987 | 0.982 | 0.868 | 73.7 |
| Spectral | 8 | 59.01 | 0.981 | 0.996 | 0.898 | 78.9 |
| Stats | 20 | 59.99 | 0.968 | 0.982 | 0.840 | 78.9 |
| PH+Spectral | 28 | 60.19 | 0.984 | 0.996 | 0.887 | 89.5 |
| PH+Stats | 40 | 60.11 | 0.994 | 0.982 | 0.850 | 84.2 |
| Spectral+Stats | 28 | 61.69 | 0.993 | 0.996 | 0.882 | 78.9 |
| Blocks selected | Avg SLA | SLA vs. full | Pearson (GCN) | Regime agr. (%) | |
|---|---|---|---|---|---|
| 8 | 3 Lap, 2 Adj, 3 Stats | 59.97 | 0.972 | 0.870 | 68.4 |
| 12 | 4 Lap, 4 Adj, 4 Stats | 60.79 | 0.988 | 0.884 | 78.9 |
| 16 | 4 PH, 4 Lap, 4 Adj, 4 Stats | 60.99 | 0.988 | 0.880 | 78.9 |
| 24 | 8 PH, 4 Lap, 4 Adj, 8 Stats | 61.71 | 0.989 | 0.888 | 78.9 |
| Dataset | ||
|---|---|---|
| AIDS | ||
| MOLTOX21 | ||
| MUTAG | ||
| DD | ||
| BZR | ||
| PROTEINS_full |
| SLA | FLA | |||||
|---|---|---|---|---|---|---|
| Probe | Pearson (GCN) | Regime (%) | Pearson (GCN) | Regime (%) | ||
| LogReg | 1.000 | 0.880 | 100.0 | 1.000 | 0.931 | 100.0 |
| Linear SVM | 0.989 | 0.892 | 84.2 | 1.000 | 0.925 | 100.0 |
| RBF-SVM | 0.989 | 0.877 | 84.2 | 0.947 | 0.930 | 85.7 |
| MLP | 0.935 | 0.918 | 73.7 | 0.925 | 0.911 | 78.6 |
| CatBoost | 0.909 | 0.926 | 78.9 | 0.930 | 0.789 | 71.4 |
| Dataset | Centroid | Mean+Std | Mean+Std+Skew | Quantile (10/50/90) | Cov. eigs (top-4) |
|---|---|---|---|---|---|
| AIDS | 96.86 | 96.12 | 97.28 | 94.74 | 77.69 |
| MUTAG | 69.58 | 67.58 | 66.42 | 67.44 | 69.69 |
| DD | 72.51 | 77.14 | 76.58 | 69.50 | 65.46 |
| BZR | 71.79 | 75.10 | 77.00 | 75.58 | 64.53 |
| PROTEINS_full | 74.08 | 74.38 | 74.27 | 74.10 | 71.46 |
| PROTEINS | 64.02 | 71.81 | 71.67 | 70.36 | 67.88 |
| Summary | Dim | Avg FLA | FLA | AlignAvg | Pearson (GCN) | Regime agr. (%) |
|---|---|---|---|---|---|---|
| Centroid | 54.70 | 1.000 | 1.000 | 0.934 | 100.0 | |
| Mean+Std | 58.45 | 0.965 | 1.000 | 0.920 | 78.6 | |
| Mean+Std+Skew | 60.10 | 0.943 | 0.978 | 0.925 | 71.4 | |
| Quantile (10/50/90) | 56.91 | 0.934 | 0.982 | 0.936 | 78.6 | |
| Cov. eigs (top-4) | 50.30 | 0.947 | 0.978 | 0.842 | 85.7 |
| Construction | Changed | HH LL | GCN | SAGE | GAT | GPS |
|---|---|---|---|---|---|---|
| Reference (full SLA, centroid FLA) | 0/14 | 0 | 0.939 | 0.709 | 0.970 | 0.775 |
| FLA: Mean+Std | 2/14 | 0 | 0.935 | 0.715 | 0.973 | 0.799 |
| FLA: Mean+Std+Skew | 2/14 | 0 | 0.937 | 0.728 | 0.973 | 0.814 |
| FLA: Quantile (10/50/90) | 1/14 | 0 | 0.938 | 0.735 | 0.972 | 0.817 |
| FLA: Cov. eigs (top-4) | 0/14 | 0 | 0.898 | 0.663 | 0.955 | 0.767 |
| SLA: PH | 1/14 | 0 | 0.928 | 0.692 | 0.952 | 0.740 |
| View | Datasets | Pearson (GCN) | Spearman (GCN) | Mean std | Max std |
|---|---|---|---|---|---|
| SLA | 19 | 0.880 0.002 | 0.842 0.012 | 0.33 | 1.07 |
| FLA | 14 | 0.934 0.003 | 0.889 0.008 | 0.45 | 1.15 |
| Dataset | #Graphs | Av.Nodes | Av.Edges | # Feat. | #Classes | |
|---|---|---|---|---|---|---|
| Texas | 1 | 183 | 1704 | 5 | ||
| Texas | 2 | 183 | 1704 | 5 | ||
| Texas | 3 | 183 | 1704 | 5 | ||
| Cornell | 1 | 183 | 1704 | 5 | ||
| Cornell | 2 | 183 | 1704 | 5 | ||
| Cornell | 3 | 183 | 1704 | 5 |
| Dataset | GCN | SAGE | GAT | GPS | SLA | FLA | AlignAvg | |
|---|---|---|---|---|---|---|---|---|
| Texas | 1 | 31.05 10.84 | 42.11 6.86 | 35.79 15.49 | 42.11 6.86 | 33.78 | 43.16 | 38.47 |
| Texas | 2 | 35.26 4.88 | 36.32 6.32 | 25.79 13.87 | 36.32 6.09 | 51.81 | 61.96 | 56.89 |
| Texas | 3 | 30.00 4.59 | 35.79 7.37 | 22.63 12.74 | 37.89 4.88 | 62.67 | 61.84 | 62.26 |
| Cornell | 1 | 36.32 3.87 | 35.26 12.85 | 35.26 6.36 | 60.00 7.88 | 17.76 | 31.34 | 24.55 |
| Cornell | 2 | 27.89 4.88 | 25.79 1.97 | 22.11 3.57 | 58.95 2.68 | 29.13 | 32.29 | 30.71 |
| Cornell | 3 | 27.37 6.78 | 33.68 9.47 | 20.53 3.07 | 58.95 1.29 | 28.89 | 32.18 | 30.54 |
| Dataset | GCN | SAGE | GAT | GPS | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| AIDS | 98.05 | 98.40 | 0.35 | 97.91 | 98.30 | 0.39 | 97.46 | 95.95 | 1.51 | 97.09 | 98.85 | 1.76 |
| MOLTOX21 | 86.75 | 73.45 | 13.30 | 86.97 | 73.63 | 13.34 | 87.71 | 71.95 | 15.76 | 88.32 | 73.70 | 14.62 |
| MUTAG | 77.32 | 71.28 | 6.04 | 76.47 | 69.74 | 6.73 | 73.57 | 67.18 | 6.39 | 71.18 | 70.77 | 0.41 |
| DD | 74.41 | 70.30 | 4.11 | 74.19 | 70.55 | 3.64 | 73.45 | 69.03 | 4.42 | 72.84 | 71.90 | 0.94 |
| BZR | 74.17 | 81.48 | 7.31 | 73.89 | 80.00 | 6.11 | 72.93 | 83.46 | 10.53 | 72.14 | 83.21 | 11.07 |
| PROTEINS_full | 73.80 | 71.07 | 2.73 | 73.82 | 71.70 | 2.12 | 73.89 | 73.84 | 0.05 | 73.95 | 74.11 | 0.16 |
| SLA | FLA | Recommended backbone | Rationale |
|---|---|---|---|
| High | High | GCN/SAGE (cheapest) | Alignment is easy; capacity adds little, prefer efficiency. |
| High | Low/Med | GCN (or SAGE) | Structure-dominant; simpler MPNNs suffice and generalize well. |
| Med | Med | SAGE/GAT | Balanced regime; moderate capacity often best. |
| Low/Med | High | GPS (or GAT) | Feature-dominant; attention/global aggregation helps. |
| Low | Low | GPS/GAT (expect low) | Neither cue aligns; need capacity but accuracy remains limited. |
| Dataset | GCN | SAGE | GAT | GPS | SLA | FLA | AlignAvg |
|---|---|---|---|---|---|---|---|
| Synth-001 | 33.83 3.21 | 34.67 0.29 | 32.17 4.07 | 34.67 3.06 | 32.17 | 34.68 | 33.42 |
| Synth-002 | 30.33 3.21 | 32.83 3.75 | 32.17 5.39 | 29.50 2.29 | 34.37 | 32.17 | 33.27 |
| Synth-003 | 42.00 2.29 | 39.00 3.28 | 41.67 2.75 | 37.00 3.04 | 36.18 | 39.75 | 37.97 |
| Synth-004 | 37.33 4.48 | 35.00 2.00 | 36.67 2.52 | 38.83 4.54 | 32.83 | 37.50 | 35.17 |
| Synth-005 | 45.00 0.87 | 45.33 3.33 | 43.17 2.57 | 43.00 6.14 | 32.90 | 41.48 | 37.19 |
| Synth-006 | 42.00 5.89 | 42.50 3.00 | 41.00 4.27 | 43.83 1.89 | 34.17 | 44.30 | 39.23 |
| Dataset | Graphs | SLA build | SLA CV | FLA build | FLA CV | GLA | GCN | SAGE | GAT | GPS | Sum | Ratio |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MUTAG | 188 | 0.30 | 0.05 | 0.01 | 0.03 | 0.39 | 1.32 | 1.02 | 2.92 | 4.15 | 9.4 | 23.9 |
| BZR | 405 | 1.32 | 0.12 | 0.02 | 0.10 | 1.55 | 3.18 | 2.69 | 10.72 | 14.49 | 31.1 | 20.1 |
| PROTEINS | 1,113 | 4.40 | 0.55 | 0.02 | 0.13 | 5.11 | 10.13 | 7.72 | 36.46 | 82.27 | 136.6 | 26.7 |
| NCI1 | 4,110 | 12.13 | 3.27 | 0.09 | 3.73 | 19.23 | 32.18 | 28.62 | 137.29 | 152.75 | 350.8 | 18.2 |
| Dataset | Obs. | Pred. | Gap | Dataset | Obs. | Pred. | Gap |
|---|---|---|---|---|---|---|---|
| Synthie | 69.0 | 53.0 | +16.0 | DD | 70.3 | 75.2 | -4.9 |
| COX2 | 78.1 | 65.0 | +13.1 | PROTEINS | 67.6 | 71.0 | -3.4 |
| MOLTOX21 | 73.5 | 86.0 | -12.6 | PROTEINS_full | 71.1 | 74.3 | -3.3 |
| COLORS-3 | 24.9 | 35.8 | -10.9 | BACE | 72.8 | 70.4 | +2.3 |
| CIFAR-10 | 27.8 | 36.8 | -9.0 | Letter-High | 41.4 | 43.4 | -2.0 |
| MUTAG | 71.3 | 79.7 | -8.4 | ENZYMES | 47.5 | 46.0 | +1.6 |
| MUTAG | -15.4 | BACE | +5.8 | COX2 | +11.4 |
|---|---|---|---|---|---|
| MOLTOX21 | -15.0 | BZR | +6.2 | ENZYMES | +14.1 |
| FRANKENSTEIN | -5.9 | CIFAR-10 | +17.6 | ||
| DD | -4.9 | MNIST | +23.0 | ||
| PROTEINS | -4.6 | Synthie | +29.7 | ||
| MOLHIV | -2.2 | COIL-DEL | +37.8 | ||
| SLA | FLA | GCN | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| BA | AUC | BA | AUC | BA | AUC | |||||||
| Dataset | S | R | S | R | S | R | S | R | S | R | S | R |
| BACE | 0.66 | 0.72 | 0.75 | 0.79 | 0.62 | 0.65 | 0.73 | 0.73 | 0.54 | 0.70 | 0.78 | 0.81 |
| MOLTOX21 | 0.64 | 0.73 | 0.74 | 0.79 | 0.70 | 0.73 | 0.80 | 0.80 | 0.68 | 0.58 | 0.76 | 0.72 |
| MOLHIV | 0.65 | 0.65 | 0.70 | 0.71 | 0.63 | 0.63 | 0.64 | 0.67 | 0.50 | 0.50 | 0.62 | 0.69 |
| BBBP | 0.56 | 0.72 | 0.60 | 0.80 | 0.58 | 0.76 | 0.64 | 0.83 | 0.52 | 0.76 | 0.65 | 0.93 |
Graph Classification
Graph classification assigns labels to whole graphs, using their connectivity, node and edge attributes, and learned representations.
See all 46 papers