PlanE: Representation Learning over Planar Graphs
Authors: Radoslav Dimitrov
Zeyang Zhao
Ralph Abboud
Ismail Ilkan Ceylan
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Representation Learning; Planar Graphs; Graph Property Prediction
TL;DR: We propose PlanE, a framework for planar graph representation learning inspired by classical algorithms. PlanE can learn complete invariants over planar graphs, is highly scalable, and achieves state-of-the-art results on multiple planar benchmarks.

Abstract: Graph neural networks are prominent models for representation learning over graphs, where the idea is to iteratively compute representations of nodes of an input graph through a series of transformations in such a way that the learned graph function is isomorphism-invariant on graphs, which makes the learned representations graph invariants. On the other hand, it is well-known that graph invariants learned by these class of models are incomplete: there are pairs of non-isomorphic graphs which cannot be distinguished by standard graph neural networks. This is unsurprising given the computational difficulty of graph isomorphism testing on general graphs, but the situation begs to differ for special graph classes, for which efficient graph isomorphism testing algorithms are known, such as planar graphs. The goal of this work is to design architectures for efficiently learning complete invariants of planar graphs. Inspired by the classical planar graph isomorphism algorithm of Hopcroft and Tarjan, we propose PlanE as a framework for planar representation learning. PlanE includes architectures which can learn complete invariants over planar graphs while remaining practically scalable. We empirically validate the strong performance of the resulting model architectures on well-known planar graph benchmarks, achieving multiple state-of-the-art results.

PlanE: Representation Learning over Planar Graphs
Radoslav Dimitrov"1
Zeyang Zhao"t Department Computer Science
Department of Computer Science University of Oxford contact@rrddslav111 com
University of Oxford zeyzang. zhao@cs..o. ox ac uk
Ralph Abboud
Ismail ilkan Ceylan
Department of Computer Science
Department of Computer Science
University Oxford ralph@ralphabb..c ai
University of Oxford
ismail. ceylanecs ox. ac uk
Abstract
Graph neural networks iteratively compute representations of nodes of input graph through series of transformations in such way that the learned graph function is isomorphism invariant graphs, which makes the learned representa- tions graph invariants. On the other hand, it is well-known that graph invariants learned by these class of models are incomplete: there pairs of non-isomorphic graphs which cannot be distinguished by standard graph neural networks. This is unsurprising given the computational difficulty of graph isomorphism testing on general graphs, but the situation begs to differ for special graph classes, for which efficient graph isomorphism testing algorithms The goal of this work to design architectures for efficiently learning complete invariants of planar graphs. Inspired by the classical planar graph isomorphism algorithm of Hopcroft and Tarjan, we propose PLANE as framework for planar representation learning. PLANE includes architectures which can learn complete invariants over planar graphs while remaining practically scalable. We validate the strong performance of PLANE architectures on various planar graph benchmarks.
known, such planar graphs.
1 Introduction
Graphs are used for representing relational data in a wide range of domains, including physical chemical [1 (36], and biological [21] 68) systems, which led to increasing interest in machine learning (ML) over graphs. Graph neural networks (GNNs) 23 [1 have become prominent for graph ML for wide range of tasks, owing their capacity to explicitly encode desirable relational nodes an input graph through series of transformations in such way that the learned graph-level function represents a graph invariant: a property of graphs which preserved under all isomorphic transformations.
53
inductive biases [6). GNNs iteratively compute representations
Learning functions on graphs is challenging for various reasons, particularly since the learning problem contains the infamous graph isomorphism problem, for which the best known algorithm, given in breakthrough result by Babai 4 runs in guasi-polynomial time. A large class of GNNs can thus only learn incomplete graph invariants for scalablity purposes. In fact, standard GNNs are known to be at most as expressive the 1 1-dimensional Weisfeiler-Lemaa algorithm (1-WL) [9] in terms of distinguishing power 45 63) There are simple non-isomorphic pairs of graphs, such as pair shown in Figure which cannot be distinguished by 1-WL and by large class of GNNs. This
'This work is largely conducted while these authors were still affiliated with the University of Oxford.
I "qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

