Canonical Tree Cover Neural Networks for Expressive and Invariant Graph Learning
Authors: Michael Ito
Danai Koutra
Jenna Wiens
Venue: ICLR 2026 Poster (2026)
Keywords: graph neural networks
canonicalization
invariance
tree
molecule graph
Primary area: learning on graphs and other geometries & topologies

Abstract: While message-passing NNs (MPNNs) are naturally invariant on graphs, they are fundamentally limited in expressive power, oversmooth, and oversquash. Canonicalization offers a powerful alternative by mapping each graph to a unique, invariant representation on which expressive non-invariant encoders can operate. However, existing approaches rely on a single canonical sequence that distorts graph distances and restricts expressivity. To address these limitations, we introduce Canonical Tree Cover Neural Networks (CTNNs), which represent the graph with a canonical spanning tree cover. Each tree is then processed with an expressive tree encoder. Theoretically, tree covers better preserve graph distances in comparison to sequences, and on sparse graphs, the cover recovers all edges with a logarithmic number of trees in the graph size, making CTNNs strictly more expressive than sequence-based canonicalization approaches. Empirically, CTNNs consistently outperform invariant GNNs and sequence-based canonical GNNs across sparse molecular and protein graph classification benchmarks. Overall, CTNNs advance graph learning by providing an efficient, invariant, and expressive representation learning framework on sparse graphs via tree cover-based canonicalization.

