Unitary convolutions for learning on graphs and groups

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).

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. 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). 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?”. I would thus ask the authors to report all the relevant results from the paper, to ensure a fair comparison.

Questions

See Weaknesses

Rating

6

Confidence

3

Soundness

2

Presentation

2

Contribution

3

Limitations

Yes

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.

Strengths

The use of unitary constraints is a sound idea for use in GNNs, in principle. Edit after rebuttal: It is also a novel idea, different than usual normalizations and ensuring higher nondegeneracy. The 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. --------------------------- 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. It has been explored in other settings though. The 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). The 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.

Questions

What's the relative benefit compared to more naive normalizations? Minor correctionsl/doubts: 1) 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? 2) line 103: "linear convolution" -- as opposed to what other kind of convolution? isn't convolution always linear? 3) line 144: the following is an important point/issue. "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. 4) 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. 5) lines 217-218: this probably the most important theory issue of the paper. "the Rayleigh quotient is invariant to unitary transformation giving a proof that unitary graph convolution avoids oversmoothing" One 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. 6) 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. 7) 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.

Rating

8

Confidence

5

Soundness

4

Presentation

3

Contribution

4

Limitations

Main limitations are already included in the "questions" section, esp questions 3,5,7.

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$).

Strengths

- Well founded mathematical formalism, defining unitarity in message passing graph neural networks in a natural way. - 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. - 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). - 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. - 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 or 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. - 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.

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? - 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)$. - 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. 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? - Line 212: is (I − A) a type of graph Laplacian? - 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?). - 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. - 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. - Line 821: missing trace on following lines and last line should not be put there ($= R_{\mathcal{G}(\mathbf{X})}$)

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors have discussed limitations of their contribution adeguatly.

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.

Strengths

- **(S1 - Novelty)** The contributions in this paper seem novel. - **(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. - **(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: - 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. - 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. - 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? - **(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. **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.

Questions

Most of my questions are already part of the weakness section. - **(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.

Rating

4

Confidence

3

Soundness

2

Presentation

1

Contribution

2

Limitations

Yes.

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.

Strengths

1. Theoretical analysis is conducted to show the effectiveness in handling oversmoothing and oversquashing issue. 2. 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. 2. The computational cost is higher compared to other methods, but there are no experimental results to show the important details.

Questions

See weakness.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A