HoloNets: Spectral Convolutions do extend to Directed Graphs

We sincerely thank the reviewer for the careful consideration of our paper! We were especially happy to read the sentiments that

the usage of holomorphic functional calculus to introduce directed graph filters is novel,

that our

theoretical analysis seems sound

and our

proposed method seems effective and expressive.

Let us adress the raised points individually below:

• The formulation seems to be restricted to one-dimensional node weights for the nodes, but it is not clear what modifications should be made if we are given multiple-dimensional node features.

Channel mixing in spectral graph networks is implemented in analogy to the Euclidean case: A Euclidean convolutional filter applied to an image acts only on a single (r, g or b)-channel. Channel mixing is then facilitated by connecting all channels in two consecutive layers via convolutional filters. All incoming information at a given channel is then summed up. A convenient visual representation may e.g. be found in Figure 2 of (Koke (2023)) .

Our method follows this paradigm. This might for example be explicitly seen in the layer update rule in Section 4: As described there, the weight matrices $W_k^{\text{fwd/bwd},\ell+1}$ are of dimension $F_{\ell}\times F_{\ell+1}$, with $F_{\ell}, F_{\ell+1}$ the feature dimensions of the respective layers. These matrices implement the contact between different channels.

• "The underlying reason for using holomorphic functional calculus has not been clearly demonstrated."

The guiding principle behind modern spectral convolutional methods is that of designing filters of the form $g(T)$, with $T$ a characteristic operator and $g$ a learnable (scalar) function (Defferrard et. al (2016)). In the undirected setting, we had $T = T^*$, which – as we detail in Sections 1 through 3 – allows to unambiguously evaluate the scalar function $g$ on the matrix $T$ by essentially evaluating $g$ on each eigenvalue of $T$ independently.

As we detail in Sections 2 and 3, this is no longer possible in the directed setting; instead the only way to consistently define the matrix $g(T)$ is to make use of the holomorphic functional calculus.

Following this concern raised by the reviewer, we have modified the corresponding discussion of this matter in Section 3.1, to reflect even more strongly that $g(T)$ may only be consistently defined if $g$ is assumed to be holomorphic.

If the reviewer would however like us to incorporate additional specific comments on this matter, we would be more than happy to do so.

• "Some typos exist. "

We are very grateful to the reviewer spotting these typos! We have dilligenly fixed them all in the updated version of our manuscript.

• "What is the computational complexity of HoloNets compared to DiGCN, MagNet, and Dir-GNN?"

For definiteness, we will assume the DirGCN configuration of the DirGNN baseline (other configurations would yield higher complexity). For a given graph $G$, let $N$ denote its number of nodes and let $E$ denote its number of edges. Assume we have input features of dimension $C$ and a $F$ hidden dimensions in our architectures.

DiGCN: In its full form, DiGCN has a $\mathcal{O}(N^2)$ complexity, which is reduced to a $\mathcal{O}(EFC)$ complexity in its approximate propagation scheme, which is used in practice.

DirGNN: Similarly, DirGNN possesses a $\mathcal{O}(EFC)$. In both cases this stems from the sparse-dense matrix multiplications that facilitate the forward function.

MagNet: MagNet is similarly implemented via sparse-dense matrix multiplications; resulting in an $\mathcal{O}(EFC)$-complexity.

FaberNet: Since FaberNet too implements its forward using sparse-dense matrix multiplications, its filtering operation also has $\mathcal{O}(EFC)$ complexity.

Dir-ResolvNet: The filtering operation in Dir-ResolvNet is implemented as dense-dense matrix multiplication, and as such has complexity $\mathcal{O}(N^2)$ like the full (not approximated) forward operation of DiGCN would have.

Following this question, we have also included this discussion in a new section (Section I.3: Efficiency Analysis) in our updated manuscript.

We would like to sincerely thank the reviewer for the careful evaluation of our paper and appreciation of our results. We were especially happy to read that

the paper is well written and easy to follow,

“novel and has theoretical depth and is

