Orbit-Equivariant Graph Neural Networks
Authors: Matthew Morris
Bernardo Cuenca Grau
Ian Horrocks
Venue: ICLR 2024 poster (2024)
Keywords: graph neural networks
equivariance
expressivity
graph orbits
Primary area: learning on graphs and other geometries & topologies
TL;DR: We define orbit-equivariance, a relaxation of equivariance, to enable solving a new class of problems and propose some orbit-equivariant GNNs

Abstract: Equivariance is an important structural property that is captured by architectures such as graph neural networks (GNNs). However, equivariant graph functions cannot produce different outputs for similar nodes, which may be undesirable when the function is trying to optimize some global graph property. In this paper, we define orbit-equivariance, a relaxation of equivariance which allows for such functions whilst retaining important structural inductive biases. We situate the property in the hierarchy of graph functions, define a taxonomy of orbit-equivariant functions, and provide four different ways to achieve non-equivariant GNNs. For each, we analyze their expressivity with respect to orbit-equivariance and evaluate them on two novel datasets, one of which stems from a real-world use-case of designing optimal bioisosteres.

Published as a conference paper at ICLR 2024
ORBIT- EQBIT-EQUVVARIAT GRAPH NEURAL NETWORKS
Matthew Morris, Bernardo Cuenca Grau, & Ian Horrocks Department of Computer Science University of Oxford (matthew mowris bernardo. . grau, iai.a.n...nrr horrocks) @cs. ox. ac..a..u uk
ABSTRACT
Equivariance is an important structural property that is captured by architectures such as graph neural networks (GNNs). However, equivariant graph functions cannot produce different outputs for similar nodes, which may be undesirable when the function is trying to optimize some global graph property. In this paper, we define orbit-equivariance, relaxation of equivariance which allows for such functions whilst retaining important structural inductive biases. We situate the property in the hierarchy of graph functions, define taxonomy of orbit-equivariant functions, and provide four different ways to achieve non-equivariant GNNs. For each, we analyze their expressivity with respect to orbit--quivariance and evaluate them on two novel datasets, one which stems from a real-world use-case designing optimal bioisosteres.
INTRODUCTION
Graph neural networks (Gilmer et al., 2017; Gori et al., 2005; Wu al., 2020) are class of neural models designed for learning functions on graphs which have been successfully applied across a wide range of domains, including chemistry (Li et al., 2018), computer vision (Wang et al., 2019), traffic (Yao et al., 2018), recommender systems (Ying et al., 2018), combinatorial optimization (Bengio al., 2021), and NLP (Marcheggiani et al., 2018). GNNs leverage local message-passing operations that are invariant to permutations so that the resulting output does not fundamentally depend on how the input graph is reordered. This strong inductive bias enables GNNs to effectively and efficiently learn functions combining local and global graph labels (Battaglia et al., 2018; Bronstein et al., 2021).
is well known that common GNNs are equivalent the Weisfeiler Leman (1-WL) graph coloring algorithm and are thus limited in the classes of non-isomorphic graphs they can distinguish (Morris al., 2019; Xu al., 2019). Different models have been proposed to address these limitations, including appending unique IDs (Dasoulas et al., 2020; Loukas, 2020; Morris et al., 2022) or random noise (Abboud et al., 2021; Sato et al., 2021) to node labels, random dropouts (Papp et al., 2021) 1), and augmenting node features message passing using graph-distance features (Li et al., 2020). Srinivasan & Ribeiro (2019) relate structural representations obtained by GNNs and node embed- dings. Zhang et al. (2021) introduce the 'labeling trick' framework learn maximally expressive representations for sets of nodes (e.g. for link prediction). Although significant advancements have been achieved, all these models are still designed with the primary objective of enhancing the or permutation-invarian functions.
expressiveness of GNNs in the context of permutation-cquivariae
As pointed out by Morris al. (2022), even GNNs with universal expressivity for equivariant functions cannot solve certain types of symmetry breaking graph problems. Equivariant functions cannot yield different outputs for similar nodes (i.e., structurally identical nodes with the same label). This presents problems in multi-agent scenarios (Morris et al., 2022) where similar agents in a communication graph might need take different actions to solve task (e.g., drones that need to split up to find a target). Similarly, if GNNs are used to transform molecules so to optimize molecular property, equivariant functions cannot transform similar atoms in different ways. An example such property is lipophilicity: the ability of a chemical compound to dissolve in fats, oils, and similar solvents. This is an important factor in drug design (Arnott & Planey, 2012; Broccatelli et al., 2018; Waring, 2010), as high lipophilicity often leads to undesirable effects (Hopkins et al., 2014; Obach et al., 2008). Figure illustrates how optimizing the lipophilicity of fluroxene molecule requires two out of three similar fluorine atoms to be replaced with chlorine and bromine atoms.

---