Published as a conference paper at ICLR 2026
CANONICAL TREE COVER NEURAL NETWORKS FOR EXPRESSIVE AND INVARIANT GRAPH LEARNING
Michael Ito University of Michigan mb i to@umi edu
Danai Koutra University of Michigan dkoutra@um ch edu
Jenna Wiens
University of Michigan wi ens umi ch edu
ABSTRACT
While message-passing NNs (MPNNs) are naturally invariant on graphs, they are fundamentally limited in expressive power, oversmooth, and oversquash. Canoni- calization offers powerful alternative by mapping each graph to unique, invariant representation on which expressive non-invariant encoders can operate. However, existing approaches rely on single canonical sequence that distorts graph distances and restricts expressivity. To address these limitations, we introduce Canonical Tree Cover Neural Networks (CTNNs). which represent the graph with canonical spanning tree cover. Each tree then processed with an expressive tree encoder. Theoretically, tree covers better preserve graph distances in comparison to se- quences, and on sparse graphs, the cover recovers all edges with a logarithmic number of trees in the graph size, making CTNNs strictly more expressive than sequence-base based canonicalization approaches. Empirically, CTNNS consistently outperform invariant GNNs and sequence-based canonical GNNs across sparse molecular and protein graph classification benchmarks. Overall, CTNNs advance graph learning by providing an efficient, invariant, and expressive representation learning framework on sparse graphs via tree cover-based canonicalization.
INTRODUCTION
In graph representation learning, capturing a graph's 's natural symmetries (i.e., isomorphism invariance) is essential for learning and generalization. One way to enforce this invariance is to bake it directly into the architecture: message-passing neural networks (MPNNs) (Duvenaud et al.] 2013 Gilmer et al.. 2017] Kipf and Welling 2017) achieve architectural invariance by iteratively aggregating neighbor embeddings, but are provably equivalent in expressive power to the 1-dimensional Weisfeiler-
test (Xu et al. 2019 Morris al. 2019), and suffer from oversmoothing (Li et al.) 2018 Chen jet al. 2020) and oversquashing (Oono and Suzuki 2000): Di Giovanni et al., 2024). and are thus fundamentally limited. A second approach achieves invariance via random sampling: random walk neural networks (RWNNs) (Tönshoff et al. 2023 Chen et al. 2025 Kim et al. 2025; Ito et al. 2025) sample walks input powerful sequence models, overcoming MPNN limitations but incurring potentially prohibitive sampling costs when training on large datasets. A complementary line of work relies on canonicalization. which maps each graph to a unique representative, allowing any expressive, non-invariant model to operate on a fixed, invariant input, bypassing expensive sampling Redde and Teh 2020 Kaba et al. [2023). In this work, we establish the limitations of existing canonicalization approaches graphs and propose new canonicalization.
Existing graph canonicalization approaches first assign labels to each node, flatten the graph into a
single sequence, either via learned sorting layers (Niepert et al.) 2016 Zhang et al. 2018 Grover
ct al. 2019) or through traversal as in canonical SMILES (Goh et al. 2017 Honda et al. 2019) and
then feed the sequence into a powerful down- stream sequence model. In this work, we for- mally quantify how flattening into sequence distorts graph distance. To illustrate this limi- tation, consider Sn, the n-node star (Figure I = 7). Each leaf node in the graph has dis- tance 1 to the center node, while leaf nodes in the sequence necessarily have distance ((n) to
Graph
Canonical Sequence
Cseq
Figure I: Canonical sequence representations in- troduce significant stretch and contraction.

---

Published as a conference paper at ICLR 2026
the center node (stretch). Moreover, while leaves have distance 2 to each other in Sn, certain leaves have distance in the sequence (contraction). Thus, the sequence-based based canonicalization can stretch and contract original distances, making structure harder to capture. We further establish that the reduction of the graph into a single sequence limits the expressivity of the overall approach to that of its node labeler, discarding the benefits of using powerful downstream models.
To address these limitations, we propose Canonical Tree Cover Neural Networks (CTNNs), which construct canonical spanning tree cover via minimum spanning tree extraction and coverage-aware edge label refinement. Each tree in the cover is processed by an existing expressive tree encoder ( (Tai al. 2015) and aggregating over the cover yields an invariant representation. Importantly, CTNNS leverage coverage-aware edge labelers that are initialized by node labeler: when using canonical graph node labeler that assigns unique labels to all nodes (e.g., NAUTY (McKay and Piperno 2014 the resulting tree cover is fully deterministic and invariant; when using inexpensive, structurally meaningful labelers (e.g., degree, centrality, or 1-WL), tie- neebbeeking introduces randomness, leading to probabilistic invariance while preserving useful inductive biases. By leveraging tree representations and capturing structure across a set canonical representatives, CTNNs better capture graph distances and more expressive than sequence- based canonical GNNs. Across sparse molecular and protein graph classification tasks, CTNNs consistently outperform architecturally invariant GNNs and existing canonical GNNs. In summary, we make the following contributions:
Current Limitations of Canonical GNNs. We establish that sequence- based graph canoni-
calization methods fail preserve graph distance and are limited in expressivity.
New Canonical GNN: Canonical Tree Cover Neural Networks (CTNNs). We introduce CTNNs, which construct a canonical tree cover. Each tree is then processed by expressive recurrent tree encoders and aggregated to obtain an invariant representation.
Theory: Invariance, Distance Preservation, and Expressivity Guarantees. We prove that CTNNs produce invariant graph representations, preserve graph distance information,
and exceed the expressivity of sequence-basee canonical GNNs and MPNNs. With universal tree encoders, CTNNs achieve universality invariant graph functions.
Extensive Empirical Evaluation. Across molecular and protein graph classification bench- marks, CTNNs outperform architecturally invariant GNNs and canonical baselines.
2 BACKGROUND AND PRELIMINARIES
We first introduce notation and review canonical approaches on graphs, the primary family of models under investigation. These approaches typically produce single sequence that is fed to sequence model. We then formalize recurrent sequence models, which often outperform attention and convolution on graphs by better matching the traversal inductive bias. Despite their practical performance, however, recurrent sequence models can suffer from long graph-derived sequences. These limitations lead us consider recurrent tree models that instead propagate information along trees, which we will later demonstrate better capture graph distance.
2.1 NOTATION ON GRAPHS AND TREES
Let G= X) be an undirected graph with n [V| nodes, m |E| edges, and node features X E Rnndd For E V, let x,, denote the w-th row of X, (v) = {u E V (u, v) E E}} its neighborhood, and deg(v) = (w))) and do(u, v) the shortest path distance in G. A rooted tree is T= (V. E, X,r) with root E V. Each non-root node e o r has unique parent p(v), and we write C(v) = (u (uEV V: p(u)= = o) for its children. Leaf nodes of the tree satisfy C(v) = Ø.
2.2 MESSAGE-PASSING GRAPH NEURAL NETWORKS AND GNN EXPRESSIVITY
Message-passing GNNs (MPNNs) update node representations by pooling representations from local neighborhoods via a permutation-invarian aggregator (Duvenaud et al. 2015 Gilmer et al., 2017 Kipf and Welling 2017). Concretely, for graph G and node E V. one layer takes the form
fMPNN (G); = fage( :j E (())),
where (1) denotes the self-loop augmented neighborhood of and fage is permutation iiniiiiinnnnaaiitt....m While this invariance is desirable, also limits distinguishability, and MPNNs cannot separate certain
2

---

Published as a conference paper at ICLR 2026
families non-isomorphic graphs (Xu al., 2019: Azizian and Lelarge 2021 To compare model expressivity, we use the standard preorder on graph-level maps: for two GNNs f1, fz. define
/2 5
- HG (G))) (iHH) = /2(G) - (2(H).
Equivalently, fi is at least as discriminative as f2. We write fo < fi if = fı and the inclusion is strict (i.c., some G, are separated by fi but not by f2), and fi ~ f2 if both f2 3 fi and 3 f2 hold. This ordering aligns with approximation power: if f2 < f1, then any target representable by f2 representable by fI, while the converse fails general.
2.3 CANONICAL GRAPH NEURAL NETWORKS
Graph canonicalization aims to obtain unique ssomophhismiivaare invariant node labeling (McKay 1981). Because computing an exact canonical labeling is as hard as the graph isomorphism problem, practical methods adopt soft approximations (e.g., GNN embeddings). After obtaining an approximate labeling, these pipelines typically flatten the graph into a single sequence either via sorting layers (Niepert et al.
2016
Zhang et al., (2018) through traversal such canonical SMILES (Goh et al., 2017] Honda
ct al. 2019 Chithrananda et al. 2020), allowing expressive sequence models to process the sequence. Formally, let .Ty
R be a node labeling function (e.g.. MPNN), Cseq be single-sequence canonicalizer that maps the labeled graph (G, πV) to sequence depending only on and carrying only the node features X, and feeq be a sequence model. A general sequence- based canonical GNN is defined as
SCanSoq (G) = (Crog πV)):
As concrete instance, if ITy is an MPNN, Cseq is differentiable sorting layer, and feeq is ID CNN, then SCanSoq recovers Deep Graph Convolutional Neural Network (Zhang et al. 2018).
2.4 RECURRENT SEQUENCE AND TREE MODELS
Recent RWNNs find that recurrence often outperforms attention and convolution by better matching the traversal inductive bias (Wang and Cho 2024 Chen et al. 2025 Ito al.) 2025). Given inputs (x,)?= initial state ho, and state transition map Φb R R" R the recurrent update is defined
h; = (h),,,,,,
for I,..,,
Recurrent models suffer on long sequences that exacerbate vanishing/exploding gradients, which motivates of recurrent tree models that shorten dependency paths and mitigate these instabil- ities. Recurrent tree models generalize sequence recurrence to rooted trees (Tai et al. 2015 Xiao al. 2024), propagating information bottom-up from children their parent. Given with L levels and node inputs [Xw recurrent tree models compute hidden states (h, Jo by applying a local transition child states and aggregating with a permutation invariant operator f faggi
E,r)
h,
Jaga (( (b, x,) |c C(w))) for L, ... and e with (v, E,
with fagg (Ø) 0 for leaves. Setting & (he, x.) standard LSTM update recovers the Tree LSTM of Tai et al. 2015 The tree representation is taken as h, at the root. In Section 4 we propose a canonicalization of graphs via spanning tree covers that can be used input to recurrent tree models.
3 LIMITATIONS OF SEQUENCE-BASE CANONICALIZATIONS
In this section, we characterize the limitations of single-sequence canonical GNNs. First, we quantify how sequence canonicalization distorts graph structure, stretching and contracting graph distances. We next turn to expressivity and demonstrate that even when the sequence model is universal, the canonical GNN is no more expressive than its node labeler because it relies on single canonical representative. Together, these limitations motivate our tree cover-based canonicalization, which better preserves distances and increases expressivity by operating on a cover of spanning trees.
3.1 DISTANCE DISTORTION UNDER SEQUENCE CANONICALIZATION
To formalize how sequence canonicalization fails preserve structure, distortion (Matoušek) 2013), which quantifies the stretch/contraction in distance after mapping points between spaces. Intuitively, we prefer canonicalizations with lower distortion, better preserving the original distances.
3

---

Published as a conference paper at ICLR 2026
Node Labelling Function (1-WL, MPNN): TV
Sequence Canonicalizer (SORT, BFS): Gooq
0000000000
coooooo.oo
Figure 3: Sequence canonicalization is only as expressive its labeler ay despite using universal downstream sequence model. fCanSeq thus fails to distinguish graphs TV fails to distinguish.
Definition 3.1 (Distortion). Let (X; xx and (Y,dy) be metric spaces. A mapping f (X, (x) (Y,dy) has distortion D 2 1 if there exists > 0 such that for all x, E X,
r dx( & dy(f(z), < Drdx(x,
Let (G, dG) denote a graph with shortest-path distance da, and let Creq (G, be its single canonical sequence under Ty. Equip Caeq with the distance dseq v) (o (v)) where
a (I, [V]] is the induced ordering. Let (G) be the graph bandwidth (Díaz et al. 2002).
which measures the smallest maximum stretch over any edge when G is laid on line:
g(G) = min max (,,D)EE
(a(u) a(v)]-
Existing work studies embeddings f + IR into the real line and imposes a non-contractive constraint, under which the distortion reduces max stretch and is lower bounded by graph band- width (Heggernes et al. 2011 Dragan et al. (014). In our setting, however, we consider permutations fI...... which are the natural inputs to sequence models and can exhibit both stretch and contraction. Under permutation embeddings, we provide an analogous result.
Corollary 3.2 (Graph bandwidth lower bounds sequence distortion). Let Daeq be the distortion of Cooq (G, πv) from from (G, dc) to the line with distance dseq. Then, for any TV, :p(G) S DDaqq-
All proofs are in Appendix A The bandwidth lower bound gives concrete, well-studied graph metric to evaluate the distortion of Czeq. Although (²G) is hard to compute in general, it is known for many families (Figures 2 on n-node stars S, and cliques Kn, one has (sS,). (p(K) ( any single-sequence canonicalization incurs the worst-case linear distortion; on complete binary trees <p(T2.)) O(2' / (n// / log n2), and cycles C, and paths P. one has yp (a,) (CC,, O1).
Beyond specific families, the bound offers general insights. Given that ((G) 2 (n - 1)/ (G).
Daeq is least (n - 1)/ diam(G), is also monotone un- der edge addition, indicating that highly connected graphs, reflected by larger algebraic connectivity A2, force larger distortion. These effects negatively impact the sequence model: distorted distances make structure more difficult capture. Importantly, any method relying on sequences, including canonicalizations and sampling approaches like RWNNs, inherits these limitations. To address the lim- itations of sequences, we turn to tree representations.
<(K..) O(n)
(T2, (mx log n)
Figure 2: yp(G) for re-noee clique, Kn, and complete binary tree with levels, T2.e.
3.2 EXPRESSIVE LIMITATIONS OF SEQUENCE-BASED CANONICAL GNNS
Beyond the limitations of sequence representations due distortion, we characterize the expressive limitations of the canonical GNN due to relying only on single sequence. Formally, we show that ScanSeq when equipped with universal [seq only as expressive as node labeler Tу.
Proposition 3.3 (TV and fCanSeq are equally expressive). Let J'CanSon be canonical sequence-based model with universal Sanq and let πV be its labeling function. Then, J'CanSoq TV.
TV is an MPNN, its power matches 1-WL; consequently, fCanSeq inherits 1-WL limitations and fails the same graph families (Figure 3) Crucially, this holds even when fsen is universal: once information is lost at the labeling stage, no downstream single-sequence canonicalization can recover it, limiting the expressivity of the full pipeline. Although multiple labelers and sequences could be used to improve expressivity, sequences remain limited by distortion. Thus, in order to address the limitations of the single labeler and sequence, instead consider multiple labelers and trees.
4

---

Published as a conference paper at ICLR 2026
Legend
Log([V] Canonical Spanning Tree Cover
Weighted MST Edge
T MST (
T
MST(G, mB
Weighted Missed Edge
Original Graph
(k)) Figure 4: Canonical spanning-tree cover. At iteration k compute MST ag using coverage- aware edge weights (thicker = larger magnitude weight). Edges missed in k (red) are up-weighted to bias their inclusion in & 1. On sparse graphs, the union of Ollog VV) trees covers all edges.
CANONICAL TREE COVER NEURAL NETWORKS (CTNNs)
To address the representation limitations of sequences due to distortion and the expressive limitations due to single sequence, introduce Canonical Tree Cover Neural Networks (CTNNs), which construct a canonical spanning tree cover. Section [ we demonstrate that tree representations better preserve graph distances in comparison to sequences, while set of canonical trees allows for complete graph reconstruction and is strictly more expressive than a single sequence.
4.1 CANONICAL SPANNING TREE COVERS
To construct canonical spanning tree cover, we leverage coverage-aware edge labelers and minimum spanning tree (MST) samplers rather than fixed node labeler and sequence canonicalizer. By updating edge weights across rounds, later trees are biased toward edges not yet selected, yielding provable coverage across the union of sampled trees. Formally, let G' be graph and at iteration
E-+ RR be an edge labeler. Let Curee be MST to spanning tree (k) according to weights TE setting the root node as the center of (k),, To promote edge coverage across the set, we update the weights by penalizing edges used in the last tree (A)) with hyperparameter We initialize with any nomorphism-invarian node labeler Ny (e.g., degree), which biases MSTs towards edges incident to high label nodes. Formally, the update and initialization can be written:
(O...., K 1} for hyperparameter K let T (k)
extractor that maps an edge-labeled graph (G, T (k) (Ik)
(i+1) TE (e) = - + (v()))), "g
= T (e) + Ie T(K)}
refer further implementation and pseudocode details of the construction in Appendix
4.2 INVARIANT CANONICAL TREE NEURAL NETWORKS
Given a canonical cover of MSTs, T (T(K) Jk=0 process each with recurrent tree encoder and augment it with message passing over the remaining non-tree edges to capture the local connectivity missed by each individual spanning tree. Let the residual graph be G) (kk)
(V. E (+)( and denote ftree as recurrent tree encoder (e.g., Tree LSTM Taii et al. 2015 and fMPNN MPNN (e.g., GIN (Xu et al. 2019)). For each is E {0...., K 1} and node
fIeeMPNN (T()), = ftroe(((()) + SAAPN(GAATTA))
We then aggregate across the set of trees with permutation-invalt operator fage to obtain
JCTNN = Sages (1TreeMPNN( (Tk) Ctroo (aceeGG, a (8)). 0 O...,, ==.....,K11) K-13)
Probabilistic invariance. When CTNNs use an inexpensive, structurally meaningful node labeler that does not uniquely distinguish vertices (e.g., degree), we obtain probabilistic invariance (Bloem) Reddy and Teh. 2020: Kim et al.) 2025 Ito et al. 2025). Such labelers are ssomorphim-invarri resolve ties using random tie- bre-brea.ing. This induces
but may assign identical scores to nodes, an isomorphism invariint distribution over spanning tree covers. Formally, for any permutation g S, acting G by relabeling nodes, the random output JCTNN(G) has the same distribution
5

---

Published as a conference paper at ICLR 2026
O(n) Single Tree Distortion
O(1) Expected Distortion over Spanning Tree Distribution
Figure 5: Single tree distortion (n)) on Cn. while expected distortion is constant over a spanning tree distribution since average the distance between any two nodes is small.
as fCTNN(O (g- GG). Consequently, the averaged predictor E fCTNNN (G) is an invariant function on graphs. In this regime, CTNN relies small amount of randomness break symmetries, but that randomness is controlled by the underlying canonicalization (i.e., node labeler).
Theorem 4.1 (Probabilistic invariance CTNNs). randomized graph representation X(G) is
probabilistically invariant if distribution unchanged under any node relabeling, i.e., X(G) _ (g. (gg-GG for every permutation E Sn- The random output fCTNs (G) is probabilisticall invariant:
fCTNN(G) _ =fCINN(g-G for all g Sn-
Then, (G)) [[JoTNN(G)) an invariant function satisfying (GG) (g- B--G for all g Sn.
Deterministic invariance. At the other end of the spectrum, one can instantiate CTNN with true graph canonicalization tool such as NAUTY (McKay and Piperno 2014), which computes canonical labeling that separates all nodes up isomorphism. With such canonical node labeler and an injective initialization of edge weights the induced tree cover becomes a deterministic canonical representation: isomorphic graphs
mapped to exactly the same set of trees, and SCTNN = JCTNN(g G)) holds for all permutations g. This is particularly beneficial when the graph exhibits high degree of symmetry such as complete regular graphs, where weaker node labelers result in many ties. CTNN thus provides a unified framework that interpolates between fully deterministic canonicalization and probabilistic invariance, depending on the choice node labeler.
4.3 RUNTIME COMPLEXITY
CTNN preprocessing is primarily dominated by constructing the K MSTs and cost of πV. Using Kruskal's algorithm (Kruskal 1956), the total cost is O(K m log + πV), which is efficient on sparse graphs where O(n) and for inexpensive my (e.g., degree). A major practical advantage of canonicalization is that these trees are computed once before training and reused across epochs, climinating on-the-fly sampling incurred by sampling approaches. The computation parallelizes naturally across graphs, and the memory cost is small (O(Kn) edges per graph). Empirically, we show this preprocessing time efficient across datasets (Appendix)) E.2).
DISTORTION AND EXPRESSIVITY BOUNDS FOR CTNNS
We first analyze distance preservation: because CTNNs aggregate over spanning trees, they yield distortion bounds that better preserve graph distance in comparison single-sequence canonicaliza- tion. We then turn to expressivity, establishing the benefits sets of canonical representatives. On sparse graphs tree cover recovers the full edge set with only Ollog m) trees, which has two im- mediate consequences for expressivity: (i) CTNNs are strictly more expressive than single-sequene canonicalizations, and (ii) when paired with universal tree encoders, CTNNs become universal.
5.1 EXPECTED DISTORTION BOUNDS FOR CTNNS
We first analyze how well CTNNs preserve distances, establishing distortion bounds for Cueee Because CTNNs sample MSTs, we use probabilistic distortion (Fakcharoenphol et al. 2003).
Definition 5.1 (Expected distortion). Let (X, dx) be metric space and let μ distribution on metrics M(X). The expected distortion of is the least D s.t for r > 0 and for all æ, y X,
dx (x. < Eppg [p(x, v)] < Dr Drdx(x,1)

---

Published as a conference paper at ICLR 2026
MST Distributions for T
MST Distributions for T
Non-isomorphic graphs G, indistinguishable 1-WL
1,0
10
10
[G, ]MPNN] (H, NMENN)
MAT ham srrrandd
Figure 6: Two non-isomorphic stably colored graphs indistinguishable to 1-WL (left). The first extracted MST T(1) for G is isomorphic to T()) from and the distributions are equal, but after reweighting and extracting T(2), the MST distributions diverge, illustrating that multiple canonical trees can be more informative than single canonical tree (right).
As a baseline, we analyze distortion for uniform spanning trees (USTs). In this regime, the expected tree distance between nodes and is upper bounded by their hitting times, the expected number of steps a random walk takes to travel from u to v. Empirically, we verify that CTNN tree distributions inherit and can improve upon the low-distortion behavior established by USTs (Appendix [E.3)
Theorem 5.2 (UST expected distortion). Let be a graph, and let T be a uniform random spanning tree of G. Denote by H (u, v) the random walk hitting time from
Then,
DUST max E [dr(u, (t)r(,))))//(.u. /d) a,v
[[dr(u,)) v)] < H(u, v) (v,u))/
In contrast to the bandwidth lower bound for single-sequenee canonicalization, which can force worst-case distortion, the expected UST distortion aligns with random walk distance and preserves structure significantly better on sparse families. Every tree admits unique spanning tree, so on trees DUST 1. By comparison, Cseq incurs distortion (nz log n.) balanced trees and (n)) on stars. On Cn. distortion also constant, highlighting the benefit of averaging over trees (Figure 5). Our bounds also provide general insights: tree distances behave well in sparse graphs, where the square root of hitting times and shortest paths scale comparably. In highly dense graphs, however, shortest paths are smaller than hitting times and distortion worsens. Overall, CTNNs yield expected distortion that is small on many sparse structures where in comparison single sequences stretch distances, better capturing graph structure for downstream encoders.
5.2 COVERAGE AND EXPRESSIVITY GUARANTEES VIA MST CANONICALIZATION
We now turn to the expressive benefits of CTNNs. Instead of relying on a single canonical represen- tative, CTNNs build spanning tree cover, providing downstream encoders access full structure. We first show our goverage-aware MST scheme needs only logarithmically many trees to cover all edges on sparse graphs. We then leverage coverage to show CTNN expressivity strictly greater than sequence- based canonical GNNs and establish its universality on graph functions.
Lemma 5.3 (Logarithmic spanning tree cover). Ler = E) be a graph with m |E| and arboricity T(G), the minimum number of forests required to cover G. Fix any node labeler πV with K-1 as the set of trees produced by CTNN. > max, TE (e) mine E (c). (0). Denote T (T(()) 1k=0
(0)
If 2 T(G) In m iterations, the union of the MSTs covers all edges: UK-1 E(r(0)) = E.
Importantly, on sparse graphs, arboricity is constant, and CTNNS obtain full coverage with K > (log((VV)). As established in Section 3 fCanSeq is only as expressive as Ty. CTNNS, by contrast, operate tree cover enabled by coverage-aware edge label refinement, and as result, are strictly more expressive than their initial labeler. In this setting, fCan Tree is randomized function due to the randomness induced by IV. Hence, we use the following probabilistic notion of distinguishabilityy. Proposition 5.4 (fMPNN < JCanTree)) Let SCauTree be a CTNN satisfying Lemma 5.3 equipped with Ty N SMPNN- Then, VG, H, SCanTree d SCanTroe = SMPNN( SMPNN((F) Moreover, 3G 인 H such that fCantree (G) $ fCanTron (H) while JMPNN (G) (MPNN(H).
In cases where the graphs exhibit a high degree symmetry, and .V fails to distinguish them initially, the reweighting scheme and tree cover allow CTNNs to distinguish the graphs, exceeding the expressivity of πy (Figure 3 When CTNNS are equipped with a canonical node labeler Vy that separates all nodes, universal free encoder, and full coverage, they are universal.
7

---

Published as a conference paper at ICLR 2026
Theorem 5,5 (CTNN Universality). Let G be a finite class of graphs. Assume: (i) K satisfies Lemma 5.3 (ii) the tree encoder fieee and aggregation fagy are universal on their domains, and (ii) TV is canonical node labeler that separates all nodes. Then for any continuous invariant graph function f G -> IR and any > O, there exists a CTNN such that
supl [CTNN(G)) [[nnN S E. GEO
6 EXPERIMENTS AND RESULTS
Through empirical evaluation, we aim to answer the following research questions, extending our theory by testing CTNNs on datasets with factors not explicitly addressed in the theoretical analysis (e.g., class imbalance), and including domain-specific canonicalizations beyond our theory, such as molecular fingerprints (Rogers and Hahn 20T0) commonly used in molecular analysis.
RQI (Discriminative performance). How does CTNN compare (i) invariant GNNs upper bounded by 1-WL expressivity (GCN, GAT, GIN), (ii) expressive GNNs more powerful than 1-WL (GT, RWSE, GSN, ESAN) and (iii) canonicalization baselines? RQ2 (Distance distortion). Do CTNNs reduce metric distortion relative to sequence-based canonicalizations, and does this reduction translate into improved task performance? RQ3 (Ablations and sensitivity). Which components of CTNN contribute most to perfor- mance, and how sensitive is performance to their settings?
6.1 EXPERIMENTAL SETUP
Datasets. We evaluate on molecular and protein benchmarks, domains where canonicalization widely adopted and frequently used in practice (Goh et al.) |017] et al.] 2019) and where long-range dependencies and high expressivity are critical (Dwivedi et al. 2022a). For molecules, we use Cox, BACE, BBBP, HIV, and PCBA datasets from MoleculeNet (Wu et al., 2018)) For proteins, adopt ProteinShake (Kucera et al., 2023) datasets: SCOP, GO MOL, and GO BIO. These tasks span diverse molecule and protein tasks such as molecular activity and protein structure classification. Notably, proteins are larger than molecules, making structure more difficult to capture. To demonstrate CTNNS are applicable to domains in which canonicalization is not yet widely adopted, we evaluate on a larger and denser brain graph classification benchmark (Said et al., 2023). where the task is to predict I of 7 mental states (e.g., emotion processing) (Appendix E.4)
Baselines. We consider invariant GNNs upper bounded by 1-WL expressivity: (1) GCN KKipf and Welling 2017). (2) GAT (Veličković et al. 2018), (3) GIN (Xu et al. 2019). We next consider expressive GNNs strictly more powerful than I-WL message passing: (4) GT (Dwivedi and Bresson 2021], graph transformers, (5) RWSE (Dwivedi et al. 2022b) and (6) GSN (Bouritsas et al. (022). which augment message-passing with additional structural features, and (7) ESAN (Bevilacqua et al. 2022), which decompose the graph into subgraphs, processing each component with an MPNN. We also evaluate canonicalization approaches: (8) Fingerprint (Rogers and Hahn 2010), stacking
an MLP hand-crafted chemical descriptors, (9) SMILES (Goh et al. 2017). applying sequence models over canonical SMILES, (10) Primary Seq. (Alley et al. 2019), applying sequence models to the primary sequence, (11) DGCNN (Zhang et al., 2018), representative sequence bassed canonical approach leveraging MPNNs as TV and sorting as Czeq. and (12) RCM (Diamant et al., 2023). applying sequence models to the ordering determined by the Cuthill-McKee algorithm. We provide summary of the design space for all canonicalizations in Appendix C
Training and Evaluation. For all benchmarks, we set ftree Tree-LSTM. fMPNN GIN, fags as SUM, (v) = deg(v), and r = 1. For molecular datasets, we set K = 4, and for pro- AUC or
teins, we use K = 8. Following each dataset's protocol, performance is computed accuracy. We report median (min, max) performance over five random splits (60/20/20), which is more robust than mean and standard deviation for small sample sizes. We compute stretch as max;, (demb (i.j))dg((, } and contraction as max;, (dc(( (i) demmm (i. For sequence canoni- calizations, demb = dueg. For CTNNs, we report expected distortion as the average across the trees (i.e., max;,, mcan, oo (i. (i. for stretch). We provide remaining details in Appendix
"Code he found http://ggthubccoommmDDDiiCCnnnnn
8

---

Published as a conference paper at ICLR 2026
Table 1: Median (min, max) of model performance (x 100) across test splits. We highlight in blue the best model. "NA" indicates not applicable; "OOT" denotes training exceeds the time limit (24h).
Small Molecular Benchmarks
Large Molecular Benchmarks
Protcin Benchmarks
ClinTax
BACE
BBBP
IIV
PCBA
SCOP
GO BIO
GO MOL
Graphs
1.5K
32K
Avg. [V]
26.1
34,1
23.9
25.5
26.0
217.5
254.5
250.1
Avg. [8]
28.0
26.0
27.5
28.1
593.8
687.5
Metric
A
AUC
AUC
AUCT
AUC T
ACC
AUC
AUC 1
GCN
62.4 plea 14.7)
59.2 (a0s, 64.31
73.9 (889) $1.41
60.1 (97.6 60.51
78.5 (160) 79.59
63.4 (52.8, 64.9)
59.2 (5TU) MAT)
60.6 (40.5, B4.5)
GAT
62.1
60.8
77.5
66.3
78.5
58.9
57.0
57.6
MPANGGE
GIN
59.7 (7-1
59.9
71.0)
75.3 (1944 85.3)
47.7 (85. 67.6
M0.4 (00.), 11.1
68.01 (67.) (9
(193,79 79 K3.7 (5...856)) 66.3
73.5)
75.8 94.0
69.4 (67.5
(79.6 90.9)
RWSE:
63.6 c..4 74.0)
57.7 (en 1..00000
73.7 (19 96.5)
59.4 (51 68
83.5 (82.5 8377)
74.5 (12.1,75.) 75.5)
74.0 (09.6 75
85.8 (5.00.661
GSN
(33. 69.2)
(64.9
71.4 (6-.3, 79.7)
54.2 (46.3,
(82.6 93.4)
(59.3 77.5)
85.0 853)
ESAN
618 (56.7, 66.7)
55,8 (523) 09.2)
74.9 (70., 90.00
71.9 (55.), 73,00
83.7 (63.5, 84.3)
66.6 (56.5, 68.5)
79.5 (1.5)
85.7 (55.6, 86.4)
Fingerprint
66.5 (52., 74.9)
82.9 (783) 00:30
86,2 (83.4 92.5)
76.2 (23.1.81.)) $1.61
84.7 (54.6 K5.2)
NA
NA
NA
Canooicall
SMILES
62.5 68577 68.0)
76.5 (68
71.9 (6655
65.8
80,4 (50.),
NA
NA
NA 85.2 (34.5, K5.8)
Primary Seq.
NA
NA
NA
NA
NA 84,9
63,0 (50.), 68.5)
74.3 (90.2 785)
DGCNN
60.1
67.2 (6.1,
75.0 (428,
66.6 (61.))
65.3
62.0 (9..,88))
84.5
RCM
70.7 688 m7
76.3 (ms 01.2)
84.3 (76 1. 198111
75.5 (21. 83.7
84.6 (845 (AM)
57.0 (7655
87.5
68.4 (M6.) 09.3)
83.3 (K2A KVT)
CTNN (ours)
91.0
(80.6, 90.4)
75.2 (3.3
(57. 57.5)
(7055, 74.0 (512)
(5644
Table 2: Mean + s.d. of empirical stretch and contraction across 50 random samples for canonicaliza- tions. In comparison to all canonicalizations, CTNNS significantly reduce stretch and contraction.
Max Stretch
ClinTox
BACE
BERP
HIV
PCBA
SCOP
GO BIO
GO MOL
SMILES
17.62 11.91
8.33
15.22 = 8.29 NA
20.02
11.31 NA
1882
NA
Canmial
Primary Seq.
NA
NA
NA
1726 34,11
165.22 + 44.51
173.08
37.83
DGUNN
23.92 1..0
6.91
14,96
6,09
19.16 10:33
19.04
196.44
16.03
192.56 : 15,54
192,84
14.62
RCM
3.92
0.75
a
4.36
33.76
3 8.71
CTNN (ours)
2.36 0.90
2.40 a 0.44
2.37 a 0.47
2:51 0.56
2.29 a 0.27
17.85 a 3.15
17.56 a 4.56
18.12 a 4.45
Max Contraction 1
SMILES
1.36
5.32 2:45
4.12 2.57
2.07
5.26 1
NA
NA
Canonkaal
Primary Seq.
NA
NA
NA
NA
NA
2.72 a 2,86
4.44 = 5.62
5:44 = 6.31
DGCNN
1..25
12.78 a 2,98
9.68 3.00
11.74
12.36
16.32 3.25
16.04 4.112
16.16 4.15
RCM
5.66
2.65
4,92 2.09
3.00
1.233
12.16
11,92 2.34
CTNN (ours)
1.00
1.00 a 0.00
1.00 a 0.00
1.00 à: 0.00
1.00 a 0.00
1.00 à: 0.00
1.00 = 0.00
1.00 a 0.00
6.2 RQ1& & RQ2: DISCRIMINATIVE PERFORMANCE AND DISTANCE DISTORTION
CTNNs significantly outperform architecturally invariant MPNNs and GTs, consistent with the theoretical expressivity gains established in Section 5.2 (Table D. Subgraph GNNs (RWSE, GSN, ESAN) are strong baselines and are particularly competitive on protein datasets, but CTNN exceeds their performance molecular benchmarks. We attribute this to the fact that, although subgraph GNNs increase theoretical expressivity beyond 1-WL, they still rely on message- paassiggg and inherit known limitations such as oversmoothing and oversquashing. CTNN mitigates these issues by operating on low-distortion spanning tree covers with powerful recurrent tree encoders.
While some canonicalizations are competitive, they depend domain knowledge and lack generality (e.g.. Fingerprint). CTNNS outperform or match all sequence-basee canonicalizations, including those that are domain-driven and provide one-to-one encodings of their graphs (SMILES, Pri- mary Seq.), allowing for maximal expressivity. We attribute CTNNs' gains to distortion (Table 2 Across molecular and protein benchmarks, CTNN tree covers achieve substantially smaller stretch than sequence- sequence-based canonicalizations. Crucially, trees never contract distances, obtaining optimal In contrast, sequences exhibit both large stretch and nontrivial contraction. A noteworthy case is RCM: its ordering reduces bandwidth and lowers stretch on molecular graphs, yet still doesn't reach CTNN performance because it incurs contraction. Moreover, on larger protein graphs its stretch increases, underscoring a fundamental limitation of single sequence canonicaliza- tion. Collectively, these results align with our theory: canonical spanning-tre tree covers preserve graph distances significantly better than sequences, enabling stronger downstream models.
contraction
On a larger and denser brain graph classification benchmark from NeuroGraph (Said et al. 2023), CTNN also obtains the best performance in comparison MPNNs (GIN) and canonicalization baselines (RCM and DGCNN) (.p4endix[E.4). These results demonstrate that CTNN is applicable beyond sparse biochemical domains, where canonicalization is not yet widely adopted.

---

Published as a conference paper at ICLR 2026
Table 3: Median (max-min performance for ablations on benchmarks across test splits. CTNN (full)
obtains or matches the best performance across all datasets, supporting each design choice.
Molecular Benchmarrks
Protein Benchmarks
Ablation
ClinTox
PCBA
SCOP
Single tree vs, cover
78.2 (122, M64) 78.7 cas. 92.) $7.4 (819, 91.3)
76.5 (1.,, aum 87.0 ase, K2.)
68.7 (603, 2010 69 (6x5, mus (222,
MPNN TreeMPNN
82.6 (73.3,90
853)
73.8 77 84.9 15.)
(563,
TreeRNN vs. TreeMPNN
84.3 (1011, 99.00
0815 857)
86.8 (82 91m)
77.9 87 87.0 874)
64.9 (82.5 68 78.7 013. 79
(H4 +5.7)
CTNN (full)
84.7 (16,9910 (9.3 350) 86.1 (806, 90A)
(5.2 81.5 87.4
72.1 (TIU, 74m 82.0 (51.2, K52) 86.6 (7.3).
6.3 RQ3: ABLATIONS AND SENSITIVITY
Ablations. We evaluate three CTNN variants to isolate which design choices matter most in which settings, including (i) replacing the cover with a single tree, (ii) replacing the TreeMPNN with an MPNN, and (iii) replacing the TreeMPNN with a TreeRNN (Table 3p On molecular benchmarks, the ablations are often competitive with the full model, suggesting CTNN robust in very sparse tree-like regimes. In contrast, on protein benchmarks the differences are more significant, highlighting when each component becomes important. (i) Using a single canonical tree instead of a cover reduces edge coverage and increases distortion. This has limited impact on sparse molecules, where graph structures are tree-like, but it underperforms on proteins, where additional trees substantially improve coverage and distance preservation on average. (ii) Using an MPNN instead of TreeMPNN processes trees with MPNNs and reintroduces mnessage-psssnng inductive biases, contributing to oversmoothing and oversquashing, which leads to a consistent drop across most benchmarks, including molecular benchmarks. (iii) Using TreeRNN instead of TreeMPNN removes the MPNN on residual edges and has little effect on molecules, where few edges remain after MST extraction, but can degrade performance on denser proteins, where residual edges carry meaningful local connectivity. Overall, CTNN (full) matches or achieves the best performance across datasets. The performance gaps across ablations small molecular graphs, but increase protein graphs, indicating that the cover, tree encoder, and residual-edge message passing are primarily important in larger and denser regimes.
Sensitivity. We also conduct sensitivity analyses for different choices of number of trees, K, node labeler, TV, and penalty, r (Appendix E.T).. Increasing K yields consistent gains on proteins: edge coverage rises rapidly, average distortion decreases, and performance improves. These results align with our theory that only a small number of trees is needed for full coverage on sparse graphs and additional trees better capture original graph distances on average, resulting in increased performance for larger K. CTNN is also robust to node labeler zv: degree, closeness centrality, and BLISS (Junttila and Kaski, 2007). a canonical node labeler, are each close in performance. In the main experiments, we default to degree for its efficiency. Lastly, CTNN is also stable across the penalty т, where coverage, distortion, and accuracy follow similar trends across choices of T.
7 CONCLUSION
In this work, we developed the first theoretical analysis of sequence-basse based canonicalization for graphs, establishing that sequences distort distances and that single-rpreesentative approaches are constrained by the expressivity of their labelers. This analysis covered canonicalizations widely used in practice such as domain-driven sequences including SMILES (Goh et al. [017]] Hoona et al.) 2019) and primary protein sequences (Alley et al. 2019 Rao et 2019), learnable orderings based on GNNs and differentiable sorting (Niepert et 2016: Zhang et al. 2018), and algorithmic orderings that optimize bandwidth (Cuthill and McKee 1969 Diamant et al. 2023). Motivated by this analysis, we introduced Canonical Tree Cover Neural Networks, which construct canonical spanning- tree covers and leverage expressive tree encoders. CTNNS are provably invariant, better preserve graph distances, and are more expressive than sequence- based canonical GNNs. Empirically, CTNNS outperform invariant GNNs and canonicalization basclines on molecular and protein benchmarks.
Our coverage and expressivity guarantees rely on sparsity assumptions, and thus, characterizing CTNNs in dense regimes remains open. Despite the focused scope, CTNNs consistently maintain advantages in our experiments, highlighting the value of spanning tree covers over sequences. More broadly, our results underscore the importance of canonical representations that respect underlying graph geometry. By leveraging canonical tree covers, CTNNs offer an expressive, invariant, and efficient framework for learning on sparse graphs.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship under Award Number DE-SC0023112. It was also partially supported by National Science Foundation under Grants No. IIS 2212143 and IIS 2504090, and CAREER Grant No. ISS 184549, We thank the anonymous reviewers and members of the MLD3 and GEMS labs for their valuable feedback.
REFERENCES
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molccular fingerprints. In Advances in Neural Information Processing Systems, 2015.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for remi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference machine learning, pages 1725-1735. PMLR, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Francesco Di Giovanni, T Konstantin Rusch, Michael M Bronstein, Andreea Deac, Mare Lackenby, Siddhartha Mishra, and Petar Veličković. How does over-squahhing affect the power of gnns? Transactions on Machine Learning Research, 2024.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions in Machine Learning Research, 2023.
Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. In International Conference on Learning Representations, 2025.
Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade, Youngmin Ryou, and Seunghoon Hong. Revisiting random walks for learning graphs. In International Conference on Learning Representations, 2025.
Michael Ito, Danai Koutra, and Jenna Wiens. Random search neural networks for efficient and expressive graph learning. In Advances in Neural Information Processing Systems, 2025.
Benjamin Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, 21(90): 2020.
Sékou- Oumour Kaba, Amab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In International Conference on Machine Learning, pages 5554-115666 PMLR, 2023.
11

---

Published as a conference paper at ICLR 2026
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pages 2014 2023. PMLR, 2016.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. Proceedings the AAAI conference on artificial intelligence, volume 32, 2018.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In International Conference on Learning Representations, 2019.
Garrett B Goh, Nathan O Hodas, Charles Siegel, and Abhinav Vishnu. Smiles2vec: An interpretable general-purpose deep neural network for predicting chemical properties. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2017.
Shion Honda, Shoi Shi, and Hiroki R Ueda. Smiles transformer: Pre-trained molecular fingerprint for low data drug discovery. arXiv preprint
2019.
Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference Natural Language Processing (Volume I: Long Papers), pages 1556-1566, 2015.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of symbolic computation, 60:94-112, 2014.
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021.
Brendan D McKay, Practical graph isomorphism. Congressus Numerantium, 1981.
Seyone Chithrananda, Gabriel Grand, and Bharath Ramsundar. Chemberta: large-scale self- supervised pretraining for molecular property prediction. arXiv preprint arXiv:2010.09885, 2020.
Yuanqing Wang and Kyunghyun Cho. Non-convolutional graph neural networks. In Advances in Neural Information Processing Systems, 2024.
Yicheng Xiao, Lin Song, Jiangshan Wang, Siyu Song, Yixiao Ge, Xiu Li, Ying Shan, et al. Mambatree: Tree topology is all you need in state space model. Advances in Neural Information Processing Systems, volume 37, pages 75329 75329-75354, 2024.
Jin Matoušek. Lecture notes on metric embeddings. ETH Zürich, 2013.
Josep Díaz, Jordi Petit, and Maria Serna. A survey of graph layout problems. ACM Computing Surveys (CSUR), 34(3):313333)33 3366, 2002.
Pinar Heggernes, Daniel Meister, and Andrzej Proskurowski. Computing minimum distortion em- beddings into path for bipartite permutation graphs and threshold graphs. Theoretical Computer Science, 4 112:12214):12755
2011.
FF Dragan, E Köhler, and A Leitert. I Line-distortion, bandwidth and path- of a graph, swat 201 4: 14th scandinavian symposium and workshops on algorithm theory, july 2-4 2014. copenhagen, denmark. Lecture Notes in Computer Science, 8503:146-255 2014.
Joseph B Kruskal. On the shortest spanning subtree of graph and the traveling salesman problem. Proceedings of the American Mathematical society, 711::48-00, 1956.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448 455, 2003.
David Rogers and Mathew Hahn. extended-conneetio fingerprints. Journal of chemical information and modeling, 50(5):742-75,, 2010.
12

---

Published as a conference paper at ICLR 2026
Ethan C Alley, Grigory Khimulya, Surojit Biswas, Mohammed AlQuraishi, and George M Church. Unified rational protein engineering with sequence-bare based deep representation learning. Nature methods, (6(12):115--132, 2019.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Advances in Neural Information Processing Systems, 2022a.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 92):513-530, 2018.
Tim Kucera, Carlos Oliver, Dexiong Chen, and Karsten Borgwardt. Proteinshake: Building datasets and benchmarks for deep learning protein structures. In Advances in Neural Information Processing Systems, 2023.
Anwar Said, Roza Bayrak, Tyler Derr, Mudassir Shabbir, Daniel Moyer, Catie Chang, and Xenofon Koutsoukos. Neurograph: Benchmarks for graph machine learning in brain connectomics. In Advances in Neural Information Processing Systems, volume 36, pages 6509-6531, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1))657-6668 2022.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
Nathaniel Lee Diamant, Alex Tseng, Kangway V Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth. In International Conference on Machine Learning, pages 7939-7959. PMLR, 2023.
Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 135-149. SIAM, 2007.
Roshan Rao, Nicholas Bhattacharya, Neil Thomas, Yan Duan, Peter Chen, John Canny, Pieter Abbeel, and Yun Song. Evaluating protein transfer learning with tape. Advances neural information processing systems, 32, 2019.
Elizabeth Cuthill and James McKee. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference, pages 157-172, 1969.
David Bruce Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 296-303, 1996.
13

---

Published as a conference paper at ICLR 2026
A MATHEMATICAL PROOFS
A.1 DISTANCE DISTORTION UNDER SEQUENCE CANONICALIZATION
Corollary A.1 (Bandwidth lower-bounds sequence distortion). Ler G (V, F.) be a connected, unweighted graph with shortest-pate -att metric dg. Let upG)) == min, [aX(u [o a(v) be
the bandwidth of G. Then for every ordering n.
(GG) S (sea(T))
Proof. For an injective ordering V + {I,...,, m), define the sequence distance d (u, v) = (m(u) =(u)l- The two-sided distortion can be written
d (u, v)
max
D Daeq (T)
u
da v)
Seq (2,
min
ufe dc(u, v)
Define Pa(u, p)( = (u,)(u))) v) for u + v, so that (T)
max Rz. min
For any edge
{u, v} E, v) = hence (2, = (T( - (T)).. Therefore, max Pmr (ur(u, v) 2 max
TT( T(b) (T(T).
{a
Let v, be the two adjacent vertices in then d5eq (I, 3) = 1 while do (21, v) 2 so
1
min Pn (w v) S Px da(z, v)
S 1.
afo
Combining the two bounds proves the claim.
Daeg(a))
PTT min Px
(((T)
1 2 ((G),
A.2 EXPRESSIVE LIMITATIONS OF SEQUENCE CANONICALIZATION
Proposition A.2 (TV and fCanSeq are equally expressive). Let fCanSeq be a canonical se- quence-based model with universal Seeq and let TV be its labeling function. Then, fCanSeq RV.
Proof. Let G; = (V,, Fs, X:) for i E (1,2) with G1 # G2. Let V, + R be node labeler and define the augmented features X, = (X,, (v)). Assume the augmented multisets coincide:
: = ((x, : V23}.
Consider a single-sequence canonicalizer Caeq that outputs a permutation of V and the corresponding sequence of per-node feature vectors, without adding structural annotations and whose ordering rule deterministic function of {x, Joev (e.g., a stable sort by a fixed key in x, with deterministic tie-breaking depending only x.). Because the two graphs have the same multiset of keys, and the ordering depends solely on these keys, the resulting ordered lists of features are identical:
Caeq (GI, = Cson (G2, RV).
(If ties occur, the tie- tie-breaking is the same function of x; when two items share identical x, they are indistinguishable in the output sequence, any permutation within such ties yields the same feature sequence.) Hence, there exist nommisomoipiic graphs that collide under such Czeq that no feeg can distinguish, regardless of its expressivity.
Example (DGCNN). Let Cseq Sort be a stable sort that orders vertices by a fixed key computed from X, = (Xu, TV (w)) with deterministic breakia depending only on x, If (f(xx, Tv) o V1 [((x,, TV (v)) a Vall and G2 _ G2, then Sort(G1, my) the DGCNN setting where Ry ~ fMPNN provides the sort keys; the sort-based canonicalization cannot separate G and Go beyond what is already encoded in the augmented multiset.
Bort(G2, TV). This covers
14

---

Published as a conference paper at ICLR 2026
A.3 INVARIANT CANONICAL TREE NEURAL NETWORKS
We introduce notions of probabilistic invariance for random trees and covers, following definitions of probabilistic invariance for random walks (Kim al. 2025) and searches (Ito al. 2025).
Definition A.3 (Probabilistic invariance for random trees). Let A be randomized procedure that, on input graph G, outputs (labeled) spanning tree Ta( We say A is probabilistically invariant if for every pair of isomorphic graphs G x H with isomorphism т V(G)-V(HH)
(Ta(G)) _ Ta(H).
Definition A.4 (Probabilistic invariance for tree covers). Let output a (multi)set or sequence of trees (G( (I(() 1()- on G. We call A probabilistically invariant if for every isomorphism G _ H,
(T((G)) A Ta(H), where т acts elementwise on the sequence (and, for an unordered cover, equality in distribution is taken after forgetting order).
Lemma A.5 (MST is probabilistically invariant). Let G = -V, E) be an undirected graph. Let base weight (so w(g-e) = w(e) for all g E w... and let Ç: - (0, 1) assign i.i.d. continuous tie-breakers edges. Run Kruskal's 's algorithm (Algorithm) 2 with lexicographic keys k(e) = (w(e), ((e) and let XMST(G) = (eo...., be the resulting edge sequence. Then, for every g E Siv 9- XMST(G) XMST(g-G)
E +B be an isomorphism-invare
Proof. We prove by induction on that the f-th edge in Kruskal's sequence has the same pushforward conditional law on G and on g.G. For prefix x (eo,..... et-1) valid for Kruskal on G. let C(G;x) be the component partition (union-find state) after processing x. Define the admissible set
A(G;x) x) {e {u, v) E u,v lie in different components of C(G;x) }
and the frontier of minimum-base bassew admissible edges
F(G:x) == f c E A(;;)) w(c) = min e'Ex(G::)
w(ee)) }.
Under Kruskal with keys (w, <). the next edge e, is the unique minimizer ( over xG; Since the Ç's are i..d. continuous, conditional on the edge e, is uniform on FG::x).
Base case (t = 0). Here A(G = E and F(; = {e E E w(e) min w wee)). Because is caterphism-iivariinee F(g G; 0) g. F(G; The next edge is uniform the respective frontier; pushing this uniform forward by g yields
g XMST [G) _
XMST(g G)
Induction step.
Assume for some 1 2 0 that the prefixes satisfy
g. X XMsT(G)): t] _
XMst(g-G){: t).
Fix any realization x = (eo..... 11) of this prefix on G, and let gx = (g- eg.e...... , 1 be the corresponding prefix on g G. Relabeling preserves adjacency, henee components map as C(g-G; gx)) g- x(G;x) and therefore
A(g-G;gx]
g. A(G;)),
F(g = F(G;x).
Conditional on x, the next edge on G is uniform on F(G;x), x). Pushing this distribution forward by gives a uniform distribution on g- F FG; = F(g Big--;gee Gx)x), which is exactly the conditional law of the next edge on g- given gx:
g. (XMST (t) x) - XMMs(g-G)H gx.
Averaging over all realizations (which, by the induction hypothesis, have matching laws under G and g. after applying g to the prefix) yields
g. X (G)[t) _ XMsT(g-G)(t
By induction for t 0, O..,..., |V| we conclude g- XMsT(G) & XMST(g G). equivalently XMST(G) _ -1. XM)T(g-G).
15

---

Published as a conference paper at ICLR 2026
Theorem A.6 (Probabilistic invariance of BULDDCANNNIALLREECCVEEE
Fix any isomor- phism-invarian invariant node labeler TV (i.e., TV (g. u) = TV (u) for all E Siv) and define base edge
weights x (0) (u, v) - (mv(U) (v())). For k 2 let the iterative weights update be
(1) (e) + 1 E T (k+1) (e) TF
FE
T> 0,
where T(k) is the tree returned by KRUSKALMST (Algorithm 2 on (G, a exchangeable brebkeekers Ç - (0, 1) reused across all rounds. Ler (G)) (T T(K-1))
(k) with i..dd continuous
be the random sequence of trees produced by BUILDCANONICLTREECCO for every permutation 9 E S 9- T(G) & T(g.G).
(Algorithm ( Then,
Proof. We prove by induction & that, together with the evolving weights, the next tree is distribu- tionally equivariant under relabeling. Write the round-k weights as function of the history
(1 (G) = - (..,,.,.., (()-
and let g act on edge-indexed objects by (g. (e) = flg The induction claim
g. (G) - (g and g. (G) & (g.)))
(+t)
Base case 0). Since TV isomorhhim--ivarrian, so is TE
(0) (0)
TE (g. E) -0)
F (e). By
Lemma A.5 we have g- (G) T (g G). The update TE a +rl E T is
(1)
(0)
cannorphism-equivarinn hence g. (G) (T Thus +g holds for k = 0.
Induction step. Assume (gg holds for all < k. Couple the two runs on G and g.G by reusing the same exchangeable tie tie-breakers Ç. By the induction hypothesis, the joint law of the prefixes
(g- T( (G), (G),..., ((k-1) (G), g- 11 (1
equals the joint law of
(g)..,,.
(g-G))
Conditioned on these prefixes, the round-k Kruskal call on each graph uses (isomor- phism-cquivarian weights and the same iidd continuous tie-breakers, Lemma A.5 applies conditionally and yields
g. (I (G),) (G)) A (( (1
Averaging over the (matched) prefixes gives (G) _ ( G). Finally, the weight update [1(++] = (k) + - 1 E T(()} is isomorphism-equivee so ( (g(t Thus
holds for round k. By induction for k = 0, 1....,,4 we conclude g- T(G) _ T(g-G). n
Having established T(G) is probabilistically invariant, follows that [CTNN deterministic function on TG),, is also probabilistically invariant.
A.4 EXPECTED DISTORTION BOUNDS FOR CTNNS
Theorem A.7 (UST expected distortion), Let G be graph, and let be a uniform random spanning Iree of G. Denote by H (u, v) the random walk hitling time from Then,
DUST = max E [[dr(u, (oflu,)))/d(uu a.v
E[dr(u, v)] < (), + H(v,
Proof. Run Wilson's algorithm (Wilson 1996) rooted at v. The unique u-v path in the resulting uniform spanning tree has the same distribution the loop-erasure of simple random walk started at u and stopped upon first hitting v, LE(S S rol). Therefore.
dr v) d [LE(S(O r.])]]-
16

---

Published as a conference paper at ICLR 2026
Since loop-erasure only removes steps, |LE(S[0, Tol) S Tv. Taking expectations yields (f,r(u, v)] - E., [Te] H (u, v).
By symmetry, rooting Wilson's algorithm at u also gives
EldT(u, v)] - H (v,
Hence
Eldr(u, u)] < H), H(u, v) + H(, u)
Cue 2
2
A.S COVERAGE AND EXPRESSIVITY GUARANTEES VIA MST CANONICALIZATION
Lemma A.8 (Logarithmic spanning-tree cover). Let G (V, E) be a graph with m E and arboricity T(G), the minimum number of forests required to cover G. Fix any node labeler πv with max, ( (e) (e)- FE (e). Denote T (TT(k) Ik=0 ]k=0
K-1 as the of trees produced by CTNN.
If 2 ((G) In m iterations, the union of the MSTs covers all edges: U E(T())) = E.
Proof. Let TG)). By the definition of arboricity, there exists a partition of the edges into forests, E = 1 EFF)) For each j. fix (witness) spanning tree T₃ 2 Fj. Let U3 C E be the set of uncovered edges after & rounds and set := |0&| For each j. define Ux.j = U n E(F))) so that Σラ= Uk uy. By the pigeonhole principle, there exists jr with uk. 2 un T. Choose max. be min, be Then, for any k: 2
min (R) EE (e)
(K) max TE (e), eEUx
eEFVUR
i.., every seen edge is strictly more expensive than every unseen edge. Hence, minimizing total weight over spanning trees is equivalent to maximizing the number of unseen edges [T' n U (any exchange that replaces edges of Fy,, it achieves [Tt, n = ukj Therefore the MST (k) satisfies
edge by an unseen edge strictly reduces cost). Since Ty. contains all
(T(M) nUkl 2 uk. 2
T
Consequently,
uk+1 = uk (7 nU S (1-
1 7)
uk.
Iterating yields ux S uoo11 +) S me me-K/T Choosing 2 Thn gives uk < hence UK Ø and UK-o E(T(K)) E, as claimed.
Proposition A.9 (fMPNN & fCan'Tre..). Let fCauTree be CTNN satisfying Lemma 5.3 equipped with TV fMPNN. Then, VG, H, fCanTree (G) & (CanTroc(11) = fMPNN(() = {M) Moreover; 3G 전 H such that fCanTroe & fCanTree (H) while [MI fMINNN(H).
Proof. We prove the preorder claim and then strictness.
Step 1: fMPNN I SCanTroe. We prove stronger statement with deterministic distinguishability
fCanTree (G) fCan/ree (H) fMPNN (G) fMPNN
Let (G) denote the first tree in the canonical cover produced on and similarly (H). Since the cover is aggregated with injective multiset aggregator fagg. equality fCan'ree (G) franTren (H) implies equality the aggregated elements, and in particular we may restrict attention
to the contribution of the first tree.
17

---

Published as a conference paper at ICLR 2026
Fix graph G = (V, and spanning tree T (G) with root chosen canonically. For v E V. write Cr(v) for its children, pr(v) for its parent (if is not the root), and No(v) for its neighbors in G. A TreeMPNN update on the first tree can be written in the form
h = Sage ((x, : E Cr(e]B l (Xpr(e) & ((x.. : u E No((v) \ (Cr(V) (or())))B)
where Jagg is ietpuutttttooiiiviiiaa and injective on multisets. By construction, the multiset union ranges over exactly the neighbors of in G (partitioned into children, the parent, and residual neighbors), so no neighbor information is dropped. Importantly, however, the elements being aggregated are not necessarily the raw features x,² the first two groups correspond free-contextual representations. Concretely, child nodes contribute representations obtained by an injective map of their rooted subtrees below them, parent nodes contribute representations obtained by an injective map of the rooted tree above them, and the remaining non-tree neighbors contribute their original representations. Since compositions of injective functions are injective, the resulting TrecMPNN update at remains an injective function of the neighborhood multiset (now with context-dependent "colors"), and thus can simulate a standard injective message-passing update at v.
Now take any two graphs G, H and suppose Tren (G) SCan (H) for a fixed realization of the CTNN randomness. Restricting to the first tree as above, for every node e the corresponding per-node representations must coincide. Since the TreeMPNN update is composition of injective functions on multisets, equality of the TreeMPNN outputs forces equality of the underlying neighborhood multisets, which in turn implies equality of the corresponding MPNN outputs. This proves the
distributional implication [CanTree d SCanTree (H) + fMPNN = SMMNNN (H).
Step Strictness. We exhibit connected graphs G * H that are indistinguishable by MPNNs but separable by CTNNs. Let G' be the graph obtained by taking two (n- --ycles and connecting them by an additional single bridge edge, and let H be obtained by taking two n-cycles and joining them (without introducing new edges) by single bridge edge (Figure 6 6). These graphs are stably colored identically by 1-WL, so fMPNN(() = fMPNN (H).
Initialize node labels and edge weights in the CTNN construction, and consider the first MST extraction. By symmetry of the initialization, there is a unique valid MST in each graph obtained by deleting (from each eycle) the edge farthest from the bridge, yielding a spanning tree that preserves the bridge and breaks cycles at their most "distant" location. The resulting trees (G) and (H) are isomorphic. Consequently, a CTNN using a single canonical tree fails to distinguish and H.
Now assume K satisfies Lemma 5.3 the iterative reweighting scheme achieves full edge coverage across the cover. Consider the second round after reweighting edges missed at round 1. On G, there are exactly four possible MSTs round 2, all isomorphic to each other (they obtained by breaking, on each cycle, one of the two edges adjacent to the upweighted "missed" edge from round 1). On H, there are also four possible MSTs round 2, but they fall into two non-isomorphic types (as illustrated in Figure 6) Therefore the distributions of the second tree differ:
(G) - (H).
Since the tree encoder and the multiset aggregator fags are injective, a difference in distribution of one tree in the cover implies a difference in the distribution of the overall CTNN outputs, and thus
ScanTree (G) 1 SCantree
Combining with (G) = fMPNN (H) yields strictness: fMPNN * fCan'reee
To prove universality, we equip CTNNs with labels obtained from the canonical node labeler similar to the randomized anonymous labeling strategy used in (Wang and Cho 2024; Kim et al. 2025). Intuitively, canonical labels allow separation among all graphs up to isomorphism.
Definition A.10 (Canonical node labels). Let labeler, i.e., an isomorphism-invariant map TV V. R such that Ty assigns distinct labels to all nodes. Define the canonical ordering oN V + {I..... [V]] by sorting nodes by my: oF (i) argsort [i] We form canonically labeled node features X, := (Xo, (v)),, and use the same canonical labels for all trees in the CTNN cover. This yields a labeled cover
(V, F, X) and let Ty be a canonical node
(G)) = x) K-
18

---

Published as a conference paper at ICLR 2026
Lemma A.11 (Canonically labeled covers separating). Let K satisfy Lemma 5.3 that Up ((T( = F Assume sepurates all nodes the finite class 9 (so on is well- defined). Then the map -> (=(G) is separating up to isomorphism on
Proof. Let ox be the canonical ordering induced nv. Form the canonical edge multiset
Canon(G) {( (u),,,, oz (t)) (u,u) E Un (Tr(k) } [l (x)( oa (v) {u, B(G) B
where the equality uses Lemma 5.3
Since on is bijection, Canon(G)) is exactly the edge list of G expressed canonical node coordinates. Hence * H then Canon(G) o Canon( H), so the canonically labeled cover separates graphs in G up isomorphism.
Theorem A.12 (CTNN Universality). Let G be finite class of graphs. Assume: (i) K satisfies Lemma 5.3 B (ii) the tree encoder furee and aggregation fags are universal on their domains; and (iii)
is canonical node labeler thut separates all nodes G. Then for any continuous invariant function f : 9 T and any e >> O, there exists a CTNN such that
supl (CT GEO
S E.
Proof. By Lemma 5.3
the cover edges union to E(G); by Lemma A.11 the canonically labeled cover Tx is separating on G via Canon(G). Thus the invariant target factors as
f(G) F( ((T)) T (G)
for some continuous permutation-ing intpuuaatiooniivriaant F on multisets of tree representations and some on canonically labeled trees (e.g., any encoding that reproduces Canon(G)), By universality, ftre can approximate arbitrarily well on the finite support of observed canonically labeled trees, and fagg can approximate on finite multisets of tree representations. Because G is finite, the composition error is uniformly bounded by after suitable parameter choices.
19

---

Published as a conference paper at ICLR 2026
B ADDITIONAL MODEL DETAILS
B.1 ALGORITHMS FOR CANONICAL SPANNING- COVERS
Algorithm| Nottines our procedure for building a K-tree canonical cover. We initialize the edge labeler Th using the negative sum of endpoint degrees for each edge, which prioritizes edges incident construct MST with respect the current
high-degree nodes. For rounds / 0, ...... K edge weights using Kruskal's ' algorithm (Algorithm 2): edges are stably sorted (random tie- breebrkkkng)) and scanned in nondecreasing order, adding an edge if does not create cycle. After forming the tree T(O, we update the labeler to encourage coverage in subsequent rounds: edges selected in T( receive an additive penalty (controlled by 7) that increases their priority in the next MST. Finally, we choose canonical root as the tree center via the standard two-BFS routine (Algorithm B one BFS finds an endpoint of longest path, and second BFS from that endpoint finds the opposite endpoint; the center(s) of this path serve as the root. This procedure runs in O m log n) per round for the MST and (n) for root selection, and returns the K trees with their canonical roots.
Algorithm I: BUILDCANONICATTTEEECCCOO iterative MST cover with root selection
Input: Graph (V, F); node labeler æv R; iterations K; step t 0; tiny & > 0
Output: Tree cover [TT*) K'11 and roots = K1'
(Initialization)
foreach e (u, E E do
(Tv(()) (u) TV (v)) (0) +- (-v
/* base edge weights T (0)
+/
Draw i..d tie breakers ( E + (0, 1) (fixed across rounds)
So + Ø
/+ covered edges so far +/
+ 2.
for k = to K do
// 1) Minimum spanning tree with lexicographic keys
( <- KRUSKALMST e+ (w! {(e)))
T (U(tt)) Sa+1 M ((T(((
11 2) Canonical root: tree center via two BFS passes
[k] + TREECENTER(T")) TV)
RU (r(1))
// 3) Edge-weight update (penalize edges just used) foreach e do
if E (((()) then w (++1) w!
clse we (k+1) we
if [S44al= = [E then break
return (T,R)
Algorithm 2: KRUSKALMST with exchangeable tie-breakers
Input: Undirected graph (V, E); base edge weights w : + IR; breakera Ç E + (0, 1) i..d
Output: A spanning tree of G T' <- Ø: initialize disjoint-set D with MAKESET(U) for all e
if E then return T'
// I.i.d. continuous tie cie-breakers Ç ake keys distinct w.p. 1. Sort edges E by nondecreasing key k(e) = (w(e), ((e))
// Union-find tracks connected components of the partial forest.
for = {u, ta E the above order do
FiND (u) o (viD then
T -- U [e]: UNIONpl (u, if T V
then return 7'
return T'
20

---

Published as a conference paper at ICLR 2026
Algorithm 3: TREECENTER: root selection by two BFS passes
Input:
Tree (Vr, Er); tie breaker ranking on vertices (e.g.. (ITv, ID))
Output: Root r E Vr (a center of ()
Pick canonical start E Vr (minimizing the tic- b-bakkrkk;;;
BFS_ [FF__ARRHESTTTT 8);
BFS_ SFS__FARTHESTT,, u);
P unique path from
T;
PP odd then <- middle vertex
else r <- the nearer of the two middle vertices under the tie-breaker
return
B.2 ALGORITIMMS FOR RECURRENT TREE NEURAL NETWORKS
We provide discussion and implementation details of the recurrent tree neural network (Algorithm
Algorithm 4: BrTREELSTTFFRNVAR Bidirectional child-sum Tree-LSTM forward pass
Input : E R NxD node features; rooted tree - (V, Er, r) in COO form with (row, col) = (parent, child); arrays parent(u)), depth [o] E {O....,7.) 7.] Output:/ RN 2H, concat. of bottom-up up and top-down hidden states
Parameters: bottom-up Wio. E R 0x3H Uso E #R# W WW W-1
sou: Uiou: W,, U of matching shapes.
Init: ht ONNHH cº +0N h+ + ONXH. ct ONNH. Bucket nodes by depth: V2 + E V depth(u) for f O,...,
10 Bottom-up pass (children + parent): process parents from deepest to root. */
for T, 0 do
P Vi
// parents depth /
// edges with parent at depth & // Aggregate child states with scatter_ade (child-sum Jae = Σ
Eg + (ut E Er: u P}
Amm +- ONxH;
ham [1] += += (ut [p]
// Per-edge forgets and summed transformed cell contributions fnot + Tooto(Waah [W + U,h (ul) for (u+v) E
a -NNH:
[u] += EuEnueojE [o
// Node-level gates and updates all
for u E do
i. ū] splity (Wouuruu) + Uiouhamlu)) ito(i), o0)( u t+tanh(ū);
c'l fi lu]; [u[ueoo tanh [ul)
Top-down pass (parent >> children); propagate from root to leaves. */ for = to do
V + Vi
11 children at depth L
for E V do
pt parentll]
unique parent
i, ū] sW (Wbb Ugghh(1)))
i<-o(i,, o())(o), ūe lanh(();
+ Uk)+
c a O
return h concat(ht, )))
[N,2H]
21

---

Published as a conference paper at ICLR 2026
Parallel bottom-up top-down passes. For each canonical tree precompute three arrays: weidinn__tt_e_ tree (row=parent, col=child), parent[v] (unique parent), and depth[v] (dis- tance to root). The bidirectional forward pass runs in two levelwise sweeps that parallel across all nodes at the same depth. In the bottom-up pass (leaves - root), we bucket nodes by depth and scatter_add to implement the child-sum aggregator and edgewise forget contributions in single batched operation over all edges whose parent is at the current depth. In the top-down pass (root leaves), each node reads its parent's state via index_ seleect and applies the same batched gating. This organization avoids Python loops over edges and exploits segmented reductions on the GPU; only iterates over depth buckets. The forward pass can be efficiently batched across trees by treating the full batch as a collection of disjoint graphs, whose edges are stored in COO format.
Tree encoder. We implement bidirectional child-sum Tree-I.STM layer with two parameter sets (children-xparen and parentt>childreen). Each direction computes input/output/upddate gates via single linear projection that yields 3H channels per node and applies elementwise nonlinearity; edgewise forget gates are computed in parallel across all incident edges at a depth. The output feature per node is the concatenation of the two hidden states, making the layer stackable (we use residual/normaalzatiin in standard practice when beneficial).
Complexity and memory. Each direction runs in ((V)) time and O(VV)) memory for node states. For cover of K trees, the bidirectional layer cost is O(K In practice we batch trees along the sample dimension, so the work parallelizes across graphs and across trees.
22

---

Published as a conference paper at ICLR 2026
C DESIGN SPACE OF CANONICAL APPROACHES
As shown in Table 4 we organize canonicalization methods along six axes: (i) whether they rely on domain knowledge; (ii) the node labeler Ty: (iii) the edge labeler =g: (iv) the canonicalizer (ordering/selcction rule); (v) the induced representation (vector/sequeene/ttre))) and (vi) whether they use a set of canonical elements per graph (vs. a single representative), together with the downstream encoder. Table 4 situates common pipelines: domain-drive approaches (Fingerprint, SMILES, Primary Seq.) produce single canonical vector or sequence; graph-agnostic orderings (DGCNN/SSoPPoolngg RCM) also yield single sequence from graph-derived ranks. CTNN is the only approach that (a) uses an edge labeler to drive a coverage-aware canonicalization and (b) represents each graph domain-agnosie agnostic, preserves distances more faithfully than sequences, and increases expressivity by operating on a rather than single representative.
cover, a of canonical trees obtaining full coverage. This design is
Table Design space for graph canonicalization. "Set" indicates whether the method uses multiple canonical elements per graph (e.g., a cover of trees) rather than single canonicalization. "Domain Knowledge" indicates reliance on domain-speeifer specific information (e.g., chemistry rules).
Approuch
Kuowledge
Node Labeler
Edge Labeler
Canoniculizer
Representation
Fingerprint
Yes
NA Atom canonical ranks
NA
Handerafted chemical descriptors
Vector
No
MLP
SMILES
Yes
NA
Canonical SMILES algorithm
Sequence
No
RNN/TRSP
Primary Seq.
Yes
NA
NA
Identity
Soquence
RNN
DGCNN
No
MENN
No
Differetiable sort (SortPooling)
Sequence
No CNN
RCM
Degree Degree
No
Revense Cuthil McKee ordering
Sequence
No
RNN
CTNN (full)
Coverage-mware
Minimum Spanning Tree
Tree Cover
Yes
TresMPNN
D ADDITIONAL EXPERIMENTAL DETAILS
Training and Hyperparameter Selection. All models are trained by minimizing the binary cross-entropy loss on binary classification tasks and the negative likeelhoooo loss on multiclass classification tasks. Training is performed for maximum of 200 epochs with early stopping patience set to 15 epochs based on validation performance. The best-performing model on the validation set selected for evaluation on the test set. We perform grid search over the following hyperparameters for models where applicable:
Number of layers: [1, 3, 4)
Learning rate: (0.05, 0.01, 0.005, 0.001)
Batch size: (64, 128, 512, 1024)
Hidden dimension: (64, 128, 256]
Global pooling: (mean, sum, max)
Sequence model: (GRU, LSTM, Transformer! Number of sequences/trees K: (1,4, 8)
Coverage penalty (1, 2, 4)
All models are optimized using the Adam optimizer.
E EXTENDED RESULTS
We include additional analyses on (i) sensitivity to the node labeler TV. (ii) the coverage penalty т, and (iii) the number of trees K. We find CTNN to be robust to the choice my and т, while increasing K consistently increases coverage, reduces distortion, and improves performance. We further conduct sensitivity analyses to the choice of sequence models for SMILES, comparing performance when feeq is LSTM or transformer. Here, we find recurrence outperforms attention aligning with recent findings in RWNN studies. We lastly report preprocessing runtimes, confirming that CTNN's preprocessing is efficient and negligible with respect training times for all datasets.
23

---

Published as a conference paper at ICLR 2026
Edge Coverade
CTNN T=1
0.00
CINN T=1
0.0
Disoctoon
CTNN 1=2
CINN C=2
0.75
CTNN T=2
0.4
CTNN
2
2
2
Nember
Nember Spanning Trees
Namber Spomning
Figure 7: Sensitivity of CTNN to the number of trees K and coverage penalty on GO BIO. Coverage rises rapidly with K; distortion decreases monotonically with K; and performance improves. Trends similar across indicating robustness, with larger yielding slightly higher coverage at fixed K on proteins. Error bars denote standard deviation over samples.
Table 5: Median (min, max) test AUC on molecular datasets. We test CTNN with three node labelers Ty: Degree, Closeness Centrality, BLISS. CTNN is robust across all choices node labeler TT.
Small MoleculeNet Molecular Benchmarks (AUC 7)
Clin
SIDER
BACE
BBBP
Tox21
ToxCast
# Graphs
L.5K
1.5K
1.5K
2K
7.8K
8.5K
Avg.
33.6
23.9
16,4
17.1
Avg.
E
Node Labeler my
28.0
35.4
36.9
26.0
16.9
17.5
CTNN
Degree
84.7 (78.5,
65.8 (62.7,
79.3 85.0)
86.1
73.4
80.0 (75.4, $0.3)
CTNN
Centrality
85.5 (76.0, 88.2)
65.1 (62.6. 70.2)
79.5 (73.1, 84.4)
85.6 (77.1, 884))
73.0 (728. 74.7)
79.3 (76.5, $0.6)
CTNN
BLISS
84.7 (78.5, 91.0)
65.2 (61.5, 68.5)
79.4 (71 84.4)
86.7 (8055 9077
73.9 (69 79.2)
79.5 80.77.007)
E.1
SENSITIVITY ANALYSES
Sensitivity to K. We vary the number of trees K on GO BIO (Figure 7. Edge coverage increases rapidly with K, reaching full coverage by K-8 on GO BIO, consistent with the theory that only small number trees needed on sparse graphs. Distortion decreases monotonically as K grows, indicating that additional trees better preserve original graph distances. Task performance likewise improves with K, showing the practical value of the canonical tree cover.
Sensitivity to r. We test coverage penalty - = 2, on the same dataset (Figure 7 Across benchmarks, coverage, distortion, and accuracy follow similar trends for different т, indicating robustness to the choice of penalizer. For proteins. larger 7 yields higher coverage at a fixed K, as heavier penalties bias the MST toward previously unseen edges. Overall, CTNN's behavior is stable across T, while K primarily controls the ewerage-distortiinn -cccurrrn tradeoff.
Sensitivity to Ty. We evaluate CTNN with three choices of node labeler Ty on small-molecule benchmarks: Degree, Closeness Centrality, and BLISS (Table Across all datasets, performance is consistent across labelers, indicating that CTNN is robust to the choice of лV in this regime. This suggests that, once the canonical tree cover is constructed and processed with an expressive tree encoder, CTNN can recover strong performance even with inexpensive labelers. Accordingly, we default Degree our main experiments for efficiency, while Centrality or BLISS provide comparable results at higher preprocessing cost.
Sensitivity to feeq We evaluate the sensitivity of the sequence encoder fieg by comparing attention (Transformer) and recurrence (LSTMM) on canonical SMILES, and include graph Transformer (GT) that operates directly on molecular graphs (Table We report the analysis on the molecular benchmarks, whereas training analogous models on the larger, denser protein graphs did not converge within 24 hours. Results demonstrate that attention and recurrence perform comparably and are similar to the GT baseline. In all cases, however, these models underperform in comparison to CTNNs, which maintain clear performance advantage. This occurs since attention relies the sequential positional encoding and recurrence relies on the linear ordering, which both incur distortion and fail capture graph distances
SMILES
24

---

Published as a conference paper at ICLR 2026
Table 6: Transformers and LSTMs achieve comparable AUC across PCBA datasets, indicating that attention and recurrence perform similarly on the canonical sequence. GT's also perform comparably to both. Values are median (min, max) over splits. CTNNS outperform all models.
Molecular Benchmarks (AUC f)
Approach
Backbone
PCBA-1030
PCBA-1458
PCBA-4467
PCBA-5297
GT
Transformer
68.1 (67.9,
81.2 (8100, 81.5)
78.9 (7.8. 79.9)
87.7 88.2)
SMILES
Transformer
71.9 (21.5, 72.3)
84.4 (83.7, 84.5)
82.4 (81.5, 82.5)
88.9 (88.3, 89.4)
SMILES
LSTM
71.9 (71.2, 72.5)
84.9 (81.5, 85.9)
81.1 (80.0, 81.4)
90.2 (90.0, 90.3)
CTNN
TreeMPNN
80.6 (80.3, 81.2)
89.1 (88.0, 89.9)
86.8 (86.5, 87.4)
94.6 (94.2, 94.9)
E.2
RUNTIME ANALYSES
We report per- -er-graph preprocessing time for CTNNs when constructing K-8 trees with degree-based node labeler TT (w)= deg(v) (Table On molecular graphs the cost is in the milliseconds, and on protein graphs it is on the order of tenths of a second. In practice, this preprocessing is parallelizable across graphs and is computed once and reused over all training epochs, making a small fraction of end-to-end training time. Overall, CTNN preprocessing is efficient for the datasets considered.
Table 7: CTNN preprocessing time per graph to construct K-8 canonical spanning trees using degree labeler (TTy()) deg(v)). We report dataset sizes and average graph statisties; times (seconds) are averaged over all graphs. Overall, CTNN preprocessing is efficient across all datasets.
Dataset
# Graphs
Avg. [V]
Avg. [E]
Avg. deg(v)
Time (sec)
PCBA-1030
160K
24.3
26.2
2.2
0,004
GO MOL
32K
250.1
687.5
5.4
0.093
NeuroGraph
7K
400.0
7000.29
17.6
0.127
E.3 UST vs. CTNN DISTORTION
The distortion bound in Theorem A.7 is stated for uniform spanning trees (USTs), whereas CTNN constructs coverage-aware minimum spanning trees (MSTs) from different, non-uniform distribution. USTs are used in the theory as a well-understood reference distribution to motivate why random tree covers can achieve low distortion. Empirically, however, we find that our coverage-aware MST scheme achieves even lower distortion than USTs on the datasets we consider. Table 8 compares the shortest-pan paatestt-pthhhhe distortion for UST's and CTNN (degree labeler, 7=1) on PCBA-1030 as the number of trees K increases. CTNN consistently attains smaller average distortion and variance than USTs for all K. This advantage is plausibly due to the coverage-aware construction, which explicitly favors edges that have not appeared in earlier trees, leading to tree covers that better preserve graph distances than independent UST samples, which have no bias toward uncovered edges. These results provide quantitative evidence that the practical CTNN tree distribution inherits and can even improve upon the low distorton behavior suggested by the UST analysis.
Table 8: Distortion as the number of trees K increases on PCBA-1030 for uniform spanning trees (UST) and CTNN, using a fearee-based node labeler and 7=1. We report mean + standard deviation distortion over graphs.
PCBA-1030 Distortion
K=1
K=2
K=4
K=8
UST
5.58 1.23
4.49
1.16
3.57 0.70
2.92
0.45
CTNN
5.10 1 0.45
3.08
0.30
2.26 1 0.42
2.13 1 0.26
25

---

Published as a conference paper at ICLR 2026
E.4 EVALUATION ON
BENCHMARKS
We ran additional experiments on a non-molecular and non-protein benchmark (Table Our main evaluation focuses on molecular and protein graph classification tasks because canonicalization is widely adopted and frequently used in practice in these domains. To demonstrate that our approach applicable beyond these biochemical domains, we additionally evaluate CTNN on a brain graph classification benchmark from NeuroGraph (Said et al. 2023). Across this benchmark, CTNN obtains the best performance compared to standard MPNN (GIN) and canonicalization baselines (RCM and DGCNN). These results demonstrate CTNNs' applicability to domains in which canonicalization not yet widely adopted.
Table 9: Median (min, max) accuracy of GIN, RCM, DGCNN, and CTNN on the NeuroGraph Activity prediction benchmark. CTNN obtains the best performance across baselines.
NeuroGraph-AAcfiitty
# Graphs
7K
Avg.
V
400
Avg. [E]
7000
Avg.
deg
18.0
Metric
ACC f
GIN
85.4 (85.4, 86.1)
RCM
91.5 (91.3, 92.5)
DGCNN
91.9 (91.9, 92.5)
CTNN
94.1 (94.0, 94.2)
26


Reviews:
[{"review_id": "3dZhMG4uKj", "reviewer": "Reviewer_1KKi", "summary": "This paper identifies limitations in existing graph canonicalization methods, particularly those that flatten graphs into sequences, arguing they introduce significant distance distortion and are bottlenecked by the expressivity of their node labelers. To address this, the authors propose Canonical Tree Cover Neural Networks (CTNNs), an invariant framework that represents each graph as a small set of canonical spanning trees. This tree cover is generated using an iterative, coverage-aware Minimum Spanning Tree (MST) algorithm. Each tree is then processed by an expressive tree encoder, and the results are aggregated. The authors provide theoretical contributions showing their method is (probabilistically) invariant, better preserves graph distances than sequence-based methods, and is strictly more expressive than both MPNNs and sequence canonicalization. Empirically, the paper demonstrates that CTNNs outperform standard GNNs, sampling approaches, and canonical sequence baselines on several graph classification benchmarks.", "questions": "See in Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized and clearly articulates the limitations of existing methods.\n    \n2. The proposed CTNN framework is a novel and intuitive solution that aims to tackle the issues by replacing the single-sequence representation with a more structurally tree cover.\n    \n3. The claims are supported by a combination of theoretical analysis and robust empirical results across diverse benchmarks.", "weaknesses": "1.  The term \"canonicalization\" is misleading. The method is not deterministic; it is a \"probabilistically invariant sampling\" algorithm that relies on random tie-breaking, making it conceptually closer to the sampling-based (e.g., RWNN) paradigms it critiques.\n2.  There is a gap between the theoretical requirement for invariance (taking an expectation $\\mathbb{E}[\\cdot]$ over all possible random choices) and the practical implementation (aggregating a small sample of $K=4$ or $K=8$ trees). This small $K$ may be insufficient to approximate the expectation, leading to unstable representations for the same graph across different runs.\n3.  A key theoretical justification (Thm 5.2) for the method's low distance distortion is based on Uniform Spanning Trees (USTs). However, the proposed algorithm (Alg 1) generates Minimum Spanning Trees (MSTs) from a different, non-uniform distribution, meaning the core distortion theory does not actually apply to the method as practiced.\n4.  For highly regular graphs (e.g., where all nodes have the same degree $\\pi_V$, resulting in identical initial edge weights ${\\pi}_{E}^{(0)}$), the selection of the MST in Algorithm 1 will be determined entirely by the random tie-breaker $\\zeta$. This suggests the process is not learning a \"canonical\" structure but rather performing a structured random decomposition of the graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CeNvL5kOfo", "reviewer": "Reviewer_3g7j", "summary": "The paper introduces Canonical Tree Cover Neural Networks (CTNNs), a new framework for graph representation learning that generalizes canonical sequence models by replacing a single canonical representation with a set of canonical spanning trees (MSTs).\nEach tree is processed with a recurrent tree encoder, and message passing is applied over residual (non-tree) edges to capture local connectivity missed by individual trees.\nThe authors further provide:\n(1) Theoretical results on probabilistic invariance and universality of CTNNs,\n(2) Distortion and expressivity bounds comparing CTNNs to sequence-based canonicalization,\n(3) Empirical evaluations on molecular and protein benchmarks, demonstrating improved performance.", "questions": "(1) Considering the conceptual resemblance between CTNN and Neural Trees for Learning on Graphs (Talak et al., 2021), both of which convert graphs into hierarchical tree representations for recursive message aggregation, it would be valuable for the authors to include a direct conceptual or empirical comparison in the paper.\n(2) Why were GNNs with proven higher expressivity than 1-WL (e.g., k-WL GNNs like GSN, or subgraph GNNs like PPGN) not included as baselines? These seem like the most relevant competitors for a method claiming to surpass 1-WL limitations.\n(3) Given that the paper's core motivation is to overcome the expressivity limits of 1-WL, why were synthetic benchmarks (like CSL or EXP) completely avoided? These datasets are specifically designed to demonstrate 1-WL failures and would be the clearest way to validate the superior expressivity of CTNN.\n(4) Given that recursive encoders (e.g., Tree-LSTM) are inherently order- and hierarchy-sensitive, how robust is CTNN to different root node selections or unbalanced tree shapes? Do the authors have any empirical results on performance variance under random root permutations or tree rebalancing?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "(1) The paper presents a structured extension of canonical graph neural networks by introducing Canonical Tree Cover Neural Networks (CTNNs), which replace a single canonical ordering with a collection of spanning trees. The proposed method alleviates the structural distortion and expressivity limitations commonly observed in sequence-based canonicalization approaches.\n(2) The paper provides a series of theoretical analyses, including probabilistic invariance, expected distortion bounds, and expressivity results, demonstrating a well-grounded theoretical foundation.", "weaknesses": "(1) Although the paper presents CTNN as an innovation grounded in canonicalization, its underlying modeling paradigm bears conceptual similarity to prior tree-structured graph neural networks (GNNs), such as Neural Trees for Learning on Graphs (Talak et al., 2021). Both approaches transform a graph into a hierarchy of trees for recursive message aggregation. As a result, the conceptual novelty of CTNN appears limited. \n(2) Dependence on root and tree structure without theoretical guarantees. The model’s expressive capacity and stability appear highly sensitive to the root selection and tree shape. Since the recursive encoder (e.g., Tree-LSTM) is order- and hierarchy-dependent, different rootings or unbalanced spanning trees may yield substantially different representations. The paper currently provides no theoretical or empirical analysis of this effect.\n(3) Dependency on the Initial Labeler ${\\pi}_{V}$: The paper criticizes sequence methods (Prop 3.3) for being limited by ${\\pi}_{V}$'s expressivity. However, CTNN's own tree generation (Alg. 1) is also initialized by ${\\pi}_{V}$. If ${\\pi}_{V}$ is weak (e.g., cannot distinguish 1-WL-equivalent nodes), the initial MST selection will also be \"blind.\n(4) Missing/Failed Key Baselines: A core claim is surpassing MPNN expressivity. A fair comparison requires stronger baselines like k-WL GNNs or Graph Transformers (GT). The paper includes GT, but it timed out (OOT) on all protein datasets where CTNN excelled. The lack of results from this key high-expressivity baseline makes CTNN's victory less convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fZ37LNo6pY", "reviewer": "Reviewer_ZKRx", "summary": "This paper critiques single-sequence canonicalization methods in graph learning for causing distance distortion and having limited expressivity. To address this, it introduces Canonical Tree Cover Neural Networks (CTNNs), a framework that represents graphs using a small set of canonical spanning trees that cover all edges. Each tree is processed by a tree encoder, and the results are aggregated. The authors provide theoretical guarantees that CTNNs are probabilistically invariant, better preserve distances, and are more expressive than sequence-based methods. Empirically, CTNNs are shown to outperform standard GNNs, sampling approaches, and canonical sequence baselines on graph classification benchmarks.", "questions": "See in Weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses a fundamental problem in graph learning: the trade-off between expressivity and isomorphism invariance.\n    \n2. It proposes a framework (CTNN) that uses a tree cover to represent graph structure, addressing the identified high distortion of sequence-based methods.\n    \n3. Theoretical analysis and empirical results across multiple benchmarks provide support.", "weaknesses": "1.  The experimental setup (e.g., using $\\tau=1$) likely fails to meet the theoretical condition required by Lemma 5.3 for guaranteed logarithmic edge coverage. This gap between theory and practice undermines the paper's claims about efficient coverage and the universality (Thm 5.5) that depends on it.\n\n2.  The empirical evaluation is missing the most critical baselines. As a method based on subgraph representations, CTNN must be compared against other state-of-the-art, subgraph-based GNNs (like GSN or ESAN) that also achieve high expressivity, not just standard 1-WL models.\n\n3.  The universality claim (Thm 5.5) is trivial and not a unique advantage. This property holds for any model that completely decomposes a graph and uses universal encoders and aggregators. The paper does not sufficiently prove the *efficiency* of CTNN's universality (i.e., that it can be achieved with a small $K$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4KskgZ6gMd", "reviewer": "Reviewer_vjKg", "summary": "This paper proposes Canonical Tree Cover Neural Networks (CTNNs) as a new approach to graph canonicalization. Instead of flattening graphs into a single sequence (which causes distortion and expressivity loss), CTNNs construct a canonical spanning tree cover and process each tree with expressive tree encoders, aggregating their outputs into an invariant representation. The authors provide theoretical results (distance preservation, expressivity beyond 1-WL, universality under certain conditions) and empirical evaluation on molecular and protein benchmarks, showing improvements over message-passing GNNs, sampling approaches, and sequence canonicalization baselines.", "questions": "I will raise my score if the authors address W2.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. The paper clearly explains the limitations of sequence canonicalization, illustrating them with intuitive examples such as star graphs.\n2. It introduces a tree cover method that better preserves structural information and invariance, supported by formal analyses of distortion, expressivity, and coverage guarantees.\n3. On multiple benchmarks, CTNNs consistently surpass strong baselines, achieving notable gains on molecular tasks and competitive results on protein tasks.", "weaknesses": "1. The key idea (use a set of trees instead of one sequence) feels like an incremental extension rather than a major conceptual advance. Many theoretical results (universality, expressivity boost by multiple views, distortion comparisons) are natural consequences of existing work. Frequent use of terms like “strictly more expressive,” “provably invariant,” and “universal” gives an impression of overselling. Some proofs (e.g., universality of CTNNs) rely on standard functional approximation arguments, which are not truly new.\n\n2. The guarantees, such as using only a logarithmic number of trees and achieving low distortion, mainly hold for sparse graphs. Dense graphs, such as proteins, show weaker improvements and less favorable theoretical bounds. Although the paper claims MST construction is efficient, it does not provide runtime or memory benchmarks. For dense graphs, the (O(Km \\log n)) cost could be significant, and the preprocessing advantage is asserted but not supported with quantitative evidence.\n\n3. Improvements on molecular benchmarks are often only 1–2 AUC points. On protein tasks, performance is inconsistent, sometimes close to baselines. No large-scale or real-world datasets beyond the standard benchmarks are tested. The ablation studies show predictable drops (removing key components hurts), but provide little insight into why certain parts matter. No analysis of failure cases or adversarial graph structures.\n\n4. While molecular and protein benchmarks are reasonable, the method is not shown on social networks, knowledge graphs, or large heterogeneous graphs. This raises questions about generality beyond biochemical datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)