ready for publication at NeurIPS.

Let us address the raised points individually:

• It would be good to examine the efficiency of the proposed method, especially when compared with DiGCN and DirGNN.

We are very happy to do so:

For definiteness, we will assume the DirGCN configuration of the DirGNN baseline (other configurations would yield higher baseline-complexity). For a given graph $G$, let $N$ denote its number of nodes and let $E$ denote its number of edges. Assume we have input features of dimension $C$ and $F$ hidden dimensions in each layer of our architectures.

DiGCN: In its full form, DiGCN has a $\mathcal{O}(N^2)$ complexity, which is reduced to a $\mathcal{O}(EFC)$ complexity in its approximate propagation scheme, which is used in practice.

DirGNN: Similarly, DirGNN possesses a $\mathcal{O}(EFC)$ complexity. In both cases this stems from the sparse-dense matrix multiplications that facilitate the forward process.

FaberNet: Since FaberNet too implements its forward using sparse-dense matrix multiplications, its filtering operation also has $\mathcal{O}(EFC)$ complexity.

Dir-ResolvNet: The filtering operation in Dir-ResolvNet is implemented as dense-dense matrix multiplication, and as such has complexity $\mathcal{O}(N^2)$ like the full (not approximated) forward operation of DiGCN would have.

Following this point raised by the reviewer, we have now included this discussion into a new subsection titled “Efficiency Analysis” in "Appendix I: Additional Details on Experiments” in our revised manuscript.

• "Moreover, a discussion on the number of learnable parameters would be beneficial."

Compared to DirGNN (in its DirGCN Setting) and assuming the same network width and depth, our FaberNet has $K$ times the number of learnable parameters in the real setting. In the complex setting, our method has $2\cdot K$ as many real parameters as DirGNN. Here $K$ refers to the highest utilized order of Faber polynomials $\Psi_k$. In our experiments, the maximal attained value of $K$ was $K = 5$ on the “Squirrel” dataset. On this dataset, complex weights and biases performed best, so that our method has 6.3 M trainable parameters in the corresponding utilized hyperparameter-configuration for Squirrel (detailed in Appendix I).

We have included this discussion above into the newly created subsection titled “Efficiency Analysis” in "Appendix I: Additional Details on Experiments” in our revised manuscript.

Thank you for addressing my questions. I believe it's a good paper and vote for acceptance.

We would like to sincerely thank the reviewer for the careful consideration of our paper! We were especially happy to read that we

give sufficient justifications to verify the advantages of holomorphic functions, convincing [the reviewer] about their effectiveness”

and it was appreciated by the reviewer that our approach

consistently outperforms other directed GNNs in both heterophilic node classification and regression tasks”.

Let us address the raised points individually below:

• "Results in Table 1 show that the performance of MagNet is far way from FaberNet. I guess that this is because MagNet operates as a low-pass filter and therefore cannot perform well in the heterophilic datasets."

We personally do not believe that the observed performance gap necessarily arises because MagNet operates as a low pass filter:

In standard graph convolutional architectures, the effect of (low-pass) Laplacian smoothing indeed makes node representations more and more similar as a signal is propagated through the layers (c.f. e.g. [1]). This is then especially bad in the heterophilic setting, where node-labels of a given node and those of its neighbourhood differ.

Mathematically, Laplacian smoothing can be understood as mapping an original feature matrix $X$ to its smoothed version $X \mapsto e^{-\Delta \cdot t}\cdot X$. Here $\Delta$ denotes a suitable graph Laplacian and the continuous time $t$ is replaced by the layer-depth $\ell$ when discussing the low-pass behaviour of GNNs. Smoothing now occurs, bevause the function $\lambda \mapsto e^{-\lambda\cdot t}$ suppresses all non-zero eigenvalues $\lambda$.

For large times ($t \gg 1$) or respectively deep architectures, the only information that survives is that corresponding to the $\lambda = 0$ eigenvalue. Since the corresponding eigenvector is (up to normalisation) simply given as $v_0^T = (1,…,1)^T$, this means that only a graph-average $v_0^T\cdot X$ of all the available information $X$ survives.

