HoloNets: Spectral Convolutions do extend to Directed Graphs
Authors: Christian Koke
Daniel Cremers
Venue: ICLR 2024 poster (2024)
Keywords: Spectral Graph Convolutions
Directed Graphs
Weighted Graphs
Complex Analysis
Spectral Graph Theory
Heterophily
Node Classification
Graph Regression pectral Graph Theory
Rigorous Proofs
Primary area: learning on graphs and other geometries & topologies
TL;DR: We extend spectral convolutions to directed graphs. Corresponding networks are shown to set SOTA on heterophilic node classification tasks and to be stable to topological perturbations.

Abstract: Within the graph learning community, conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs: Only there could the existence of a well-defined graph Fourier transform be guaranteed, so that information may be translated between spatial- and spectral domains. Here we show this traditional reliance on the graph Fourier transform to be superfluous and -- making use of certain advanced tools from  complex analysis and spectral theory -- extend spectral convolutions to directed graphs. 
We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based. In order to thoroughly test the developed  theory, we conduct experiments in real world settings, showcasing that  directed spectral convolutional networks provide new state of the art results for heterophilic node classification on many  datasets  and -- as opposed to baselines -- may be rendered stable to resolution-scale varying topological perturbations.

Published as a conference paper at ICLR 2024
HOLONETS: SPECTRAL CONVOLUTIONS DO EXTEND TO DIRECTED GRAPHS
Christian Koke & Daniel Cremers Technical University Munich and Munich Center for Machine Learning (christic fanttiann.. koke, cremers @ttumdde
ABSTRACT
Within the graph learning community, conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs: Only there could the existence of well-defined graph Fourier transform be guaranteed, so that information may be translated between spatial- and spectral domains. Here we show this traditional reliance on the graph Fourier transform to be superfluous and making use of certain advanced tools from complex analysis and spectral theory- extend spectral convolutions to directed graphs. We provide a frequency- response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based. In order to thoroughly test the developed theory, we conduct experiments in real world settings, showcasing that directed spectral convolutional networks provide new state of the art results for heterophilic node classification many datasets and opposed to baselines may be rendered stable to resolution-scale varying topological perturbations. Our code is available at htnttpss///itthb...om http::/twwww..cm..octcecaaaaaana oNet..
INTRODUCTION
particularly prominent line of research for graph neural networks is that of spectral convolutional architectures. These are among the theoretically best understood graph learning methods (Levie et al.
diverse selection of 2019a Ruiz al. 202 la Koke 2023) and continue set the state of the Furthermore, spectral
tasks (Bianchi et al. 2019 He et al. 2021 2022a; Wang & Zhang (022b).
interpretations allow better analyse expressivity (Balcilar al. (021), shed light on shortcomings of established models (NT & Maehara 2019) and guide the design of novel methods (Bo et al. 2023).
Traditionally, spectral convolutional filters are defined making use of the notion of a graph Fourier transform: Fixing self-adjoint operator on an undirected -node graph traditionally suitably normalized graph Laplacian U AU with eigenvalues transform is defined by projecting given signal x onto the eigenvectors of L via x Ur. Since I, is self-adjoint, the eigenvectors form a complete basis and no information is lost in the process.
diag A AN) - a notion of Fourier
In analogy with the Euclidean convolution theorem, early spectral networks then defined convo- lution as multiplication the Fraaph-Fourier domain" " via x + U diag(O),..., .x), Ux, with learnable parameters (O,,.... 0x (Bruna et al. 2014). To avoid calculating an expensive explicit cigendecomposition U, [effeeraard et al. (2016) proposed to instead parametrize graph convolu- tions via
U (A, with Go a learnable scalar function applied to the eigenvalues A as (o(A) diag (go (A1). go "o))....9ooA.... (A))). This precisely reproduces the mathematical definition of apply- ing a scalar function go self-adjoint operator I., so that choosing go to be (learnblee) polynomial allowed to implement filters computationally much more economically as (L) ΣK 0g Follow up works then considered the influence of the basis in which filters {go} ) are learned (He et al. 2021: Levie et al. 2019b Wang Zhang, 2022a) and established that such filters provide networks with the ability to generalize to unseen graphs (Levie et al. 2019a Ruiz et al., 2021b
Koke 2023).
Common among all these works, is the need for the underlying graph to be undirected: Only then are the corresponding operators symmetric, that complete set of orthogonal eigenvectors exists and the graph Fourier transform U (used to define the filter go (L) via x + (A)U x) is well-defined
Strietly speaking it is not symmetry (J. I, but normality (L.LT T. I.) of L that ensures this.

---

Published as a conference paper at ICLR 2024
Currently however, the graph learning community is endeavouring to finally also account for the previously neglected directionality of edges, when designing new methods (Zhang et al.) 202. Rossi
et al. 2023 Beaini et al. 2021] Geisler et al. 2023 He et al. 2022b). Since characteristic operators on digraphs are generically not self-adjoint, traditional spectral approaches so far remained inaccessible in this undertaking. Instead, works such /Zang al. (202T); He et al. (2022b) resorted to limiting themselves to certain specialized operators able to preserve self-adjointness in this directed setting. While this approach is not without merit, the traditional adherence to the graph Fourier transform remains a severely limiting factor when attempting to extend spectral networks to directed graphs.
Contributions: In this paper we argue to completely dispose with this reliance on the graph Fourier transform and instead take the concept of learnable functions applied to characteristic operators as fundamental. This conceptual shift allows us to consistently define spectral convolutional filters on directed graphs. We provide corresponding frequency perspective, analyze the interplay with chosen characteristic operators and discuss the importance of the basis used to express these novel filters. The developed theory is thoroughly tested on real world data: is found that directed spectral convolutional networks provide new state of the art results for heterophilic node classification and as opposed to baselines may be rendered stable to resolution-scal varying topological perturbations.
SIGNAL PROCESSING ON DIRECTED GRAPHS
Our work is mathematically rooted the field of graph signal processing; briefly reviewed here:
Weighted directed graphs: A directed graph G := (G, E) is collection of nodes G and edges E E G x G for which (i,j) E E does not necessarily imply (j. E E. We allow nodes e G to have individual node-weights (4 0 and generically assume edge-weights Waj > 0 not necessarily equal to unity or zero. In a social network, a node weight μ4 1 might signify that a node represents a single user, while weight μ4 > 1 would indicate that node represents a group of users. Similarly, edge weights {wyy} could be used to encode how many messages have been exchanged between nodes and j. Importantly, since we consider directed graphs, we generically have Wis * Wzi- Edge weights also determine the so called reaches of a graph, which generalize the concept of connected compo- nents of undirected graphs (Veerman & Lyons] 2020): A subgraph R = G called reach, if for any two vertices b E R there is a directed path in R along which the (di- rected) edge weights do not vanish, and R. simultancously possesses no outgoing connections (i.e. for any c G' with c& R: Wen = 0). For us, this concept will be important in generalizing the notion of scale insensitive networks (Koke)
2
Figure 1: A di-graph with reaches R1 [1,2,3) and Rs = (3, 5, 6, 2}.
ct al. 2023) to directed graphs in Section 3.3 below.
Feature spaces: Given F-dimensional node features on graph with N = | nodes, we may collect individual node-feature vectors into a feature matrix X of dimension N x F. Taking into account our node weights, we equip the space of such signals with an inner-product according to (X = Tr(X*MY) = Σm Ex of weights. Here X* denotes the (hermitian) adjoint of X (c.f. Appendix B for a brief recapitulation). Associated to this inner product is the standard 2-norm X 1 = ΣN Σ/ |
with M- = diag ((H,)) the diagonal matrix
Characteristic Operators: Information about the geometry of a graph is encapsulated into the set of edge weights, collected into the weight matrix W. From this, the diagonal in-degree and out-degree matrices (D Σ, We, Dom E, Wty) may be derived. Together with the node-weight matrix M defined above, various characteristic operators capturing the underlying geometry of the graph may then be constructed. Relevant to us- apart from the weight matrix W - wwil especially be the (in-degree) Laplacian 7 := M -Dii W). which is intimately related to consensus and diffusion on directed graphs (Veerman & Kummel 2019). Importantly, such characteristic operators T are generically not self-adjoint. Hence they do not admit a complete set of orthogonal eigenvectors and their spectrum (T)) contains complex eigenvalues À E C. Appendix contains additional details on such operators, their canonical (Jordan) decomposition and associated generalized eigenvectors.
2

---

Published as a conference paper at ICLR 2024
3 SPECTRAL CONVOLUTIONS ON DIRECTED GRAPHS
Since characteristic operators on directed graphs generically do not admit complete set of orthogonal eigenvectors, we cannot make use of the notion of graph Fourier transform to consistently define filters of the form (T))). While this might initially seem to constitute an insurmountable obstacle, the task of defining operators of the form (()) for a given operator T and appropriate classes of balar-valued functions (g) such that relations between the functions {o) translate into according
relation of the operators (g())) - is in fact a well studied problem (Haase) 2006) Colombo et al. 2011). Corresponding techniques typically bear the name "functional calculus' and importantly are also definable if the underlying operator T is not self-adjoint (Cowling et al. 1996):
3.1 THE HOLOMORPHIC FUNCTIONAL CALCULUS
In the undirected setting, was possible to essentially apply arbitrary functions {g} to the characteris- tic operator T' = U AU by making use of the complete cigendecomposition (T)) := U go (A)U,. However, a different approach to consistently defining the matrix g(") not contingent on such a decomposition is available if (and only if) restricts g to be holomorphic function: For given subset U of the complex plane, these are the complex valued functions U C for which the complex derivative dg(=)) (0)()//el)) dz exists everywhere
the domain U (c.f. Appendix D for more details).
The property of holomorphic functions that allows to consistently define the matrix (T) is the fact that any function value g(A) can be reproduced by calculating an integral of the function g along path T encircling À (c.f. also Fig. 2 as
f g(2) g(2)) 2
1
.(A)
(2-2) 22-
(1)
Figure 2: Cauchy Integral I
Here "dz" denotes the complex lineintegration-measure in C. In order define the matrix g()), the formal replacement À - T is then made on both sides of (1). with the path now not only encircling single value À but all eigenvalues X a(T) (c.f. also Fig. 3
1
g(T) = 2ti g()) (T - Id) dz
(2)
Note that 2- Id) and hence the integral in 2 is indeed well-defined: All eigenvalues of T are assumed to lie inside the path I. For any choice of integration variable on this path I' the matrix (T - z Id) is thus indeed invertible, since is never an eigenvalue. Figure 3: Operator Integral
The integral in 2 defines what is called the holomorphic functional calculus (Gindler) 1966 Kato 1976). Importantly (c.f. Appendix the definition of g(T) in (2) agrees with algebraic relations:
Theorem 3.1. Applying a polynomial g = Σ a T yields g(T) Σ ag Th Simi-
larly applying the function g( 1/A yields g(T) T-1 provided T is invertible.
3.2 SPECTRAL CONVOLUTIONAL FILTERS ON DIRECTED GRAPHS
Since the holomorphic functional caleulus evidently longer contingent on T being self-adjoint, it indeed provides an avenue to consistently define spectral convolutional filters on directed graphs.
Parametrized spectral convolutional filters: In practice it is of course prohibitively expensive to
continuously compute the integral (2) the learnable function g is updated during training. Instead, we propose to represent a generic holomorphic function via a set of basis functions { as go(2) := = 0, V (2) with learnable coefficients {0t] ier parametrizing the filter 9o-
For the 'simpler' basis functions (Vithe we either precompute the integral 2 or perform it analytically (c.f. Section 3.3 below). During training and inference the matrices (T(T)
2mi f.. 12(2)) (T- - 2 Id) de are then already computed and learnable filters are given as
(T) = Σ 0, (T).
(3)
ief
3

---

Published as a conference paper at ICLR 2024
Generically, each coefficient 8, may be chosen a complex number; equivalent two real parameters. If the functions { 1 Wek are chosen such that each matrix (T) contains only real entries (e.g. for v/ a polynomial with real coefficients), it is possible to restrict convolutional filters to being purely real: In this setting, choosing the parameters (0:] to be purely real as well, leads to (T) Eier 0, V (.(T)) itself being a matrix that contains only real entries. In this way, complex numbers need never to appear within our network, if this is not desired. In Theorem [f Section [below, we discuss how, under mild and reasonable assumptions, such complexity-redee can be performed without decreasing the expressive power of corresponding networks.
to using only real parameters
Irrespective of whether real or complex weights are employed, the utilized filter bank (Wi)er determines the space of learnable functions yo span( (V, heer) and thus contributes significantly to the inductive bias present in the network. should thus be adjusted to the respective task at hand.
The Action of Filters in the Spectral Domain: In order to determine which basis functions are adapted to which tasks, a "frequency-respone
interpretation of spectral filters is expedient:
In the undirected setting this proceeded by decomposing any characteristic operator T into sum T = Exea(T) A- PA over its distinct eigenvalues. The spectral action of any function g was then given by g(T)) = (T) ((A)-PP Here the spectral projections P' project each vector to the space spanned by the eigenvectors {us) corresponding to the eigenvalue À (i.e. satisfying (7 - Ald)u; 0).
In the directed setting, there only exists a basis of generalized eigenvectors (w; ) each satisfying (T' X Id)" w. 0 for some À E (TT) and m IN (c.f. Appendix (B) Denoting by PA the matrix projecting onto the space spanned by these generalized eigenvectors associated to the eigenvalue A E (TT), any operator T may be written a T Exeo(r) X Px (T) (T A Id) Px. It
can then be shown
Kato 1976), that the spectral action of given function 9 is given
[n) (A)
s())
Σ s(A)Ps+ + (TO
Σ (T)
(T - Id)" Pa-
(4)
n!
Here the number m is the algebraic multiplicity of the eigenvalue X; i.e. the dimension of the associated generalized eigenspace. The notation (m)) denotes the Tihh complex derivative of g. The appearance of such derivative terms in (4) is again evidence, that we indeed needed to restrict from generic- to differentiable functions 5 in order to sensibly define directed spectral convolutional filters.
It is instructive to gain some intuition about the second sum the right-hand-side of the frequency response (4), as it is not familiar from undirected graphs (since it vanishes if T is self-adjoint): As an example consider the un un-weighted directed path graph on three nodes depicted in Fig. 4 and choose as characteristic operator T the adjacency matrix (i.e. T W). It is not hard to see (c.f. Appendix ffor an explicit calculation) that the only eigenvalue of W is given by X = with algebraic multiplicity my 3. Since spectral projections always satisfy Exer(T) PA Id (c.f. Figure 4: Directed
path on 3 nodes
Appendix B and here (W) {0} we thus have Px-o Id in this case.
Suppose now we are tasked with finding a (non-trivial) holomorphic filter g()) such that (TT) 0. The right- hand sum in (4) implies, that beyond (0)) = 0, also the first and second derivative of (A) needs to vanish at À = 0 to achieve this. Hence the zero of (A)) at À = 0 must be at least of order three; or equivalently for - we need g() of )3). This behaviour of course exactly mirrored in the spatial domain: As applying W simply moves information at a given node along the path, applying W once or twice still leaves information present. After two applications, only node 3 still contains information and thus applying W precisely removes all information if and only if & >> 3. Without the assumption of acyclicity, the spectrum of characteristic operators of course generically does not consist only of the eigenvalue x = 0. Thus generically Px=o # Id and the role played by the operator = W' in the considerations above is instead played by its restriction (T PA=o) to the generalized eigenspace corresponding the eigenvalue À 0.
For us, the spectral response (4) provides guidance when considering scale-insensitive convolutional filters 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)
2 Additional details on this so called Jordan Chevalley decomposition are provided in Appendix B N.B.: A mmmc-ccoplex-diffeeenilll function is automatically infinitely often differentiable (Ahlfors 1966
4

---

Published as a conference paper at ICLR 2024
3.3 EXPLICIT FILTER BANKS
Having laid the theoretical foundations, we consider examples of task-adapted filter banks { (Wiher-
3.3.1 BOUNDED SPECTRAL DOMAIN: FABER POLYNOMIALS
First, let us consider spectral networks on a single graph with a fixed characteristic operator T. From
the holomorphic functional calculus ( we infer that convolutional filters (g(T)) are in principle provided by all holomorphic functions {g} defined on a domain U which contains all eigenvalues À E (T) of T. As noted above, implementing an arbitrary holomorphic g is however too costly, and we instead approximate via collection of simpler basis functions { hee as g(A) = Lier 0, (A).
In order to choose the filter bank [Ve)ier, we thus need answer the question of how to optimally approximate arbitrary holomorphic functions on a given fixed domain U. The solution to this problem is given the guise of Faber polynomials (Ellacoti, 1983] Coleman & Smith 1987) which generalize the familiar Chebychev polynomials utilized in (Defferrard et al. 2016) to subsets U of the complex plane (Elliott 1978). Faber polynomials provide near mini-max polynomial approximation to any holomorphic function defined on domain U satisfying some minimal conditions (c.f. |Ellion (1978) for exact details). What is more, they have already successfully been employed in numerically approximating matrices of the form (TT) for I not necessarily symmetric (Moret & Novati 2001
While for a generie domain U Faber polynomials are impossible to compute analytically, this poses no limitations to us in practice: Short of costly explicit calculation of the spectrum (TT), the only information that is generically available, is that eigenvalues may be located anywhere within a circle of radius [T]] This circle must thus be contained in any valid domain U. Making the minimal choice by taking U to be exactly this circle, the n -Fbeer polynomial may be analytically calculated (He) 1995): Up to normalization (absorbed into the learnable parameters) it is given by the monomial \ We thus take our nhhh basis element vr (A) to be given precisely by this monomial: (A) = A Thus Faber polynomials evaluate to (T'(T) = T on our characteristic operator T (c.f. Thoerem (.1]. In setting where more detailed information on (TT) is available, the domain U may of course be adapted reflect this. Corresponding Faber polynomials might then be pre-computed numerically.
3.3.2 UNBOUNDED SPECTRAL DOMAIN: FUNCTIONS DECAYING AT COMPLEX INFINITY
In the multi-graph setting - c.g. during graph classification we are confronted with the possibility that distinct graphs may describe the same underlying object (Levie et al. 2019a Maskey et al. 2021 Koke 2023). This might for example occur if two distinct graphs discretize the same underlying continuous space; e.g. at different resolution scales. In this setting instead of precise placements of nodes what is actually important the overall structure and geometry of the respective graphs.
Un- unroozzalized Laplacians provide convenient multi-scale descriptions of such graphs, as they encode information corresponding to coarse geometry into small (in modulus) eigenvalues, while finer graph structures correspond to larger eigenvalues (Chung 1997 Ng et al. (200)). When designing networks whose outputs are not overly sensitive to fine print articulations of graphs, the spectral response 4 then provides guidance on deteriming which holomorphic filters g are able to suppress this superfluous high-lying spectral information: It is sufficient that g(m) (A)/n! æ 0 for [ > 1. can be shown that no holomorphic function with such large- A asymptotics defined on all of C exists We thus make the minimal necessary change and assume g to be defined on punctured domain = (fy instead. The choice of y E C is treated as a hyperparameter, which may be adjusted to the task at hand. Any such g may then be expanded as gA) Σー- 0,(A- y) / for some coefficients {0,);21 Bak & Newman 2017). J. Evaluating the defining integral (2) for the Laplacian _ on the atoms 1
(A - y) yields V (T.") ([T.in y- Id] [d]- ) as proved in Appendix Hence corresponding filters are polynomials in the resolvent R, == [I in y Id of L
Such resolvents are traditionally used as tools to compare operators with potentially divergent norms (Teschl, 2014). Recently Koke et al. (2023) utilized them in the undirected setting to construct net- works provably assigning similar feature-vector to weighted graphs describing the same underlying object at different resolution-scales. Our approach extends these networks to the directed setting:
'L.. minimizing the maximal approximation error on the domain of definition U.
'This is immediate consequence of Liouville's theorem in complex analysis Ahlfors 1966
5

---

Published as a conference paper at ICLR 2024
Effective directed Limit Graphs: From diffusion perspective, information in graph equalizes faster along edges with large weights. In the limit where the edge-weight within certain sub-graphs tend to infinity, information within these clusters equalizes immediately and such sub- sub-graphs should thus effectively behave as single nodes. Extending uediieeced-grappe results (Koke & Kutyniok] [2022] Koke et al. 2023), we here establish rigorously that this is indeed also true in the directed setting.
Mathematically, we make our arguments precise by considering a graph G with a weight matrix W admitting a (disjoint) two-scale decomposition as W Wreegulur + c- Whigh (c.f. Fig. 5 As the larger weight scale e > 1 tends to infinity, we then establish that the resolvent Ry (L on G
converges to the resolvent Ry ())) of the Laplacian L on a coarse-grained limit graph G. This
limit G arises by collapsing the reaches R of the graph Ghigh = (G, Whigh) (c.f. Fig. (c) into
single nodes. For technical reasons, we here assume equal in- and out-degrees within Guigh (i.e.
2 W high 6)
-i W Appendix G contains proof' corresponding the results below.
(a)
(b)
Figure 5: (a) Graph G with Wregular (blue) & Whigh (red); (b) Wregular, (c) Whigh; (d) Limit Graph G
When defining G. directed reaches now replace the undirected components of Koke et al. (2023);
Definition 3.2. The node set G of G is constituted by the set of all reaches in Gnigh- Edges & of G are given by those elements (R. P) e x g with non-zero agglomerated edge weight W RP Eren Eper Wrp. Node weights in G are defined similarly by aggregating as ER EreR Mr.
To map signals between these graphs, translation operators Jh are needed. Let be scalar graph signal and let 1 R be the vector that has as entry for nodes r E R and zero otherwise. Denote by uR the entry of at node R E G. The projection operator J is then defined component-wise by evaluation at node R E G as (J'z) (IR 2)/ Interpolation is defined J = Reg uR RR. The maps Jt, J are then extended from single features {r} to feature matrices {X} via linearity.
With these preparations. we can now rigorously establish the suspected effective behaviour of clusters: Theorem 3.3. In the above setting, we have [R,y X J ( X| as e - 80.
For C >> 1, applying the resolvent R.y(L") on G is thus essentially the same first projecting to the coarse-graie gearse-grained graph G (where all strongly connected clusters are collapsed), applying the corresponding resolvent there and then interpolating back up to G. The geometric information within R,, is thus essentially reduced to that of the coarse grained geometry within G.
Large weights within graph typically correspond to fine-structure articulations of its geometry: For graph-discretisations of continuous spaces, edge weights e.g. typically correspond to inverse discretization lengths (wi 1/diz) and strongly connected clusters describe closely co-located nodes. In social necial-networks, edge weights might encode closeness pooseness-measure. and coarse- -rrriiing would correspond to considering interactions between (tightly connected) communities as opposed to individual users. In either case, fine print articulations are discarded when applying resolvents.
Stability of Filters: This reduction a limit description on G is respected by our filters {ge}: Theorem 3.4. In the above setting, we have [[ X J
X 0 as c - 50.
If the seight-scale e is very large, applying the learned filter go(A) = Σ 0,(2 - .) to a signal X on as X + go In X thus is essentially the same as first discarding fine-structure information by projecting X to G. applying the spectral filter go there and subsequently interpolating back to G. Information about the precise articulation of a given graph G is thus suppressed this propagation scheme; it is purely determined by the graph structure of the coarse- -griined description G. Theorem 4.2 below establishes that this behaviour persists for entire (directed) spectral convolutional networks.
This is known Kirchhoff's assumption (Batt 2018 ; repraducing the eponymous law of electrical circuits.

---

Published as a conference paper at ICLR 2024
4 SPECTRAL NETWORKS ON DIRECTED GRAPHS: HOLONETS
We now collect holomorphic filters into corresponding networks; termed HoloNets. In doing so, we need to account for the possibility that given edge directionalities might limit the information-flow facilitated by filters (T))): In the path-graph setting of Fig. 4 for example, a polynomial filter in the adjacency matrix would only transport information along the graph: features of earlier nodes would never be augmented with information about later nodes. To circumvent this, we allow for two sets of filters (T)) and (g)"d((")) based on the characteristic operator T and its adjoint T*, Allowing these forward- and backward-filet to be learned in different bases { [wd(dd/ww)] Jie (onarns we may write Go ((vdbwd()) (X) Th
prodows Olwabwdy fow//bwdd (A). With bias matrices B of size N x Fe+1 and weight matrices W W. of dimension Fe x Fe+1, our update rule is then efficiently implemented as
X =
Σ ( (T) x I.w. + +(1 a1-a) a) VE/TMM
Σ SE/
V w.wdd
(T*)
x b.wwd, + Be
Here p is a point-wise non-linearity, and the parameter a E [] or tunable- - is introduced following Rossi et al. 2023) to allow for a prejudiced weighting of the forward or backward direction.
We additionally provide a pseudocode description of the corresponding models in Appendix
The generically complex weights & biases may often be restricted to R without losing expressivity:
Theorem 4.1. Suppose for filter banks { (V/nnd/fued J preann that the matrices Wffd(T)) Whwd((") contain only real entries. Then any HoloNet with layer-widths { {Fe) with complex weights & biases and a non linearity that acts on complex numbers componentwise as p(a ib) m() i7(a) can be exactly represented by a HoloNet of widths {2- Fe} utilizing P and employing only real weights & biases.
This result (proved in Appendix H establishes that for the same number of real parameters, real HoloNets theoretically have greater expressive power than complex ones. In our experiments in Section 5 below, we empirically find that complex weights do provide advantages on some graphs. Thus we propose to treat the choice of complex vs. real parameters as a binary hyperparameter.
The first specific instantiation of HoloNets we consider, employs the Faber Polynomials of Section 3.3.T for both the forward and backward filter banks. Since Rossi et al. (2033) established that considering edge directionality is especially beneficial on heterophilic graphs, this is also our envisioned target for the corresponding networks. We thus use as characteristic operator a matrix that avoids direct comparison of feature vectors of node with those of immediate neighbours: We choose T (D"))= $ W- (D - since it has a zero-diagonal and its normalization performed well empirically. For the same reason of heterophily, we also consider the choice of whether to include the
FaberNet:
Faber polynomial vo (A) = 1 in our basis as hyperparameter. As non-linearity, we choose either p(a + ib) = ReLu(a) + (b)Lu(b) or p(a + ib) = |a| + i|bl. Appendix contains additional details.
Dir-ResolyNet: In order to build networks that are insensitive to the fine-print articulation of directed graphs, we take as filter bank the functions (A) = (A - y)-"}iso evaluated on the Laplacian I. for both the forward and backward direction. To account for individual nedg-weights when building up graph-level features, we use an aggregation 12 that aggregates N x F-dimensional
node-feature matrices 9(X), ΣN Xx,gl 14 to graph-feature ((X) RF. Graph-level stability under varying resolution scales then captured by our next result:
Theorem 4.2. Let & and & be the feature maps associated to Dir-ResolyNets with the same weights and biases deployed on graphs G and G as defined in Section
3.3.2
With Ω the aggregation method
specified above and W Wrregular + c- W/high as in Theorem
3.4 we have for e - 00:
|| (x()) Ω (Φ(J
||
Appendix G contains proofs of this and additional stability results. From Theorem 4.2 we conclude that graph-level features generated by a Dir-ResolyNet are indeed insensitive to fine print articulations of weighted digraphs: As discussed in (ectioon3.3.2 geometric information corresponding to such fine details is typically encoded into strongly connected sub-graphs; with the connection strength corresponding to the level of detail. However, information about the structure of these sub-graphs is precisely what is discarded when moving to G via J+. Thus the greater the level of detail within G, the more similar are generated feature-vector vectors to those of a (relatively) coarse- -raniee description G.
7

---

Published as a conference paper at ICLR 2024
5
EXPERIMENTS
We present experiments on real-world data to evaluate the capabilities of our HoloNets numerically.
5.1 FABERNET: NODE CLASSIFICATION
We first evaluate on the task of node-classification in the presence of heterophily. We consider multiple heterophilic graph-datasets on which we compare the performance of our FaberNet instantiation of the HoloNet framework against representative array of baselines: As simple baselines we
consider MLP and GCN Kipp & Welling, 2017). H₂GCN (Zhu et al.. 2020), GPR-GNN (Chien
et al. 2021), LINKX (Lim et al., 2021), FSGNN (Maurya et al., [2021] ACM-GCN (Luan et al.
2022), GloGNN (Li et al., 2022) and Gradient Gating (Rusch et al. (023) constitute heterophilic
state-of-the-od models. Finally state-of- state-of-theeart ther models for directed grapks given by DiGCN (Tong
eet al., 2020), MagNet (Zhang et al., (202T) and Dir-GNN (Rossi et al., (023). Appendix || contains
dataset statistics well as additional details on baselines, experimental setup and hyperparameters.
Table 1: Results on real-world directed heterophilic datasets. OOM indicates out of memory.
Squirrel 0.223
Chamelcon
Arxiv-year 0.221
Snap-patents 0.218
Roman- Roman-Empire 0.05
Homophily
0.235
MLP
28.77 +: 1,56
46,21 = 2.99
36.70 + 0.21
31.34 + 0.05
64.94 + 0.62 73.69 +'2 0.74
GCN
53.43 + 2.01
64.82 2.24
46.02 + 0.26
51.02 + 0.06
H₂GCN
37.90 + 2.02
59,39 = 1.98
49.09 + 0.10
OOM
60.11 + 0.52
GPR-GNN
54.35 + 0.87
62.85 = 2.90
45.07 0.21
40.19 + 0.03
64.85 + 0.27
LINKX
61.81 + 1.80
68.42 1.38
56.00 0.17
61.95 0.12
37.55 + 0.36
FSGNN
74.10 + 1.89
78.27 = 1.28
50.47 + 0.21
0.21
65.07 + 0.03
79.92 + 0.56
ACM-GCN
67.40 + 2.21
74.76 2.20
47.37 + 0.59
55.14 0.16
69.66 + 0.62
GloGNN
57.88 + 1.76
71.21 1.84
54.79 + 0.25
62.09 + 0.27
59.63 1 0.69
Grad. Gating
64.26 1 2.38
2.38 71.40
63.30 1.84
69.50 1 0.39
82.16 1 0.78
DiGCN
37.74 + 1.54
52.24 - 3.65
OOM
OOM
52.71 + 0.32
MagNet
39.01 + 1.93
58.22
2.87
60.29 0.27
0OM
88.07 + 0.27
DirGNN
75.13 1 1.95
79.74
1.40
63.97 0.30
73.95 1 0.05
91.3 0.46
FaberNet
76.71 1: 1.92
80.33
1.19
64.43
0.28
75.10 1 0.03
92.24 1: 0.43
As can be inferred from Table FaberNet sets new state of the art results on all five heterophilic graph datasets above; out out-performing intricate undirected methods specifically designed for the setting of heterophily. What is more, it also outperforms directed spatial methods such as Dir-GNN, whose results can considered as reporting a best-of-three performance over multiple directed spatial methods (c.f. Appendix [ or Rossi et al. (2023) for details). FaberNet also significantly out- out-performs MagNet. This method is a spectral model, which relies on the graph Fourier transform associated to a certain operator that is able to remain self-adjoint in the directed setting. We thus might take this gap in performance as further evidence of the utility of transcending the classical graph Fourier transform: Utilizing the holomorphic functional calculus graph Fourier transform allows to base filters on (non-self-adjoont) operators more adapted to the respective task at hand. On Squirrel and Chameleon, our method performed best when using complex parameters (c.f. Table 7 Appendix [}. With MagNet being the only other method utilizing complex parameters, its performance gap to Dir-ResolvNet also implies that indeed the interplay of complex weights with judiciously chosen filter banks and characteristic operators that provides ofate-of-the-are performance; not the use of complex parameters alone.
opposed to the traditional
5.2 DIR-RESOLVNET: DIGRAPH REGRESSION AND
We test the properties of our Der-ResolyNet HoloNet via graph regression experiments. Weighted- directed datasets containing both node-features and graph-level targets are currently still scarce. Hence we follow Koke et al. (2023) and evaluate on the task of molecular property prediction. While neither our Bir-ResolvNet nor baselines of Table Tare designed for this task, such molecular data still allows for fair comparisons of expressive power and stability properties of moonspeciallize) graph learning methods (Hu et al. 2020a). We utilize the QM7 dataset (Rupp et al. 2012), containing graphs of 7165
8

---

Published as a conference paper at ICLR 2024
organic molecules; each containing hydrogen and up to seven types of heavy atoms. Prediction target is the molecular atomization energy. While each molecule is originally represented by its Coulomb matrix Wij Z; 2,/1 žzl. we modify these edge- weights: Between each heavy atom and all atoms outside its respective immediate hydrogen cloud we set Wi Zouuside (Z) 1)/l p Zا|. While the sole reason for this change is to make make the underlying graphs directed (enabling comparisons of directed methods), we might heuristically interpret it as arising from a (partial) shielding of heavy atoms by surrounding electrons (Heinz & Suter 2004).
With W as directed weight-matrix and setting y -1, we evaluate Dir- ResolyNet against all other directed methods of Table []] Atomic charges are used as node weights (1, = Z₁) where applicable and one-hot encodings of atomic charges Z₁
Bigraph-Regressoon
Table 2: [kcal/mlooll
provide node-wise input features. As evident from Table 2
our method pro-
duces significantly lower war----absuuueerrrnnn (MAFs) than corresponding directed baselines: Competitors are out-performed by factor of two and more. We attribute this to Dir-ResolvNets ability to discard superflu- ous information; thus better representing overall molecular geometries.
DirGNN
59.01 +2.04
MagNet DiGCN
45.31
39.9516.25
Ne-RReoolvNe11..... 17. 10.1..2.666.
Scale- :inensiinsss:
To numerically investigate the stability properties of Dir-ResolyNet that were
and 4.2 we mathematically established in Theorems and
Restifiet
translate Koke et al. (2023)'s 's undirected setup to the directed setting: We modify (all) molecular graphs on QM7 by deflecting hydrogen atoms (H) out of equilib- rium towards the respective nearest heavy atom. This introduces a two-scale setting as in Section 3.3.2 Edge weights between heavy atoms remain the same, while weights between H-atoms and closest heavy atoms in- creasingly diverge. Given original molecular graph G, the corresponding limit G corresponds to a coarse grained description, with heavy atoms and surrounding H-atoms aggregated into super-nodes. Feature vectors of aggregated nodes are now normalized bag-of-wort vectors whose individual entries encode how much total charge of a given super-node is contributed by individual provides additional details.
107
DYGAN
10
10'
10-1
20P
10¹
307
10a
10
joquilib. dist.)
Figure 6: Feature-difffrence for collapsed
(F) and deformed (F) graphs.
atom-types. Appendix !
In this setting, we compare feature vectors of collapsed graphs with feature vectors of molecules where hydrogen atoms have been deflected but have not yet arrived at the positions of nearest heavy atoms. Feature vectors generated with the previously trained networks of Table 2 As evident from Fig. 6, Dir-ResolyNet's feature-vectors converge as the scale e ~ | Thavv increases; thus numerically verifying the scale-invariance Theorem 4.2 Feature vectors of basclines do not converge: These models are sensitive to changes in resolutions when generating graph-level features.
This difference in sensitivity is also apparent in our final experiment, where collapsed molecular graphs {G} are treated as a model for data obtained from a resolution- able to resolve individual H-atoms. Given models trained on directed higher resolution digraphs {G). atomization energies are then to be predicted solely using coarse grained molecular digraphs. While Dir-ResolvNet's prediction accu-
observation process un-
Table 3: QM7
[kcal/mol]
racy remains high, performance of baselines decreases significantly if DirGNN
195.64=2.20
the resolution scale is reduced during inference: While Dir-ResolvNet MagNet out out-performed baselines by factor of two and higher before, this lead increases to a factor of up to 240 if resolutions vary (c.f. Table
663.63
DiGCN
6672.71 22243.61
Dir-ResolvNet
27.34
CONCLUSION
We introduced the HoloNet framework, which allows to extend spectral networks to directed graphs. Key building blocks of these novel networks are newly indroduced holomorphic filters, no longer reliant on the graph Fourier transform. We provided a corresponding frequency perspective, inves- tigated optimal banks and discussed the interplay of filters with characteristic operators in shaping inductive biases. Experiments real world data considered two particular HoloNet instanti- ations: FaberNet provided new state-of-ther art results for node classification under heterophily while Dir-ResolvNG generated feature vectors stable resolution-scale- varying topological perturbations.
9

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENTS
The authors thank Mariia Gladkova and Tarun Yenamandra for helpful discussions. This work was supported by the ERC Advanced Grant SIMULACRON.
REPRODUCIBILITY
We are taking great care ensuring reproducibility of our work:
We give complete mathematical definitions all utilized concepts. Proofs all Theorems are provided in the appendix (c.f. e.g. Appendices F H
We exactly detail our newly introduced (HoloNet) framework and its two particular instances (FaberNet, Dir-ResolvNet) the main body of our paper (c.f. Section 4
The experimental setups for our experiments are described exactly Appendix
|
All hyperparameter settings of our methods for experiments are detailed in the appendix (c.f. T Table and Section [.2]
com Our code is available at https:: wttpttt.cco//criststaaooooooo. oNet.s
REFERENCES
L. V. Ahlfors. Complex Analysis. McGraw-Hill Book Company, 2 edition, 1966.
Joseph Bak and Donald J. Newman. Complex analysis. Springer, 2017.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL httts:://ppenreweee htt.:enetttooooeeeooeeeeeeooeooe forum?
4M0XXXXxv
Marwa Balti. Non self-adjoint laplacians on a directed graph, 2018.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabricle Corso, and Pictro Lió. Directional graph networks. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 748 758.7 PMLR, 2021.
URL httphtt:/ppocceeinnggee/// htt.://mmmm...........////////// wttppp/ss///leeaannaa/aa.
mrr.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Francesco Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions Pattern Analysis and Machine Intelligence, 44:3496-3507, 2019.
L. C. Blum and J.-L. Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database GDB-13. Am. Chem. Soc., 131:8732, 2009.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representattinss, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.nee, 2023. /tL/ net/ DdF2idd0ppStsoyyall
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally con- nected networks on graphs. In International Conference on Learning Representations (ICLR2014). CBLS, April 2014 2014.
Eli Chien, Jianhao Peng. Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URLpttps httppp/p/ppeeeeeeeerrr
10

---

Published as a conference paper at ICLR 2024
Fan R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. ISBN 0-8218-03152
John P. Coleman and Russell A. Smith. The faber polynomials for circular sectors. Mathematics of Computation, 49(179):3112241 1987. ISSN 00255718, 10886842. URL http:://wwwwt http::/www.jstor jstor org/ pog/ssaabee/2208222
Fabrizio Colombo, Irene Sabadini, and Daniele C. Struppa. Nonconuuuative Functional Calculus:
Theory and Applications of Slice Hyperholomorphic Functions, pp. 201-210. Springer Basel, Basel, 2011. ISBN 978-3-0348-01100
10-2_5. URL https
//doi. 1007/97--3-008-00000
Michael Cowling, Ian Doust, Alan Micintosh, and Atsushi Yagi. Banach space operators with bounded hoo functional calculus. Journal of the Australian Mathematical Society, 60(1):51-89, 1996. doi: (4417//54477787000773399
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
S. W. Ellacott. Computation of faber series with application to numerical polynomial approximation in the complex plane. Mathematics of Computation, 40(162):575-588 587, 1983. ISSN 00255718, 10886842.
:/www/
G. H. Elliott. The construction of chebyshev approxxmaiios in the complex plane. PhD Thesis. Im- perial College London, 1978. UtL/httpss//ppp..seaaiiccccoooot wwt.:cchh.......ooooooooos..saaa
126233753
Simon Geisler, Yujia Li, Daniel J. Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. CoRR, abs/2302.00049, 2023. doi: 10.48550/arXiv. 2302.00049. URL htttt: http//oo.orr//o/oooo http://11.45550///11aaa 2302. 00049.
Herbert A. Gindler. An operational calculus for meromorphic functions. Nagoya Mathematical Journal, 26:31-38, 1966. doi:
Markus Haase. The Functional Calculus for Sectorial Openators, pp. 19-60. Birkhäuser Basel, Basel,
2006. ISBN 978-3-7643--698- doi: 10.1007/3-7643-7766 2. URL https://doi.ozg/ 10.
8
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017. URL
http://wwooeeciigg.......rss.sss /c/ 5 htapar/00..aaaaocaaaaaaaaaaaaaa0
html
M. He. The faber polynomials for circular lunes. Computers & Mathematics with Applica- lions, 30(3):307-315, 1995. ISSN 0898-1221. doi: http://bbboorr/11101111888888111
00109-3. URL https:/ http:://wwww.... scieecediieccccccco rect. com sci wttp://eee/aeeeeeeeeeette
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbi- trary graph spectral filters via bernstein approximation. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 14239 14251, 2021. URL http:ttttss//pcceeeeiieee ngs www.nnurrp...m wwwuurps.ccpappaeee wttcc//ppppppcccc /2021 /hash/ T DAC.EE222....co000000aaaaTTr...,
Abst html
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks In NeurIPS. 2022a.
with chebyshev approximation, revisited. http::/papers..t pip.eess.iipp nips http://sesrs.aa..oo/ooooaaaaa//a 2 010 ort.
graphs URL

---

Published as a conference paper at ICLR 2024
Yixuan He, Michael Perlmutter, Gesine Reinert, and Mihai Cucuringu. MSGNN: A spectral graph neural network based on a novel magnetic signed laplacian. In Bastian Rieck and Razvan Pascanu (eds.), Learning on Graphs Conference, LoG 2022. 9-12 12 December 2022, Virtual Event, volume 198 of Proceedings of Machine Learning Research, pp. 40. PMLR, 2022b. URL https //proceedings.oo ml www.rrp.eassee. http://lll////22/ html
Hendrik Heinz and Ulrich W. Suter. Atomic charges for classical simulations of polar systems. The Journal of Physical Chemistry B, 108(47):1833111885 2004. doi: 10. 10.1021/jp04814 142t. URL https: /oos:://do..o 1ttp://00.02111008111134
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a. URL Fb60d41 11 2ac.cbcb2222222333333c3 ract html
h neurips CC wtwp//pptr///2//////ooo
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00633 2020b.
Tosio Kato. Perturbation theory for linear operators; 2nd ed. Grundlehren der mathematischen Wissenschaften a series of comprehensive studies mathematics. Springer, Berlin, 1976. URL
https: cds cern. ch. chtreecor//rorraa..
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24- 26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
net fttt:/ooumm.d==SJAA0.
Christian Koke. Limitless stability for graph convolutional networks. 11th International Conference on Learning Representattinss ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL
net http:/iwwwwee///ourrrreoo id= XgcQhuOO22
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, NeurlPS 2020, November 28 December 9, 2022, New Orleans. OpenReview.net, 1XDMMM
2022. URL httpttt:///ppeeeeeeetee /tt.D//L/Lss///eeeeeesssseeetee.
Christian Koke, Abhishek Saroha, Yuesong Shen, Marvin Fisenberger, and Daniel Cremers. Re- solvnet: A graph convolutional network with multi-scale consistency. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023, URL V5eDWEDEXT
Chi Lee, Hideyuki Hasegawa, and Shangce Gao. Complex-valued neural networks: A com- prehensive survey. IEFE/CAA Journal of Automatica Sinica, 98):1406-1426, 2022. doi:
(..1009/AAS.2222.1555
Ron Levie, Michael M. Bronstein, and Gitta Kutyniok. Transferability of spectral cog. convolutional neural networks. CoRR, abs/1907.12977 2019a. 12972
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convolu- tional neural networks with complex rational spectral filters. IEEE Trans. Signal Process., 67(1): 97-109, 2019b, doi: 1LLL10///SP22012887762..2 URL haattp:://do..oog/1...oo 2018.28799 2879624
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.),
12

---

Published as a conference paper at ICLR 2024
International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 13242-13256. PMLR, 2022.
URL WRLLtttps:/ppoceeiiiia http.//ppp.pppee///////aa.... html
mlr www.ppeess.iiii
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non homophilous graphs: New benchmarks and strong simple methods. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrlPS 2021, December 6-14, 2021, virtual, pp. 20887-20902, 2021. URL /tts
cc/
paper 22t// aew/ 6ew.ea0000046eeeeee1ee /atppe//0000//aaaeeeeeeaeaaaaae2
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NeurlPS, 2022. http///////////pprrrs....a..////
/ html|
Sohir Maskey, Ron Levie, and Gitta Kutymiok. Transferability of graph neural networks: an extended graphon approach. CoRR, abs/2109.10096, 2021. URL. /tt.
10096
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. CoRR, abs/2105.07634, 2021. h UKL/pttps://arxxi..rrr//bbbb 07634
I. Moret and P. Novati. The computation of functions of matrices by truncated faber series. Numerical Functional Analysis and Optimization,, 22(5-)))677-719 2001. doi: 10. 10.1081/NFA- 10NNA--1000 1000 1tt.:///1..1111/11111101000 URL htt.:: /tt:::/doooooooo http:///////a...111110110..11110
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In
T. Dietterich, S. Becker, and Z. Ghahramani (cdss), in Neural Information Processing Sys- tems, volume 14. MIT Press, 2001. wtt.///ttse//rrrreeees.....eaao.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All have is low-pass filters. CoRR, abs//905.00950 2019.
190.//99550000 09550
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks, 2020. /
wwtp:/o.rg.oooooo.oooooooooo www.://///./o/......... 05287
Michael Perlmutter, Feng Gao, Guy Wolf, and Matthew Him. Understanding graph neural networks
with asymmetric geometric scattering transforms, 2019. URI. htt.:taaa//axx...o/////a//
1911.063
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URUlhttps:: nttp://eet///// id=tJbbQfw -ww
Olaf. Post. Spectral Analysis Graph-like Spaces / by Olaf Post. Lecture Notes in Mathematics, 2039. Springer Berlin Heidelberg, Berlin, Heidelberg, 1st ed. 2012. edition, 2012. ISBN 3-642-23840-8.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. Edge directionality improves learning on heterophilic graphs, 2023,
Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Transferability properties of graph neural networks. CoRR, abs/21 12.04629, 202 UR..tttps.//axx...rr//asss
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stability and transferability, 2021b.
13

---

Published as a conference paper at ICLR 2024
M. Rupp. A. Tkatchenko. K.-R. Müller, and O. A. von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. Physical Review Letters, 108:058301, 2012.
T. Konstantin Rusch, Benjamin Paul Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5,
2023. OpenReview.net, 2023. URL http:s::///peeeeeeeeeee net/ wttp:/eeettppaddddppaaaaaaeee rid-JpRExTo11
Gerald Teschl. Mathematical Methods in Quantum Mechanics. American Mathematical Society, 2014.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 17907-17918 Curran Associates, Inc., 2020. URL httpes:/pprooeeddnss.rerr.s.....
pdf
J. J. P. Veerman and Robert Lyons. A primer on laplacian dynamics in directed graphs, 2020.
Jjp Veerman and Ewan Kummel. Diffusion and consensus weakly connected directed graphs. Linear Algebra and its Applications, 578, 05 2019. doi: (0.1016f).aa.2211.05..
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https:://///... httpt::://ppeeeeieeee
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 23341-23362. PMLR, 2022a. URL
mlr pre.t/reessssee 62/ 62/wang22am, html
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning, 2022b. Uttp
CorpusID:228993
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew J. Hirn Magnet: A neural network for directed graphs. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Ad- vances Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 27003-27015, 2021. URL http::tta//poocceaiiiiii .ww.rieurspp..... httpppscccppppppppeeee pcc/papee//02//haattt. Abstaaa html
e
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. httLlihtttt:://roeeeete ngs nwwrips. wwtpppppr/222////aeeep 58ae23d8 75540000838888884448488883 Absttt0--bstttttttate .htll
14

---

Published as a conference paper at ICLR 2024
A
NOTATION
We provide a summary of employed notational conventions:
Table 4: Notational Conventions
Symbol
Meaning
a graph
Nodes of the graph G
N
number of nodes [ G
G
Coarse grained version of graph G weight of node weight matrix inner product
M
<.)
W
(weighted) adjacency matrix
Dinkout
in/out-degree matrix
L
in-degree graph Laplacian generic characteristic operator
T
T
hermitian adjoint of T
TT
transpose of (used if and only if has only real entries) change-of oo-basis matrix a (complete) basis consisting of eigenvectors (used in the undirected setting only) spectrum (i.c. collection of eigenvalues) of T''
U
(I)
A
an eigenvalue a holomorphic function function applied to operator T an element of filter-bank complex numbers subset of C the resolvent -- Id)-
g
g(T)
V;
2,
U
(L")
z
a weight-/resolution scale
J1,J
projection and interpolation operator map associated to graph convolution network
graph-level aggregation mechanism
Z,
atomic charge of atom corresponding node i Cartesian position of atom corresponding to node Coulomb interaction between atoms i and Euclidean distance between x; and 2i
2,2,
B OPERATORS BEYOND THE SELF-ADJOINT SETTING
Here we briefly recapitulate facts from linear algebra regarding self-adjoint and non-self-adjoint matrices, their spectral theory and canonical decompositions.
Self-Adjoint Matrices: Let us begin with the familiar self adjoint matrices. Given a vector space V with inner product <,'>v consider linear map 7 V - V. The adjoint T of the map 7 is defined by the demanding that for all v, y
have
{x, Ty) < x x>v.
If we have V Cd and the inner product is simply the standard scalar product (x, V)e x. we have
T
Here denotes the complex conjugate of x and AT denotes the transpose of A.
An eigenvector- eigenvalue pair, is pair of a scalar E C and vector E V so that
(T X Td)y 0.
15

---

Published as a conference paper at ICLR 2024
It is standard result in linear algebra es. (Kto 1976)) that the spectrum a (T) of all eigenvalues of T contains only real numbers (i.e. E R), if T is self-adjoint. What more, there exists complete basis (ex )d of such cigenvectors that span all of V. These eigenvectors may be chosen to satisfy
(Ut; Ug 6zj-
(5)
with the Kronecker delta dij. As consequence of this fact, there exists a family of (so called) spectral projections > that have the following properties (c.f. e.g. [Teschl (014) for proof)
Each Px is linear map on V (Px: V).
For all eigenvectors e to the eigenvalue À (i.e. such that (T- - XId)e O), we have
Px V.
If w is an cigenvector to different eigenvalue E oTT) (i.e. w such that (T -- ud) w = and j X), we have
PA = 0.
Each PA is projection (i.e. satisfies PA PA PA).
Each PA is self-adjoint (i.e. PA = P))
Each PA commutes with (i.e. PA T = T PA).
The family (PX)XEa(T) form resolution of the identity:
Σ
P Id.
(TO(T)
These properties together then allow us "diagonalise" the operator T and write sum over its eigenvalues:
T A
(T)
Applying a generic function may then defined as (Teschl 2014)
g(T)
Σ a(A) Px. (EA(T)
Non self-adjoint operators: If the operator T' is no longer self adjoint, eigenvalues no longer need to be real, but are generically complex (i.e. À C). Furthermore, while there still exist eigenvectors these longer need to form basis of the space V. What instead becomes important in this setting, are so called generalized eigenveectors. A generalized eigenvector w associated to the eigenvalue vector for which have
A Id)"
some power n E Clearly each actual eigenvector is also a generalized eigenvector (simply
for 1). What can be shown (Kato) 1976) is that there is a basis of V consisting purely of generalized eigenvectors (each associated to some cigenvalue A). These now however need no longer be orthogonal (i.e. they need not satisfy (5)).
There then exists a family of spectral projections (Px)x that have the following modified set of properties (c.f. e.g. Kato 1976) for proof)
Each PA is linear map on V (PA : V - V).
For all generalized eigenvectors w to the eigenvalue (i.e. w such that (T - Ald)" w for some n IN), we have
PA w.
If w is a generalized eigenvector to a different eigenvalue μ (T)) (i.e. such that for some m E N and μ ze A), we have
(T n. Id)
PAw 0.
Each Px is projection (i.e. satisfies Pa P P.).
16

---

Published as a conference paper at ICLR 2024
Each Px commutes with T (i.e. Px T -...).
P.).
The family (PX)X) form resolution of the identity:
Σ
PA Id.
(T)
Using these facts, we may thus decompose each operator T into a sum as
T= Σ P
Σ -T- X. Id) Px- AEG(T)
(6)
(T)
This sum decomposition is referred to as Jordan-Che Corval-Ch decomposition. Importantly, for each E (T)) there corresponding natural number m, E N referred to the algebraic multiplicity the eigenvalue A. This number m counts, how many generalized eigenvectors {wr H are associated to the generalized eigenvalue X. These generalized eigenvectors can be chosen such that
X. Id) w (T Id) Px w w if i & my - 1. For the case > my we have
Id) umn =0.
In total, this implies the milpotency-relation
(T' - X md) PA = - x-1-d) Id) PAJT = 0.
C
SPECTRUM OF ADJACENCY OF THREE-NODE DIRECTED PATH GRAPH:
The adjacency matrix associated to the graph depicted in Figure is given by
0
0
0
0
Denote by ej the 7thh canonical basis vector. Then
W 61
c2.
W e2 c3
W 63
Clearly is an cigenvector to the eigenvalue À = 0, so that 0 o(W). Suppose there exists an eigenvector u associated different eigenvalue μ 0:
W =
Then have
W c n1d Since (ei, e2, 2x) clearly basis, there are numbers a, b, so that
v = de1 + bez + ces-
But then
n 3 v aW3 e1 bw3 e2 + cW -3= 0-10000+a Thus we have μ 0 and hence zero is indeed the only eigenvalue.
D COMPLEX DIFFERENTIABILITY
Complete introductions into this subject may be found in Ahlfors 1966) or (akk & Newman, 2017).
For complex valued function f C C single complex variable, the derivative of f point 20 E C in its domain of definition is defined as the limit
f'(z)) lim f(z)
f(z0)
20
17

---

Published as a conference paper at ICLR 2024
For this limit to exist, it needs to be independent of the 'direction' in which approaches 20, which is a stronger requirement than being real- differentiable.
open set U if is complex differentiable at every point in U. The value g()) of any such function at may be reproduced as
A function is called holomorphic
1
g(z)
9(A)
dz
2Ti
for any circle S = C encircling À so that S is completely contained within U and may be contracted to a point without leaving U. This equation is referred as Cauchy's integral formula (Bak & Newman 2017).
In fact, the integration contour need not be a circle S, but may be the boundary of any so called Cauchy domain containing X:
Definition D.1. A subset of the complex plane C is called Cauchy domain D is open, has a finite number of components (the closure of two of which disjoint) and the boundary of OD of D composed of finite number of closed rectifiable Jordan curves, no two which intersect.
Integrating around any such boundary then reproduces the value of g at X.
E ADDITIONAL DETAILS ON THE HOLOMORPHIC FUNCTIONAL CALCULUS
Fundamental Definition: In order define the matrix g(T), the formal replacement À + T is made on both sides of the Cauchy formula (7) with the path I now not only encircling a single value but all eigenvalues À (T") (c.f. also Fig.
b g(2) g(T) = 2mi
(T = 2 Id) dz
(8)
631
The integral is well defined since all eigenvalues of T are assumed to lie inside the path r. For any choice of integration variable on this path I, the matrix (T z Id) is thus indeed invertible, since is never an eigenvalue.
Figure 7: Operator Integral
This integral is also known Dunford- Taylor integral, and the holomorphic functional calculus is also sometimes called Riesz-Dunford functional calculus (Kato) 1976 Post 2012). As with the scalar valued integral (7). can be shown that the precise path I is not important, long encircles all cigenvalues counter-clockwiee and is contractable to single point within the domain of definition U for the function g.
Spectral characterization of the Holomorphic Functional Calculus: As stated in Section 3.2 the operator g (T)) may also be characterized spectrally, Writing T Exea(r) X PA Exer(r))
A Id) PA as in (6) it can then be shown (Ktto 1976,, that the spectral action a given function given
mx-1
g ((m)(A)
(T)
Σ
8(A)Px +
Σ
Σ ==1
nd (T X Id)"
Pa-
AEO(T)
(20
proof of this can be found in Chapter of Kato 1976
One of the strong properties of complex differentiability previously alluded to is, that as soon as once, it already complex differentiable infinitely often (Bak & Newman 2017). Hence the th -derivatiie in (9) does indeed exist.
function is cimplex-differentiin
With the preparations of Appendix
B
we can interpret the sum
mx-1
(() (T A Id)=
S =
Σ
Σ
P
(10)
n!
==
further:
18

---

Published as a conference paper at ICLR 2024
We first note, that summing up to > my would not make sense, since the nilpotency relation
T X- mx Px [(T - X. Id) PaJm 0.
tells us that any such term would be zero.
Furthermore, the factor - X basis (w:) f==1 of generalized eigenvectors spanning the generalized eigenspace associated to the eigenvalue X: It acts as
Id)* can be considered to be a "ladder operator" acting on
(T - A- Pa w 10 ++1
as discussed in Appendix B
The values g g(m) (A) in 10p can then be interpreted as weighing the individual "permutations" (T
A Id)" Px of basis elements in the generalized eigenspace associated to the eigenvalue X.
Finally we note that the spectrum of the new operator g(T) given as
(g((T) ((o(T) == (g(A) X (T)).
This is known the "Spectral Mapping Theorem" (Kato 1976).
Compatibility with Algebraic relations Here we prove compatibility of the holomorphic func- tional calculus with algebraic relations. For ease in writing, we will use the notation
1
(2 Id -d-d--
2-T
below.
Let us begin with monomials:
Lemma E.1. Applying the function g(A) = x to T yields T
Proof. We want to prove that
b T
dz
2mi
2 T
To this end, we use the Neumann series characterisation of the resolvent (Teschl 2014
(= (x-
Σ
which is valid for |a| > [T'] Substituting with g(A) = x yields
T
g(T)
1 Σ
de
2
2 1-k
11
which we may rewrite as Here we used the relation (c.f. e.g. Bak & Newman (017))
dz
Σ
T
8'k = T
2Tá
z
-
f
dz
8nk-
2mi
z
Next prove that the holomorphic functional calculus is also consistent with inversion:
19

---

Published as a conference paper at ICLR 2024
Lemma E.2. If is not eigenvalue of T, applying the function g(A) (x-1)
T yields
g(T) [(T' y- (dd 1d)
For case in notation we will write [(T - y 1d - y ld)
Proof. What want to prove, is thus the equality
(y Id - + =
1
p(v =) .(II( - T) T
2Ti
r
We first note that for the resolvent (T) = (T y. Id) we may write
(T) Σ (x- 1-1"
n=0
for |x 1 y| (T)) using standard results in matrix analysis (namely the 'Neumann Characteri- sation of the Resolvent' which is obtained by repeated application of resolvent identity; c.f. (2012) or Teschl (2014) for more details). We thus find
Post
1
& 1
k Σ
zld - T dz
(y 2)" Ry (T)
n+1
2Ti
2
2Ti
11
Using the fact that
0 -)
dz 8mk
2
then yields the claim.
F PROOF OF THEOREM 3.3
To increase readability, we here use the notation
In this section, we then prove Theorem 3.3 For convenience, we first restate the result together with the definitions leading up to it again:
Definition F.I. Denote by G the set of reaches in Ghigh- We give this set graph structure follows: Let It and P be elements of & (i.e. reaches in Ghigh). We define the real number
WRP
ΣΣ Wrps
ME PeP
with and p nodes in the original graph G. We define the set of edges & G
- (R, P x WRP >0 0)
and assign W RP weight to such edges. Node weights of limit nodes are defined similarly as aggregated weights all nodes (in G) contained the reach as
Σ Jr.
PR
In order to translate signals between the original graph and the limit description G, we need translation operators mapping signals from one graph the other:
20

---

Published as a conference paper at ICLR 2024
Definition F.2. Denote by 1 the vector that has 1 as entries nodes belonging to the connected (in G'uga) component and has entry zero for all nodes not in R. We define the cown-projection operator J component-wan via evaluating at node R in G as
(J²z)R= (IR. 2)/
The upsampling operator Jf is defined as
J Σ
Lun un 1 1
(11)
where un is scalar value (the component entry of u at R E 9) and the sum is taken over all reaches in Ghigh-
The result we then have to prove is the following:
Theorem F.3. We have (A) J (2) the weight scale increases. Explicitly,
J'
as
holds.
The proof closely follows that of the corresponding result in (Koke et al. 2023)
Proof. We will split the proof of this result into multiple steps. For 2 < 0 Let us denote by (2(A) (A =Id)=
R2 (Atrgg)) = (Arigh =Id) -1
R2 (Arguaa)))) = (Aregutar - 2Id)
the resolvents corresponding A, Ahigh and Areguiar respectively. Our first goal is establishing that we may write
(A)
[Td + RZ(Anigh [ R2 (Aiig))
This will follow as consequence of what is called the second resolvent formula (Teschl 2014):
"Given operators A, B, we may write
R B) (A) R. (A) B)."
In our case, this translates to
R=(A) RZ(Asigh)
- Rz (Anggh Aregular R2 (A)
or equivalently
[Td + Rz(Anien) Multiplying with [Td + (Aigg))) Aregular] -1 from the left then yields
Dregiaat Aregntar] R2
R2 (Aiign)))
(A) [Td + (A migh) reguiar)] ( (igh)
as desired.
Hence we need to establish that [Id + R2 (Anig)) A is invertible for = <
To establish a contradiction, assume is not invertible. Then there is signal æ such that
[[d R2 (Anigh) Areguiar
O.
Multiplying with (Arigh =Id) from the left yields
(Aigh + Aregular - =Id =
which is precisely to say that
(A =Td)a:
21

---

Published as a conference paper at ICLR 2024
But since A is a graph Laplacian, it only has cigenvalues with non non-negative real part Veerman & Lyons 2020). Hence we have reached our contradiction and established
R
[Id + (Agghhg regutar 1-1 R2 (ainhn)))
Our next step is to establish that
phigh R (Atgg))))
where phish is the spectral projection onto the eigenspace corresponding the lowest lying eigenvalue Ao (ngaa) = of nigh
Indeed, using the spectral characterization of the holomorphic functional calculus, we may write
9 (()(())
g( ((Ag)))= = Σ
g(A)Pa+ +
Σ
(Arigh - Id) Px
n!
XEo (Arigt
with
1
9(2)
2
Scaling the operator
Anigh as
Aigh
Aiihh
also scales all corresponding eigenvalues À À a- X, while leaving the spectral projections Pa invariant (Kato 1976). Thus taking the limit e 00 we indeed find
phigh
lim g(c. Anigh) =
Our next task use this result order show that the difference
high n
high
==
Id
A regular
[Id + Re(Diigh Aregatar]
R2 (Diigh)
goes to zero as - CC. To this end we first that the relation
[A + B - 2Id pTd ((AA)B]-RR((
provided to us by the second resolvent formula, implies
[Td + R2(A))]=' = Id - B[A+ B B- =Idd
Thus have
[Id + R2( (2(Anigh) Amgutar]
< 1 + A Aregutar|
(A))
1 regular
With this, have
22

---

Published as a conference paper at ICLR 2024
phigh
phigh
Td +
A
regular
R2(
2
Phigh
Phiigh
Id +
A
regudar
[[d R.g R (Atigh) Areutarl
R ( high)
2
phigh 0
fiihh
Id +
regular
[Id + R2 (A(giigh) Aropuiar
phigh
Rs R& (nigi))))
[Id + Riz (Aiigh) ( Aregutar] |111
philsh
Id +
A Augular
[Td Rs (Arigh) Aregnar)
+
Hence remains to bound the left hand summand. For this we use the following fact (c.f. Hoon & Johnson 2012). Section 5.8. "Condition numbers: inverses and linear systems"):
Given square matrices A, B, C with C B A and | < 1, we have
- |
||
B
A C
In our case, this yields (together with |
1) that
Id + phigh ((-2) Arguter
[Id + R. (Anigh Areuuarr
(1 Argularr 1/21)/ 2 regular|
plus
R. (Anigh))
(1 regutar /|=/) A Drgular
R2 (nigh))
For sufficiently large, we have
- Phish// /2- R. (nigh))))) $
1
2(1 + || 1/
so that we may estimate
phigh
Id + A Aregular
[Id A Aregutar Ri (Arigh))
phigh
2 (1 + Aregular
R2 (Aiigh))
-0
Thus we have now established
hiihh
high
Id +
A
regular
(A( 0.
Hence done with the proof, as
establish
=Id + phigh
phigh = J'R
Dregitar
23

---

Published as a conference paper at ICLR 2024
with J/, A J defined above. To this end, we first note that since the left-kernel and right-kerell of nigh are the same (since in-degrees are the same as out degrees), we have
J J.JJ_ Pouph
(12)
and
J Idg.
(13)
Indeed,the relation (12) follows from the fact that the eigenspace corresponding to the eignvalue zero is spanned by the vectors {1 R. with (R) the reaches of Ghgh (c.f. Veerman & Lyons (2020)) Equation (33) follows from the fact that
(In, (R)1R) = En.
With this we have
Id phigh Amgular]
-1 phich
[Td JJ A ngudtr] ] J
To proceed, set
:= F
and
2. phigh Arguilor zld
phigh x.
Then
(piish A Aregiarr Td x phish,
and hence 2' Ran( plish) Thus we have
J J regular =Id)J' 2 = =
Multiplying with J from the left yields
J regulur -=Id)J g. J&z.
Thus we have
(J+ Argulard - zId) --= Jtx.
This in turn implies
J. x. [egglegulardt -zd]] J.C.
Using
phish Φ -i
we then have
x= = Jt [ A - 2Id] -1 J.z.
We have thus concluded the proof if we can prove that J Aregnlar Jt the Laplacian corresponding the graph G defined in Definition F.1 But this is straightforward calculation.
As corollary, we find Corollary F.4, We have
R.(A)* - J'R'
Proof. This follows directly from the fact that
JJJt Idc.
This thus establishes Theorem
3.4
24

---

Published as a conference paper at ICLR 2024
G STABILITY UNDER SCALE VARIATIONS
Here we provide details on the scale-invariance results discussed in Section most notably Theorem
In preparation, we will first need to prove a lemma relating powers of resolvents on the original graph G and its limit-description G: Lemma G.1. Let R. (A -=ld)= and Rs == (A - =Id)= -1, For any natural number k, we have
1 J R. J² R l [JR 1 & k -
for
[RA <A
Proof. We note that for arbitrary matrices T, T, we have
Th T ( - T) -
-7 - - T) T 2 - TYT + (T -
Iterating this, using the fact that [A) stays bounded as c + 0,, since
[ - || (2(A) &
for some constant together with ||J || J4|| < and
Jt P (J'
(which holds since JhJt Idg) then yields the claim.
Hence let us now prove a node-level stability result:
Theorem G.2. Let & and 2, be the maps associated to Dir-ResolyNets with the same learned weight matrices and biases but deployed graphs G and G as defined in Section 3.3.2 We have
1 (J-X)] & (C,(W, A) |X|2 C2(W B, A)) [2())) J R. (A)++) (14)
with A a constant such that
|R & A.
Proof. Let define
Let us further use the notation R. : (A - 2ld) and Rg = (A =ld)-1
Denote by X and X the (hidden) feature matrices generated in layer e for networks based on resolvents Rg and R, respectively: Le. we have
K
x = p
Σ
Rb Rxxx* x 8-
Bº
and
K X p
Σ
x
We B²
Here, since bias terms proportional to constant vectors the graphs, we have
J = B
and
J'B B
(15)
for bias matrices B and B in networks deployed on G and G respectively.
25

---

Published as a conference paper at ICLR 2024
We then have
(X) - (
-188
K
K
Σ
R xL- + B²
-Jip Σ
R R -- X +
B²
K
R x -- W + B².
J R X
W + B².
Here we used the fact that since p(-) maps positive entries to positive entries and acts pointwise, commutes with JT We also made use of (5). Using the fact that p(-) is Lipschitz-coome continuus with Lipschitz constant D 1, we can establish
K
K
(x)()) - 11
Σ
R x
W
Σ J
Using the fact that S4,l = Idg. we have
K
(' &
-
From this, we find (using |1'| & 1 ), that
x - 11
K
K
Σ 1 x L- -
k=0
Σ R (JI
+ Σ | 1 x 1
Σ (R (J' W
+ -1 - X
[ - (J' ( -J' 1 || -1 8 xL-11
Applying Lemma G.I yields
| - 1
K
(k. 1 w |R= - (J'R. 1|2-11 + || 1 FL -
&
Similarly, one may establish that we have
| < C(A) (1D*) + Σ [
1- | [1 12
-IIXI)
(16)
W== 1-0
Hence the summand on the left-hand-side can be bounded in terms of a polynomial in singular values of bias- and weight matrices, as well as |||]| A and most importantly the factor R (J" R. J
26

---

Published as a conference paper at ICLR 2024
which tends to zero.
For the summand on the right- right-hand-ae sidd- we can iterate the above procedure (aggregating terms like
116 multiplied by [R= (J) R.,++)) (+)l until reaching the last layer L 1. There observe
X X
K
K J + B¹) )
R XX + +B²
-1pp
>
P
K
R X Σ J
Σ (R - J J.)
(k: (k.
(1 - -IX
The last step is only possible because we let the sums over powers resolvents start at = as opposed to a 0. In the latter case, there would have remained term |X - J1J X||, which would
not decay as c - :0.
Aggregating terms, we build up the polynomial stability constants of (4) layer by layer, and complete the proof.
Next we transfer the previous result to the graph level setting:
Theorem G.3. Denote by Ω the aggregation method introduced in Section With p(G) -i 14g the total weight of the graph G, we have in the setting of Theorem G.2 that
[9((2 2 (Q lla
<VM(G) (C(W,,) || C2(W B, A)) -
Proof. Let us first recall that our aggregation scheme Ω mapped a feature matrix E R NxF to graph-level feature vector (XX) IR defined component-wise
2(X),
X pr-
In light of Theorem G.2 we are done with the proof, once we have established that
|| (X) a (2, 12 < VV(G) ((xr(X) (1
To this end, we first note that
2(J'X) 9(X).
Indeed, this follows from the fact that given reach R in Gnight the map J assigns the same feature vector to each node r R C G (c.f. (II)). together with the fact that
Σ Mr.
PR
PER
Thus we have
- (00):))))-(((00))000000000000100
Next let us simplify notation and write
= = (x())
and
B JJ
27

---

Published as a conference paper at ICLR 2024
with A, N We note:
[0() Q
=
Σ J-1
((1A)
(B
By means of the
inequality together with the inverse triangle-inequalig. have
Σ
Σ (1Atg] - (Byl))
$
AAg Bigl² M4
Σ 14
Σ
Asy Buyl ps =(G).
Since we have
(x)(X) - J'
Σ
Σ Ais - 3. pei
the claim is established.
H PROOF OF THEOREM 4.
Here prove Theorem which restate here for convenience:
Theorem H.1. Suppose for filter banks (Dp////wwd ylaareed that the matrices Tf (T), (T con- tain only real entries. Then any HoloNet with layer-widths {Fr} with complex weights & biases and a non linearity that acts on complex numbers componentwise as p(a + ib) = p(a) + ip(a) can be exactly represented by HoloNet of widths (2 Fe) utilizing ğ and employing only real weights & biases.
Proof. It suffices prove, that in this setting the update rule
x² = (p (ind(()) x w.fddde + +(1 a) Σ (huud(rr) x w.oud. + 1z
can be replaced by purely real weights and biases. For simplicity in notation, let assume the general case follows analogously but with more cluttered notation.
Let us write Xreat + iXimag W Wreat iWimag- B Breat BBiaagg Then have with (T) (T) purely real, that
x = p
twd (T) x w.wde + Be
f.udd (T) Ax-a
w-f-d reat.5
Ximag wrodd (mag..) Be Bleat
p
v fuud (T) (Xfel smag.s + X.mma wead.)) Bl Blrmag +
y food (T)
(x wiude Xiina Wiidde imag..) Breat
p
ip
T (fud(() (Xt-Iwfudd imag.
X
Kimag
Wriddd real.))
+ Bf Biiag
seT
The result then immediately follows after using the canonical isomorphism between Cddd and R22d as
((wd(T) (x reat,i X W (mag, + Bf
X
x
(17)
X Xmmgg
Σ fud (T)
(x W flw.e + X w.wwd.ey + Bimagg
28

---

Published as a conference paper at ICLR 2024
The above layer update
x--1 X f-1 imag
X real X immag
can then clearly be realised by a real network as described in Theorem 4.1
I ADDITIONAL. DETAILS ON EXPERIMENTS:
1.1 FABERNET: NODE CLASSIFICATION
Datasets: We evaluate on the task of node classification on several directed benchmark datasets with high homophily: Chameleon & Squirrel (Pei et al. 2020), Arxiv Year (Hu et al. (0200)), Snap- Patents (Lim et al. (20TT) and Roman- Comann-Empire (Platonov et al. 2023). These datasets are highly heterophilic (edge homophily smaller than 0.25).
Table Node Classification Datasets: Statistics
DATASET
NODES
# EDGES
FEAT.
#
UNID. EDGES
EDGE HOM.
CHAMELEON
2,277
36,101
2,325
5
85.01%
0.235
SQUIRREL
5,201
217.073
2,089
90.60%
0.223
ARXIV-YEAR
169,343
1,166,243
128
99.27%
0.221
SNAP-PATENTS
2,923,922
13,975,791
269
5
99.98%
0.218
ROMAN-EMPIRE
22,662
44,363
300
18
65.24%
0.050
Experimental Setup All experiments are conducted on a machine with NVIDIA A4000 GPU with 16GB of memory, safe for experiments on snap-patents which have been performed machine with one NVIDIA Quadro RTX 8000 with 48GB of memory. We closely follow the experimental setup of (Rossi et al., 2023). In all experiments, we use the Adam optimizer and train the model for 10000 epochs, using early stopping on the validation accuracy with patience of 200 for all datasets apart from Chameleon and Squirrel, for which we use a patience of 400. For OGBN-Arxiv we use the fixed split provided by OGB (Hu et al.) (020b), for Chamelcon and Squirrel we use the fixed GEOM-GCN splits (Pei et al. 2020), for Arxiv- Year and Snap-Patents we use the splits provided in while for Noman-Empiin we use the splits from Platonov al. (2023)
Lim et al. (021),
and LINKX were taken from Lim ct al.] Results for Gradient Gating are taken from their paper (Rusch et al. 2023). Results for GloGNN taken from their paper (Li al. 2022). Results Roman-
Baselines Results: Results for MLP, GCN, H₂GCN,
taken from Platonov
jet al. (2023) for GCN, H,GCN, GPR- GNN, FSGNN and GloGNN and from Rossi et al.) (023) for MLP, LINKX, ACM-GCN and Gradient Gating. Results for FSGNN are taken from Maurya al.
(2021) for Actor, Squirrel and Chameleon, and from Rossi et al. (2023) for results on Arxiv-year and Snap-Patents. Results for DiGCN. MagNet are taken from Rossi et al. (202)). Results for DirGNN were obtained via re-implementation; using the official codebase and hyperparamters specified in (Rossi al.| | (003)). Note that as detailed in Rossi et al. (2023) the reported results for DirGNN correspond to best-of-three report over directed version of GCN (Kipf & Welling, 2017). GAT
(Velickovic et al. 2018) and Sage (Hamilton et al. 2017).
Design Choices: Some design choices made in Section warrant an additional discussion:
Separation of forward and backward filters
Choice of zero-diagonal for T
Choice of normalization in T as T ) W. (D as opposed to the more traditional square-root normalization in T = (D W (Dow))
Choice of non-linearity: |. ReLu.
29

---

Published as a conference paper at ICLR 2024
We here provide the corresponding discussions:
In principle, the need to consider both forward- and backward-filters arises from the nature of directed graphs: If say- only forward filters would be implemented, information would only be allowed to flow along the directed edges of a given graphs. In a citation network (with the characteristic operators T chosen e.g. the adjacency matrix graph Laplacian) for example, this would only endow a given node representing a specific paper with information about papers that the given paper cites. The (equally important) information about papers that cite the given one never reaches the node of our fixed paper. This can be remedied by not only considering filters based on T, but also its transpose T One can consider T as describing the original graph. with all edge directions reversed, so that T* facilitates information flow in exactly the opposite direction when compared with T. In principle, one could then be tempted try to implement filters as functions f(z, y) in two complex variables (æ: and y) and make the replacements -- T and y - T*, thus implementing a joint filter [T, T*) for both directions simultaneously. However, such procedure is unfortunately mathematically ill-defined Kato (976): Consider for example the function fzz u) = zy = yz. It is then not clear we should set T*T = T T or f(T,T") = T T. This would not be a problem if T T T
. T and one may indeed prove
that in this setting, one might consistently define the matrix fTT the relevant tool here is the "Functional calculus for commuting operators". In general however, we have 7 T +f T T if T describes a directed graph. Hence we can not construct such a joint spectral filter J(T, T*)) and instead consider learnable spectral filters of the form f(T) + g(T*). In principle, one may of course also consider other algebraic combination of the two directions of information flow (such as c.g. f(T) g(**)) and g(1*). f(T).. We however leave this for future work.
To avoid comparing the features of surrounding nodes with the feature vector of a given node when applying the characteristic operator T (or powers T of T) to the feature matrix X as T X, we choose I' to have only the entry zero on the diagonal. This is done, as FaberNet is designed for node-classification on heterophilic graphs. Thus, when updating the feature vector given node, the previous feature vector of this node is discarded, and the new feature vector is solely made up of the
of information about surrounding nodes (i.c. information about the neighbourhood((tructun original node). This avoids a mixing of self-features and neighbourhood features, which is desireable as Maurya et al. 2021] pointed out theoretically, and we also observed empirically in our experiments. Hence choose T as (some form of) the adjacency matrix, it has
diagonal.
Different from the normalization of T that we have chosen, a symmetric normalization such as T (D W. -D"'') -1. might arguably be considered more traditional. 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 the original undirected spectral models such as Bruna et al. (2014): Defferrard et al. (2016); Kipf & Welling (2117). A main point of the present paper however, is transcending this graph Fourier transform. as the traditional approach is limited 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, traditional holding-on-to a normalization stemming transforms is no longer necessary. As
from traditional use of a Laplacian-based observed experimentally, such a traditional normalization is also (slightly) disadvantageouss, as far as performance is concerned.
Arguably, a majority of the machine learning literature in general uses some form of (leaky-) ReLU activations. In the graph setting, an exception is constituted by graph-scattering networks (c.f. e.g. Perlmutter et al. (2019); Koke & Kutyniok (2022)): ): Corresponding scattering architectures are based on the absolute-val walue-noonineeeee 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. [ee et al. (2022). Hence we consider two possible choices in our architecture, whenever we enable complex parameters (c.f. also Table 7 beloow.
For us, the choice to use either ReLu or the absolute value
Hyperparameters: Following the setup of Rossi et al. 2023), our search space for generic hyper- parameters is given by varying the learning rate Ir E {0.01, 0.005, 0.001, 0.0005). the hidden dimen- sion over F (32, 64, 128, 256, 512], ne number of layers over L E (,,3, 4, 5, 6), jumping knowl- edge connections over jk E {maz, cat, n layer-wise normalization in norm E (True, False), patience as patience E (200, 400) and dropout as p e 0., 0.4, 0.6, 0.8, 13.
30

---

Published as a conference paper at ICLR 2024
Table Final Generic Hyperparameters
DATASET
lr
PATIENCE
NORM
JK
CHAMELEON
0.005
400
128
TRUE
CAT
SQUIRREL
0.01
400
128
TRUE
MAX
ARXIV-YER YEAR
0.005
200
256
FALSE
CAT
SNAP-PATENTS
0.01
200
32
TRUE
MAX
ROMAN-EMPIRE
0.01
200
256
FALSE
0.2
CAT
In practice we take the parameters of Table as frozen and given by Rossi et al. (2023). We then optimize over the custom hyperparameters pertaining to our method. To this end, we vary the maximal order of our Faber polynomials { ( ( as K E {1,2, 3, 4, 5). Note that we also discount higher 1/2*, this improved results experimentally. We thus have VR x*/2². 'he type of weights & bisases varied over parameters E (R, C). The non-linearity varied over {1- |c. ReLu), with |a + üblc |a + 2/6]. The parameter a is varied a (0, 0.5, 1} as in Rossi et al. (2023). The zero-order Faber polynomial ()(A) = is either included or discarded, as discussed Section 4 and weight decay parameters for real- and imaginary weights are varied over A Aimag E {0, 0.,0.1, 1]. Final selected hyperparameters are listed in Table
order terms with regularization
Table 7: Final Custom Hyperparameters
DATASET
K
PARAMETERS
NON.-LIN.
Vo
ABEAL
CHAMELEON
4
C
lc
0
No
1
0
SQUIRREL
5
C
lc
0
No
0.1
0.1
ARXIV-YEA YEAR
R
RELU
0.5
No
0.1
N.A.
SNAP-PATENTS
RELU
0.5
0.1
N.A.
ROMAN-EMPIRE
R
RELU
0.5
YES
0.1
N.A.
1.2 HIR-RESOLYNET: DIGRAPH REGRESSION AND SCALE INSENSITIVITY
Dataset: The dataset we consider is the QM7 dataset, introduced in Blum & Reymond (2009); Rupp al. (2012). This dataset contains descriptions of 7165 organic molecules, each with up to seven heavy atoms, with all non-hydrogen atoms being considered heavy. In the dataset, given molecule is represented by its Coulomb matrix W. whose off-diagonal elements
2,2,
W E - 33
(18)
correspond to the Coulomb-repulsion between atoms and j. We discard diagonal entries of Coulomb matrices; which would encode polynomial fit of atomic energies to nuclear charge (Rupp al. 2012).
To each molecule an atomization energy calculated via density functional theory is associated. The objective is to predict this quantity. The performance metric is mean absolute error. Numerically, atomization energies are negative numbers in the range 600 -2200. The associated unit is [kcal/mol].
For each atom in any given molecular graph, the individual Cartesian coordinates F, and the atomic charge Z; are also accessible individually.
Weights only from heavy atoms to aloms outside this heavy atom's respective immediate hydrogen cloud are modified as
In order induce directedness, we modify the Coulomb weights (8)
Zoutside
W
(19)
The immediate hydrogen cloud a given heavy atom, we take to encompass precisely those hydrogen atoms for which this heavy atom is the closest among all other heavy atoms.
31

---

0... Published as a conference paper at ICLR 2024
This specific choice (19) is made in preparation for the scale insensitivity experiments: The theory developed in Section 3.3.2 applies to those graphs, where strongly connected subgraphs contain only nodes for which the in-degree equals the out-degree (where only strong weights considered when caleulating the respective degrees). The choice (19) facilitates this, as hydrogen-hydrogge weights and weights between hydrogen and respective closest heavy atom remain symmetric.
We shuffle the dataset and randomly select 1500 molecules for testing. We then train the remaining graphs. We run experiments for 5 different random random seeds and report mean and standard deviation.
Experimental Setup:
All considered convolutional layers (i.e. for Dir-ResolvNet and baselines) incorporated into two layer deep and fully connected graph convolutional architecture. In each hidden layer, we set the width (i.e. the hidden feature dimension) to
F = F2 = 64.
For all baselines, the standard mean-aggregatioon scheme is employed after the graph-convolutional layers generate graph level features. Finally, predictions generated via an MI.P
For Dir-ResolyNet, we take a 1, use real weights and biases and set 2 = -1. These choices are made for simplicity. Resolvents are thus given as
R-) (A+
As aggregation for our model, we employ the graph level feature aggregation scheme introduced before Theorem 4.2 in Section 4 Node weights set atomic charges of individual atoms. Predictions are then generated via a final MLP with the same specifications as the one used for baselines.
Scale Insensitivity We then modify (all) molecular graphs in QM7 by deflecting hydrogen atoms (H) out of their equilibrium positions towards the respective nearest heavy atom. This is possible since the QM7 dataset also contains the Cartesian coordinates of individual atoms.
This introduces a two-scale setting precisely as discussed in section 3.3.2 Edge weights between heavy atoms remain the same, while Coulomb repulsions between H-atoms and respective nearest heavy atom increasingly diverge; as is evident from (18).
Given an original molecular graph G with node weights 14 Z, the corresponding limit graph G' corresponds to a coarse grained description, where heavy atoms and surrounding H-atoms are aggregated into single super-nodes in the sense of Section 3.3.2
Mathematically, G is obtained by removing all nodes corresponding to H-atoms from G, while adding the corresponding charges Zh 1 the node-weights of the respective nearest heavy atom. Charges in (19) are modified similarly to generate the weight matrix W.
On original molecular graphs, atomic charges are provided via one-hot encodings, For the graph of methane consisting of one carbon atom with charge Zc = 6 and four hydrogen atoms of charges Zu the corresponding mode-feature-matrr e.g. given as
0 0
0 1 0...
1
0 0
0
X
1 0
0
0
0...
0 0
0 0 0...)
with the non-zero entry in the first row being in the 6th column, in order to encode the charge Zc = for carbon.
The feature vector of an aggregated node represents charges of the heavy atom and its neighbouring H-atoms jointly.
As discussed Section 3.3.2. node feature matrices are translated as X = Jtx. Applying J to one-hot encoded atomic charges yields (normalized) bag-of-word embeddings on G: Individual entries of feature vectors encode how much of the total charge of the soder-node contributed by individual atom- In the example of methane, the limit graph G consists of single node with node-weight
/ + 1
1
10.
32

---

Published as a conference paper at ICLR 2024
The feature matrix
==J-X
a single row-vector given as
X (4 (100
6 10"
0, ,0, 0, 0,....
1.3 EFFICIENCY ANALYSIS:
Here compare the efficiency of our model with the directed baselines of Section 5
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 F hidden dimensions in our architectures.
Complexity:
DiGCN: In its full form, DiGCN has O(N2) complexity, which is reduced to O(EFC) complexity its approximate propagation scheme, which used in practice.
DirGNN: Similarly, DirGNN possesses a (EFFC). In both cases this stems from the pparse-dense matrix multiplications that facilitate the forward function.
MagNet: MagNet is similarly implemented via sparse-dense matrix multiplications; resulting in an O O(EFCtycomplexity
Since FaberNet too implements its forward using sparse-dense matrix multiplications, its filtering operation also has OEFCC) complexity.
FaberNet:
Dir-ResolyNet: The filtering operation in Dir-ResolvNet is implemented as dense-dense matrix multiplication, and as such has complexity ((N2) like the full (not approximated) forward operation of DiGCN would have.
Number of trainable parameters: 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 as many real parameters as DirGNN. Here K refers the highest utilized order of Faber polynomials (4 Ju- In experiments, the maximal attained value of K was K = 5 on the "Squirrel" dataset (c.f. Table 7 On this dataset, complex weights & biases performed best, so that our method has 6.3 M trainable parameters with the configuration specified in Table
33

---

Published as a conference paper at ICLR 2024
J PSEUDOCODE
In this section we provide a pseudocode deseription of the forward function implemented within standard Holonet. Using the notation of Section we first recall the corresponding update rule:
X ((a Σ
(T) x W.ldd (1 a)
(T"* X W B
(20)
In practice, full forward pass within standard HoloNet is then implemented described in Algorithm below:
Algorithm 1: The forward function HoloNets
Data: Basis functions Vofwd (T),
(T*) (T** evaluated at T, T* (precomputed; for
1 E & I Network depth L E IN; Feature dimensions Fe (for 0 & l & L);
Weighting parameter [0, 1]: Biases B B.wahhddf (for & & Mfwdd/bwd and & l L);
Weight matrices f.fdd/bdd.e of dimension Fg x Fe+1 (for & & MIwd/bwd and
1 1 1
Input: Node-feature matrix X
Output: Sina--ayyr-features H
H - X;
for 1 & & do
H' < a. Linear(matmann (T), H wiinde Bludd.); (f
H < H (1 (1) Lincar(mattull (TD HC-1), wiidde Blidd,e);
if Mfwd > 2 then
for 2 & i & Mfvd do
H H + (aateallmmtmmll(( H wfidde Bluddt):
end
end
> then for 2 s & Mudd do
pwdd
Hº - H² (1 - a). Linear Linear(mattmul()umu H wowd. B.bwd..)
end
end
H p
end
return H
Note that the bias term B
20
is related to the individual bias terms in Algorithm as
And
M bod
B
twd
Bbwd
where biases are broadcasted to nodes to match the dimension of 11*
34


Reviews:
[{"review_id": "6sY90lu0N8", "reviewer": "Reviewer_tzrV", "summary": "This paper studied the problem of designing graph filters for directed graphs. Instead of following the same approach for undirected cases (first define the spectrum based on Graph Fourier Transform, then define the filters based on spectral responses), the authors proposed to analyze the relationship between spectral response $g(\\lambda)$ and graph filter $g(T)$ directly when function $g$ comes from some constrained set. By observing an interesting connection between this problem and results from functional calculus, this paper presented a principal design for directed graph filters and two feasible approximations: faber polynomials and resolvent. Furthermore, the stabilities of these graph filters are established, and the simulations show that the new method outperforms other directed GNN baselines over several benchmark datasets.", "questions": "Besides the ones listed above, I have the following questions as well:\n\n1. What is the choice of $y$ for Dir-ResolvNet?\n\n2. Why is the normalization for $T$ $-1/4$ not $-1/2$? If in undirected case, I believe the practice is to use $D^{-1/2}$. Why is there a discrepancy? Also, I am not sure how this is related to the motivation stated in the paper \"We thus use as characteristic operator a matrix that avoids direct comparison of feature vectors of a node with those of immediate neighbours\".\n\n3. Where do the imaginary weights in FaberNet come from? Is it because the eigenvalues can be complex?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "I believe the most important contribution of this paper is that the authors point out the fact that we do not really need Graph Fourier Transform to define graph filters, which has always been an obstacle in graph learning and signal processing community due to the non-symmetric nature of directed Laplacian. The literature review and observations presented in this paper can be viewed as a general guidance to design convolutional kernels for directed graphs, and lay the theoretical foundations for other future works on this subject. Following the general design, this paper also introduced two computationally feasible filter banks to implement the directed graph kernels in practice, which achieves good results on standard benchmark datasets.", "weaknesses": "Although the technical insights shown in this paper are great and very interesting, the presentation of this paper, especially the main text, can be improved. I understand that the authors want to convey as much information as possible within the main text, but the main goal of this paper, which is the implementation of the practical directed convolutional kernels (layers), should still be explained clearly in detail. 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. In other words, even 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? Do we still have to consult Eq (3) to compute $\\Psi_k(T)$, which can be computationally expensive? This type of question should be clearly explained in the main text to help readers better understand the big picture. A pseudocode of the algorithm/training procedure can help solve this issue.\n\nBesides the computation of graph kernels, some of the heuristic choices adopted in Holonets lack theoretical insights as well. For example, why do we need to use forward and backward filters separately? Why the operator is chosen to be $T=(D^{in})^{-1/4}W(D^{out})^{-1/4}$? Why use absolute value as the nonlinear activation, which is unusual in GNN literature? 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.\n\nOne 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.\n\nTwo other small comments: 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; on page 5, \"Faber polynomials provide near near mini-max polynomial approximation\" there are two \"near\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fbXpdTnXDK", "reviewer": "Reviewer_RxaJ", "summary": "This paper introduces a novel approach to extending spectral graph neural networks (GNNs) from undirected graphs to directed graphs. \nInstead of leveraging the traditional Graph Fourier Transform, this paper employs the holomorphic function to avoid the self-adjoint requirement. This paper further discusses the significance of this extension, highlighting its frequency-response interpretation and the basis used to express filters. Finally, the proposed method, namely FaberNet, is validated through experiments on diverse datasets.", "questions": "Replacing $\\lambda$ with $T$ yields equation 2. I wonder what $d$ indicates in $T - z \\cdot I d$? This symbol seems to conflict with the differential symbol.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a new direction for designing spectral GNNs in directed graphs, i.e., holomorphic functions, which can preserve the algebraic relations to construct the polynomial filters.\n\n2. The authors give sufficient justifications to verify the advantages of holomorphic functions, convincing me about their effectiveness.\n\n3. The proposed FaberNet consistently outperforms other directed GNNs in both heterophilic node classification and regression tasks.", "weaknesses": "I'm concerned about the datasets used in the node classification task. 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.\n\nSince extending spectral GNNs to direct graphs mainly relies on the modification of eigenvectors, I think the choice of filters should not be the major reason to affect the model performance.\n\nIt would be better if the authors could provide more experimental results in the homophilic graphs to validate the effectiveness of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SKh4Yw7XHq", "reviewer": "Reviewer_T8Vv", "summary": "This paper targets the limitation of conventional Graph Neural Networks (GNNs) that struggle with handling directed graphs effectively. The objective is to enhance spectral convolution networks to cater to directed graphs, thereby eliminating reliance on the Graph Fourier Transform. The proposed method's effectiveness is confirmed through experiments conducted on real-world datasets.", "questions": "Please reply to questions in weaknesses.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is novel and has theoretical depth.\n2. The proposed method is technically sound.\n3. The paper is well-written and easy to follow.\n4. The proposed method achieves SOTA performance in several real-world directed heterophilic datasets.", "weaknesses": "I am not an expert in spectral GNNs thus I could only point out a limited number of issues in the experiments:\n1. It would be good to examine the efficiency of the proposed method, especially when compared with DiGCN and DirGNN. Moreover, a discussion on the number of learnable parameters would be beneficial.\n2. The impact of the number of layers on the model's performance is worth exploring. Do we have the same problem of over-smoothing in directed graphs when the GNN goes deeper?\n3. Did HoloNet outperform the baselines in graph classification tasks? More evaluation tasks could be investigated.\n\n\nOverall, I think it's a good paper ready for publication at NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6i0HEtUmHx", "reviewer": "Reviewer_XGUM", "summary": "This paper introduces spectral convolutions to directed graphs without relying on the graph Fourier transform. The paper provides a frequency-response interpretation of the proposed filters with a theoretical analysis. Experimental results seem promising.", "questions": "1) The formulation seems to be restricted to one-dimensional node weights for the nodes. What modifications should be made if we are given multiple-dimensional node features?\n2) What is the computational complexity of HoloNets compared to DiGCN, MagNet, and Dir-GNN?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The usage of holomorphic functional calculus to introduce directed graph filters is novel.\n2) Directed graphs are important to consider.\n3) Theoretical analysis seems sound.\n4) The proposed method seems effective and expressive.", "weaknesses": "1) 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.\n2) The underlying reason for using holomorphic functional calculus has not been clearly demonstrated.\n3) Some typos exist. For example, in the \"Contributions\" part at the end of Sec. 1, there is one redundant \"the\" in line 6; in the second paragraph of Sec. 3.3.1, there is one more \"near\" in line 5; there should be an 'as' after 'referred to' right after equation (5) on page 17; the first 'eigenvalue' should indeed be 'eigenvector' in Sec. C on page 17; 'interpreting' should be 'interpreted' right after the mention of Appendix B on page 18.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)