Unitary Convolutions for Learning on Graphs and Groups
Authors: Bobak Kiani
Lukas Fesser
Melanie Weber
Venue: NeurIPS 2024 spotlight (2024)
Keywords: graph neural networks
geometric deep learning
learning stability
unitary
orthogonal
Primary area: graph_neural_networks

Abstract: Data with geometric structure is ubiquitous in machine learning often arising from fundamental symmetries in a domain, such as permutation-invariance in graphs and translation-invariance in images. Group-convolutional architectures, which encode symmetries as inductive bias, have shown great success in applications, but can suffer from instabilities as their depth increases and often struggle to learn long range dependencies in data. For instance, graph neural networks experience instability due to the convergence of node representations (over-smoothing), which can occur after only a few iterations of message-passing, reducing their effectiveness in downstream tasks. Here, we propose and study unitary group convolutions, which allow for deeper networks that are more stable during training. The main focus of the paper are graph neural networks, where we show that unitary graph convolutions provably avoid over-smoothing. Our experimental results confirm that unitary graph convolutional networks achieve competitive performance on benchmark datasets compared to state-of-the-art graph neural networks. We complement our analysis of the graph domain with the study of general unitary convolutions and analyze their role in enhancing stability in general group convolutional architectures.

Unitary convolutions for learning on graphs and groups
Bobak T. Kiani*
Lukas Fesser
Melanie Weber
Data with geometric structure is ubiquitous machine learning often arising from fundamental symmetries in domain, such commutation-invaiiann in graphs and images. Group-convolutional architectures, which encode symmetries as inductive bias, have shown great success in applications, but can suffer from instabilities their depth increases and often struggle to learn long range dependencies in data. For instance, graph neural networks experience instability due to the convergence node representations sover-smoothing), which can occur after only few iterations of peassage-passinng reducing their effectiveness in downstream tasks. Here, we propose and study unitary group convolutions, which allow for deeper networks that are more stable during training. The main focus of the paper are graph neural networks, where we show that unitary graph convolutions provably avoid over-smoothing. Our experimental results confirm that unitary graph convolutional networks achieve competitive performance on benchmark datasets compared to sfate-of-the-are graph neural networks. We complement our analysis of the graph domain with the study of general unitary convolutions and analyze their role in enhancing stability in general group convolutional architectures."
in
1 Introduction
In recent years, the design of specialized machine learning architectures for structured data has received a surge of interest. Of particular interest architectures for data domains with inherent symmetries, such as permutation-invarian other symmetries that arise from fundamental laws of physics in scientific data.
in graphs and sets, translation-invarinne in images, and
Group-convolutional architectures allow for explicitly encoding symmetries as inductive biases, which has led to performance gains in scientific applications [ESM23, WWY20]; theoretical stud- ies have analyzed the impact of geometric inductive biases on the complexity of the architec- ture [MMM21. BVB21, KLL+24]. Graph Neural Networks among the most popular architectures for graph machine learning and have found impactful applications in a wide range disciplines, including in chemistry [GRK+21], drug discovery [ZAL18], particle physics [SBV20], and recom- mender systems [WSZ+ 22). However, despite these successes, several limitations remain. A notable difficulty is the design of stable, deep architectures. Many of the aforementioned applications require accurate learning long-range dependencies the data, which necessitates deeper networks. How- ever, it has been widely observed that group-convolutional networks suffer from instabilities their depths increases. On graph domains, these instabilities have been studied extensively in recent years, notably in the form of over-smoothing effects [RBM23), which characterizes the fast convergence of the representations of nearby nodes with depth. This effect can often be observed after only few it- erations of message- pasggggggggnngggggg (i.c., small number of layers) and can significantly decrease the utility of the learned representations in downstream tasks. While interventions for mitigating over-smoothing have been proposed, including targeted perturbations of the input graph's connectivity (rewiring) and skip connections, more principled architectural approach with theoretical guarantees is still
'John A. Paulson School of Engineering and Applied Sciences, Harvard; e-mail: bkiani@g harvard. edu John A. Paulson School of Engineering and Applied Sciences, Harvard: e-mail:
I lukas- seatas-fesserfas... harvard. edu
'John A. Paulson School of Engineering and Applied Sciences, Harvard; e-mail: mweberøg. harvard. edu *Code available at /att:://giihuit cww/Weber Bom//eber-GeeML/Uiiii BeeMMl/UnitaryyCCoolllutt
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

lacking, Similar effects, such as exploding or vanishing gradients, have also been studied in more general group-convolutional architectures, specifically CNNs [TK21, SF21, LJW* 19], for which architectural interventions (e.g., skip connections) have been proposed.
In this work, we take different route. Inspired by a long line of work studying unitary recurrent neural networks [ASBI6, 16, HSLI6, LCMR19, KBLL22], we propose to replace the standard group convolution operator with a unitary group convolution. By construction, the unitarity ensures that the linear transformations are norm-preserving and invertible, which can significantly enhance the stability of the network and avoid convergence of representations increases. We introduce two unitary graph convolution operators, which vary in the way the message passing and feature transformation are parameterized. We then generalize this approach to cover more general group- convolutollt architectures.
fixed point as its depth
Our theoretical analysis of the proposed unitary graph convolutions shows that they enhance stability and prevent over-smoothing effects that decrease the performance of their vanilla counterparts. We further describe how generalized unitary convolutions avoid vanishing and exploding gradients, enhancing the stability of group-convolutional architectures without additional interventions, such as residual connections batch normalization.
1.1 Related work
We now provide brief background into work that motivated and inspired this current study, deferring a more complete discussion to App. A. Unitary matrices have a long history of application in neural networks, specifically related improving stability for deep networks [SMG13, PMB13] enhancing the learning of long-range dependencies in data [BSP94, Hoc91, SMG13). [ASB16, 17, HSL16] implemented unitary matrices in recurrent neural networks address issues with the challenge of vanishing and exploding gradients inherent to learning long sequences of data in RNNs [BSF94, LJHI5]. These original algorithms were later improved to be more expressive while still being efficient to implement in practice [HWY18, LCMR19, KBLL22). For graph convolution, [HSTW20] discuss applications of the exponential map to linear convolutions; here, we use this same exponential map to explicitly apply unitary operators parameterized in the Lie algebra. For image data, various works [SGL18, LHA+19, 19, TK21, SF21, KBII122] design and analyze variants of orthogonal or unitary convolution used in CNN layers. These can be viewed as particular instance of the group convolution we study here over the cyclic group. More recently, proposals for unitary or orthogonal message passing have shown improvements in stability and performance compared to conventional message passing approaches 22, AEL*24, QBY24]. However, in contrast to our work, these methods do not always implement unitary transformation across the whole input (e.g. only applying it in the feature transformation) and in the case of [QBY24] can be computationally expensive to implement for large graphs (see App. A for more detail).
2 Background and Notation
We denote scalars, vectors, and matrices as c, w. and M respectively. Given a matrix M, its conjugate transpose and transpose are denoted Mt and M Given two matrices, A and B, we denote their tensor product (or Kronecker product) as A B. Given a vector wr its standard Fuclidean norm is denoted |/w.. For matrix M, we denote its operator norm as || and Frobenius norm as |||.
Group Theory Basics Symmetries ("invariances") describe transformations, which leave proper- ties of data unchanged ("invariant"), and as such characterize the inherent geometric structure of the data domain. Algebraically, symmetries can be characterized as groups. We say that group is matrix Lie group, if it is a differenniable manifold and a subgroup of the set of invertible n x matrices (see App. C). Lie groups are associated with Lie algebra, vector space, which is formed by its tangent space at the identity. A comprehensive introduction into Lie groups and Lie algebras can be found in [FH13, Hal15]. Throughout this work we will encounter the n-dimensional orthogonal (n) and unitary U(z) Lie groups, which are defined as
O(n) = (U E nX" UU = =
V(n) = (U E c :U =
(1)
2

---

Lie algebras of (n) and Un) are the set of skew symmetric (n) and skew Hermitian u(n) matrices respectively, i.e.,
o(n) {M R M + M O]. u(n) {M C"X" -M M =0] =
Given a matrix M E o(n) (or u(n)), the matrix exponential maps the matrix to an element of the Lie group exp(M M) O(n) (or U(n)). More details on unitary parametrizations can be found in App. C.2.
Graph Neural Networks We denote graphs by G (V,E) E) where V and É denote the set of nodes and edges respectively. For a graph on n nodes, unless otherwise specified, we let V = =1...... index the nodes and denote the adjacency matrix by A R and node features also often use D E R to denote the diagonal degree matrix where diagonal entry records the degree of node i. The normalized adjacency matrix is defined as A = D-1 AD-122 Given node feature matrix X IRaxda where row i denotes the di fia-dmennsioall feature vector of node i, graph convolution operators take the general form [K W16, ZK20]
Rnnd We
Sconv A) XW + AXW, + .... X
where Wo... W& Adea are trainable parameters. For ease of presentation, will often omit the adjacency matrix as an explicit input to the operation. Often, only a single "message passing" step included and the operation takes the simple form fconv(X) AXW. Eq. (3) is equivariant under any permutation matrix Pa E B since
Scome P Pa Pp =
(4)
We aim parameterize particular subset of these operations which preserve unitarity properties.
Group-Convolutional Neural Networks In general, linear convolution operation convg C" C" takes the form of weighted over linear transformations that equivari- ant to a given group G. For simplicity, we assume here that we are working with finite groups though this be generalized to other settings [KT18, CGKWI& 18, CW16]. Given input X C"Xe consisting of channels a vector space of dimension n, we study convolutions of the form
convo c
Σ TXW,
(5)
where Ti...., C are linear operators equivariant to the group G and W...., W E Coxe parameterized weight matrices. The graph setting is recovered by setting Tę A Similarly, for cyclic convolution as in conventional CNNs, one sets Tę to be the circulant matrices sending basis vector T&e; Giok where indexing taken mod n.
3 Unitary Group Convolutions
We first describe unitary convolution for data on graphs (equivariant to permutations) which is the main focus of our study and then detail general procedures for performing unitary convolutions equiv- ariant to general finite groups. Implementing these operations often requires special considerations handle nonlinearities, complex numbers, initialization, etc. which we discuss in App.
3.1 Unitary graph convolution
We introduce two variants of unitary graph convolution, which we denote as Separable unitary convolution (short UniConv) and Lie orthogonal/umitary convolution (short Lie UniConv). UniConv a simple adjustment to standard message passing and treats linear transformations over nodes and features separately. Lie UniCony, in contrast, parameterizes operations in the Lie algebra of the orthogonal/unitarry groups. This operation is fully unitary, but does not have the tensor product nature of the separable UniConv.
By introducing complex numbers, we can enforce unitarity separately in the message passing and feature transformation.
*In matrix form, entry [Pzlij is one if z()) = and zero otherwise.
3

---