The story is however different when the magnetic Laplacian $\Delta_q$ as in the MagNet Paper is considered: Generically, this Laplacian does not have $0$ as an eigenvalue if $q \neq 0$. ((To be exactly precise, $0$ is an element of the spectrum $\sigma(\Delta_q)$ if and only if the magnetic potential that gives rise to $\Delta_q$ is gauge-equivalent to the trivial potential; c.f. e.g. [2].)) Since $0$ is (generically) not an eigenvalue of $\Delta_q$, we have that $e^{-\Delta_q\cdot t}$ does not (generically) converge to a graph average, when $t$ (respectively the layer-depth) is increased. This makes us question, whether the MagNet architecture really acts as a low-pass filter.

Our interpretation of the performance gap between MagNet and FaberNet is a different one:

The operator on which MagNet is based, is the magnetic Laplacian $\Delta_q$. Up to magnetic modifications and normalization, this operator is of the form $D – A$, with $D$ the degree matrix and $A$ the adjacency matrix. Applying this operator to the feature matrix $X$, thus essentially compares the local feature of a given node (retained via $D$) with the features of all surrounding nodes (aggregated via $A$).

As was remarked in "Improving Graph Neural Networks with Simple Architecture Design” (i.e. “Maurya et al., 2021” in our Bibliography) the following holds:

Under homophily, nodes are assumed to have neighbors with similar features and labels. Thus, the cumulative aggregation of node’s self-features with that of neighbors reinforce the signal corresponding to the label and help to improve accuracy of the predictions. While in the case of heterophily, nodes are assumed to have dissimilar features and labels. In this case, the cumulative aggregation will reduce the signal and add more noise causing neural network to learn poorly and causing drop in performance. Thus it is essential to have node’s self-features separate from the neighbor’s features.

To avoid comparing the features of surrounding nodes with the feature vector of a given node our architecture is based on (a modified version of) only the adjacency matrix $A$ (instead of a Laplacian $\sim D - A$).
The adjacency matrix has only the entry $0$ on the diagonal. Thus, when updating the feature vector of a given node, the previous feature vector of this node is discarded, and the new feature vector is solely made up of information about surrounding nodes (i.e. information about the neighbourhood(structure) of the original node). This avoids mixing and comparing self-features with neighbourhood features. This is beneficial in the heterophilic setting, as (Maurya et al., 2021) pointed out theoretically, and we also observed empirically.

We would like to sincerely thank the reviewer for the careful review of our paper! We were especially happy to read that

the technical insights shown in this paper are great and very interesting

and that

[our paper] lay[s] the theoretical foundations for other future works on [convolutional kernels for directed graphs].

Let us address raised points individually:

• "Although the technical insights shown in this paper are great and very interesting, [...] the implementation of the practical directed convolutional kernels (layers), should still be explained clearly in detail."

We agree that our paper is written to serve a dual purpose: To --on the one hand-- develop the theory of spectral convolutions on directed graphs in detail so that it may be taken up by the community for further research and on the other hand to establish our own specific architectures conforming to the developed framework.

Following this advice by the reviewer, we have now put additional emphasis on introducing and describing our specific architectures in more detail, as we explain below.

• "For example, after reading the entire paper, I still do not know if we need to perform the eigendecomposition of the graph operator or not."

We thank the reviewer for this important and indeed central question. The answer is that an explicit eigendecomposition (or in fact a Jordan Chevalley decomposition in the directed setting) NEVER needs to be computed in our approach.

Following this question by the reviewer, we have now modified the final paragraph of the corresponding Section 3.2 in our updated manuscript. It now reads:

“For us, the spectral response (4) provides guidance when considering scale-insensitive convolutional filters on directed graphs in Sections 3.3 and 4 below. The spectral response (4) is however never used to implement filters: As discussed above, this is achieved much more economically via (3).”

