Graph Label Alignment: A Diagnostic Atlas for Graph Classification
Authors: Neelam Akula, Varun Shiralkar, Murat Kantarcioglu, Baris Coskunuzer
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
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
Figure 1: Real benchmarks in the alignment plane (GCN). Each point is a real graph classification dataset positioned by its SLA and FLA scores, colored by GCN accuracy. Other backbones are shown in Appendix Figure 3 .
Figure 2: Synthetic alignment sweep (GCN& GPS). Each point is a synthetic dataset positioned by its SLA and FLA, colored by GCN(left) and GPS (right) accuracy. The dashed line marks an illustrative 80% accuracy contour. Other backbones are shown in Appendix Figure 5 .
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 ∗∗∗
Table 1: Pearson correlations between alignment scores and model accuracy on 19 real benchmarks (datasets where FLA and AlignAvg ((SLA+FLA)/2) are defined; see Table 2 ). Statistical significance: ∗p<0.05 , ∗∗p<0.01 , ∗∗∗p<0.001 .
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
Table 2: Real Graph Benchmarks. Pooled-model accuracy (%) tracked against the alignment plane: structural and feature alignment scores (SLA/FLA, %). AlignAvg summarizes alignment as (SLA+FLA)/2 . Datasets are ordered by decreasing AlignAvg when FLA is defined, and by decreasing SLA for featureless datasets (FLA/AlignAvg shown as –).
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
Table 3: Twin setting Accuracy results (%) for binary (random assignment vs. one structured assignment) and triclass tasks (random assignment plus two structured assignments).
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
Appendix
Table 4: Dataset statistics across molecular, computer vision, synthetic, and social graph benchmarks.
Figure 3: GNN on graph classification benchmarks. Each point is a real benchmark dataset in the SLA-FLA plane, colored by GNN classification accuracy. Beginning in the top left: GCN, GraphSAGE, GAT, and GPS.
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
Appendix
Table 5: Structural ablation: SLA (%) for each block alone, each pair, and the full 48-dimensional summary vector, on 14 TU benchmarks with node attributes and 5 featureless social benchmarks. Bold is the best score per row.
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
Appendix
Table 6: Structural ablation summary. Rank correlations are Spearman against the full descriptor, for SLA (19 datasets) and for AlignAvg (the 14 datasets where FLA is defined, with centroid FLA held fixed). Pearson is against GCN accuracy on the 19 datasets. Regime agreement uses per-axis tertiles of the full-descriptor SLA.
k
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
Appendix
Table 7: Minimal structural descriptor: top- k dimensions by mutual information, averaged across datasets. Lap and Adj are the Laplacian and adjacency spectral blocks. Dimensions are selected and evaluated on the same 19 datasets, so these figures are in-sample.
Dataset
δSLA
δFLA
AIDS
+0.06
−1.24
MOLTOX21
−3.13
−2.92
MUTAG
−1.71
+0.78
DD
−0.13
−3.97
BZR
−7.16
−11.07
PROTEINS_full
−2.18
−0.25
Appendix
Table 8: Probe sufficiency self-check: difference between alternative-probe and reference alignment scores. We report δSLA=SLAalt−SLAref and analogously for FLA. Most datasets show small, unsystematic differences. Letter-High is the clearest probe-sensitive case.
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
Appendix
Table 9: Individual probes on the same summaries. ρ and regime agreement are measured against LogReg alone, not against the two-probe reference average. SLA uses 19 datasets and FLA uses 14.
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
Appendix
Table 10: FLA (%) under five feature summaries on the 14 TU benchmarks with node attributes. Bold is the best score per row.
Summary
Dim
Avg FLA
FLA ρ
AlignAvg ρ
Pearson (GCN)
Regime agr. (%)
Centroid
d
54.70
1.000
1.000
0.934
100.0
Mean+Std
2d
58.45
0.965
1.000
0.920
78.6
Mean+Std+Skew
3d
60.10
0.943
0.978
0.925
71.4
Quantile (10/50/90)
3d
56.91
0.934
0.982
0.936
78.6
Cov. eigs (top-4)
4
50.30
0.947
0.978
0.842
85.7
Appendix
Table 11: Feature-summary robustness on 14 datasets. Rank correlations are Spearman against centroid FLA, for FLA and for AlignAvg (with full SLA held fixed). Regime agreement uses per-axis tertiles of centroid FLA.
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
Appendix
Table 12: Stability of joint regimes and of the backbone trend. A dataset is high/high if SLA and FLA are both ≥60 , low/low if both are <40 , and mixed otherwise. Changed counts datasets whose joint regime differs from the reference row of the same block. HH ↔ LL counts direct jumps between the two extremes. The last four columns are Pearson correlations between AlignAvg and accuracy. All rows above the last block use the 14 TU benchmarks with node attributes.
Figure 4: The SLA–FLA plane under alternative constructions. The 14 TU benchmarks with node attributes, colored by mean accuracy over the four backbones. Panel (a) is the reference construction; panels (b)–(d) change the feature summary and panels (e)–(f) change the structural blocks.
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
Appendix
Table 13: Stability across 5 seeds, each drawing new 10-fold splits and refitting the probes. GCN accuracies are held fixed at their Table 2 values. The last two columns are the mean and largest per-dataset standard deviation of the score, in accuracy points.
Dataset
k
#Graphs
Av.Nodes
Av.Edges
# Feat.
#Classes
Texas
1
183
4.05
9.83
1704
5
Texas
2
183
66.68
215.73
1704
5
Texas
3
183
127.83
450.69
1704
5
Cornell
1
183
4.03
8.74
1704
5
Cornell
2
183
55.86
146.09
1704
5
Cornell
3
183
116.04
360.03
1704
5
Appendix
Table 14: Dataset statistics for Node-to-Graph heterophilic ego-graph benchmarks at varying k -hop sizes.
Dataset
k
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
Appendix
Table 15: Pooled-model accuracy (%) tracked against the alignment plane for heterophilic ego-graph datasets at varying hop sizes k . AlignAvg summarizes alignment as (SLA+FLA)/2 .
Figure 5: GNN performance across synthetic sweep with boundaries. For a full synthetic sweep across the SLA-FLA plane colored by GNN accuracy. The dashed line marks a decision boundary for “good” performance set at 80% accuracy. We include results for all four backbones, beginning in the top left: GCN, GraphSAGE, GAT, and GPS.
Figure 6: Graph Filtration: For G=G3 in both examples, the top figure illustrates a superlevel filtration using the node degree function with thresholds 3>2>1 , where nodes of degree 3 are activated first, followed by those of lower degrees. Similarly, the bottom figure illustrates a sublevel filtration based on edge weights with thresholds 1.5<1.8<2.1 .
Dataset
GLAGCN
GCN
ΔGCN
GLASAGE
SAGE
ΔSAGE
GLAGAT
GAT
ΔGAT
GLAGPS
GPS
Δ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
Appendix
Table 16: Absolute deviation between predicted GLA scores and observed pooled accuracy. For each backbone, ΔBB=∣GLABB−AccBB∣ . Accuracies use reported means. Featureless datasets (FLA undefined) are omitted.
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.
Neither cue aligns; need capacity but accuracy remains limited.
Appendix
Table 17: Practical backbone choice as a function of SLA/FLA regime.
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
Appendix
Table 18: Synthetic sweep results reported in dataset-style format. All GNN results are reported as mean ± standard deviation (in percentage points), computed over multiple random seeds. Synthetic datasets were generated consistently across backbones using 1000 graphs per configuration, approximately 120 nodes ( ±20 variance), feature dimension 16, and a 15×15 SLA/FLA grid. AlignAvg denotes the arithmetic mean of SLA and FLA (lower is worse).
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 ×
Appendix
Table 19: Wall-clock seconds for one pass of GLA (one seed, 10-fold CV, LogReg and RBF-SVM on SLA and FLA) against one 100-epoch training run of each backbone with a single hyperparameter configuration, on one machine.
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
Appendix
Table 20: Leave-one-dataset-out prediction of GCN accuracy from SLA, FLA, and AlignAvg with a linear model, on the 19 benchmarks where FLA is defined, sorted by absolute residual (observed minus predicted).
Δgraph≤+2
+2<Δgraph<+10
Δgraph≥+10
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
Appendix
Table 21: Δgraph (accuracy points) for the 19 benchmarks where FLA is defined, computed from Table 2 .
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
Appendix
Table 22: Official OGB scaffold split (S) against a random split of the same train and test sizes (R). SLA and FLA average LogReg and RBF-SVM, and R averages 5 seeds. GCN is a single untuned run on each split with unweighted cross-entropy. BA is balanced accuracy and AUC is ROC-AUC, using the first task on multi-task datasets.
We propose a novel benchmarking methodology for graph neural networks (GNNs) based on the graph alignment problem, a combinatorial optimization task that generalizes graph isomorphism by aligning two unlabeled graphs to maximize overlapping edges. We frame this problem as a self-supervised learning task and present several methods to generate graph alignment datasets using synthetic random graphs and real-world graph datasets from multiple domains. For a given graph dataset, we generate a family of graph alignment datasets with increasing difficulty, allowing us to rank the performance of various architectures. Our experiments prove that there is an optimal task difficulty for having a statistically relevant ranking of different models and that, even on a structure-only task, anisotropic models perform better compared to isotropic ones. To further prove that our synthetic task capture meaningful information, we show its effectiveness for self-supervised GNN pre-training: the learned node embeddings can be leveraged as positional encodings by transformers for graph regression or can be used to reconstruct the full structure of the graph with 98% accuracy. To support reproducibility and further research, we provide an open-source Python package to generate graph alignment datasets and benchmark new GNN architectures. The source code is available at https://github.com/adrien-lagesse/graph-alignment-benchmark.
Adrien Lagesse, Marc Lelarge
INRIA, École Normale Supérieure - PSL, Paris, France.
For the combinatorial graph alignment problem (GAP), finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs, the classical Frank-Wolfe heuristic FAQ remains a strong baseline once it is properly initialized, while existing GNN approaches struggle in the purely structural setting. We introduce a chaining procedure: a sequence of Folklore-type (2-FWL) GNNs in which each network is trained with cross-entropy after decoding the previous network's similarity matrix and ranking nodes by their current alignment quality. This non-differentiable ranking step injects discrete combinatorial feedback at every stage; at inference, we iterate the final network and keep the candidate with highest observed nce. On sparse Erdos-Renyi graphs at noise level 0.25, chained FGNNs used to initialize FAQ reach 85% accuracy versus 13% for FAQ initialized from the convex relaxation, and essentially 0% for prior GNN methods. On correlated regular graphs, where MPNNs with constant features produce identical node embeddings (1-WL fails to refine) and FAQ's convex initialization is degenerate, chaining is the only method among those we evaluate, including Gromov-Wasserstein solvers, that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline. Code and pretrained chains available at: https://github.com/mlelarge/chaining-gnn-graph-alignment.
Marc Lelarge
INRIA - Ecole Normale Supérieure PSL Research University
Graph pooling is commonly applied in graph classification, yet its empirical gains over standard WL-1 expressive GNNs are often marginal or inconsistent. We study this gap by analysing the interaction between node features and graph topology and their effect on pooling objectives. Our analysis reveals that pooling operators require node features that are well-aligned with the graph's topology -- a condition often overlooked and not guaranteed in empirical networks. We formalise fundamental requirements for node features to enable effective pooling, and introduce a quantitative measure of feature quality. Our empirical evaluation shows that, when these requirements are satisfied, pooling can be beneficial and improve performance on appropriate datasets.
Jan von Pichowski, Alžbeta Hrabošová, Ingo Scholtes +1
Center for AI and Data Science University of Würzburg, Germany · Department of Computing Science Umeå University, Sweden