limitation motivated a large body of work aiming to explain and overcome the expressiveness barrier of these architectures
[5] 37 42
43 45
50]
The expressiveness limitations of standard GNNs already apply on pla- nar graphs, since, e-g., the graphs G1 and G2 from Figure [ are planar. There are, however, efficient and complete graph isomorphism testing algorithms for planar graphs [28 29 which motivates an aligned de- sign of dedicated architectures with better properties over planar graphs. Building on this idea, we propose architectures for efficiently learning complete invariants over planar graphs.
G₁
G2
Figure 1: Two graphs in- distinguishable by 1-WL.
Planar structures appear, c.g., in road networks 622 circuit design [ and most importantly, in biochemistry (54). Molecules are commonly encoded planar graphs with node and edge types, shown in Figure 2 which enables the application of many graph MI. architectures on biochemistry tasks, For example, all molecule datasets in OGBG [33] consist of planar graphs. Biochemistry has been a very important application domain for both classical graph isomorphism testing and for graph ML. By designing architectures for learning complete invariants over planar graphs, our work unlocks the full potential of both these domains.
Figure 2: Acid anhy- dride as a planar graph.
The contributions of this work can be summarized as follows:
Building on the classical literature, we introduce PLANE as framework for learning isomorphism complete invariant functions over planar graphs and derive the BASEPLANE architecture (Sec- tion 5). We prove that BASEPLANE is a scalable, complete learning algorithm on planar graphs: BASE can distinguish any pair of non-isomorphic planar graphs (Section 6)
We conduct an empirical analysis for BASEPLANE evaluating its expressive power on three tasks (Section 7.J). and validating its performance on real-world graph classification (Section 7.2) and regression benchmarks (Section 7.3 and 7.4). The empirical results support the presented theory, and also yield multiple state-of the--ar results for BASEPLANE on molecular datasets.
The proofs and additional experimental details are delegated to the appendix of this paper.
A primer on graphs, invariants, and graph neural networks
Graphs. Consider simple, undirected graphs G (V, E, E,C). where V is a of nodes, V is a set of edges, and Ç V + C is (coloring) function. If the range of this map is C = Rdd we refer to it as a dd-dimensional feature map. A graph is connected if there is path between any two nodes and disconnected otherwise. A graph is biconnected if it cannot become disconnected by removing any single node. A graph is triconnected two nodes. graph is planar if it can be drawn on a plane such that no two edges intersect.
the graph cannot become disconnected by removing any
Components. A biconnected component of a graph G is a maximal biconnected subgraph. Any connected graph G can be efficiently decomposed into tree of biconnected components called the Block- Chock-Cuttin tree of G [30], which we denote as BLOCKCUT(G). The blocks are attached to each other at shared nodes called cut nodes. A triconnected component of graph G is a maximal triconnected subgraph. Triconnected components of a graph G can also be compiled (very efficiently (27]) into a tree, known the SPQR tree [16), which we denote as SPQR(G). Given graph G, we denote by o the set of all SPQR components of G (i.e., nodes of SPQR (G)), and by c the set of all biconnected components of G. Moreover, we denote by oς the set of all SPQR components of G where appears as node, and by G the set of all biconnected components of G where u appears as a node.
Labeled trees. We sometimes refer to rooted, undirected, labeled trees r = (V, E, where the canonical root node is given as one of tree's centroids: a node with the property that none of its branches contains more than half of the other nodes. We denote by ROOT(I') the canonical root of I, and define the depth d, of a node u in the tree as the node's 's minimal distance from the canonical root. The children of node u is the set x(u) {ul(u, v) E, d, = d, 1). The descendants of node
'Graph isomorphism first appears in the chemical documentation literature 49 as the problem of matching molecular graph against database of such graphs; see, e.g., Grohe and Schweitzer 266 for recent survey.

---

is given by set of all nodes reachable from through a path of length & 2 0 such that the node at position j + 1 has one more depth than the node at position j. for every 0 S j S k. Given rooted tree I and node the subtree of I rooted at node u is the tree induced by the descendants of u, which we donote by r,. For technical convenience, we allow the induced subtree r, of a node u even if u does not appear in the tree r, in which case r, is the empty tree.
Node and graph invariants. An isomorphism from graph G GV(VE to a graph G' C" is bijection f V + V such that ((u) = ((((w) for all u E V. and (u, E E if and only if ( associates with each graph G = E.) function E(G) defined on V such that for all graphs G and G², all isomorphisms f from G to G², and all nodes u E V. holds that ((G)(u) = E(G') (f))). A graph invariant is function& & defined on graphs such that E(G) E(G') for all isomorphic graphs G and G'. We can derive graph invariant & from node invariant 5 by mapping each graph G the multiset (()
E E", for all u, v E V. A node invariant is a function & that
E VB. We say that graph invariant & distinguishes two graphs G' and G' if E(G) * ( If a graph invariant& { distinguishes G". the converse also holds, then & is complete graph invariant. We can speak of (in)completeness of invariants on special classes of graphs, e.g. I-WL computes an incomplete invariant on general graphs, but it is well-known to compute a complete invariant on trees 24
and G' then there no isomorphism from G to
Message passing neural networks. A vast majority of GNNs are instances of message passing neural networks (MPNNs) (22. Given an imput graph G = (V, E), an MPNN sets, for each node
E V, an initial node representation ((u) = ha and iteratively computes representations a fixed number of layers 0 S l S L as:
(E) for
h (f+1) = ( 10h (h. u (ueN))))
where ø and s are respectively update and aggregation functions, and N₂ is the neighborhood of u. Node representations can be pooled to obtain graph-level embeddings by, e.g., summing all node embeddings. We denote by z(L) the resulting graph-level embeddings. In this case, an MPNN can be viewed as an encoder that maps each graph G to a representation 2g computing graph invariant.
3 Related work
The expressive power of MPNNs is upper bounded by 1-WL 45 63)
terms of distinguishing
graphs, and by the logic C² in terms of capturing functions over graphs (5). motivating a body of work to improve on these bounds. One notable direction has been to enrich node features with unique
node identifiers 42 65), random discrete colors [1). or random noisy dimensions 50) Another
line of work proposes higher-order architectures 37 45 based higher-order tensors 44 or
a higher-order form of message passing [45), which typically align with a k-diiensional WL. tes
for some k > 1. Higher-order architectures are not scalable, and most existing models are upper bounded by 2-WL (or, oblivious 3-WL.. Another body of work is based on sub-graph sampling 79 56). with pre-set sub-graphs used within model computations. These approaches can yield substantial expressiveness improvements, but they rely on manual sub-graph selection, and require running expensive pre-computations. Finally, MPNNs have been extended to incorporate other graph kernels, i.c., shortest paths [2] 64], random walks 46 47 and nested color refinement [67]
The bottleneck limiting the expressiveness of MPNNs is the implicit need to perform graph isomor- phism checking, which is challenging in the general case. However, there are classes of graphs, such as planar graphs, with efficient and complete isomorphism algorithms, thus eliminating this bottleneck. For planar graphs, the first complete algorithm for isomorphism testing was presented by
Kukluk et al. [1 presented an algorithm, which we refer to as KHC, that is more suitable for practical applications, and that we align with in our work. As result of this alignment, our approach is the first. efficient and complete learning algorithm on planar graphs. Observe that 3-WL (or, oblivious 4-WL) also known to be complete on planar graphs [38), but this algorithm is far from being scalable (35] and as a result there is no neural, learnable version implemented. By contrast, our architecture learns representations of efficiently computed components and uses these to obtain refined representations. Our approach extends the inductive biases of MPNNs based on structures, such as biconnected components, which are recently noted to be beneficial in the literature [66].
Hopcroft and Tarjan (29), and was followed up by a series of algorithms 10 19
28 52
We write k- &-WL to refer to the folklore (more standard) version of the algorithm following Grohe 225
3

---

4 A practical planar isomorphism algorithm
The idea behind the KHC algorithm is to compute a canonical code for planar graphs, allowing us to reduce the problem of isomorphism testing checking whether the codes of the respective graphs are equal. Importantly, we do not use the codes generated by KHC in our model, and view codes as an abstraction through which alignment with KHC is later proven. Formally, we can define code as a string over the alphabet Σ U N: for each graph, the KHC algorithm computes codes for various components resulting from decompositions, and gradually builds code representation for the graph. For readability, we allow reserved symbols "(", ")" and "," in the generated codes. We present an overview of KHC and refer to Kukluk al. [1 for details. We can assume that the planar graphs are connected, as the algorithm can be extended to disconnected graphs by independently computing the codes for each of the components, and then concatenating them in their lexicographical order.
Generating a code for the the graph. Given a connected planar graph decomposes G' into Block-Cut tree I BLOCKCUT(G). Every node E 8 is either cut node of G. or a virtual node associated with a biconnected component of G. KHC iteratively removes the leaf nodes of 5 as follows: if u is leaf node associated with biconnected component B, KHC uses a subprocedure BICODE to compute the canonical code CODE (6.) ) = BICODE( [)) and removes from the tree; otherwise, if the leaf node is cut node, KHC overrides the initial code CODE( ())) using an aggregate code of the removed biconnected components in which occurs node. This procedure continues until there is single node left, and the code for this remaining node is taken as the code of the entire connected graph. This process yields a complete graph invariant. Conceptually, it is more convenient for our purposes reformulate this procedure as follows: we first canonically root 6, and then code the subtrees in a bottom-up procedure. Specifically, we iteratively generate codes for subtrees and the final code for G is then simply the code of 6 (ooo)())-
(V, E, S), KHC
Generating a code for biconnected components. KHC relies on a subprocedure BICODE to compute code, given biconnected planar graph B. Specifically, it uses the SPQR tree y SPQR(B) (B) which uniquely decomposes a biconnected component into a tree with virtual nodes of one of four types: S for cycle graphs, P for two-node dipole graphs, Q for graph that has single edge, and finally R for a triconnected component that is not a dipole or a cycle. We first generate codes for the induced sub-graphs based on these virtual nodes. Then the SPQR tree is canonically rooted, and similarly to the procedure on the Block-Cut tree, we iteratively build codes for the subtrees of y in bottom-up fashion. Due to the simpler structure of the SPQR tree, instead of making overrides, the recursive code generation is done by prepending a number O(C, C") for parent SPQR tree node C' and each C' x(C). This number is generated based on the way C and C" are connected in B. Generating codes for the virtual P and Q nodes is trivial. For S nodes, we use the lexicographically smallest ordering of the cycle, and concatenate the individual node codes. However, for R nodes we require a more complex procedure and this is done using Weinberg's 's algorithm as a subroutine.
Generating code for triconnected components. Whitney (60) has shown that triconnected graphs have only two planar embeddings, and Weinberg introduced an algorithm that computes canonical code for triconnected planar graphs [58] which call TRICODE. This code is used as one of the building blocks of the KHC algorithm and can be extended to labeled triconnected planar graphs, which is essential for our purposes. Weinberg's 's algorithm (58) generates canonical order for a triconnected component T, by traversing all the edges in both directions via a walk. Let w be the sequence of visited nodes in this particular walk and write wi]] to denote i-th node in it. This walk is then used to generate sequence of same length. that corresponds to the order in which we first visit the nodes: for each node u w[i] that occurs in the walk, we set k[i] = + [n]j]] i < i) if w[i] is the first occurrence of u. or re[i] = k[min [j w = w[H otherwise. For example, the walk w (V1, 03, 02, V3, 21) yields x- = 2, 2, 1). Given such a walk of length k and a corresponding sequence K, we compute the following canonical code: TRICODE(T) (x(1), CODE((([[]] (t)).....
5 PLANE: Representation learning over planar graphs
KHC generates a unique code for every planar graph a hierarchical manner based on the decompo- sitions. Our framework aligns with this algorithm: given an input graph G = (V, E, C). PLANE first computes the BL. and SPQR trees (A- - C), and then learns representations for the nodes, the components, and the whole graph (D G), as illustrated in Figure 3

---

A. Input Graph
G. Update
o( oO C
Neighbors
Readout
SPQR
Bi-comnected
Cut Node
B. Block-Cut Tree
F. CutEne
C. SPQR Trees
E. BiEne
D. TriEnc
O Targel Node
Neighbor Node
Cul Node
Biconmecied Compunent
SPQR Component
Figure 3: Given an imput graph (A) PlanE computes the BLOCKCUT (B) and SPQR (C) trees and assigns initial embeddings to SPQR components using TRIENC (D). Then, BIENC iteratively traverses each SPQR tree bottom-up (numbered), updates SPQR embeddings, and computes biconnected component embeddings (E). CUTENC then analogously traverses the BLoCKKCT tree compute graph embedding (F). Finally, the node representation is updated (G).
Formally, PLANE sets the initial node representations h!! ((u) for each node u V, and computes, for every layer < l s L. the representations Ā of SPQR components of oG, the representations ( of biconnected components G the representations h of subtrees Block-Cut tree d = BLOCKCUT(G) for each node u E V, and the representations h of nodes as:
T TRIENC(C,((111 uu] uEC))
hg BIENC(B, ( (000)"")))))
h ( CUTENC ((h (e-1) w)l uv)l B) BEx
h (((((-)) (h. (e- DI N.B. (h. uee (ht of (h
B T B.
where TRIENC, BIENC, and CUTENC are invariant encoders and ø is an UPDATE function. The encoders TRIENC and BIENC analogous TRICODE and BICODE of the KHC algorithm. In PLANE, we further simplify the final graph code generation, by learning embeddings for the cut nodes, which implemented by the CUTENC encoder. For graph-level tasks, we apply a pooling function on final node embeddings to obtain a graph-level embedding z
There are many choices for deriving PLANE architectures, but propose simple model, BASE- PLANE, to clearly identify the virtue of the model architecture which aligns with KHC, as follows:
TRIENC. Given an SPQR component C and the node representations h (f-1) of each node u, TRIENC encodes C' based the walk given by Weinberg's algorithm, and its corresponding sequence as:
= MLP
MLP
(h W
P llpp.))
where Par Rdd is the positional embedding 57 This is simple sequence model with a positional encoding the walk, and second one based on the generated sequence Edge features can also be

---

concatenated while respecting the edge order given by the walk. The nodes of SPQR(G) are one of the types S, P. Q. R. where for S, P. Q types, we have trivial ordering the induced components, and Weinberg's s algorithm also gives an ordering for R nodes that correspond to triconnected components.
(2) BIENC. Given a biconnected component B and the representations he of each component induced by a node C in y = SPQR B), BIENC uses the SPQR tree and the integers ((C, C") corresponding to how we connect C and C" E x(C). BIENC then computes representation for each subtree "CC' induced by a node C' in a bottom up fashion as:
MLP
(0)
Σ ('EX(C)
MLP (1 ( (ppccc))))
This encoder operates in a bottom up fashion to ensure that subtree representation of the children of C' exists before it encodes the subtree TO. The representation of the canonical root node in y used as the representation of the biconnected component B by setting: (1))) (e)
"anar(y)"
CUTENC. Given a subtree d, of a Block-Cus tree 8, the representations h of each biconnected
component B, and the node representations h (<-1) of each node, CUTENC sets h not a cut node; otherwise, computes the subtree representations as:
dd if is
(4) 8
MLP h
Σ BEX(W)
(1) MLP
Σ BEX(B)
( h
hB
The CUTENC procedure is called a bottom-up order to ensure that the representations of the grandchildren already computed. We learn the cut node subtree representations instead of employing the hierarchical overrides that are present in the KHC algorithm, as the latter is not ideal in learning algorithm. However, with sufficient layers, these representations are complete invariants.
of each node UPDATE. Putting these altogether, we update the node representations h
h = (00 (00 (11)))
+
Σn
(8) 11
Σ h
vEN
DEV
(
(h!
( l1 94
(8)
(h
Σ
93
CE
BER
where ((0) and gi are either linear maps or two-layer MLPs. Finally, we pool as:
I1 Σ
(I
(
MLP
ueVC
6 Expressive power and efficiency of BASEPLANE
We present the theoretical result of this paper, which states that BASEPLANE can distinguish any pair of planar graphs, even when using only logarithmic number of layers in the size of the input graphs:
Theorem 6.1. For any planar graphs G1 = (V1, E1. and G2 (V2, Eg, (o). there exists parametrization of BASEPLANE with at most L [log, (max( [V2H) layers, which computes a complete graph invariant, that is, the final graph-level embeddings satisfy zG, + = if and only G1 and G2 are not isomorphic.
(L) (L)
The construction is non non-uriform, since the number of layers needed depends on the size of the input graphs. In this respect, our result similar to other results aligning GNNs with 1-WL with sufficiently many layers 45 63 There are, however, two key differences: (i) BASEPLANE computes ssomorphism-comple
invariants over planar graphs and (ii) our construction requires only logarithmic number of layers in the size of the input graphs (as opposed to linear).

---

The theorem builds on the properties of each encoder being complete. We first show that a single application of TRIENC and BIÈNC sufficient to encode all relevant components of an input graph in an ssomorhhism-compeet way:
Lemma 6.2. Let G (V, E. be a planar graph. Then, for any biconnected components B, B' of G, and for any SPQR components C and C' of G, there exists parametrization of the functions TRIENC and BIENC such that:
(i) h + hg if and only if B and B' are not isomorphic, and
(ii) hcc + hi if and only if C and C' are not isomorphic.
Intuitively, this result follows from natural alignment the procedures of the KHC algorithm: the existence of unique codes for different components is proven for the algorithm and we lift this result the embeddings of the respective graphs, using the universality of MLPs [14 31 32
Our main result rests on a key result related to CUTENC, which states that BASEPLANE computes complete graph invariants for all subtrees of the Block-Cut tree. We use an inductive proof, where the logarithmic bound stems from a single layer computing complete invariants for all subtrees induced by cut nodes that have at most grandchild cut node, the induced subtree of which is incomplete.
Lemma 6.3. For a planar graph G (V, E, <) of order n and its associated Block-Cut tree 5 = BLOCKCUT(C)) there exists a L = [log (ni] + 1 layer parametrization of BASEPLANE that computes a complete graph invariant for each subtree 5, induced by each cut node u.
With Lemma 6.2 and Lemma 6.3 in place, Theorem 6. follows from the fact that every biconnected component and every cut node of the graph are encoded in an isomorphism-commplle way, which is sufficient for distinguishing planar graphs.
Runtime efficiency. Theoretically, the runtime of one BasePlanE layer is ((VVdd) with (one-off) pre pre-processing time (()V as we elaborate in Appendix B In practical terms, this makes BasePlanE linear in the number of graph nodes after preprocessing. This is very scalable opposed other complete algorithms based on 3-WL (or, oblivious 4-W1.).
Experimental evaluation
In this section, we evaluate BASEPLANE in three different settings. First, we conduct three ex- periments to evaluate the expressive power of BASEPLANE. Second, we evaluate a BASEPLANE variant using edge features on the MolHIV graph classification task from OGB [33 61. Finally, we evaluate this variant on graph regression over ZINC [18] and QM9 [22
48 We provide an
additional experiment the runtime of BASEPLANE in Appendix B and an ablation study on ZINC All experimental details, including hyperparameters, can be found in Appendix
in Appendix C
7.1
Expressiveness evaluation
7.1.1 Planar satisfiability benchmark: EXP
Experimental setup. We evaluate BASEPLANE on the pla-
Table 1: Accuracy results on EXP.
nar EXP benchmark ( and compare with standard MPNNs, MPNNs with random node initialization and (higher-order) 3-GCNs [45). EXP consists of planar graphs which each rep- resent satisfiability problem (SAT) instance. These instances are grouped into pairs, such that these pairs cannot be distin- guished by 1-WI,, but lead to different SAT outcomes. The task EXP to predict the satisfiability of each instance. To obtain above-random performance on this dataset, a model must have a sufficiently strong expressive power (2-WL or more). To conduct this experiment, we use a 2-layer BASE- PLANE model with 64-dimensional node embeddings. We instantiate the triconnected component encoder with 16-dimensional positional encodings, each computed using periodicity of 64.
Baselines are from Abboud et al. [I]
Model
Accuracy (%)
GCN
50.020.00
GCN-RNI(N)
98.0 08.0+1.85
3-GCN
99.740.004
BASEPLANE
100
$ Across all experiments, we present tabular results, and follow a convention in which the best result is bold in black, and the second best result is shown in bold in gray.
7

---

Results. All results are reported in T As expected. BASEPLANE perfectly solves the task, achieving a performance of 100% (despite not relying on any higher-order method). BASEPLANE solely relies on classical algorithm component decompositions, and does not rely on explicitly selected and designed features, to achieve this performance gain. This experiment highlights that the general algorithmic decomposition effectively improves expressiveness in a practical setup, and leads to strong performance on EXP, where a standard MPNN would otherwise fail.
7.1.2 Planar 3-regular graphs: P3R
Experimental setup. We propose a new synthetic dataset P3R based on 3-regular planar graphs, and experiment with BASEPLANE, GIN and 2-WL-expressive PPGN [43]. For this experiment, generated all 3-regular planar graphs of size 10, leading to exactly 9 non-isomorphic graphs. For each such graph, we generated 50 isomorphic graphs by permuting their nodes. The task is then to predict the correct class of an input graph, where the random accuracy is approximately 11.1%. This task is challenging given the regularity of the graphs.
Table 2: Accuracy results P3R.
Model
Accuracy (%)
GIN PPGN
11.1 +0.00
100 20.00
BASEPLANE
100 #0.00
Results. We report all results in Table 2 whereas BASEPLANE and PPGNs easily solve the task, achieving 100% accuracy.
As expected, GIN struggles to go beyond random guess,
7.1.3 Clustering coefficients of QM9 graphs: QM9cc
In this experiment, we evaluate the ability of BASEPLANE to detect structural graph signals without an explicit reference to the target structure. To this end, we propose a simple, yet challenging, synthetic task: given a subset of graphs from QM9, we aim to predict the graph-level clustering coefficient (CC). Computing CC requires counting triangles in the graph, which is impossible to solve with standard MPNNs (65]
Data. We select subset QM9cc of graphs from QM9 to obtain a diverse distribution of CCs. As most QM9 graphs have a CC of 0, we consider graphs with a CC in the interval [0.06, 0.16], as this range has high variability. We then normalize the CCs to the unit interval [0, 1]. We apply the earlier filtering on the original QM9 splits to obtain train/validation/tes sets that are direct subsets of the full QM9 splits, and which consist of 44226, 3941 and 3921 graphs, respectively.
Experimental setup. Given the small size of QM9 and the locality of triangle counting, we use 32- 12-dimensional node embeddings and 3 layers across all models. Moreover, we use a common 100 epoch training setup for fairness. For evaluation, we report mean absolute error (MAE) on the test set, averaged across 5 runs. For this experiment, our baselines are (i) an input-agnostic constant prediction that returns a minimal test MAE, (ii) the MPNNs GCNs 40 and GIN 63), (iii) ESAN 77). MPNN that computes sub-structures through node and edge removals, but which does not explicitly extract triangles, and (iv) BASEPLANE, using 16-dimensional positional encoding vectors.
Results. Results on QM9cc are provided in Table 3 BASE- PLANE comfortably outperforms standard MPNNs. Indeed, GCN performance is only marginally better than the constant baseline and GIN's MAE'N over an order of magnitude behind BASEPLANE. This is very substantial gap, and confirms that MPNNs are unable to accurately detect triangles to compute CCs. Moreover, BASEPLANE achieves an MAE over 40% lower than ESAN. Overall, BASEPLANE effectively detects triangle structures, despite these not being explicitly provided, and thus its underlying algorithmic dccomposition effectively captures latent structural graph properties in this setting.
Table MAE of BASEPLANE and basclines on the QM9cc dataset.
Model
MAE
Constant GCN
0.1627 #0.000
0.1275 10.0012
GIN ESAN
0,0612 10.0016
0.0038 =0 2010010
BASEPLANE
0.0023 =00004
Performance analysis. To better understand our results, we visualize the predictions of BASEPLANE, GIN, and GCN using scatter plots in Figure As expected, BASEPLANE follows the ideal regression line. By contrast, GIN and GCN are much less stable. Indeed, GIN struggles with CCs at the extremes of the [0, 1] range, but is better at intermediate values, whereas GCN is consistently unreliable, and rarely returns predictions above 0.7. This highlights the structural limitation of GCNs, namely its self-loop mechanism for representation updates, which causes ambiguity for detecting triangles.
8

---

BASEPLANE
GIN
GCN
Prodicted CC
Predicted CC
Predicted CC
0.5
0.5
0.5
0
0
0.5
0.5
0.5
Normalized CC
Normalized CC
Normalized CC
Figure 4: Scatter plots of BASEPLANE, GIN, and GCN predictions versus the true normalized CC. The red line represents ideal behavior where predictions match the true normalized CC.
7.2 Graph classification on MolHIV
Model setup. We use BASEPLANE variant that uses edge features, called E-BASEPLANE (defined in the appendix), on
Table 4: ROC-AUC of BASE-
OGB 33 MolHIV and compare against baselines. We in-
PLANE and baselines on MolHIV.
stantiate B-BASEPLANE with an embedding dimension of 64,
16-dimensional positional encodings, and report the average ROC-AUC across 10 independent runs.
GCN 40
75.58
GIN 63
77.07+1.40
Results. The results for E- E-BASEPLANE and other baselines on MolHIV are shown in Table 4 Despite not explicitly ex- tracting relevant cycles and/or molecular sub-structures, E- BASEPLANE outperforms standard MPNNs and the domain- specific HIMP model. It is also competitive with substructure- aware models CIN and GSN, which include dedicated structures for inference. Therefore, E- B--BEEPPLANE performs strongly in practice with minimal design effort, and effectively uses its structural inductive bias to remain competitive with dedicated architectures.
PNA 13
79.05+11.2
ESAN 7
78.00+1.42
GSN [1]
80.3 60.3940.00 40.900
CIN 9
80.9440.57
HIMP 220
78.80+0.58
E-BASEPLANE
80.04
Graph regression on QM9
Experimental setup. We map QM9 48 edge types into features by defining learnable embedding per edge type, and subsequently apply E B-BAEELLANE the dataset. We evaluate E --BSEPLANE on all 13 QM9 properties following the same splits and protocol (with MAE results averaged over 5 test set reruns) of GNN-FiLM [12). We compare R-SPN against GNN-FiLM models and their fully adjacent (FA) variants 3. as well as shortest path networks (SPNs) 22. We report results with an 3-layer B-BASEPLANE using 128-dimensional node embeddings and 32-dimensional positional encodings.
Results. E-BASEPLANE results on QM9 are provided in Table 5 In this table, E-BASEPLANE outperforms high-hop SPNs, despite being simpler and more efficient, achieving sfate-of-the-art results on 9 of the 13 tasks. The gains are particularly prominent on the first five properties, where R-SPNs originally provided relatively little improvement over FA models, suggesting that E-BASEPLANE offers complementary structural advantages SPNs. This corroborated in experimental tuning: E-BASEPLANE performance peaks around 3 layers, whereas SPN performance continues to improve up to 8 (and potentially more) layers, which suggests that E-BASEPLANE is more efficient at directly communicating information, making further message passing redundant.
Overall, E-BASEPLANE maintains the performance levels of R-SPN with a smaller computational footprint. Indeed, messages for component representations efficiently propagate over trees in E- BASEPLANE, and the number of added components is small (see appendix for more details). There- fore E-BASEPLANNE and the PLANE framework offer more scalable alternative to explicit higher- hop neighborhood message passing over planar graphs.

---

Table 5: MAE of E- E-BASEPLANE and baselines on QM9. Other model results and their fully adjacent (FA) extensions are previously reported [2] 3).
Property
R-GIN
R-GAT
R-SPN
BASEPLANE
base
+FA
base
+FA
k = 5
k = 10
mu 2.64+0.11
2.54=0.09
2.6820.11
2.7320.07
2.16:0.08
2.21
1.9720.03
alpha
4.6720.52
2.28=0.04
4.6520.44
2.3220.16
1.7420.05
1.66:2.06
1.63:0000
HOMO
1.42+0..01
1.26=#002
1.48+0.03
1.43
1.19
1.20++.08
1.15 #0.01
LUMO
1.50:10.09
1.34
1.53
+..00
1.13:00.01
1.20
1.06:10.00
gap
2.2710009
1.96=10004
2.31
2.08
1.76
1.77:1.00
1.73
R2
15.63=1.40
12.61
52.39:1424
15.76=1.17
10.59
10.63
10. 10.55
ZPVE
12.93=1.81
5.03=0.36
14.87+2.85
5.98
3.16+D.0G
2.58+4.13
2.81
UO
5.88+1.01
2.21
7.61#a.48
2.19
1.10
0.89
0.95
U
18.71+22..
2.32=a018
6.86+v.63
2.11+0010
1.09
0.93+
0.94+40.04
H
5.6222.81
2.26=0.19
7.64
2.27
1.10
0.92:0.01 0.92#0.03
G
5.3840.75
2.04
6.54
2.07=0.07
1.04
0.83
0.88
Cv
3.53+0.37
1.8620.03
4.11
2.03
1.34
1.23:20.0
1.20
Omega
1.05
0.80
1.48
0.73
0.53
0.52:10.02
0.45:10.0
7.4 Graph regression on ZINC
Experimental setup. We (i) evalu- ate BASEPLANE on the ZINC subset (12k graphs) without edge features, (ii) evaluate E-BASEPLANE on this subset and on the full ZINC dataset (500k graphs). To this end, we run BASEPLANE and E-BASEPLANE with 64 and 128-dimensional embed- dings, 16-dimensional positional em- beddings, and 3 layers. For evaluation, we compute MAE on the respective test sets, and report the best average of 10 runs across all experiments.
Table 6: MAE of (E-)BASEPLANE and baselines on ZINC.
ZINC(12K)
ZINC(12K) ZINC(Full) Yes
Edge Features
No
Yes
GCN
40
0.27840.003
GIN E)
34 63
1.3884+0.012 0.252
0.088 0.88=0.000 0.002
PNA 13
0.320+o.032 0.188
0.320
GSN
1..40
0.101=0.00
CIN 9
0.115 0.0003
0.079 : 006
0.022
ESAN
0.102
HIMP 20
0.151 00.006 0.036=2.0022
Results. Results on ZINC are shown Table Both BASEPLANE and E-
(E-) 0.12410.001
0.076:0.000 0.028
BASEPLANE perform strongly, with E-BASEPLANE achieving state-of- the-art performance on ZINC12K with edge features and both models outperforming all but one baseline in the other two settings. These results are very promising, and highlight the robustness of (E-))AAFPLAANE
8 Limitations, discussions, and outlook
Overall, both BASEPLANE and E- B-BAEEPLANE perform strongly across all our experimental evalua- tion tasks, despite competing against specialized models in each setting. Moreover, both models isomorphism-comppl over planar graphs. This implies that these models benefit substantially from the structural inductive bias and expressiveness of classical planar algorithms, which in turn makes them reliable, efficient, and robust solution for representation learning over planar graphs.
Though the PLANE framework is a highly effective and easy to use solution for planar graph representation learning, is currently limited to planar graphs. Indeed, the classical algorithms underpinning PLANE do not naturally extend beyond the planar graph setting, which in turn limits the applicability the approach. Thus, very important avenue for future work to explore alternative (potentially incomplete) graph decompositions that strike balance between structural inductive bias, efficiency and expressiveness on more general classes of graphs.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank the anonymous reviewers for their feedback which led to substantial improvements in the presentation of the paper. The authors would like to also acknowledge the use of the University of Oxford Advanced Research Computing (ARC) facility in carrying out this work (http://bx.doiirrg/10.2288 (a./5/2///eeooo wtt.eeooo...2555...
References
[1] Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. IJCAI, 2021.
[2] Ralph Abboud, Radoslav Dimitrov, and ismail ilkan Ceylan. Shortest path networks for graph property prediction. In Proceedings of the First Annual Learning on Graphs Conference, LoG, 2022.
[3] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Proceedings of the Ninth International Conference on Learning Representations, ICLR, 2021.
[4] László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the Forty-Eighte Annual ACM Symposium on Theory of Computing, STOC, 2016.
[5] Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In Proceedings of the Eighth International Conference on Learning Representations, ICLR, 2020.
[6] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzale Gonzalez, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint: 1806. 01261, 2018.
[7] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In Proceedings of the Tenth International Conference on Learning Representations, ICLR, 2022.
[8] Sandeep N Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28(2):300 343, 1984.
[9] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido Montúfar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. In Proceedings of the Thirty-Fourth Annual Conference on Advances in Neural Information Processing Systems, NeurlPS, 2021.
[10] Kellogg S Booth and George S Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976.
[11] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Puttern Analysis and Machine Intelligence, 45(1):657-666 2023.
[12] Mare Brockschmidt, GNN-FiLM: Graph neural networks with feature-wise linear modulation. In Proceedings of the Shirth-Seventh International Conference on Machine Learning, ICML, 2020.
[13] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic. Prin- cipal neighbourhood aggregation for graph nets. In Proceedings of the Thirty-Thir Annual Conference Advances in Neural Information Processing Systems, NeurIPS, 2020.
11

---

[14] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
[15] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI, 2020.
[16] G. Di Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR- trees. Algorithmica, 15(4):302-318, 1996.
[17] David Duvenaud, Dougal Maclaurin, Jorge Aguilera- litieraa-ppraauuirree Rafael Gómez-Bombarelley Timothy Hirzel, Alán aapuru-Guzik and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Proceedings of the Twenty-Fightn Annual Conference on Advances in Neural Information Processing Systems, NIPS, 2015.
[18) Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 2023.
[19] David Eppstein. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications, 3(3):1-27, 1999.
[20] M. Fey, J. G. Yuen, and F. Weichert. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop. 2020.
[21] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Proceedings of the Thirtieth Annual Conference on Advances in Neural Information Processing Systems, NIPS, 2017.
[22] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the Mhirty-Fourth International Conference Machine Learning, ICML, 2017.
[23] Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, IJCNN, 2005.
[24] Martin Grohe Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes Logic. Cambridge University Press, 2017.
[25] Martin Grohe The logic of graph neural networks. In Proceedings of the Thirty-Sixth Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2021.
[26] Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, 63(1 (1:18)):88-144 2020.
[27] Carsten Gutwenger and Petra Mutzel. A linear time implementation of spqr-trees. In Proceedings of the Eigth International Symposium on Graph Drawing, 2000.
[28] J. F. Hoperoft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC, 1974.
[29] John Hopcroft and Robert Tarjan. A v2 algorithm for determining isomorphism of planar graphs. Information Processing Letters, 1(1):32-34, 1971
[30] John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378 1973.
[31] Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251-277 1991.
[32] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989.
12

---

[33] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs In Proceedings of the Thirty-Third Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, 2020.
[34] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Proceedings of the Eighth International Conference on Learning Representations, ICLR, 2020.
[35] Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canoniza- tion. Complexity Theory Retrospective, pages 59-81, 1990.
[36] Steven M. Kearnes, Kevin McCloskey, Mare Berdl,, Vijay S. Pande, and Patrick Riley. Molecu- lar graph convolutions: moving beyond fingerprints. Journal of Computer Aided Molecular Design, 30(8):595-660 -08, 2016.
[37] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Proceedings of the Thirly-Second Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, 2019.
[38] Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The weisfeiler-leman dimension of planar graphs is at most 3. Journal of the ACM, 66(6):1-31, 2019.
[39] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the Third International Conference on Learning Representations, ICLR, 2015.
[40] Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the Fifth International Conference on Learning Representations, ICLR, 2017.
[41] Jacek Kukluk, Lawrence Holder, and Diane Cook. Algorithm and experiments in testing planar graphs for isomorphism. Journal of Graph Algorithms and Applications, 8(3):313-356 2004.
[42] Andreas Loukas. What graph neural networks cannot learn: depth width. In Proceedings of the Eighth International Conference on Learning Representations, ICLR, 2020.
[43] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Proceedings of the Thirty-Secont Anmual Conference on Advances in Neural Information Processing Systems, NeurlPS, 2019.
[44] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Proceedings of the Thirty-Sixth International Conference on Machine Learning, ICML. 2019.
[45] 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 Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, 2019.
[46] Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Pro- ceedings of the Thirty-Third Annual Conference Advances in Neural Information Processing Systems, NeurIPS, 2020.
[47] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social represen- tations. In Proceedings of the Twentieth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, 2014.
[48] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177, 2014.
[49] Louis C. Ray and Russell A. Kirsch. Finding chemical records by digital computers. Science 126(3278):814-819 1957.
13

---

[50] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining, SDM, 2021.
[51] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
[52] Wei-Kuan Shih and Wen-Lian Hsu, A new planarity test. Theoretical Computer Science, 223 (1-2):179-191, 1999.
[53] Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2021.
[54] Howard E. Simmons and John E. Maggio. Synthesis of the first topologically non-planar molecule. Tetrahedron Letters, 22(4))287-25) 290, 1981.
[55] Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. In Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, STOC, 1981.
[56] Erik H. Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism- based graph neural nets. In Proceedings of the Thirty-Fourt Annual Conference on Advances in Neural Information Processing Systems, NeurlPS, 2021.
[57] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the Thirtieth Annual Conference on Advances in Neural Information Processing Systems, NIPS, 2017.
[58] Louis Weinberg. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Transactions on Circuit Theory, 13(2) 142-148, 1966.
[59] Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to canonical form and an algebra arising during this reduction. Vaachno-TTehhicchen
Informatsia, 2(9):12-16, 1968.
[60] Hassler Whitney. set of topological invariants for graphs American Journal of Mathematics, 55(1):231-233, 1933.
[61] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9():51335300 2018.
[62] Feng Xie and David Levinson. Topological evolution of surface transportation networks. Computers, Environment and Urban Systems, 33(3):211-223 2009.
[63] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the Seventh Annual Conference on Learning Representations, ICLR, 2019.
[64] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tin-Yan Liu. Do transformers really perform badly for graph representation? In Proceedings of the Chirty-Fourth Annual Conference on Advances in Neural Information Processing Systems, NeurIPS, 2021.
[65] Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the Thirty-Fifih AAAI Conference on Artificial Intelligence, AAAI, 2021.
[66] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. In Proceedings of the Eleventh International Conference on Leurning Representations, ICLR, 2023.
[67] Muhan Zhang and Pan Li. Nested graph neural networks. In Proceedings of the Thirty- Annual Conference on Advanced in Neural Information Processing Systems, NeurlPS, 2021.
[68] Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i457-ii46, 2018
14

---

A Proofs of the statements
In this section, we provide the proofs of the statements from the main paper. Throughout the proofs, we make the standard assumption that the initial node features are from compact space K C R for some d E N We also often need to canonically map elements of finite sets to the integer domain: given finite set S, and any element x to a unique integer index given by some fixed order over the set S. Furthermore, we also often need to injectively map sets into real numbers, which is given by the following lemma.
S of this set, the function ((, S + {I,.... |S]] maps
Lemma A.1. Given finite set S, there exists an injective map g P(()) - [0, 1].
Proof. For each subset M S, consider the mapping:
g(M) = I+ ++EEEM VSS -(S
which clearly satisfies ((M) * (M2)) for any MI + M2 S.
We now provide proofs for Lemma 6.2 Lemma 6.3 which are essential for Theorem 6.1 Let us first prove Lemma 6.2
Lemma 6.2. Let G = (V, be planar graph. Then, for any biconnected components B, of G. and for any SPQR components C and C' of G. there exists a parameterization the functions TRIENC and BIENC such that:
(i) hB hy if and only B and B' not isomorphic, and (ii) he + foo if and only if C and C' are not isomorphic.
Proof. We show this by first giving parameterization of TRIENC to distinguish all SPQR com- ponents, and then use this construction to give a parameterization of BIENC to distinguish all biconnected components. The proof aligns the encoders with the code generation procedure in the KHC algorithm. The parameterization needs only single layer, so we will drop the superscripts in the node representations and write, e.g., h,, for brevity. The construction yields single-dimensional real-valued vectors, and, for notational convenience, we view the resulting representations as reals.
Parameterizing TRIENC. We initialize the node features as h. <(u), where Ç V. + Rr.. Given an SPQR component C' and the initial node representations h. of each node TRIENC encodes C' based on the walk w given by Weinberg's algorithm, and its corresponding sequence x as:
w
hC = MLP Σ
MLP (hwja (esa||/PAaa)))))
In other words, we rely on the walks w generated by Weinberg's algorithm: we create a walk on the triconnected components that visits each edge exactly twice. Let us fix 4([V] + |E|+ 1), which serves as an upper bound for size of the walks w. and the size of the walk-induced sequence k.
We show bijection between the multiset of codes F (given by the KHC algorithm), and the multiset of representations M (given by TRIENC), where the respective multisets are defined, based on G, as follows:
F = (CODE(C) CC E G.:: the multiset of all codes of the SPQR components of G.
M the C E B:: the multiset of the representations of the SPQR components of G.
Specifically, we prove the following:
Claim 1. There exists bijection p between and M such for any SPQR component C:
p(hc) CODE(C)) and (CODE(C)) hc.
15

---

Once Claim 1 established, the desired result is immediate, since, using the bijection P. and the completeness of the codes generated by the KHC algorithm, we obtain:
he + he
(CODE(C)) + p- (CODE((C))) $ CODE(C) + CODE(C")
C and C' are non-isomorphic.
To prove the Claim I first note that the canonical code given by Weinberg's algorithm for any component C' has the form:
CO) = TRICODE(C) = (x:11, (ODE(((([1)) (MM ((DE((())) ()))
= [x:[1), ((((1))) (rc[A), ((w(H))
(2)
There is a trivial bijection between the codes of the form (2) and sets of the following form:
Sc ((S(w(t)),xf)
S i [w]
and, as a result, for each component C, we can refer to the set Sc that represents this component C instead of CODE(C). Sets of this form of bounded size (since the number of walks bounded in C) and each of their elements is from a countable set. By (e.maaA.I]thaall
exists an injective map between such sets and the interval [0, 1]. Since the size of every such set bounded, and every tuple from a countable set, we can apply Lemma of Xu et al. 63,, and decompose the function g as:
g(Sc)
Σ f(x)
LEESc
for an appropriate choice Ø: Rd + [0, 1] and f(x) RRd", Based on the structure the elements of Sc, we can further rewrite this as follows:
g(Sc)
Σ ((CC(W)))
Observe that this function closely resembles TRIENC TT. More concretely, for any w and i, we have that ((wli)) hw and, moreover, Px|j and p: are the positional encodings of k[i], and i, respectively, Hence, it is easy to see that there exists a function which satisfies, for every i:
((C(w))))) m((), = p(h [IPPPp]lppp)
This implies the following:
W
g(Sc)
f x(]..
(n(hwaal (ww.lllllllllllee
W
Σ (f (h (wtglll
Observe that this function can be parameterized by TRIENC: we apply the universal approximation theorem [1 32), and encode (f μu) with an MLP (i.e., the inner MLP) and similarly encode with another MLP (i.e., the outer MLP).
This establishes a bijection between F and M: for any SPQR component C, we can injectively map both the code CODE(C) (or, equivalently the corresponding set Sc) and the representation he the same unique value using the function g as he = g(Sc), and we have shown that there exists parameterization of TRIENC for this target function g.
16

---

Parameterizing BIENC. In this case, we are given a biconnected component B and the representa- tions he of each component C' from the SPQR tree 7 SPQR(B). We consider the representations he which are result of the parameterization of TRIENC, described earlier.
BIENC uses the SPQR tree and the integers (C,, C*) corresponding to how we connect C and C" E x()). BIENC then computes representation for each subtree "cc induced by node C in bottom up fashion as:
Σ MLP (M ((roolpacc)))) C'EXIC)
xC = MLP
hc +
(5)
This encoder operates in bottom up fashion to ensure that subtree representation of the children of C' exists before it encodes the subtree Tc. The representation of the canonical root node in y is used as the representation of the biconnected component B by setting: hg = "woett)))
To show the result, first note that the canonical code given by the KHC algorithm also operates in a bottom up fashion on the subtrees of y. We have two cases:
Case 1. For leaf node C in 7, the code for "ce is given by CODE(1C) TRICODE(C). This case can be seen as special case of Case (and we will treat as such).
Case 2. For a non-leaf node C, we concatenate the codes of the subtrees induced by the children of C' in their lexicographical order, by first prepending the integer given by 0 each child code. Then, we also prepend the code of the SPQR component C' to this concatenation to get CODE(Ti). More precisely, if the lexicographical ordering of ( based on CODE()C.) for given C' E x(C) is x [[]].... 2 [[xx( then the code for "jc is given by:
CODE(TC) = (TRICODE(C), (O(C, [1]), CODE())())) ..... (0(C, (ODE(())) (6)
We show a bijection between the multiset of codes F (given by the KHC algorithm), and the multiset of representations M (given by BIENC), where the respective multisets are defined, based on G and the SPQR tree y, as follows:
F = (CODE(1C) C' E yB: the multiset of all codes of all the induced SPQR subtrees.
M {ha C E 3:: the multiset of the representations of all the induced SPQR subtrees.
Analogously to the proof of TRIENC, we prove the following claim:
Claim 2. There exists bijection p between F and M such that, for any node C in 7;
p( = CODE(TC) and p (CODE(TC)) = h
Given Claim 2 the result follows, since, using the bijection p, and the completeness of the codes generated by the KHC algorithm, we obtain:
h + hBs
h M B) # h (B'))
(CODE(ROOT(B)) # ( (CODE((ROO((B")
CODE(ROOT(B)) + CODE(ROOT(B')
B and B' are non-isomorphic.
To prove Claim 2 let us first consider how CODE(TC) is generated. For any node C' in y, there is bijection between the codes of the form given in Equation (6) and sets of the following form:
Sc |f (TR)CODE(C)) } U ((((), C"), CODE(Te)) C' x(C)
17

---

Observe that the sets of this form are of bounded size (since the number of children is bounded) and each of their elements from countable set (given the size of the graph, we can also bound the number of different codes that can be generated). By Lemma A. there exists an injective map from such sets to the interval [0, 1]. Since the size of every such set is bounded, and every tuple is from countable set, we can apply Lemma 5 of Xu et al. [63] and decompose the function f as:
g(Sc) = f
LES
for an appropriate choice Ø: R2 [0, 1] and f(x) Rdd Based on the structure the elements of Sc, we can further rewrite this as follows:
g(Sc) á [(TRICODDF()))
Σ C'Ex(C)
[((OCC ((
Observe the connection between this function and BIENC 5 for every C' E x(C). we have hyer instead of CODE(TC), and, moreover, Pe(c,Cr) is positional encoding of (CC, C"). Then, there exists function y such that:
(0(C, C"DE,.)))))))) =
=(pp((t))) u(Potc.cyllmee))
provided that the following condition is met:
hic CODE(TC)) for any C' x(C).
Importantly, the choice for can be the same for all nodes C. Hence, assuming the condition specified Equation (9) is met, the function can be further decomposed using some function f'(x) E Rd which satisfies:
9(Sc)= = [((TRICODE(C)))+
Σ ((B(C)C"), C'EX(C)
hot Σ I' (" C'EX(O)
Φ he +
Eooon) (potc.cs))))) C'EX(C)
(F'm))
Observe that this function can be parameterized by BIENC 5): we apply the universal approximation theorem [4 B1 32), and encode (f" o (4) with MLP (1.c., the inner MLP) and similarly encode
with another MLP (i.e., the outer MI.P).
To conclude the proof of Claim 2 (and thereby the proof of Lemma 6.2 existence of bijection p between F and M such that, for any node C in 7
we need to show the
p(hyae) CODE(TC) and p (CCDEE(()))) = -hac-
This be shown by straight-forward induction the structure of the 7. For the base case, it suffices to observe that is leaf node, which implies h =((cc) and CODE(?C) (TRiCODE(C)). The existence of bijection is then warranted by Claim I For the inductive case, assume that there is bijection between the induced representations codes to ensure that the condition given in Equation (9) is met (which holds since the algorithm operates in bottom up manner). Using the injectivity of g, and the fact that all subtree representations (of children) already admit bijection, we can easily extend this to bijection on all nodes C' of 7
the children C' and their
We have provided parameterization of TRIENC and BIENC and proven that they can compute repre- sentations which bijectively map to the codes of the KHC algorithm for the respective components, effectively aligning KHC algorithm with our encoders for these components. Given the completeness of the respective procedures in KHC, we conclude that the encoders are also complete in terms of distinguishing the respective components.
Note that a (TRICODE((") be omitted, because TRIENC has outer MLP, which can incorporate f.
18

---

Having showed that a single layer parameterization of BIENC and TRIENC is sufficient for distin- guishing the biconnected and triconnected components, we proceed with the main lemma.
Lemma 6.3. For a planar graph G = (V, F., C) of order n and its associated Block-Cut tree 5 = BLOOKKUT((G) there exists I. = (n))
layer parameterization of BASEPLAANE that computes a complete graph invariant for each subtree óy induced by each cut node u.
Proof. CUTENC recursively computes the representation for induced subtrees o, from nodes U, where & = BLocKCUT(G)) Recall that in Block-Cut trees, the children of cut node always represent a biconnected component, and the children of biconnected component always represent a cut node. Therefore, it is natural to give the update formula for a cut node in terms of the biconnected component represented by u's children x(u) and B's children (B).
h MLP
((
Σ BEX(M)
MLP
T TO+
Σ
(10)
(EX(
To show the result, we first note that the canonical code given by the KHC algorithm also operates in bottom up fashion the subtrees of 5. We have three cases:
For leaf B in ö, the code for in given by CODE(ŌR) BICODE(B). This is because the leafs of are all biconnected components.
Case 1.
For non-leaf biconnected component B in 6, we perform overrides for the codes asso- ciated with each child cut node, and then use BIENC. More precisely, we override the associated CODE( (1) = CODE( for all u É xBB, and then we compute CODE(AR) BICODE(BB)
Case 2.
Case 3. For non-leaf cut node in 8, encode in similar way BIENC: get the set of codes induced by the children of u in their lexicographical order. More precisely, the lexicographical ordering of x(u), based on CODE((8) for given B E x(u) is =f1]...... =[[]]....==[((()) ==[x(u)]], then the code for 5, given by:
CODE(6.)) (CODE()<u)), ..... CODE(S.(==)))
(11)
Instead of modelling the overrides (as in Case 2), BASEPLANE learns the node representations. We first prove this result by giving a parameterization of B BASEPLANE which uses linearly many layers in and then show how this construction be improved logarithmic number of layers. Specifically, we will first show that BASEPLANEE can be parameterized to satisfy the following properties:
1. For every cut node we reserve dimension in h that stores the number of cut nodes in 6g This done in the UPDATE part of the corresponding layer.
2. There is a bijection À between the representations of the induced subtrees and subtree codes, such that ((h( CODE(δ.) and X (CODE( ()) (L) for cut nodes that have strictly less than L cut nodes in 8n.
3. There is bijection between the cut node representations and subtree codes, such that !( CODF(Ō.) and p (CODR(D) = (T.) for cut nodes u that have strictly less than T. cut nodes in ò,,
Observe that the property (2) directly gives us a complete graph invariant for each subtree 8, induced by each cut node u, since the codes for every induced subtree are complete, and through the bijection, we obtain complete representations. The remaining properties are useful for later order to obtain more efficient construction.
19

---

The UPDATE function in every layer is crucial for our constructions, and we recall its definition:
h = |(
91 (hl
(0)
((-1)
Σ
h
9 h
(8)
vENs
DEV
1 93 (h
((-1))
Σ CE
9
(8)
( +
)
BEE
We prove that there exists a parameterization of BASEPLANE which satisfies the properties (1)-(3) by induction on the number of layers L.
Base case. L = 1. In this case, there are no cut nodes satisfying the constraints, and the model trivially satisfies the properties (2)- To satisfy (I), identity function, and the outer MLP as a function which adds 1 to the first dimension of the input embedding. This ensures that the representations f.s.. (1) of cut nodes have their first components equal
set the inner MLP in CUTENC the
to the number of cut nodes in on. We can encode the property (1) in h using the representation b since the latter is a readout component in UPDATE.
Inductive step. L 1. By induction hypothesis, there is an (L - 1)-layer parameterization of BASEPLANE which satisfies the properties (1)-(3). We can define the L-th layer so that our L layer parameterization of BASEPLANE satisfies all the properties:
(1) Property (1): For every cut node u, the function UPDATE has readout from h and h
which allows to copy the first dimension of fi!(-1) into the first dimension of h! using linear transformation, which immediately gives us the property.
Property (2): For this property, let us first consider the easier direction. Given the code of 8.. we want to find the CUTENC representation for the induced subtree of u. From the subtree code, we can reconstruct the induced subtree ōu, and then run L-layer BASEPLANE on reconstructed Block-Cut Tree to find the CUTENC representation. As for the other direction, we want to find the subtree code of given the representation of the induced subgraph. The CUTENC encodes multiset K (hhB. (h,lv E BB) B x(u) B. By induction hypothesis, we know that all grandchildren E (²) already have properties (1)-() satisfied for them with the first (L- 1) layers. Hence, using the parameterization of TRIENC and BIENC given in Lemma 6.2 as part of the L-th BASEPLANE layer, we can get bijection between BICODE and biconnected component representation. This way we can obtain (ICODE(B) for all the children biconnected components B E X(u), with all the necessary overriding. Having all necessarily overrides is crucial, because to get the KHC code for the cut node u, we need to concatenate the biconnected codes from that already have the required overrides. Hence, make the parameterization of CUTENC encode multisets of representations for biconnected components B E (u),, and by similar arguments as in the proof of Lemma 6.2 this can be done using the MLPs in CUTENC.
Property (3): Using the bijection from (2) as a bridge, we can easily show the property (3). In the update formula, we appended (L) using the MLP. If the MLP is bijective with the dimension taken by ( we get bijection between the node representation and the subtree representation. By transitivity, we get bijection between node representations and subtree codes.
This concludes our construction using L (n)) BASEPLANE layers.
Efficient construction. We now show that the presented construction can be made more efficient, using only [nog + 1 layers. This is achieved by treating the cut nodes u differently based on the number of cut nodes they include in their induced subtrees 8.. In this construction, the property (I) remains the same, but the properties (3)-() are modified:
1. For every cut node u, we reserve a component in (-) that stored to the number of cut nodes in 5_. This is done in the UPDATE part of the corresponding layer.
2. There is bijection À between the representations of the induced subtrees and subtree codes, such that (1) = CODE((.) and X - (CCDDE(() h for cut nodes u that have strictly less than 2(11)) cut nodes in d..
20

---

3. There is bijection between the cut node representations and subtree codes, such that p(h (L) (ō)) and p (CODE((d)) )) ha for cut nodes u that have strictly less than 2(2-1) cut nodes in 8n.
These new modified properties allow us to reduce the depth of the induction to a logarithmic number of steps, by having more carefully designed parameterization of CUTENC. The logarithmic depth comes immediately from properties (2) and (3), while the core observations for building the CUTENC parameterizations are motivated by standard literature on efficient tree data structures, and in particular by the Heavy Light Decomposition (HLD) [55]. HLD, we build "chains" through the tree that always go to the child that has the most nodes in its subtree. This gives us the property that, the path between each two nodes visits at most a logarithmic number of different chains, and we will use this concept in our parametrization. More precisely, we can construct single CUTENC layer, that will make the above properties hold for whole chains, and not only individual nodes as in the previous construction.
We will once again use induction to show that such parametrizations exist.
Base case. L = 1. The properties are equivalent to the ones in the less efficient construction: property (I) is the same, and ( (1.-1) = 20 = L. so we will satisfy them with the same parameterization.
Inductive step. I, 1. By induction hypothesis, there is an (L - 1lllayer parameterization of BASEPLANE which satisfies the properties (1)-(). We can define the I--th layer so that our T. layer parameterization of BASEPTANNE satisfies all the properties:
Property (7): This is satisfied in the same way as in the less efficient construction we allocate one of the dimensions for the required count, and propagate it from the previous layer.
Property (2): Let us consider an arbitrary cut node u that has strictly less than 2(L-1) cut nodes in its induced subtree 8 and still does not satisfy property (2). We will call such nodes "improper" with respect to the current induction step, and show that there a single layer CUTENC parameterization that makes all improper nodes satisfy these two properties, or become "proper".
First, observe that an arbitrary cut node Fi has at most one improper grandchild en E x ("),. because if there were more improper grandchildren then it would have had at least 2(4-1) cut nodes in it. Repeating a similar argument, we know that there is at most one improper 222 E x² (01). Continuing this until there are no improper grandchildren, we form sequence of improper cut nodes u = %o Vi..... Uk. such that 0/+1 is grandchild of is for all 0 < i < k. The chain Up. .,...., U2 is precisely a chain in HLD, and we will show that a single CUTENC layer can make an "improper chain" satisfy the properties. We prove this by applying inner induction on the chain:
Induction hypothesis (for grandchildren): By the induction hypothesis, we have an established (L-1)-layed) parameterization of BASEPLANE that satisfies properties (1)-() for all but a single grandchild of each node in the chain Vo, ...: Uk. This assumption is critical as it provides the ground truth that our subsequent steps will build upon.
Having established the hypothesis for our node's children, we initiate an inner induction, starting from the farthest improper node in the chain, 2k, and progressively moving towards the root of the chain, u = Vo- This process is akin to traversing back up the chain, ensuring each node, starting from Ug, satisfies property (2) as ascend.
Inner induction:
For each node o; in our reverse traversal, we apply the special property: there exists at most one improper grandchild (potentially 1)4-1) within its local structure. Our CUTENC architecture then identifies this improper grandchild, which, crucially, is "proper" in its representation due to our inner induction process. This identification is facilitated by the inner MLP given in Equation (10), and property (1), as identifying is equivalent to selecting the grandchild with the largest number of cut nodes in the allocated dimension.
Having identified and isolated our improper grandchild U++1 (now proper in (T.) b ). CUTENC
then integrates this node with the other children and grandchildren of v.. It is important to note that all these other nodes have representations bijective to their respective subtree codes because of the induction hypothesis. This integration is not a mere collection; instead, the outer MLP in
21

---

Equation (T0) models the "code operation" that BICODE would have done, which is possible due to the mentioned bijections to codes. This concludes the inner induction.
Our choice for u was arbitrary and the required CUTENC parameterization is independent from the exact node representaton- it simply models a translation back codes, and then injecting back to embeddings. Hence, all chains of improper nodes will satisfy property (2) after a single CUTENC layer.
Property (3): We once again follow the same approach as in the less efficient construction we use property (2) bridge, know we have already satisfied it. Property (3) is needed to ensure that all nodes that once became "proper" will always stay so, by propagating the bijection to codes,
This concludes our construction using [Iog + layers.
Theorem 6.1. For any planar graphs G1 = F4, F,, C1) and G2 = (V2, F.z, C2), there exists parameterization of BASEPLANE with at most L logg (max[ [V21))] + layers, which computes a complete graph invariant, that is, the final graph-level embeddings satisfy z + z(() if and only 11 and G2 not isomorphic.
(L)
Proof. The "only if" direction is immediate because BASEPLANE, is an invariant model for planar graphs. To prove the "if" direction, we do case analysis the root of the two Block-Cut Trees.
(L) For each case, we provide parameterization BASEPLANE such that = * ZG² for any two non-isomorphic graphs 11 and G2. A complete BASEPLANE model can be obtained by appropriately unifying the respective parameterizations.
Case 1. ROOT();) and ROOT(52) represents two nodes.
Consider parameterization of the final BASEPLANE. update formula, where only cut node represen- tation is used, and simplified readout that only aggregates from the last layer. We rewrite the readout for graph in terms of the cut node representation from the last BASEPLANE layer:
(L) 2
MLP Σ MLP(h (L)
VEEVO
V.J. Intuitively, CUT(G) is multiset of cut node representations from the last BASEPLANE layer. We assume VV, < VV, without loss of generality. Consider the root node (OOT(52) of the Block-Cut Tree 82. By Lemma 6.3, we have hgoor(62) as a complete graph invariant with layers. Since &2 cannot appear as a subtree of 61, hRoo1(6)) & CUT(G1). Hence, CUT(Gr) * CUT(G2). Since this model can define an injective mapping on the multiset CUT(G)
Let CUT(G) (
using similar arguments before, we get that =G; + 2G2
(L)
(E)
Case 2. ROOT( and ROOT(62) represents biconnected components.
We use a similar strategy to prove Case 2. First, we consider a simplified BASEPLANE model, where the update formula considers biconnected components only and the final readout aggregates from the last BASEPLANE layer. We similarly give the final graph readout in terms the biconnected component representation from the last BASEPLANE layer.
ZG MLP
Σ MLP((N(L-)) +
Σ BER
NEVO
Let Bc(G) = ((h(-1)) ( B E GB) u E VG). In Lemma 6.3, we prove that h()) also a complete invariant for the subtree rooted at B in the Block-Cut Tree. First, we show Bc(Gi) * Bc(G2). As before, assume V6, < VV, without loss of generality. Consider how
(L)
22

---

the biconnected component representation (8)) appears in the two multisets of pairs. For G2. there exist at least one node u and pair:
(h(4-1) Ahg B E Bc(G2),
(2) B E T However, because (RooT(82) is complete invariant for 82 and 82 cannot appear as a subtree in ō1, no such pair exists in Bc(G,). Given Bc(G1) o Bc(G2), we can parameterize the MLPs to define an injective mapping to get that 2G. + 2G2
such that (6)) Khg
(T.)
Case 3. (O)T(61) represents a cut node and ROOT(62) represents biconnected component.
We can distinguish G1 and G2 using a simple property of ROOT()1). Recall that TH represents the set of biconnected components that contains u, and x (C) represents the C's children in the Block-Cut Tree 5. For RO0T(61), we have | = (u)]. However, for any other cut node u, including the non-root cut node in ò1 and all cut nodes in 52, we have [ Ix (u)l + because there must be
parent node of such that E Ge but x" (u))
Therefore, we consider a parameterization of one-layer BASEPLANE model that exploits this property. In BIENC, we have constant vector O] for all biconnected components. In CUTENC, we learn [0, |x,|_ for all cut nodes u. In the update formula, we have [ Ix (u)] - -, All of the above specifications can be achieved using linear maps. For the final readout, we simply sum
all node representations with no extra transformation.
Then, for ROOT(61), ), we have (d.. [- 0] T. For any other node u, have h. [0, 0
For all non-cut nodes u, we also have h. [0, 0] because | G = 1 and hs. = [0, 0J Summing
all the node representations yields zG, = [-1, 0] but 2G,- = [0, 0j Hence, we obtain = + 2G
(L)
(L)
as required.
B Runtime analysis of BASEPLANE
B.1 Asymptotic analysis
In this section, we study the runtime complexity of the BASEPLANE model.
Computing components of planar graph. Given an input graph G = (V, E),, BASEPLANE first computes the SPQR components/SPQR tree, and identifies cut nodes. For this step. we follow a simple (2(V?2 procedure, analogously to the computation in the KHC algorithm. Note that this computation only needs to run once, as a pre- pre-processing step. Therefore, this preccomputation does not ultimately affect runtime for model predictions.
Size and number of computed components.
1. Cut nodes: The number of cut nodes in G is at most [V], and this corresponds to the worst-case when is a tree.
2. Biconnected Components: The number of biconnected components | is at most [ 1, also obtained when G is a tree. This setting also yields worst-case bound of 2/V| - 2 on the total number of nodes across all individual biconnected components.
3. SQPR components: As proved by Gutwenger and Mutzel 227, given biconnected compo- nent B, the number of corresponding SPQR components, as well as their size, is bounded by the number of nodes in B. The input graph may have multiple biconnected components, whose total size is bounded by 2| 2 as described earlier. Thus, we can apply the earlier result from Gutwenger and Mutzel 27 to obtain an analogous bound of | - on the total number of SPQR components.
4. SPQR trees: As each SPQR component corresponds to exactly one node in SPQR tree. The total size of all SPQR trees is upper-bounde by 2| 2.
Complexity of TRIENC. TRIENC computes representation for each SPQR component edge. This number of edges, which we denote by ec, is in fact linear in V: Indeed, following Fuler's theorem for planar graphs (LE) < 3| 6), the number of edges per SPQR component is linear in its size.
23

---

Moreover, since the total number of nodes across all SPQR components is upper- bouuded by 2 - 22 the total number of edges is in OVV). Therefore, as each edge representation can be computed in constant time with an MIP, TRIENC computes all edge representations across all SPQR components in (eec - d) = ((V)))) time, where d denotes the emhedding dimension of the model.
Using the earlier edge representations, TRIENC performs an aggregation into triconnected com- ponent representation by summing the relevant edge representations, and this is done (Eed). Then, the sum outputs across all SPQR components are transformed using an MLP, in O(1o") (d)). Therefore, the overall complexity of TRIENC is O((e+ + 10 = O([V]d))
Complexity of BIENC. BIENC recursively encodes nodes in the SPQR tree. Each SPQR node is aggregated once by its parent and an MLP is applied to each node representation once. The total complexity of this call is therefore O dd) = ((V
Complexity of CUTENC. A similar complexity of O( (d²) applies for CUTENC, as CUTENC follows similar computational pipeline.
Complexity of node update. As in standard MLPs, message aggregation runs in ((E]d), and the combine function runs in O(V]d)). Global readouts can be computed in O(Vld). Aggregating from bi-connected components also involves at most O V d)) messages. as the number of messages corresponds the total number of bi-connected component nodes, which itself does not exceed 2|V| - 2. The same argument applies to messages from SPQR components: nodes within these components will message their original graph analogs, leading to the same bound. Finally, the cut node messages are linear, i.e., ((V)), each node receives exactly one message (no aggregation, no transformation). Overall, this leads to the step computation having complexity of O (VV dF).
Overall complexity. Each BASEPLANE layer runs in O(IV (ce) time, as this is the asymptotic bound of each of its individual steps. The d² term primarily stems from MLP computations, and is not main hurdle to scalability, as the used embedding dimensionality in our experiments is usually small.
Parallelization. Parallelization can be used to speed up the pre- pre-processing of large planar graphs. In particular, parallelization can reduce the runtime of KHC pre- pre-processing. and more precisely the computation of the canonical walk in Weinberg's 's algorithm, which itself is the individual step with the highest complexity (O(V)))) in our approach. To this end, one can independently run Weinberg's s algorithm across several triconnected components in parallel. Moreover, algorithm's 's operation within a single triconnected component: as the quadratic overhead comes from computing the lexicographically smallest TRICODE, where the computation depends on the choice of the first walk edge, we can concurrently evaluate each first edge option and subsequently aggregate over all outputs more efficiently find the smallest code.
can also parallelize the
B.2 Empirical runtime evaluation
Experimental setup. To validate the runtime efficiency of BASEPLANE, we conduct a runtime experiment on real-world planar graphs based on the geographic faces of Alaska from the dataset TIGER, provided by the U.S. Census Bureau. The original dataset is TIGER-Alaska-93K and has 93366 nodes. We also extract the smaller datasets TIGER-Alaska-2K and -IGER-Alaska-IOK, which are subsets of the original dataset with 2000 and 10000 nodes, respectively. We compare the wallclock time of BASEPLANE and PPGN which is as expressive as 2-WL.
Table 7: Runtime experiments on planar graphs TIGER-Alasee
TIGER-Alaska 100K and TIGER- Alaska-93K. We report the pre- prepprccesiing and training time (per epoch) for all models.
BASEPLANE
PPGN
ESAN
Dataset
#Nodes
Pre.
Train
Pre.
Train
Pre.
Train
TIGER-Alaska-2K
2000
9.8 sec
0.1 sec
3.4 sec
5.9 sec
4.6 sec
87.73 sec
TIGER-Alaska-10r
10000
50 sec
0.33 sec
OOM
OOM
OOM
OOM
TIGER-Alaska 93366
3.7 h's
2.2 sec
OOM
OOM
OOM
0OM
Results. The runtimes reported in Table 7 confirm our expectation: BASEPLANE is the only model which can scale up to all datasets. Indeed, both ESAN and PPGN fail on TIGER-Alaska-ln 10K and TIGER-ABE AARR-Alasaa9955 99K.. Somewhat surprisingly, ESAN training time is slower than PPGN training time
24

---

Table BASEPLANE ablation study on ZINC. Each component is essential achieve the reported performance. The use of bi- and triconnected components yields substantial improvements. Aggre- gating over direct neighbours in the update equation remains important.
Models
ZINC MAE
BASEPLANE (original)
0.076 0.003
BASEPLANE (no readout)
0.079 0.002
BASEPLANEE (no CUTENC)
0.079 0.003
BASEPLANE (no neighbours)
0.099+ 0.004
BASEPLANE (only BIENC)
0.097 0.002
BASEPLANE (only TRIENC)
0.092 0.003
on RIGER-Alasker 2K which is likely due to the fact that the maximal degree of TIGER-Allska-- 620, which the ESAN algorithm depends on. BASEPLANE very fast for training with the main bottleneck being one-off vre-procesiigg This highlights that BASEPLANE is a highly efficient option for inference on large-scale graphs compared to subgraph or higher-order alternatives.
C An ablation study on ZINC
We additionally conduct extensive ablation studies on each component in our model update equation using the ZINC 12k dataset. We report the final results in Table 8 The setup and the main findings can be summarized as follows:
BASEPLANE (no readout); We removed the global readout term from the update formula and MAE worsened by 0.003.
BASEPLANE (no CutEnc): We removed the node from the update formula and MAE worsened by 0.003.
BASEPLANE (no neighbors): We additionally removed the neighbor aggregation from the update formula and MAE worsened by 0.023.
BASEPLANE (only BiEnc): We only used the triconnected components for the update formula and MAE worsened by 0.021.
BASEPLANE (only TriEnc): We only used the triconnected components for the update formula and MAE worsened by 0.016.
Hence, BasePlanE: significantly benefits from each of its components: the combination of standard message passing with component decompositions is essential to obtaining reported results.
D Further experimental details
D.I
Link to code
The code for experiments, well instructions to reproduce results and set up dependencies, can be found at this GitHub repository: https:://githi: com Mamm/Z2SSnnn//Part.
D.2 Computational resources
We run experiments on 4 cores from Intel Xeon Platinum 8268 CPU 2.90GHz with 32GB RAM. In Table g report the approximate time to train BASEPLANE model on each dataset and with each tuned hidden dimension value.
D.3 E-BASEPLANE architecture
E-BASEPLANE builds on BASEPLANE, and additionally processes edge features within the input graph. To this end, it supersedes the original BASEPLANE update equations for SPQR components
25

---

Table 9: Approximate Training Time for BASEPLANE.
Dataset Name
Hidden Dimension
Training Time (hours)
QM9cc cc MolHIV
32
2.5
64
QM9
128
25
64
ZINC(122)
128
ZINC(Full)
128
45
EXP
32
0.2
and nodes with the following analogs:
w
6C MLP
MLP(h (E-1) (t-1)
[[1l [P<a)))p)))) and
h f(() (g) (2)
1e-1) Σ
(8) (8-1)
(h!
(h | (( || 02
(2) Σ n(--))
9s
VEN.
VEV
93
(hg
(t-1)
Σ
h
94 h
(t-1)
Σ CE
BE
where hij h (i. E and the ones vector (1d) otherwise
D.4 Training setups
4k
3k
# Graphs
2k
1k
0
0.2
0.4
0.6
0.8
Normalized CC
Figure 5: Normalized clustering coefficient distribution of QM9cc-
Graph classification on EXP We follow the same protocol the original work: we use 10-fold cross validation on the dataset, train BASEPLANE on each fold for epochs using the Adam 39 optimizer with a learning rate of 10-3 and binary cross entropy loss.
Graph classification P3R. We follow very similar protocol to the one in EXP: we use 10-fold
cross validation, where we train BASEPLANE for 100 epochs using the Adam 39 optimizer with learning rate of 10-3 and cross entropy loss.
Clustering coefficient of QM9 graphs. To train all baselines, we use the Adam optimizer with a
learning rate from (10-3 3, 10040 43. and train all models for 100 epochs using batch size of 256 and L2 loss. We report the overall label distribution of normalized clustering coefficients on QM9 graphs in Figure
Graph classification on MolHIV We instantiate E-BASEPLANE with an embedding dimension of 64 and positional encoding dimensionality of 16. We further tune the number of layers within the
26

---

set {2, 3) and use a dropout probability from the set {0, 0.25, 0.5, 0.66). Furthermore, we train our models with the Adam optimizer [39,, with constant learning rate of 10-3 Finally, we perform training with batch size of 256 and train for 300 epochs.
Graph regression QM9. As standard, train E- E-BASEPLANE using mean squared emror (MSE) and report mean absolute error (MAE) on the test set. For training E-BASEPLANE, we tune the learning rate from the set {10-3, 5 10=4] with the Adam optimizer, and adopt learning rate decay of 0.7 every 25 epochs. Furthermore, we use a batch size of 256, 128-dimensional node embeddings, and 32-dimensional positional encoding.
Graph regression on ZINC. In all experiments, we use a node embedding dimensionality from the set (64, 128). use 3 message passing layers, and 16-dimensional positional encoding vectors. We train both BASEPLANE. and E.- E-BASEPLANE. with the Adam optimizer [39] using a learning rate from the set {10-3, 5 10-1, 10-1), and follow decay strategy where the learning rate decays by a factor of 2 for every 25 epochs where validation loss does not improve. We train using a batch size of 256 in all experiments, and run training using LI loss for 500 epochs the ZINC subset, and for 200 epochs on the full ZINC dataset.
27


Reviews:
[{"review_id": "3fJLDDz8tM", "reviewer": "Reviewer_fYDw", "summary": "Message passing based neural network is well-known for its limited expressivity of identifying graphs, while higher order neural network like  IGNs and SetGNNs are not scalable. Instead of trying to solve complete invariant for any graphs, this paper focuses on finding complete invariant for planar graphs. The author revisited the literature of the complete graph isomorphism test for planar graphs, which does hierarchical graph encoding based on block cut tree and SPQR tree (that decomposes a graph into k-connected components iteratively with k=1,2,3). Furthermore, the author proposes an neural network variant that aligns with the planar graph isomorphism test procedure, and proved that it is theoretically compete invariant for planar graphs. The author shows the advantage of these methods over simulation datasets as well as real-world datasets.", "questions": "I listed all suggestions and questions in weakness. \nWhile this paper is interesting, I hope some important problems can be improved during the rebuttal period.", "limitations": "The main limitation is that the designed architecture relies on the fixed top-down graph decomposition method for planar graph. The designed architecture should at least to be able to run all graphs while being incomplete graph invariant. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Given planar graphs are widely appeared in real-world (road networks, circuits, moleculers and so on), designing an efficient graph neural network while still be expressive enough is an important problem (Powerful than 3-FWL but more efficient than ). The author makes a first step by revisiting planar graph isomorphism test. The contribution and its foundation is solid. \n\n2. As planar graph isomorphism test makes use of hierachical decomposition in a top-down manner and then encode each components in a bottom-up manner, the author's proposed neural network is kind of bottom-up hierachical graph encoding. The direction of hierarchical graph representation learning is promising and deserves more attention, although being a hard direction. \n\n3. The designing of neural network architecture clearly follows the procedure, is well supported by planar graph isomorphism test theory. ", "weaknesses": "1. The presentation is not clear enough, the author better provide a good figure to illustrate the hierachical steps clearly to help the reader understand the main idea in a minute. \n\n2. Some unclear notations, such as line 232, tilde h_u^(l).\n\n3. Very importantly, the paper lacks the comprehensive complexity analysis, giving the goal of this paper is designing a powerful but also efficient method comparing with 3-FWL. Also, the author should discuss the impact of using the procedure of graph decomposition inside planar graph isomorphism test (the top-down step). First, the top-down step is kind of preprocessing that needs for the designed neural network which may introduces additional runtime and computational complexity. Second, as the top-down step is highly aligned with planar graph, it doesn't support other type of graphs.   \n\n4. Although the design of neural network tries to follow the planar graph isomorphism test closely, the author should discuss and do some ablation study over these designs. \n\n5. Experimental step is too vague and unclear. For all experiments, the description of experimental setup is incomplete. The hyperparameter is set completely with a single number and no discussion of hyperparameter tuning for different methods. It is unfair for baselines to use the same hyperparameter as the proposed method. The author should do hyperparameter tuning for all methods properly. \n\n5. Baselines are not SOTA. Only ESAN is used, while other recent baselines like SetGNN (Lingxiao Zhao, et al.) and SSWL (Bohang Zhang, et al. 2023) should be considered. Also I strongly recommend the author to tune hyperparameter in a systematic way. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback, and respond to their main points below:\n\n> The presentation is not clear enough, the author better provide a good figure to illustrate the hierachical steps clearly to help the reader understand the main idea in a minute.\n\nFollowing your suggestion, we added a figure visualising the PlanE pipeline, which can be found as Figure 1 in our response file. This figure shows the graph decomposition and the corresponding encoding steps. Please let us know if you have any further suggestions, and we will do our best to accommodate these.\n\n> Some unclear notations, such as line 232, tilde h_u^(l).\n\nThis is indeed a typo. We corrected this to $\\mathbf{h}_{\\gamma_u}^{(\\ell)}$.\n\n> Very importantly, the paper lacks the comprehensive complexity analysis, giving the goal of this paper is designing a powerful but also efficient method comparing with 3-FWL. \n\nPlease note that the paper includes a dedicated complexity analysis in Appendix A, which grounds the asymptotic efficiency of BasePlanE. The runtime of BasePlanE is $O(|V| d^2)$ with a (one-off) pre-processing time $O(|V|^2)$. In practical terms, this makes BasePlanE linear in the number of graph nodes after preprocessing. This is very scalable as opposed to 3-FWL (or 4-WL) which requires about $O(|V|^4  \\log |V|)$ steps to reach a stable coloring. Following your feedback, we added this explanation to the main paper.\n\nTo validate this empirically, we conduct a runtime experiment on real-world planar graphs. We compare the wallclock time of BasePlanE and 2-FWL-expressive PPGN. We observed that both the pre-processing and inference of BasePlanE run efficiently and scale very well, whereas PPGN quickly fails to run for larger graphs. This highlights that PlanE is a highly efficient option for inference on large-scale graphs compared to higher-order alternatives. We report the full runtime results in Table 3 of  *response.pdf*, and describe our findings in detail in the global response. \n\n> Also, the author should discuss the impact of using the procedure of graph decomposition inside planar graph isomorphism test (the top-down step). First, the top-down step is kind of preprocessing that needs for the designed neural network which may introduces additional runtime and computational complexity.\n\nWe discuss the runtime complexity of the decomposition step in Appendix A. In essence, we emulate the classical Weinberg algorithm in our pre-processing to obtain all necessary components, and this incurs a *one-time, worst-case* pre-processing cost of $O(|V|^2)$. This worst-case applies only when the *entire graph is a single tri-connected component*, which is rare in practice. \n\n> Second, as the top-down step is highly aligned with planar graph, it doesn't support other type of graphs.\n\nYes: BasePlanE is explicitly aligned with KHC, and does not immediately apply beyond planar graphs as stated in our limitations section. However, our main contribution is to develop a specialized, complete, and learnable network to efficiently learn functions over planar graphs. While our work *can* be applied to other graphs with simple modifications, this will either come at the expense of (i) completeness or (ii) efficiency. If we forgo the completeness criteria (as it is the case for existing GNNs), then PlanE can easily be extended to general graphs by choosing appropriate encoders for TriEnc and BiEnc. The resulting model will not be complete but still very expressive, since most existing models cannot even detect biconnectivity; see, e.g., Zhang et al. (2023). \n\nThe study of graph components has been very influential in graph theory, but remains much less explored in the context of graph ML. Hence, we think our work paves the way for designing powerful architectures, which additionally exploit different graph components. \n\n> Although the design of neural network tries to follow the planar graph isomorphism test closely, the author should discuss and do some ablation study over these designs.\n\nThanks for this! We experimented with several simplifications of BasePlanE on ZINC. In summary, we observed  that BasePlanE substantially benefits from each of the components in its message passing update. Indeed, dropping any individual component leads to loss of performance. Moreover, the combination of standard message passing with KHC component decompositions proved essential to our results. Hence, each component is ultimately beneficial within the overall PlanE framework. We provide a comprehensive discussion on this experiment in our global response, and the full results can be found in Table 1 of *response.pdf* \n\n> Experimental step is too vague and unclear. For all experiments, the description of experimental setup is incomplete. The hyperparameter is set completely with a single number and no discussion of hyperparameter tuning for different methods. It is unfair for baselines to use the same hyperparameter as the proposed method. The author should do hyperparameter tuning for all methods properly.\n\nAll details of our experimental setup are reported in the appendix.  Based on your feedback, we included these details into the main body.  We use exactly the same hyperparameter search protocols from the literature for each dataset for fairness with all models. This is actually constraining our own model’s tuning, as opposed to the other way around.\n\n> Baselines are not SOTA. Only ESAN is used, while other recent baselines like SetGNN (Lingxiao Zhao, et al.) and SSWL (Bohang Zhang, et al. 2023) should be considered. \n\nThanks for bringing these to our attention! We are happy to include these in the next version of our work.\n\n> Also I strongly recommend the author to tune hyperparameter in a systematic way.\n\nWe understand your concern, but we were systematic with the experimental setup, as detailed in our response. "}, {"review_id": "AeYxbr4QjM", "reviewer": "Reviewer_fXaJ", "summary": "This paper improves the graph isonophism inspired GNN design for a particular type of graph, planar graphs.\n\nIt utilizes KHC algorithm to generate a symbolic code for each graph. Follow the sequence, they apply GNN to recursively get the whole graph representation, which shall have the good property to be invariant.\n\nThe results show good performance than some prior baselines such as GIN.", "questions": "The authors mention the message passing and the KHC algorithm could be run in parallel, but I guess it means when you do GPU calculation you could do KHC on CPU for the next batch? Could the authors elaborate this part?", "limitations": "THe authors include a limitation statement,.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The paper levereages existing algorithm for isomorphism testing of planar graph, which is both effective and efficient;\n\n2. The authors prove that there exist a parametrization of GNN followed their message passing order that could distinguish any two planar graphs.\n\n3. Empirical results on chemical graphs show their advantage for real-world graphs.", "weaknesses": "My major concern for this papaer is that the presentation makes it really hard to understand the algorithm.\n\nIn sec 4 you define CODE, but I didn't see where you utilize these codes in the algorithm? Seem that all you utilize is the sequence of walk and the results of SPQR. It's very hard for me to understand what each notation is referring to (is it a node or a subgraph or a sequence). Also I don't see the definition of X.\n\nI highly suggest the authors improve the sec 4 & 5 to make it easier to understand what you did in this algorithm. It would be better to add a pseudocode for illustration. \n\nAlso, as you claim the achieve efficient calculation, it's better to show the time & memory usage for you to train & infer some graph datasets, especially over some larger graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We respond to your main points below:\n\n> My major concern for this papaer is that the presentation makes it really hard to understand the algorithm.\n\nThanks for raising this point. We have now included a figure visualising the full decomposition and encoding process. This is Figure 1 and can be found in *response.pdf*.  We have also added discussions on complexity analysis as well as experimental setup in the main paper. Please refer to the global response for more information.\n\n> In sec 4 you define CODE, but I didn't see where you utilize these codes in the algorithm? Seem that all you utilize is the sequence of walk and the results of SPQR.\n\nYes, we do not directly use CODEs as part of our model, but instead build on CODE to prove completeness results. In our proofs, we show how our model can yield embeddings which are in bijection with the corresponding codes of the formal Weinberg algorithm. This is similar to the GNN expressiveness results: every (maximally expressive) GNN layer aligns with a step of 1-WL algorithm if the computed node embeddings refine the 1-WL hash and vice versa. Therefore, CODEs can be seen as a meaningful abstraction through which alignment with the classical planarity algorithm can be explained.\n\n> It's very hard for me to understand what each notation is referring to (is it a node or a subgraph or a sequence).\n\nWe will clarify all these definitions in the paper. Please let us know if there are any particular aspects of our notation you would like us to address.\n\n>  Also I don't see the definition of X.\n\nWe define this on page 3: $\\chi(u)$ denotes the set of the children of node $u$.\n\n> I highly suggest the authors improve the sec 4 & 5 to make it easier to understand what you did in this algorithm. It would be better to add a pseudocode for illustration.\n\nThanks for the suggestion! We have added an illustrative figure visualizing the steps and intermediate outputs of our model, which we hope will improve these sections. This figure can be found as Figure 1 in our *response.pdf*. We will also provide more information on runtime, component designs, and experimental setup in the main paper. We considered adding pseudo-code as per your suggestion, but found this to be harder to follow than the overall figure. \n\n> Also, as you claim the achieve efficient calculation, it's better to show the time & memory usage for you to train & infer some graph datasets, especially over some larger graphs.\n\nThank you! To validate this empirically, we conduct a runtime experiment on real-world planar graphs. We compare the wall-clock time of BasePlanE and 2-FWL-expressive PPGN. We observed that both the pre-processing and inference of BasePlanE run efficiently and scale very well, whereas PPGN quickly fails to run for larger graphs. This highlights that PlanE is a highly efficient option for inference on large-scale graphs compared to higher-order alternatives. We report the full runtime results in Table 3 of  *response.pdf*, and describe our findings in detail in the global response. \n\nPlease also note that the paper includes a dedicated complexity analysis in Appendix A, which stated the asymptotic efficiency of BasePlanE. The runtime of BasePlanE is $O(|V|  d^2)$ with a (one-off) pre-processing time $O(|V|^2)$. In practical terms, this makes BasePlanE linear in the number of graph nodes after pre-processing. This is very scalable as opposed to 3-FWL (or 4-WL) which requires about $O(|V|^4 \\log |V|)$ steps to reach a stable coloring. We added this explanation to the main paper. \n\n> The authors mention the message passing and the KHC algorithm could be run in parallel, but I guess it means when you do GPU calculation you could do KHC on CPU for the next batch? Could the authors elaborate this part?\n\nThank you for the question. We assume you refer to the statement on lines 203-204 (page 5). We meant the following with this statement: there is a parallel in the *ideas* between the component code generations of KHC, and the encoders of PlanE. \n\nCoincidentally, however, paralel computability is a very good point: it is indeed possible to parallelize the batches in the way you point out. Furthermore, it could be possible to parallelize the KHC pre-processing for a single graph instance, by evaluating the lexicographically smallest TriCode in parallel (which is the quadratic bottleneck in the KHC algorithm). We will integrate this in the discussion of the runtime."}, {"review_id": "oQTeXu7U4O", "reviewer": "Reviewer_hVMw", "summary": "This work focuses on enhancing the representation power of GNNs in terms of distinguishing non-isomorphic graphs. Inspired by the classical planar graph isomorphism algorithm, the paper designs architectures within the proposed PLANE framework for learning complete invariants of planar graphs. The proposed framework achieves scalability while producing strong performance on planar graph benchmarks.", "questions": "See Weakness.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. In contrast to previous approaches that cannot strike a balance between algorithmic efficiency and representation power, the proposed framework, PLANE, can efficiently learn isomorphism-complete invariant functions for planar graphs.\n\n2. The architectural designs within the PLANE framework draw inspiration from classic planar graph isomorphism algorithms and can provably distinguish between any pair of non-isomorphic planar graphs.\n\n3. The efficacy of the proposed framework is validated through extensive experiments conducted on both synthetic datasets and real-world benchmarks, further highlighting its effectiveness in practical scenarios.", "weaknesses": "1. While the synthetic datasets used in the study provide some insights into the theoretical power of the proposed framework, they may not fully capture its potential. Notably, the clustering coefficient and EXP datasets can be easily handled by a class of models known as subgraph GNNs ([1, 2], and [7] in the main paper), which can be efficient enough [3]. To showcase the representation power of the proposed framework, it is recommended to include additional datasets, such as the strongly regular graphs used in CWN ([9] in the main paper) or generate planar graph datasets.\n\n2. Furthermore, it is important to report the runtime of the proposed framework, including the preparation time (e.g., time to generate the BlockCUT or SPQR trees) and the overall runtime encompassing training and inference. Comparisons should be made with existing models, including the classic MPNN and baseline models like ESAN, to demonstrate the efficiency of the proposed framework.\n\n[1] You J, Gomes-Selman J M, Ying R, et al. Identity-aware graph neural networks. AAAI 2021.\n\n[2] Zhang M, Li P. Nested graph neural networks. NeurIPS 2021.\n\n[3] Zhao L, Jin W, Akoglu L, et al. From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness. ICLR 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. We respond to your points below:\n\n> While the synthetic datasets used in the study provide some insights into the theoretical power of the proposed framework, they may not fully capture its potential. Notably, the clustering coefficient and EXP datasets can be easily handled by a class of models known as subgraph GNNs ([1, 2], and [7] in the main paper), which can be efficient enough [3]. To showcase the representation power of the proposed framework, it is recommended to include additional datasets, such as the strongly regular graphs used in CWN ([9] in the main paper) or generate planar graph datasets.\n\nThanks for this suggestion! We agree that running our model on larger (synthetic) graphs would further demonstrate the benefits of our specialized approach. Please note that we sought to use strongly regular graphs as in CWN, but there are only 7 strongly regular planar graphs, which are in fact $\\text{K}_1$, $\\text{K}_2$, $\\text{K}_3$, $\\text{K}_4$, $\\text{C}_4$, $\\text{C}_5$, and $\\overline{3\\text{K}_2}$. However, these graphs are easily distinguishable by standard GNNs, as all but $\\text{C}_4$ and $\\text{K}_4$ have a different number of nodes, and the latter pair have a different number of edges, rendering the whole task trivial. \n\nAs a result, we designed a new synthetic dataset based on 3-regular planar graphs, and experimented with BasePlanE, GIN and PPGNs. In this experiment, we observed that GIN struggles to go beyond a random guess, whereas BasePlane and PPGNs perfectly solve the problem, achieving 100\\% accuracy. We provide the full experimental setup and details in the global response, and our results can be found in Table 2 of *response.pdf*. We hope that the inclusion of this new experiment addresses your concern.\n\n> Furthermore, it is important to report the runtime of the proposed framework, including the preparation time (e.g., time to generate the BlockCUT or SPQR trees) and the overall runtime encompassing training and inference. Comparisons should be made with existing models, including the classic MPNN and baseline models like ESAN, to demonstrate the efficiency of the proposed framework.\n\nThank you! We agree it is important to illustrate this, and following your feedback, we conduct a runtime experiment on real-world planar graphs. We compare the wall-clock time of BasePlanE and 2-FWL-expressive PPGN. We observed that both the pre-processing and inference of BasePlanE run efficiently and scale very well, whereas PPGN quickly fails to run for larger graphs. This highlights that PlanE is a highly efficient option for inference on large-scale graphs compared to higher-order alternatives. We report the full runtime results in Table 3 of  *response.pdf*, and describe our findings in detail in the global response. \n\nPlease note that the paper includes a dedicated complexity analysis in Appendix A, which stated the asymptotic efficiency of BasePlanE. The runtime of BasePlanE is $O(|V| d^2)$ with a (one-off) preprocessing time $O(|V|^2)$. In practical terms, this makes BasePlanE linear in the number of graph nodes after preprocessing. This is very scalable as opposed to 3-FWL (or 4-WL) which requires about $O(|V|^4 \\log |V|)$ steps to reach a stable coloring. We added this explanation to the main paper based on your feedback."}, {"review_id": "fhx3jusdD0", "reviewer": "Reviewer_o9ac", "summary": "The paper deals with supervised learning on the graphs. Conventional models of message passing Graph Neural Networks are known to be restricted in their expressivity by the 1-WL test for isomorphism. Although more expressive models like higher-order GNNs have been proposed, they are inefficient and also, are not able to generate complete invariants for all graphs. The authors in this paper, propose to specialise their study to a class of graphs for which complete invariants can be efficiently computed i.e. planar graphs. They propose “PLANE” framework based on the graph isomorphism algorithm for planar graphs. PLANE can learn complete invariants for planar graphs in an efficient way and experiments are shown to validate the promising nature of the proposed method.", "questions": "Please address the weaknesses", "limitations": "Not applicable since this is general method on graphs.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. The paper is well-motivated in finding complete invariants for a class of graphs i.e. planar graphs while remaining computationally efficient.\n1. The paper is well-written with most parts of the paper easy to follow. However, few more illustrations would help the reader.\n1. Experimental results are mixed, partly promising.", "weaknesses": "1. **Novelty:** The major problem with this paper is the lack of novel ideas or insights. It is well-known that planar graphs are solvable for isomorphism and algorithms exist to do that. This paper leverages the KHC algorithm in a straightforward manner. Presumably, simply running the KHC algorithm on graphs and using the generated codes as features would give similar results. What is the additional usefulness of learning almost exact same procedure with parameters is neither discussed nor shown with some empirical results. \n1. There are no insights in the theoretical analysis as well. Improved expressivity and the logarithmic steps are directly adaptable from the planar isomorphism algorithm.\n1. The experimental results are not sufficient to make a convincing case for the method. \n1.    It is not very insightful to compare with GCN/GIN since they are known to be restricted with 1-WL power for clustering co-efficients or other experiments. \n1.   However, if you could include other more expressive models and show improvement compared to these, that would be helpful. For example, 3-WL GNN(Maron et al. (2019)), PF-FGNN (Dupty et al. (2021)) should produce complete invariants as well. However, they are not specifically designed for planar graphs and PLANE method can give substantial improvements over these models on planar graphs, then it would make sense to use algorithms specialized for planar graphs.\n1.   Other synthetic datasets like strongly regular planar graphs can be used to validate the method as well.\n1.   Results on QM9 could be better analysed if comparison with other methods are provided or the units are same as used in Dimene​​t (Gasteiger et. al. (2019))\n\n**References:**\n+ [1] Maron et al.(2019). \"Provably powerful graph networks.\" Advances in neural information processing systems 32 \n+ [2] Dupty et al. (2021) \"PF-GNN: Differentiable particle filtering based approximation of universal graph representations.\" International Conference on Learning Representations.\n+ [3] Gasteiger et al. (2019). Directional Message Passing for Molecular Graphs. In International Conference on Learning Representations.\n\n**Overall**, \n\nI find it hard to see significant contributions from this paper although the motivation of finding specialized learning models for planar graphs is interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We address your concerns below.\n\n> Novelty: The major problem with this paper is the lack of novel ideas or insights….This paper leverages the KHC algorithm in a straightforward manner.”\n\nOur work generalizes the classical, KHC algorithm to a *learnable neural* model while maintaining completeness and theoretical guarantees. In effect, PlanE builds on KHC like MPNNs build on 1-WL. Indeed, MPNNs align with 1-WL while crucially learning features from data. PlanE achieves the same relative to KHC, with added complexity coming from mapping this more involved algorithm to learnable functions. This mapping is by no means straightforward, and requires a series of subtle decisions: Please see our response on our adaptation of KHC.\n\n> Presumably, simply running the KHC algorithm on graphs and using the generated codes as features would give similar results. What is the additional usefulness of learning almost exact same procedure with parameters is neither discussed nor shown with some empirical results. \n\nThe learnability of PlanE is *critical* vs KHC, just as MPNN learnability is critical vs 1-WL. MPNNs vastly outperform 1-WL on almost all real-world datasets as they can learn dataset-specific features while still having the 1-WL inductive bias. We are *not* learning the KHC procedure with parameters, but rather learn *component representations* and a *specific feature mapping*, while also aligning with KHC.\n\nTo make this more concrete, we conduct a dedicated ablation of BasePlanE on ZINC (cf. \tTable 1 of *response.pdf* and global response for details). There, we drop standard MPNN neighbor aggregation (which is not part of KHC), and show that BasePlanE degrades very significantly, despite being more faithful to KHC. We kindly ask the reviewer to take these into account.\n\n> There are no insights in the theoretical analysis as well. Improved expressivity and the logarithmic steps are directly adaptable from the planar isomorphism algorithm.\n\nThough PlanE builds on KHC, it does *not* emulate all its components one-to-one. For instance, we do not use the KHC interleaving component, as this does not map to a learnable function due to its intricate overrides (which overwrite component representations and *eliminate gradients*). Moreover, PlanE uses component and node representations, which are not in KHC, but are essential for learning due to local inductive bias.\n\nGiven these fundamental differences, we had to provide *novel proofs* for all our results. As a case in point, KHC only requires *one* step due to interleaves, whereas we show a logarithmic step bound for PlanE based on our learnable components. We are happy to elaborate more on this.\n\n> The experimental results are not sufficient to make a convincing case for the method.\n \nTo our knowledge, PlanE is the only method that is practically scalable and provably complete on planar graphs. Moreover, our results, obtained without any specific optimizations, are already competitive with specialized models, e.g., CIN on ZINC, and other methods, e.g., SPN on QM9.\n\n> It is not very insightful to compare with GCN/GIN since they are known to be restricted with 1-WL power for clustering co-efficients or other experiments.\n\nWe include GCN/GIN as baselines, analogously to their use in standard 1-WL expressiveness tests. For stronger comparisons, we include an expressive subgraph baseline, ESAN, which we outperform by roughly 40%.\n\n> However, if you could include other more expressive models and show improvement compared to these, that would be helpful. For example, 3-WL GNN(Maron et al. (2019)), PF-FGNN (Dupty et al. (2021)) should produce complete invariants as well. However, they are not specifically designed for planar graphs and PLANE method can give substantial improvements over these models on planar graphs, then it would make sense to use algorithms specialized for planar graphs.\n\nUnfortunately, this statement seems the result of a common confusion between the dimension counts of FWL and WL: Folklore $k$-WL (or, $k$-FWL in ML literature) is equivalent to oblivious $(k+1)$-WL. Kiefer et al. (2019) show that 3-FWL (e.g., oblivious 4-WL) is complete on planar graphs, and this dimension remains the best known to date. Hence, higher-order models with an established *3-FWL* result are complete on planar graphs. However, both 3-WL-GNNs and PPGNs only have *2-FWL* expressive power. Moreover, PF-GNN provides no such expressiveness result. None of these models is provably complete on planar graphs. In fact, we are not aware of an implementation of a 3-FWL model: we are happy to incorporate such models provided there is one. \n\n> Other synthetic datasets like strongly regular planar graphs can be used to validate the method as well.\n\nPlease note that we sought to use strongly regular graphs as in CWN, but there are only 7 strongly regular planar graphs, which are in fact $\\text{K}_1$, $\\text{K}_2$, $\\text{K}_3$, $\\text{K}_4$, $\\text{C}_4$, $\\text{C}_5$, and $\\overline{3\\text{K}_2}$. However, these graphs are easily distinguishable by standard GNNs, as all but $\\text{C}_4$ and $\\text{K}_4$ have a different number of nodes, and the latter pair have a different number of edges, rendering the whole task trivial.\n\nInstead, we propose a new synthetic dataset based on 3-regular planar graphs, and experiment with BasePlanE, GIN and PPGNs (see global response and Table 2 of *response.pdf*). There, GIN matches a random guess, while BasePlane and PPGNs perfectly solve the task. PPGNs can solve this task because these graphs are 2-FWL-distinguishable. \n\n> Results on QM9 could be better analysed if comparison with other methods are provided or the units are same as used in Dimene​​t (Gasteiger et. al. (2019))\n\nWe follow the QM9 setup of Alon et al. In this version, the regression quantities are scaled for more uniformity, and the baselines used are trained using different grids/splits than Dimenet. Hence, these two setups are not comparable."}, {"review_id": "BdHghLpXlq", "reviewer": "Reviewer_Wih2", "summary": "The paper proposes PLANE: a graph neural network which is complete on planar graphs. The idea behind this is very natural and well explained in the paper: while graphs in general are difficult to separate, and as a result standard GNNs cannot separate them, planar graphs can be separated in polynomial time, and are very common in applications. Therefore it is useful to have a complete algorithm for these graphs.", "questions": "Main question: The part about why we want GNNs complete for planar graphs is explained very well. What is not explained so well, I believe, is: given that there exist `graph isomorphism algorithms' for planar graphs, what is it that needs to be done to turn them into architectures, and what, in the high level, is your contribution here? What were the challenges?\n\nTechnical question: For a given graph, is the partition into maximal biconnected (or triconnected) components unique? What is the source for the information presented in lines 75-84 in page 2? No reference is given\n\nExperimental question: could you report how well both E-BasePlane and BasePlane did on all tasks?\n\nMinor typos and comments for authors use (no need to discuss this in rebuttal):\n\nThe usage of \\mathbb{C} is a notation for anything other than complex numbers is confusing. I would suggest redefining this to something else (e.g,. \\mathcal{C})\n\nPage 4 line 171: what are `two node dipole graphs'? explain?\n\nPage 7 line 278 `clustering coefficient'-what is this?\n\nIn Table 4 and Line 377 you use (E)-BasePlane and in other places E-BasePlane. If the adding of parenthesis is intentional you should explain what is meant by it.\n\nIn Table 4 bottom line there is a slanted font, different from the rest of the table. This also happens in the other tables occasionally. If this is intentional explain what it means, otherwise fix font to be consistent\n\n\n", "limitations": "Overall yes. It does not seem the method can handle node features, this could be added to the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "As noted above, the question addressed by the paper is very natural, and the provided method achieves good empirical results", "weaknesses": "I felt the algorithm was \n(a) very technically involved and difficult to understand \nand\n(b) did not seem very novel, or very much like an architecture for graphs: that is, most neural networks are composed of simple building blocks (convolutions). This is not the case here. Rather it seems like the authors took a planar graph isomorphism algorithm, and then somewhat superficially replaced hashing operations in the algorithm with continuous set valued operations. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback! We respond to your comments below: \n\n> Main question: The part about why we want GNNs complete for planar graphs is explained very well. What is not explained so well, I believe, is: given that there exist `graph isomorphism algorithms' for planar graphs, what is it that needs to be done to turn them into architectures, and what, in the high level, is your contribution here? What were the challenges?\n\nThe fundamental challenge is to turn a classical algorithm which is tailored for isomorphism testing on planar graphs into a general learning algorithm on planar graphs. In our context, the goal is to capture similarities between the graph structures along with the features. In fact, a learning algorithm needs to implicitly compute structural similarities, which is a harder problem than plain isomorphism testing. More concretely, the challenges we encountered can be summarized as follows: \n\n(1) How to encode cut nodes, biconnected components, and triconnected components in order to adequately update these representations to best capture the structural similarities? \n\nKHC does not keep track of node-level or component level representations. The codes can be of varying lengths and do not capture a notion of similarity. In contrast to this, we need these representations to be explicitly learned, as they indicate node-wise, component-wise, or graph-wise similarities.\n\n(2) How to integrate classical operations into meaningful computational layers without leading to optimization problems? \n\nKHC employs standard operations such as overriding, or interleaving, which have no natural counterpart in a learning algorithm: this is due to the fact that codes do not need to reflect similarity, unlike the hidden representations. This constraints the design space of our algorithm: we had to replace the interleave operation (an operation on the Block cut tree nodes) with a multi-layer update, and show that this suffices for completeness: we have shown logarithmically many layers suffice.\n\n(3) What kind of inductive biases are helpful in a learning algorithm which are not relevant for code generation of KHC?\n\nThere are operations in KHC which do not have a counterpart in PlanE, but the converse is also true: we consider node neighbor representations in the update for better local context and also a standard readout for better global context. The lack of these worsens our empirical results as it can be seen from our ablation study (Table 1 in response.pdf), whereas these have no importance for the KHC algorithm.\n\nAll in all, we revisited the KHC planarity algorithm, modified it in several non-trivial ways to arrive at a provably complete, learnable and scalable model PlanE, and the main challenge was  designing components to preserve the theoretical properties of KHC while also having the right inductive biases for graph ML.\n\n> Technical question: For a given graph, is the partition into maximal biconnected (or triconnected) components unique? What is the source for the information presented in lines 75-84 in page 2? No reference is given\n\nYes indeed, an undirected graph (even if not planar) can be decomposed into its maximal biconnected components in linear time and this decomposition is unique. This is from classical literature, e.g., *“Hopcroft and Tarjan (1973) Algorithm 447: efficient algorithms for graph manipulation.”* The same is true for triconnected components and SPQR trees, see, e.g., *“Gutwenger, C., Mutzel, P. (2001). A Linear Time Implementation of SPQR-Trees”* for a classical reference. We refer to these references and related literature regarding the definitions in the  mentioned paragraph.\n\n> Experimental question: could you report how well both E-BasePlane and BasePlane did on all tasks?\n\nAs per your request, we also reran E-BasePlane without edge features (which is equivalent to BasePlanE) on QM9. Since it doesn't use edge features, the results worsened, but interestingly, the results remain nevertheless very strong compared to the baselines. For reference, for all target properties on QM9,  BasePlanE is on average only 5.6\\% worse than E-BasePlanE. This shows a strong evidence on how well BasePlanE exploits structural information. We will report the results in the next version of our paper (as the table is very large to fit into our one-page rebuttal document)"}]

Author rebuttal:
We thank the reviewers for their comments. We have responded to each concern in detail in our individual responses. In this global response, we include a response file, *response.pdf*, containing the results of additional experiments for your reference. 
The changes made during the rebuttal can be summarized as follows:

1. **Overall figure (Reviewers fYDw, fXaJ):**
We provide a figure visualizing the PlanE pipeline in our response file, which details all the steps involved in our model’s computation. This figure shows the pre-processing steps, namely computing the block-cut and SPQR trees, and also illustrates the mapping from these to embeddings at all the different levels of our model, leading up to the final node-level representation update. We hope this figure provides a much clearer picture of our contribution.
2. **Runtime analysis (Reviewers fYDw, hVMw, o9ac):**

    * Theoretically, the runtime of BasePlanE is $O(|V| d^2)$ with a (one-off) pre-processing time $O(|V|^2)$. In practical terms, this makes BasePlanE linear in the number of graph nodes after preprocessing. This is very scalable as opposed to 3-FWL (or 4-WL) which requires about $O(|V|^4 \log |V|)$. 

    * To validate this empirically, we conduct a runtime experiment on real-world planar graphs based on the geographic faces of Alaska from the dataset TIGER, provided by the U.S. Census Bureau. The original dataset is TIGER-Alaska-93K and has 93366 nodes. We also extract the smaller datasets TIGER-Alaska-2K and TIGER-Alaska-10K, which are subsets of the original dataset with 2000 and 10000 nodes, respectively. We compare the wallclock time of BasePlanE and 2-FWL-expressive PPGN. We observed that both the pre-processing and inference of BasePlanE run efficiently and scale very well, whereas PPGN quickly fails to run for larger graphs. This highlights that PlanE is a highly efficient option for inference on large-scale graphs compared to higher-order alternatives. We report the full runtime results in Table 3 of  *response.pdf*.

3. **New expressiveness experiment (Reviewers fYDw, hVMw, o9ac):** 
We propose a new synthetic dataset based on 3-regular planar graphs, and experiment with BasePlanE, GIN and 2-FWL-expressive PPGN. For this experiment, we generated all 3-regular planar graphs of size 10, leading to exactly 9 non-isomorphic graphs. For each such graph, we generated 50 isomorphic graphs by permuting their nodes. The task is then to predict the correct class of an input graph, where the random accuracy is $\sim$11\%. We report accuracy results in Table 2 of our response file. As expected, GIN struggles to go beyond a random guess, whereas BasePlane and PPGNs easily solve the task, achieving 100\% accuracy. Note that PPGNs can solve this task because these graphs are 2-FWL-distinguishable. 

4. **Ablation experiments (Reviewers fYDw, o9ac):** 
We additionally conduct extensive ablation studies on each component in our model update equation using the ZINC 12k dataset. We report the final results in Table 1 of *response.pdf* and summarize them here:
    * *BasePlanE (no readout):* We removed the global readout term from the update formula and MAE worsened by 0.003.
    * *BasePlanE (no CutEnc):* We removed the cut node term from the update formula and MAE worsened by 0.003.
    * *BasePlanE (no neighbors):* We additionally removed the neighbor aggregation from the update formula and MAE worsened by 0.023. 
    * *BasePlanE (only BiEnc):* We only used the triconnected components for the update formula and MAE worsened by 0.021.
    * *BasePlanE (only TriEnc):* We only used the triconnected components for the update formula and MAE worsened by 0.016. 

    Hence, BasePlanE significantly benefits from each of its components: the combination of standard message passing with component decompositions is essential to obtaining our reported results. 

We hope that our answers address your concerns along with the new experiments. We are looking forward to a fruitful discussion period.


Meta-review: This paper focuses on the family of planar graphs and proposes a new GNN inspired by the classical planar graph isomorphism algorithm of Hopcroft and Tarjan. The proposed learning algorithm extends beyond the given algorithm while maintains the theoretical guarantee. Experiments on synthetic and real-world datasets validates the proposed solution. Despite some concerns regarding the novelty as the method is inspired by the classical algorithm, we still consider the contribution significant enough; it extends beyond the original algorithm by learning a graph representation that can be used broadly for different learning tasks.
Decision: Accept (poster)