• "[...] if we set the function to be faber polynomials $\Psi_k(\lambda) = \lambda^k/2^k$, what will $\Psi_k(T)$ in this case, where $T$ is the operator? "

If we have $\Psi_k(\lambda) = \lambda^k/2^k$ then we exactly have

$\Psi_k(T) = \frac{1}{2^k}T^k.$

We had initially discussed this effect of applying the holomorphic functional calculus to monomials and polynomials at the end of Section 3.1. Following this valid point raised by the reviewer, we have -- for additional clarity -- promoted said discussion at the end of Section 3.1 into a Theorem (namely Theorem 3.1 in our updated manuscript) into its own right for heightened visibility.

Additionally, we now also explicitly provide the above result of applying the Faber polynomial $\Psi_k(\lambda)$ to the operator $T$ already in Section 3.3.1 (i.e. precisely when Faber Polynomials are first introduced).

• "Do we still have to consult Eq (3) to compute $\Psi_k(T)$, which can be computationally expensive? "

The answer to this question is a resounding NO:

Equation (3) never needs to be used to implement a filter in practice. The purpose of this equation is instead to serve as a theoretical tool to spectrally interpret the action of given filters. Additionally it provides guidance on the choice of suitable filters adapted to a given task.

To avoid a costly explicit Jordan-Chevalley decomposition, our model instead uses parametrized spectral convolutional filters, which were introduced and discussed in the first paragraph of Section 3.4.

This is indeed an important point brought up by the reviewer, and – as already mentioned above – we now explicitly state the following in our revised manuscript [Note that equation (4) in the revised document refers to equation (3) in the original submission]:

“For us, the spectral response (4) provides guidance when considering scale-insensitive convolutional filters on directed graphs in Sections 3.3 and 4 below. The spectral response (4) is however never used to implement filters: As discussed above, this is achieved much more economically via (3).”.

• "This type of question [as above] should be clearly explained in the main text to help readers better understand the big picture."

We hope that the provided modifications in our updated manuscript have clarified these points. Should this not yet be the case, we will of course be more that happy to act on any additional feedback.

• "pseudocode of the algorithm/training procedure can help solve this issue."

Apart from the aforementioned added and modified discussions, we have also included a pseudocode of the forward of our model in our revised manuscript (c.f. Appendix J) which we reference in the main text of our revised manuscript.

• "What is the choice of $y$ for Dir-ResolvNet?

We have chosen $y = -1$ for simplicity. We had already detailed this in “Appendix I: Additional Details on Experiments”, but have now also included this in the main text of our paper in our revised manuscript.

• "Where do the imaginary weights in FaberNet come from? Is it because the eigenvalues can be complex?"

Yes, that can indeed be thought of as the underlying reason.

In more detail: If the underlying graph is directed, the associated characteristic operators $T$ are generically not self-adjoint. Hence eigenvalues of such operators are generically complex. If one intends to apply a function $g$ to such a matrix $T$, this necessitates $g$ to be defined at least in a neighbourhood of each eigenvalue of $T$, as can e.g. be seen from the spectral response discussed in the paper. Thus $g(z)$ needs to be defined for complex $z$. If one represents such a function via simpler functions (e.g. a polynomial $g(z)$ represented via a sum of monomials $z^k$ as $g(z) = \sum_k a_k z^k$ ), the corresponding coefficients $a_k$ are generically complex. These coefficients precisely constitute the learnable parameters in our method.

References:

[1]: Michael Perlmutter, Feng Gao, Guy Wolf, and Matthew Hirn. Understanding graph neural networks with asymmetric geometric scattering transforms, 2019. URL https://arxiv.org/abs/1911.06253.

[2]: Christian Koke and Gitta Kutyniok. Graph scattering beyond wavelet shackles. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2020, November 28 - December 9, 2022, New Orleans. OpenReview.net, 2023. URL https://openreview.net/forum?id=ptUZl8xDMMN.

