Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability
Authors: Zehao Dong
Muhan Zhang
Philip Payne
Michael A Province
Carlos Cruchaga
Tianyu Zhao
Fuhai Li
Yixin Chen
Venue: ICLR 2024 poster (2024)
Keywords: Graph neural networks
Graph canonization
Stability
Primary area: learning on graphs and other geometries & topologies

Abstract: The expressivity of Graph Neural Networks (GNNs) has been studied broadly in recent years to reveal the design principles for more powerful GNNs. Graph canonization is known as a typical approach to distinguish non-isomorphic graphs, yet rarely adopted when developing expressive GNNs. This paper proposes to maximize the expressivity of GNNs by graph canonization, then the power of such GNNs is studies from the perspective of model stability. A stable GNN will map similar graphs to close graph representations in the vectorial space, and the stability of GNNs is critical to generalize their performance to unseen graphs. We theoretically reveal the trade-off of expressivity and stability in graph-canonization-enhanced GNNs. Then we introduce a notion of universal graph canonization as the general solution to address the trade-off and characterize a widely applicable sufficient condition to solve the universal graph canonization. A comprehensive set of experiments demonstrates the effectiveness of the proposed method. In many popular graph benchmark datasets, graph canonization successfully enhances GNNs and provides highly competitive performance, indicating the capability and great potential of proposed method in general graph representation learning. In graph datasets where the sufficient condition holds, GNNs enhanced by universal graph canonization consistently outperform GNN baselines and successfully improve the SOTA performance up to $31$%, providing the optimal solution to numerous challenging real-world graph analytical tasks like gene network representation learning in bioinformatics.

Published as a conference paper at ICLR 2024
RETHINKING THE POWER OF GRAPH CANONIZATION IN GRAPH REPRESENTATION LEARNING WITH STABILITY
Zehao Dong' Muhan Zhang² Philip R.O. Payne" Michael A Province" Carlos Cruchaga Tianyu Zhao Fuhai Liš7 Yixin Chen (zehao. dong, prpayne, www.mpioiiicmm ice, cruchagac, htaasssstt chenScse. wustl. edu & muhan@pku.edu.
ABSTRACT
The expressivity of Graph Neural Networks (GNNs) has been studied broadly in recent years to reveal the design principles for more powerful GNNs. Graph canonization is known as typical approach to distinguish non-isomorphic graphs, yet rarely adopted when developing expressive GNNs. This paper proposes to maximize the expressivity of GNNs by graph canonization, then the power such GNNs is studies from the perspective of model stability. A stable GNN the vectorial space,
will map similar graphs to close graph representations and the stability of GNNs is critical generalize their performance unseen graphs. We thcoretically reveal the trade-off of expressivity and stability in graph- canonization-enhance GNNs. Then we introduce notion of universal graph canonization as the general solution to address the trade-off and characterize a widely applicable sufficient condition to solve the universal graph canonization. A comprehensive set of experiments demonstrates the effectiveness of the proposed method. In many popular graph benchmark datasets, graph canonization success- fully enhances GNNs and provides highly competitive performance, indicating the cupability and great potential of proposed method in general graph represen- tation learning. In graph datasets where the sufficient condition holds, GNNs enhanced by universal graph canonization consistently outperform GNN baselines and successfully improve the SOTA performance up to 31%, providing the opti- mal solution to numerous challenging real-world graph analytical tasks like gene network representation learning in bioinformatics. Our source code is available at
INTRODUCTION
Graph Neural Networks (GNNs) Kipf & Welling, 2016 Hamilton et al. 2017 Xu et al. 2019 Velickovic et al.) 2018 You al. 2018 Scarselli al. 2008 Duvenaud 2015 Gilmer et al.
2017/ZZhag et al. 2018) are dominant architectures for modeling the relational structured data. GNNs implicitly leverage the inductive bias in the graph topology by iteratively passing messages between nodes to extract a node embedding that encodes the local substructure, showing great expressivity and scalability to extract representative features for graph learning problems. Due to the superior representation ability and scalability, GNNs have achieved impressive results on various graph-structured data, such as social networks (Monti et al. [01 7 Ying al. 2018), protein networks
(Fout 2017: Zitnik et al. 2018) and circuit networks (Dong et al. 2022a).
Numerous efforts (Xu et al. 2019 Morris et al., 2219)) have been put in analyzing the effectiveness of GNNs and indicate that popular GNNs, which mimic the 1-dimensional Ceisfeiler-Lehmae (1- WL) algorithm/color refinement algorithm (Leman & Weisteiler 1968), suffer from the limitations
Department of Computer Science & Engineering, Washington University in St. Louis. Institute for Artificial Intelligence, Peking University. Institute for Informatics, Data Science, and Biostatistics. Washington University School of Medicine Department of Genetics. Washington University School of Medicine 5 Department of Psychiatry, Washington University School of Medicine Department of Radiation Oncology. Washington University School of Medicine Department of Pediatries, Washington University School of Medicine Corresponding authors.

---

Published as a conference paper at ICLR 2024
of 1-WL in the expressive power. Hence, the dominant approach to enhance the performance of GNNs is to improve their expressivity. Informally, recent powerful GNNs achieve this purpose
from four perspective. (1) High-order GNNs (Morris et al. 2019 MMron et al. 2019) mimic the
higher-order WI. tests to improve the expressicity beyond 1-WI; Subgraph-hasn
GNNs (Zhang You et al. [222 Bevilacqua al., 2021) encode (learnable) local structures (i.e. induced
& L 2021
k-hop neighborhoods) of nodes, thus formulating hierarchies of local isomorphism on neighborhood
subgraphs to beat 1-WL. (3) GNNs with markings (Papp et al. (021)) slightly perturb the input graphs for multiple times to execute GNNs and then aggregates the final embeddings of these perturbed graphs in each run. (4) Feature augmentation GNNs (Abboud et al. 2020 Lim et al.) 2022) add
pre-computed/lernt node features to improve the expressivity. Overall, these expressive GNNs are powerful, yet still far from efficiently distinguishing any pair of nonisomorphic graphs. For instance, high-order GNNs and GNNs with markings are not scalable to large-scale graphs due to the space and time complexity, while subgraph-basee GNNs have an upper bounded expressicity as there always exists graphs (Papp& & Wattenhofer 2022) distinguishable by 2-WL (3-WL) yet not distinguishable by subgraph- based GNNs.
Graph canonization generates the canonical form of a graph G that is isomorphic to any graph in it's isomorphic group IS)(G), then any two graphs are distinguishable by checking whether their canonical forms are identical. Thus, graph canonization maximizes the discriminating ability of non-isomorphic graphs. As for the concern of the complexity, though determination of the canonical form of graph is shown to be NP-hard Babai & Luks (1983), canonization tools such as Nauty (McKay & Piperno| (0144) can effectively find the canonical form of a reasonable-sized graph. For instance, Nauty has an average time complexity of On)) and polynomial canonization al algorithms also exist for graphs of bounded degrees. Hence, we propose to enhance GNNs with graph canonization.
graph
The positional encoding scheme (Vaswani et al. 2017) is introduced in the sequence encoding problem to describe the position of an entity in a sequence so that each position associated with a unique representation. In recent years, it is widely adopted in graph Transformers (Yan et al. 2020 Dong et al., 2022b), and we resort to this scheme when applying graph canonization in GNNs. For a graph G' with node set V {U1, 1/2, .... }. the graph canonization finds a bijective function p(v GG) from V onto {1, 2, n such that the canonical form of G can be obtained by reordering nodes according to the generated discrete colouring {p(va] [G), p(1y G). p(e, }. Since isomorphic graphs have the same canonical form, function p(u G) provides a unique way to label nodes in graphs from the same isomorphic group ISO Thus, our proposed
saaph--annnzzaioo-enaaaaa take one-hot encodings of [p(m (G), p( (02 (G.,...,,r p(un, [G)} as nodes' positional encodings, which help to maximize the expressive power in graph classification.
GNNs
In the design of deep learning models, the generalization behavior (Bartlett et al. 2017) also plays a critical role for competitive performance. Inspired by [Wang al. (0022). we study how well GNNs are generalized to unseen graphs with the model stability. Informally, stable GNN can map similar graphs to close graph representations the vectorial space. In the graph canonization problem, similar graphs may have complete different discrete colourings {p(r) |G), p()))(())))))))))) ...; p(un [G), causing graph representations learnt by GNNs fail to capture the similarity of input graphs when GNNs are enhanced by graph canonization. We theoretically prove that GNNs using graph canonization to generate nodes' positional encodings are unstable. Thus, there is a trade-off between the stability and expressivity in GNNs equipped with the graph canonization
enhancer.
In the paper, we theoretically prove that the trade-off can not be generally addressed due to the iitividdaaliaatio-refeeen
paradigm used in practical graph canonization tools. Consequently, we develop a notion of universal graph canonization to address the trade-off. Though the universal graph canonization problem is also NP-hard, we characterize widely applicable sufficient condition when it is solvable through an injective (node labeling) function GGG V + N, which utilizes the augmented information across the whole graph dataset G [G,Inn ..., to introduce node asymmetry consistent with subgraph isomorphism in G. That is, for any common subgrpah G' of G and G2 in dataset G, the output of 7 [G1|G] and 7 (G2 are identical on subgraph G', Then, GNNs with nodes' positional encodings of {r(e, [ (G), ..., T(e, [G}} is proven to be stable, indicating that GNNs enhanced by universal graph canonization can maximize the expressivity while maintaining the stability.
2

---

Published as a conference paper at ICLR 2024
The key contributions in this paper as follows: 1) we propose novel alug-and-ples architecture to enhance GNNs by generating nodes' positional encodings with graph canonization algorithms, and theoretically study its' strengths and limitations. The proposed suaph--cmmnizatiio-nnaaanee GNN (GC-GNN) has the maximized expressivity in distinguishing non-isomorphic graphs, and theory reveals the trade-off between the expressivity and model stability. 2) We theoretically solve the trade-off by introducing a notion of universal graph canonization, and propose a widely applicable sufficient condition to solve it for numerous graph datasets, including gene networks, brain networks, Bayesian networks, etc. 3) A comprehensive set of experiments demonstrates the effectiveness of proposed method. In popular graph benchmark datasets, GC-GNN successfully enhances GNNs' performance and achieves competitive results. In graph datasets where the universal graph canonization is tractable by our sufficient condition theorem, the GNNs enhanced by the universal graph canonization (UGC-CGNN) consistently outperforms GNN baselines and improves the SOTA performance up to 31% over baselines.
1.1 OTHER RELATED WORKS
Graph canonization problem is proven to be NP-hard (Babai & Luks, 1983). Practical canonization tools such as Nauty (McKay & Piperno 2014) and Bliss (Junttila Kaski 2012 are developed to effectively find the canonical form in practice. PATCHY-SAN (Niepert et al. 2016) uses graph canonization tools black-box function to determine the global/local node order that CNNs can be applied to fixed-size patches extracted from nodes' neighborhood. On the other hand, PFGNN (Dupty et al. 202T) train neural architectures with particle filtering mimic the paradigm of individualization and refinement (McKay & Piperno. 2014 Junttila & Kaski 2011 in practical graph canonization tools.
2 GRAPH CANONIZATION AND STABILITY OF GNNS
In this section, we introduce useful concepts. and then reveal the trade-off between the expressivity and stability in GNNs enhanced by graph canonization. Let = (V, E,, e) denote a colored graph of n nodes, where V = {V1, U2...., Un)
is the set of nodes, E E V x V is the set of edges, and the function e : V + N associates to each node an integer color (node type). The edge information is always expressed as adjacency matrix A e {0, 1]"Xn such that A. 1 iff edge (i.j) E.
colouring of is surjective function from the node set onto a set of k integers. In this paper, We use "colouring" to denote both the image of this surjective function (i.e. set of integers). A colouring is discrete l = n, then each cell (i.e. set of nodes with the same image) is singleton.
2.1 GRAPH DISTANCE AND STABLE GNNS
Let V + V be permutation operation on the node set V. We denote by nt the image of any node V, then π (G) (i.e. permutation operation on graph G) generates another colored graph (G) = G = EV,E*,C , c*) such that (1) (Ef eg) E ET iff (u,, U2) E E (i.e. A A = Ap, and (2) (2) (x") c(v). Each permutation operation æ associates to a n-dimension permutation matrix pd (0, 1) n where each row and each column has only one single All the permutation operation on graphs of n nodes formulate a permutation group I[(n).
Given two n-size graphs G, (Vi, c)). G2 = (V2, E2, 02) and their corresponding adjacency matrix A and A2. there exists permutation operation n" E II()) associates the permutation matrix Px that best aligns the graph structures and the node colors (i.e. node features),
p argmin PP Ea00=
The distance between two graphs is thus characterized d(Gr, = ||A - Pd P' A
Σ, (i)) (2)) (1)), which measures the similarity of two graphs of the same size.
Equipped with the notion of graph distance, characterize the the stability of GNN models. The GNN model provides graph representation vector based on adjacency information and node features, then we express it as 9(A A, X), where X is 2-dimension tensor of one-hot features of node colors.
3