Standard Message Passing
Unitary Message Passing
L=0
L=0
Magnitude
0.4
L=2
L=2
L=5
L=5
L=20
L=20
0.0
20
40
60
20 40
60
80
Node Index
Node Index
Figure 1: Comparison of standard linear message passing with iterates I*+1 = c(æ + Aæz) versus unitary message passing with iterates æL+1 exp(iA))z for graph 80 nodes connected a ring. The unitary message passing has a wave-like nature which ensures messages "propagate" through the graph. In contrast, the standard message passing has unique fixed point corresponding to the all ones vector which inherently causes oversmoothing in the features. Here, is chosen to ensure the operator norm of the matrix I + is bounded by one.
Definition (Separable unitary graph convolution (UniConv)). Given an undirected graph & over nodes with adjacency matrix A E R=*n, separable unitary graph convolution (UniConv) fucon Cnxd _ Ca takes the form
fuconv (X) = exp(iAr)XU, UU'= =I
where U e U'd) is a unitary operator and I R controls the magnitude of the convolution.
One feature of the complexification of the adjacency matrix is that messages propogate "waves" as observed for example in Fig. 1. Since A is a symmetric matrix, exp(iAr) is unitary for all values of E R and corresponds to vanilla message passing up first order: exp(iAr) I+ iAr O(P²). Remark 2.
We observe that performance real-world tasks is usually improved when enforcing unitarity in the node message passing where oversmoothing occurs, but not necessarily when enfore- ing unitarity in the feature transformation U. Thus, one can choose to leave U in Eq. (6) as fully parameterized (unconstrained) matrix as we often do our experiments.
More generally, one can parameterize the operation in the Lie algebra by first forming a skew Hermitian convolution operation geonv Cand Cnxd and then applying the exponential map. This approach has the benefit that it can be fully implemented using real numbers to obtain an orthogonal operator by enforcing constraints in the real part of the weight matrix W only.
Definition (Lie orthogonal/unitaryy graph convolution (Lie UniConv)). Given an undirected graph G over n nodes with adjacency matrix RRaxa, Lie unitary/orthogonal graph convolution (Ortho- Conv) fuconv Cuxd - @nx takes the form
Σ R=
Reanv (X)
= fucmn X) (xpp(gcov)
X geony (X)+
2 8cone (gcony (X)) + +....
k!
8conv (x)= = AXW. W + : =0
The operation of geony can be represented as vector-matrix operation voc(gcov((X)) A W vec(X) X) where A @ WT belongs in the Lie algebra. If W is real-valued, the above returns an orthogonal map since the exponential of real-valued matrix is real-valued.
Implementing the exponential map The exponential map in Definitions and 3 can be performed using accurate approximations with typically constant factor overhead in runtime. We the simple K-th order Taylor approximation
M
| K+1
exp( M)
+0
(K + 1)!
k=0
For experiments, we find that setting K = 10 suffices all cases as the error exponentially decreases with K. Various other accurate and efficient approximations exist detailed in App. C.2. We also

---

refer the reader to App. E for other implementation details associated to handling complex numbers, initialization, etc.
3.2 Generalized unitary convolutions
In the more general setting, we are concerned with parameterizing unitary operations of the form
conv
T,XW;
i=1
where ....... Tm Cuxn are linear operators equivariant to the group G and W..... W m Cexe are parameterized weight matrices (e.g.. set Tą = A to recover graph convolution). One can enforce and parameterize unitary convolutions in Eq. (9) in the Lie algebra basis or in the Fourier domain as detailed in App. D.
Algorithm Unitary map from Lie algebra
Input: cquivariant linear operator L E C" C Input: vector C
I: L J(L L (skew symmetrize operator)
2: return exp( (x) (or approximation thereof)
In the Lie algebraic setting (Algorithm 1), one explicitly parameterizes operators in the Lie algebra or orthogonally projects arbitrary linear operators onto this basis by the mapping This parameterization is particularly simple to implement (it is linear basis) and unitary operators are subsequently implemented by applying the exponential map. This setting covers previous implementations of unitary RNNs and CNNs [LCMR19, SF21] and is detailed in Sec. 3.1 for GNNs.
(X- (X-X)) x/2
Example 1 (Convolution regular representation (Lie algebra)). Given group G and vector space V of dimension |G] with basis {eg g E G), then the left action Tg (right action Rg) of any g E G a permutation Tgee, = 1g-in (Ryen, Chg) )- Let x e CIGl be the vectorized form of an input C and G C the filter for convolution
function
(m * (u) = Σ m(u mm v)x(v) = co)va(
Σ m x. BCG
(10)
VEG
Parameterizing operations the Lie algebra simply requires that m(g) m(g " since Ry R
An example implementation of the above for a toy learning task on the dihedral group App. F.3. One can also generally implement convolutions in the (block diagonal) Fourier basis of the graph or group (see App. and Algorithm 3). Here, one employs Fourier operator which block diagonalizes the input into its irreducible representations or some spectral representation. Fourier representations often have the advantage of being faster to implement due to efficient Fourier transforms. Since we do not use this in our experiments, we defer the details to App. D.
4 Properties and theoretical guarantees
Unitary operators now well studied in the context of neural networks and have various properties that are useful in naturally enhancing stability and performance of learning architectures [ASB 16, SMG13, LCMR19, JSD*17 17, KBLL22). These properties and their theoretical guarantees are outlined here. We defer all proofs to App. B, many of which follow immediately from the definition of unitarity.
Throughout, we will assume that convolution operators act vector space V and built from basis of linear operators that is equivariant to input and output representation p(g) of a group G. We set input/output representations to be equal so that the exponential map of equivariant operator is itself equivariant.
Typically called cross correlaornn in mathematics literature.
5

---

Fact 1 (Basic properties), Any unitary convolution fucone V V built from Algorithms and 3 meets the basic properties:
(invertibllay): [eoos : V - -V such that Var E V Ueone (/ocomy (a))) x. (isometry): Vx E EV: [[f(conv(=)]]] ||=||
(11)
(equivariance): p(g) ficcov feconv a p(g).
A simple corollary of the above isometry property leveraged in prior work on unitary CNNs [TK21, SGL18] is that unitary matrices naturally provide robustness guarantees and provable means to bound the effects of adversarial perturbations (see Corollary 9 in App. B). For graphs, we note
that the properties above are generally impossible to obtain with graph convolution operations that perform single message passing step show below.
Proposition 4. Let foon Buudd Bundd be a graph convolution layer of the form
Samne (X,, A)= XWD AXW1.
(12)
where Wo. W1 Raxd are parameterized matrices. The linear map f(: : Baxd - Raxd is orthogonal for all adjacency matrices A of undirected graphs only if Wi 0 and Wo ((d) is orthogonal. Furthermore, denoting JA E Rndxad as the Jacobian matrix of the map fcone A).
any choice of Wo. W1, there always exists a normalized adjacency matrix À such that
[ II
(13)
2d
where [| is the operator norm of matrix M.
The above shows that one must apply higher powers of A as in the exponential map to achieve linear operator that is close to orthogonal.
Oversmoothing During the training of GNNs we often observe that the features of neighboring nodes become more similar as the depth of the networks (i.e., the number of message-passing iterations) increases. This "oversmoothing" phenomenon has strong connection to the spectral properties of graphs where convergence of function on the graph is measured through the Dirichlet form² or its normalized variant also termed the Rayleigh quotient.
Definition (Rayleigh quotient [Chu97]). Given an undirected graph G (V, E) on [V| n nodes with adjacency matrix A E {0, 1)nxn, let D E R=x" be a diagonal matrix where the i-th entry Dü di and di the degree of node i. Let f V Cd be a function from nodes features. Then
the Rayleigh quotient Rf()) is equal to
R 1 EiuL)ER
f(u)
[()) vdl
Tr (I(Xt(IAA (IX)
Vew
(14)
Σwev [l
|
where Ā D-2 is the normalized adjacency matrix and X ( is a matrix with the i-th row set to feature vector f(i). We will at times abuse notation and let X be an input to Rg(X),
Given an undirected graph & on n nodes with normalized adjacency matrix Ā ADD/ADD--- compare the Rayleigh quotient of normalized vanilla and unitary convolution. First, it is straightfor- ward to show that the Rayleigh quotient is invariant to unitary transformations giving a proof that unitary graph convolution avoids oversmoothing.
we
Proposition (Invariance of Rayleigh quotient). Given an undirected graph G on n nodes with normalized adjacency matrix À = D 1/2 1D21/2 the Rayleigh quotient R F (X)) is invariant under normalized unitary or orthogonal graph convolution (see Definitions and 3).
In contrast, oversmoothing commonly occurs with vanilla graph convolution and has been proven to occur in a variety of settings [RBM23, CW20, 22, Ker22]. To illustrate this, we exhibit simple setting below commonly found at initialization where the parameterized matrix is set be an orthogonal matrix and input features are random. Here, the magnitude of oversmoothing concentrates around its average and grows with the value of Tr( A²) which corresponds to the (weighted) number of triangles in the graph.
"This quantity has various equivalent names including the Dirichlet energy, local variance, and Laplacian quadratic form.

---

Proposition 7. Given simple undirected graph G on nodes with normalized adjacency matrix D and node degree bounded by D, let X I have rows drawn i..d from the uniform distribution the hypersphere in dimension d. Let (X) AX W denote convolution with orthogonal feature transformation matrix W E O(d). Then, the event below holds with probability exp(-S((vn)):
Tr( (3 Tr (T)
2 1 0
and RRgCcoom (X)) 1
+
(15)
1/1
Vanishing/Explodingg gradients A commonly observed issue in training deep neural networks, especially RNNs with evolving hidden states, is that gradients can exponentially grow vanish with depth [HS97, GBC16]. In fact, one of the original motivations for using unitary matrices in RNNs directly avoid this vanishin//exploding gradient problem [ASB16, LCMR19, JSD* HSL16). From a theoretical view, prior work has shown that carefully initialized layers have Jacobians that meet variants of the dynamical isometry property commonly studied in the mean field theory literature characterizing the growth/decay over layers of the network [SMG13, XBSD 18, PSG18J. We analyze a version of this property here and discuss in the context of our work.
Definition 8 (Dynamical isometry). Given functions f......fL. R" - R", let F; = fi. Let Jr, (œ) be the Jacobian matrix of F₁ at x E R"'. The function FL o o fi is dynamically isometric up at æ R" if there exists orthogonal matrix V O(n) such that [|TT% (x)
Vll s e where || || denotes the operator norm.
Network layers that meet the dynamical isometry property generally avoid vanishing/cxploding gradients. The particular form we analyze is stricter than those studied the mean field and Gaussian process literature which analyze the distribution of singular values over the randomness of the weights [PSG18, XBSD*18). Unitary convolution layers followed by isometric activations are examples of dynamical isometries that hold throughout training exemplified below.
Example 2. Compositions of the layer GroupSort (2)) consisting of the unitary convolution layer (Definition 1) followed by the Group Sort activation (Eq. (61)) are perfectly dynamically isometric (e 0) at all æ E Cn9.
5 Experiments
Our experimental results here show that unitary/orthogonal variants of graph convolutional net- works perform competitively various graph learning tasks. Due to space constraints, present experiments on additional datasets and architectures App. F. This includes experiments on TU- Dataset [MKB*20 and an instance of unitary group convolutional networks on the dihedral group where the goal is to learn distances between pairs of elements in the dihedral group. Training procedures and hyperparameters reported in App. G. Reported results in tables are the mean plus/minus standard deviation.
Toy model: graph distance To analyze the ability of our unitary GNN to learn long-range dependencies, we consider a toy dataset where the aim is to learn the distance between two indicated nodes large graph connected ring. This task is inspired by similar toy models ring graphs where prior work has shown that message passing architectures fail to learn long-range dependencies between distant nodes [DGGB*23], The particular dataset we analyze consists of training set of N = 1000 graphs on = 100 nodes where each graph is connected as ring (see Fig. 2a). Node features 2; E R are single number set to zero for all but two randomly chosen nodes whose features are set to one. The goal is to predict the distance between these two randomly chosen nodes. For graph of nodes, conventional message passing architectures require least n/2 sequential messages to fully learn this dataset. As shown in Fig. 2b, conventional message passing networks fail to learn this task whereas the unitary convolutional architecture succeeds. We refer the reader to App. F.1 for further details and results for additional architectures.
FFor complex valued inputs, additionally require that the functions holomorphie. For sake of simplicity, we will treat functions f C - C" as real-valued functions f R22n 2 Teehnically. this holds for almost all æ E C due to non-differentiabiiity of the activation at singular points, but this is handled in practice by choosing gradient in the sub-diffen differrenial which meets the criteria.
7

---

METHOD
PEPTIDES-FUNC TEST APT
HEPTIDES-STRUSE
COCO
PASCAL-VOC TEST
TEST MAE J
TEST
GCN 7
0,6860 = 0.0050
0.2460 0.0007
0.1338 # 0.0007 0.2078 = 0.0031
GINE 1
0.6621 = 0.0067
0.2473 0.0017
0.2125 = 0.0009 0.2718 + 0.0054
GATEDGON
0,6765 + 0.0047
0.2477 0.0009
0.2922 0.0018 0.3880 + 0.0040
GUMP
0.6843 = 0.0037
0.2564 0.0023
GPS ?
0.6534 + 0.0091
0.2509 0.0014
0.3884 + 0.0055 0.4440 1 0.0065
HOURS OTHERS
DREW
0.7150 + 0.0044
0.2536 0.0015
0.3314 # 0.0024
EXPHORMER
0,6527 = 0,0043
0.2481 0.0007
0.3430 0.0008 0.3960 = 0.0027
GRIT
0.6988 0.0082
0.2460 0.0012
GRAPH VIT
0.6942 = 0.0075
0.2449 0.0016
CRAWL
0.7074 + 0.0032
0,2506 0.0022
0.4588 + 0.0079
UnIGCN
0.7072 + 0.0035
0.2425
0.0009
0.2852
0.0016 0.3516 + 0.0070
LIE UNIGCN
0.7173 = 0.0061
0,2460 = 0.0011
0.3153 + 0.0035 0.4005 # 0.0067
REPORTED PERFORMANCE TAKEN FROM [TRRG23).
Table I: Unitary GCN with UniConv (Definition 1) and Lie UniConv (Definition 3) layers compared with other GNN architectures LRGB datasets [DRG+22]. Top performer bolded and second/third underlined. Networks are set to fit within a parameter budget of 500, 000 parameters. Complex numbers are counted as two parameters each. See App. for additional details.
(UniConv)
Figure 2: (a) Example datapoint on 25 nodes; the target is y (dis- tance between red nodes). (b) Results for the ring toy model problem with 100 nodes where the unitary GCN with UniConv Lie UniConv layers is the only message passing architecture able learn successfully. Best performance over networks with 5, 10, and 20 layers plotted. Other architectures typically perform best with 5 layers and only learn shorter distances (see App. F.
Unitary (Ue UniConvi Trinnl Performance
Spectral Convelution
Varilla GCN
12.5
MAE
10.0
5.0
2.5
50
300
150
200
250
epoch
(a) Data sample (b) Results for message passing architectures
Long Range Graph Benchmark (LRGB) We consider the Peptides, Coco, and Pascal datatsets from the Long Range Graph Benchmark (LRGB) [DRG*22]. There two tasks associated with Peptides, a peptide function classification task (Peptides-func) and regression task (Peptides-struct), Coco and Pascal are node classification tasks. Table 1 shows that the Unitary GCN outperforms standard message passing architectures and is competitive with other state the art architectures as well, many of which employ global attention mechanisms. This provides evidence that the unitary GCN is nearly as effective at learning long-range signals.
Heterophilous Graph Dataset For node classification, we consider the Heterophilous Graph Dataset proposed by [PKD*23]. The dataset contains the heterophilous graphs Roman-empire Amazon-ratings, Minesweeper, Tolokers, and Questions, which are often considered as a benchmark for evaluating the performance of GNNs on graphs where connected nodes have dissimilar labels and features. Our results in Table show that the unitary GCN outperforms the baseline message passing and graph transformer models. Given the heterophilous nature of this dataset, these findings reinforce the notion that unitary convolution enhances the ability of convolutional networks to capture long-range dependencies.
6 Discussion
In this paper we introduced unitary graph convolutions for enhancing stability in graph neural networks. We provided theoretical and empirical evidence for the effectiveness of our approach. We further introduce an extension to general groups (generalized unitary convolutions), which can be leveraged in group-convolutionl architectures to enhance stability.
8

---

METHOD
ROMAN-E.
AMAZON-R. AP
MINESWEEPER ROC AUCT
TOLOKERS ROC AUCT
QUESTIONS ROC AUC 1
TEST APT
GCN f
73.69 = 0.74 48.70 = 0.63
89.75 = 0.52
83.64 = 0.67 76.09 = 1.27
SAGE
85.74 = 0.67 53.63 + 0.39
93.51 0.57
82.43 # 0.44 76.44 = 0.62
GAT
80.87 + 0.30 49.09 + 0.63
92.01 = 0.68
83.70 0.47 77.43 = 1.20
GT
86.51 = 0.73 51.17 = 0.66
91.85 = 0.76
83.23 # 0.64 77.95 = 0.68
OURS
UNITARY GCN
87.21 +: 0.76 55.34 + 0.74
94.27 + 0.58
84.83 1 0.68 79.21 = 0.79
LIE UNITARY GCN 85.50 # 0.22 52.35 + 0.26
96.11 0.10
85.18 = 0.43 80.01 = 0.43
REPORTED PERFORMANCE TAKEN
[PKD*23].
Table 2: Comparison of Unitary GCN with UniConv (Definition 1) and Lie UniConv (Definition 3) layers with other GNN architectures on the Heterophilous Graph Datasets.
Limitations Perhaps the biggest challenge in working with unitary convolutions is the overhead associated with maintaining unitarity or orthogonality via approximations of the exponential map or diagonalizaaions in Fourier spectral bases. For implementing unitary maps, working with complex numbers also requires different initialization and activation functions. We refer the reader to App. C.2 and E for methods to alleviate these challenges in practice. Separately, there may be target functions or problem instances where unitarity or orthogonality may not be appropriate. For example, one can envision node classification tasks where the target function is neither (approximately) invertible isometric. In such instances, non-unitary layers will be required to learn the task. More generally, deciding when smaller input graphs, simple and more efficient interventions such as adding residual connections or including batch norm will likely suffice for addressing signal propagation problems.
unitary layers is problem- dependent. In some cases, such applications with
Future Directions In the graph domain, extensions of graph convolution to more advanced methods such as those that better incorporate edge features could widen the range of applications. Exploring hybrid models that combine unitary and non non-unitary layers (e.g. global attention mechanisms) could potentially lead to more robust and versatile graph neural networks. Future work can also improve the efficiency of the parameterizations and implementations of the exponential map (see App. C.2). In a similar vein, it is likely that approximately unitary/orthogonal layers suffice in many settings to achieve the performance gains see in work. Methods that approximately enforce regularize layers towards unitarity may be of interest in these instances due to their potential for improved efficiency. In this study, we mainly focused on applications to graph classification and regression lasks; however, the proposed methodology is much more general and could open up wider range of applications to domains with more general symmetries or different data domains. For example, unitary matrices offer provable guarantees to adversarial attacks (see Corollary 9) and testing this robustness in practice on geometric data has yet to conducted.
Acknowledgements
We thank Derek Lim and Andrew Cheng for insightful discussions and Stephen Becker for finding an error in the definition of matrix Lie groups BK and MW were supported by the Harvard Data Science Initiative Competitive Research Fund and NSF award 21 2110085.
References
[ABKL23] Eric R Anschuetz, Andreas Bauer, Bobak T Kiani, and Seth Lloyd. Efficient classical algorithms for simulating symmetric quantum systems. Quantum, 7: 189, 2023. 18
[AEL+24] Yassine Abbahaddou, Sofiane Ennadir, Johannes F. Lutzeyer, Michalis Vazirgiannis, and Henrik Boström. Bounding the expected robustness of graph neural networks subject node feature attacks. In The Twelfth International Conference on Learning
Representations, 2024. 2. 18, 19
[AK22] Eric Anschuetz and Bobak T Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1):7760, 2022. 18

---

[ALG19] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approxima- tion. In International Conference on Machine Learning, pages 291-301. PMLR, 2019.
27, 31
[AMH09] Awad H Al-Mohy and Nicholas Higham. Computing the fréchet derivative of the matrix exponential, with an application to condition number estimation. SIAM Journal Matrix Analysis and Applications, (004)):639-11) 2009. 25
[AMHIO] Awad Al-Mohy and Nicholas Higham. A new scaling and squaring algorithm for the matrix exponential. SIAM Journal on Matrix Analysis and Applications, 31(3))970- 989, 2010. 25
[ASB16] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks, In International Conference on Machine Learning, pages 1 1120- 1128, 2016. 2, 5, 1.
[BDGC*22] Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pietro Lio, and Michael Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. Advances in Neural Information Processing Systems, 35:1 1527-1811,, 2022. 6
[BL17] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint
arXiv:1711.05533, 2017. 18, 30
[BQL21] Joshua Bassey, Lijun Qian, and Xianfang Li. A survey of complex-valued neural networks. arXiv preprint arXiv:2101. 12249, 2021. 27
[BSC*24] Ilyes Batatia, Lars Leon Schaaf, Gabor Csanyi, Christoph Ortner, and Felix Andreas Faber. Equivariant matrix function neural networks. In The Twelfth International Conference on Learning Representations, 2024. 18
[BSF94] Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult, IEEE transactions on neural networks, 572):157-166 1994. 2
[BVB21] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 18673-18684. Curran Associates, Inc., 2021.
[CGKW18] Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. arXiv preprint arXiv:1801.10133 2018. 3, 18
[Chu97] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[CNDP*21] Grecia Castelazo, Quynh Nguyen, Giacomo De Palma, Dirk Englund, Seth Lloyd, and Bobak Kiani. Quantum algorithms for group convolution, cross-correlation, and equivariant transformations. arXiv preprint 21X
2021. 18
[CST+21] Andrew M Childs, Yuan Su, Minh C Tran. Nathan Wiebe, and Shuchen Zhu. Theory of trotter error with commutator scaling. Physical Review X, 11()):01 1020, 2021. 25
[CW16] Taco Cohen and Max Welling. Group equivariant convolutional networks. In Interna- tional conference on machine learning, pages 2990-2999. PMLR, 2016. 3, 18
[CW20] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020. 6, 28
[DGGB+23] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio, and Michael M Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In International Conference on Machine Learning, pages 7865-7885. PMLR, 2023. 7
10

---

[DRG*22] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty- sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. 8, 33
[ESM23] Carlos Esteves, Jean-Jacques Slotine, and Ameesh Makadia. Scaling spherical cnns. arXiv preprini arXiv:2306.05422 2023.
[FH13] William Fulton and Joe Harris. Representation theory: first course, volume 129. Springer Science & Business Media, 2013. 2, 20, 26
[FL.1]] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. 30, 33
[FSIW20] Marc Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing convolutional neural networks for equivariance lie groups arbitrary continuous data. International Conference on Machine Learning, pages 3165-3176. PMLR, 2020. 18
[FW24] Lukas Fesser and Melanie Weber. Mitigating over smoothing and squr-shug using augmentations of Forman- Ricci curvature. In Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 19:1-19:28. PMIR, 27-30 Nov 2024. 18
[GBC16] lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016. 7
[GBH18] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Advances in neural information processing systems, 31, 2018. 18
(GDBDG23) Benjamin Gutteridge, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Gio- vanni. DRew: Dynamically rewired message passing with delay. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learn- ing, volume 202 of Proceedings of Machine Learning Research, pages 12252-12267. PMLR, 23-29 Jul 2023. 18, 30
[GRK*21] Gligorijević, Renfrew, Kosciolek, Leman Koehler, Berenberg, Vatanen, Chandler, Taylor, Fisk, Vlamakis, et al. Structure- protein function prediction using graph convolutional networks. Nature communications, 12(1):3168, 2021.
[GXI5] Qinghua Guo and Jiangtao Xi. Approximate message passing with unitary transforma- tion. arXiv preprint prriiv15000
1eeei15044444 504.04499, 2015. 18
[GZH*22] Kai Guo, Kaixiong Zhou, Xia Hu, Yu Li, Yi Chang, and Xin Wang. Orthogonal graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3996-4004, 2022. 2, 18, 19
[Hal15] Brian Hall. Lie groups, Lie algebras, and representations: an elementary introduction, volume 222. Springer, 2015. 2, 23, 24, 25
[HH]*33] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann Lecun, and Xavier Bresson. A generalization of mii/ to graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, vol- ume 202 of Proceedings of Machine Learning Research, pages 12724-12745. PMLR, 23-29 Jul 2023. 18, 30
[Hig09] Nicholas J Higham. The scaling and squaring method for the matrix exponential revisited. SIAM review, 51(4)7747-764 2009. 25
[Hoc91] Sepp Hochreiter.
Untersuchungen zu dynamischen neuronalen netzen. Diploma, Tech-
nische Universität München, 91(1), 1991. 2

---

[HS97] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compu- tation, 988):1735-178,, 1997. 7,
[HSL16] Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long-memory tasks. In International Conference on Machine Learning, pages 2034- 2042. PMLR, 2016. 2, 7.
[HSTW20] Emiel Hoogeboom, Victor Garcia Satorras. Jakub M Tomczak, and Max Welling. The convolution exponential and generalized sylvester flows. arXiv preprint
2020. 2
[HWY18] Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning, pages 1969-1978. PMLR, 2018. 2, 17, 25, 27
[HYL17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017. 18
[JD15] Bo Jiang and Yu- Yu-Hong Dai. A framework of constraint preserving update schemes for optimization stiefel manifold. Mathematical Programming. 153(2):535-5777 2015.
[JSD+17] Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačić. Tunable efficient unitary neural networks (eunn) and their application to rnns. In Proceedings of the 34th International Conference on Machine Soarning-Volumee 70, pages 1733-1741. JMLR. org, 2017. 2, 17
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rxiv:1412.69000 2014.
[KLL222] Bobak Kiani, Randall Balestriero, Yann LeCun, and Seth Lloyd. projunn: efficient method for training deep networks with unitary matrices. Advances in Neural Infor- mation Processing Systems, 35: 44411443-4 2022. 5, 17, 18, 20, 26,
[Ke175] Joseph Keller. Closest umitary, orthogonal and hermitian operators to a given operator. Mathematics Magazine, 48(4):192-197, 1975. 19
[Kem03] Julia Kempe. Quantum random walks: an introductory overview. Contemporary Physics, 44(4):307-327, 2003. 18
[Ker22] Nicolas Keriven. Not little, much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268-2281, 2022.
[KJ08] Alexander Kirillov Jr. An introduction Lie groups and Lie algebras. Number 113.
Cambridge University Press, 2008. 24
[KLL+24] Bobak T Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, and Melanie Weber. On the hardness of learning under symmetries. In International Conference on Learning Representations, 2024.
[KT18] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convo- lution in neural networks to the action of compact groups. In International conference on machine learning, pages 2747-2755. PMLR, 2018. 3, 18, 20, 26
[KW16] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolu- tional networks. arXiv preprint 1rXiv:1609.02900 2016. 18, 28, 30
[LCMR19] Mario Lezcano-Casade and David Martmez-Rubio. Cheap orthogonal constraints in neural networks: simple parametrization of the orthogonal and unitary group. In International Conference Machine Learning, pages 3794-3803, PMLR, 2019. 2, 7, 17, 20, 24, 25, 27
[LFT20) Jun Li, Li Fuxin, and Sinisa Todorovic. Efficient riemannian optimization on the stiefel manifold via the cayley transform. arXiv preprint arXiv:2002.01 /1 2020. 20, 27
12

---

[LGJ Man Luo, Qinghua Guo, Ming Jin, Yonina C Eldar, Defeng Huang, and Xiangming Meng. Unitary approximate message passing for sparse bayesian learning. IEEE transactions on signal processing, 69:6023-6039, 2021. 18
[LHA*19] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jörn- Henrik Jacobsen. Preventing gradient attenuation in lipschitz.constrained networks. Advances neural information processing systems, 32: 13300-15554,, 2019. 2, 17, 20
constrained convolutional
[LJH15] Quoe V Le,, Navdeep Jaitly, and Geoffrey Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv: 150440094, 2015. 2
[1] Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, 1354):135 2019. 18
1996. 25 [MBB24] Nimrah Mustafa, Aleksandar Bojchevski. and Rebekka Burkholz. Are gats out of balance? Advances in Neural Information Processing Systems, 36, 2024. 18
[Llo96] Seth Lloyd. Universal quantum simulators. Science, 273
[MGL*23] Grégoire Mialon, Quentin Garrido, Hannah Lawrence, Danyal Rehman, Yann LeCun, and Bobak Kiani. Self-supervised learning with lie symmetries for partial differential equations. Advances Neural Information Processing Systems, 1122973-29000 2023. 25
[MHRB17] Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In International Conference on Machine Learning, pages 2401-2409 PMLR, 2017.
17
[MKB*20] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. 7, 28, 33
[MLL*23) Liheng Ma, Chen Lin, Derek Lim, Adriana Romero- Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pages 23321- 23337. PMLR, 2023. 18, 30
[MMM21] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Pro- ceedings of Machine Learning Research, pages 3351-3418. PMLR, 15-19 Aug 2021.
[MM Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1706. 06088, 2017. 20
[MP17] Junjie Ma and Li Ping. Orthogonal amp. IEEE Access, 5:2020-2033 2017. 18
[MPBK24] Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36, 2024. 18, 19
[MQ02] Robert McI and Reinout W Quispel. Splitting methods. Acta Numerica, 11:341-434, 2002. 25
[NA05] Yasunori Nishimori and Shotaro Akaho. Learning algorithms utilizing quasi-geodesic flows on the stiefel manifold. Neurocomputing, 67:106-135, 2005. 27
13

---

[3HN*23] Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricei curvature. In International Conference Machine Learning, pages 25956-25979. PMLR, 2023. 28, 32
[NSB*22] Quynh T Nguyen, Louis Schatzki, Paolo Braccia, Michael Ragone, Patrick Coles, Frederic Sauvage, Martin Larocca, and Marco Cerezo. Theory for equivariant quantum neural networks. arXiv preprint arXiv:2210.08566 2022. 18
[Pet06] Peter Petersen. Riemannian geometry, volume 171. Springer, 2006. 24
[7G Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. 30, 33
[PKD*23] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are really making progress? arXiv preprint arXiv:2302. 16440, 2023. 8, 32, 33
[PMB13] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310-1318. Pmir, 2013. 2
[PSG18] Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence spectral universality in deep networks. In International Conference Artificial Intelligence and Statistics, pages 1924-1932 PMLR, 2018.
[PTPV17] Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. Column networks for collective classification. In Proceedings of the AAAI conference on artificial intelli-
gence, volume 31, 2017. 18
[QBY24] Haiquan Qiu, Yatao Bian, and Quanming Yao. Graph unitary message passing. arXiv preprint arXiv:2403.11199 2024. 2, 18, 19, 20
[RBM23] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10995 2023. 1, 6, 18, 28
[RCR*22] T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In International Conference on Machine Learning, pages 18888-18900 18909. PMLR, 2022. 28
[RGD*22] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515, 2022. 18, 28, 30, 33
[S* Lean-Pierre Serre et al. Linear representations of finite groups, volume 42. Springer, 1977. 25, 26
[SBV20] Shlomi, Battaglia, and Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
[SCY+23) Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas Bäck, and Vedran Dunjko. Equivariant quantum circuits for learning on weighted graphs. npj Quantum Informa- tion, 2023.
2023.
18
[SF21] Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. arXiv preprint arXiv:2 1417, 2021. 2, 5, 17, 18
[SGL18]] Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. arXiv preprint 1805. 2018. 2, 6, 17, 20
14

---

[SHF*20] Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for sup-rsupee classifi- cation. arXiv preprint arXiv:2009.03509 2020. 18
[SLN*24] Louis Schatzki, Martin Larocca, Quynh T Nguyen, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for permutation-equivriiai quantum neural networks. npj Quantum Information, 10(1):12, 2024. 18
[SMG13] Andrew M Saxe, James McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 2013. 2, 7,
[Str68] Gilbert Strang. On the construction and comparison of difference schemes. SIAM journal on numerical analysis, 5(3):506-517, 1968. 25
[SVV*23] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613-31632. PMLR, 2023. 18,30
[TK21] Asher Trockman and J Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. arXiv preprint urX1v:21044.01177 2021, 2, 6, 17, 18, 20, 25, 26, 27, 31
[Tro59] Hale Trotter. On the product of semi-groups of operators. Proceedings of the American Mathematical Society, 10(4):545-5511 1959. 25
[TRRG23] Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe. Where did the gap go? reassessing the long-range graph benchmark. arXiv preprint 2xXiv2309.00366, 2023. 18, 30, 31, 36
[TRWG21] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing, arXiv preprint arXiv:2102.08786, 2021. 31
[TRWG23] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. Transactions on Machine Learning Research, 2023. 18, 30
[VCC*17] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017. 18, 28
[6P Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. arXiv preprint arXiv: /6/:66// 1.00035, 2016. 15
[WSZ+22] Wu, Sun, Zhang, Xie, and Cui. Graph neural networks in recommender systems: a survey, ACM Computing Surveys, 55(5):1-37, 2022.
[WWY20] Rui Wang, Robin Walters, and Rose Yu. Incorporating symmetry into deep dynamics models for improved generalization. arXiv preprint arXiv:2002.0306. 2020. I
[WZR*20] Melanie Weber, Manzil Zaheer, Ankit Singh Rawat, Aditya K Menon, and Sanjiv Ku- mar. Robust large- learming in hyperbolic space. Advances in Neural Information Processing Systems, 33: 33:17863-17877 2020. 18
[XBSD*18] 18] Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dicke Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and mean field theory of cnns: How to train 10,000- layer vanilla convolutional neural networks. In International Conference on Machine Learning, pages 3393-5402. PMLR, 2018. 17, 18
[XHIJ18] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 18/0.0082,, 2018. 8. 18, 30
15

---

[8L Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR, 2018. 18
[YYL20] Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems, 33:17009- 17001,, 2020. 30, 33
[ZAL18] Zitnik, Agrawal, and Leskovec. Modeling polypharmacy side effects with graph volutional networks. Bioinformatics, 34(13):145-i4666 2018.
[ZK20] Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International conference on learning representations, 2020. 28
16

---

Table of Contents
A Extended related works
17
A.I
Further related literature
17
A.2 Comparison with other proposals for unitary message passing
18
Deferred proofs
20
C Background on representation theory, Lie groups, exponential map, and related ap- proximations
23
C.1 Matrix Lie groups
23
C.2 Exponential map
24
D Fourier implementation of group convolution
25
Architectural considerations
27
F
Additional experiments
27
F.1
Additional results on toy model of graph distance
27
F2
TU Datasets
28
F3
Dihedral group distance
28
F.4
Orthogonal Convolution
29
G Experimental details
30
G.1 Licenses
33
A Extended related works
A.1 Further related literature
Unitary RNNs Unitary neural networks were initially developed tackle the challenge of vanish- ing and exploding gradients encountered in recurrent neural networks (RNNs) processing lengthy sequences of data. Aiming for more efficient information learning compared unitary architectures like the long-short term memory unit (LSTM) [HS97]. early approaches ensured unitarity through sequence of parameterized unitary transformations [ASB 16, MHRB17, JSD* 17]. Other methods like the unitary RNN (uRNN) [WPH*16] the Cayley parameterization (scoRNN) [HWY18], and exponential RNN (expRNN) [LCMR19] parameterized the entire unitary space, maintaining unitarity via Cayley transformations parameterizing the Lie algebra of the unitary group and performing the exponential map. To eliminate the reliance on the matrix inversion or ma- trix exponential in these prior al algorithms which are computationally expensive in higher dimensions, [KBLL22] showed how to fully parameterize unitary operations more efficiently when applying gradient updates in low rank subspace.
established non-
Group convolutional neural networks For convolutional neural networks acting on data in lattices or grids (e.g. images), various algorithms have proposed orthogonal or unitary versions of linear convolutions over the cyclic group [LHA* 1A, SF21, TK21, KBLL22). [XBSD* 18] study the task of initializing convolution layers to be an isometry and thereby are able to train very deep CNNs with thousands of layers without the need for residual connections or batch norm. [SGL18] project convolutions onto an operator-nora ball to ensure the norm of the convolution within given range. [LHA+19] introduced a block convolutional orthogonal parameterization (BCOP) parameterizing
17

---

subspace of orthogonal convolution operations. [SF21] implement orthogonal convolutions by parameterizing the Lie algebra of the orthogonal group and approximating the exponential map. Their approach is special case of the instances we discuss in our work. [TK21]] and [KBII122] perform convolution in the Fourier domain where convolution is block diagonalized and unitarity can be enforced across each of these blocks. Generally, unitary convolutional architectures do not perform as well as their vanilla counterparts in terms of accuracy on large image datasets such as CIFAR or ImageNet [TK21, SF21, LJW* 19]. Nonetheless, enforcing unitarity here can provide other benefits such as improved robustness to adversarial attacks or added stability with many layers [TK21, KBLL22, SF21, XBSD* 18]. Various architectures for more general geometric domains have been proposed [KT18, CGKW18, CW16, GBH18, WZR* 20, FSIW20J, including generalized group convolutional neural networks considered here. To the best of our knowledge, no explicit extensions of unitary convolutions and related stability aspects have been considered in these settings.
GNNs and oversmoothing Our GNN architectures develop on seminal work proposing variants of graph convolution architectures [KW16, BL17J. Graph convolution is one of various types of trainable layers that act on graphs and are equivariant to the permutation group; among those we compare to in our experiments are [KW16, 16, BL17, XHLJ18, TRRG23, HHL*23, GDBDG23, RGD*22, MLL*23 SVV*23, TRWG23, HYL17, VCC* 17, 2HF* Recently, some work has proposed variants of unitary/orthogonal graph convolution which we discuss in more detail in the next section (App. A.2). Compared to our method, these either only enforce unitarity in part of the transformation or are expensive to compute. For example, [GZH* AEI.*24] propose variants of graph convolution which enforce orthogonality in the feature transformation but not in the message passing update itself. [QBY24] propose a graph unitary message passing algorithm that is in general close to an isometry, but scales poorly with the graph size (see App. A.2). Some recent work has also proposed performing message passing in the complex domain. [MPBK24] show continuous time message passing update that can be made unitary as discussed in App. A.2. [BSC 24] propose an equivariant matrix function graph neural network layer that performs a global update by taking a trainable pole expansion of a matrix function of the adjacency matrix. This layer is effective at incorporating global information, but requires matrix inversion operations that scale poorly with dimension. [MBB24] give a so-called "balanced orthogonal" initialization for message passing networks using graph attention (GAT). The weight matrix parameters in the GAT layer are initialized as some orthogonal matrix which improves stability for GNNs of the given form with many layers. Nonetheless, the layer itself does not implement an isometry due the presence of the attention mechanism in the GAT layer.
Various architectures have been proposed to avoid oversmoothing and incorporate nonlocal graph information more generally. This includes approaches that perform small perturbations of the input graph (rewiring [RBM23, FW24]), as well as architectural interventions, such skip connec- tions [PTPV17, HYL17, XLT* which can improve stability in homophilous settings.
Other settings In the context of Bayesian statistics and graphical algorithms, there are variants of the approximate message passing algorithm which leverage properties of unitarity or orthogonality in the message passing [LGJ+21, GXIS, MP17J. Unitary equivariant operators are also used in the context of quantum computation and quantum variational algorithms [NSB*22, 22, CNDP*21, SCY*23, SLN* These papers generally study a very different context to that of classical machine learning algorithms. Furthermore, it is unclear whether practical instances of these algorithms offer improvements in comparison to classical machine learning algorithms [AK22, ABKL233.. Separate from quantum machine learning, the unitary graph convolution used here is partly inspired by quantum walks which feature similar unitarity properties [Kem03].
A.2 Comparison with other proposals for unitary message passing
We compare here previous GNN architectures which have proposed variants of complex-valued or isometric message passing. To facilitate this comparison, first let us recall some standard notation and implementations. Given an (possibly normalized) adjacency matrix A E Ra*xn acting on n nodes and input features X E nadd of dimension d, a basic linear message passing layer f R - nadd' takes the form
fw = o (AXW).
(16)
18

---

where R - R is a pointwise nonlinearity and W E R is a parameterized weight matrix transforming the node features. There are variations of the above which normalize the adjacency matrix or add residual connections, but for sake of comparison, we will study the simplified form above. In contrast, the unitary message passing layer we propose takes the form
uni (X) (r(exp(iAA)XW)
(17)
where X and W are now complex-valued and / R as parameter controlling the strength of message passing.
[GZH"22] propose version of an orthogonal GNN which enforces either exactly or approximately that the matrix W in Eq. (16) is orthogonal, i.c.
fw = (AXXW, where W W
(18)
They also discuss regularization of node transformations W to bias towards orthogonality, [AEL-*4] also detail a version of a GNN which enforces orthogonality in the matrix W. We note that our study focuses on orthogonality in the node evolution during message passing. We discuss in the main text how to combine this with orthogonality in the feature transformation W.
Our work also has overlap with the recently proposed fractional Graph Laplacian approach of [MPBK24]. There, they analyze a continuous-time message passing scheme called the fractional Schrödinger equation taking the form
0X Ō1 = -W.
(19)
where a > O is a chosen parameter and L is the normalized graph Laplacian. Unitarity can be strictly enforced in this continuous time format although [MPBK24] do not take this approach. In fact, solving this continuous-time differential equation for some time r, we obtain (1) = e @ W) (0) where vec (r) is the vectorized version of X at time Constraining L @ W to be Hermitian obtains a unitary transformation. Beyond enforcing unitarity, our method works over discrete time, and we find it more efficient parameterize the weight matrix W outside of the exponential map.
A recent preprint proposes a unitary message passing algorithm called gruph unitary message passing (GUMP) which sends messages through a larger ring graph constructed from the edges of the original graph [QBY24]. Given graph G with nodes and edges V and E respectively, the steps of this approach loosely are as follows:
1. Construct new directed graph (digraph) G' with the same nodes and include directed edges (i,j) and (j.i) for any undirected edge (f, j) in original graph.
2. Convert G' to its line graph L(G"): here, each node is an edge in G' and two nodes in L(G') share an edge there a path through the original edges in G' (e.g. nodes corresponding to edges (i. j) and (j, k)).
3. Construct new node representations in the line graph where for each edge (i. we append the node representations [ax, Ff.
4. Given the adjacency matrix A₁ for L(G'), find permutation matrices Pl, Pa which form a block diagonal matrix PT A.P.
5. Project each block its closest unitary in Frobenius norm according the closed form projection operation [Ke175]:
o = arg min U (())))))
|| = AL
(20)
In the above, U() denotes the set of unitary matrices in C"X".
6. Invert the permutations obtaining P.A.P.
7. Perform GNN convolution using the adjacency matrix constructed previously for layers.
8. Attach node representations of I.(G") to corresponding nodes of and append these to the initial representations to output the final representations.
19

---

As evident above, the approach here is rather meticulous and many details of the approach are left out. We refer the reader to the preprint [QBY24] for those details. Key to this procedure is that unitarity is roughly enforced by constructing the matrix Ar, which is itself unitary in the vector space of the line graph L(G"). Nonetheless, the map from node representations the original graph G to new node representations on will only be approximately unitary as the additional steps here will not guarantee properties of isometry and invertibility in general.
For sake of comparison, we should note that the complexity of this approach (in number of nodes [V] and edges [FI) is at least least [?]) and in practice ((EE)) where the most expensive step is the unitary projection which requires a matrix inverse square root. More efficient parameterizations of this pro- cedure or approximations to the projection exist as noted in prior work [KBLL.22, LCMR (LMM1,, LFT20J, but this would only improve runtimes to w( w(E) at best with additional overhead. Furthermore, the GUMP algorithm expands the memory needed to store hidden states from O(IVI) to O(E)). In comparison, our approach can be made strictly unitary and is more efficient scaling only a constant factor times standard graph convolution runtime to ((T]VI| where T is the truncation in the matrix exponential approximation (see App. C.2) with no change to the way hidden states are stored. Our approach is also noticeably simpler it only reparameterizes the message passing step be an exponential map over standard message passing procedures.
B Deferred proofs
First, review the properties shown in Fact 1 that unitary convolution meets the properties of invertibility, isometry, and equivariance. This fact follows virtually immediately from the definition of unitarity and equivariance.
Proof of Fact 1. The proofs of isometry and invertibility follow directly from the definition of unitarity. What remains to be shown is the equivariance property. For unitary convolution built using Algorithm 1, equivariance can be checked by noting that the exponential map is a composition of equivariant linear operators. For unitary convolution in the Fourier domain (Algorithm 3), equivariance follows from convolution theorems where linear operators appropriately applied in the block diagonal Fourier basis are equivariant [FH13, KT18).
As an application, unitary transformations are often used to provide provable robustness guarantees adversarial perturbations of inputs (TK21, LHA+ + 19, MMS* 17, SGL18].
Corollary 9 (Certified robustness to adversarial perturbations [TK21J). A simple consequence of the isometry property of the unitary convolution is that II f -fuonn y)) = || yll the Lipschitz constant of this function is 1. Assume neural network classifier f I2"" + Rn' is composed of unitary transformations and 1-Lipschitz bounded nonlinearities followed by an L-Lipschitz transformation and for given input x, it has margin Mf(x) defined as
My(x)
max rc(m]
(. max [f()))
(21)
te(m),ior
Then, f is certifiably robust (i.e. classification is unchanged) to perturbations x + A of magnitude || < My(x))
In the main text, we noted in Proposition that the above facts in some way cannot be obtained using the standard graph convolution. We restate this here and prove it.
Proposition 4. Let foom Ruudd - Bundd be a graph convolution layer of the form
Jamne X, A) = XW, AXW,
(12)
where Wo. W1 E Raxd are parameterized matrices. The linear map f(.A) : Raxd - Raxd is orthogonal for all adjacency matrices A of undirected graphs only if W, 0 and Wo O(d) is orthogonal. Furthermore, denoting JA E gndxnd as the Jacobian matrix of the map feome A).
any choice of Wo. Wi, there always exists a normalized adjacency matrix A such that
1| 11
|
(13)
2d
where [| is the operator norm of matrix M.
20

---

Proof. Note that for (a potentially normalized) adjacency matrix A, the Jacobian JA in the basis of vec( (e) equal
JA W A W.T. Thus, for the map to be orthogonal, it must hold that
(22)
I= JAJAJA = & Wi Wo A @ W Wi + A8 W, Wo+ A 2 W, W1.
(23)
First, let Ao be the empty graph on two nodes so O, then
JA. I @ W Wo.
(24)
which means Wo must be orthogonal if JA, is orthogonal. A simple instance with the desired structure can be constructed as follows: Consider the graph on two nodes, which is connected with adjacency matrix Aj. Here, we have
JA J = I W, Wo + W, Wi) A (W, Wo + W. Wi).
(25)
Note that if Wo is orthogonal, then W1 0 if JA J = I. This proves the first part of the proposition.
For the second part, we take traces and note that
Tr JA wlll
(26)
JA. JA 2 wlll 2l] 21
In contrast, Tr(I)= 2d. Therefore, for any choice of the values of [Woll W[ must hold that either
ITr (J (JA Jh.) 22d |
(27)
Tr [JA -2d 2 [
(28)
W.L.ogg. assume the first event holds. Denoting the singular values of matrix JA, JA I as $1,-.., S2d, we have
W s |r (JA, -)] s s ..... s2d 2d max 8;-
(29)
Rearranging, we obtain the final result.
One consequence of the above fact is that fully parameterized unitary graph convolution requires higher order powers of A implemented. This is essentially one reason why the exponential map (or some approximation thereof) is needed.
We now show that the Rayleigh quotient defined in Definition is invariant under unitary transfor- mations. As before, this will follow virtually directly from the unitarity properties. We restate the proposition below.
Proposition 6 (Invariance of Rayleigh quotient). Given an undirected graph normalized adjacency matrix À D-11/AA the Rayleigh quotient Rg( Rg) fucom (X)) is invariant under normalized unitary or orthogonal graph convolution (see Definitions and 3).
nodes with
Proof. First, consider separable unitary convolution (Definition 1). The Rayleigh quotient takes the form
Tr ((sp(iā)xX)) (I ()
Rg (fucon (X)
(30)
exp((i)
The Frobenius is invariant under unitary transformations so the denominator || exep(iA) || For the numerator have by the cyclic property of trace
Tr (T((oxp(A)xXU)' (I = = =Tr
-
exp(-iA)(1 - Ā) exp(iA)x)
(31)
21

---

The matrices exp(-iA), (I exp(AA) all share the same eigenbasis so they commute and thus
Tr (xxtexp-iAA)( A) exp(iA)x) Tr (x - -
(32)
Thus, we have
Tr x x (I -)) = ( (X).
R RUCCoc (X))
(33)
Similarly for Lie unitary/orthogonal convolution (Definition 3), the isometry property guarantees || (X)]l. Furthermore, when viewed as linear map in the basis of vee e Cnd (i.e. entries X viewed as a vector), fucony can be written as a linear map of the form
vec(ffucom (X)) exp( A @ W vec(
(34)
where W is the feature transformation matrix in Definition 3. Finally, note that exp( A @ WT) commutes with so
Tr (X) -A) ((a))m (X))
= v exp( A W " (I (1- exp(A @ W veo(X)
(35)
= vec(X))
|II A) @ I vec(X))
Multiplying the above by ; recovers (x
In contrast, we gave an example (Proposition 7) where the Rayleigh quotient decays with high probability for vanilla convolution, which restate below.
Proposition 7. Given simple undirected graph G nodes with normalized adjacency matrix D AD-1/2 and node degree bounded by D, let X RRaxd have rows drawn i.i.d. from the uniform distribution on the hypersphere in dimension d. Let feom (X) AX W denote convolution with orthogonal feature transformation matrix W E O(d). Then, the event below holds with probability (Sp(-
Tr(A+)
and 1/
21
(15)
Tr(A2)
11/4
Proof. Note that
Tr x (1-A))
-B Tr (I -xxx
=B
(36)
||
By symmetry properties of the uniform distribution Uni on the hypersphere, X[XX = I. Thus,
B [Rg(X)) 1.
(37)
Furthermore, treating Rg (X) as function of its node features EI...., In where 2; = XT we have by the Azuma- Azuma-Hoeffdinn Hoeffding inequality that
[ (X) e] exp((S2(ne")).
(38)
The above can be shown by noting that the operator norm of À is bounded by two and changing the values any x; changes (x( by most 4/n. Therefore, setting en -1/4 we get that with probability 1 vm),
(x = 0
(39)
22

---

For Rg( (X)), we have
Tr WTX A(I A)AXW)
[ (X)) =B
|AX
Tr X A(I A)āX)
E
(40)
||
X x
E
||
Again, using the Azuma-Hooffding argument as before, the numerator above concentrates around its expectation
-
2 en s exp(-
(41)
A similar statement holds for the denominator || properties the distribution X and linearity of expectation:
Furthermore, we have by symmetry
ETr x X Tr( )²)
B A (²)).
(42)
Combining the above facts and applying the union bound, we have that with probability =xp((2(=2Vm)..
Tr TT A'X
Tr(A-) en
Tr(A')
+ +n 11/4).
(43)
|XX||
Tr(A?) + 3n3/4
Tr(A2)
In the last equality, use the fact that has bounded degree and thus Tr( Tr( O
C Background on representation theory, Lie groups, exponential map, and related approximations
C.1 Matrix Lie groups
We give a brief overview of matrix Lie groups and Lie algebras here and recommend [Hal15] for detailed exposition. Matrix Lie groups are subsets of invertible matrices that form differentiable manifold formally defined below.
Definition (Matrix Lie groups [Hal15]). matrix Lie group any subgroup of GL(n, C) with the property that any convergent sequence of matrices Mm e Cuxn in the subgroup converge to matrix M that either an element the subgroup or not invertible (i.e., not GL(n, C)).
The orthogonal and unitary groups whose definitions copied below meet these criteria.
((n) (M R
MM |
M M I]
(44)
U(n) = M CM M M
(45)
A crucial operation in matrix Lie groups is the exponential map. Given matrix M C which is an endomorphism End(C") on the vector space C", the exponential map exp End(C") - End(C") returns another matrix (endomorphism) and is defined
Σ MP. p=ù
exp(M)
(46)
The exponential map, as we will show below, maps from the Lie algebra to the Lie group. also has an interpretation over Riemannian manifolds which we do not discuss here. We refer the reader to
23

---

textbook [Pet06] or prior work in machine learning [LCMR19] for further details of that connection. For compact groups, the exponential map is smooth map whose image is the connected component to the identity of the Lie group [KJ08, Hal15]. The Lie algebra is the tangent space of a Lie group the identity element. To see this, note that
d dt exp(1X)= = X eexp(rX)= =xx(((x)=xxp(()) exp(1X)X,
(47)
and
d exp(1X) 1m00
= =
(48)
di
Note that exp(O)= I. The above gives the Lie algebra given group.
Definition (I.ie algebra [Hal15]). Given matrix Lie group G, the Lie algebra g G is the set of matrices X such that ex G for all e R.
As example, consider the unitary group where given matrix U Un) and X E u(n). Here, we have
d exp(-1X) 1=0 di
d
exp(:x))
-X -X
(49)
dt
1-0
C.2 Exponential map
First, let recall the definition of the exponential map. Given linear operator L : V V which is an endomorphism End( on a vector space V, the exponential map exp End(V) - End(V) defined as
exp(L) Σ 1 p!
= = L))) 1 L(X)
(50)
Applying the exponential map of linear operator to given vector in vector space of dimension to computer precision can scale in practice as O similarly to performing an eigendecomposition. In fact, for matrices M C which have eigendecomposition M U DU (for skew- diee-Hermitian matrices M E u(n), the spectral theorem guarantees the existence of an eigendecomposition, exp(M) U exp( D)U where exp( D) be easily implemented by performing the exponential elementwise on the diagonal entries D. However, practice, we can exploit approximations which avoid expensive operations such eigendecompositions.
Taylor approximation Often the simplest and most efficient approximation a k-th order trunca- tion the Taylor series
exp[conv] (X)
(P) (X),
cony (P)
(51)
p!
where conv"; V - one can bound the error in this approximation as
V indicates the composition of the operator conv p times. By Taylor's theorem,
50 |ccov||| ( 1)!
exp[conv]
cony (X) p'
where [|conv]| denotes the operator norm of conv. Therefore, error decreases exponentially with k. In practice, we find setting = 12 is sufficiently accurate for the GNNs we train our experiments. Of course, k can be increased in settings with larger graphs more training time where instabilities are likely to arise. We also by default perform unitary convolution with normalized adjacency matrices D- 1/2 AD 1/2 (D the diagonal degree matrix) so that the operator norm the linear convolution operation is bounded by one.

---

Padé approximant Padé approximations are optional rational functional approximations of given function up to given order. In unitary settings, Padé upproximants are often preferred because they return unitary operator. In contrast, Taylor approximations discussed previously only return a linear operator which can be made arbitrarily close to unitary operator. Padé approximants of order take the form
(52) where Pk. qk are degree polynomials. The degree k Padé approximant agrees with the Taylor expansion up to order 2k. The first order Padé approximant, also known as the Cayley map, has been used in prior neural network implementations [WPH*16, 16, HWY18, TK21] and takes the form
exp(M = P& (
1 2 M
exp(M)
I+ M
(53)
One practical drawback of Padé approximants are that they typically require implementations of a matrix inverse or approximations thereof which render this more challenging to implement. In our setting, we found that the Taylor approximation sufficed in accuracy and stability so we did not implement this.
Finally, should remark that Padé approximants be used pre-compute matrix exponentials to computer precision [Hig09, AMH10, AMH09). [LCMR19] use these techniques to parameterize unitary layers accurately for RNNs. One could pre-compute matrix exponentials of adjacency matrices in our setting to speed up training, though we have not implemented this in our experiments. We leave this for future work.
Other implementations of exponential map We briefly mention here for sake of completeness a different approach to approximating the exponential map based on the Makker-ampbell-- Hausdorfi formula [Hal15] which states that for matrices X, Y e C
Hausdill
exp(Xi X) eYp = exp x Y
[X
Xx, YJ
X XXXXX 12
12 Y. [X][ + -XX
(54)
The Lie-Trotter approximation uses the above fact to implement the matrix exponential of a sum of matrices product of matrix exponentials over elements of the sum. This method is often used in high dimensional spaces where the output of the exponential map on each Lie algebra generator known. The first order expansion takes the form [Tro59, 2ST+21]
X
X k
exp( X lim
exp
exp
~
exp
exp
(55)
k
where & is a positive integer controlling the level of approximation. The above is accurate to order O(1kk), and higher order accurate schemes exist. These methods are commonly used in machine learning, quantum computation, and numerical methods [CST*21, MGL*23, Llo96, Str68, MQ02]. One advantage of this approach that the approximation applied an operator in the Lie algebra always returns an element in the Lie group since the approximation is product of Lie group elements themselves.
D Fourier implementation of group convolution
In the main text, described generalized procedure to implement unitary convolution with parameterized operators in the Lie algebra of a group. We complement that with a mostly informal discussion how to implement unitary convolution in the Fourier domain. The algorithms summarized in Algorithm and Algorithm 2.
Before detailing the algorithm in Algorithm 3, provide brief overview of Fourier-based convo- lutions over arbitrary groups, which generalizes the classical Fourier transform to that over arbitrary groups. We recommend [S* for more complete and rigorous background. Throughout this, we will assume that groups are finite, though this can be generalized to other groups, especially those that are compact.
In numerical methods, they fall under the umbrella of splitting methods Strang splitting.
25

---

Algorithm 3 Unitary map in Fourier basis
Algorithm 2 Unitary map from Lie algebra
Input: Fourier transform F C A chise,
Input: equivariant linear operator L E C" C Input: vector C"
Input: Unitary operators (U/) U; E (dd)
Input: vector X E C*
I: L= (L - Lt) (skew symmetrize operator)
I: Y F (x) (apply Fourier transform)
2: Z = 1 Ui| Y (apply block diagonal uni-
2: return (x) (or approximation thereof)
taries)
3: return F - (2) (inverse Fourier transform)
A representation of group is map p G - puxd for a given field F such that p(g)p(g)) p p(gg') (homomorphism). A representation is reducible if there exists an invertible matrix Q E poxd such that (p(g) (g) is direct sum of at least k 2 2 representations Pl.....PP.. A such a decomposition does not exist. For any finite group G, a system .......P.... PK PK always exists. It holds that Σ, dim(p;)) 2 = |G] for any such set of unique irreducible representations [S*77]. Here, the uniqueness is to eliminate redundancies due to the fact new one by invertible transformation p'(x) Qp(g)(-1.
representation is irreducible if such
of unique irreps pl. pI......
that any irrep p can be mapped
The Fourier transform of a function f f G - C with respect to a set of irreducible representations
(irreps) (pr jm is given by:
f(p)) = E(wpii)) i= 1,
(56)
WEG
For abelian groups these irreps are all one dimensional. The set of (u) for the cyclic group for example correspond to the entries of the discrete Fourier transform matrix. For non-abelian groups, there always exists an irrep which is at least of dimension 2.
In Algorithm 3, we denote the Fourier transform F : -
- 0/ 1dtxd as map that takes in the inputs to a function f and outputs direct sum of the Fourier basis of the function f over the irreps. Given two functions f.g: G - C, their convolution outputs another function (f * g) : - C and is equal to
(f + (u)
Σ f(uv fgv))) (v()
(57)
VEG
In the main text, we describe these operations as vector operations over a vector space C". Setting = |G] and taking the so-called regular representation as maps acting on C!Gl can recover the form in the main text. Finally, the Fourier transform of their convolution is the matrix product of their respective Fourier transforms:
(p)) = ((p))
(58)
m are the irreps of G. The above assumes that all the functions have input domain over the group. This is not strictly necessary and generalizations exist which map functions homogeneous spaces to the setting above [KT18].
where Pije
The general implementation of Fourier convolution is given in Algorithm 3. Here, one employs a Fourier operator which block diagonalizes the input into its irreducible representations or some spectral representation. Then, applying blocks of unitary matrices in this representation and inverting the Fourier transform implements a unitary convolution. The details will depend on the particular form of the Fourier transform and irreducible representations. This method is often preferred when filters are densely supported and efficient implementations of the Fourier transform are obtained. Previous implementations have been designed for CNNs [TK21, KBLL22).
Example (Convolution on regular representation (Fourier basis)). Continuing the previous ex- ample, assume the group G has unitary irreducible representations Pl.....Pm (irreps) where Pi G Edi The group Fourier transform maps input function x G C to its irrep
basis as [FH13, KT18]
((p:) = Σ x()))((s).
(59)
gEG
and group convolution is now block diagonal in this basis
(m * (p) = xp)))(pp)
(60)
Implementing unitary convolution requires that m (p) is unitary for all irreps p.
26

---

E Architectural considerations
Handling complex numhers and enforcing isometry in neural networks requires changes some standard practice in training neural networks. We summarize some of the important considerations here and refer the reader to surveys and prior works for further details [BQL21, TK21, LCMRI9, KBLL22J.
Handling different input and output dimensions Unitary and orthogonal transformations defined on input and output spaces of the same dimension. Maintaining isometry for different input and output dimensions formally requires manipulations of the Stiefel manifold studied in various prior works [LCMRI9, LFT20, NA05, JD15J. When the input dimension is less than that of the output dimension, one simple way to implement semi-unitary or semi-orthogonal convolutions via standard unitary layers is simply to pad the inputs with zeros to match the output dimensionality. We also often will simply use standard (unconstrained) linear transformation first embed inputs in the given dimension that is later used for unitary transformations.
Nonlinearities For handling complex numbers, must typically redefine nonlinearities to handle complex inputs. We find that applying standard nonlinearities separately to the real and imaginary parts works well in practice in line with other works [BQL21]. To enforce isometry as well in the nonlinearity, we use the GroupSort: R² - R activation [TK21, ALG19), which acts on a pair of numbers
GroupSort(a. a, b) = (max(a, b), min( b)),
(61)
and is clearly norm-pon corm-preserving To apply this nonlinearity given layer, we split the channels or feature dimension into two separate parts and apply the nonlinearity across the split.
Initialization Given the constraints on unitary matrices and Herm-ttnn matrices, prior work
has proposed various forms of initialization that meet the constraints of these matrices. One strategy that has been effective in prior work and proposed in (HSL16, HWY18] is to initialize in 2 2 blocks along the diagonal. For skew symmetric matrices, one way of achieving this is to initialize 2 x blocks as
s
-s 0
where Unif(-n, .t) for example [HSL16].
Directed graphs Directed graphs present a challenge because their adjacency matrix is not guar- anteed to be symmetrie. Given an adjacency matrix A E R=** of directed graph, one simple way to proceed is to split the directed graph into its symmetric and non-symmetric parts A Asym Anonsym- Here, we assume that for matrix entry Aij. either Aij = A or Aj (i.e. one of the transposed entries is zero). Then, we set
= Aij if A, A 10
[Asymly
(63)
otherwise
and
Aij
if Aij # A ji-
Aij #0
A [Anossym]
Jig
Aji
if Aij # Aji. Aij =0
(64)
otherwise
Finally, one then perform graph convolution with the skew-Hermitian matrix We do not work with directed graphs in our experiments and have not implemented this in our code.
Ay + Anonsym-
(65)
Additional experiments
F.1 Additional results on toy model of graph distance
Fig. shows additional results for the toy model considered in the main text. As reminder, this
task is to learn the graph distance between pairs of randomly selected nodes in a ring graph of 100
27

---

layers
test MAE
0
layers
model
Residual GCN
test MAE
Grap CCop GCN
Unitary GCN
Vanilla GON
Spectral Convolu tion
0
Graph Attention Network
layers
best MAE
1000 150 200
250
epoch
Figure 3: Additional results the ring plot toy model including additional architectures. We show here the performance of various models with 5, 10, or 20 layers. The unitary GCN is the only message passing architecture that achieves stable performance with added layers and can learn the task. Apart from message passing architectures, global transformer architectures like GPS can learn the task when given Laplacian positional encoding. The trivial performance corresponding outputting the average output is shown as a dotted horizontal line.
nodes. Message passing architectures need at least 50 sequential messages to fully learn this task. layers are added to the unitary GCN, the network is able learn the task better. This in contrast to other message passing architectures which perform worse with additional layers. Apart from message passing architectures, strong performance is also achieved by transformer architectures like GPS with global attention. The networks we study are the vanilla GCN (Residual GCN includes skip connections) [KW16], graph attention network [VCC* 17], spectral convolution [ZK20], transformer- based GPS [2G and graph-coupled oscillator network (GraphCON), which is discretization of recond-orded ODE on the graph [RCR*22] 222]. Hyperparameters and additional network details are reported in App. G.
F.2 TU Datasets
MUTAG, and PROTEINS tasks from the TU Dataset database [MKB*20] As can be seen in table 3, with the exception of IMDB, GCN with UniConv layers outperforms message-passing GNNs tested against on all datasets, by margins of up to 18 percent. We follow the training procedure in [NHN*23] and report results for GCN and GIN from [NHN*23]. For GAT and unitary GCN, we tune the dropout and learning rate detailed in App. G. All results accumulated over 100 random trials. In addition, in Fig. show that the unitary GCN maintains its performance over large network depths in contrast to other message passing layers. The deteriation in performance of conventional message passing layers is likely a consequence of over-smoothing which we show does not occur in unitary graph convolution [CW20, RBM23].
We perform experiments on the ENZYMES,
F.3 Dihedral group distance
The dihedral group D,, is a group of order 2n describing the symmetries (rotations and reflections) of regular polygon. Its elements are generated by rotation generator and reflection generator s:
D, = (r. r" = (sr) = =)-
(66)
In this task, analaogous to the graph distance task in Sec. 5, the goal is to learn the distance between two group elements g. g in the dihedral group D,,- Formally, aim to learn target function R DDal - Z mapping inputs of dimension 2n (the vector space of the regular representation) to
28

---

METHOD
ENZYMES IMDB
MUTAG TEST
PROTHINS TEST AP
TEST APT
TEST APT
GCN GIN
25.5 # 1.2
49.3
68.8
2.4
70.6 # 0.7
OURS MP
31.3 * 1.1
69.0 + 1.0
75.7 + 3.6
69.7 + 0.8
GAT
26.8 = 1.2
47.0 1.1
68.5
72.6 = 0.8
UNITARY GCN
41.5 # 1.6
61.2 1.4
86.8
3.3
75.1 + 1.3
WIDE UNITARY GCN
42.1 1.5
62.4
1.3
87.1
3.5
75.6 1.0
Table 3: Comparison of Unitary GCN with Lie UniConv layers (Definition 3) with other GNN architectures on the TU datasets. Each complex number is counted as two parameters for our architectures, except for wide Unitary GCN which counts a complex numbers as one parameter so that the width of hidden layers roughly matches that of vanilla GCN.
0.85
Acoraay
I-CCN
0.65
GNT
040
0.55
20
100
120
Numbar Layers
Figure 4: Test accuracies on Mutag for GCN, GIN, GAT, and GCN with UniConv layers with increasing number of layers. Except for the unitary network, all other message passing architectures collapse to trivial accuracy levels as the number of layers increases.
positive integers. The input space PM indexed by group elements and convolution is performed on the regular representation of the group. Each data pair (2%, y;)i drawn follows:
Draw two group elements g.g' g Unif(D,) from the uniform distribution over the group Dn without replacement.
Set eg eg' where eg E IDal is a unit vector whose entries are all zero except for the entry corresponding to operation g set to one.
Set y; dp, (g.g') E Z where dp, (g.g') indicates the number of applications of the generators that need to be applied to go from g to g', i.e.
dp, (8. (') ==
min
{T aia2 - 01a2-..arr--3 =g)=
(67)
dl (l..r.r-1)
Fig. 5 plots the performance of three different networks in this task. The vanilla network performs standard convolution each layer where the group convolution parameterized over elements of the generator. The residual network is the same architecture but includes skip connections after convolutions. The unitary network applies the exponential map to skew-Hernitian version of the group convolution outlined earlier. The unitary network is able learn this task in fewer layers and with added stability. No hyperparameter tuning was performed in these experiments. Adam optimizer parameters
set the default settingg All networks have global average pooling after the last convolution layer followed by 2 layer MLP to output scalar. The number of channels is to 32 for each convolution layer.
E.4 Orthogonal Convolution
To compare orthogonal (real-valued) and unitary convolutional layers, we repeat our experiments on Peptides-func and Peptides-struct from the main text. We report the results in table 4. Edge features
29

---

layers - 20
layers 50
network
unitary
60
residual
metric
value
40
train
test
20
0
200
epoch
epoch
5: Training and test MAE of the distance learning task for the dihedral group. Listed as column headers are the number of convolution layers in each network. Residual and Unitary convolutional networks are both able to learn the task under default hyperparameters for the optimizer.
METHOD
PEPTIDES-FUND
PEPTIDES-STRUCT TEST MAE
TEST AP I
UNITARY GCN
0.7043 = 0.0061
0.2445 = 0.0009 0.2429 0.0007
WIDE U. GCN
0.7094 = 0.0020
NARROW O. GCN
0.701 = 0.0096
0.2461 + 0.0021
ORTHOGINALL GCN
0.7037 * 0.0053
0.2433 0.0018
Table 4: Comparison of GCN with Lie UniConv layers (Definition 1) with real-valued (hence orthogonal) or complex-valued (hence unitary) on Peptides-func and Peptides-struct. The Narrow Orthogonal GCN as the same width and depth as the Unitary GCN where we counted complex weights twice. Narrow Orthogonal GCN therefore has only about 285K parameters. Orthogonal GCN has the same width and depth as Wide Unitary GCN, and therefore about 490K parameters.
are not included this ablation as no edge feature aggregator was included in the architecture. GCN with OrthoConv layers achieves performance levels similar to UniConv without using complex numbers in its weights.
G Experimental details
For LRGB datasets, we evaluate our GNNs using the GraphGym platform [YYL20]. In Table 1, list reported results where available from various architectures [KW16, BL17, XHLJ18, TRRG23, HHL*23, GDBDG23, RGD*22, MLL*23, SVV*23, TRWG23J. Reported results are taken from existing papers as of May 1, 2024. Experiments were run on Pytorch [PGC* 17] and specifically the Pytorch Geometric package for training GNNs [FL19].
Our implementation of unitary graph convolution does not take into account edge features. Thus, for datasets with edge features, at times, included single initial convolution layer using the GINE [XHLJ18] or Gated GCN [BI.1]] architecture which aggregates the edge features into the node features. For instances where this is done, indicate the type of layer "edge aggregator" hyperparameter in the tables below.
All our experiments were trained on single GPU (we used either Nvidia Tesla V100 Nvidia RTX A6000 GPUs). Training time varied depending on the dataset. Peptides datasets trained no more than 15 seconds per epoch. PascalVOC-SP took about minute per epoch to train and COCO-SP took about 15 minutes per epoch to train. The PascalVOC-SP and two Peptides datasets are no more than GB in size. The COCO dataset much larger, about 12 GB in size. The TU and Heterophilous Node Classification datasets are all less than 1GB in size and take only few second train per epoch.
Remark 12 (Parameter counting). LRGB datasets require neural networks to be within budget of 500k parameters. For fair comparison, complex numbers are counted as two parameters each. Furthermore, to handle constraints for parameterized matrices in the Lie Algebra, we treat the
30

---

Table Hyperparameters on Peptides datasets. Number of parameters are counted using the default Pytorch method which undercounts complex numbers or the methodology as stated in Remark 12. Edge aggregator indicates single layer of the specified type which used to incorporate edge
feature data into node features.
Unitary GCN
Lie Unitary GCN
PEPTIDES-FUNC HEPTIDES-STRUC
PEPTIDES-FUNC PEPTIDES-STRUCS
0.001
0.001
0.001
0.001
dropout
0.1
0.2
0.1
0.2
Conv. Layers
10
6
14
6
hidden dim.
135
200
155
200
PE/SE
RWSE
LapPE
RWSE
LapPE
batch size
200
200
200
200
epochs
2000
500
4000
500
edge aggregator
GINE
GINE
GINE
GINE
Param. (see Remark 12)
468K
470K
466K
470K
Param. (default Pytorch)
282K
305K
464K
305K
Table 6: Hyperparameters on Coco and PascalVOC datasets. Number of parameters are counted using the default Pytorch method which undercounts complex numbers or the methodology as stated in Remark 12. Edge aggregator indicates single layer of the specified type which is used to incorporate edge feature data into node features.
Unitary GCN
Lie Unitary GCN
COCO-SP
PASCALVOC-SP
COCO-SP
PASCALVOC-SP
Ir
0.001
0,001
0.001
0,001
dropout
0.1
0.1
0.1
0.1
# Conv. Layers
12
15
12
15
hidden dim.
120
145
155
145
PE/SE
None
RWSE
None
RWSE
batch size
50
50
50
50
# epochs
750
1000
500
1000
edge aggregator
Gated
Gated
Gated
Gated
# Param, (see Remark 12)
466K
453K
478K
453K
# Param. (default Pytorch)
290K
305K
481K
305K
number of parameters the dimension of the Lie Algebra (i.e. the number of parameters to fully parameterize the Lie algebra).
Toy model: graph distance All networks consist of the stated number of convolution trans- former layers with feature dimension 128 followed by global average pooling over nodes. Pooled features then passed through single hidden layer MLP with 128 dimension width. For net- works with 5, 10 and 20 layers respectively, we set the learning rate to 0.0007, 0.0003 and 0,0001 respectively. Networks are trained with the mean average error (LI) loss. Activation functions for all networks are set to GELU apart from the unitary networks where we choose the norm- preserving activation GroupSort [TK21, ALG11] (see App. E). ensure unitary layers are also truly norm- preserving, we do not include a trainable bias in these layers.
Peptides For the Peptides experiments, the training procedure follows that of [TRRG23). Unless otherwise stated, we use the Adam optimizer with learning rate set to 0.001 and a cosine learning rate scheduler [KB14]. Most hyperparameters were taken from [TRWG21]. For our purposes, we tuned dropout rates in the set 10.1, 0. 15,, 0.2) and tested networks of layers in the set (6, 8, 10, 12, 14) selecting the hidden width to fit within the parameter budget. For larger levels of dropout, we found that we needed to train the network for more epochs to achieve convergence. Final hyperparameters are listed in Table 6.
COCO-SP and PasCaIVOC-SP For the COCO-SP and PascalVOC-SP experiments, our training procedure again follows that of [TRRG23). We use the Adam optimizer with learning rate set to 0.001 and a cosine learning rate scheduler [KB14], unless otherwise stated. For our purposes, we
31

---

Table 7: Hyperparameters on the TU datasets.
Unitary GCN
Unitary GCN
ENZYMES
IMDB
MUTAG
PROTEINS
ENZYMES
IMDR
MUTAG
PROTFINS
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
dropout
0.5
0.5
0.5
Conv. Layers
6
6
hidden dim.
128
128
128
128
256
256
256
256
PE/SE
None
None
None
RWSE
None
None
None
RWSE
Edge Features
No
No
Yes
No
No
No
Yes
No
batch size
50
50
50
50
50
50
50
50
epochs
300
300
300
300
300
300
300
300
Table Hyperparameters the Heterophilous Graph datasets.
Unitary GCN
Lie Unitary GCN
ROM
AMA
MINE
TOL
QUE
ROM
AMA
MINE
TOL
QUE
Ir
0.001
0.001
0.0001
0.0001
0.0001
0.001
0,001
0.0001
0.0001
0.0001
dropout
0.2
0.2
0.2
0.2
0.2
0.5
0.2
0.2
0.2
0.5
# Conv. Layers
8
8
8
8
4
8
8
4
hidden dim.
512
512
512
512
512
512
512
512
512
512
PR/SE
I.PE
LAPE
LAPE
LAPE
LAPE
LAPE
LAPE
L.PE
LAPE
LAPE
batch size
50
50
50
50
50
50
50
50
50
50
epochs
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
tuned dropout rates in the set (0.1, 0.150.1,1.. 0.2) and tested networks of layers in the set {6, 8, 10, 12, 14) selecting the hidden width fit within the parameter budget. For larger levels of dropout, found that we needed to train the network for more epochs to achieve convergence. Final hyperparameters listed in Table 6.
TU Datasets Our experiments are designed as follows: For a given GNN model, we train on a part of the dataset and evaluate performance on a withheld test set using train/val/test split of 50/25/25 percent. all models considered, we record the test set accuracy of the settings with the highest validation accuracy. As there is certain stochasticity involved, especially when training GNNs, we accumulate experimental results across 100 random trials. We report the mean test accuracy, along with the 95% confidence interval. For the TU Datasets, our training procedure and hyperparameter tuning procedure follows that described in [N].* Namely, we fix the depth and width of the network as in [NH and tune the learning rate and dropout parameters. Final hyperparameters are listed in Table To ensure fairness and comparability, we conducted the same hyperparameter searches with the baseline models we compare against, but found improvements over the numbers reported in previous papers. We therefore report their (higher) numbers instead of ours for these models.
Heterophilous Graph Datasets For given GNN model, we train a part of the dataset and evaluate performance on a withheld test set using train/val/test split of 50/25/25 percent, in accordance with [PKD*23]. Note that do not separate ego- and neighbor-embeddingg, and hence also do not report accuracies for models from the original paper that used this pre-processing (e.g. GAT-sep and GT-sep). Our training procedure generally follows that described the original paper [PKD*23]. We use the AdamW optimizer, stop training after no improvement in 200 steps, and including residual connections in the intermediate network layers. For the unitary GNNs, we tuned values for the dropout in (0.2, 0.5), number of layers in {4, 6, 8) and learning rate in (0.001, 0.0001): To output single number, we use single convolution layer (SAGE convolution) map from the higher dimensional space to single number for each node. [PKD*23] 23] differs in that they have an MIP between layers; we opt for more simple approach. Final hyperparameters are listed in Table 8. To ensure fairness and comparability, we conducted the same hyperparameter searches with SAGE and GCN, but generally found no significant differences with respect to the numbers reported in previous papers. We therefore report their usually higher numbers instead of ours for these models.
32

---

G.1 Licenses
We list below the licenses of code and datasets that we use our experiments.
Model/Dataset
License
Notes
LRGB [DRG*22 22]
Custom
See here for license
TUDataset [MKB*20]
Open
Open sourced here
Heterophily Data [PKD*23]
N/A
Data is open source; no license stated in repository
Pytorch Geometric [FL19]
MIT
See here for license See here for license See here for license See here for license
GraphGym [YYL20]
MIT
GraphGPS [RGD*22]
MIT
Pytorch [PGC*17]
3-clause BSD
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: this work, we support formal claims with proof's and include results for various different datasets which show that the unitary layer propose enhances stability and achieves strong performance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have described limitations of our work at various points. Incorporating unitarity is not panacea and we mention the challenges in dealing with this (e.g. see discussion section).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All formal statements are proven either in the main text or Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We follow established training procedures as stated in the main Code is shared to replicate various experiments. Training details and hyperparameters are reported in App. G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps
taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way reproduce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results.
35

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is shared in the anonymized zip file to replicate the LRGB Peptides experiments and toy model experiments (both the ring dataset and the dihedral group convolution in App. F). Instructions to initialize our unitary/orthooonal convolution layer and perform experiments are given therein. To handle different datasets, we had format code differently for the various code bases, and we did not have time to make the code consistent for other graph experiments. Nonetheless, we plan to make all code available before eventual publication and/or during rebuttals if desired. In addition to the submitted code, experimental details are provided the main text as well as App. F and
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. //nips.ccppublll///// wwtpccccpcccc//ccccccccccccc.lll heallic/guieee gewggeddeeeeee /Code ssi onPolicy) for details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We report how we trained different models in the main text and App. G. For LRGB experiments, procedure in [TRRG23] as mentioned in the main text. Hyperparameters and other training details are reported in App. G for all experiments.
report in comparison to reported results and follow the training
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental
material.
7. Experiment Statistical Significance
Does the reporreport error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
36

---

Justification:
Error bars included in all experiments and tables. Details are provided in App. G.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: single GPU needed to run an individual experiment; details are provided in App. G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:/ hwa.rppp..ccpalllc//ccccccccaaad
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
37

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work presents foundational research improving learning on graphs and groups. Though this work has impact on the research community in machine learning, do not any clear links questions of privacy, misuse, fairness, other major societal impacts here.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is largely foundational and theoretical. All models and datasets are relatively small and scientific in nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
38

---

Justification:
Datasets and models are cited throughout and licenses are listed in App. G.1.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//tttte dataatsssss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The unitary convolution layers shared in the attached code and documented
in the text. Apart from the simple toy datasets of graph distance on a ring or group, no new datasets are introduced here.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
39

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equívalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
40


Reviews:
[{"review_id": "BTzdr5pP4E", "reviewer": "Reviewer_9r1r", "summary": "This paper proposed a new convolution operator UniConv on graphs and general tasks. Both graph convolution and general form convolution form are provided based on the group theory. With the toy experiment, it shows the advantages of the proposed method clearly. Based on both theoretical and experimental analysis, the proposed network is effective in long range graphs and heterophilic graphs.", "questions": "See weakness.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theoretical analysis is conducted to show the effectiveness in handling oversmoothing and oversquashing issue.\n\n2. The toy analysis is easy to understand and clearly shows the advantage.", "weaknesses": "1. Though the general form of convolution is provided. It is not evaluated in experiment. I will suggest putting these content in the appendix in this case. Otherwise, it is better to provide the corresponding experimental results.\n\n2. The computational cost is higher compared to other methods, but there are no experimental results to show the important details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and feedback. We respond to their questions and comments below.\n\n&nbsp;\n___\n> Though the general form of convolution is provided. It is not evaluated in experiment. I will suggest putting these content in the appendix in this case. Otherwise, it is better to provide the corresponding experimental results.\n\nWe thank the reviewer for pointing this out. Our primary goal was to show a general recipe for constructing equivariant unitary/orthogonal maps, which allows for introducing more general convolution on finite groups beyond just graph convolution. Our main application are GNNs, hence, much of the experiments are focused on the graph setting. We provide experimental results for another instance of the general case, namely group convolution over the dihedral group, in Appendix E.3. We note that previous literature has studied unitary/orthogonal CNNs which also fit within this framework. We discuss and reference these works in the extended related works (see Appendix A.1). We will add more explicit pointers to these sections in the main text.\n\n&nbsp;\n___\n> The computational cost is higher compared to other methods, but there are no experimental results to show the important details.\n\nThe unitary and orthogonal layers have a constant factor overhead over standard message passing. As stated in the paper, the runtime is $O(KnD)$ where $K$ is the approximation in the exponential map, $n$ is the number of nodes, and $D$ is the maximum degree of the graph. Since the approximation error is exponentially small in $K$ (see Appendix C), we found that setting $K$ to be a constant (around 10 for example) sufficed in all experiments. We will specify this in the main text in the revised manuscript.\n\nNote, that this is more efficient than many graph algorithms such as graph transformers which are quadratic scaling in $n$ and other proposed (near) unitary graph message passing algorithms which also scale poorly in $n$ and $E$. \nThe computational cost is detailed further in Appendices A and C. We should also note that this factor $K$ overhead is in some sense unavoidable if one wants invertibility and isometry as detailed in Proposition 4.", "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": "1Hmdagp7Ce", "reviewer": "Reviewer_vJVB", "summary": "This paper introduces convolutional layers for GNNs that are based on group-convolutions. Some of the proposed layers have interesting theoretical properties such as avoiding oversmoothing or vanishing gradients. Experimentally, these layers are able to aggregate information across long distances and achieve strong results on real-world benchmarks.", "questions": "Most of my questions are already part of the weakness section.\n\n- **(Q1)** (Lie) UniConv are implemented as a $k$-th taylor approximation. What is the value for $k$? It seems to me like the ability to model long-range interactions is primarily dependent the value of $k$ and the number of layers $L$, so knowing this value seems important.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- **(S1 - Novelty)** The contributions in this paper seem novel.\n\n- **(S2 - Significance)** From a theory perspective, some of the proposed operations have interesting theoretical properties such as that they can avoid oversmoothing or vanishing gradients.\n\n- **(S3 - Significance)** The authors perform extensive experiments on real-world datasets and achieve strong results on most of them.", "weaknesses": "- **(W1 - Clarity and Significance)** The reader is not guided through the paper and it is difficult to understand the flow of ideas. I will give some examples of this:\n\n   - In Section 3.1 (Lie) UniConv layers are introduced which is the main contribution of the pape. However, to me it was not clear that this is the central definition. \n\n   - In the following Section 3.2, the paper generalizes the setting of unitary convolutions and gives several examples. Yet, to me it is unclear what this section intends to communicate and how it is relevant to the rest of the paper. \n\n   - Another example of this is the “Vanishing/Exploding gradients”-part of Section 4, here dynamical isometry is defined as a measure as a property to analyze exploding gradients and an example is given that a combination UniConv together with a yet completely undefined activation function (GroupSort) is “perfectly dynamically isometric”. This raises many questions to the reader: Why is an example important enough to warrant the definition of Dynamical isometry? How does this relate to the main contribution of the paper? Are vanishing / exploding gradients a problem with GNNs? What is GroupSort and is it actually used in practice? \n\n- **(W2 - Clarity)** The experiment section is difficult to read and does not properly explain the experiments or the design decisions. For example, for the graph distance dataset the model is not mentioned in the text. In this case, the model is GCN with the novel Lie UniConv layer (Figure 2). However, it is not explained why the Lie UniConv layers are used and not the UniConv Layers. Similarly, for the experiments on LRGB UniConv layers are used but it is not explained why Lie UniConv layers are not tried.\n\n**To sum up.** To me it seems like this could be a good paper with interesting ideas and solid experiments. However, the writing significantly holds it back and I think more time is required to allow  the authors to rewrite their paper. Furthermore, I think that there is a lot of useful information hidden in the appendix and it might make sense to focus the paper on the main idea (Section 3.1) and move other parts to the appendix to make more space.  As I do believe that this paper requires significant changes to the text I thus vote to reject.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for praising the novelty and theoretical results in our work. We have read their concerns about the format and writing of the paper, and hope to address them below. \n___\n> In Section 3.1 (Lie) UniConv layers are introduced... it was not clear that this is the central definition.\n\nCan the reviewer expand on what they mean by central definition? From our understanding, the definitions of UniConv operations are central to the paper. \n\n\n> The paper generalizes the setting of unitary convolutions... it is unclear what this section intends to communicate...\n\nOur goal was two-fold: to show that unitary convolution on graphs is a simple method applicable to general symmetric domains, and to connect it to previous CNN implementations, demonstrating how to generalize beyond graph convolution, such as applying unitary convolution to hypergraphs or other message-passing types. That being said, we understand the reviewer's concerns. We will shorten this section in the paper focusing specifically on the points above. Please see our general response for details.\n\n> Dynamical isometry is defined as a measure as a property to analyze exploding gradients and an example is given that a combination UniConv together with a yet completely undefined activation function (GroupSort) is “perfectly dynamically isometric”... Why is an example important enough to warrant the definition of Dynamical isometry?\n> Are vanishing / exploding gradients a problem with GNNs?\n\nVanishing/exploding gradients are a general problem with any deep or recurrent network and occur because norms of the states at intermediate layers grow or decay exponentially with depth (see e.g. [LMTG19], [LMGK21]). GNNs are no different from deep networks in that they also have weights initialized randomly causing norms to grow or decay as a product of the number of layers. We found that standard GNNs cannot train at very large depths (see figure 4 showing standard message passing schemes do not train well at around 40 layers for example). We also show an example of a standard GCN featuring vanishing/exploding gradients in the one page response pdf (UniConv does not have this issue in contrast).\n\nFor scalability to many layers, stable information and gradient propagation is essential. Dynamical isometry offers a rigorous framework to study this stability, supported by experiments and theory across various architectures. We aim to show that GNNs also exhibit the stability properties described by dynamical isometry.\n\n  \n\n\n> What is GroupSort and is it actually used in practice?\n\nGroupsort is a nonlinearity that splits the input vector into pairs of numbers and sorts the pairs (see eq. 58). It is a nonlinearity that preserves isometry and used in the adversarial learning literature to get provable adversarial bounds via unitary architectures. E.g., see its use in Trockman & Kolter Orthogonalizing convolutional layers with the cayley transform. \n\n\n\n> For the graph distance dataset the model is not mentioned in the text. In this case, the model is GCN with the novel Lie UniConv layer (Figure 2). However, it is not explained why the Lie UniConv layers are used and not the UniConv Layers. Similarly, for the experiments on LRGB UniConv layers are used but it is not explained why Lie UniConv layers are not tried.\n\nPlease see global response and additional figures/tables for a full answer to this. In summary, this choice did not make a significant difference. For experiments where networks were not very deep, we found that enforcing unitarity in the message passing was helpful and unitarity was not needed in the feature transformation.  For example, UniConv performs slightly better in LRGB though little difference is observed. \n\n\n\n\n\n> To me it seems like this could be a good paper with interesting ideas and solid experiments...I think more time is required to allow the authors to rewrite their paper... there is a lot of useful information hidden in the appendix and it might make sense to focus the paper on the main idea (Section 3.1) and move other parts to the appendix to make more space.\n\nIf we understand the reviewer correctly, they have requested that we focus more on section 3.1, defer parts of section 3.2 to appendix, and make more space for clarifying some points such as when to use Lie UniConv vs. UniConv. We will make these changes in the revised manuscript. Are there other parts of the paper that the reviewer feels should be moved from the appendix to the main text or vice versa?\n\nWe are hesitant to make significant changes to the writing and format given this concern was not shared by all the reviewers, but are of course open to more feedback.\n\n> (Lie) UniConv are implemented as a k-th taylor approximation. What is the value for k?... knowing this value seems important.\n\nWe found in all our experiments that $k=10$ suffices. The error in the Taylor approximation exponentially decreases with $k$. This value is in line with that in other papers (e.g. see [SF21]). We will state this in the main text.\n\n___\n&nbsp;\n\n**Dynamical Isometry References:**\n\n[SMG13] Saxe et al. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv:1312.6120, 2013 \\\n[XBSD+18]  Xiao et al. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. ICML, 2018 \\\n[PSG18] Pennington et al. The emergence of spectral universality in deep networks. PMLR, 2018\n\n&nbsp;\n\n**Vanishing/ Exploding Gradient Problems with GNNs:**\nIn addition to above, see also:\n\n[LMTG19] Li et al. Deepgcns: Can gcns go as deep as cnns?. Proceedings of the IEEE/CVF international conference on computer vision, 2019. \\\n[LMGK21] Li et al. Training graph neural networks with 1000 layers. PMLR, 2021.", "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": "ldnkWvGzhP", "reviewer": "Reviewer_feJe", "summary": "In this paper the authors propose a mathematically consistent treatment of unitary convolutions in the context of neural networks defined on graphs and groups. In the graph neural network context, the main idea is to transform a standard linear convolutional layer $f_\\text{conv} = \\mathbf{AXW}$ with $\\mathbf{A}$ the adjacency matrix, $\\mathbf{X}$ the signal input matrix and $\\mathbf{W}$ the parameterize into a linear layer $f_\\text{Uconv}$ that is unitary (norm preserving), taking into account both the matrices $\\mathbf{A}$ and $\\mathbf{W}$ (previous literature focus on $\\mathbf{W}$ or perform this in a less natural way (with worse computational complexity) [QBY24]. The main idea revolves around the following two steps: (1) project the operation into matrix Lie algebra (e.g., the space of skew-symmetric matrices) (2) apply the exponential map on the projected operation to obtain an unitary operation. In the graph setting the authors do this in two ways: the first is called \"Separable unitary graph convolution (UniConv)\" and takes the form $f_{\\text{Uconv}} (\\textbf{X}) = \\exp(i\\textbf{A}𝑡)\\textbf{X}\\textbf{U}, \\textbf{U} \\textbf{U}^{\\dagger} = \\textbf{I}$. The second is called \"Lie orthogonal/unitary graph convolution (Lie UniConv)\" and is defined by applying an exponential map on a convolution with skew-symmetric weight matrices in Lie algebra, having the advantage of being parameterizable over the reals only. The authors then discuss how to approximate the exponential map (they resort to simple Taylor truncation).  Subsequently, the authors develop the theory in the case of general groups and show to ways of obtaining unitary convolutions: the first case generalizes the two methods defined for graphs, by first skew-symmetrizing the equivariant map and then applying exp; the second is defined as a (block-diaognal) convolution in the Fourier domain followed by inverse transform. Following the authors show basic properties of the proposed method (invertibility, isometry and equivariance) and prove favorable results which mainly follow by isometry (avoiding oversmoothing, avoiding vanishing/exploding gradients). In the experimental section, the authors perform experiments on toy ring graph (on Lie UniConv) and the standard benchmarks LRGB and Heterophilous Graph Dataset (on UniConv) (also showing group convolution in Appendix on Dihedral group $D_n$).", "questions": "- I don't see how the graph convolutions defined are particular cases of the group convolutions described. Is it the symmetric group S(n) acting on the graph?\n- Line 122: Why UniConv has a \"tensor product nature\"? From what I understand the tensor product is more related to the Lie UniConv because you can write it as $\\exp(\\mathbf{A} \\otimes \\mathbf{W}^T)$.\n- Line 186: \"We set input/output representations to be equal so that the exponential map of an equivariant operator is\nitself equivariant\": Assuming this does not limit the class of groups or transforms we can use? Not all groups have irreps of same dimensions. Or we say that the transforms are equivariant only in this sense? Also why exponential map is equivariant only if the input output representations are equal?\n- Line 212: is (I − A) a type of graph Laplacian?\n- Line 272: Why authors don't compare to new architectures as well on this task, like in Table 1? Also I see in Appendix that GPS it is performing pretty well w.r.t. Unitary GCN but it was not put in this graph (maybe to show better improvements?).\n- Line 763: I think authors should say that in case of Algo 2 this follows because Fourier transform is unitary. It is not clear if and why this should be the case in finite group setting.\n- Line 766: \"For unitary convolution in the Fourier domain (Algorithm 2), equivariance follows from convolution theorems where linear operators appropriately applied in the block diagonal Fourier basis are equivariant\". This is too succinct and should be more expanded formally.\n- Line 821: missing trace on following lines and last line should not be put there ($= R_{\\mathcal{G}(\\mathbf{X})}$)", "limitations": "The authors have discussed limitations of their contribution adeguatly.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Well founded mathematical formalism, defining unitarity in message passing graph neural networks in a natural way.\n- Strong performance over other message passing algorithms, comparable performance with respect to graph attention based models. On very large graphs attention could be prohibitive so UConv could perform well in that situation.\n- The paper has an extensive and complete literature overview, comparing with related literature in very detailed manner (the Appendix on related work relative to unitary convolutions is a very good addition and clearly let us understand the contribution).\n- Theoretical analysis on oversmoothing and vanishing/exploding gradients shows the advantage on adopting UConvs in a quantitative way.", "weaknesses": "- There aren't many experiments on Lie UniConv. From what I understand, the only experiment with this layer is the graph ring experiment in Figure 2. Also it would have been interesting to see comparison between the two type of convolutions (UniConv vs Lie UniConv), with the more realistic datasets, in order to asses which one performs better in practice.\n\n- The part on unitary maps in Fourier basis feels somehow detached from the general discourse of the paper. I believed the author added it for completeness but (1) the theory to understand it is relatively advanced (had to study externally some representation theory to understand well the definition of Fourier transform on finite groups); a short primer on representation theory in the Appendix, similar to the one for Lie groups / algebras, would have been of great help. (2) There are no experiments in this setting. (3) some parts are a little bit shaky, for example in: ```One can also generally implement convolutions in the (block diagonal) Fourier basis of the graph\nor group (Algorithm 2). Here, one employs a Fourier operator which block diagonalizes the input into its irreducible representations or some spectral representation.```, if one considers using the eigendecomposition of some graph Laplacian as a spectral basis, the (graph) Fourier transform is not given by a set of matrices varying over irreps but a signal of the same dimensionality of the input function. I do not think one can use the same approach there.\n\n- Sometimes authors leave facts implicit and the writing could be improved in key places. For example I had difficulty understanding why Lie UniConv returns an unitary map before looking at the tensor product version of $g_{\\text{conv}}$ (Eq. (36), Proposition 6). Also the statements in Propositions 4 and 7 are not really clear from a first reading, some more intuition about the statements should be given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and going through the paper in detail. There are many insightful questions and points of feedback that we will incorporate into the draft. \n___\n\n> There aren't many experiments on Lie UniConv... it would have been interesting to see comparison between the two\n\nWe agree with the reviewer on this point and have included many comparisons in the global response and attached one page pdf there. This includes experiments for Peptides and TU datasets. In general, the empirical differences are rather minimal.\n\n> The part on unitary maps in Fourier basis feels somehow detached from the general discourse of the paper... the theory to understand it is relatively advanced... a short primer on representation theory in the Appendix... would have been of great help. There are no experiments in this setting.\n\nWe aimed to show that Fourier space can often speed up operations and simplify convolution as observed in many works. Since this is tangential to the main points, we'll move it to the appendix with a detailed background. In the main text, we'll briefly note that a Fourier basis methodology exists.\n\n> The part on unitary maps in Fourier basis feels somehow detached... if one considers using the eigendecomposition of some graph Laplacian as a spectral basis, the (graph) Fourier transform is not given by a set of matrices varying over irreps but a signal of the same dimensionality of the input function.\n\nWe believe there is a small misunderstanding here. One can diagonalize the adjacency matrix of an undirected graph and perform convolution over the spectral basis as in spectral graph convolution. When the input and output is a single channel, this can be treated as block diagonal operations, but the blocks are trivially scalars  ($1 \\times 1$ matrices). More generally, the block size will depend on the input/output channel dimensions. We will provide a lemma explicitly showing this in the more general case for arbitrary graphs/groups.\n\n> Sometimes authors leave facts implicit... I had difficulty understanding why Lie UniConv returns an unitary map before looking at the tensor product version of (Eq. (36), Proposition 6). Also the statements in Propositions 4 and 7 are not really clear from a first reading, some more intuition about the statements should be given.\n\nWe agree this was slightly confusing on a first read. We will revise these passages for clarity in the updated manuscript.\n\n&nbsp;\n___\n**Questions:**\n\n> I don't see how the graph convolutions defined are particular cases of the group convolutions described. Is it the symmetric group S(n) acting on the graph?\n\nTo map graph convolution to this case where $conv_G(X) = \\sum_i T_i X W_i$, simply set $T_i= A^i$ or the $i$-th power of the (potentially normalized) adjacency matrix. We will explicitly state this after the equation in the main text.\n\n> Line 122: Why UniConv has a \"tensor product nature\"? From what I understand the tensor product is more related to the Lie UniConv because you can write it as $\\exp(A \\otimes W^T)$.\n\nThe reviewer is right that Lie UniConv is parameterized in a tensor product fashion, but crucially, the output is not a tensor product: there may not exist matrices $M_1, M_2$ such that $\\exp(A \\otimes W^T) \\neq M_1 \\otimes M_2$. In contrast, UniConv is always of the form $\\exp(iA)\\otimes W^T$ and one can apply the feature and message passing transformations separately and in sequence. We tried to capture this in remark 2, but will clarify in the main text.\n\n> Line 186: \"We set input/output representations to be equal so that the exponential map of an equivariant operator is itself equivariant\": Assuming this does not limit the class of groups or transforms we can use? Not all groups have irreps of same dimensions...\n\nThis statement is written confusingly and we will clarify. What we meant to say is that the input/output representations need to act on the same vector space. For a unitary transformation to be well defined, it needs to be invertible and isometric so the input and output vector space are must have the same dimension. One can generalize beyond these assumptions, but it seems unnecessary for our purposes. \n\n> Line 212: is (I − A) a type of graph Laplacian?\n\nThat is correct. \n\n> Line 272: Why authors don't compare to new architectures as well on this task, like in Table 1? Also I see in Appendix that GPS it is performing pretty well w.r.t. Unitary GCN but it was not put in this graph (maybe to show better improvements?).\n\nWe show GPS for sake of completeness, but did not include it in the main plots because it is not a message passing architecture. The goal of the toy model task was to see which architectures can learn long range dependencies with local operations. For transformers, the notion of long range dependency is not as well defined. \n\nIs there another method that the reviewer feels we should compare to? We are happy to include it.\n\n> Line 763: I think authors should say that in case of Algo 2 this follows because Fourier transform is unitary. \n> Line 766: \"For unitary convolution in the Fourier domain (Algorithm 2), equivariance follows from convolution theorems...\". This is too succinct and should be more expanded formally.\n\nYes, we will say that and expand on this. Thank you for pointing it out.\n\n> Line 821: missing trace on following lines and last line should not be put there ($=R_G(X)$)\n\nWe think there is a misunderstanding. The following lines have the notation $vec(X)^\\dagger ... vec(X)$ which is an equivalent way of writing the trace as an inner product between vectors since $Tr(A^\\dagger B)= vec(A)^\\dagger vec(B)$ where $vec$ vectorizes the matrices. We will use inner product angle bracket notation to make this clearer. The last line also needs the normalization by the Frobenius norm which we will include as a separate line. Thank you for pointing this out.", "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": "KHnXmaZCYa", "reviewer": "Reviewer_EVha", "summary": "The paper proposes to use so-called \"unitary group convolutions\" in graph neural networks, with main motivation to do steps to overcome gradient collapse or explosion and oversmoothing effects in graph neural networks under equivariance constraints. This fits within a more general line of work in which unitary constraints are applied for regularizing various learning architectures.", "questions": "What's the relative benefit compared to more naive normalizations? \n\n\nMinor correctionsl/doubts:\n1) lines 29-31: \"it has been widely observed that group-convolutional networks suffer from instabilities as their depth increases\" -- if it's widely observed, please indicate a few references where this was observed?\n\n2) line 103: \"linear convolution\" -- as opposed to what other kind of convolution? isn't convolution always linear?\n\n3) line 144: the following is an important point/issue. \n\"When W contains only real-valued entries, the above returns an orthogonal map\" -- I don't follow this, why is that? this statement would require a proof, because it far from obvious, and in general it is false. Recall that a product of matrix exponentials is in general not the exponential of the product, so $exp (g_{\\mathrm{conv}})(X) \\neq e^A X e^{W^*}$ in this case.\n\n4) I don't see what's the importance / relevance of examples 1 and 2 from Section 3. I think these are standard examples, they can be skipped or moved to the appendix. \n\n5) lines 217-218: this probably the most important theory issue of the paper.\n \"the Rayleigh quotient is invariant to unitary transformation giving a proof that unitary graph convolution avoids oversmoothing\" \nOne can vaguely agree that Rayleigh quotient collapse may in some way be correlated to oversmoothing, but saying that Prop 6 \"gives a proof that unitary convolution avoids oversmoothing\" is unjustified without further proofs/details. In particular some form of a result saying that \"Rayleigh quotients do not collapse implies there is no oversmoothing\" is missing. Without this, the main claim of the paper hinges on \"vague intuition\" about RQ's and the paper is much less valuable at a theory level.\n\n6) Definition 6 (dynamical isometry): what iis the connection of this definition with the definitions from section 3.1? This part on dynamical isometry is at present very weakly (if at all) connected to the core of the paper, and I did not understand how the authors are linking it to the main definitions. See question 3 related to this.\n\n7) The experiments show performance on some benchmarks, but I would have been more convinced if the unitary convolution proposed method would have been compared to other simpler normalization methods which have similar effects on oversmoothing and gradient vanishing/explosion.", "limitations": "Main limitations are already included in the \"questions\" section, esp questions 3,5,7.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The use of unitary constraints is a sound idea for use in GNNs, in principle. \nEdit after rebuttal: It is also a novel idea, different than usual normalizations and ensuring higher nondegeneracy.\n\nThe explanations are clear and the paper is mostly well written (see \"questions\" part for some possible doubts).", "weaknesses": "Edit: after rebuttal, the main issue of originality is 100% solved, and the points in questions 3 and 5 are fully solved. The authors have proposed better experiments. This makes my concern in high part mute, the only small (and out of the scope of this work) point is that it will be great to see more verifications of oversmoothing control of beyond the (already convincing) Rayleigh Quotients preservation, which is proved in the work. As said above, this is for future work, and requires much more space, so the paper is very strong as is.\n---------------------------\n\nThe originality of this approach is a bit limited, since normalizing message passing is not a very novel idea. \nDoing it with unitary constraints has not been explored before for GNNs. It has been explored in other settings though.\n\nThe mathematical setup is sketchy at times, it needs better care. In particular, it is not clear if the proposed convolution is really a unitary operation (see question 3 and the crucial question 5 in \"questions\" section, especially).\n\nThe experiments show that normalizing is a good idea, but they don't fully convince that unitary constraints is the best way to normalize, since comparisons are done mainly against non-normalized GNNs. One has the impression that this is mainly a first exploration of a theme, and it would need more careful benchmarking, since the computational cost for implementing this particular normalization is not always negligible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions. As an overall point, the reviewer made many comments about normalized convolution which we were unsure of the specific message. We kindly ask the reviewer to clarify.\n___\n> The originality of this approach is a bit limited, since normalizing message passing is not a very novel idea. Doing it with unitary constraints has not been explored before for GNNs.\n\nUnitary layers normalize the 2-norm, but we politely disagree that they are simply a type of normalization as they also guarantee invertibility, lack of oversmoothing, stable Jacobian, etc. \n\n> What's the relative benefit compared to more naive normalizations?\n\nAs stated above, we are not sure what a \"naive normalization\" is referring to. We believe this may refer to other interventions listed below. We stress that that unitary layers are not competing with these, but complement them: any architecture can be implemented in tandem with such techniques.\n\n1. **batch norm**: batch norm helps normalize layer outputs, but does not have useful properties of unitary layers listed above, e.g. vanishing/exploding gradients, over-smoothing, and stability.\n2. **regularizers and feature adjustments**: There are methods to constrain, regularize or adjust features or layer outputs to make neighboring feature vectors more dissimilar and mitigate oversmoothing. These include Dirichlet energy constraints (e.g. Zhou et al. Dirichlet energy constrained learning...), Pairnorm (Yang et al. Pairnorm...), and others. These may help over vanilla methods in addressing oversmoothing though their benefit is arguably limited -- see survey of [RBM23] and comments below. \n3. **normalizing adjacency matrix**: One typically normalizes adjacency matrices by multiplying it by $D^{-1/2}AD^{-1/2}$ where $D$ is a diagonal matrix with $i$-th entry as the degree of node $i$. This is by default used in message passing architectures, and we use it too. This to us is a separate topic from how to perform message passing on an adjacency matrix.\n4. **residual connections**: Though not a type of normalization, residual connections have been proposed to help avoid oversmoothing. We experimentally compare to this intervention in our experiments and also give a theoretical argument for why residual connections alone can only alleviate the problem (see Proposition 4). \n\nFor more detail, consider a concurrent paper [SWJS24] using feature normalizations and residual connections. They have weaker empirical results on datasets such as Mutag and Proteins with their normalization, GraphNorm, and residual connections. We can include more details if this is what the reviewer means by \"naive normalization\".\n\n___\n**Other questions/concerns:**\n\n\n> if [instabilities with depth] is widely observed, please indicate a few references where this was observed?\n\nInstabilities come in various forms and have inspired various architectectural changes, including for CNNs and GNNs (see related work). We have also included some examples. Figure 4 in the appendix shows an example of instabilities with increasing depth for several message-passing GNNs. The attached one page response also shows this issue with vanishing/exploding gradients.\n\n\n> \"linear convolution\" -- as opposed to what other kind? isn't convolution always linear?\n\nLinear here is linearity in the input $x$. Some convolutions are not of this form, e.g. steerable convolution acts over a set of potentially nonlinear filters. \n\n> \"When W contains only real-valued entries, the above returns an orthogonal map\" -- I don't follow this, why is that? this statement would require a proof, and in general it is false... $\\exp(g_{conv})(X)\\neq e^{A} X e^{W^*}$ in this case.\n\nWe think there is a simple misunderstanding. This fact is true for the simple reason that $\\exp(W)$  is real-valued whenever $W$ is real-valued (the exponential map cannot return complex numbers when its input is real-valued). So the output is always orthogonal provided $W$ meets the Lie algebra criteria of eq. (7), namely $W+W^T=0$. \nWe also do not claim that $\\exp(g_{conv})(X)=e^{A} X e^{W^*}$. In general, it will not take this tensor product form. Perhaps the reviewer can clarify further their concern?\n\n> I don't see what's the importance / relevance of examples 1 and 2 from Section 3. I think these are standard examples, they can be skipped or moved to the appendix.\n\nPlease see general response. We will shorten section 3.2 by moving the discussion of the Fourier/spectral based methods to the appendix. \n\n\n> Saying that Prop 6 \"gives a proof that unitary convolution avoids oversmoothing\" is unjustified without further proofs/details... \n\nWe will be more precise stating that UniConv provably avoids oversmoothing as measured by the Rayleigh Quotient or Dirichlet Energy, but we push back that this is simply \"vague intuition\". The Rayleigh quotient is a widespread measure of oversmoothing (see references below). Beyond this, unitary message passing is invertible and isometric, two properties that ensure signals always propogate through a network without getting \"lost\". \n\n\n> [vanishing/exploding gradients and dynamical isometry]: what is the connection of this definition with the definitions from section 3.1? \n\nDue to lack of space available here, please see response to reviewer vJVB asking the same question. \n\n&nbsp;\n\n**References**:  \n[AL24] Roth, Andreas, and Thomas Liebig. Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks. PMLR, 2024. \\\n[RBM23] T Konstantin Rusch et al. A survey on oversmoothing in graph neural networks. arXiv:2303.10993, 2023 \\\n[RCR+22] T. Konstantin Rusch et al. Graph-coupled oscillator networks. PMLR, 2022. \\\n[SWJS24] Scholkemper, Michael, et al. \"Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs.\" arXiv preprint arXiv:2406.02997 (2024). \\\n[WAWJ24] Wu, Xinyi et al. \"Demystifying oversmoothing in attention-based graph neural networks.\" NeurIPS (2024).", "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": "hobE43IRxm", "reviewer": "Reviewer_9k9v", "summary": "The paper introduces two unitary graph convolution operators (UniConv and Lie UniConv), and studies their performance and ability to avoid over-smoothing even in deep Graph Neural Networks. UniConv (short for separable unitary convolution) takes the form f_{Uconv} = exp(iAt)XU (with A the adjacency matrix, i the imaginary unity, and U a unitary operator), while Lie UniConv (short for Lie Unitary Convolution) is defined as f_{Uconv} = exp(g_conv)(X) (with g_conv(X)=AXW, and W a skew-symmetric matrix). In both cases, the exponential map is approximated with a truncated Taylor series to contain complexity and avoid any form of eigen-decompositon. In experimental evaluation, GNNs implemented with UniConv achieved good performance on a variety of real-world datasets, while Lie UniConv was the only model to succeed in a toy example exhibiting long-range dependencies when compared to classic GNNs (such as GCN, GAT and Residual GCN).", "questions": "See Weaknesses", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper is generally well written and with a good introduction exhibiting the oversmoothing effect that one can observe with a classic GCN approach, and how the proposed unitary convolution can avoid that. In terms of the presentation of the methods, I didn’t have particular difficulties following the general idea of the authors, although there are some items I need to clarify with them (please see below in the weaknesses of the paper). Experiments appear overall good (though with some limitations on the Lie Uniconv method), with UniConv achieving good performance on a variety of benchmarks (including datasets showing long range dependencies and heterophilic graphs).", "weaknesses": "While I generally appreciated the paper (hence my slightly positive score), I’m not fully convinced by the Lie UniConv approach. The authors propose the two methods I highlighted above as a solution to avoid overfitting. As overfitting is caused by a contraction of all frequencies associated to all but the lowest frequency of the Laplace operator, converting the adjacency matrix of the provided graph into a unitary operator (as it is done in UniConv) makes sense to avoid the issue (as all eigenvalues of the obtained diffusion operator now have norm equal to 1). However, the Lie UniConv approach doesn’t go in that direction, but rather applies an exponential map on operator g_conv to obtain an orthogonal map. In this case, why the exponential of such operator is an orthogonal map is not specified in the paper, and I struggle to understand the rationale behind this approach. In this direction, in the experimental evaluation of the paper, I didn’t see any result using Lie Uniconv besides the experiment of the synthetic long rage benchmark I highlighted above. On top to this, on such benchmark, UniConv is not applied in the paper. If this was achieving comparable, or even superior, results to Lie Uniconv, then there would not be any result in the paper showing the benefit of using the Lie Uniconv method.\n\nI would kindly ask the authors if they could clarify my doubts above, and present additional results with Lie Uniconv in the rebuttal (unless I missed them somehow in the paper).\n\nIn addition to this, I would like to point out that the results presented in Table 2 are incomplete, and while the proposed Uniconv outperforms the reported methods, it is possible to see better performing solutions on Roman E in “A critical look at the evaluation of gnns under heterophily: Are we really making progress?”. I would thus ask the authors to report all the relevant results from the paper, to ensure a fair comparison.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and for their insightful questions. We have conducted additional experiments to answer the reviewers' main questions and will also amend the manuscript accordingly. We respond to individual points below.\n\n&nbsp;\n___\n\n> While I generally appreciated the paper (hence my slightly positive score), I’m not fully convinced by the Lie UniConv approach. The authors propose the two methods I highlighted above as a solution to avoid overfitting. As overfitting is caused by a contraction of all frequencies associated to all but the lowest frequency of the Laplace operator, converting the adjacency matrix of the provided graph into a unitary operator (as it is done in UniConv) makes sense to avoid the issue (as all eigenvalues of the obtained diffusion operator now have norm equal to 1).\n\nThis is a neat perspective on the UniConv operator that we appreciate you highlighting. Indeed, one can view this as replacing standard graph convolution which is a dissipative process with a unitary one.\n\nLet us now address the point about Lie UniConv. To continue, you write:\n> However, the Lie UniConv approach doesn’t go in that direction, but rather applies an exponential map on operator g_conv to obtain an orthogonal map. In this case, why the exponential of such operator is an orthogonal map is not specified in the paper, and I struggle to understand the rationale behind this approach.\n\nWe believe there are two points here that need clarifying. \n\nFirst, we want to clarify what we think is a simple misunderstanding. The operator $g_{conv}$ is a linear map which lies in the Lie algebra of the orthogonal/unitary group. The matrix exponential maps from the Lie algebra to its Lie group, so the exponential map of this operator will be unitary/orthogonal meaning that $\\|g_{conv}(X)\\| = \\|X\\|$ and $g_{conv}$ is invertible. One can easily check that enforcing $W + W^\\dagger=0$ enforces that the map $g_{conv}$ is in the Lie algebra. \n\nSecond, there is a question about the rationale. In practice, Lie UniConv and UniConv are both unitary, but the UniConv operator acts as a tensor product $\\exp(iA)\\otimes W$ whereas $\\exp(g_{conv})$ cannot be written in this tensor product form. The reason we separate these two is because in practice one may only want to change the message passing to be unitary leaving the feature transformation acting as before. Also, the tensor product structure makes implementation faster as one can apply feature transformation and message passing separately in sequence. Remark 2 aims to highlight these points, which we will make clearer in the revised manuscript. To return to your intuition from earlier, both of these will act as diffusion operators that are unitary. The sole difference is in how one wants to transform the feature space of the nodes. For example, one may use Lie UniConv in situations where the 'magnitude' of message passing depends on the features.\n\nWe also refer the reviewer to the overall response to all reviewers for additional details about this. Since this was also a point of confusion for another reviewer, we will clarify this further in the paper (see overall response for specifics).\n\n&nbsp;\n___\n> I didn’t see any result using Lie Uniconv besides the experiment of the synthetic long rage benchmark I highlighted above. On top to this, on such benchmark, UniConv is not applied in the paper. If this was achieving comparable, or even superior, results to Lie Uniconv, then there would not be any result in the paper showing the benefit of using the Lie Uniconv method.\n\nWe thank the reviewer for sharing this feedback which was also shared by other reviewers. There are now a number of updates for this (see overall response with attached pdf). We have added a table comparing Lie UniConv to UniConv on the Peptides and TU datasets including a split for whether one parameterizes in the orthogonal or unitary group. UniConv performs slightly better though the differences are minor. Furthermore, we include a figure showing that Lie UniConv and UniConv are both equally capable of learning the toy model task. \n\nIn practice, the differences between the two methods can be hard to discern. In real-world experiments, we often find that UniConv often performs slightly better since it addresses oversmoothing issues in the message passing leaving feature transformations unconstrained. Please see the overall response for more details.\n\n> I would kindly ask the authors if they could clarify my doubts above, and present additional results with Lie Uniconv in the rebuttal (unless I missed them somehow in the paper).\n\nPlease see prior response. We would be happy to answer any additional questions or perform additional experiments that could help clarify the contributions of our paper.\n\n&nbsp;\n___\n> In addition to this, I would like to point out that the results presented in Table 2 are incomplete, and while the proposed Uniconv outperforms the reported methods, it is possible to see better performing solutions on Roman E in “A critical look at the evaluation of gnns under heterophily: Are we really making progress?”.\n\nThe reviewer is correct in that there are models in “A critical look at the evaluation of gnns under heterophily: Are we really making progress?” that perform better, for example on the Roman Empire dataset. However, these methodologies use different embeddings in their pre-processing. As noted in Appendix F under 'Heterophilous Graph Datasets', *\"we do not separate ego- and neighbor-embeddings, and hence also do not report accuracies for models from the original paper that used this pre-processing (e.g. GAT-sep and GT-sep)\"*.", "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:
We thank all the reviewers for their insightful comments, recommendations, and feedback. 

&nbsp;

There were some common themes in the reviews which we want to address in an overall response here. We have also included a one page pdf containing plots and tables which help address reviewers' concerns.

 1. **Lie UniConv experiments:**
Reviewers requested additional experiments comparing Lie UniConv to UniConv. We originally did not include these as they performed similarly, and apologize for the oversight. We include in the one page pdf experiments comparing Lie UniConv and UniConv (both with real-valued orthogonal and complex-valued orthogonal/unitary matrices) for the Peptides experiments and TU datasets. Overall, performance is very similar for Lie UniConv and UniConv. 
We also include a figure showing that UniConv and Lie UniConv are equally effective at learning the toy model task of graph distance.
All results will be included in the revised version of the paper.

2. **Vanishing/exploding gradients:**
Reviewers vJVH and EVha questioned the relevance and importance of vanishing/exploding gradients. In response, we have included a simple plot showing vanilla GCNs are no different than other deep networks and can suffer from this issue. This plot also shows unitary GCNs avoid this issue. This plot was created using standard initialization and settings of the graph convolution layer in pytorch Geometric. Of course, vanishing/exploding gradients are a common problem accross deep networks of all kinds, and unitary layers are not the only way to help alleviate this problem. 

3. **Generalized and Fourier basis convolution:**
Section 3.2 generalizes unitary graph convolution to convolution over arbitrary finite groups and in the Fourier/spectral basis. While we believe that this more general perspective is instructive to the reader in that it gives background on other attempts at unitary/orthogonal convolution, we agree that the discussion of the Fourier/spectral based methods in the main paper distracts from the main contributions of the paper.
Based on your detailed comments and feedback, we have decided to make the following changes to the presentation: We will defer the description of Fourier/spectral basis convolution to the appendix and include a richer background into representation theory to make it more accessible to the reader. We will shorten the discussion in the main text to a paragraph to informally present potential advantages of implementation in the Fourier domain and note that we did not implement this in our work. These changes will give us space to include additional experimental results for Lie UniConv.

&nbsp;

***Please see attached one page pdf with additional tables and plots below.***

Meta-review: This paper introduces unitary convolutional layers for Graph Neural Networks (GNNs), with the primary aim of mitigating issues like gradient collapse, explosion, and over-smoothing in GNNs. The experimental results demonstrate that these layers can effectively aggregate information across long distances and achieve strong performance on real-world benchmarks.

The paper was well received by the reviewers, who appreciated the formalism and theoretical analysis of the proposed operators. The initial scores generally improved after the authors' rebuttal, which clarified some misunderstandings and provided additional experimental results.

The main limitation pointed out by the reviewers concerns the writing and organization of the paper. This is the main reason for the “borderline reject” score from one of the reviewers, who, however, decided to lower his confidence score. The authors have proposed addressing these issues with revisions that should be applied in the camera-ready version. Additionally, the introduction of two unitary convolution operators caused some confusion, and the authors should better motivate their inclusion.
Decision: Accept (spotlight)