[3]: ChiYan Lee, Hideyuki Hasegawa, and Shangce Gao. Complex-valued neural networks: A comprehensive survey. IEEE/CAA Journal of Automatica Sinica, 9(8):1406–1426, 2022. doi:10.1109/JAS.2022.105743.

2. Why is the normalization chosen as $D^{-frac14}$ as opposed to $D^{-frac12}$ ?

It is indeed true that a symmetric normalization by $D^{-frac12}$ is traditional in the undirected setting. Historically, this can be traced back to the utilization of the symmetrically normalized Laplacian as providing the Fourier-atoms (i.e. the Laplacian eigenvectors) of the graph Fourier Transform that underlies e.g. the original undirected spectral models such as (Bruna et al., 2014), (Defferrard et al., 2016) (Kipf & Welling, 2017) [using the nomenclature of the Bibliography of our submission].

A main point of the present paper however, is transcending this graph Fourier transform, as the traditional approach is limited to undirected graphs. Our approach instead does not need to be based on any underlying Laplacian on the graph: Indeed, the holomorphic functional calculus may be applied to arbitrary operators.

As such, a traditional holding-on-to a normalization stemming from a traditional use of a Laplacian-based Graph-Fourier transforms is no longer necessary and we want to point this out to the community. As we observed experimentally, such a traditional normalization is also (slightly) disadvantageous, as far as performance is concerned.

• "Why use absolute value as the nonlinear activation, which is unusual in GNN literature?"

It is indeed true that a large percentage of the machine learning literature in general uses some form of ReLU activations. In the graph setting, an exception is constituted by graph-scattering-networks (c.f. e.g. [1,2]): Corresponding scattering architectures are based on the absolute-value-nonlinearity.

For us, the choice to use either ReLu or the absolute value arises as our networks are potentially complex. In the complex setting there is no clear consensus which activation function performs best (c.f. e.g. [3]). Hence we consider two possible choices in our architecture, whenever we enable complex parameters (c.f.also Table 7 in Appendix I)

• "All of these choices seem to just come out of trial and error in simulations. It would be good if the authors could provide some further explanations for these choices."

We hope that we were able to clarify these points. As mentioned above, we have added corresponding discussions of the points raised by the reviewer in our revised manuscript.

• "One minor concern that I have is about the simulation of directed graph regression problems. I am not very convinced why we should treat this as a directed graph problem, and how it helps when we consider the edges to be directed and the nodes to be weighted. Maybe it has some physical/chemical meanings, but since I am not an expert in physics, I will leave this to other reviewers to decide."

Our view of this matter is as follows:

Our aim in this present paper is to establish within the graph learning community that the use of spectral methods on directed graphs is not limited to achieving state of the art performance on node-classification: HoloNets can e.g. also be used at the graph level, to construct networks that are transferable between directed graphs describing the same underlying object at different resolution scales.

While transferability is certainly an established research topic for graph neural networks, the approach via of such multiscale-consistency has only recently started to be investigated. As such standard benchmarks have not yet been established; especially not in the directed setting. We thus modify a standard dataset (i.e. QM7) that was recently used to test for multiscale-consistency in the undirected setting (c.f. Koke et al. (2023)) in order to test for such consistency in the directed setting.

Whether a molecule is represented as a directed or undirected graph is irrelevant from the perspective of retained physical information: Both descriptions may be translated into each other. In either case, the node-weights arise naturally as a way to represent additive (under combining nodes) node-wise information, such as charges (like in the case at hand), particle numbers (e.g. Neutron- or Proton numbers) or masses corresponding to individual nodes/atoms.

• "I would not describe the difference between the performance of FaberNet and that of Dir-GNN to be significant, as most of the differences are within one standard deviation. Also from the implementation side, Dir-GNN is much simpler than FaberNet; "

That is a valid point. We have amended the corresponding statement about the comparison between Dir-GNN and Faber-Net in Section 5.1.

• "on page 5, "Faber polynomials provide near near mini-max polynomial approximation" there are two "near"."

We thank the reviewer for spotting this typo, which we have now correced.