---

Published as a conference paper at ICLR 2024
Figure 1: Overview of graph canonization techniques in the design of GNNs. Graph canonization improves the expressivity of GNNs at the cost of stability. Consequently, universal graph canonization is proposed to alleviate the problem.
Unless specified, following theoretical analysis assumes a GNN model consists of several message passing (MP) layers and sum readout layer.
Definition 2.1 (Stability). A GNN model g is claimed to be stable under X. if there exists a constant C' > 0, for any two graphs G1, G2. satisfies [19(A1, - 9(2,, X2) S Cd(G1, G2).
In analog to Wang al. (0222) the stability of GNN model guarantees that similar graphs in the graph distance space will be mapped to similar representations the vectorial space. Hence, it will provide good generalization ability to apply GNNs unseen graphs. Overall, the stability and expressivity are two fundamental design principles of GNN architectures. The stability helps to bound the gap between the representations of an unseen testing graph and a similar but different training graph, while the higher expressivity enables GNNs to recognize more graph structures.
2.2 GNNS WITH GRAPH CANONIZATION
Two colored graphs Gi and G2 of n nodes are isomorphic (denoted by G₁ = G2) there exists permutation operation E II(m) such that (G1) G2. The set all colored graphs isomorphic to G' forms it's isomorphism class ISO(G) = {G |G' G), while automorphism of G is an isomorphism that maps G onto itself.
Definition 2.2 (Graph canonization) Graph canonization fn. is function that maps a colored graph to an isomorphism of the graph itself (a graph ISO(G)) such that Vo [T(n), (G) = (T())
In other words, graph canonization assigns to each coloured graph an isomorphic coloured graph that is unique representative of its isomorphism class. The order of nodes fn (G) denoted as p(u| Then, the graph canonization provides a unique discrete colouring {p(0) [G), ()) ...., ((U,, G)} as nodes' positions for each isomorphism class ISO(G) to break the symmetry of nodes.
Let P be 2-dimension tensor of one-hot features of the discrete colouring generated by an arbitrary graph canonization algorithm. A GNN model g that takes P as nodes' positional encodings maximizes the expressivity, if gruph convolution layers of g are injective.
Lemma 2.3
Let P be a 2-dimension tensor of one-hot features of the discrete colouring generated by a graph canonization algorithm follows the individualizatioo--eeneee g is stable under X, and is not stable under X ④ P, where C denotes the concatenation operation.
Lemma 2.4
paradigm. GNN model
We prove lemma 2.3 and lemma 2.4 in Appendix C Graph canonization algorithms that follow the wwwiiiualiiaiiooreeeeeeee
(2017) will respect the order of initial node colors/types when breaking ties to introduce the node asymmetry, thus there always exists similar graphs to have complete different discrete colourings as Figure 2
paradigm (Groh
illustrates. These two lemmas indicate the trade-off of expressivity and stability in GNNs enhanced by graph canonization. Then, GNNs (GC-GNNs) can distinguish more graph structures in the training data, yet the ability of generalizing well to unseen testing data is deteriorated to some extend. Hence, we study how to overcome this trade-off in next section. Furthermore, since the graph canonization problem is Na-hard, and practical tools like Nauty (McKay & Piperno| 2014) and Bliss (Junttila & Kaski 22122) for the problem always follow the dadividualizatiionrrfeeee paradigm, the trade-off not generally solvable in practice.
seaph-canonization-ebeee
4

---

Published as a conference paper at ICLR 2024
3 UNIVERSAL GRAPH CANONIZATION
In this section, we first introduce the notion of universal graph canonization, and theoretically prove that it can maximize GNNs' expressive power without losing the stability. Then we propose a widely applicable sufficient condition to apply GNNs with universal graph canonization in numerous graphs.
3.1 UNIVERSAL GRAPH CANONIZATION
Ideally, the maximally powerful GNNs are expected to be expressive and stable. Thus, our goal is to generate discrete colouring {T(w), (r2),,.... ((,)) that is equivalent to the output colouring (p(m/[G), ((v2)G),... p(,,]()()))))) of general graph canonization algorithm in breaking the node symmetry, while maintaining the stability to provide better generalization performance.
Definition 3.1 (Universal graph canonization) Ler G {G,li = ........J N) be a graph dataset. discrete colouring function T( (G: V > N is claimed as an universal graph canonization for G, Y common subgrpah G' of G1, G2 E G. r(Gi]G) and (G) are identical in G'.
is straightforward that the output discrete colouring [ T(o))))))) G)} of the proposed universal graph canonization is equivalent to {o(vi [),, p(v2 p(..,,,,,,,) ((), of general graph canonization algorithm in breaking nodes' symmetry and distinguishing non-isomorphic graphs. Both of them will be same for isomorphic graphs and be different for non-isomorphic graphs, one can get the canonical form of an input graph by sorting nodes according to the discrete colouring (G), (v. (G)]
The main difference between the output discrete colourings (r |G), (v..
and {p(r)/G), ( .... p(),,G)) is their resistance ability to graph perturbations. The graph canon- ization tools employ the technique of mndividualizatio--eeineeeee
to sequentially refine a colouring until it is discrete. Then, the output discrete colouring {p(vi p(vz|G),.... ((v,,/)) is heavily dependent on the order of nodes to individualize, which is determined by the symmetry in the graph structure. Consequently, even a small perturbation that breaks the symmetry. such as recoloring a single node, may causes a significant change of the sequence of individualized nodes, resulting in compete different output colouring. That is, the change of output colouring happens across all nodes regardless of their geometric relation to the position of the perturbated node. Figure provides an example as the illustration. After we recolor the top yellow node as orange (i.e. G + G2), the output discrete colouring (i.e. numbers nodes) of left triangle and bottom triangle are completely different, yet these subgrpahs are isomorphic in G1 and Gg. contrast, the universal graph can- onization generate the discrete colouring conditioned
whole graph dataset G to guarantee the color consistency among subgraphs G' of any pair of graphs in G. Thus, the graph perturbation to nodes/edges outside G' will not affects generated colours within G'.
Let G(v[G) be an universal graph canonization for dataset G, and T be the 2- dimensional tensor of one-hot features of discrete colouring (T(v)]G), ( (v, (r.)))).),,, [)). A GNN model g under + T is stable, where a denotes the concatenation operation.
Theorem 3.2
We prove Theorem in Appendix D. This theory guarantees that GNNs enhanced by universal graph canonization (CCGNNs) are stable. In addition, since universal graph canonization is equally powerful as the general graph canonizaton in distinguishing non non-isomorphic graphs, UGC-GNNs can also maximize the expressive power in graph discrimination.
3.2 A SUFFICIENT CONDITION FOR GNNS WITH UNIVERSAL GRAPH CANONIZATION
Having recognized the stability and expressivity of UGC-GNN, we next discuss its' applicability in real-world graph representation learning. The main challenge to effectively solve the universal graph canonization problem where many practical tools, such as Nauty (McKay & Piperno 2014) and Bliss (Junttila & Kaski 2012), developed to effectively implement the algorithm, there is existing software to solve the universal graph canonization problem. Furthermore, according to the definition 3.I this problem is at least hard the subgraph isomorphism problem, thereby is ha-hard.
given dataset G. Unlike the general graph canonization problem
5

---

Published as a conference paper at ICLR 2024
Figure 2: Illustration of the limitation in graph canonization follows the individualization-reeue paradigm. In the example, initial node colors/types follow the order: orange blue < yellow. Then, two similar graphs G1 and G2 will always have complete different discrete colouring generated by graph canonization algorithms.
Lemma 3.3 Let [v]GG: V + N be injective function. [(v[G) is universal graph canonization,
if (I) for V Un un E G₁, 12. U2 E G2. G1, G2 E G such that 1(v [G) = 1(02 (G) and I(u, [G) G)) we have (v), En (12, E2, where <> is equivalence relation. Or (IT)
G(u]G) is independent of G.
Application scenarios We prove Lemma 3.3 in Appendix E and this lemma provides a sufficient condition to compute the universal graph canonization. Together with the definition 3.1 universal graph canonization is tractable in numerous scenarios: (1) In gene networks Shuhendler et al. (2010)
Dong et al. (2023), each gene appears at most once in each gene network, and the connection of any pair of genes Is shared among different gene networks, then [(u) GG) can be extracted by lexico- graphically sorting all genes appear the dataset; (2) In brain graphs Li al. (202T); Venkataraman et al. (2016), the brain FMRI images are parcellated into ROIs (regions of interests) as nodes, and edges are computed by the functional correlation matrix between ROIs. Since these ROIs can be pre-ordered across all brain images, these pre-orders traffic networks such as METR-LA and Roadnet-CAl CC Li et al. (2017). nodes represent fixed intersec- tions road endpoints whose pre-defined orders can be treated as the output of I(u]G). (4) Many well-known computer vision datasets such as MNIST and CIFAR10 are also transformed to graph signals fixed-gen bood--rid-lik like structures, where I(t: G) can be defined by lexicographically sorting nodes' grid positions, and these datasets have become benchmarks for graph learning recently Dwivedi et al. (2020); (5) In many DAG learning problems Zhang et al. (2019), such neural architecture search (NA) and Bayesan structure learning (BN), the function (2]G) can be obtained by sorting nodes according to their positions the Hamiltonian path in NA or to their node types BN.
be used the output of the I(v]G). (3) In
Readout layer Both message passing layers and readout layers contribute to GNN's s learning ability the graph-level prediction. Thus, UGC-GNN also propose to incorporate the discrete coloring (G),
[G] in the readout layer to break nodes' symmetry. Specifically, weighted summation over set node representation [A E V} is used, where the trainable weight matrices associated w.r.t the discrete colouring {((0)
Readout (h- v E V}) = Σ Wi
VEV
Here, A. is the output representation of node in the last (7'-th message passing layer of UGC-GNN. Thus, UGC-GNN introduces node asymmetry in both graph convolution layers and readout layer.
Lemma 3.4 UGC-GNN is permutation invariant.
We prove Lemma 3.4 in Appendix F As nodes in a graph have no intrinsic ordering, GNN model should also be permutation invariant the permutation operations. That is, VP e 11(n). we have g(A, X) = g(PAPT AX). Machine learning model fail to do so will lead to a waste of training data and computation time. Hence, the proposed UGC-GNN is stable, maximally expressive, and permutation- invariant. -nntutaaiooninvriiann.
4 EXPERIMENTS
In this section, we evaluate the effectiveness of proposed graph-canonizaaion-enin competitive GNN baselines. Concretely, first conduct experiments synthetic datasets and TU datasets to test the general performance of proposed method (GC-GNN). Then we demonstrate the superiority of our UGC-GNN when universal graph canonization is solvable through proposed
GNNs against

---

Published as a conference paper at ICLR 2024
sufficient condition, and use challenging gene network datasets, brain graph dataset, DAG datasets as the benchmark this scenario. Details of datasets are provided in Appendix A
4.1 DATASETS
Synthetic datasets and TU datasets. EXP (Abboud et al. 2020) and CSL (Murphy et al. 2019)
are two graph isomorphism test datasets where non-isomorphic regular graphs are required to be distinguished. Specifically, the EXP dataset contains 600 pairs of 1- WW.-indistinguishable but non- isomorphic graphs, while the CSL dataset contains 150 4-regular graphs from 10 isomorphism groups. TU datasets (Dobson & Doig 2003] Toivonen et al., (003) include five graph datasets: PROTEINS, PTC-MR, MUTAG, ENZY MES, D&D. TU datasets are widely used to perform the graph classification task.
Gene network datasets. Gene networks ubiquitous in bioinformatics. In the experiment, we select three gene network datasets: RosMap, Mayo, and Cancer, for the challenging graph classification tasks in bioinformatics. Mayo and RosMap are designed for the Alzheimer's disease (AD) classification (De Jager et al.] 2018 Allen et al. 2016); Cancer is designed for the cancer subtype classification. In gene networks, gene expressions are used as node features, while edges between genes are collected from KEGG (Kyoto Encyclopedia of Genes and Genomes) Kanehisa & Goto 2000) based on the physical signaling interactions from documented medical experiments.
Brain graph datasets. Brain graphs in the public dataset fMRI ABIDE Di Martino et al. (2014) take as nodes the ROIs (regions of interests) parcellated from brain FMRI images, and use the computed functional correlation matrix between ROIs as edges. The objective is to classify the brain state.
DAG datasets. This experiment contains two DAG datasets: NA and BN. In dataset NA, neural architectures generated by the software ENAS (Pham et al. (2018). and the corresponding weight- sharing (WS) accuracy on CIFAR-10 10 (Krizhevsky et al., (2009) is pre-computed for each arcitecture. In dataset BN, Bayesian networks (DAGs) are randomly sampled by the bnlearn package (Scutari 2010). Each DAG is associated with a Bayesian Information Criterion (BIC) score that measures the architecture performance on dataset Asia (Lauritzen & Spiegelhalter 1988).
4.2 BASELINES AND EXPERIMENT CONFIGURATION
The experiment takes three types of baselines: (1) popular GNNs and graph Transformers that
achieve top places on OGB leaderboard: GCN (Kipf & Welling 2016), GIN (Xu et al.
2019 b
GAT (Velickovic et al. 2018). GraphSAGE (Hamilton et 20.1)) SAN (Kreuzer et al.
2021
Graphormer (Ying et al. 2021 ; (2) Expressive GNNs beyond I-WL: NGNN (Zhang & Li
2021
GCN-RNI (bbboud et al. 22220). PNA (Corso et al. (020)) GINE (Brossard et al. 2020).
PPGN
Maron et al. 2019), GraphSNN (Wijesinghe & Wang. 2022 and GNN-AK+ (Zhao et al.
2021
SignNet (im et al.] (0022), ESAN (Bevilacqua al. 2021. ,, -DooGGNN (Papp et al. 2021):
Dominant DAG GNNs: GraphRNN (You et al. 2018), S- VAE [Bowman et al. 2016)) D-VAE (Zhang
al. 2019) DAGNN(Thost & Chen 2021). (021).
Gene networks have received considerable attention in bioinformatics and numerous deep learning (DL) models are developed recently to analyze gene networks. Thus, beside above GNN basclines, we also compare our UGC-GNN against powerful DL models in bioinformatics: Transyynergy Liu &
Xie (202T) SANEpool Dong et al. (2023), Decagon Zitnik al. (2018), DimiG[Pan & Shen 2019
MLA-GNN Xing et al. (2022). J. We thoroughly introduce graph- structured data in bioinformatics and
their DL baselines Appendix H to explain why we select above DL models as additional baselines.
We perform 10-fold (or 5-fold) cross validation for robust comparison. All experiments are imple- mented in the environment of PyTorrh using NVIDIA A40 GPUs. Our graph-canonization based GNNs take backbone GNNs from [GIN, GCN, GraphSAGE, GAT). In GNN baselines, the embed- ding dimension of graph convolution layer is set to be 32. The number of graph convolution layer se- lected from the set (2, 3, 4). The graph-level readout function is selected from {mean, sum, sortpool). In NGNN, we use height-1 rooted subgraphs to avoid the off-ooymymory problem in gene network datasets. The experimental settings follow Dong al. (2022b) on dataset NA/BN and follow Zhang & Li (202T) on TU datasets. The training protocols is composed of the selection of the evaluation rates and training stop rules. Specifically, the learning rate of optimizer picks the best from the set
7

---

Published as a conference paper at ICLR 2024
{le - 4, le 3. 2}; the training process is stopped when the validation metric does not improve further under a patience of 10 epochs.
4.3 EVALUATION OF GC-GNN
To test the general performance of GNNs enhanced by graph canonization (i.e. GC-GNN), we conduct experiments to answer following questions: Q1: Can GC-GNN empirically achieve the maximal expressive power in distinguishing non-isone isommrppii graphs? Q2: To what extend can GC-GNN improve the predictive performance without ameliorating the model stability?
Answer to Q1 (Table [1 Here we start with the first question. In this experiment, we test the expressive power of GN-GNN on two synthetic datasets, EXP and CSL. use GIN and GCN as backbone GNN. As Table [ shown, for any backbone GNN, GC-GNN can significantly improve the expressive power and distinguishes almost all the 1-WL indistinguishable graphs.
Medel GC-GNN (GEN)
Tran Auoenyy
Tisi Accanay
Trie Awarrdy
Telt Apsency
0.908 08082
0.926 0JR55
0.5964 CJA0S
013883 0.099
GCA-NN (GAN)
3J81
1.001 GJMI
E18667 (.1072
Table 1: Evaluation of expressive power on synthetic datasets for graph isomorphism test.
Answer to Q2 (Table 2 Lemma 2.4 demonstrates the limitation of GC-GNN. This experiment empirically show that GC-GNN can still achieve impressive performance when the stability concern not well addressed. The widely adopted TU datasets are used as the example, and Table [rreeents the results. 1) GC-GNN consistently brings performance gains to GNN backbones by large margin, and the erformance gain is up to 29. 29.6% 2) Nested GNN has been shown to a powerful plug-and-play framework to improve GNNs' expressivity beyond 1-WL. Compared to this popular subgraph- baseed GNN, GC-GNN also provides a considerable performance improvement without the additional spacelcomputation cost raised by the subgraph extraction. 3) Compared to recent powerful GNNs like GraphSNN, GNN-AK+, SignNet, ESAN, etc, GC-GNN can still achieve highly competitive performance. For instance, GC-GNN significantly improves the of-e--of-the-at performance on D&D to an accuracy above 90%.
GUN Ducddwee GIN Dusdhwer (eecleee)
316.1
314 10.
11.
25.11:51
324 3.35
09.6
Tu6 43
51. 9.3
64
2.0-2.4
19.9=10.
720
578
Noved OCN
233.2.33
13.:5.1..1
15.3 43
$2.3 9-2
31.2 67
Nevel ON
315-2-33
673
75 5.1
26-0- 80
Nand GAT
250-2-44
8.9 10
75.7
56.7
26.1 6.7
346-1-3
57.8-16
21.3 1.9
516-115 3.5
16.
GIN-AK+
8.5
55.1
36.5
756
GKN-D06
33. 3.5
1664 02 7.4
13.5 4.5
35.2 0.3
361
BresGNNN
5.6
1914 T/)
76.3
02.7
GCOIN (Ge)LAAGGE)
2014 = 8.5
755 4.0
02.3
GC-GNN
2:4-2.55
30.2200
49
(GA))
9.5
756
ingrovenent over haddvas Mas, Avc. iegroveenn onr Notte GNN
20.0%
18%
1864
19.77
3
3.5
10.3
12.%
Improveent
Table 2: Prediction accuracy (%) TU datasets. Highlighted are the best results.
4.4 EVALUATION OF UGC-GNN
Though we have shown the huge potential of GC-GNN in enhancing GNNs, the loss of model stability still raises challenges when applied to some graph datasets, especially these with large-scale graphs For instance, gene networks in datasets Mayo, Rosmap and Cancer contain more than 3000 nodes, then Table shows that GC-GNN with a backbone of GIN even performs worsen than GIN. More similar ablation results are available in Appendix G Another example is the experiments on OGB datasets. Appendix B shows that GC-GNN can improve base GNNs on OGB datasets (ogbg-molhiv, ogbg-molpeba) to a close performance to ESAN with ED policy, yet they are comparable the SOTA performance. These results empirically demonstrate the importance of maintaining GNN's s stability and the necessity of designing UGC-GNN.
The superior representation learning ability. (Table Baadd Table 4 This experiment evaluates UGC-GNN against powerful GNN baselines on many real-world datasets where Lemma 3.3 can
8

---

Published as a conference paper at ICLR 2024
Mayo
Redhay
ABR-ARIDE
Mebala
Fl Flwect
P1
BPN
8.51 4.0.-M
0535 0021
0.33 - 6054
0.51 4 6003
0.00-000 -0.0
[.50 -4.03
8.677 0.331
0.66 8-333
PSA
0.51 6.037
8:54 0796
8.00- 6055
0158111 - 006
0638 086
[66) -481
8 8663 6/77
0.88 0-77
0.71
0372 4
0521 1122
NGNN
8.0333
8231
0318 054)
0.57
TEON
0469
0901
0.332
0.31 8.31
0534
0.250
Sight
0227 0.333
0.229
0244
0.33 0034
0.77-1000 1.0055
00M
00M
0 0302-8-0000
Buay 2 0063
1LV1 1060
00H
D0M
0507 1/W0
DE BEANNGGINI
8 0177--0001
0.86 R0K
0.500 F003
(15)) 1133-8-00 664
0537 01166
Table 3: Experimental results on bioinformatical tasks: gene network datasets and brain graph datasets. Shown is the mean s.d. of 10 runs with different random seeds. Best results are highlighted.
N4
Patsur
GEN
ES37 01311
p:57 01311
Hottob
Areray
Autrnyy
SANtppo
E482 E236
&
D-DAE
[3841 0::85
(105 0111
2311 5 U164
0084 (:31
0.50 0.30
-0321
5.63
0.511 0042
6:39 0004
4
1:25 1180
B1ed 0.0
0534 (-91
0.512
-381
0,57-
1.5% 5.632
0 0U2S
0.544 6i05
0353
01811
-0.01
MLS DAN
0.588
00851
0.31
0034
8:85 6/04
3822
5.00
0649
0311-0991:
335
0455 -0901
009
0054-0.00
06041 6696
0,70
4.82
0,7011 0/25
0,08 0019
8714.
8.701 9,33
TGCGNNNCIN) 12551
1202
006 EXII
03577 (192 0.36
Table 5: Comparison to powerful DL baselines in Bioinfor- matics. Shown is the mean + s.d. of 5 runs with different random seeds. Best results are highlighted.
Table 4: Experimental results on DAG
datasets. Best results are highlighted.
help to find the universal graph canonization. Table 3nd Table show that UGC-GNN consistently achieves the state-of-the-art (SOTA) performance and can provide a performance improvement up to 31% over GNN baselines.
Efficiency.. Another significant advantage of enhancing GNNs with universal graph canonization is the time/space complexity. Suppose the graph has n nodes with maximum degree d. then UGC- GNN has a space complexity of (n) and each layer takes ((d) operations. In contrast, high-order GNNs like PPGN has a space complexity of O(n2) for each layer and a O(n²) time complexity; Subgraph-based GNNs (to radius r) has a O(nd") space complexity and each layer takes O (1d"+1) operations. In many real-world tasks especially in bioinformatics, graphs has large n and which makes existing dominant expresive GNNs (high-order GNNs and subgraph-based GNNs) unsuitable. Table indicaaess that existing dominant expresive GNNs can easily have the our-of-memory (OOM) problem (like ESAN and DropGNN), while Appendix showws that UGC-GNN can significantly reduce the computation time. Sepeifically, UGC-GNN only requires about 1 and 1 epoch compared to subgraph- basedd GNN (NGNN) and high-order GNN (PPGN), respectively.
10 average time per
The optimal solution to the challenging gene network analysis. Table 5 Gene networks are the prevailing data structure in Bioinformatics (Podolsky & Greene] 2011 Carew et al. 2008). Recent years, has emerged as popular topic of developing the de facto standard for effective representation learning methods over gene networks, which leads to potential advancements in clinical applications
including drug synergy prediction (Hopkins) 2008 Podolsky & Greene, (01I). Alzheimer's s discase (AD) detection (Song al. 2019 Qin et al. (022)) and cancer subtype classification (Lu & Han 2003). In the experiment, we compare UGC-GNN against existing SOTA deep learning (DL) models for gene network analysis. Table indicates that UGC- outperforms these DL. models and is
the optimal solution to the challenging gene network analysis.
5 CONCLUSION AND DISCUSSIONS
In this paper, we propose to enhance GNNs through graph canonization that generates discrete colouring of nodes their positional encodings to introduce node asymmetry. We theoretically show that wwwpph-cannnizztinnennannccee GNNs (i.e. GC-GNNs) maximize the expressivity in distinguishing non-isomorphic graphs at the cost of model stability, and then design a universal graph canonization to ameliorate this trade-off under widely applicable sufficient condition that is satisfied in numerous real-world graph datasets. Massive experiments demonstrate the capability and great potential of GC-GNN in general graph representation learning; Furthermore, GNNs enhanced by the universal graph canonization (i.e. UGC-GNNs) show superior predictive ability and consistently achieve the state-of- -he--rrt performance when the sufficient condition is satisfied, providing the optimal solution to many real-world applications like the challenging gene network representation learning in bioinformatics.

---

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. arXiv preprint urXiv:2010.01179, 2020.
Mariet Allen, Minerva M Carrasquillo, Cory Funk, Benjamin D Heavner, Fanggeng Zou, Curtis Younkin, Jeremy D Burgess, High-Seng Chai, Julia Crook, James A Eddy, et al. Human whole genome gen and transeriptome data for alzheimer's and other neurodegenerative diseases. Scientific data, 3(1):1-10, 2016.
László Babai and Eugene Luks. Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM symposium Theory of computing, pp. 171-183, 1983.
Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-norrmaizzedd margin bounds for neural networks. Advances neural information processing systems, 30, 2017.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2110.0200 2021.
Samuel Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from a continuous space. In Proceedings of The 20th SIGNLL Conference Computational Natural Language Learning, pp. 10 2016.
Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:201 15069, 2020.
Jennifer S Carew, Francis Giles, and Steffan T Nawrocki. Histone deacetylase inhibitors: mech- anisms of cell death and promise in combination cancer therapy. Cancer letters, 269(():7-17, 2008.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances Neural Information Processing Systems, 15:13260-132777 2020.
Philip L De Jager, Yiyi Ma, Cristin McCabe, Jishu Xu, Badri N Vardarajan, Daniel Felsky, Hans- Ulrich Klein, Charles C White, Mette Peters, Ben Lodgson, et al. A multi-omic atlas of the human frontal cortex for aging and alzheimer's ' disease research. Scientific data, 5(1):1-13, 2018.
Adriana Di Martino, Chao-Gan Yan, Qingyang Li, Erin Denio, Francisco X Castellanos, Kaat Alaerts, Jeffrey Anderson, Michal Assaf, Susan Y Bookheimer, Mirella Dapretto, et al. The autism brain imaging data exchange: towards large-scale evaluation of the intrinsic brain architecture in autism. Molecular psychiatry, 19(6):659-667, 2014.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4))771-783, 2003.
Zehao Dong, Weidong Cao, Muhan Zhang, Dacheng Tao, Yixin Chen, and Xuan Zhang. Cktgnn: Circuit graph neural network for electronic design automation. In The Eleventh International Conference on Learning Representations, 2022a.
Zehao Dong, Muhan Zhang, Fuhai Li, and Yixin Chen. Pace: A parallelizable computation encoder for directed acyclic graphs. arXiv preprint arXiv:2203. 2022b.
Zehao Dong, Heming Zhang, Yixin Chen, Philip RO Payne, and Fuhai Li. Interpreting the mechanism of synergism for drug combinations using attention based hierarchical graph pooling. Cancers, 15 (17):4210, 2023.
Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee. Pf-gnn: Differentiable particle filtering based approximation universal graph representations. International Conference on Learning Representations, 2021.
10

---

Published as a conference paper at ICLR 2024
David Duvenaud, Dougal Maclaurin, Jorge equilera-Iparraguunn Rafael Homee-Bommarelll Timo- thy Hirzel, Alán Aspuru- Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in Neural Information Processing Systems, 2015:2224-203 2232, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Alex M Fout. Protein interface prediction using graph convolutional networks. PhD thesis, Colorado State University, 2017.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1263-1272. PMLR, 2017.
Martin Grohe. The logic of graph neural networks. In 2021 36th Annual ACM/IEEE Symposium Logic in Computer Science (LICS), pp. 1-17. IEFE, 2021.
Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. Van den Broeck, G.; Kersting, K.; Natarajan, S, 30, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL https:t//prcceeeennnngg mewrepss.......o...e.e.......r.s http:///p...ccppppp//////L// ppf
Andrew L Hopkins. Network pharmacology: the next paradigm in drug discovery. Nature chemical biology, 4(1 1):62-6690, 2008.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00682 2020.
Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling. In Theory and Practice of Algorithmss in (Computer) Systems: First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, Proceedings, pp. 151-162. Springer, 2011.
Tommi Junttila and Petteri Kaski. bliss: A tool for computing automorphism groups and canonical labelings of graphs. URL http://www. tcs. hut. f//Software/bliss, 2012.
Minoru Kanehisa and Susumu Goto. Kegg: kyoto encyclopedia of genes and genomes. Nucleic acids research, 28( 28(1):27-30, 2000.
Thomas N Kipf and Max Welling. Semi-supervise classification with graph convolutional networks. arXiv preprint arXiv: 1609, (609900997, 2016.
Devin Kreuzer, Dominique Beaini, William L Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.0388) 03893, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Steffen L Lauritzen and David Spiegelhalter. Local computations with probabilities on graphical structures and their application expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2): 157-194, 1988.
AA Leman and Boris Weisfeiler. A reduction of graph canonical form and an algebra arising during this reduction. Mauchmo-Techhiccesssee Informatsiya, 229): 1968.
Xiaoxiao Li, Yuan Zhou, Nicha Dvomek. Muhan Zhang, Siyuan Gao, Juntang Zhuang, Dustin Scheinost, Lawrence H Staib, Pamela Ventola, and James S Duncan. Braingnn: Interpretable brain graph neural network for fmri analysis. Medical Image Analysis, 74:102233, 2021.
11

---

Published as a conference paper at ICLR 2024
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv: 2017.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra. Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202. 13013, 2022.
Qiao Liu and Lei Xie. Transynergy: Mechanism-driver interpretable deep neural network for the synergistic prediction and pathway deconvolution of drug combinations. PLoS computational biology, 17(2) 008653,, 2021.
Ying Lu and Jiawei Han. Cancer classification using gene expression data. Information Systems, 28 (4):243-268. 2003.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii Journal of symbolic computation, 60:94-1:9100 112, 2014.
Federico Monti, Michael M Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-grape grapih neural networks. arXiv preprint arXiv:1704.06803, 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 on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023 PMLR, 2016.
Xiaoyong Pan and Hong-Bin Bin Shen. Inferring discase-associated micrornas using semi-supervised multi-label graph convolutional networks. Iscience, 20:265-277, 2019.
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning, pp. 17323-17345. PMLR, 2022.
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-220099 2021.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, pp. 4095 4104. PMIR, 2018.
Scott H Podolsky and Jeremy A Greene. Combination drugs hype, harm, and hope. New England Journal of Medicine, 365(6):488 491, 2011.
Zhiwei Qin, Zhao Liu, and Ping Zhu. Aiding alzheimer's disease diagnosis using graph convolutional networks based on rs-fmri data. In 2022 15th International Congress Image and Signal Processing, BioMedical Engineering and Informatics CCISPBMMET pp. 1-7. IEEE, 2022.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Marco Scutari.
Learning bayesian networks with the bulearn r package. Journal of Statistical Software, 35(103), 2010.
12

---

Published as a conference paper at ICLR 2024
Adam J Shuhendler, Richard Y Cheung, Janet Manias, Allegra Connor, Andrew M Rauth, and Xiao Yu Wu. A novel eexorubicin-mitomyar co-encapsulated nanoparticle formulation exhibits anti-cancer synergy in multidrug resistant human breast cancer cells. Breast cancer research and freatment, 19(():255-26) 2010.
Tzu-An Song, Samadrita Roy Chowdhury, Fan Yang, Heidi Jacobs, Georges El Fakhri, Quanzheng Li, Keith Johnson, and Joyita Dutta. Graph convolutional neural networks for alzheimer's disease classification. In 2019 IEEE 16th international symposium on biomedical imaging (ISBI 2019), pp- 414-417. IEEE, 2019.
Veronika Thost and J. Chen. Directed acyclic graph neural networks. ArXiv, abs/2101.07965, 2021.
Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10):1183-11 2003.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6000-6010, 2017.
Petar Velickovic, Guillem Cucurull, A. Casanova, Adriana Romero, P. Lio', and Yoshua Bengio. Graph attention networks. ArXiv, abs/1710.10903, 2018.
Archana Venkataraman, Daniel Y-J Yang. Kevin Pelphrey, and James Duncan. Bayesian community detection in the space of group-level functional differences. IEEE transactions medical imaging, 186611886 2016.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arXiv:2203.00/ 209999 2022.
Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lehman?. In International Conference on Learning Representations, 2022.
Xiaohan Xing, Fan Yang. Hang Li, Jun Zhang, Yu Zhao, Mingxuan Gao, Junzhou Huang, and Jianhua Yao. Multi-level attention graph neural network based on co-expression gene modules for disease diagnosis and prognosis. Bioinformatics, 38(8):2178- 77877166611111 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https
//openreview net Dipenerrreew.ntt/ooommdadoodo
Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representa- tion learning help neural architecture search? Advances in Neural Information Processing Systems, 33, 2020.
Chengxuan Ying, Tianle Cai. Shengjie Luo, Shuxin Zheng, Guolin Ke. Di He, Yanming Shen, and Tie Yan Liu. Do transformers really perform bad for graph representation? arXiv preprint arXiv:2/06.0m 052444 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I. Hamilton, and Jure Leskovec. 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
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, pp. 77108-5777. PMLR, 2018.
Jiaxuan You. Jonathan Homes-Selmant Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. arXiv preprint 1rXiv:2101.1030 2021.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
13

---

Published as a conference paper at ICLR 2024
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning archi- tecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: A variational autoencoder for directed acyclic graphs. Advances in neural information processing systems, 32, 2019.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gmn with local structure awareness. arXiv preprint arXiv:2110.03753, 2021.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):157-i466, 2018.
14

---

Published as a conference paper at ICLR 2024
A REPRESENTATION LEARNING TASKS ON GENE NETWORKS AND OTHER GRAPH BENCHMARKS
In the natural world, genes don't operate independently and always function as part of a set of genes. Hence, they can be regulated as the graph modality based on reported genetic interactions that underlie phenotypes in a variety of bioinformatical systems. Then, various computational tasks on gene networks (graphs) are proposed in recent bioinformatics to numerically analyze contribution of genes to complex disease humans. In this work, we take two bioinformatics, Alzheimer's disease (AD) classification and cancer subtype classification, as example, and introduces corresponding gene-network datasets. Here we compare the these gene network datasets against popular graph benchmark datasets to illustrate challenges of graph representation learning over gene networks.
challenging tasks in
Dataset
Ave. nodes
Ave. edges
Tasks
Task Type
Metric
Mayo
3000
60000
Classificution
Accuracy & F]
RosMap
3000
60000
2
Classification
Accuracy & F1
Cancer Subtype
3800
48000)
Classification
Accuracy & H1
12
Regression Regression
RMSE & Pearson't RMSE Pearson'r
BN
15
ogbg-molhiv
26
55
Classificution
ROC-AUC
ZINC
23
50
Regression
MAE
D&D
284
1431
Classification
Accuracy
MUTAG
18
39
Classification
Accuracy
PROTEINS
39
146
Classificution
Accuracy
PTC-MR
Classificution
Accuracy
ENZYMES
33
124
Classification
Accuracy
Table 6: Comparison of gene networks and graphs in popular benchmark datasets
Table 6 presents preliminary results. Compared to graphs in popular benchmarks, gene networks always contain significantly large number of nodes (denoted as well the number of edges (denoted as m), which limits the applicability of popular expressive GNNs due to the complexity consideration. For subgraph-based GNNs like NGNN (Zhang & Li 202I). the space complexity grows exponentially as the average node degree increases. For high-order GNNs, such as k-WL (Moris et al. 2019) and F-F (Grohe 202T), that mimic the high-order WL algorithms, the stable rrrreenintrrrresennattiinnn can be computed in Otk"n** log n) with space complexity of O(n*). Consequently, is hard to apply these methods to gene network representation learning.
B MORE DISCUSSION OF GC-GNN AND UGC-GNN
In this section, we provide more discussion of GC-GNN.
Part 1: Limitations of GC-GNN and UGC-GNN.
Part 2: The complexity of GC-GNN and UGC-GNN.
Part (Table One significant limitation of GC-GNN and UGC-GNN that the (universal)
graph canonization fail to consider the heterogeneity among edges. In addition. GC-GNN is also not guaranteed to be suitable for all graph learning tasks. Here we empirically test GC-GNN on moleculr datasets, ogbg-molhiv and ogbg-molpete provides empirical results. As we can see, GC-GNN still improve the performance over backbone GNNs and GC-GNN can achieve competitive performance to the powerful GNN baseline: ESAN with ED policy. However, we also notice that the improvement of GC-GNN is not significant as TU datasets and GC-GNN can not achieve the SOTA performance. In order make fair comparison, set the number of epochs for training to be
in Open Graph Benchmark (Hu et al. 2020 Table
Part The main concern of complexity comes from the graph canonization algorithms. As we discussed in the main paper (section 1.1, other related works), although graph canonization is well- know completee problem. practical canonization tools such as Nauty (McKay & Piperno 2014) and Bliss (Junttila & Kaski 2012), can effectively solve the problem in practice with an average time
15

---

Published as a conference paper at ICLR 2024
ogbg-molhiv (AUC1)
ogbg-molpcha (AP 1
GCN (backbone) ESAN (GCN + FD)
0.7501 +: 0.0140
0.2422 0.0034
0.7559 +: 0.0120
0.2521 0.0040
GN-GCN
0,7552 + 0.0156
0,2510 + 0.0047
GIN (backbone)
0.7744 + 0,0098
0.2703 + 0.0023
ESAN (GIN
0.7803 + 0.0170
0.2782 0.0036
GN-GIN
0,7785 + 0.0195
0.2761 + 0.0043
Table 7: Empirical results on molecular datasets.
complexity of (n). The process of computing the canonical forms of graphs can be implemented in the graph pre-process phase and we only need to perform practical graph canonization tools once for each graph. Furthermore, as the output discrete colouring {p(1g p (G),..p(r,,(G) of graph canonization are used as positional encodings of nodes, the additional space complexity is also (nn). Hence, compared to dominant expressive GNNs like subgraph- -ased GNNs and high-order GNNs, GC-GNN (UGC-GNN) is much more efficient with a significant low space and computation cost. For instance, on ogbg-molhiv, GC-GNN (GIN) takes 39 seconds per epoch, while Nested GIN takes 168 seconds.
C PROOF OF LEMMA 2.3 AND LEMMA 2.4
We first prove Lemma 2.3 Since discrete colouring [p(r)]G), p(r))))))))))...... ((v](G) generated by graph canonization provides a unique way to label nodes for graphs in the same isomorphic group ISO(G), then the isomorphism of two graphs can be determined by checking whether the node pairs of the same labels share the same edge relation. When the graph convolution layers GNN g are injective, can injectively map the pair node and the set its' neighboring nodes. then if two graphs get different sets of learnt node embeddings by the GNN g. there must exists least one pair node label and the set of its' neighboring nodes' labels are different. Then, these two graphs not isomorphic. On the other hand, when two graphs least one pair of nodes with the same labels, while the pair of nodes are connected in one graph yet disconnected in another graph. Then the graph convolution layer will output different embeddings for each node in the node pair.
isomorphic, there must be
Next, we prove Lemma 2.4 to support theoretical results about the stability of GNNs and GC-GNN: Before proving our lemma, we first introduce some necessary preliminaries that we will later use in the proofs.
Preliminary 1: Decomposition of message passing layer of GNNs The message passing scheme adopted in popular GNNs iteratively updates a node's representaaiio//embedee multiset of its neighbors' representations/embbddiie ht, denotes the representation of in layer f, the massage passing scheme is given by:
according to the and its current representation/mbeeding Let
h++1
M(h, (ui E E})
u(h A(thulu, v) E E}))
Here, A is an aggregation function on the multiset S = (ui E E}) and U is an update function.
Definition C.1 A function f is claimed as L-stable multiset function if 1) Enes f(h) unique for each multiset of bounded size; and 2) for any two multisets S and S2. Exes, [(h)- Eves, f(h') II| < L x ds(Si, where dy (s(S1, S2) |S11 | |S S2).
The L-stable multiset function provides unique mapping between the multiset space and represen- tation space, while distance between multisets in the representation space are bounded through the constant multplier L.
Corollary C.2 Assume that feature space H. is countable. Any message passing function function M over pairs (h, S), where h. E and S C HH, can be decomposed as M(h, o((1 + (h)
16

---

Published as a conference paper at ICLR 2024
function f. some function and infinitlly many choices of Ewes ( for some L-stable multiset function e.
This corollary C.2 can be obtained by following the Lemma 5 and Corollary 6 in Xu et al. (019). Basically, since the space HI is countable, we can always get a mapping Z H N from E H to natural numbers. As S are bounded multiset, there always exists upper bound B of their cardinality such that |S] < B for any S. Hence, the example function f(h) B -()( satisfies both the uniqueness condition as well as the inequality condition in Definition
C. where the constant
L n
Preliminary 2: Graph canonization and hatpluuiiiiiattii-aa--eeeeeeeeee paradigm Here we provide an extended discussion on the graph canonization and individualizaaioo--eeieen paradigm. To address the complex graph isomorphism/ graph canonization problem, practical graph canonization tools resort to the individualization-nn refiieeeen paradigm, where the color refinement and individualization steps are iteratively performed to get a discrete colouring.
1. Color refinement step: The color refinement algorithm aims to recolor nodes in graph by similarity. The algorithm starts with some initial node colors, then the algorithm updates node's s color round by round, and in each round, two nodes with the same color will get different new color if the multiset of neighboring colors are different. This process continues until equitable colouring is obtained such that the node colors will not change even if another color refinement round happens.
2. Individualization step: When a stable colouring generated by the color refinement step is discrete, then returns a order of nodes in the canonical form. However, in many cases, the stable colouring are not discrete. Then the individualization step selects node in a color class with more than one node and assigns new (unseen) color to the node. Then the color refinement step is implemented again.
Specifically, in the color refinement step, the new colors are obtained by lexicographically sorting the pair of node current color and it's multiset of neighboring colors. Hence, the new order of new node colors always follows that of the previous colors. That is, at round t, if two nodes v, u have (u) < (v)), then after one round of color refinement, the new colors of these two nodes have c (u) < (v))
different colors c'(u) and et (v) such that c'
Above catuualizaiion-efineeeeee paradigm in practical graph canonization tools provide solution to obtain a discrete coloring, yet not in a canonical way. That is, generated discrete coloring is not guaranteed to be the same for graphs in the same isomorphic class. To fix this, practical tools usually branch on all nodes of the same color in the individualization step and individualizes one node in each branch. Then a tree of colouring can be obtained such that each leaf of the tree is discrete coloring of the input grpah G. Then the final discrete colouring is selected, for example, as the leaf with the lexicographically minimal string that consists of the rows of the adjacency matrix according to the discrete colouring (i.e. node orders). More details can be found in McKay & Piperno (2014).
Proof. (Part one: A GNN model g is stable under X) Here, we assume the function & in the decomposition of message passing layer of GNNs is K-Lipschitz. A function Φ (X, dz) + (Y, dy) between two metric spaces K-Lipschitz if (g(((()). 6(22)) - [dg(#1, 22) for any ø1, 22 E X, where K is a constant.
Corollary C.3 MLPs are K-Lipschitz.
In popular message passing GNNs, ő is always modeled by a MLP. Hence, we need to prove corollary c to use the K-Lipschitz assumption. For each MLP layer that characterized by the trainable parameter tensors W, and by (bias), it can be represented as a oW + by), where a is the activation function. Then we have [|o[W, + 6.) - oW,2z2 + b,)1l || 2 W2 22)]]. Since the activation function usually takes ReL.U/sigmoidtanh, it's straightforward that || @= is bounded by constant K1. Then we get de W1(x1 22)1l < K, ||lllalll - x2l1. where Kj [Wll2 is constant independent of z; and x2. Hence, we show that MLPs are K- K-Lipschitz
Next, let's prove the theoretical result. Without loss of generality, we assume that the GNN contains single message passing layer. For any two graphs (()) (A(), x() and ((2) (A(2), X(2)),
17

---

Published as a conference paper at ICLR 2024
m' E [I(n) denotes the optimal permutation operation that best aligns the G1 and G2, and P is the corresponding permutation matrix. Then we have,
11ta111 x(1) - x(
=|| Σ o((l +(x++))(x+)++
Σ
(X E al +(1+0111
E
seat))
JEN a(l)
< Σ [0((1+0)(xx+++
Σ
(X oi(l + +
E
1XX
(2)
eEG())
JEN 6(1)
(o)
sK Σ 11++))x(;1)
E
((x))) (1+ (1+e) (0))
Σ
(3)
.ca())
(oV( o(3)
+))
Σ lIf(x! - 1(x ((x))))) K Σ ||
Σ
1(x9)
E
1(x
)|
(4)
vec()
e d'ENCIOO)
XX
Σ _ # * + x ds ((
(5)
SK x LX+ ()d((()) )
(6)
Here, we use the K-Lipschitz property in the step (4), and use the property of s-stable multiset function in step (6). Furthermore, (N G denotes the set of neighboring nodes of in G and can be characterized by the uth row of adjacency matrix A (N (v) (G2)) denotes the set of neighboring nodes of v's image in G2, and can be characterized by the vth row of adjacency matrix Pa A(2) p-T Hence, we show that GNN g is stable under with a constant C' of K x L. x (1 + e).
Proof. (Part two: A GNN model g is not stable under X @ P) Here we provide a counter example. Let G be graph of nodes such that 1) there is no node symmetry in the graph; 2) the node v. has an initial color (integer feature) that is strictly larger than the colors of other nodes. Then, we obtain a graph ((2) by changing the initial color of node Un in G(1) to another color which is strictly smaller than the colors of other nodes. Then, we know that there is no node symmetry in the
graph ( either. Furthermore, it's straightforward that the best graph matching n¹ [[()) between G() and ( is (i) = i for Vi = =12,... and the corresponding permutation matrix P = 7 is an identity matrix.
Since there is no node symmetry in G(2) and G(2), the color refinement step in graph normalization tools will generate discrete colourings for G(1) and G(2) Let ((()) (())) corresponding discrete colourings. As we discussed in preliminary 2, the output discrete colouring from color refinement will keep the order of initial colors. Hence, we know that p(u, ( = n, ((v))G(2)) and p(u; p(u,)G()) = p(vi(G(2) + 1 for ((D))(()) # ((2))G(2) for i = 1,2,.... ..., indicating that P * p!!) for Vo. Thus, we have,
[))) and {p(vi] ( p(v2 ((2)), "......,,,,,((""
denote the
1,2, 1. Thus, we get
(1)(A(1), x1)) 0(1 (x)))1
2|| Σ (1 ()((x())) p( - -((((2) + P(2))
eE
(1+ + c) x | x B
(8)
> (1) G(2))
(9)
Since the function f is defined on the multiset whose cardinality is bounded by the overall graph size n, we get B < [GL)
D PROOF OF THEOREM 3.2
Proof. Following the proof of Lemma 2.4 we consider the same decomposition scheme M(h, S) Φ((1 +c) ΣN's es ((h)) of the message passing layer, yet the input space is X ( P (where P
18

---

Published as a conference paper at ICLR 2024
is the 2-dimensional tensor of one-hot encodings of discrete colouring generated by universal graph normalization), instead of the input feature X.
Then, let's consider any pairs )) and A( (1) ((()) Since the discrete colouring in any common subgraph G' GO) and G are identical, the number of same items in multisets (x(")l Ju' E (W( )) and (x(e) ju (M(T")))))) will not change if we replace x-1) with x p and x(2) with x²2 + +p())
Then we get,
Σ
s(x + p
E
1(x + )))
o (ENGGGG)
Σ
5(x!))
Σ
1(x(?))
(10)
V ('EN(NGG))
(')G(1)))
Thus, we have
" xx0)
=|| Σ o(1 (() + p(P)+
Σ
1(X + (lll
vEGL)
o ('E((IG
Σ ([(x)) + +P!)
Σ
1(x9) + PP
(II)
mEG())
<K Σ |[(++)) +P: +
Σ
1(x + +P!))
- + +1+ff(x( (t()) + + ())
Σ
f(x() !! ||
(12)
(1)
<k(I+e) Σ |1((X!) + PP - [(x
+ p()) P((
DEG(1)
K Σ Σ f(X() - +P(!)-
Σ
f(x!9) a +P())11
(13)
eEG
V'EN(OIGM)
a' (E
=K(1+d Σ !If(x!! + p(D)) - ((x x*()) + p(() ((
tGG()
K Σ Σ 1(x Σ
((x
(14)
( <K xx X ((
EGG
(15)
where we use the equation (11) in the step (14) to get step (15).
E PROOF OF LEMMA 3.3
Proof. Since the function ((v[G) : V + N is an injective function, it can distinguish nodes in each graph according to 1(v G). Furthermore, since for V U1, U1 E G1. U2 U2 G2, G1, G2 E G such that l(v,)(33 [(2g| and [(4,]G) = 1(uz)00 (G), we have (V,, u,) E Ej ++ (U2, U2 E Eg. we know that connectivity between node pairs (u, u) of the same label pairs ([(+ (w)G) is shared among all graphs. Let N be the total number of all potential different labels (v(g), then we can expand each graph to a larger graph of size N, where each node o has an order/position of ((v]g). and rest positions are padded by dummy nodes that is not connected with any other nodes. Then, any common subgraph G' of G1 and G2, is also common subgraph of their converted larger graphs, and it obivous that the orders of nodes in each common subgraph of these generated larger graphs identical.
19

---

Published as a conference paper at ICLR 2024
F PROOF OF LEMMA 3.4
Proof. Let G = X) be an arbitrary graph of size n, and AP E 11(n) where I1(n) is the permutation group. (1(1) [G), (er,))).....
is the discrete colouring of G generated by the universal graph canonization. The discrete colouring is invariant to the permutation operation P as graphs from the same isomorphic class has the same canonical form (so as the same output discrete colouring from universal graph canonization). Here, we use L to denote a 2-dimension tensor of one- hot features of this discrete colouring. Then, let G' (PAP" PX) (G' is isomorphic to G), then, the corresponding discrete colouring tensor is PL. Let M be a stack of message passing layers, then we have PM((A, X) M(PAPPT PX) for VX, A. Let R denote the readout function of UNGNN, that Ru(h,lu E V1) Vvev he then R is invariant to the order of (he/v E V) as the corresponding weight matrix Wi(EE)) is solely decided by node's discrete color ((v])). Hence, UNGNN g is a composition of functions R and M, then get:
g(PAP" PX) R(M(PAP= PX + PL))
= =R(M(PAP", ,P(X , + L))) (R(PM(A,X+)) = =R(M(A, X + L)) = ()),X)
G
MORE ABLATION RESULTS
Mayo
RosMap
Cancer Subtype
Methods
Accuracy
Fl score 1
Accuracy
Fl score
Accuracy
Fl score
GIN
0.496 + 0.042
0.484 + 0.036
0.471 + 0.039
(482 + 0.041
0.537 + 0.045
0.512 + 0.047
GCN
0.561 = 0.049
0.535 0.021
0.520 + 0.036
0.571 0.032
0.593 0.039
0.561 = 0.042
GIN
0.483 0.026
0.472 0.031
0.486 0.041
0.510 0.037
0.539 0.041
0.532 +: 0.069
GCN + GC
0.522 +: 0.019
0,539 :: 0.031
0,508 1: 0.032
0.527 4: 0.031
0.544 0.025
0,582 :: 0.042
GIN UGC
0.561 1: 0.027
0.570 1: 0.031
0.697 1 0.041
0.624 1: 0.037
0.589 0.041
0.562 1 0.069
GCN UGC
0.572 0.021
0.619 0.037
0.658 + 0.030
0.621 0.021
0.619 0.025
0.581 +: 0.031
UGC-GNN (GIN)
0.624= 0,036
0.713 0.022
0,701 0.025
0.689= 0,019
0,714= 0.011
0.701 0.032
UGC-GNN (GCN)
0.603= 0.031
0.652 0.020
0.724 0.021
0.697:: 0.019
0.691= 0.013
0.7061: 0.029
Table 8:
Ablation study results. GC = graph canonization, UGC universal graph canonization. Best
results are highlighted.
Ablation study reults. Table 8 This experiment tests the effectiveness of different components in UGC-GNN and empirically supports theoretical findings the paper. When comparing GIN (GCN), GIN + GC (GCN GC), and GIN + UGC (GCN + UGC), (1) we find GNNs with general graph canonization usually causes the decrease of the testing performance (i.e. GIN + GC; GIN, GCN + GC; ; GCN). This finding aligns well with Lemma 2.4 indicating that stability of GNN is of great practical importance in real datasets especially when graphs are large. (2) We also observe that GNNs with universal graph canonization significantly enhance the model performance, and the observation empirically supports the Lemma
3.3] Furthermore, we also find that GIN (GCN); GIN + UGC (GCN + UGC): and UGC-GNN (GIN or GCN). Consequently, the canonical information from the discrete colouring (1(v) (G) 1(2z) GG... (G)) enhance the base GNN architecture from the perspective of both message passing process and the readout function.
H GRAPH STRUCTURED DATA IN BIOINFORMATICS AND THEIR GNN BASELINES
The dominant graph-structure biological data in bioinformatics can be categorized into three types: (1) molecular graphs, (2) biological interaction graphs and (3) gene networks/graphs. Different types of these biological graph data have different SoTA GNN baselines.
In molecular graphs, atoms or other chemical compounds are used as nodes, and the bonds are formulated as the edges. Molecular graphs are homogeneous graphs and are widely used benchmark
20

---

Published as a conference paper at ICLR 2024
datasets in the field of representation learning on graphs and GNNs (graph neural networks). Typical molecular graph benchmark datasets include ZINC, QM9 Ramakrishnan et al. (2014). Molhiv in OGB (Open Graph Benchmark), etc. Dominant baseline deep learning models for these molecular graph datasets are popular GNN models, such as GIN, GCN, GINE, NGNN, PPGN, and these baselines are used in our experimnets.
In biological interaction graphs, nodes represent genes, drugs, disease, RNA, etc, and an edge indicates the existence of known association between entities connected by the edge. Thus, biological interaction graphs are heterogeneous graphs. Typical biological interaction graphs include gene-drug interaction networks in the drug synergy prediction task, drug-protein interaction networks Zitmik et al. (2018) in side effect prediction tasks, and miRNA-disead interaction networks Pan & Shen 2 in the disease classification task. For the representation learning tasks on biological interaction graphs, various task-specific graph neural networks are proposed, and here we provide
some popular examples: TransSynergy Liu Xie (202T) and SANEpool [Dong et al. (2023) for gene-drug interaction networks; Decagon for drug-protein interaction networks; and DimiG Pan & Shen (219)) for miRNA-disean interaction networks. Overall, these task-specific GNNs focus more how effectively construct the biological interaction graphs and represent initial features related to genes/drugs/ dise Instead of the architecture design of GNNs. Consequently, these task-specific GNNs may not be well generalized other graph learning tasks such the gene network representation learning. In the paper, we select TransSynergy, SANEpool, Decagon and DimiG as baselines. and compare them with the proposed UGC-GNN.
In gene graphs/networks, genes are used as nodes, and an edge is used to link two genes if there physical signaling interaction between the genes from the documented medical experiment Similar to molecular graphs, gene graphs/networks are also homogeneous graphs. Very limited works are proposed for gene network representation learning. MLA-GNN proposed for graph-level classification tasks on gene networks, thus it can be used as good baseline in the field.
I COMPUTATION EFFICIENCY
In this experiment, we compare the of computation cost of GNNs enhanced by graph canonization techniques (UGC-GNN) against dominant expressive GNNs to emphasize the advantage in effi ciency.(1) For high-order GNNs, PPGN has space complexity of O(n2) for each layer, while 1-2-3 GNNs has a space complexity of (n²)) for each layer. Then, when we test 1-2-3 GNN on Mayo, RosMap and Cancer, 1-2-3 GNNs always meet the OOM (out-of-memory) problem On the other hand, by reducing the embedding dimension and number of layers, PPGN can avoid OOM problem B in the main paper indicates; (2) For subgraph-based GNNs like NGNN (nested GNN), we also implement the similar strategy to restrict the radius of subgraphs to be smaller than 2, then NGNN can avoid the OOM problem, too. Consequently, here we compare the average computation time per epoch of UGC-GNN against NGNN and PPGN on large-scale datasets.
on these datasets as Table
Mayo
RusMap
Cancer
NGNN PPGN
48s
42s
334s
143s
126s
1261s
UGC-GNN (GIN)
13s
10s
89s
Table 9: Average computation time per epoch.
Table @demonttrates the experimental results. First, we find that UGC-GNN significantly reduces the computation complexity compared to high-order GNN PPGN, and this observation can be explained by the O(x2) time complexity of PPGN and the large size of graphs. On the other hand, NGNN suffers from large subgraph sizes caused by the large average node degree in these datasets, then the extra computation burden is also larger than popular graph datasets with small average node degree (like OGB and TU datasets).
In addition, we need to point out that ESAN with EGO and EGO+ policy can be considered as subgraph-based GNN. However, when the node-deleted subgraphs (ND) and the edge-deleted subgraphs (ED) polices are used, graph is mapped to the set of subgraphs obtained by removing a single node or edge, then ESAN can be understood through the marking prism. In our experiments. ESAN is equipped with ED policy.
21


Reviews:
[{"review_id": "lWhyVtmVNA", "reviewer": "Reviewer_abzL", "summary": "Authors propose to tackle GNN expressivity issues by graph canonization. Either using ordering of nodes implied by the referene data distribution (e.g. image or voxel datasets that can give canonical ordering of nodes) or by running existing fast canonization algorithms. Inclusion of this ordering is shown to improve GNN expressive power and performance on real-world datasets.", "questions": "Please address the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "I find the canonization of graphs to be a very intriguing avenue of making GNNs better or to automatically tailoring generic GNNs for a given data distribution if the canonization is specific for that distribution.\n\nThe authors do show that including such canonical order does improve the performance of backbone GNN architectures.", "weaknesses": "In general I find the paper quite problematic. Mainly due to the total disregard for related work. Let me split this in three parts:\n\n1) Including ordering of nodes as features is very close to other feature augmentation techniques, widely used for GNN expressive power improvements, such as adding random walk embeddings (https://arxiv.org/pdf/2110.07875.pdf), graph laplacian embeddings (https://arxiv.org/abs/2202.13013 https://arxiv.org/pdf/2201.13410.pdf) or even just random features (https://www.ijcai.org/proceedings/2021/0291.pdf). These are not mentioned among the types of expressive GNN architectures (only higher order and subgraph GNNs are mentioned), while conceptually they are very similar (add pre-computed features to increase power). Neither any of the experiments compare to these existing models. \n\n2) The selection of discussed subgraph-based GNNs is quite peculiar, as it skips in my opinion some of the most popular works in this context (such as DropGNN https://arxiv.org/pdf/2111.06283.pdf and ESAN https://arxiv.org/pdf/2110.02910.pdf as well as various follow up works to these of which there has been many). They also say that subgraph GNNs are not more expressive than 2-WL, which in general is definitely not true, for example see theorem 6.5 in https://proceedings.mlr.press/v162/papp22a/papp22a.pdf where the marking GNN is very closely related to the DropGNN and one of the ESAN variants mentioned above. Also as shown in Table 1 here https://openreview.net/pdf?id=8WTAh0tj2jC experimentally many of these expresive GNNs such as ESAN or DropGNN distinguish the usual 2-WL counter example graphs. (Note that here by 2-WL following the notation in those papers I mean the folklore WL hierarchy, where 2-WL is equal to the 3-WL in the usual WL hierarchy).\n\n3) The known results for the power of assigning unique identifiers to nodes, such as the seminal work of https://arxiv.org/pdf/1907.03199.pdf which shows that GNNs with unique IDs are universal, although generally we don't have a way to assign such IDs in a stable manner. In my eyes the UG-GNN in Tables 4 and 5 essentially just a direct application of this in cases where the data comes with a good ID assignment due to the nature of data distribution. \n\nNote that many more of works in all 3 categories exist, I just cited a few important ones that came to my mind as an example.\n\nNow moving on to the experiments, its again very strange that none of the aforementioned baselines, especially the pre-computed feature ones are included. And generally almost. no expressive GNNs from the past couple of years are included in the benchmarks (e.g. ESAN, CIN, etc.). Not even giving nodes random noise/random IDs is compared against, which is a very usual expressive GNN baseline. Actually it is interesting that in Table 1 the GC-GNN does not achieve 100% test accuracy in any of the cases, usually expressive GNNs manage to hit 100% or at least 99%, with GNN augmented with random features also managing >90% test set accuracy. Random features are usually underperforming other expressive GNNs due to the poor stability of feature (or random ID) assignment, but as the authors point out their GC-GNN can also suffer from poor ordering stability.  \n\nSo now, for me its completely unclear if this proposed expresivity enhancement is any better than existing, even simplest ones.\n\nWhile OGB benchmarks are mentioned, the model is not evaluated on any of them? Why is that? It is now the main standard GNN benchmark as the TU-Datasets usually have quite few graphs in them, which can induce high variance of the results.", "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": "ctr9Nh2VSU", "reviewer": "Reviewer_RfLx", "summary": "This work focuses on the problems of the expressive power of graph neural networks (GNNs) where they aim to enhance the expressive power of GNNs by graph canonization. To this end, the paper first reveals the trade-off between the expressivity and stability in GNNs enhanced by graph canonization, showing that graph-canonization-enhanced GNNs maximize their expressive power at the cost of model stability. The paper further proposes a universal graph canonization to tackle this trade-off under a sufficient condition. The advantages of the proposed models against some GNN baselines are validated by their experimental results on both synthetic datasets and several benchmark datasets.", "questions": "Please refer to weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clear and well-structured.\n\n 2. The theoretical results that reveal the trade-off between expressivity in distinguishing non-isomorphic graphs and the stability in GNNs enhanced by graph canonization are interesting. The theoretical findings have shown the limitations of applying graph canonization to enhance the expressive power of GNNs. The proposed universal graph canonization to tackle the trade-off between expressivity and stability is novel. \n\n 3. The experimental results of the proposed model, UGC-GNN, on several bioinformatical graph datasets are impressive and consistently outperformed some well-known GNN baselines.", "weaknesses": "1. Lack of experiments to compare the expressive power of the proposed models with high-order GNNs [1, 2] and subgraph-based GNNs [3, 4] in distinguishing non-isomorphic graphs. Since high-order GNNs also enhance the expressive power of GNNs, it would be helpful to conduct experiments to compare the expressive power of the proposed models and high-order GNNs. Are graph-canonization-enhanced GNNs more powerful than high-order GNNs and k-WL test algorithms?\n\n 2. Lack of computation cost comparison with k-WL-GNNs. High-order GNNs and subgraph-based GNNs may suffer from high computational cost when applied to large-scale graphs. The paper asserts that the proposed models are more efficient with a significantly low space and computation cost. It would be nice to provide empirical evidence to support the claim.\n\n 3. As shown in Table 7, the GC-GNN doesn't consistently enhance the performance of the GNN backbone. In some instances, the performance even diminishes. It would be beneficial to delve deeper into which graph properties might influence this fluctuation in performance when integrating the GNN backbone with GC-GNN or UGC-GNN.\n\n 4. The universal graph canonization problem is NP-hard. While the paper has provided a sufficient condition to compute the discrete coloring and discussed the applicability in several application scenarios, finding an injective function $l(v|\\mathbb{G})$ might be elusive or challenging for general graph learning contexts. Furthermore, if there could be multiple choices of $l(v|\\mathbb{G})$, it is unclear what the impact of applying different choices of $l(v|\\mathbb{G})$ is on the performance of the proposed model.\n\nOverall, the paper is well-written and easy to follow. The theoretical findings on the trade-off between expressive power and stability in graph-canonization-enhanced GNNs are interesting and the proposed universal graph canonization to tackle the trade-off is novel. Despite the potential high computational cost induced by the graph canonization algorithms and the effectiveness of the proposed models that might not be generalized to general graph datasets, the paper has provided some insights into the expressive power of GNNs enhanced by graph canonization methods. Therefore, the reviewer is inclined to accept the paper.\n\nReference\n\n [1] Weisfeiler and leman go neural: Higher-order graph neural networks, AAAI 2019.\n\n [2] Provably powerful graph networks, NeurIPS 2019.\n\n [3] Nested graph neural networks, NeurIPS 2021.\n\n [4] Equivariant Subgraph Aggregation Networks, ICLR 2022.", "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)