Published as a conference paper at ICLR 2024
FLUROXENE
Similar atoms
FC(CIXBr)COC=C cI LogP 2.4
Different outputs
LogP= 1.7
Molecular transformation (output molecule SMILES notation)
Figure 1: Non-equivariant molecular transformation that increases lipophilicity (LogP), where the nodes are labelled with the atom type, without positional information.
To tackle symmetry-breakinng problems, we advocate the adoption of functions that generate multiset of output labels for each equivalence class, called an orbit, formed by the node similarity relation; for instance, in Figure 1, the orbit of three fluorine atoms is replaced by multiset of three new atoms. The assignment of labels to specific nodes should be considered arbitrary because all nodes are fundamentally identical within the same orbit. Thus, more permissive property than equivariance is necessary, which we define as orbit- bibbi--quivariance This property stipulates that irrespective of how the input graph is reordered, the multiset of outputs for each distinct orbit should remain identical. This approach enables to address symmetry-breakinn problems while preserving the valuable inductive bias that "the manner which the graph is rearranged should not impact the outcome".
Our contributions in this paper are as follows. We define orbit-equivariance and place it in the hierarchy of node-labelling functions as strictly in-between equivariant and universal node-labelling functions. We introduce a property called max-orbit, which allows for further refinement of orbit-equivariant functions. We establish a connection between the 1-WL graph isomorphism test and the identification of orbits, using it to assess the capacity of GNNs to differentiate between the orbits within graph. We exploit these insights to examine four distinct GNN architectures, two of them novel, which are capable of learning non-equivariant functions and examine the theoretical expressivity of each architecture. Additionally, we define a custom loss function designed to facilitate the training of orbit-equivariant GNNs. To evaluate the performance of our models, we conduct The former
empirical assessments on two novel datasets: Bioisostere and Alchemy-Max-Orhe scenario involving the optimization of drug effectiveness. Neither of these tasks can be fully addressed using equivariant functions, but both can be tackled with the aid of an orbit-equivariant function. Full proofs for all our technical results are given Appendix
stems from
BACKGROUND
Graphs A labelled graph G is a triple (V, E, A), where V(G) is finite set of nodes, E(G) S {(v, w) | v, w E (G)) is set of directed edges, and A: VGG + L is an assignment of labels from the codomain IL each node. For u E (G),, A(w) the label (also known as an attribute, or feature) of v. For ease of notation, we let V(G) 21,2.... n) for G' with nodes and denote A(u) as G.. A graph is undirected if ( is symmetric. permutation
permutation on a set X a bijection o : + X. A tuple (II, ..., X..) yields the tuple (o(x)), (x.)). A permutation
graph
G yields the graph == σ G, where V(H) = (G),, E(H) = {(a(v), aw))) (v. w) E E(G)), and G, Ho)r) for each v E V(G). An automorphism of G is permutation
G satisfying G = G. Nodes v, E V(G) are similar if there is an automorphism of G such that (v) w. Node similarity induces an equivalence relation on VG),, where each equivalence class is an orbit. The set RRG) of orbits of G forms partition of (G)). Figure 2 depicts an example of graph orbits.
Equivariance Permutation equivariance is an important property for models realising functions on graphs (Battaglia et al., 2018; Bronstein al., 2021). Intuitively, if the function has an output for each node, then permuting the nodes of the input should be equivalent to applying the same permutation to the output values (see Figure 3). A node-labelling function f maps each G (V, E, A) in its domain with VGG) = {1, 2, .... n to an assignment f f(G) E L of the nodes of G to values from the
Ithoughh in this paper we focus node labels only, anticipate that our definitions and results will extend seamlessly to graphs with edge and global labels.
2

---

Published as a conference paper at ICLR 2024
f(G)
f(G)
G
f(oo
G)
Equal
Figure 2: Graph with nodes colored by orbit.
Figure 3: Example of an equivariant function f.
codomain L. Node-labelling function f domain D closed under permutation is equivariant if f(a G) = a f(G) holds for all G E D and permutations a on V(G).
Graph Neural Networks GNNs such GCNs (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), and GATs (Veličković et al., 2018) are commonly defined within the Message Passing framework (Gilmer al., 2017). GNN consists of multiple local pressage-passingg include global readouts (Barceló al., 2020). For layer and node v with label X the new label Am+1 is computed as Am fupuaee (A /ugge if ( w E (e) Fee (
layers that can
( w E V(G) H)) where (v) is all nodes with edges connecting to and Pm. 6m 8% are the sets of parameters of the update, aggregation, and readout functions for layer m. Parameters may be shared between layers,
e.g. 0g 01. The functions n f are permutation invariant. This definition can be extended to incorporate graphs with global and edge labels (Battaglia et al., 2018). Importantly, GNNs are equivariant node-labelling functions for graphs labelled with real vectors (Hamilton, 2020).
ORBIT-EQUIVARIANCY.
As discussed in Section equivariance may be too restrictive in applications where optimizing some graph-level property (such as lipophilicity) requires similar nodes be differentiated. Indeed, cquivariant functions will always produce the same output for nodes within the same graph orbit.
Proposition 1. Let f be equivariant node-labelling function and let G be labelled graph in its domain. If v, w E ((G are similar, then f()). = f(
We next introduce orbit- brbiit-quivarancc
suitable relaxation of equivariance that still retains its critical structural inductive biases (Battaglia et al., 2018; Bronstein al., 2021) while extending the range of problems that can solved. This is accomplished by mandating that, regardless of the permutation applied to the input graph, the multiset of outputs associated with each distinct graph orbit should not change.
Definition A node-labelling function I on domain D closed under permutation orbit-equivariant if. for all labelled graphs G E D, permutations a on (G),, and orbits R(G), it holds that l.f G)a()) u E = [f( r..
We now position orbit- cubivi-quvvriiccc within the hierarchy of node-labelling functions. We begin by demonstrating that not all node-labelling functions are orbit-equivariant In the following example, we define graphs with the vertex set V(G) = {1, 2, 3). Node colors represent their Boolean labels, where white represents 0 and gray signifies 1. While visually represented
graph, the output of each function corresponds to 3-tuple of node labels. Consider a node-labelling function f that exhibits the following behavior for distinct graphs G1, G2, G3 and assigns all other graphs to g!@l
2
2
3
3
3
3
2
2
G
G2:
G3:
3

---

Published as a conference paper at ICLR 2024
This function is not orbit-equivariant. Consider permutation d (2.) for which a GGG1 = G2, and consider orbit r = {1} of G1. Then (f(or-GGoa / e E = = [ {о} and ([()),, l Er] = ([(G))) {1]. So there exists an orbit R(G1) and permutation such that ff G1)a(1) |ver + [f(G)) ( Er..
For an example of an orbit-equivariant function that is not equivariant, consider the node-labelling function f that maps input graphs G1, G2, G3 as shown, and maps each other graph G {0)
2
2
3
3
3
2
2
G1:
G2:
G3:
We first show that orbit-equivariance holds for G1- There are two orbits G1, (2,3)
Consider the permutation 0 = {{1, 2), (2, 1), (3, 3) Note that G1 = G2 and 0 Cj. E r1 = {OB. and for r2, we have f.f(a Gi)a(o) v E r2] = ).(G)),, u E r2]l {0.13. J. similar argument holds for the other graphs and permutations. Thus, f orbit-equivariant. However, is not equivariant. For the same permutation a. {(a G1) J(G)) = (0, 0, 1) and a f(G1) = a. (0, 1.0) = 01,0,0). So ((o-G) # f(G1). Furthermore we can show that each equivariant function is orbit-equivarian.
For ri, we have f Gi)a(e) e E r = {f(Gi),
J(G2)
Proposition 2. All equivariant functions are orbit-equivarian, but not vice-versa. There exist node-labelling functions which are not orbit-qquivariant
We proceed to establish a taxonomy orbit-cquivarian functions, categorizing them according to the count of distinct values in the output for each orbit. This refined definition offers more granular characterization of urbit-qquivariant functions, facilitating the identification of functions that might be empirically challenging learn and aiding in the development of tools, particularly GNNs, for approximating such functions.
Definition 2. For a node gode-labelling function f on domain D, we define max-orbit(f) to be the maximum across all G D and orbits R(G) of the cardinality of the (S(G), r).
For any equivariant function f, max-orbit(f) any m E Zt, there an orbit-equivariant function f such that max mrxittrbi(f) = m, since there graphs (c.g. cycle graphs) with arbitrarily large orbits.
direct consequence of Proposition 1. For
Proposition 3. If f is orbit-equivaricn and max max-orbit(f) 1, then f is equivariant.
The proposition above illustrates that the only restriction lost when moving from equivariant to orbit-equivariant functions is the limitation of having a single value the output each orbit, which aligns with the intuition motivating orbit-equivarianee. The example below of a function f shows why max (oxx-orbi((f)
alone is not sufficient to obtain equivariance. Function maps input graphs G1, G2, G3 as shown, and maps each other graph G (0)1G), Certainly max-orbit(J) = 1, but the function is not equivariant, since for permutation
{(1,2), 2), (2, 1), (3,)),, flo G1) f(G2) = (0, 0, 0) and o f(G1) = o. (0, 1, = (1, 1), so f(o G1) # o f(G)
2
3
3
3
2
2
G₁:
Gz:
G3:
4 NON-EQUIVARIANT GNN ARCHITECTURES
In this section, we discuss four GNN architectures for solving orbit- problems which extend standard equivariant GNNs in way that independent from the specific details of the GNN.
4

---

Published as a conference paper at ICLR 2024
2
Assign labels within orbits
GNN
2
3
5
Equivalent to orbit-1-WL
m-Orbit- Transform or Orbit-Indiv
6
2
Figure 4: Architecture for constructing orbit-equivarian GNNs.
For each of these extensions, we provide a classification of their expressivity and in Appendix C. we analyze their computational complexity.
Before delving into the details of these architectures, we first argue that the 1-WL graph coloring algorithm (Morris al., 2021; Weisfeiler & Leman, 1968) for isomorphism testing can also be used to compute graph orbits. This is achieved by computing iterative recolorings in the usual way, and then using the final stable colorings to partition the nodes into their orbits (instead of comparing them to another histogram of colors as in the standard isomorphism testing use case). When I-WL is used this manner, we refer to it as orbil- that GNNs and 1-WL respectively model each other's 's computation, which implies that GNNs can distinguish between orbits if and only if orbit-
Theorems and 2 of Morris et al. (2019) prove
can. That is: for nodes v, w E V(G),, there exists GNN f such that f(v) # f(w) if and only if the final colors of and orbit-1-WI. is applied to G. Orbit-1-WI. sound but not complete: there exists a graph G and nodes v, E G such that orbit- 1- assigns the same colorings to and w, but and Such graphs are shown in Appendix B.3.
different when
not similar.
Theorem 1. If orbit- I-WL. assigns different colorings to u, v V(G), then u, u are not similar.
Analogously to 1-WL (Morris et al., 2019), there is strict hierarchy of orbit-k-WL algorithms such that for all 2 there are graphs for which orbit-k- WL correctly identifies the orbits but wibit-(k-)--Wi does not. This is proved in Appendix B.4.
We are now ready discuss and analyze four distinct GNN architectures that are able to capture non-equivariant functions. The first have been proposed in prior work.
(1) Unique-I--GNN (Dasoulas et al., 2020; Loukas, 2020; Morris et al., 2022): this extension deterministically appends unique IDD to the label of each node before the GNN is applied to the input graph.
(2) RNI-GNN (Abboud al., 2021; Sato et al., 2021): some independently sampled random noise is appended to the label of each node before the GNN is applied to the input graph; max pooling is used for the global readout fread in each GNN layer.
The remaining two architectures are novel and can be viewed as instantiations of the general approach illustrated in Figure where we first apply a standard GNN to the input graph, then compute the orbits using orbit-1-WL, and finally devise a mechanism for assigning labels to nodes within the identified orbits.
(3) Orbit-Indiv-GN- in this extension, the GNN is first applied to the input graph G as usual to yield foNN(G), Orbit- 1-L is subsequently used identify the orbits of G; then, for each orbit, unique ID from (1,.., .... m) is appended to each of the node labels, where m is the orbit size, yielding an updated labelled graph footit_indii (JanN )) A single MI.P is finally applied to every extended node label in parallel and hence the overall function is defined (fobbi indiv (foN)(G))).
(4) m SebiitTrranffrr-GGr description with an example depicted in Figure 5; in our description, we use ($number) to refer to markers in the example. A GNN (*1) is first applied to the input G to yield faNx (G) and the orbits computed using orbit-1-WEL WL: in the example,
this is a more advanced extension, and we illustrate its formal
demonstrate the model primarily using the orbit highlighted blue. Each vector faNN(G), has m (o + 1) components, where is the number of final output channels (often categories) and > is a parameter of the model; result,

---

Published as a conference paper at ICLR 2024
0+133
Blue nodos orbit
111.0, 0J.
10. 1.
(1, 0)
Orbit
(19)
(110)
(*10)
(11)
(10, 1. OL, [1. 00. 0.00000 01
[0. 1)
(1.
(1.
(111)
(1.0)
2
(1. 0)
([1. OJ, 1, [0. O))
(1,
Stop
GNN
(i1, 0J, O. 10, 0. 0))
(1.
fraun()) ([T, 0, [0. 1, oj
([1. 0, 0J. [0. 1, 9). [0. OD
(1. 0)
partition (1. 0,
(10, 1. [1. 00. 0.0
[0. 1)
pertition 2: (0. 1,9)
brackets
(22)
("3)
pertition (0, 1,
partitions
denote
01 0j. 10, 1, 9) (0.
(1.
p= 2: The argmax of partition is not change the label of node 2
==3 3: The argmax of parition not o, so update the label of node 3
10. 1)
[1.
(*4)
For p (2, 3):
for orbite, (5, 7) and (6)
(1.
(1.
(1.
(1.0)
(1,
[0. 1)
(1. 0)
(1. 0y
(1.0)
(0, 1) ("6)
Final output
(1))
(1. 0)
(1.0)
Figure 5: The transform operation a 3-Orbit- -NN with o = 2.
define m partitions
in the output of SCNN(G) each of them of size (o (0+1)
(+2). Then we apply ftansfoom to (GNN(G)
(G), ; follows.
1. Iterate through each E V(G), and set G, (GNN o 1]. where [0 o -1] denotes the vector slice from 0 to
(inclusive). This vector of size o (*3).
2. Iterate through each orbit R(G)) (+4) and each partition p (,, -..; min(m, Ir]) (*5). Select the p-th node v (*6) in orbit r, where r is sorted by ascending order of node index. Then, if argmax(Sesw
o o, G2 fCNN
1] (*7).
This yields a final model output of Stranstorm (JONN (G)) (*8). Since faNN is equivariant, for each orbit r E R(G) and for all nodes v, w E r. fONN G) = faNN( (G) Thus, the transformed output for an entire orbit is essentially contained in the output of foNN for any e E r. Intuitively, the first partition (GNN(G)) (*9) contains the default value for the orbit and each remaining partition value (GN (#10) represents that the label of a single node in the orbit should be swapped from the default to the given value. If the final channel of the partition (with index o) is the largest (*11), 1), this represents that the default should not be swapped out for the value in this partition. The motivation for this is that it aids the model in learning functions which are "nearly equivariant": i.e. ones in which within most orbits, most of the target labels within each orbit the same.
Theorem 2. The expressivity of our proposed models is as follows, where for a class of models X, the claim " XX is not equivariant" means that "there exists I E X such that f is not equivariant":
1. Unique-ID-GRi GNNs not orbit-equivariant and, for any fixed node-labelling function f: .,, + RK, where G, is the set of graphs with S n nodes.
approximate any
2. RNI-GNNs are equivariant in expectation and, for any fixed n, can approximate any equiv- ariant function f: Gr + Rn" with probability arbitrarily close (Abboud al., 2021; Morris et al., 2022). They can approximate some non non-equivariant and orbit-equivariant functions with probability arbitrarily close 1, but there exist RNI-GNNs which, with probability arbitrarily close to 1, are not rrbit-quuivaiian.
3. Orbit-Indiv-GNN GNNss are not equivariant but are orbit-equivarian on graphs whose orbits are distinguishable by orbit-I-WI. For any m Z,t, there exist Orbit-Indiv--Nn f with max max-orbit(f) > m.
4. m-Orbit- Transform-GNN nn-Orbit-Transfrmm-co orbits are distinguishable by orbit-I-WL. They have max (aaxxoorit(ff) S m and there exist m-Orbit-TTee --rbit-rransforme Transform-GGMi J with max-orbit(]) m.
f are not equivariant but orbit-equivariant graphs whose

---

Published as a conference paper at ICLR 2024
5 EXPERIMENTS
Loss We focus on categorical outputs in our experiments, so we adopt cross-entropy loss as our baseline. For the loss to be representative of the model performance for orbit-equivariant problems, however, we need to account for the fact that we now support a multiset of outputs for each orbit, and that treating multisets as vectors may lead to sub-optimal performance. Welleck et al. (2018) investigate loss functions for multiset prediction, but purely in the context of the multiset being a collection of sequential decisions made by a policy. Similarly to the method of Probst (2018), we use a deterministic algorithm to greedily pair up outputs and targets and then compute cross-entropy between them. Specifically, for each orbit, we sort the model outputs and target outputs by fixing some a-priori order upon the output categories, and then pair outputs and targets based on where they appear in the sorted lists. Computationally, this is On log n), so computing the loss is feasible even for large orbits. We refer to this method as orbit-sorting cross-entropy loss. For the m-Orbit- Transform-GNN models, loss is computed before the transform takes place, since the transform operation is not parameterised and does not require training. To obtain targets for the loss, we invert the transform operation on the ground truth outputs for the training set. This means that standard cross-entropy can be used, since the model is equivariant before the transform is applied. Full details on our novel loss function are given in Appendix C.4. We note that there are many other ways ((Zhu et al., 2016), for example) in which this problem could be approached, and leave it as future work. We focus on evaluating different models in our experiments, rather than different loss functions.
Datasets We propose a new dataset (Bioisostere) capturing a real-world use-case and new suite of synthetic datasets (Alchemy-Man) Max---tt) designed to test the ability of models to learn functions with different max-orbit values. Although synthetic, Alchemy- Maaeemy-------e Max-Orbit datasets consist of graphs obtained from world organic molecule data.
The task in Bioisostere is, given an input molecule graph, output a label for each node which represents either keeping the atom or swapping it out for some other particular atom, in such a way that the final resulting molecule has minimal lipophilicity; as discussed in Section 1, this is an important factor in drug design. Solving this task requires a non-equivariant function when an atom being swapped out comes from an orbit of size 2 2. To construct this dataset, retrieved 961 small drug molecules from ChEMBL (Mendez et al., 2019) and then used MMPDB (RDKit, 2023a) to compute many different bioisosteres for each molecule that each differ by at most one atom from the original molecule. Using RDKit (RDKit, 2023b), we computed the lipophilicity of each bioisostere and selected the one that yielded the lowest value as the target for each molecule. Of these molecules, only 588 actually require some swapping out of an atom to achieve minimal lipophilicity, and only 156 require a non-equivariant function. The function f required to solve the task is orbit-equivariant with max max-orbit(f) = 22
dataset is constructed using Alchemy (Chen et al., 2019; Morris et al., 2020), large dataset of organic molecules. All graphs without an orbit of size 2 m are removed and the dataset is then extended by augmenting the existing graphs, if it is not already large enough. Details on this process are in Appendix C.2. The task in the dataset is to identify the largest orbit(s) in the graph and, for each largest orbit, distribute the labels T == 1,, 1, 1,2,..... ..., m JI at random without replacement amongst the orbit's nodes, such that [T] coincides with the number of nodes
An Alchemy-Max-Orbite
in the orbit. Every node not part of a largest orbit should be assigned the label of O. Equivariant functions such as GNNs cannot solve any of the examples in the dataset. The function f required to solve the task is ebbi-equuvariiant with max max-orbit(f) m.
Methodology We perform our experiments on the Bioisostere, Alchemy-Max--rte Michemy-Max-Orbiceee datasets. We adopt GCNs (Kipf & Welling, 2016) as our baseline GNN to be augmented, since they are simple, effective, and still competitive in contemporary work (Frasca et al., 2022; Hou et al., 2022; Li et al., 2022; Rampášek et al., 2022). For each experiment, we train and test the following models: Unique-ID-GCN, RNI-GCN, Orbil-Indiv-GNN, and m-Orbitt- Transform-GCN, Pure GCNs are equivariant and thus cannot achieve better graph accuracy than 0 on the Maaeemy-Max-oo Orbit datasets. However, they can still solve some subset of the examples in Bioisostere, experiment is run 10 times, with different seeds, and 10% of the data is randomly left out of training to be used as test dataset. We report the mean and standard deviation across all seeds. We run
and
we include it baseline to how equivariant model performs. Every
7

---

Published as a conference paper at ICLR 2024
Table 1: Mean and standard deviation of final model accuracy percentage on the test datasets.
Dataset
Model
Graph Accuracy
Orbit Accuracy
Node Accuracy
Bioisostere
GCN
52.4 1 6.37
92.9 + 1.14
94.4 +: 0.79
(cross-entropy
Unique-I--GCN
66.1 1: 5.13
94.5 + 0.97
95.6 1: 0.62
loss)
RNI-GCN
63.6 + 4.29
93.9 = 0.86
95.1 0.76
Orbit-Indiv-GCN
69.9 + 4.68
96.3 0.49
57.1 + 6.43
93 0.99
94.1 = 0.79
Alchemy-
Unique-ID-GCN
20 + 4.57
79.9 + 2.01
77 1.52
Max-Orbit-2
RNI-GCN
0 0
74.5 = 1.7 87.5
75.2 + 1.66
(orbit-
Orbit-Indiv-Ge
51.9 + 4.38
90.6 1.12
cross-entropy)
2-Orbit-Transfom
47.9 + 6.45
86.8 = 1.53
85.1 = 1.66
Alchemy-
UniqueIID-GCN
66.8 7.15
84.8 + 2.97
95.4 + 1.07
Max-Orbit-6
RNI-GCN
44.9 7.19
78.5 3.39
91.4 1.47
(orbit-sorting Orbit-Indiv-GCN
83.4 + 4.22
88.9 2.71
97.1 1.46
cross-entropy)
6-Orbit-Transform
10.6 1 4.14
71.2 1 2.47
87.6 1 1.08
each experiment with standard cross-entropy loss and with orbit-sorting cross-entropy loss. Full hyperparameters for our experiments can be found in Appendix C.3. Accuracy is measured and reported in 3 ways: the average proportion of nodes for which the correct output predicted (node accuracy), the average proportion of orbits which have entirely correct predictions (orbit accuracy), and the proportion of graphs which were entirely solved (graph accuracy). Since are dealing with orbit-equivariant functions, accuracy is calculated by collecting the orbits of the graph and computing the multiset intersections of model and target outputs for each orbit.
Results Our main results are shown in Table 1 and full results are shown in Appendix C.S. In the plots, "max_ orbit_goon refers to --rrrrrrrraasfrmmm.. GCN.. Since we found that slightly better results were obtained for Bioisostere when standard cross-entropy is used, those results are shown, with orbit-sorting cross-entropy used for the other two datasets. Across all 3 datasets and metrics, Orbit-Indiv-GCN. consistently and definitively exhibited the best performance. GCNs exhibited the worst performance on Bioisostere and would have achieved an accuracy of O on the Alchemy- Max-Orbit datasets, highlighting the need for models that go beyond equivariance. Unique-ID-GCNs consistently outperformed RNI-GCNs, which aligns with the experiments of Morris et al. (2022) on non-equivariant problems. It is also interesting to note that, whilst RNI-GCNs achieved the 3rd highest test accuracy on Bioisostere, they had the highest accuracy on the training set, suggesting that the model is more inclined to overfit.
On the Alchemy-Max-Orbit- dataset, 2-Orbit-Transfomm Transform- GCNNs achieved comparable performance to Orbit-Indiv-GCNN whilst the other two models performed poorly. This suggests that the transfor- mation model can be useful certain tasks, when the max-orbit of the function is low. In contrast, the Alchemy-Max -ax--rbit--- dataset, 6-Orbit- Transform- Mannsfooon-Gsssss had by far the worst performance among all the models, demonstrating that the transformation becomes infeasible for large max-orbit sizes. This is expected, since the number of output channels required for the transformation is linear in the max-orbit. Overall, whilst Alchemy-Max Max-Orbit-2 has smaller max-orbits than the models tend to perform better on the latter dataset because there are fewer graphs in Alchemy that possess maximum orbit of 6 than those that possess a maximum orbit of 2, meaning that similar structures appear repeatedly when the Max-Orbit Orbit-6 graphs are augmented to extend the dataset.
Model performance on the test datasets during training are shown in Figure for the experiments using cross- cross-entropy loss, and in Figure for those using orbit-sorting cross-entropy loss. In addition to Moiit-Indi--GMM performing the best out of all the models, they also converge by far the fastest. We attribute this to their strong structural inductive bias: they are exactly orbit-equivarian whilst not deviating much from the provenly effective architecture of GCNs. Abboud et al. (2021); ) Morris et al. (2022) found that RNI-GCNs can be slow to converge, but Bioisostere, we find them to converge comparatively swiftly. A comparison between Figures and highlights the importance of using subit-sorting cross-entropy loss. The performance of Orbit- Transform-Ger since they are trained as equivariant models: this is an advantage unique to Orbit- Pransfomm-GCN. The models also do not show improvement Bioisostere when using orbit-sorting cross-entropy,
is mostly unaffected,
8

---

Published as a conference paper at ICLR 2024
nodel: eox. mox.orbit.gon rodel: miagpn
model: man man_orbit_aen
woded: mav_orbit_ggo
sodel: orbit Lodiv get
rodel: ordit_.rdvv.gon rodel: entugen sodel: uniqua_Id__een
vodel: orbit Indiy gon rodel: mnd gon
nodel: untaue..d..po 5d. rodel: pch
wodel: unique..d.gon
5.15
28
0A
033
5.1
0.2
02
5.05
Figure 6: Graph accuracy with standard error on the test datasets across all models using cross-entropy loss: Bioisostere (left), Aichemy-Ma--Orbit- (center), and Manteemy-Ma--Obbiiei (right).
vodel: unique, Ielaer model: ind_aen rottel: pon model: ewc_orbit Lugen
wodel: nax orbit gon
model: orbit, indiv_in rodel: gen =odol: unique
orbi inc
wodel: man, b-.oo
sodu1: uni.ue.11 11.
0.4
0.6
0.1
0.2
033
opoch
e00ch
26
Figure 7: Graph accuracy with standard error on the test datasets across all models using orbit-sorting cross-entropy: Bioisostere (left), Alchemy- Max-Orbit- (center), and Alchemy- Maatemy-Max-Oree - (right).
which is probably because each node from an orbit that to be swapped out is chosen deterministically to be the one with the lowest index. This is not the case for the Max-Orbit datasets.
6 CONCLUSION
We show the limits of equivariant functions when it comes to producing different outputs for similar nodes. We define a less restrictive property, orbil--quivariance, to address this issue while still retaining strong structural inductive bias and show where it lies in the hierarchy of node-labelling functions. We also provide a brief taxonomy of orbit-equivariant functions using a further property, max-orbit. We present four different ways extend GNNs to solve non-equivariant problems and analyze their expressivity. We evaluate these models on both real-world and synthetic datasets, finding that one of our novel models (Orbit-Indiv-GNN) exhibits the best performance in all scenarios. We also find that the use of a specialist loss function can be necessary for the models to train.
The novelty of orbit--quivariaace as a property provides considerable scope for future work in this area. Firstly, the idea of orbit-qquivariance can be generalized to other data structures besides graphs (Bronstein et al., 2021) and related to node embeddings (Srinivasan & Ribeiro, 2019). GNNs have also proven to be useful for aiding in designing optimal bioisosteres, but this is a complex task and deserves further investigation. Moreover, the establishment of orbit--quivariance as a formal property could lead to the identification of other problems that require non-equivariant and orbit-equivarian models to solve. Finally, there may be ways to design better, specially tailored orbit-equivariant GNNs to solve such problems.
Limitations Our work considers only graphs where the nodes are not individualized; this does not account for application domains where the nodes have noisy features that are almost identical, but not precisely. Our theorems focus on property satisfaction and there are open questions as to how expressive the new proposed models are. The scope of our experiments is restricted to datasets where non- -oueeiaivai functions are required. Furthermore, the Bioisostere dataset does not capture all aspects of actual drug design, since we only optimize for a single molecular property instead of many, and do not consider biological effects.

---

Published as a conference paper at ICLR 2024
7 ETHICS STATEMENT
We see no ethical concerns in our work. This is largely theoretical paper, and we see no potential negative societal impact of the theories or of the partieular applications. Our models and datasets do not have a high risk for misuse, so we are releasing them to the public. Furthermore, we did not use human subjects and did not need IRB approval. All papers and repositories have been cited and licenses explicitly mentioned for the software used.
8 REPRODUCIBILITY STATEMENT
Code, data, and instructions for how to reproduce our experimental results are given in the supple- mental material. Full model hyperparameters (including random seeds) are given in the appendix. Important training details are given in section 5 of the main paper, and full details are given in the appendices. Full details on the amount and type of compute used are given the appendix. All terminology and symbols are explicitly defined, and the assumptions are clearly stated across the paper, particularly sections and 4. Complete proofs are given in the appendices and intuitions given in the main paper.
ACKNOWLEDGMENTS
Matthew Morris is funded by an EPSRC scholarship (CS2122_EPSRC_____ 1339049). This work was also supported by the SIRIUS Centre for Scalable Data Access (Research Council of Norway, project 237889), Samsung Research UK. the EPSRC projects AnaLOG (EP/P025943/I), OASIS (EP/S032347/1), UKFIRES (EP/S019111/1 and ConCur (EP/V050869/)) The authors would like to acknowledge the use of the University of Oxford Advanced Research Computing (ARC) facility in carrying out this work http: / /dxx doi, org/10, 5281/ zenodo. 22558, as well as thank Ismail Ceylan for helpful etrly-stage discussions.
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2112-2118, 2021.
John A Arnott and Sonia Lobo Planey. The influence of lipophilicity in drug discovery and design. Expert opinion on drug discovery, 7(10):863-33 2012.
Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The
logical expressiveness of graph neural networks. In 8th International Conference Learning Representations (ICLR 2020), 2020.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 180::1800.00161 2018.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405 421, 2021.
Fabio Broccatelli, Ignacio Aliagas, and Hao Zheng. Why decreasing lipophilicity alone is often not a reliable strategy for extending iv half-life. ACS Medicinal Chemistry Letters, 96)):222-527, 2018.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 1344,, 2021.
Guangyong Chen, Pengfei Chen, Chang- Yu Hsich, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, et al. Alchemy: A quantum chemistry dataset for benchmarking models. arXiv preprint 1X06::906.00445 2019.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. International Joint Conference on Artificial Intelligence, pp. 2126-2132, 2020.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Jiarui Feng. Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. In Advances in Neural Information Processing Systems, 2022.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and ex- tending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31390, 2022.
Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference Digital libraries, pp. 89 08-998111 1998.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEFE International Joint Conference Neural Networks, 2005., volume 2, pp. 729-734, IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
11

---

Published as a conference paper at ICLR 2024
William L Hamilton. Graph representation learning. Synthesis Lectures Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
Andrew L Hopkins, György M Keserti Paul D Leeson, David C Rees, and Charles H Reynolds. The role of ligand efficiency metrics in drug discovery. Nature reviews Drug discovery, 13(2):105-22) 2014.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjje Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 594-604, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.022 0200000000297,,. 2016.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint wrXiv:1801.02144 2018.
Loic Landrieu and Martin Simonovsky. Large-scale point cloud semantic segmentation with super- point graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4558 4567, 2018.
Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, pp. 1-17, 2022.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-4478. 2020.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. In ICML, pp. 1-21, 2018.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. International Conference Learning Representations (ICLR), 2020.
D Marcheggiani and Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In EMNLP 2017- 2017-Conference on Empirical Methods in Natural Language Processing. Proceedings, pp. 1506-1515, 2017.
Diego Marcheggiani, Jasmijn Bastings, and Ivan Titov. Exploiting semanties in neural machine translation with graph convolutional networks. In Proceedings of NAACLLILL,, pp. 486-492, 2018.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000,
David Mendez, Anna Gaulton, Patrícia Bento, Jon Chambers, Marleen De Veij, Eloy Félix, María Paula Magariños, Juan F Mosquera, Prudence Mutowo, Michal Nowotka, et al. Chembl: towards direct deposition of bioassay data. Nucleic acids research, 47(D1):D930 290.DD9999--90,,,.- 2019.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. Advances neural information processing systems, 30, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs arXiv preprint arXiv:2007.08663, 2020.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck. Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint 2rXiv:21/2.09999 2021.
12

---

Published as a conference paper at ICLR 2024
Matthew Morris, Thomas D Barrett, and Arnu Pretorius. Universally expressive communication in multi-agent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS) 35, 2022.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pool- ing: Learning deep permutation-invariant functions for variable-size inputs. arXiv preprint arXiv:1811.01900, 2018.
R Scott Obach, Franco Lombardo, and Nigel J Waters. Trend analysis of a database of intravenous pharmacokinetic parameters in humans for 670 drug compounds. Drug Metabolism and Disposi- tion, 36(7):1385-14000 2008.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34:21997-22009, 2021.
Malte Probst. The set autoencoder: Unsupervised representation learning for sets. openreview, 2018.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, 15:14501-14515, 2022.
RDKit. Matched molecular pair database generation and analysis.
rdkit teiit//mppa /mmpdb, 2023a.
RDKit. Rdkit: Open-source cheminformatics. https://www.rdkkttt
2023b.
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), pp. 333-341. STAM, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data, Al magazine, 29(3):93-93, 2008
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference Learning Repre- sentations, 2019.
Gusi Te, Wei Hu, Amin Zheng, and Zongming Guo. Rgenn: Regularized graph enn for point cloud segmentation. In Proceedings of the 26th ACM international conference on Multimedia, pp- 746-754, 2018.
Amanda L Traud, Peter J Mucha, and Mason Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 391(16):4165-118) 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations (ICLR), 2018.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural pessage-passiigg Advances in neural information processing systems, 33: 15:14143-14155, 2020.
Cédric Vincent- Cuaz, Rémi Flamary, Marco Comeli, Titouan Vayer, and Nicolas Courty. Template based graph neural network with optimal transport distances. In NeurlPS 2022-36th Conference on Neural Information Processing Systems, 2022.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1-12, 2019.
Michael J Waring. Lipophilicity in drug discovery. Expert Opinion on Drug Discovery, 5(3):235-24 2010.
13

---

Published as a conference paper at ICLR 2024
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 199111.16, 1968.
Sean Welleck, Zixin Yao, Yu Gai, Jialin Mao, Zheng Zhang, and Kyunghyun Cho. Loss functions for multiset prediction. Advances in Neural Information Processing Systems, 31, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang. and S Yu Philip. comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, and Zhenhui Li. Deep multi-view spatial-temporal network for taxi demand prediction. Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovee. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983, 2018.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances Neural Information Processing Systems, 34:9061 1073, 2021.
Zhuotun Zhu, Xinggang Wang, Song Bai, Cong Yao, and Xiang Bai. Deep learning representation using autoencoder for 3d shape retrieval. Neurocomputing, 204:41-50, 2016.
14

---

Published as a conference paper at ICLR 2024
A PROOFS
A.1 PROPOSITION
Proposition. Let f be an equivariant node-labelling function and let G be labelled graph in its domain. If v, w E (G) are similar, then f(G). = f(G)w. w.
Proof. Define a to be a permutation that maps v - w, and maps other nodes such that a is an automorphism of G. Such permutation exists since v and w are similar. Since is automorphism, G = G. So we prove:
f(G). = (o- a. f(G)) lo f(a G)),
(identity permutation)
(equivariance) (a maps w - v) (a is an automorphism)
f(a G)w f(G)
A.2 PROPOSITION 2
Proposition. All equivariant functions are ebbbi--quivriiant, but not vice-versa. There exist node- labelling functions which not orbit-equivariant.
Proof. We prove the three claims of this proposition separately.
All equivariant functions are orbit-equivariant
Let node-labelling function f domain D be equivariant. Then for all labelled graphs and permutations on [( G) = a S(G). To prove that f is orbit-equivarian, choose arbitrary labelled graph G D, permutation on (G), and let E R(G) be any orbit of G. Then,
[f G)a(o) luer] ((o-1 f(a- G)), luer]
(permute vector)
-o |vEr] (f(G), Iver
(equivariance)
(inverse permutation)
Thus, f orbit-equivariant.
There orbit-equivariant functions which are not equivariant.
For an example of an orbit-equivariant function that is not equivariant, consider the node-labelling function J, defined on the set of all labelled graphs, that maps input graphs G1, G2, G3 as shown, and maps each other graph G to [O]IG).
2
2
3
3
2
2
G1:
G3
G3
This function is orbit-qquivariant There are orbits of G F1
[1), r2 {2, 3). Consider
the permutation = {(1, 2), (2, 1), (3,3)}. Note that a G G2 and G2 G,. For
Ti, we have [f(a G1)(() E ril = (f(G])) v r1 (O), and for r2, we have
(a G1)(()) / (r) [/(
10,
15

---

Published as a conference paper at ICLR 2024
Any permutation graph in D (G1, G2, G3) yields graph in D, and the only graphs that permute to a graph in D are the graphs in D. In other words, and G \ D are both closed under permutation, where 9 is the set of all labelled graphs. Each graph G E D has two orbits ri, 22. of size and respectively, with (,(()), c E r {O) and (f(G), p E r2)
(0. B. For (3), {1,2).
G1 (1), (2, for G2 (2), (1,3), and for G3,
Thus, following the same unfolding of the definition as above, we see that AG E D, V permutations on VG), for the corresponding orbit rı of G, have {/(o G)(()) m {.(G), lve
ri }
H and for 72, we have {.fl G)a()) u r2) = [f(G), v2 = (0.1).
Furthermore, each graph E G D has f(G) {0)IV()), and for any permutation on V(G), a. G = G D. so f(a G) [0) Thus, VG \ D, V permutations on V(G), Vr R(G). have (.(l G)o(e) E r (f(G), E r {(] r
Thus, f is orbit-equivariant, since the definition holds VG D and VG 9 \\D.
However, f is not equivariant. For the same permutation σ {(1.2), (2, (3. f(o G1) = f(G2) = (0, 0, 1) and f(G1) (0, 1, = (1, So f(o G1) # f(G1).
There exist node-labelling functions which are not orbit-equivariant.
Consider node- labeliing function f that exhibits the following behavior for distinct graphs G1, G2, G3 and assigns all other graphs G to {0} GI.
2
3
3
3
3
2
2
G1
G2:
G3:
This function is not orbit-equivariant. Consider permutation o = ((1,2), (2, 1), 3). for which
G G2, and consider orbit = (1) of G1. Then (((o-Gi)o()) v w E = [[ {0}
and (f())) J E [f(G [.. So there exists orbit E R(G and permutation such that fflo G))a()) v + (G() E
16

---

Published as a conference paper at ICLR 2024
A.3 PROPOSITION 3
Proposition. I is orbil-equivarianl and max (aax-orbi(()) = 1, then f is equivariant.
Proof. Let G be labelled graph in the domain of f and a a permutation on V(G). RTP: fla G) = a f(G).
Since max-orbit(f)
the maximum across all orbits R(G) of the number of unique values in ([()), rB is 1. Thus, Vr E R(G), Ve, Er, f(G), J(G) m.
Since f is orbit-equivariant
orbits r E R(G), [í(a Gl(()) |vr) = (S()), |vEr]
orbits r E R(G), Vu E, f(o Glao) = f(G).
(RHS multiset all equal) (all orbits all nodes)
= Vu E V(G), l'a ([a-Gi G)o()) = [(G),
+
Vu E V(G), (o flo G)), = I(G),
(permute vector)
+
E V(G), o f(o G)), = (a. f(G)).
EUE V(G), f(a -), = (a f(G)),
(inverse permutation)
f(o G) = f(G)
17

---

Published as a conference paper at ICLR 2024
A.4 THEOREM
Theorem. !forbit-I-WL assigns different colourings to u, E V(),, then u, are not similar.
Proof. We prove this by induction n. the number of iterations the orbit- 1-WL algorithm has taken. The orbit-I-WL. algorithm is given formally in Appendix B.I. The stated theorem thus becomes: "if orbit-1- 1-W assigns different colourings to nodes u, G after iterations, then they not similar".
Base case: n=0
If u, have different colourings after no iterations of orbit-1-WL, then they have different labels in the original graph. This implies that u and v are not similar, since any automorphism must be label-presss -reeeerres....g..
Inductive step: assume frue for n
Let On V(G) + C the colouring of after n iterations of orbit-1-Wi and similarly C after + 1 iterations. We have nodes u, G s.t. (n+1(u) Cn+1(v), and aim to prove that and are not similar.
Case 1: Cn(u) # Cn(v)
Then as assumed in the inductive step, and are not similar.
Case 2: Cu(u) Cn(v)
C (u) is computed by (n))(u) = h(C.(u), (Cn(we w N(u))), where the WL hash function. But then since Cn(u) = (v) and (u) * (n)i(t). (C.(w) w E ((w) + (C,(w) w E N(u)).
If [w)) + [N),,,, then and trivially not similar, since any automorphism must be edge- preserving. So assume that (u) [v)]. The above set inequality thus implies that there does not exist bijection (u) + (t) such that Ve E (u), C,(w) (Tw)).
Assume the contrary that u and are similar.
Then there exists an automorphism
+ G such that (u) v. This implics that Vei (u)) Ewa (vv) such that a(w1) = w2. otherwise is not edge-preserving. So we have [N(w)] pairs (wi, W2) similar nodes, where each w1 E Nu),, W2 E N(v). Define V, == {(w1, W2) w1 E Nuu,, we (w1)} to be the containing those pairs.
for some (W1, w2) E Vg, Cn(ww) * C₂ (w2), then wi and We are not similar by assumption in the inductive step, which creates contradiction.
So instead assume that ((wi,ws E Va. (, (w This implies that Vi e Nuu), (w)) = C. (a()). Thus, when restricted to N(u), induces bijection N(u) + N(v) such that Yu E (u), (.))) = (x))())). But this is contradiction, since it was shown above that such bijection can exist.
Conclusion
Thus, either way, by contradiction, we can conclude that u and are not similar. This completes the inductive step, we have shown that the hypothesis holds for C. Thus, the theorem is true Vn. by induction.
18

---

Published as a conference paper at ICLR 2024
A.5 THEOREM
Theorem. The expressivity of our proposed models is as follows, where for a class of models X, the claim "X is not equivariant" means that "there exists f E X such that f is not equivariant",
1. Unique-II-GGNNs not orbit-equivarian and, for any fixed node-labelling function f Gn - R", where Gn is the set of graphs with S n. nodes.
approximate any
2. RNI-GNNs are equivariant in expectation and, for any fixed n, upproximate any equiv- ariant function f: Gn + R" with probability arbitrarily close to (Abboud et al., 2021; Morris et al., 2022). They approximate some non-equivarian and orbit-equivariant functions with probability arbitrarily close to I, but there exist RNI-GNNs which, with probability arbitrarily close to I,
orbit-equivariant.
3. Orbit-Indiv-GNo are not equivariant but are orbit-equivariant on graphs whose orbits are distinguishable by orbit- I-WI_ For any m ZT+, there exist Orbit-Idii--GNN, f with max-o0 (xx-oobii(f)) > m.
4. m- DOrrbi-Transform-GGG I are not equivariant but are orbit-equivariant on graphs whose orbits are distinguishable orbit-I-WL. They have max nax-orbbi(f) S m and there exist m- m-Orbit- taiti-rrrrffo--GNM,, f with max -xxitorbi((f) m.
Proof. The theorem follows from the four following Lemmas (1, 2, and 4), each of which proves the expressivity of one of the models in the Theorem.
Lemma Unique-ID-GNe -N-NNs are not orbit-equivarian and, for any fixed n, can approximate any node-labelling function f Gn > IR,, where Gn is the set of graphs with S nodes.
Proof. This proof has two sections, one for each of its claims.
Unique-ID-GNNs are not orbit-equivariant.
The following a trivial example of Unique-ID-GNN f that is not orbit-equivarint. Let f be UniQue-ID-GNNN defined by S(G) JaNN(Junique (G)), where Junique == (v, G.) deter- ministically appends unique label (the unique label is v itself, since it is already an integer) to each node v. Define fGNN as GNN with a single layer, where fagg and f are arbitrary and fupdate (A," _ = X The GNN does not do any actual pesssge-passingg and simply keeps the original label. Then, consider the below graphs G1, G2, where the nodes have empty labels.
2
2
3
3
G₁:
Gz:
Consider the permutation a {11,2) (3,1) for which a G = G2, and consider the orbit {1) of G1. Then [f(a G1)a(o) r [f(G2)2 {2] and [f(G1)) e r = (f(G) = {1]. So there exists an orbit E R(G1) and permutation a such that [f(o Gi)a(w) v E r + (f(G)),
rB. Hence, the Unique-ID-GNN f is not orbit-
equivariant.
Unique-ID-GNNs can, for any fixed n, approximate any node-labelling function f:G. - RR..
We aim to prove that, for any node-labelling function Gn R", there exists a Unique-ID ID-GNN that approximates if with arbitrary precision e. For this proof, we rely on Theorem 4 of Morris et al. (2022), which we state here:
19

---

Published as a conference paper at ICLR 2024
Let n 2 1 and f Gn R be equivariant. Then Ve 0, there exists CNN with unique node IDs that e-approximates f-
Note that their definition of "GNN with unique node IDs" is identical to Unique-ID-GNN. Gn defined as the set of all graphs with at most n nodes, so n can made arbitrarily large so as codomain of IK for each node feature, but note that the result extends to real vectors of arbitrary size. In their proof, they show that there exists a Unique-ID-GNN g( unique (G)) that with arbitrary precision yields final label of X, (u,, re) for each node v, where To uniquely identifies the graph G in G, (up to isomorphism) and u, is the original unique ID given to v.
to include any particular graph. They also
However, this only identifies the graph up to isomorphism. So, we first prove that for any graphs H with VG) V(H), funiqu (G) = funique (H) $ G H. G H, then trivially Funique (G) = funique ()) and thus Sunique (G)
Sunique (H). If instead Sunique (G) funique (H), then there exists a permutation a on V(G) such that Sunique ( (G) f uunqque ()). The permutation maps each E V(G) (with unique ID u.) to the vertex
V(H) with the same unique ID, since permutation is label-preserving. But since Junique is deterministic, v w. Thus, Ve, w E V(G), w) E E(G) < ((()),(())) E E(H) > (v, w) E E(H), and G. H. So G H. This proves that identifying funique (G) up to isomorphism is equivalent to identifying G up to equality.
Thus, define a GNN fcopy with single layer that simply copies the unique label: Juggr and frad are arbitrary and updaace ((v, G,), == (v, U. G.), The GNN does not do any actual message- message-passing, and simply copies the unique ID portion of the original label. But then the GNN {f (funiqu)) )) yields final label of X (u,: ru) for each node u, where Ty uniquely identifies the graph G (up to isomorphism) and ue is the original unique ID given to But since identifies funique (G') up to isomorphism, it identifies up to equality.
But then we can define mapping fmode such that for each labelled graph G. c E G, frade (ue: To) f(G),. p- This mapping can be approximated by an MLP with arbitrary precision and appended onto the GNN g( coop (Sunique) )) as a final update layer. This yields a GNN that approximates f with arbitrary precision.
20

---

Published as a conference paper at ICLR 2024
Lemma 2. RNI-GNNs equivariant in expectation and, for any fixed n. can approximate any equivariant function f G,, + R² with probability arbitrarily close to (Abboud et al., 2021; Morris al., 2022). They can approximate some non-equivariant and orbit-equivariant functions with probability arbitrarily close to I, but there exist RNI-GNNs which, with probability arbitrarily close to I, orbit-equivariant
Proof. This proof has three sections, one for each of its claims.
RNI-GNNs are equivariant in expectation and, for any fixed n, can approximate any equivariant function f Gn - IR" with probability arbitrarily close to 1.
Note that since RNI-GNNs are functions that include randomness, we can no longer discuss them simply approximating functions. Instead, we need to refer to them approximating functions with given probability.
To formally define "with probability arbitrarily close to 1": Abboud al. (2021) say that a ran- domized function X that associates with every graph G' E G, a random variable X(G) is an (c, 6) approoxxiitao of f if for all G G, it holds that Pr(If(G) (G)) S 2 8. Note that an RNI-GNN N computes such functions X. If X is computed by N. we say that N (e, approximates f. If for e, > there a RNI-GNN that (e, -)pppooxxissstss f. then we abbreviate this by saying that the RNI-GNN "approximates with probability arbitrarily close to 1"
Abboud et al. (2021) prove that RNI-GNNs are equivariant in expectation and that they can ap- proximate any invariant graph function with probability arbitrarily close to I (ín their Theorem 1). Morris et al. (2022) extend the universality results of Abboud et al. (2021) and prove that they can approximate any equivariant node-labellin function with probability arbitrarily close (in their Theorem 2).
RNI-GNNs can approximate some non-equivariant and orbit-equivariant functions with probability arbitrarily close 1.
We provide example of non-equivariant and orbit-equivariant function that RNI-GNNs can approximate with probability arbitrarily close to 1. This is done to demonstrate their ability to go beyond equivariance and into orbit--quivariance, but it remains an open question as whether RNI-GNNs can approximate any orbit- equivarquiari function.
Define function f that relabels the nodes of each input graph as follows and returns the relabelled graph. For labelled graph G. fG)) = TG.v, where TG is some value that uniquely identifies the orbit of e G up to isomorphism. Formally: TG = THH < there exists an isomorphism a: G - H (the graphs containing nodes and w, respectively) such that a(u) = Thus, for any permutation a, TG.. (())) since o is an isomorphism from G to a G.
This function / equivariant, since for all labelled graphs G, all permutations a V(G) and all nodes (G), we have f(a G), To-G.v (w)) f()),- cquivariant, Theorem 2 of Morris et al. (2022) proves that can be approximated with probability arbitrarily close to by an RNI-GNN, g.
f(G).. Since f is
Now consider another such function feupy that relabels the nodes of each input graph and returns the relabelled graph, such that feopy (G), (Me r. This is the same as f. except it also copies the random noise Th given to node v in the input graph G. fcopy is also equivariant, as a trivial consequence of f being equivariant, and can be approximating by extending the RNI-GNN copy the random noise for each node.
Now fix some graph H and node H such that the orbit of w has size at least 2. Then consider node-labelling function fmax, such that fmax (G), = if TG, = TH and ny is the maximum of 7)u for all u E ((G) such that FG THH Otherwise, frna (G). =
The node-labelling function h defined by h(G) == Fmax(fccu (G)) can be approximated by extending the previously mentioned RNI-GNN g. Append one final layer to the GNN, de- fined by f T u E V(G) == max (n.. u E V(G) and rG.u. TH B). This function is permutation-invariant and is valid choice for fread- Supdate is defined by
21

---

Published as a conference paper at ICLR 2024
if rG,. THe and T 7u. and 0 otherwise. This exten- sion approximates h with probability arbitrarily close to 1, since a unique value 17 u E V(G) and T..u TH J is maximal with probability arbitrarily close to 1, because the random values are sampled from a continuous interval.
It now remains be shown that the node-labelling function h is orbit-equivariant. To prove that h is orbit--quivariant, let G be labelled graph, a be a permutation on V(G), and r E R(G) an orbit.
Case 1: G..())))) M,,0 su for some node E Then:
(hla G)a(e) v E [mmuxx (Scopy (a G)) 1 v {TP 1OR
Also, since TG,u Go-G (proven when f is defined), we can derive that rG.. rHHw-
Thus:
[k(G), / {mmmxxxx (Sapp (G)), |vEr] 81 u (ogln-1
Case 2: (o) # THo for every node u E r. Then:
Uh(a G)o(s) E = [max (Juopy M))()) | EvEr (ODIn)
Again, since TG.a = Ta.G, for every a E V(G), we can derive that TG.u * TH for every u E Thus:
-m (C) r 103
Hence, in either case, (h(o (h(o--))(o) e [ (h(G), L h is orbit-equivariant However, fOB -i-1 when G H and w E (note that |r| > 2 by the definition of w), which shows that the function produces different values for similar nodes, violating the property equivariance proved in Proposition I.
is non-equivariant, since (h( e e u
There exist RNI-GNNS which, with probability arbitrarily close to 1, are not orbit-equivariant
Consider RNI-GNN f with a single layer. The readout function foe is defined by Fead (f 1o)) E V(G))) max ( : I w V(G) where The is the random noise given to node w. The update function (d) /upitme is defined by Sup (Np: Ad); 7max) = if Tue 1/max and
otherwise, where 7mma is the output of fraid
Thus, for graph G' with nodes, f(G) = 1 for some E V(G) (chosen uniformly at random), and f(G), = for all u E V(G) such that u + w.
As becomes large for graphs with small orbit sizes, the probability that f(G) 1 and f(G) 1 for any w, u E VGG such that w, u are in the same orbit of G, across two separate applications of f. becomes arbitrarily small.
Thus also, the probability that for all labelled graphs G, permutations a on V(G), and orbits E R(G), it holds that (a G)a(s) E r} = (f(G), E r) becomes arbitrarily small. So the RNI-GNN is not equivaraiva with probability arbitrarily close to
22

---

Published as a conference paper at ICLR 2024
not equivariant but are orbit- orbit-equivarian graphs whose bits are distinguishable by orbit-1-WLL For any m E Z*, there exists Srbir-Indv-GNNN. f with max max-orbit(f) >>
Lemma 3.
Proof. This proof has four sections, for each of its claims and one demonstrating the consequences of having an input graph whose orbits are not distinguishable by orbit-I-WL.
Orbit-Indiv-GNNY are not equivariant.
We provide a simple example of an Orbit-Indiv-GNN f that is not equivariant, defined on a graph G by S(G) :- m indiv (foNN (G))). fONN is defined by JaNN (G), Define mip be the identity function. Let G' be the below graph.
2
Then f() = ((1,0), (1,0), (2. Nodes 2 and 3 are similar in G. But f(G)2 (1, and f(G) = (2, 0), breaking the property equivariance proved in Proposition Thus, Arbit-Indive
GNN f is not equivariant.
For any m Z+, ttere exist Orbit-Indiv-GNN: f with max-orbit(f)) > m.
Let m Z* and D {C,, I E }ナ} be the set of all single-cycle graphs. Let f be an Orbit-Indiv- GNN defined on D by f(G) = [mip(forbitinndd indiv (fGNN(G))). faNN is defined by faNN(G), == Define Smip to be the identity function.
Then for any G = On E D, orbit-1-WL. correctly identifies nodes as belonging to the same orbit, f(G) (11,0), (), .... (n, 0)). This has different outputs within the same orbit. But o)...
Cm+1 E D, so max max-oorbi(()) 2 m +1>1<n m.
Orbit-Indiv-GNe GNNNs are orbit-equivariant on graphs whose orbits are distinguishable by orbit-1-Wi
Let be an Orbit-Indiv-GNY defined by S(G) == Smip(Janii whose orbits are distinguishable by orbit-I-WL.. Then since Vr E R(G), v,, w r JGNN (G), fGN w. we have, for all labelled graphs G D, permutations o on VGG), and orbits R(G):
(Jubit indiv (JaNN (G)) and D all graphs
(f(G), v E = (.Smp(((u (aox(())))))))) Er, u (1,2,...,/I
Also, Vr R(G), v, w E r, faNN(O G)a(o) faNN (a G) since v, w similar in implies that (v), (w) are similar in G. So have, for all labelled graphs G, permutations V(G). and orbits r R(G):
[f(a G)a()) IvEr]
= [[Smmp (u, JaNN(O G)o(v)) |r,, u (1,2,...,/11)
(since Smip is element-wise)
-(Smip( (a (CNN(G)) v u /rl
(since saNN is equivariant)
= =ffmmp ( (GNN e u e (1,2 r[]
Thus, (S(G), E (5(a Do(u)) v E r.. Orbit-Indiv-GNN f is orbit-equivariant.
23

---

Published as a conference paper at ICLR 2024
The expressivity of Orbit-Indiv-GNNs for distinguishing nodes into different orbits is limited by orbit-1-WL.
First, note that fONN has the same expressive power as orbit-I-WL for distinguishing nodes into different orbits and that both fGNN and orbit- I-L are explicitly used in computing the output of an Sebit-nndv-GGNe Thus, Orbit-Indiv- Iaei--nddvvyyan GNNs are limited by the expressivity of orbit- I-WL. We will briefly unpack the consequences of this here.
The contrapositive of Theorem colorings to u, v. Thus, the following statement (used in the above proof that Orbit-Indiv-GNN are orbit-equivariant) still holds true, despite the limited expressive power of foNN: Vr E R(G), v, w fONN (G), [GN
if v, w VG)) are similar, then orbit 1-WL. assigns the same
the above proof, it was assumed that for every orbit r E R(G), orbit-I-WL correctly identifies nodes in r and thus that forta indi distributes the labels {1, 21,2,... [r]] among the nodes of the orbit. However, consider the following graph for which orbit- I-WL fails to identify the orbits:
indiv
2
3
The actual orbits are r1 (1,2,37 12 64, 7], but orbit- 1-WL incorrectly identifies them graph G by S(G) := SaNN is defined by (GNv(G),, == 0. Define Smip to the identity function. Then f(G) ((1,0), (2, 0), (3,0), (4, (5, 0), (6, 0). (7, Let be the permutation {(L, (), (7, (2, (3,3), (4, (4.4) 4), (5, 5), (6,6)) 6)). Then G is the following graph:
as r3 2, 3, 4, 5, 6, 7}. Consider Orbit-Indiv-GNN f. defined [mtp(aatti indiv (GNNN(
5
2
3
Then HS()), ve = (1,0),, (2,0), (3,0) 0) J. but since fohit indiv uses orbit-1-WL orbits, [f(a G)r(s) e (7, (2),).2)))))) (2, (3,0) So f is not orbit-equivariant for this graph, due to the expressivity of Orbit-Indiv-GNNs for distinguishing nodes into different orbits being limited by orb. The problem occurs any input graph where the orbits cannot be correctly identified by orbit-1-WL. This theoretical issue can be alleviated by using a more expressive (and likely slower) orbit-identification algorithm than orbit- 1-L, by only operating graphs whose nodes can be distinguished by orbit-1-WL.
24

---

Published as a conference paper at ICLR 2024
f are not equivariant but orbit-equivariant graphs whose orbits are distinguishable by orbit-1-WL. They have max-orbit(f) I m and there exist Trantf-Trafffmmm---
Lemma 4.
with max-orbit(f).
Proof. This proof has four sections, one for each its claims and one demonstrating the consequences of having an input graph whose orbits are not distinguishable by orbit orbit-I-WI..
m-
not equivariant.
We provide a simple example
that is not equivariant, defined on graph G by f(G) == firasfiom (G)) In this case, == (the number of final output channels). foNN is defined as stated below for input graphs G1, G2. G3. and maps each other graph G to (((0,99) 99), (0, 99)) /l. In the diagram below, the colors of nodes represent their features, with white ((0, 99), (0, 99)) and gray swapping from the default (i.e. the final channel is the largest, then the default should not be swapped out for the value in this partition).
(9),, (2, 99)). The large final channel (99) represents not
2
2
3
3
3
2
2
G1:
G2:
G3:
Then f(G) (0, 1,). Nodes 2 and 3 are similar in Gi. But ((1))2 = and f(G))
breaking the property of equivariance proved in Proposition 1. Thus, 2-Orbit-Transform Daafform-GNNNTT is not equivariant. similar example for any m shows that Sobit-Trassfome equivariant.
are not
O-Obiit-Transform--G. have max-orbit(f) S and there exist m--Orbit-Transform-CNN f with max-orbit(f) m..
Since we aim to convey the max-orbit of an entire class of models instead of just single function, we prove that there exist specific m-Orbit- Transforn-nnaaaa GNNs f that have max-orbit = m and that there no Tn-Orbit-Transform--OO trivial m--rbit- Transform--NNss / such that max orbit((]) < m.
f with max max-orbii(() > m. Note that there do exist
We prove this in two parts. First, we prove that for any m-Orbit-Tre Dorbit-rranffomm-CC GNNN f. max max-orbit(f) S m. This follows from there being exactly m partitions in the output of (G). For each graph G and orbit E R(G),, step (1) of funnsform gives a single label to all nodes in the orbit. Then step (2) adds a new label to the orbit at most min(m, |r]) - times, meaning there are at most different labels in the orbit after step (2) is finished.
Second, we give an example of an m JaNN is defined by [(),, ((1, 99), (2, -99),... ..., (m, -9)) for each node V(G). Consider the cycle graph H = Gm (a single cycle of m nodes). It has a single orbit, r = {1, 21,2,..., m), which is identifiable by orbit-1-WL. Thus, f(H) (1. m). so there are unique values in (H)) even r..
GNN f that has max-orbit (f) = m.
Tranbit-TranffommGGGN are orbit-equivariant graphs whose orbits are distinguishable by orbit-1-WL.
Let f be a m- Sa--Orrr--Trasffomt GNN defined by f(G) == finnsfom (oommffann (fNNN (G) and D set of all graphs whose orbits are distinguishable by orbit- orbit-I-WL. Then since Vr E R(G), V, w E r, ToNN(G),, fGNN(G) w. we have, for all labelled graphs G E D, permutations a on (G),, and orbits R(G):
(S(G), E forii transform (oaiaamm//ssa (JaNN (G))) (for any E E))
25

---

Published as a conference paper at ICLR 2024
where forbit transtoem function that yields the multiset of outputs of fuanstorm for the orbit containing w. These outputs are all set to a single value by step (1) of fuanstorm- and are then changed by each iteration of step (2). Also, vr E R(G), v, r, faNN G) faNN(a ()a(w), since e, similar in G implies that (v), (ww) are similar in G. So we have, for all labelled graphs G,
permutations o on V (G), and orbits E R(G):
Kf(a (f(a))))(m) G)a(v) U r forbit, transtiom (fONN (a G)a(w))
(for any w E r) (since foNN equivariant)
forbit transform ( (a faNN(G))
forbit transtoom (G)
Thus, | = ([((a-)aatt l E Er so mn-Orbit-Transfommee / orbit-equivariant. The expressivity of m--Oritt-rannform: limited by orbit-1-WL.
for distinguishing nodes into different orbits is
First, note that fGNN has the same expressive power orbit- 1-it- for distinguishing nodes into different orbits and that both foNN and orbit-I-WL are explicitly used in computing the output of ----Oritrraasfomm---
Thus, m--Obbit-Transee Transform-GNNG are limited by the expressivity of orbit-1-WL. We will briefly unpack the consequences of this here.
The contrapositive of Theorem is: if v, w. V(G) are similar, then orbit-1-WL assigns the same colorings to u, Thus, the following statement (used in the above proof that m- Transform-GNNs are orbit-equivariant) still holds true, despite the limited expressive power of fGNN: Vr E R(G),
E [C) = faNN(G)..
In the above proof, was assumed that for every orbit R(G), orbit-1-WL. correctly identifies the nodes in and thus that forbit transform yields the multiset of outputs of firanfoom for the orbit containing w. However, consider the following graph for which orbit-1-WL fails to identify the orbits:
5
2
The actual orbits are f1
(1,2,3} 12 (4,5, 6, 7), but orbit-1-WL incor-
rectly identifies them as 13 = (1,2,3.4.5. 6,446,6,7. 6. Consider Dorbit-Transform-GG defined by (GNN(G), = (11, (9), (2, 99)), (3, -99), 94.99 (5. -99). (6. 99), (7, (7.-99)). Then [(G) 21, 4, 5, 6, 7). Let be the permutation {1,,7) (7. (2, (2. (3, 3), (4.4), (5,5), ()),(,))))) (6, 6)). Then
I. defined on a graph
by ((G) = mmnnfoomm (JaNN(G))
JaNN
Gs the following graph:
Then [.(()), E m) = (1, but since furmsfurm uses the orbit-1-WL. orbits, [f(o G)a(o) v E r [7,2,3]. So f not orbit-equivariant for this graph, due to the expres- sivity of --L. The same problem occurs on any input graph where the orbits cannot be correctly identified by orbit-1-WI. This theoretical issue be alleviated by using more expressive (and likely slower) orbit-identificttion algorithm than orbit- 1- IWL, or by only operating on graphs whose nodes can be distinguished by orbit-1-WIL.
for distinguishing nodes into different orbits being limited by
26

---

Published as a conference paper at ICLR 2024
B ORBIT-I-WL
B.1 DEFINITION
The 1-WL algorithm (Weisfeiler & Leman, 1968) can be formalized algorithmically as follows:
1. Initialize Co V(G) + C by Co(o) for each node e E V(G), where C' is codomain of colors and C1 C. Co is a node coloring function iteration 0 of the algorithm.
2. each iteration of the algorithm (starting from n = 0), we define new coloring function Cn+1- For each node E V(G), set Cn+1 (v) = (v), H.C. w (N)) B), where à is hash function and (u) the set of all neighbors of v in
3. At each iteration n of the algorithm, also compute a partition Px+1 V (G), where for any nodes
V(G), e; E Q for any Q P if and only if (v) Cn+1(1o). In other words, the nodes are partitioned by their colors.
4. If at any point, Pa+1 Pn, the algorithm halts and returns h
w E (())))
Orbit-1-W/ operates in the exact same way, except that when the algorithm halts, it returns Pa instead of h( (w) w E V(G))). P, represents a partition nodes into their orbits by orbit-I-WL.
B.2 SUCCESSFUL EXAMPLES
As an example, here orbit- I-LL identifying the orbits of a graph:
8
6
3
2
9
8
6
3
2
9
5
This yields orbits of ((1), (2). (3). (4,5), (6. 7], (8, 9} so orbit-1-Wi has correctly identified the orbits. As another example, consider the following two graphs, G1 and G2:
5
4
G₁:
G₂
27

---

Published as a conference paper at ICLR 2024
Despite 1-WL being unable to distinguish between these two graphs, orbit-1-WL correctly identifies the orbits for both (all nodes are the same orbit). This illustrates why it is important to distinguish between 1-WL and orbit-1-WL, since there cases where 1-WL fails and orbit- wrbit---WL succeeds, and conversely there are cases where orbit-1-WI. fails and 1-W1. succeeds (as will be shown in later section).
B.3 COUNTEREXAMPLES FOR COMPLETENESS
Theorem proves the soundness of orbit- 1-WL. However, orbit-1-WLI is not complete. That is: there exists graph G and nodes U, w E such that orbit-1-WL. assigns the same colorings to v and w, but u and not similar. We show several such graphs here.
In the following example, orbit-1-WL colors all the nodes the same (since the graph is 2-regular), so identifies all nodes as being the same orbit. However, the orbits are (11,2,3), {4, 7}}.
2
3
The above example can be scaled up into infinitely many other 2-regular graphs for which the same problem arises, yielding infinitely many counterexamples. It is worth noting as well that if graph G contains graph H as a maximally connected sub-graph (i.e. collection of components of G), such that the orbits of H are incorrectly identified by orbit- 1-WL, then the orbits of G are also incorrectly identified by orbit-1-We 1-WL. This yields another way to generate infinitely many counterexamples.
Here follows two other non-trivial 3-regular graphs (one planar and one non-planar) for which orbit- 1-WI. fails. Orbit-1-WI, colors all nodes the same since the graphs are 3-regular. The first has actual orbits of {(1, 7, 8), (3, 4, 6}). The second has actual orbits of ([1, 7, 9, 10), (3, 4, 5, 6)].
10
Here follows a counterexample (found in the Alchemy dataset (Chen et al., 2019)) which is not regular graph. It is colored by orbit-1-WI.c shown.
28

---

Published as a conference paper at ICLR 2024
9
10
4
5
7
9
11
10
9
11
10
4
5
However, the true orbits of the above graph are
{11, 2) 43, (7,8), (9, 10), (11)
Out of the 202579 graphs in Alchemy (Chen al., 2019), orbit- 1-L only predicts the incorrect orbits for 5. We calculated this by comparing the true orbits and orbit-1-WL. orbits for every graph in the dataset.
B.4 ORBIT-K-Wi -L
Similar to classic WI. (Morris et al., 2019), there is strict hierarchy of orbit-WI. algorithms: orbit-1- WL, orbit-3-WL. orbit-4-WL, such that for all there are graphs for which orbit-k-WL will correctly identify the orbits but orbit-(k- 1L will not. The below example shows construction that proves this:
5
2
3
Neither orbit-1-WL orbit-2-Wi correctly identifies the orbits of the graph, but orbit-3-WL. does. For any l: 2 3, the graph consisting of (I: + 1)-cycle and a k-cycle has its orbits correctly identified by orbit-k-WL but not by orbit-(k-)--LL
29

---

Published as a conference paper at ICLR 2024
Table 2: Properties of the new datasets proposed in the paper.
Datasct
Bioisostere
Alchemy-Max--rbitt-2
Alchemy-Max-Orbit--
Graphs
961
1000
1000
Input Features
43
6
6
Possible Targets per Node
44
2
6
Nodes
Average
10.3
10
12.1
Min
9
Max
15
22
Edges
Average
10.4
12.5
Min
9
8
Max
17
12
22
C EXPERIMENTS
C.I COMPUTATIONAL COMPLEXITY
With respect to the computational complexity of our proposed models, Unique-ID-GNNS and RNI- GNNs have extra overhcad, besides yielding larger input vector for each label in the GNN. Orbit-Indiv-GNNs use 1-WL, which is worst-case Onn), where n is the number of nodes in the graph.
Appending unique IDs and the application of the final MLP are also O(n). So overall, the additional complexity of Orbit-Indiv-GNNs is O(n).
Likewise, for TenDrbit-Tranffomm--o larger than before: is now m(( + 1) instead of o, which adds additional computation to the GNN. Apart from this, there no additional computational cost during training. When making predictions, the transform is applied, which is worst-case Onn). So overall, the additional complexity of
1-WL worst-case O(n). The output size of the GNN
GNNs when making predictions Onn).
C.2 DATASETS
In Table 2, we present a summary of the new datasets we propose in this paper. Full details are provided in the following sections.
C.2.1 BIOISOSTERE
The task in Bioisostere is, given an input molecule graph, output a label for each node which represents either keeping the atom or swapping it out for some other particular atom, such a way that the final resulting molecule has minimal lipophilicity; discussed in Section 1, this is an important factor in drug design. Solving this task requires a non-equivariant function when an atom being swapped comes from orbit of size 2.
To construct this dataset, we first retrieved 961 small drug molecules from ChEMBL (Mendez et al., 2019). The version of ChEMBL used is CHEMBL32 and the content licensed under the CC AttributinnSShareAA
3,0 Unported license. We filtered to only include drug molecules. From there, we filtered by "Type" include only those with the type "Small molecule". and further filtered by "Molecular Weight" to only include molecules with molecular weight < 199. This yielded CSV file of molecules. which was cleaned up into chembl. smi a file of SMILES code and molecule name pairs
We then used MMPDB (RDKit, 2023a) to compute many different bioisosteres for each molecule that each differ by at most one atom from the original molecule. mmpdb fragment chembl. smi -o chembl. fragments --num cutt was used to compute the fragments all the molecules from CHEMBL that can be created by cutting single non-ring bond. mmpdbb index chembl. grantss -o chembl.. mmpdb was then used to group fragments with the same R-groups into database. For each molecule with SMILE code "input smile", mmpdbb transfo for --smiles input_smi molecule. For each of those bioisosteres (and the original molecule), we used RDKit (RDKit, 2023b)
chembl .mppd was used to compute a list of bioisosteres of the
30

---

Published as a conference paper at ICLR 2024
to compute the lipophilicity and selected the one that yielded the lowest value as the target for each molecule. Both MMPDB and RDKit are licensed under the BSD 3-Clause License.
Of these molecules, only 588 actually require some swapping out of an atom to achieve minimal lipophilicity, and only 156 require a non-equivariant function. All 961 molecules are used in the dataset. The function required to solve the task is orbit-equivariant with max-orbit(] = 2.
C.2.2 ALCHEMY-MAX-ORE
An Aichemy-Max-Orbiiee dataset is constructed using Alchemy (Chen et al., 2019; Morris et al., 2020), large dataset of organic molecules. The dataset constructor is given First, it removes all duplicate graphs from Alchemy using 1-WL as a heuristic. Next, all graphs without orbit of size m are removed, where the orbits computed using orbit-1-WL." If the number of graphs remaining is larger than the desired size of the constructed dataset (1000 for this paper), then graphs are dropped from the end of the dataset make the dataset the desired size.
hyperparameter.
If the number of graphs remaining is instead smaller than the desired size of the constructed dataset, then new graphs are added the dataset using two graph generators. Both generators make small changes to graphs already in the dataset, broadly preserving the structures whilst adding new non- isomorphic graphs. The constructor continues to alternate between applying each generator, with the process immediately halting when the dataset has attained the desired size. Each generator is applied to every graph that the dataset so far. However, before any new graph added to the dataset, is checked using its 1-WI. hash to ensure that graph isomorphic to it is not already in the dataset. For each graph given to it, the first generator takes every orbit of the graph, and varies all the node features within the orbit in the same way. The second generator takes every orbit of the input graph and, for every node v within the orbit, appends a new node w to the graph that is connected to only e.
The task in the dataset is identify the largest orbit(s) in the graph (where the orbits are computed by 1-btt--WWL and, for each largest orbit r, distribute the labels T = HI 1,.,, 1, 1,2, 2... mB at random without replacement amongst the orbit's nodes, where [T' [r]- Thus, T contains the multiset {[ 1, 2..,, m } and is padded with 1 to ensure that there are the same number of labels in it as nodes in the orbit. Every node part of largest orbit should be assigned the label of O. Equivariant functions such as GNNs cannot solve any of the examples in the dataset. The function f required to solve the task is orbit-equivariant with max orbit(f) m..
C.3 HYPERPARAMETERS
Fixed hyperparameters across all experiments are shown in Table 3. The fixed hyperparameters were chosen by preliminary optimization experiments of GCN Bioisostere. Hyperparameters for the experiments on Bioisostere are shown in Table 4. Hyperparameters for the experiments on Alchemy- Max-Orbit- are shown in Table 5. Hyperparameters for the experiments Alchemy-Max-Orie are shown in Table 6.
C.4 LOsS
Here follows full explanation of orbit-sorting cross-entropy loss. Let f be a GNN and D a dataset of graphs. Let be a "target function" that yields a category for each node in the input graph. For each orbit of the graph G (computed by orbit 1-bL), collect the model outputs (f(G), E r) and the target outputs (t(G), V E r) for the orbit, both as tuples. The category predictions of the model are (arg max(f(G),) category. Fix some a-priori order on the output categories and define a function sort that takes in tuple of categories and returns the permutation that, when applied to the indices of the tuple, yields the tuple sorted by category. For example, given the tuple c = (8, 2, 4, 7, of categories, scrt
r), since each output channel of f(G), corresponds to
(11, 5), (2, 1). 3)3), (),(())))))))) (4, 4), (5, 2) and
(2, 2,4,4,77 7,8).
We elected to use orbit- I- WL to compute the orbits when creating the Alchemy- Max-MMxx--naae Orbit datasets, because some of the graphs in the dataset were too large efficiently compute all automorphisms and thus the orbits. For consistency, elected to compute all orbits using 1-W rather than exactly computing the orbits of the graphs that were small enough and using orbit- 1-. for the others.
31

---

Published as a conference paper at ICLR 2024
Table 3: Fixed model parameters for all experiments
Group
Parameter
Value
Description
Model
gnn_lag enn_layers gnn gnn_hidden hidden_ddizzii size mi mi_channels use
Number of message-passing layers in the GNN
Size each hidden layer GNN
10
Number of channels of random noise to append
True
Force use of the CPU over CUDA
Evaluation
train_cval_ing inteevall interval loss_ jis_log_interve
10
Eval on train set interval in epochs
10
Eval on test set interval in epochs
How often log the model loss epochs
Dataset
train entire dataset
False
Whether tain the entire dataset
train train_split
Ratio of dataset to use for the train set
bioisostcre_only _l
False
Filter out non non-equivariant examples from Bioisostere
thuffle_targett sn__aa__orlll _obit
True
Shuffle targets within orbits of Alchemy-Mat -rbit
@oufte_datasse
True
Shuffle dataset before splitting into train test sets
Training
learning rate
0.0001
Adam optimiser learning rate
Biightdecaay
5e-4
Adam optimiser weight decay
aLepochs
8000
Number of epochs (full training set) run
Table 4: Model parameters for Bioisostere experiments
Parameter
Value
Description
dataset
bioisostere
Dataset
loss
[ crrosseetroppy.
Loss function
orbit orbit_ sortins ctwoscerorooppppeeeeeeeee
model
[ gen, unique id gen, rni gen, indiv gen, max_orbil gen 2
Model (max_ = Transforn-GGNN
model__ax__om
Max orbit for Orbit Transform-Gii Seed for all random generators
seed
[1.23345.....89..0000]
Table 5: Model parameters for Machemy-Max-Orbiige experiments
Parameter
Value
Description
dataset
alchemy
dataset
max orbit alchemy loss
Max-orbit size (m)) in Alchemy-Max-Orbin Loss function
cross_entropy,
vrbit_sorting_eve satg__ooosssssoopp__ unique_id gen, mingon orbit indiv_idvvee gen, max orbit_gen
model
Model amax_oobii-e Orbit Transform-GNii
model_men _mx____axa____ _rbit seed
Max orbit for Tobi--Transfoo--GNN Seed for all random generators
[1,2.345.6678899.10]
Table 6: Model parameters for Alchemy-Max-Orbinn 6 experiments
Parameter
Value
Description
datasct
alchemy
Base dataset
max_orbit_alcheme
Max-orbit size (m) Alchemy-Max-Othin
loss
cross_entropy.
Loss function
orbit sorting cross conoopyyyypyy// unique id gen, mi orbit indiv Lndn gen, max orbit_ gen
model
Model (max orbit PottitTransffom-GGNN
modeL_max_orbii seed
Max orbit for subit-Transfommee Seed for all random generators
[1.23.1...6.......
32

---

Published as a conference paper at ICLR 2024
For the entire graph, initially set T := t(G). Then, for each orbit (computed by orbit- I-WL,, we compute oy == sort (oart((rg__mm)) max(f(()))
E r)), the permutations that sort the model category predictions and the targets respectively. We then compute re-ordered target 7 for the orbit, with 7 == of (o (MG)), v E r)). Then T(r) is set to T", where Tr) accesses the indices of T using the nodes in r.
E r)) and oj = sort((t(G),
Once all orbits have been iterated through, we compute the cross-entropy between the new targets T and the model outputs (f(G), V E r))
To better illustrate the mechanisms of orbit-sorting cross-entropy loss, here follows an example, For an input graph G, f(G) (converted to categorical outputs with ur_max for ease of notation) and t(G) are shown below, where colors represent node features. White 0, red 1, green and blue 3.
6
4
6
2
f(G):
t(G):
The orbits of this graph are 71 = (2,3) rs = {4, 5, 6, 7}, as computed correctly by orbit-
1-WL. Set T = f(G) (0,0,2,3.2,0.1) initially. has size 1. so no re-ordering is possible. For r2. (arg marg__axx/(())) (2) af = (11,)), (2, 1)]. Also, (L(G), v E r2) (0. 2). so o, ((1, 1), (2, }) Thus T" o0," (a,-(t(G)) v r2)) = of (a. (0, 2)) = (2, 0). T[r is then set to 2 so T = (0.2.0,3,2.0,1) (the affected part of the tuple is highlighted in bold).
For T3, (arg_ (mg__ax(f(G))) e ra) (0, 80 (1,,1) (4, Also, ((G)), v ra) = 2, 1), so ar = (2),, (4, Thus 7 = of (I(G), E ra)) = o, (a, (3,2,0, 1)) 2,),, T[ra] then set to 7 so T (0,2,0,0,2,1,3) Cross-entropy in then computed between the new targets T and the model outputs (S(G), (ve))
= (az
0,,,1,
For the WwOOr--TTranforree MONNGGNNNNNNN models, loss is computed before the transform takes place. This method works for this model in particular since the transform component of the function does not need to be trained. Thus, standard cross-entropy can be used, since the model is equivariant before the transform is applied.
33

---

Published as a conference paper at ICLR 2024
C.5 FULL RESULTS
All experiments were run in a distributed manner on an internal university cluster, on exclusively CPU nodes. In our final experiments, there were 260 individual runs. A total of 88 days of compute time was used for our final experiments. Across all of our experiments, including failed runs and preliminary experiments, a total of 219 days of compute time was used. Full results for our experiments across each of the datasets are shown in the following sections. The mean is shown along with standard error.
C.5.1 BIOISOSTERE
Cross-Entropy Loss
gain_ggrap_accuug
test graph_accurage
wodel: eoxorbit..go model: ordst_indiv..on D model: miluggn
D model: essorbbt.ggo model: ortst_ tnd
D model: mnl_gtn
rodel: idl soced: gm
rodel: uniqua sd O socel: pm
24
12
spech
spoch
train_orbit_ wobiottbbiiiooe accuracy
test_orbit aacuracy
sodel: tbxorbttt.gon
model: trddtt.
wodel:
model: issorbit..go
model: ortit tndll model:
rodal: 1d_
socall
O rodel:
0.35
0.5
0.33
spoct
spoct
26
train accuraccuraty
tost_ accuracyyyyy
wodel: eox.orbit.gon
ordst..Eddv.pon pon wodel: rilugon
sodel: eoc.orbit..on
ordst_.rddvv.om pon wodel: red_gon
0.96
0.55
0.55
095
0.30
24
train Joss
D wodel: mox.ortit..com D sodel: orddt_..dd.v.pon wodel: rillggn
model: ini.ger model: pm
200
50
34

---

Published as a conference paper at ICLR 2024
Orbit-Sorting Cross-Entropy Loss
trsin, Seinn_prapp__eee
prcuurryeecccuracyyyy sacuracy
test wwt.grppccpccrccc..ee accuracy
mode:: eatorbi nAlel indiin.nniis.ann gon
wodel: milacon
matel: ww Lag
make: urbit indee gon
moiel: indagon
rodel: untove_Ieuger socel: pon
rodel un10ue_16_607 socel: pon
24
12
train_orbi orbit accuracy
vest_orbit_.eem sccuracy
D molel: L.g.orbi malel urbi indiivaer
D madel: migge
madel: La
makels urba inali models migen
rodel: uni.ue.io.gor eodel:
rodel: untave.in.ge ecceli pon
0.35
033
0.95
rpoch
train, node, accuraty rodel. Iil.ue.td..or eosel:
test node,
man_orbi
037
003
0.3
0.54
rpoch
24
loss
eas_orbit irdii model: milugen
rodel: vol.ue.id..or sccel: pon
100
35

---

Published as a conference paper at ICLR 2024
C.5.2 ALCHEMY-MAX-ORITT2
Cross-Entropy Loss
test graph_accuraae
0 wodel: roxorbittggon D node:: ordst_irdivv.o
D model: migggnn
D model: eoxorbit.gcn mode): ortst trm
wodel: mnl_gtn
modell: uniquu_id_aen
(I model: unique_i1_pp
24
24
31
spech
train_orbit_ accuracy
test_ vist.rbiit.c accuracy
wodel: tox.orbit.gon
vodel: trddt..nd wodel: miduggn
woeel: sox.rbbit.gon todel: trddg-ind model: mnd.gon
eodel: idi_en
CI sodel: unique_id_go _d.gon
0.33
0.54
0.34
0.32
678
0.75
0.74
spect
2<
train accuracy
wodel: sox.orbit.gon
sodel: Inndiv. pon wodel: mndugnn
sode:: mox.orbit.gon
wodel: irdii_indivvgom wodel: rel.ggon
unioue_lddje
0.55
0.
0.75
07
0.7
train Joss
D wodel: max.orbit.gon DI sode:: orbit Lrddi.. poo
wodel: millggn
model: inlque_1d_gen
430
290
36

---

Published as a conference paper at ICLR 2024
Orbit-Sorting Cross-Entropy Loss
train priin_praph__eee prcuurrreeeccuracyyy
test wwwpgggpppphgg accuracy
model: eus D xale: inbii_innii..an
D moiel: milgen
matel: sarorbilan make:: urbi Lindio.ae aac
moiel: mndagnn
modell infove_1d_go1
O Rodell infove_18_pon
13
train_orbie oobitttbbbbooo accuracy
test_orbit,cor Bok_oorbi__cccueee sccuracy
model: L.g. D solels L. andiv.acn
D model: migan
D malel: Lgg
makll urbi indlii O eodell unfaue_is.gon
model: migen
eodel: infoue_Id.gon
0.80
0.85
0.32
0.78
0.75
spoch
train, node_ accuraty
test poil_node.co
model: aas
model:
madel: pgo
urbi model: wt..eee...........
model:
eodel. inlove.id.gon
0.35
0.75
07
rpoch
0.
24
train_loss loss
madel: am D udees indixxann model: milggnn
eodel: inlque.id.gon
430
37

---

Published as a conference paper at ICLR 2024
C.5.3 ALCHEMY-MAX-ORITT6
Cross-Entropy Loss
test_ graph__ccurae
wodel: roxorbit.ggn D mode:: ordst_indivv.on model: milgggn
model: eox.rbbt.ggcn nodel: orbst_.nndvv.pp
Model: mndugtn
eodel: unique_id_aen
CI modell: Hi_
0.55
0.5
train wobitttiittooooo accuracy
test orbit accuracy
model: soxorrbit.gon
ordst_indiv.gon
wodel: wox.orbtt.goo
orddt_indi wodel: rnd.ggn
eodel: untoue__d
eodel: Ld_
16
2.4
spect
spoct
24
24
Ee
train, accuracy
htt_nood_accuree
sodel: sox.orbit.gon sodel: Irddx..n mndugnn
mox.orbit.goon
ordit_irdivv.om wodel: ril_gco
24
14
24
wodel: eax.orbit..gon DI sode:: orbi Liddi.i wodel: millggn
model: inloue_1d_je
1423
625
420
38

---

Published as a conference paper at ICLR 2024
Orbit-Sorting Cross-Entropy Loss
train, srinn__rppp___om
prw.rppppppaarrrcyyyyoo accurscy
test www.gggppppppggco accuracy
madel: eur D mAle:: onbii_indiisaac ago
moiel: miagen
matel: ao
male:: urbi indii pon O Rodel: infgue_1d_pon
moiel: midagon
model: infove_1d_gon
2.8
14
13
train orbit, train_orbit.co
accuracy
rest_orbittco Boi_oorii__cccuue sccuracy
D molel: ggm
solel L. indiv.ac madel: miagn
maie:: sgm
makll urbi
model: mijgen
eodel: ld..e
Rodel: untose 18.gon
16
apoch
train, node. accuraty
test nodee
model:
L. motel:
eodel: inlove.16e
12
13
rpoch
rpoch
26
loss
amo_orbii uddi: indix_iiiixx model: milugen
eodel: inique.id.gon
1200
1000
022
62B
200
39


Reviews:
[{"review_id": "SI7do5zRZK", "reviewer": "Reviewer_nEVg", "summary": "The authors propose an overarching framework for the hierarchy of node-labelling functions via the lens of orbit-equivariances. They do this by allowing an equivalence class of nodes in a graph to be mapped to a multiset of outputs. The hierarchy spans from permutation equivariant functions for graphs (two nodes belong to the same equivalence class obtain the same representation) to the case where all nodes get unique representations (aking to positional embeddings). The authors  introduce max-orbit, which allows for further control of\norbit-equivariant functions - and establish a theoretical connection between 1-Weisfeiler Leman isomorphism test to identification of orbits and thereby categorizing the expressive power of different GNN architecture. Subsequently they study 4 different GNN architectures in terms of theoretical expressiveness. In the experimental front, the authors propose two new datasets to demonstrate the success of using orbit-equivariant GNNs.", "questions": "Please address the minor weaknesses in the prior section.\n\nAdditionally, the term orbit-equivariance appears to be a slightly misleading name for the framework - given it is not about learning representations for the elements in an orbit  which are equivariant to something like a permutation action on the orbit itself. But it is rather assigning a multiset as output labels to an orbit. Unfortunately, I do not have an apt name as well - but would suggest the authors ponder about this a bit more.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper proposes a hierarchy which brings under one umbrella different GNN architectures. \n2. The paper provides a study of theoretical expressiveness (akin to the WL hierarchy) \n3. The paper shows empirical evidence on simple new datasets (proposed by the authors) to validate their claims\n4. The paper is very well written and easy to comprehend", "weaknesses": "**Minor Weakness**\n1. Misses relevant theoretical works which theoretically unifies positional embedding GNNs - to equivariant GNNs, and node labelling works to develop more powerful GNNs [1][2][3]\n2. In figure 1, please make it explicit that the 3 Fluorine atoms in the molecule belong to the same equivalence class only if the position coordinates of the atoms - are not used as part of the node features\n3. As the authors list in the limitations section - there is a lack of strong experimental results present in many real word molecular datasets, etc.\n4. Novelty is definitely present - but not something completely unexpected and draws and builds upon existing literature\n\n\n**References**\n\n[1] Srinivasan and Ribeiro, ICLR 2020, On the Equivalence between Positional Node Embeddings and Structural Graph Representations.\n\n[2] Li, et al. Neurips 2020, Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning\n\n[3] Zhang, et al. Neurips 2021, Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LeDmSnQIDh", "reviewer": "Reviewer_y9Hz", "summary": "The paper first introduces the orbit-equivariance of a function that takes a graph (with an ordered node set) as the invariance of the multiset of values on each orbit of the graph isomorphism under node permutations. Also, $\\texttt{max-orbit}$ is defined as the maximum number of unique values on each orbit, and it is shown that the usual equivariance is equivalent to orbit-equivariance and $\\texttt{max-orbit}=1$. Two types of existing GNNs are shown to be orbit-equivariant either deterministically or stochastically. Also, Orbit-Indiv-GNN and $m$-Orbit-Transform-GNN are proposed, which are orbit-equivariant, along with orbit-sorting cross-entry loss as a loss function for orbit-equivariant functions to train the models. The proposed models are applied to real or synthetic datasets that require orbit equivariance to verify their practical prediction performances.", "questions": "* P.2, Section 2: It is appropriate that the input to an orbit-equivariant function (or, more generally, a node-labeling function) is a graph with an ordered set of nodes. Node sets of graphs in this paper are ordered as $V=\\\\\\{1,\\ldots, N\\\\\\}$. Also, examples of node-labeling functions are defined using this ordering. If the node-labeling function takes the graph structure only, we need to show that the function is well-defined regardless of the node ordering. If it is well-defined, the function is automatically equivariant.\n* P.6, Figure 5: Since $m=o+1(=3)$, it is difficult to understand whether the triples represent $m$ or $o+1$. It would be better to use a different number for both (e.g., $m=5$). In Figure 5, the last element of the partition is 1-index, whereas 0-index is used in the text, which is confusing and should be unified.\n* P.6, Theorem 2: Regarding the claim that a function is not orbit-equivariant, does it mean the function is *not necessarily* orbit-equivariant? For example, Unique-ID-GNNs happen to be orbit-equivariant depending on the choice of the underlying GNN (e.g., degenerated GNN that always returns 0.)\n* P.7, Section 5: I have a question about whether it is appropriate to apply the cross-entropy loss to the output before transforming in the training of $m$-Orbit-Transform-GNN. This operation implies that $m$-Orbit-Transform-GNN is trained to output the correct labels before the transformation. If I understand correctly, this is different from what is intended.\n* P.8, Section 5: GCNs [...] would have achieved an accuracy of 0 on the Alchemy-Max-Orbit, [...]: Does this sentence mean that GCNs have not been tested on the Alchemy-Max-Orbit?\n* P.8, Table 1: The graph accuracy of RNI-GCN is 0 for all ten trials in Alchemy-Max-Orbit-2. Is this result due to the nature of RNI-GCN? Or does insufficient training cause it, and RNI-GCN could have non-zero accuracy when appropriately trained?\n\n【Minor Comments】\n* P.1, Section 1: Graph Neural Networks (GNNs) -> GNNs: The abbreviation for GNNs appears at the beginning of this section. So, there is no need to repeat the full phrase.\n* P.2, Section 2: aka -> a.k.a. or also known as (I suggest using the full phrase)\n* P.3, Section 2: $f^{\\theta'\\_{m}}\\_{\\mathrm{aggr}}$ and $f^{\\theta''\\_{m}}\\_{\\mathrm{read}}$ are imposed to be permutation invariant, but both of them are automatically equivariant when receiving a multi-set Isn't it automatically a permutation invariant when both of them receive a multi-set?\n* P.4, Section 3: $\\\\\\{0\\\\\\}^{|G|}$ -> $0^{|G|}$\n* P.4, Section 3: the number of unique values in $\\\\\\{\\\\\\{ f(G)_v \\mid v\\in r \\\\\\}\\\\\\}$: wouldn't it be easier to write $|\\\\\\{f(G)_v \\mid v\\in r\\\\\\}|$ in a mathematical way?\n* P.5, Section 4: What does *Indiv* in Orbit-Indiv-GNN stand for? Does it mean individualization?\n* P.7, Section 5: $|T|$ is not used.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The significance of introducing the concept of orbit-equivariant functions is appropriately demonstrated by using an example from drug discovery. The mathematical definition of orbit-equivariance is appropriate because it adequately explains the drug discovery example.\n- By introducing the concept of max-orbit, the relationship between orbit-equivariance and equivariance is clearly shown (Proposition 3).\n- This paper shows the existence of GNNs that are orbit-equivariant by concretely constructing Orbit-Indiv-GNN and m-Orbit-Transform-GNN.\n- Numerical experiments show that the proposed models improve accuracy in tasks that require learning orbit-equivariant functions.\n- The hyperparameters and datasets are described in detail, and the code is provided, making the experiments reproducible.", "weaknesses": "- The description of Orbit-Transform-GNN (Figure 5) has room for improvement (see Questions).\n- I have a question about whether the learning method of $m$-Orbit-Transform-GNN is appropriate (see Questions).\n- The proposed $m$-Orbit-Transform, although constructive, is constructed using operations that are difficult to explain intuitively, such as rewriting output values. In addition, numerical experiments have shown that $m$-Orbit-Transform has yet to achieve good accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wOzCSJOL9f", "reviewer": "Reviewer_GKac", "summary": "Typical GNNs are permutation equivariant, which, however, are unable to allow antisymmetric behaviors of symmetric nodes in the same orbit. Motivated from the example of molecules transformation and agent learning, this paper defines orbit-equivariance, a relaxation of equivariance which allows for such functions whilst retaining important structural inductive biases. Two orbit-equivariant GNNs are proposed namely Orbit-Indiv-GNNs and m-Orbit-Transform-GNNs. Besides the interesting theoretical derivations, the proposed models are evaluated empirically.", "questions": "No more question but the concerns in the weakness part.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n\n1. This paper is well written and well-motivated. I enjoy the reading. The example in Figure 1 and the illustrated examples in Section 3 nicely help the understanding of the proposed idea. The propositions and theorems are well organized and clearly demonstrated. \n\n2. The proposed idea of orbit-equivariance is novel and valuable. It allows permutation equivariance between the nodes in different orbits, but breaks the equivariance for the nodes in the same orbit. In this way, while it allows the distinct output of the symmetric nodes in the same orbit, the hierarchy of the graph structure is still represented in an invariant way, which means the multiset of outputs associated with each distinct graph orbit is unchanged. More succinctly, an orbit-equivariant GNN now becomes a set function of orbits other than individual nodes.\n\n3. The design of Orbit-Indiv-GNNs and m-Orbit-Transform-GNNs is meaningful and fulfill the theoretical guarantee derived by Theorem 2. \n\n4. The experiments, although not as impressive as the methodology part, are still sufficient to support the benefit of the proposed orbit-equivariance and the developed models.", "weaknesses": "1. The introduction of m-Orbit-Transform-GNN is a bit confusing. I have to read it multiple times to understand the process. It seems there are many freedoms to derive an orbit-equivariant GNN that has max-orbit no more than m. It is unclear why the authors choose the one proposed in the paper. And the experiments on Bioisostere show that the performance of 2-Orbit-Transform-GNN is worse than Orbit-Indiv-GNNs. Does it mean the proposed construction of m-Orbit-Transform-GNN requires further exploration?\n\n2. Another concern is that the processes in both Orbit-Indiv-GNN and m-Orbit-Transform-GNN to make them orbit-equivariant are not differential. I would like to hear form the authors’ thinking about if it is possible to derive a learnable equivariance-to-orbit-equivariant layer other the ad-hoc transformations proposed by the authors. Will the learnable ones further improve the performance? \n\n3. The last concern is about the efficiency of Orbit-1-WL that is applied to determine the orbits, particularly for large-scale graphs in practice. The authors should discuss this point if necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TQ2pJE8GFf", "reviewer": "Reviewer_AmbM", "summary": "This paper propose to capture a new kind of equivariance called orbit-equivariance.\nThe orbit denotes node subsets in graphs.\nWhen a function is orbit equivariance, the label subsets containing labels of nodes in orbit are the same if the input nodes indices are permuted.\nFor the commonly used GNN, it always preserves permutation equivariance $S_n$, and it is also orbit-equivariance and orbit-equivariance is less restricted.\nI suggest to give a better conceptual illustration for max-orbit first, and then provide the motivation to give such max-orbit function to make it more clear.", "questions": "1. Would you mind providing some illustrations about the concept of max-orbit?\n2. I am not sure whether the proposed model has some connection to the paper like DeepSet [1]. Would you mind giving some insights?\n3. The motivation of developing orbit-equivariance is still confusing to me. Would you mind providing more examples and situations that such symmetries are required?\n\n[1] Zaheer, Manzil, et al. \"Deep sets.\" Advances in neural information processing systems 30 (2017).", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed orbit-equivariance is a new symmetry for GNN, and two new datasets are provided with the required symmetry.\n2. From the experimental results, the proposed Orbit-Indiv-GCN can achieve much better performance compared to original GCN model on the new datasets.", "weaknesses": "1. The figure and illustration of concept is concrete, but it is better if conceptual understanding is provided. The current writing flow is a little hard to follow.\n2. The proposed Bioisostere data is obtain by RdKit which is based on semi-emperical methods, and accurate geometry can be obtained through DFT calculation like QM9 and OC20.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)