Spectro-Riemannian Graph Neural Networks
Authors: Karish Grover
Haiyang Yu
Xiang song
Qi Zhu
Han Xie
Vassilis N. Ioannidis
Christos Faloutsos
Venue: ICLR 2025 Poster (2025)
Keywords: Graph representation learning
Spectral graph theory
Riemannian geometry
Non-Euclidean graph neural networks
Geometric deep learning
Primary area: learning on graphs and other geometries & topologies
TL;DR: A novel mixed-curvature spectral GNN that unifies both curvature (geometric) and spectral insights for learning graph representations.

Abstract: Can integrating spectral and curvature signals unlock new potential in graph representation learning? Non-Euclidean geometries, particularly Riemannian manifolds such as hyperbolic (negative curvature) and spherical (positive curvature), offer powerful inductive biases for embedding complex graph structures like scale-free, hierarchical, and cyclic patterns. Meanwhile, spectral filtering excels at processing signal variations across graphs, making it effective in homophilic and heterophilic settings. Leveraging both can significantly enhance the learned representations. To this end, we propose Spectro-Riemannian Graph Neural Networks (CUSP) - the first graph representation learning paradigm that unifies both CUrvature (geometric) and SPectral insights. CUSP is a mixed-curvature spectral GNN that learns spectral filters to optimize node embeddings in products of constant curvature manifolds (hyperbolic, spherical, and Euclidean). Specifically, CUSP introduces three novel components: (a) Cusp Laplacian, an extension of the traditional graph Laplacian based on Ollivier-Ricci curvature, designed to capture the curvature signals better; (b) Cusp Filtering, which employs multiple Riemannian graph filters to obtain cues from various bands in the eigenspectrum; and (c) Cusp Pooling, a hierarchical attention mechanism combined with a curvature-based positional encoding to assess the relative importance of differently curved substructures in our graph. Empirical evaluation across eight homophilic and heterophilic datasets demonstrates the superiority of CUSP in node classification and link prediction tasks, with a gain of up to 5.3\% over state-of-the-art models.

Published as a conference paper at ICLR 2025
SPECTRO-RIEMANNIAN GRAPH NEURAL NETWORKS
Karish Grover': Haiyang Yu', Xiang Song', Qi Zhu', Han Xie Vassilis N. Ioannidis', Christos Faloutsos'
'Carnegi Mellon University, Texas A&M University, AAmaoon (karishg, christos @css cmu, edu, {haiyang] amu edu, (xiangsx, gzhuamzn, hanxie, i vasilell aasasleee@aaaaaa @amazon com
ABSTRACT
Can integrating spectral and curvature signals unlock new potential in graph rep- resentation learning? Non-Euclidean geometries, particularly Riemannian mani- folds such as hyperbolic (negative curvature) and spherical (positive curvature), offer powerful inductive biases for embedding complex graph structures like scale-free, hierarchical, and cyclic patterns. Meanwhile, spectral filtering excels at processing signal variations across graphs, making it effective in homophilic and heterophilic settings. Leveraging both can significantly enhance the learned Graph Neural Net-
representations. To this end, we propose works (CUSP) - the first graph representation learning paradigm that unifies both CUrvature (geometric) and SPectral insights. CUSP is a mixed-curvature spec- tral GNN that learns spectral filters to optimize node embeddings in products constant-curvature manifolds (hyperbolic, spherical, and Euclidean). Specifically, CUSP introduces three novel components: (a) Cusp Laplacian, an extension of the traditional graph Laplacian based on Ollivier-Rice curvature, designed to capture the curvature signals better; (b) Cusp Filtering, which employs multiple Rieman- from various bands in the eigenspectrum; and (c) Cusp Pooling, a hierarchical attention mechanism combined with a curvature- based positional encoding to assess the relative importance of differently curved substructures in our graph. Empirical evaluation across eight homophilic and het- erophilic datasets demonstrates the superiority of CUSP node classification and link prediction tasks, with gain of up to 5.3% over ffate-of-the-eeee art models. The code is available at: pnttps://qiit
nian graph filters to obtain
com/ ama zon www.ecceeeeeueeeeo cusp
INTRODUCTION
Graph representation learning has garnered significant research interest in recent years, owing its fundamental relevance in domains such as natural language processing (Mihalcea & Radev 2011). biology (Zhang al. (202aa), and social network analysis (Grover et al.) [2022]. Recent advances have rigorously examined constant curvature spaces to learn distortion-free graph representations, as they provide suitable inductive biases for particular structures while avoiding the intrinsic problems of very high dimensionality. For example. hyperbolic space (negative curvature) is optimal for hierarchical tree-like graphs (Chami et al.] 2019). while spherical geometry (positive curvature) is best suited for cyclic graphs (Gu et al., 2019).The idea behind all Riemannian GNNs is that optimal embeddings are achieved when the underlying manifold's curvature aligns with the graphs' discrete curvature. To model real-world graphs with complex topologies that cannot be adequately represented within a single constant-curvatury manifold, various mixed-curvature GNNs have been proposed, that operate across multiple manifolds (Zhu et al. 2020).
Despite their success in managing complex graph topologies, existing mixed-curvature GNNs still have significant limitations (Figure (b)). (a) L1 (Low-pass filtering bias): State-of-the-ae mixed- curvature Riemannian GNNs, such as RGCN (Bachmann et al., 2020) and QGCN (Xiong et al.] 2022), inherently mimic low-pass spectral filters. These models are adaptations of the Euclidean GCN (Kipf & Welling, 2016) to Riemannian manifolds, which are known to operate under the ho- mophily assumption (low-pass filters) predominantly. Consequently, their performance degrades on
The work was done during Karish Grover's intersship at Amazon, US.

---

Published as a conference paper at ICLR 2025
(opeehata) (Taclleea) (Splnckal)
(BooggHy))
[Boregghily]
Syectron
Out
somos
Chavature Vistiburiio
Frequcacy Ditiibatio
Queer of
ieprosstatiie
Piiuerty
Cuza
2315
Geunetey
14
1o
o0 Oeg/Al)
Chamesonn
Coest Rddee
axtc
Pullscom
Low pais
Spectrom
(batA))
Cf MApe
Year
Specral Sorpe
Toxss
Aca
Riemannian GNN
Spectral GNNG
(ag(Al)
(b)
Figure 1: Motivation behind CUSP. (a) Diversity of curvatures (-ve +ve and frequencies in homophilic (Cora) and heterophilic (Texas, Chameleon) real-world graphs (Section 5). (b) Spectral GNNs overlook the curvature, whereas Riemannian GNNs are restricted by a cut-off frequency. CUSP aims for the best of both rich geometrie representation full access to the spectrum.
graphs with varying degrees of heterophily. (b) L2 (Task-specific relevance of curvature); Different datasets and tasks may emphasize more on different curvatures within a graph (Figure T (a)). For example, the task of community detection focuses on clustered nodes typically associated with a positive curvature (Tian et al., (023). In contrast, fake news detection on social media graphs priori- tizes tree-like cascade structures characterized by a negative curvature (Grover et al. 2022). Current models do not adapt curvatures to tasks. (c) L3 (Lack of geomelry-equuivvriaee in spectral GNNs):
Spectral GNNs like BernNet (He et al. (02T) and GPRGNN (Chien et al. (020) incorporate flexible graph filters to learn representations based on different parts of the eigenspectrum but assume a flat Euclidean manifold, ignoring the underlying geometry. As the geometry of the graph changes, these filters should adapt to reflect the changing geometric properties, which is currently not the case.
To bridge these gaps, introduce CUSP, a mixed-curvaiiee spectral GNN that operates a prod- uet manifold composed of multiple constant- -ettaatte spaces and computes geometrically and spec- trally parameterized graph filters. We begin by introducing the (a) Cusp Laplacian, curvature- aware Laplacian operator for graphs, inspired by the equation of heat flow (Thanou et al. 2017) and the discrete Ollivier-Ricci curvature (Ollivier 2007). At the core our approach is (b) Cusp Filtering, where we propose filter bank consisting of multiple mixed-curvature graph filters to en- sure that our GNN captures information from multiple bands in the eigenspectrum. Using the Cusp Laplacian, we extend the generalized PageRank (GPR)-base) spectral GNN (Chien et al. 2020) to mixed-curvature spaces by incorporating operations based on the n-stereographic model of Rieman- nian geometry (Bachmann al.) 2020). We chose GPRGNN as the spectral backbone of CUSP because of its ability to capture node features and topological graph signals simultaneously. Lastly, introduce the (c) Cusp Pooling mechanism, complemented by functional curvature embeddings based on Bochner's Theorem (Xu et al.) (2000), to weigh differently curved substructures, enhancing its ability to model real-world graphs with diverse geometric and spectral properties. We perform an extensive empirical evaluation of CUSP for Node Classification (NC) and Link Prediction (LP) tasks, on eight real-world datasets. CUSP records state-of-the-art performance, with gain of up to 5.3%. We summarize our main contributions as follows:
To the best of our knowledge, this is the first attempt towards a graph learning paradigm that seamlessly integrates both geometry and spectral cues.
We introduce a curvature-awe Cusp Laplacian operator, design a mixed-curvature spectral graph filtering framework, Cusp Filtering, and propose a curvature embedding method using classical harmonic analysis and a hierarchical attention mechanism called Cusp Pooling.
We conduct extensive experimentation on eight mophilic and heterophilic graphs, for node classification and link prediction tasks.
benchmarking datasets, featuring ho-
2

---

Published as a conference paper at ICLR 2025
2 RELATED WORKS
Riemannian Geometry in Graph Neural Networks. Graph Neural Networks (GNNs) have set new benchmarks for tasks like node classification and link prediction. Recently, non-Euclidean (Riemannian) spaces particularly hyperbolic (Sala et al. 2018) and spherical (Liu et al,, 2017 Wilson et al. 2014) geometries have garnered attention for their ability to produce less distorted representations. aligning well with hierarchical and eyclic data structures, respectively. Several ap- proaches have emerged in this context. (a) Single Manifold GNNy: GNNs such as HGAT (Zhang et al., 202Tb), HGCN (Chami et al., 2019), and HVAE (Sun et al. 202T) have demonstrated state- of-the-art performance on tree-like or hierarchical graphs by learning representations in hyperbolic space. (b) Currvt--eee GNNs: To model more complex topologies (for example, a tree branch- ing from cyclic graph), mixed-curvatieo
GNNs have been proposed. Gu et al. (2019) pioneered this direction by embedding graphs in a product manifold combining spherical, hyperbolic, and Eu- clidean spaces. Building on this, models like seGCNN (Bachmann al., 2020) and Q-GCN (Xiong) iet al. 2022) extended the GCN architecture (Kipf & Welling 2016) to constant-curvature spaces us- ing the k-Stereographic model and Seeudo-Riemannia manifolds, respectively. More recently, [Sun) ct al. (2022) proposed a mixed-curvature GNN for -upervviee learning, while FPS-T (Cho et al., generalized the Graph Transformer (Min et al. 2022) operate across multiple manifolds.
2023
Spectral Graph Neural Networks. Spectral GNNs employ spectral graph filters (Liao et al. 2024) to process graph data. These models either use fixed filters, as seen in APPNP (Gasteiger et al., 2018) and GNN-LF/HF (Zhu et al. 202I), or learnable filters, as demonstrated by ChebyNet (Def-) ferrard et al., 2016) and GPRGNN (Chien et al. 2020), which approximate polynomial filters using Chebyshev polynomials and generalized PageRank, respectively. BernNet (He et al.] 2021) ex- presses filtering operations through Bernstein polynomials. However, many of these methods focus primarily on low-frequency components of the cigenspectrum, potentially overlooking important in- formation from other frequency bands particularly in heterophilic graphs. Models like GPRGNN and BernNet address this by exploring the entire spectrum, performing well across both homophilic and heterophilic graphs. GPRGNN stands out among them because it can express several poly- nomial filters and incorporate node features and topological information. Despite these advances, current mixed-curvature and spectral GNNs face significant limitations (L1, L2, L3) that constrain their performance. To the best of our knowledge, this work is the first to unify geometric and spec- tral information within a single model. Before presenting the architecture of CUSP, we introduce some key preliminary concepts the following section.
3 PRELIMINARIES
We study graphs G = (V, E, A), where V a finite set of |V| = n vertices, & is a set of edges and A Rax" is weighted graph adjacency matrix. The nodes are associated with the node feature matrix F E Raxd; (dy is the feature node dimension). A graph signal f V + R on the nodes of the graph may be regarded as a vector E H²' where f; is the value of f at the zth node. An essential operator in spectral graph analysis is the graph Laplacian L D A E Rax= where D E R is the diagonal degree matrix with D = E, Aij (Kipf & Welling 2016). The normalized Laplacian
is defined as L,, = I- A, where A,, D 1-11-///0 AD-1122 is the normalized adjacency matrix, and I E Ruxn is the identity matrix. As L is a real symmetric positive semidefinite matrix, it has a complete set of orthonormal eigenvectors U- {w)) E Raax,, and their associated ordered real nonnegative eigenvalues [[>))]]]] E IR," identified as the frequencies of the graph. The Laplacian can be diagonalized as L UAUT where A = diag( [(o)) Ra**.
Riemannian Geometry (Do Carmo & Flaherty Francis 1992). A smooth manifold M generalizes the notion of surface to higher dimensions. Each point x E M is associated with a tangent space TRM, which is locally Euclidean. On tangent space TxM, the Riemannian metric, 9x(,,)) TT& x T.M + IR, defines an inner product so that geometric notions (like distance, angle, etc.) can be induced. The pair (M,g) is called a Riemannian manifold. For x E M,, the exponential map at x, expx TxM + .M, projects the vector v E TxM onto the manifold M, and the logarithmic map, (y) : MM- + MxM, projects the vector y E .M back to the tangent space TxM The Riemannian metric defines curvature (x) at each point on the manifold, indicating how the space is curved. There are three canonical types: positively curved Spherical (S) space (R > 0), negatively curved Hyperbolic (IH) space (N < 0), and flat Euclidean (E) space (K 0).
3

---

Published as a conference paper at ICLR 2025
Product Manifolds Gu et al. 2019). Consider q curvtture manifolds (MMud)) yi with dimension de and curvature Ki.. Then, the product manifold is defined as the Cartesian product P = -M Mf x Mi .... x My with total dimension Σ d,. Each M; E ( S, Ej is known as a component space, and the decomposition IP M is called the signature of P.
--Stereographic Model (Bachmann et al. 2020). In this work, we adopt the s-Stereographic Model to define Riemannian algebraic operations across both positively and negatively curved spaces within unified framework. This model eliminates the need for separate mathematical for- mulations for different geometries. In particular, M is the stereographic sphere model for spherical manifold (K >> 0), while it is the Poincaré ball model (Ungar) (001) for hyperbolic manifold (x < 0).
More mathematical details and intuitions have been discussed in Appendix 7.2.4)
Ollivier-Rieci Curvature (ORC). Discrete data like graphs lack manifold structure (hence, no cur- vature). Several discrete analogs of manifold curvature have been defined, which satisfy properties similar to curvature. ORC (Ollivier 2007) ) is graph discrete analog of Ricci curvature (Tanno 1988) and is defined by transport along an edge of the network, between neighborhoods of the vertex. In an unweighted graph, for hyperparameter 8 [0. 1]. we endow each node's 's (x) neighbourhood Vz e ea()), and m (z) = 5 when & I, and analogously for (2). ORC for an edge (z, y) is then defined w.r.t. the Wasserstein- 1 distance,
(N(x) with probability measure, (=) [M]
1-5
W1 (Piccoli & Rossi 2016), between these measures, i.e., R((,, y) == Wi m,)) dg (1r, v) is dg(2.9)
the shortest graph distance between nodes x and y. The Ollivier- Ricci curvature k(x) for node defined as the average curvature its adjacent edges i.e. R(x)
[ल) ExeN(e)) M(x,2). 2).
Generalized PageRanks (GPR). Generalized PageRank methods originated the context of un- supervised graph clustering, where they demonstrated notable improvements over the classical Per- sonalized PageRank (Kloumann et al. 2017 Li et al. 2019). The core idea behind GPRs is as (vertex set) within graph cluster, an initial feature vector ())) E R=x1 is set, where ! 8ys (i.e., 1 for the seed node and O for all others). The GPR score is then defined as Ex=o A = Ex= (HH where 7ik E R are the GPR weights that control the importance of higher-order neighbors. This iterative process propagates the feature information throughout the graph. Clustering is performed by locally thresholding the GPR scores. Refer to the Appendix for more details on ORC 7.2.2). product manifolds (7.2.3). and GPR 7.4).
follows: starting with seed node
4 PROPOSED METHOD: CUSP
In this section, we present comprehensive overview of the architecture of CUSP, as shown in Figure 2 We start by introducing and deriving the Cusp Laplacian (Section 4.1 Building on this, we propose Cusp Filtering, the core component of our approach, which is a GP GPR-basse based, mixed-curvature spectral graph filtering network (Section 4.2p. Next, we introduce curvature embedding technique grounded in classical harmonic analysis (Section 4.3). which acts the positional encoding in the hierarchical attention-based Cusp Pooling mechanism (Section 4.4). Throughout this paper, we use denote the continuous manifold curvature and र. for the Ollivier-Rice curvature.
4.1 CUSP LAPLACIAN
To effectively incorporate geometric insights into spectral graph learning, introduce the Cusp Laplacian, a curvature-aware Laplacian opera- tor. We begin by examining the con- cept of heat flow on a graph (Weber 2008]. Suppose th describes tem- perature distribution across graph, where vxx) is the temperature at ver- tex I. According to Newton's law of cooling (He) 2024). the heat trans- ferred from node to node y is pro- portional to vx(x) (yy if nodes x and y are connected (if they are not
[Soww))
Effection Heat Blow fott (x==x)
(Piotert)
(4) Niggstive
(c) Pooltive Riraa O. W water, wff
R/a s) 3, w: (nf. 1
R(K,a) D W. W.inf..m =1
[Mismmal
Neigllwazheed
Figure 2: Consider heat diffusion from y + x. If a) < 0, there is a single path for the heat to diffuse from y + x. When R(x, v) 2 O, heat can effectively diffuse through other paths from y + x (dotted).
4

---

Published as a conference paper at ICLR 2025
connected, no heat is transferred). Consequently, the heat diffusion equation the graph can be - (1)(((x)) (z)), where 8 is constant of proportionality and A denotes the adjacency matrix of the graph. Further insight can be gained by considering Fourier's law of thermal conductance (Liu 1990), which states that heat flow is inversely proportional to the resistance to heat transfer. In this context, leverage the Ollivier-Riee curvature (ORC) to define the notion of resistance between nodes. Implicitly, ORC measures the transportation cost (W1 (:(::)) between the neighborhoods of nodes, reflecting the effort required transport mass between these neighhorhoods (Bauer et al. 2011). We interpret this transportation cost as the resistance between nodes.
expressed del
dt
The vital takeaway here is that Heat flow between two nodes in graph is influenced by the underlying Ollivier-Ricci curvature (ORC) distribution. The diffusion rate is faster on an edge with positive curvature (low resistance), and slower on an edge with negative curvature (high resistance).
Intuitively, if the neighborhoods of two nodes overlap significantly (Figure 2 c)), the transportation
cost between them is low (Rzg Wi (m mmm
1), resulting in positive curvature value for the edge connecting these nodes. In this scenario, messages (analogously, heat) can be transmitted efficiently between the neighborhoods. Conversely, if the neighborhoods have little overlap (Figure 2()),, the transportation cost is high, leading to a negative curvature value (Ray > 1), and the edge acts bottleneck, impeding effective message-passing. As result, the heat diffusion process is influenced by the underlying curvature (resistance).
dg(w.y)
Definition 1. The Cusp Laplacian operator takes the form
(x(x) = Σ Day (b(x)) vb1)) =
Σ you
el Renno (0(x)~v(())
(1)
where x ~ denotes adjacency between nodes x and Way e NER. represents the curvature- based weight between nodes x and y, and R(x, y) is the discrete Ollivier-Rieci curvature between and y. The function 1b - R is defined on the vertex set V of the graph. In the matrix form, we can write, L = D A, where D and A are the degree and adjacency matrices based on Way
Refer to Appendix| 7.3 for the derivation of Definition ! The curvature- based Laplacian operator al- low us to incorporate geometric cues into the spectral perspective, which are otherwise not captured by the traditional graph Laplacian.
4.2 CUSP FILTERING
Now, we will talk about how create filter bank (i.e. multiple graph filters) to fuse information from different parts of the eigenspectrum and learn node representations on a product manifold IP.
Product manifold construction. IP can have multiple hyperbolic spherical components with distinct learnable curvatures (parameters). This enables us to be representative of a wider range of curvatures. However, we only need one Euclidean space, since the Cartesian product of Euclidean space is Ed(c) E, such that Σ des die). This is not the case with H or S (Eg. Torus i.e. gl x St is topologically distinct from Sphere i.e. 8²). Thus, we can represent the product manifold signature, wpdd x x Mi = "x (1) x (xS=, Sto))0)) x Edd with
total dimension d = Dim h-1 d(n + ( + d(e). We use a simple combinatorial construction of the mixed-curvature space, induced by the cartesian product (Sun et al. (022). In Section 5 and Appendix 7.2.3 we describe how heuristically identify the signature of pa
Extending PageRank GNN to P. We choose GPRGNN (Chien et al. 2020) as the spectral back- bone of CUSP (See Appendix 7.4 for more background on GPRGNN), becasue it jointly optimizes node feature and topological information extraction, which is different from other spectral GNNs like ChebyNet (Defferrard et al. (0166.. The GFR weights automatically adjust to the node label pattern (homophilic or heterophilic). Given the node feature matrix F E Raxd, and normalized
symmetric Cusp adjacency matrix A,, = Ā = we first extract hidden state features for
5

---

Published as a conference paper at ICLR 2025
(4) Cusp Piltering
(f) Cusp Pooling
Righove
Final Node Represcntation
Chep Pooling
Cupp Fibering
Mac ID
7iler thak
Encading
Cusy Lapladin
Product Manittld
Olliviz--ie Btedi
(c) Curp Laplacian
Carvalure
2,00
Ingrtt Graph
Madildesa (s O)
Piims
Doversttone Tuni
Ryperloii (e ic
map
Rile)
Product
Manifaid
Je
Fasture Matei
(o) Inpot Graph
Computation
(c) Eucoding
Figure 3: Architecture of CUSP. The input graph (a) is used to construct the Cusp Laplacian (L), based the Ollivier-Ricci curvature (b), as illustrated in (c). The computed edge ORC (red), node ORC (Green), and curvature-based weights (blue) have been highlighted in the input graph. With L, (d) Cusp Filtering introduces multiple graph filters to capture different parts of the eigenspectrum. Each node receives a curvature positional encoding & in (e) as part the (f) Cusp Pooling mecha- nism, which computes the relative importance of different filters and manifold components.
each node and then use GPR to propagate them.
The process can be mathematically described as:
H M (6)
expo ((x)
(Fo(F))
:H
An, MA(C)
H H (1-))
M
M
K(a)
(44
M
@r())
H M
:Z0) DdM
= |1
Z
M, M,, (1)) (())
(3)
IE (0.L)
where fo(.) Rdd + wdd represents a neural network with parameter set {0} that generates the hidden state features of dimension d'M. Here, expă Rd + Mr.dM is the exponential map (Section 3 to transform the euclidean node features F to the component manifold M, and || is the attentional concatenation operator (discussed in Section 4.4). Gx &n and B, denote mobius addi- and
tion, fiighttmmrrri-mmlippiicaa
respectively (Appendix (72.44) These operations generalize vector addition and multiplication on s-stereographie model. The GPR weights "n are trained together with {0} in an end-to-end fashion. The final mixed-curvature node embeddings after attention can be represented Z ((L) [aaxdd, such that Σ d(g) dm-
Filter Bank. The GPR component of the network may be viewed polynomial graph filter (See Appendix 7.4p. Let A, UAUT be the eigenvalue decomposition of A Then, the polyno- mial graph filter equals ΣL= A Ugy
where 9 A) is applied element-wiss wise and (A) = E N. If one allows 7 to be negative and learnt adaptively, the graph filter will pass relevant high frequencies. Consequently, CUSP performs exceptionally well on heterophilic graphs.
Theorem (Informal (Chien et al. 2020)). If 2 0 VI E {0, 1,.., L}. El = and 31' > 0 such that y > O, then (-) is a low-pass graph filter. Also, in = (-a)'. a E (0. and L is large enough, then 1-, a high-pass graph filter.
We encourage the reader to refer to Chien et al. (2000) for detailed discussion how different initializations of the GPR weights, as mentioned in the theorem above, assist designing low-pass and high-pass filters. We present proof of Theorem in Appendix 7.4. Motivated by the limitation

---

Published as a conference paper at ICLR 2025
L1, instead of single filter, we construct filter bank to focus different parts of the eigenspec- trum (to assist in both heterophilic and homophilic graphs). In an attempt to be representative of the
higher order filters, the proposed filterbank is: Upar [Z Zp'xe Z _ ....... Z (L) p'x Here,
Z Aeum is the unfiltered case, where we pass the identity matrix I instead of A, for GPR propagation.
4.3 FUNCTIONAL CURVATURE ENCODING
Recall our motivation that CUSP must be able to pay more attention to differently curved sub- structures in our model, depending different tasks and datasets, while learning the final node representations. Specifically, our goal is to obtain a continuous functional mapping & Kp + pdde from curvature domain the de-dimensional product space to serve as positional encoding in attention mechanism (Section (4.4). We approximate this in two steps, by considering the Ollivier- Ricci (ORC) discretization of curvature on our graph and using the Bochner's theorem (Moeller et al. 2016) from classical harmonic analysis. First, we construct a translation-invariant Euclidean curvature encoding map, and then map it to the product manifold. Without loss of generality, we assume that the curvature domain can be represented by the interval: K- = [-1. where -1 to 1 is the rypical range" of ORC in the observed data. Formally, we define the Curvature Kernel KR K x K + IR with (Ra, Kb)) == gd (Ra), &gee (ma)) and Ka(Ka.. Kb)) 22 ki), VRa, Kb. E K. for some UR [-2, 2| + R. The intuition behind choosing such a kernel for curva- ture values, lies in the fact that when comparing K. and Ri we are only concerned with the relative difference between the two values. According to the Bochner's 's theroem (Moeller et al. (216)). continuous, translation- canslation-invariantt invariant kernel K(x. y) = (x y) on IR is positive definite if v the Fourier transform of non-negative probability measure on IR. Our kernel is translation-inariin since (a C Kb + ?) = V Vn (KKaaa +2) (Kg+7)) +)) (Ka, Kis) for any constant č. The following theorems defines the Euclidean encoding and it's corresponding mapping to the product space.
Definition 2. Let IRde be the ambient Euclidean space for a node's 's curvature encoding. The func- tional curvature encoding &gde + 12dc for curvature R(x) E K. of node x, is defined as:
Dyd (f(x)) = dc
(u(wwck(x)))
(4)
Lid where wi,..., Wio ~ p(w) are sampled from a distribution p(w). The corresponding mapping to the product manifold pde, is defined as:
(F(x)) go (1 K(e) (fRi (F()))( =go (1 M ) (f(z))):
(5)
where expo Miu) Rdd + M Mi denotes the exponential map on the 9th component manifold
with curvature Hi()) || the concatenation operator and go Pdd - pdc is Riemannian projector.
It is easy show that (Dde (Ra), Pac (Rt)) K(Kaa Ro). The unknown distribution p(w) is esti- mated using the inverse cumulative distribution function (CDF) transformation as in et al. (2020). Next, we prove the translation invariance of the curvature kernel in the product manifold setting.
Theorem 2. The mixed-curvature kernel Kpp (R,, Ra) == pP (Ra), @ptc (Ra)) is translation in- variant, i.e. (K Rb)) = V2 -Kb).
Please refer to Appendix 7.5 for the detailed proofs (derivations) of Definition 2 and Theorem 2 We employ Dpcc (K(x)) the ORC-based positional encoding for each node in the final pooling layer, enabling it to incorporate local curvature information and compute the task-specific relevance of substructures with varying curvatures within the graph.
4.4 CUSP POOLING
The importance of constant-curvatur component spaces depends on the downstream task. To this end, we propose a hierarchical attention mechanism called Cusp Pooling. We perform attentional
'ORC can theoretically vary from -o0 to 1. but in practice. its values usually lie within [-1, 1] for the majority of graphs. For extreme scenarios, such very sparse highly clustered graphs, values may fall outside this range. In such instances, ORC normalized to [11 1].
7

---

Published as a conference paper at ICLR 2025
concatenation to fuse constant-curvature curvature representations across component spaces mixed-curvature representations in the product space, weighing them appropriately. Specifically, we lift component encodings to the common tangent space, where can perform the usual euclidean operations, and compute their centorid by the mean pooling. Then, we model the importance of a component by the position of the emhedding relative the centorid, parameterized by 0.
learn
1 1
Nio) (Wo Bryp logo
Z My
(Centroid using linear transformation Wa) (6)
Tq a000 (logo Kin) (W, BnC)
Z L1) Mg
mo) 11) (Relative importance of Mg)
Finally, with the learnable attentional weights 8g = E-x Eg=o(e we perform attentional con- catenation. Further, as motivated earlier, for every node x, we fuse the curvature embedding as positional encoding:
(1(x)) FM
1
9=1 (B/
Z (()) Mr (C
(4) Z
(L)()) (p(m)((x))
(8)
We weigh different filters in our filter bank to yield the final node representation {(e)) for as C(x)
Etsr ((()) Here, Ç E ppx(ddxdde) contains the final node embeddings, and < is learnable parameter to weigh the importance of different filters in our bank. These node embeddings are then used for the final downstream tasks of node classification and link prediction. In the following section, we lay out the empirical results validate the efficacy of CUSP.
EXPERIMENTATION
Datasets. We evaluate CUSP on the Node Classification (NC) and Link Prediction (LP) tasks using
eight benchmark datasets. These include (a) Homophilic datasets such as (i) Citation networks Cora, Citeseer and PubMed (Sen al.
2008 Yang et al. 2016), and (b) Heterophilic datasets, which comprise (i) Wikipedia graphs Chamelcon and Squirrel (Rozemberezki et al.) (021). (ti) Actor co-occurrence network (Tang al. 2009), and (iii) Webpage graphs from WebKB Texas and Cornell. The dataset statistics and their respective homophily ratios are detailed in Table D Refer Appendix 7.2.1 2 for the discrete curvature and eigenspectrum distributions of these datasets.
Baselines. To ensure a fair comparison, we evaluate CUSP against three types of baselines: (a) Spatial-Fuelidean, includ-
Dataset
Cora Citeseer PubMed Chamelcon Squirel Actor Texas Comell
Chases
7
6
Features
1433
Nodes
2708
3327
19717
2277
5301
7600
183
ing traditional methods such GCN (Kipf Welling 2016). GAT (Veličković et al.
Edgess
5278
4552
44334
31371
198353
26690
279
277
H
08825
0.718
0.792
0.247
0.217
0.215
0.057
0.301
2017). and GraphSAGE (Hamilton et al.
Table 1: Data statistics and homophily ratio (7O).
2017 (b) Spatial--Remannian, comprising
(i) Constant-curvature models like HGCN (Chami et al., 2019) and HGAT (Zhang al. 202
and (ii) Mixed-curvature GNNs such as xGCN (Bachmann et al. 2020), QGCN (Xiong et al. 2022
and SeIfMGNN (Sun al. 2022). (c) Spectral, including ChebyNet (Defferrard al. 2016 Bern-
Net (He et al. 2021). GPRGNN (Chien et al.) 2020). and FiGURe (Ekbote et al.) 2024) (More details Appendix 7.6.2) There are no existing methods that integrate both spectral and geometric signals.
Experimental Settings. For the transductive LP task, we randomly split edges into 85%/5% 10% for training, validation and test sets, while for transductive NC task, we use the 20%%20% 220%/20%%%2/2/ 20% split. The results are averaged over 10 random splits and their 95% confidence intervals are reported. We report the AUC-ROC and F1 Score metrics for LP and NC respectively. For computing ORC (in Cusp Laplucian). we use ō 0.5, i.e. equal probability mass is retained by the node and distributed among it's neighbors. We adopt the ORC implementation from Ni et al. (2019), and use the Sinkhorn algorithm (Sinkhorn & Knopp 1967) to approximate the W; distance. See Appendix 7.2.2 for more computational details and complexity analysis. Next, we adopt the implementation of the k-stereographic product manifold from Geoopt libraryE] We heuristically determine the signature of our manifold (i.e. component manifolds) using the discrete ORC curvature of the
11 hwww//www.t
https://gi http://...ooogggggggggggeee/
8

---

Published as a conference paper at ICLR 2025
Baseline
Cora
Citeseer
PubMed
Chameleon
Actor
Squirrel
Texas
Cornell
Av. AGain
GCN
75.21
67.30
83.75=007
61.16=021
31.1240.5
43.06=033
67.72s1.9 75.61=0m
11.95
GAT
76.70
66.23:10s
82.83.om
63. 10
32.65
43.90=00:
76.09_077
74.01:000
10.63
SAGE
71.88
20.0
81,09
59.99.0a9
36.73.001
41.11=11
27.5
29.9
11.59
HGCN
78.50
83.72=021 69.55=0039
60.18:0557
35,89
39.93-035
88.11=112
72.88=1115
8.97
HGAT
77.12x001
12:122
84,02:0.19
62.43:0.59
35. 15:12:0227
41.78-0033
73.12:018 L5,
8,91
RGCN
78.71
14.14
85. 18:0
12:00.
34.57.1005
43.04_00
85.03.00
86.362064
7.06
QGCN
79.644638
71.15a101
84.76
61.83:1011
32.24:045
46.65=090
83.90 82.76zam
7.20
SeUMGNN
80.191000
82.81
64.97:10.54
38,99
49.79..028
90.92.005
85.01 g:0e
4.62
Cee
71.09
66.67.00.
83.83:10.1
59,96
38, 18002:1001
45.67
79.08:006
1..
10.61
BerNeet
73.34
62. 12:
82.15
62.03
13.55.004
42.81
65.56.110 15.1
12.98
GPRGNN
79.49
67.61
84,07=0000
65.09:0043
37.43:2009
=0.51
88,34=0m
a7.21
5.58
FiGURe
80.011000
71.26.044
83.89.0.11
67.1810m
38:3
48.71
86.662288
85.01
4.94
CUSP
83.45:
74.21
87,99...45
70.23:041
43.91
52.98-..25
94.03:0.2
92.31
0.0
Almp.
3.26%
2.95%
2.81%
4.05%
5.32%
3.19%
3.11%
5.10%
Table 3: Performance comparision of CUSP with baselines for NC task (Mean Fl Score = 95% confidence interval). First, Second and Third best performing models are highlighted. Av. A Gain represents the average gain of CUSP over the model in that row, averaged across the different datasets. Almp, implies the % improvement of CUSP over the second best performing baseline.
input graph. The key idea is that the underlying curvature of the manifold must align with ORC. However, this discussion, along with how we initialise the learnable curvatures for the component manifolds, has been reserved for the Appendix [7..4. For all experiments, we choose the total manifold dimension dmm
48 and learning rate as 4e-3. We use the filter bank Sptn
pd J. with = 10. For the GPR weights, we experiment with different initializations, E {0.1, 0.3, 0.5, 0.9}. We list the hyperparameter settings in Appendix 7.6.5
2 [2/am pd pd I....-.. Z (L)
Analysis. Tables 3 and g present a comparative performance analysis of CUSP against base- line models for the NC and LP tasks respectively. (a) CUSP consistently outperforms all base- line models across both homophilic and heterophilic datasets, achieving an improvement up to 5.32% in Fl-score for NC, up to 5.11% increase in ROC-AUC score for LP. (b) Riemannian base- lines perform well for homophilic datasets, while performing poorly in heterophilic cases (Evi- dence of limitation L1). (c) While spectral baselines like ChebyNet and BernNet perform poorly on heterophilic tasks because they act as low-pass, owing to the fixed filters, FiGURe performs well across all tasks because it uses filter bank to handle different bands in the eigenspectrum. (d) Mixed-curvature baselines (sGCN and QGCN) outperform constant-curvaturee GNNs (HGCN and HGAT) because they capture the complex graph geometry (Evidence of limitation L2).
Table 4 presents the leart filter weights (c), highlighting the distinct preferences of homophilic and heterophilic datasets. Homophilic datasets, such as Citeseer and PubMed, emphasize low-pass filters, with the highest weights assigned to lower-order filters, ( and (3 at 45.94% and 47.97% respectively. In contrast,
CUSP
Cora
Clacser
PubMial
Chanclan
Actur
Squinel
Toxas
Camell
1874 y
82.50.a1s
73,201e44
87.20.02s
69.42.mx
42200am
52.001e2
81.97.004
17.30
(1877 189977 o gi
82.00as
73.50seis
85.50
69 60:80
43.06
50.76aexx
01.60
91 30
ift st
82. 22.20umss
73,40amm7
W5 40unze
69 60
40
51.20ae19
9400
92.31:m
81.8
22.72am
85 90
70.23:30
42:50
52,98:43
92 20
agae x gle
81 $1.90ua17
72.501035
87.99 .us
65 a5.30
4391iam
51,10102
93.20umm
91 91.20114
1 g"
81.60.a1s
72.30103=
87.50.0044
67.50.am3
43.50:115
18,301e2
91.25
91.39 91.3911
8h4 x g2
71.80.c.0
80.99-uu
69 60.20
36.4--1
51,83iem
90.9
90.00a1100
aas gis ate
83.45aau
74.21.422
35.80
7u Taaa
43.20aa1
52.714077
93,80am
91. 91.801a11
(5+)* g2
80 10
71.50as
68 Raam
37 14
51,40amm
92.00
90 90.30am
91.00.a1
72.001046
87.70..03
6k.11002
43.70a1
45.671e2
15.15
55.011151
Table 2: Performance comparison of CUSP with different manifold signatures for Node Classification (NC), Best performing signatures are in Bold, and cases with a large decline in performance because of manifold mismatch are in Blue.
heterophilic datasets like Actor and Cornell favor high-pass filters, attributing 40.09% and 28.56% to higher-order filters, (6) and 7 In the next section, we perform extensive ablation studies to evaluate the effectiveness of all components of CUSP.
5.1 ABLATION STUDY
Impact of product manifold signatures. Different datasets leverage substructures with varying curvatures as inductive biases for downstream tasks, leading to differing performance across prod- uet manifold signatures. 5 the learned curvature and weight (13) for the best-performing

---

Published as a conference paper at ICLR 2025
Datanet
g.4
210
2'")
Siguatee
Gm
BP% -caas (.39) [ (122)) (2
Clesser
0.047
0.859
00181
01006
00187
01330
0,7755
0.2866
00731
0.063
Closerr
8"% C.42, 0.36 87%) -35
0.3066
0/137
00132
8.795
01116
00381
6.151
0.5644
06357
0.664
PabMad
-5x91,
(1.50) E
Chanolon
08033
3.664
0.616
01085
08031
00137
00392
0.373
0.356
00040
81%) 0.55, 0:30) (-.5 0.300 85
Sppimol
0.0106
00726
0,019
03562
09881
0001
0.133
11850
01005
010881
Sctindl
B:4 6.25 (.34) 6. 6.333, 0.89) x.5 -0.5 0.60)
Trox
0.8052
0/731
01664
D089
0006
00774
86095
0.1111
09679
033667
Rous
E7/ 0. 11455.0.2
x (0.34-4333330 x (2..0.044
Corual
013159
0/707
01661
00131
01687
00PN
00966
0/003
0.391
8.38%
010008
Gamall
B1 50.0
S.y 0.11) (..00.0.77
Table 4: Learned filter weights (NC) for the top-performing split, distinguishing between homophilic (favoring low-pass filters) and heterophilic (favoring high-pass filters). First, second, and third highest filter weights are highlighted.
Table 5: Learning results (NC) of
CUSP for the best performing prod-
uct signature manifold (dim) (cur- vature, weight).
configurations. Table 2 highlights performance across multiple signatures (which are heuristically determined as discussed in Appendix [7.6.4). with large degradation (marked in blue) when there is a mismatch between manifold and graph curvature. For example, Squirrel, which has a predomi- nantly positively curved structure (Figure 7.2.1. performs poorly (drop of 6.5%) on signatures dominated by negative curvature, such as S x E24 and (H)
Impact of mixed-curvature space. Table Table ooullnnes the comparison of CUSP with its Euclidean variant CUSP euc, where all representations are learned in Euclidean space, omitting Cusp pool- ing- On average, CUSPeuc experiences a 3.2% performance drop across all datasets for the NC task, highlighting the importance of capturing mixed-curvature signals. Notably, the perfor- mance degradation is more pronounced on heterophilic datasets (~ 4%) compared to homophilic datasets (~ 2%). This suggests that CUSP's s integration of spectral and geometric properties is crucial, particularly for heterophilic data where capturing the eigenspectrum is more relevant.
Impact of Cusp Laplacian. To assess the effectiveness of the Cusp Laplacian, we conducted ablation study by replacing the Cusp Laplacian-based adjacency matrix A, with the standard graph adjacency matrix (for Cusp filter- ing) in CUSP This resulted in a performance drop of 1.57% (avg.) across all datasets. The rel- atively modest degradation high- lights the Cusp Laplacian's 's role in capturing curvature information.
Dataset
CUSP
CUSP
CUSPlap
CUSP
CUSE pood
CUSP
Cora
83.45:0.15
80.78
81.95
82.61
80.11=022
81.20=029
Citeseer
74.21
72.50.0.1
72.734a.0
71.95
73.10
72.87
PubMed
87.99:045
85.23
86.672900
87.11
86,23-0.1
87.29
Chamelcon
70.23::0.11
66.47=0.6
68.
67.83=n31
68.47=0a2
66. 12:044
Actor
43.91:0.11
39.03-000
43.03+a22
41.12#022
40.03=0027
38.81
Squirel
52.98=005
49.92=0.36
$1.39
50,924aa5
51.03=0.1
48.13
Texas
94.03-072
90.15
92.15195
93.15
92.15
90.27
Cornell
92.31::0.9
89 19.4620.18
90,46gau7
91.062022
90.462007
89.73.2009
Avg. A Gain
3.19
1.57
1.67
2.19
3.08
Table 6: Ablation study (NC) results on benchmark datasets. Av. A Gain represents the average gain of CUSP over the model in that column, averaged across the different datasets.
Impact of the filter bank, cur-
vature encoding and Cusp pooling. CUSP za replaces the filter bank with a single learnable filter, as a result the performance degrades largely on heterophilic datasets (~ 4%), while the degradation in performance is not that large homophilic datasets (~ 2.5%). Further, we remove the curvature- based positional encoding in CUSP ene and replace the Cusp pooling mechanism with simple con- catenation in CUSP pool. We observe consistent decline in performance across both these ablations. Owing to spatial limitations, we present the experimental results for the LP task in Appendix 7.6.3
6 CONCLUSION
In this paper, we propose to unify Spectral and Curvature signals in a graph for learning optimal graph representations, aiming to inspire further research in this area. CUSP introduces a graph learning paradigm parameterized by spectral filters on mixed-curvature product manifold. We propose a new curvature-informed Cusp Laplacian operator to capture the underlying geometry, use to define a novel GPR-based spectral fittr-bank (Cusp Filtering) and introduce an attention- based pooling mechanism to fuse representations from multiple Pooling). CUSP outperforms the state-of-the-art baselines for node classification and link prediction over homophilic and heterophilic datasets, highlighting the efficacy of combining spectrum and curvature (geometry), in learning graph representations.
graph filters (Cusp
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We would like to sincerely thank Prof. Geoffrey J. Gordon Eggordon@cs.o cmu cmu.edu) from Carnegie Mellon University for his invaluable feedback and comments throughout multiple itera- tions of this paper, which greatly helped improve its quality.
REFERENCES
Gregor Bachmann, Gary Bécigneul, and Octavian Ganea. Constant curvature graph convolutional networks. In International conference on machine learning, pp. 486-4866666 PMLR, 2020.
Frank Bauer, Jürgen Jost, and Shiping Liu. Ollivier-ricci curvature and the spectrum of the normal- ized graph laplace operator. arXiv preprint arXiv: / 105.3803, 2011.
Mikhail Belkin, Jian Sun, and Yusu Wang. Discrete laplace operator on meshed surfaces. In Pro-
ceedings of the founty-fourth annual symposium Computational geometry, pp. 278-287, 2008.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006. 07988, 2020.
Sungjun Cho, Seunghyuk Cho, Sungwoo Park, Hankook Lee, Honglak Lee, and Moontae Lee. Curve your attention: Mixed-curvature transformers for graph representation learning. arXiv preprint arXiv:2309.04002, 2023.
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.
Manfredo Perdigao Do Carmo and J Flaherty Francis. Riemannian geometry, volume 2. Springer, 1992.
Chanakya Ekbote, Ajinkya Deshpande, Arun Iyer, Sundararajan Sellamanickam, and Ramakrishna Bairi. Figure: Simple and efficient unsupervised node representations with filter augmentations. Advances in Neural Information Processing Systems, 36, 2024.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: arXiv:/810.052 1810000911.. 2018.
Karish Grover, SM Angara, Md Shad Akhtar, and Tanmoy Chakraborty. Public wisdom matters! discourse- aware hyperbolic fourier co-attention for social text classification. Advances in Neural Information Processing Systems, 35:9417-9431, 2022.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature represen- tations in products of model spaces. International conference on learning representations, volume 5, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34:14239-14251, 2021.
Zhuo-Chen He. Constrained heat kernel graph diffusion convolution: A high-dimensional statistical approximation via information theory. IEEE Access, 2024.
Alec Jacobson and Olga Sorkine-Hormune A cotangent laplacian for images surfaces. Technical Report/ETH Zurich, Department of Computer Science, 757, 2012.
Jost and S. Liu. Ollivier's Ricci curvature, local clustering and curvature-dimentte inequalities graphs. Discrete & Computational Geometry, 5122)330--32,, 2014.

---

Published as a conference paper at ICLR 2025
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 10X.:0669.00207, 2016.
Isabel M Kloumann, Johan Ugander, and Jon Kleinberg, Block models and personalized pagerank. Proceedings of the National Academy of Sciences, 114(1):33-35 2017.
Taewook Ko, Yoonhyuk Choi, and Chong-Kwon Kim. A spectral graph convolution for signed directed graphs via magnetic laplacian. Neural Networks, 164:562-574, 2023.
H. Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, (1-2):83-97, 1955.
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. Advances in Neural Information Processing Systems, 32, 2019.
Ningyi Liao, Haoyu Liu, Zulun Zhu, Siqiang Luo, and Laks VS Lakshmanan. Benchmarking spec- tral graph neural networks: A comprehensive study on effectiveness and efficiency, arXiv preprint arXiv:2406.0967 2024.
Y. Lin, L. Lu, and S. Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, 63(4):605 627, 2011.
I-Shih Liu. On fourier's law of heat conduction. Continuum mechanics and Thermodynamics. 2: 301-305, 1990.
Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj, and Le Song. Sphereface: Deep hypersphere embedding for face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 212-220, 2017.
Rada Mihalcea and Dragomir Radev. Graph-based natural language processing and information retrieval. Cambridge university press, 2011.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455. 2022.
John Moeller, Vivek Srikumar, Sarathkrishna Swaminathan, Suresh Venkatasubramanian, and Dustin Webb. Continuous kernel learning- In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part II 16, pp. 657-673. Springer, 2016.
Chien-Chunnaa Ni. Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific reports, 91):1112,,001
Yann Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique, 345(11):643 646, 2007.
Benedetto Piccoli and Francesco Rossi. On properties of the generalized wasserstein distance. Archive for Rational Mechanics and Analysis, 222:1339-1366 2016.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnnbb014, 2021.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoff's for hyperbolic embeddings. In International conference machine learning, pp. 4460-4469. PMLR, 2018.
Aliaksei Sandryhaila and José MF Moura. Discrete signal processing graphs: Graph fourier transform. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 6170. IEEE, 2013.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rate Collective classification in network data. Al magazine, 29(3):93-93, 2008
R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):33-3448 1967.
12

---

Published as a conference paper at ICLR 2025
Li Sun, Zhongbao Zhang, Jiawei Zhang, Feiyang Wang, Hao Peng, Sen Su, and S Yu Philip. Hyper- bolic variational graph neural network for modeling dynamic graphs. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 4375 4383, 2021.
Li Sun, Zhongbao Zhang, Junda Ye, Hao Peng, Jiawei Zhang, Sen Su, and S Yu Philip. A self- supervised mixed-curvatrre graph neural network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 4146-4155, 2022.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 807-816, 2009.
Shukichi Tanno. Ricci curvatures of contact riemannian manifolds. Tohoku Mathematical Journal, Second Series, 40(3):441 -488, 1988.
Dorina Thanou, Xiaowen Dong. Daniel Kressner, and Pascal Frossard. Learning heat diffusion graphs. IEEE Transactions on Signal and Information Processing over Networks, 3(3):484-499 2017.
Yu Tian, Zachary Lubberts, and Melanie Weber. Curvature-based clustering on graphs. arXiv preprint arXiv:2307.10155. 2023.
Abraham A Ungar. Hyperbolic trigonometry and its application in the poincaré ball model of hy- perbolic geometry. Computers & Mathematics with Applications, 41(112))135-147, 2001.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Andreas Weber. Analysis the physical laplacian and the heat flow on locally finite graph. arXiv preprint rrXXiv0801.0811 2008.
Richard C Wilson, Edwin R Hancock, Elzbieta Pekalska, and Robert PW Duin. Spherical and hyperbolic embeddings of data. JEEE transactions on pattern analysis and machine intelligence, 36(11):2255-224) 2014.
Bo Xiong, Shichao Zhu, Nico Potyka, Shirui Pan, Chuan Zhou, and Steffen Staab. Pseudo- riemannian graph convolutional networks. Advances in Neural Information Processing Systems, 35:3488-333 3501, 2022.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning temporal graphs. arXiv preprint arXiv:2002.07662, 2020.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming- Jing Tang. Graph neural networks and their current applications in bioinformatics. Frontiers in genetics, 12:690049, 2021a.
Yiding Zhang, Xiao Wang, Chuan Shi, Xunqiang Jiang, and Yanfang Ye. Hyperbolic graph attention network. IEEE Transactions on Big Data, 8(6):1690-170.. 2021b.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pp- 1215-1226, 2021.
Shichao Zhu, Shirui Pan, Chuan Zhou, Jia Wu, Yanan Cao, and Bin Wang. Graph geometry inter- action learning. Advances in Neural Information Processing Systems, 33:7548-7558, 2020.
13

---

Published as a conference paper at ICLR 2025
Table of Contents
14
7
Appendix
15
7.1
Notation Table
15
7.2
More on Preliminaries
16
7.2.1
Analysis of Real-world Graphs
16
7.2.2
Ollivier-Rice Ricier Curvature (ORC)
17
7.2.3
Product Manifolds
17
7.2.4
Kappa-Stereographic Model
18
7.2.5
Spectral Graph Theory
18
7.3
More on Cusp Laplacian
18
7.3.1
Relevent Theorems for Cusp Laplacian
19
7.4
Generalised Pageranks and GPRGNN
7.4.1
Proof of Theorem
21
7.4.2
Why GPRGNN as backbone of CUSP?
22
7.5
Theorems for Curvature Encoding
22
7.5.1
Proof of Definition
22
7.5.2
Proof of Theorem
23
7.6
Experimentation
24
7.6.1
Datasets
24
7.6.2
Baselines
24
7.6.3
Experimental Results for Link Prediction
25
7.6.4
Estimating Product Manifold Signature
26
7.6.5
More Experimental Settings
27
14

---

Published as a conference paper at ICLR 2025
7 APPENDIX
7.1
NOTATION TABLE
Notation
Reference
Hyperholic manifold
S
Spherical manifold
E
Euclidean manifold
pdM
Product manifold of dimension d.M
Continous manifold curvature
Ollivier-Rice Ricci Curvature (ORC)
((a,y)
ORC of edge {.. of node
x(x))
Probability mass assigned to node for ORC computation Kroneckner delta function
8y
(a)))
Neighbourhood of node
myy
This implics that x and y are adjacent nodes ORC neighbourhood weighting parameter Wasserstein-1 I distance
Wi()
Shortest path (graph distance) between nodes and y on graph
Mi
Constant-curvature manifold with dimension di and curvature R4. M, E [))
D,
Cusp Laplacian operator; L D
L, An
Normalized Cusp Laplacian and Adjacency matrices; A. = D Á + Traditional graph Laplacian, Adjacency and Degree matrices; L D A Input graph feature dimension
D,D,A
dy
dm
Total dimension the product manifold
de
Total dimension of the curvature embedding
FERaxy
Input feature matrix
expă RAM + M
Exponential map, to map from tangent plane (Buclidcan) to the product manifold Mobius addition
@x
8x
s-rrightmmarrx--mulle multippicationn
K.
matrii-muuliplication
Stx)
Final node representation for node x Learnable weight of 7 filter
Ç E (dd
Matrix containing final node embeddings Learnable weight of 9t component manifold
8
To
Relative importance of manifold MM in Cusp Pooling
L
Total number of filters
Q
Total number of components in product manifold Used to denote the 1hh filter
z (1)6))
The GPR-based node representation filter with L layers, on manifold pd
((g)
Manifold curvature of 9th component product manifold
digh
Manifold dimension of 9d component in product manifold
H
Hidden state representation after / layers of GPB, on gth manifold component with curvature (i(g) and dimension d(g)
M (())
GPR weight for feh layer in the filter, while propagation GPR score.
Initialising parameter for GPR
Signature
Pdd x 8 MMM Me -(w)
(x hー 1= (x (x52)800)
BBdc))
w: - K
function defined on vertex
Ppec (R(x))
Curvature encoding on product manifold
Ke (K. No)
K=(Ra, Ro) ( (Dgee (Na), ag (Ro)) is the curvature kemel
d
8th cigenvalue of A.
de
tth eigenvalue of L., Neural network with parameter set (0) that generates the hidden state features be- fore feeding imput Cusp Filtering.
fa()) Rd4 RdM
go(-) TM + Re
Neural network projector used in curvature encoding
15

---

Published as a conference paper at ICLR 2025
7.2
MORE ON PRELIMINARIES
7.2.
ANALYSIS OF REAL-WORLD GRAPHS
cora
Citeseer
PJbMed
Chameleon
200
4000
400
Proquancy
Frequency
400
-300
2000
200
-1.0
0.3
0.0
0.5
1.0
1.0
-3.5
C.0
0.5
1.0
-1.0
-0.5
0.0
2.5
1.0
-1.0
-1.3
11:11
0.5
1.0
Node Piczi Curvalure
Kode Rice Curvalure
Node Ricsi Curvature
Kode Riczi Curvatuue
Actor
Squirel
Texas
Cornell
Requaney
frequenccy
40
400
20
10
-1.0
-0.5
0.0
0.5 1.0
-1.0
-0.5
0.0
0.3
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.3
0.0
0.5
1.0
Node Riczi Cunvoture
Kode Rice Curvature
Node RICOI Curvature
Kodi Ricoi Curvature
Figure 4: Distribution of Ollivier-Ricei curvatures K(x,, y) of edges across different datasets. The histograms illustrate the frequencies of edge-based Ollivier-Ricci curvature values for each dataset, highlighting the topological diversity both homophilic and heterophilic settings, and hence the need of learning representations in manifolds with different curvatures.
Cora
Citeseer
RubMedd
Chameleon
800
Requeroy
300
reeqeercy
300
4000
nequenoy
4000
200
200
2000
2000
100
-1.0
-05
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
100
-1.0
-0.5
0.0
0.5
10
-1.0
-3.5
DO
0.
1.0
Edge Riisi Curvature
Curvattree
Edge Ricti Curvalure
Edge Ricci Curveture
Actor
Squirrel
50000
60
Requency
2000
Irequency
40000
30
10
20000
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.3
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-03
0O
0.5
Edge Ricri Curvature
Edge Rinci Curvattur
Edge Ricri Curvaltio
Edge Rirri Eurvattoe
Figure 5: Distribution of Ollivier-Ricci curvatures k(z) of nodes across different datasets.
Cora
Citeseer
Texas
Cornell
0.010
0.010
0.010
0.010
Spectral Energy
0.008
Energy
0.008
Spectral Energy
0.000
0.008
0.006
Spectral
0.004
0.004
0.004
0.004
0.002
0.002
0.002
0.002
0.000
0.000
0.000
0.000
10-1
101
10-5
10-1
100
102
100
101
102
log(A)
log(A)
log(A)
logt2)
Figure 6: Distribution of Spectral Energy with the respective eigenvalues of the graph Laplacian. Spectral Energy, & f2//, f7. where fy is the 5th Fourier mode of the graph Laplacian. Low frequency implies homophily and high frequency components correspond to heterophily. These plots highlight the importance of capturing signals from different parts of the eigenspectrum for designing GNN that works well across multiple tasks.
16

---

Published as a conference paper at ICLR 2025
7.2.2 OLLIVIER PLLIVIER-RICCI CURVATURE (ORC)
In an unweighted graph, the neighborhood of each node x, denoted as ((x). is assigned probability distribu- tion according to lazy random walk formulation (Lin et al. 2011). Specifically, we define the distribution as follows:
a:
i if ((x),
my (x)
I-a I
(9)
0,
otherwise.
Here, a controls the probability that a random walk will remain at the current node, while the remaining probability mass (1-a) is uniformly distributed across the neighboring nodes. This formulation connects ORC with lazy random walks and influences the balance between local exploration and the likelihood of revisiting node. In this work, we use a 0.5, meaning that equal probability mass is distributed between the node itself and its neighbors, striking a balance between breadth-first and depth-first search strategies, The choice of a crucial and depends on the topology of the graph. A smaller a value encourages more local exploration, while a larger a favors revisiting nodes, thereby promoting a "lazy" walk. For our experiments, = 0.5 was chosen reflect equal probability mass distribution between the node and its neighbors.
Computational Considerations. Computing ORC can be computationally intensive due the need calculate the Wasserstein-I distance (W1), between the neighborhood distributions of connected nodes. In a discrete setting, this corresponds to solving a linear program. Typically, and y is computed using the Hungarian algorithm (Kuhn 1955). which has a cubic time complexity. However, this becomes prohibitively expensive the graph size increases. Alternatively, the Wasserstein- distance be approximated using the Sinkhorn algorithm (Sinkhorn & Knopp 1967). which reduces the complexity to quadratic time. For this work, we employ the Sinkhorn approximation to compute ORC efficiently. Below, we provide an alternative to approximate ORC of an edge in lincar time, in case of very large (million-scale) roal-world graphs.
my between two nodes æ
Approximating ORC in Linear Time. Even with the quadratic complexity of the Sinkhorn algorithm, scaling to large networks remains challenging. To address this, linear-time combinatorial approximation of ORC can be employed, as suggested by Tian et al. (203)). This method approximates the Wasserstein distance by utilizing local structural information, making it much more computationally feasible. The approximation of ORC builds on classical bounds first introduced by Jost & Liu (2014). Let #(x y) denote the number of triangles formed by the edge (ær, y), and define A b min b max(a, b) and de the degree of node r. The following bounds on ORC can be derived for an edge e x. y
Theorem 3 (Jost& & Liu 2.144). For unweighted graph, the Ollivier-Ricd curvature of an edge x. satisfies the following bounds:
1. Lower bound:
1
#(x
#(x, B) d, V dy
#(r m) dr V dy
R(2, v)
2
dz
dy de h dgy
-
dx dy
+
2. Upper bound:
7(z v) # 4)
(10)
d. dyy
The ORC of an edge, can then be approximated as the arithmetic mean of these bounds:
R(x, w) == SeTer (Ir, u) + lower
(11)
The proof of these bounds has been detailed in Tian et al. 2023). This approximation is computationally efficient, with linear-time complexity. and can be parallelized easily across edges, making suitable for large- scale graphs. The computation relies solely on local structural information, such as the degree the nodes and the number of triangles.
7.2.3 PRODUCT MANIFOLDS
Let M1. .M Mr denote a set of smooth manifolds. Their Cartesian product forms product manifold, denoted by P. such that P Mi M2 ... Mr. Any point p E P characterized by its coordinates p= (P1, P2,..., p&), where each p. corresponds a point on the individual manifold Mi. Similarly, tangent vector o E T.P can be expressed as e = (V1, ......, Uk). where each e; E T,, M, represents the projection of in the tangent space of the respective component manifold M,. Optimization over manifolds requires the notion of taking steps along the manifold, which can be achieved by moving in the tangent space and mapping those movements back onto the manifold through the exponential map. The exponential map at point p E P,
17

---

Published as a conference paper at ICLR 2025
denoted exp, TpP I,, allows for this transfer. For product manifolds, the exponential map decomposes into individual component exponential maps. Specifically, given a tangent vector v = (vi, U2,.... vb) at = (21.P2..... P. the exponential map on P can be expressed as:
exp,(1) (expp, (vi), exp (v2)...... exPpo (v+))
(12)
7.2.4 KAPPA-STEREOGRAPHIE MODEL
The x-stereographic model (Bachmann et al. 2020) unifies Hyperbolic and Spherical geometries under gy- rovector formalism. This model leverages framework of gyrovector spaces represent all three con- stant curvature geometries hhyeerooiicee Euclidean, and spherical simultaneously. Additionally, facilitates smooth transitions between these constant curvature geometries, enabling the joint learning of space curvatures alongside the embeddings. It is smooth manifold M (= E R-1 < <=|= < 1}. whose origin is 0 E R. equipped with Riemannian metric 9 (A where X is given by x 2 (1 The Riemannian operations under this model are elahorated in the table helow:f
Operation
Formalism in E
Unified formalism in x-stereographic model /3
Distance Metric
d' (x, = ||x ylla
di (x)
VMal tan,''
(vix/ -x Br. y ylla
Exp. Map
exp = v
exp = Cx taan [xxx] مااlاi V Vialllalia
Log. Map
log (y) = x Dr
(y) VINAg
2
tan
[x | Ox 81l22
X -x
(Dx [122xx Klyl
(xll
Addition
ytx
Table 7: Operations in Hyperbolic Spherical Sdd and Euclidean space Edd
Given matrix X R holding r-stereographic embeddings in its and weights W E Id the Euclidean right multiplication can be written row-wise as (XW):. X., W. Then the friihhtmmarix-muliilaai is defined row-wise as
wrright-matri--multipll
(W)
X 8x W).. -exp (llgg ().) = -tan. (ax Laug (I|X.:))) ())
(13)
[
where (XW) X and exp, and logã denote the exponential and logarithmic map in the x-stereo, model.
n- deff-marrix-mulippiccttio Given matrix E Rxd holding s-stereographic embeddings in its rows and weights x the x-left-matrix- mautttiiimmliipiiaaiionn is defined row-wise as
(A AA X)i+ = E Aij) 8x mx "
(14)
7.2.5 SPECTRAL GRAPH THEORY
Graph Fourier Transform (GFT) Sandryhaila & Moura 2013) lays the foundation for Graph Neural Networks (GNNs). GFT is defined using a reference operator R which admits a spectral decomposition. Traditionally, in the case of GNNs, this reference operator has been the symmetric normalized Laplacian L,, = A R" is then defined as f UTf E R". and its inverse f Uf. A graph filter is operator that acts independently on the entire eigenspace of diagonalisable and symmetric reference operator R, by modulating their corresponding eigenvalues. graph filter is defined via the graph filter function g-)) operating on the reference operator as gR) = Ug(A)U
(Kipf Welling 2016). The graph Fourier transform a signal
7.3 MORE ON CUSP LAPLACIAN
Spectral graph theory has shown significant progress in relating geometric characteristics of graphs to properties of spectrum of graph Laplacians and related matrices. Several variants of the graph Laplacian matrices have been shown capture specific inductive biases for different tasks (Ko et al. 2023 Belkin al. 2008 Jacobson Sorkine- Sorkine-Horuung 2012).
Say the function + V + RR is defined on the vertex set V of the graph. Suppose & describes temperature distribution across graph, where vb(x) is the temperature vertex According to Newton's law of cooling (He 2024), the heat transferred from node node y proportional ((x)) ())
Proof of Definition] /
18

---

Published as a conference paper at ICLR 2025
if nodes x: and y connected (if they connected. heat is transferred). Consequently, the heat where 3 is constant of
diffusion equation on the graph can be expressed as dr = 3- (v)((x)) proportionality and A denotes the adjacency matrix of the graph. Further insight be gained by considering Fourier's law of thermal conductance (Ltul 1990), which states that heat flow is inversely proportional to the resistance to heat transfer. CRC measures the transportation cost (Wi(::)) between the neighborhoods of two nodes, reflecting the effort required to transport mass between these neighborhoods (Bauer et al. 2011). We interpret this transportation cost the resistance between nodes. The vital takeaway here is that Heat flow benween two nodes a graph is influenced by underlying Ollivier-Rice Ricci curvature (ORC) distribution. The diffusion rate faster on an edge with positive curvature (low resistance), and slower on an edge with negative curvature (high resistance). Thus, the ratio Ray Wi(ma.mul represents the resistance from node æ to node dg (r.a))
y. i.e. ditau R.y.
I-A(x.9) (From definition of ORC) would tend to infinity when W Wi(mz, my) = 0 (i.c. R(2, v) = 1). Thus, to ensure continuity, we create new
can observed that Ray W. (R))
do(s.y)
ratio
Roy
= Thus, we can modify the above heat flow equation as:
dep
(v(x) +v)) (Inversely proportional to Ray))
- Σ
dt
REy
Σ
(vr((()) - (v))) - = -8 ((x) Σ Azy [AnA((li)
T-R(P.07
8 ((i Σ (v) TTR((_.))
(D:
Σ Asy)
- Σ
Ozy e cT DRx e. CI-cc
A Azy) vuv)
(Nay is the Kronecker delta.)
8
Σ (cl Lay (1))
(L, D, are Laplacian, Degree and Adjacency matrices.)
- LOeT x(o.3)) -
( the dement-wise product)
This gives us the standard heat equation on graphs. Here, the updated constant proportionality. Ż D A is the Cusp Laplacian operator, where D and A the updated Degree and Adjacency matrices, represent that the graph transformed under edge weights Way
R.. e -ーर(.... Finally, our Cusp
Laplacian operator can be written as (x ~ means xy is an edge in the graph):
Lab(r) = Σ Tay (1b()) (v)) = Σe ex (sb(x) - +by)
(15)
gr
Why is R25 = -t. the right choice? To mathematically justify that e 1- is an appropriate choice, we must verify its properties:
1. Asymptotics. As R(x, v) - 1,e T- 0, indicating that nodes with high positive curvature experience very fast heat diffusion (minimal resistance). Conversely, as R(2, y) + -1, Ria.s + ve meaning that nodes with high negative curvature have slow heat diffusion (higher resistance).
2. Continuity. The exponential function is smooth and continuous, ensuring that even small changes in the curvature result in smooth changes in the heat flow dynamics, which crucial stable numerical simulations and theoretical consistency.
Monotonicity. A(., y) > 0 T- is decreasing function with respect to (a y). This means as curvature increases, the resistance decreases, aligning with the physical intuition of heat flow.
7.3.1 RELEVENT THEOREMS FOR CUSP LAPLACIAN
Theorem (Positive Semidefiniteness Cusp Laplacian), The normalized Laplacian operator positive Th semidefinite, i.e., for any real vector R", we have n1 L,
19

---

Published as a conference paper at ICLR 2025
Prouf. We start by showing that the normalized Cusp Laplacian
L. 1 - 1--1-1220 AD 1/2 - A..
(16)
positive semi-definite. u be any real vector unit norm f D-1/2u, then we have
u u'L.u= = u"u uu-'D 1/2
AD
1/2 u
Σ
(17)
3,y=1
Σ
EgfAA zy
1
22 D 22
-2
n
f.fy ay +
Σ D
(18)
==1
2,y=1
2m1
2,8=1
y=1
1
Σ (L= a.y=
==)²=
Σ m,y=l
Any (Le fg)
(19)
2
where the last step follows from the definition of the degree. We know that e K(maa) >> O VK(H, y), hence our Cusp Laplacian is positive semidefinite.
Theorem 5. The eigenvalues (A.)is of the normalized Cusp Laplacian Ly lie in the interval [O, 2].
Proof. We begin by noting that Theorem 4 shows that the normalized Cusp Laplacian L, has real, non- negative eigenvalues, meaning need only to prove that the largest eigenvalue, denoted as A is less than equal to 2. Before moving to that, we show that 0 is indeed eigenvalue of L associated with the unit VD,,
eigenvector where T VE. D.v
Let 1 be the all one vector. Then, direct calculation reveals that
E T = 1/2 AD 1/2 = T 10-0/AD
1//2 x
(20)
VΣ.
D..
1
D1
(21)
Σ D.c
Σ D
-
(22)
Σ D
Combining this result with the positive semi-definite property of the Laplacian shows that 0 is indeed the smallest cigenvalue of Lym associated with the eigenvector т. For the second part, using the Courant-Fischh theorem, we know that the largest eigenvalue can be expressed as:
1 L
max 10
Tu
Substituting the definition of the normalized Cusp Laplacian La = I- An into this expression, and letting f D 1/2 u, we have:
1TD1I/LD 1/2
r L'
A, max u
max F70
Df
The degree matrix, can be expressed in the quadratic form as f DD
Σn x=
D 1o
For the numerator involving L, we expand the quadratic form:
f L
Σ As =,,)²= 2 x
Aecioo Azy f2)²
(23)
2
4,8=1
e -
A Azy + f22) 52
12, Σ Azy = > Dax f())
(24)
The last inequality follows from the fact that [T as R( v) + - implies that it is always < 1. Thus, can conclude that, f Lf < 2f Df, and the Rayleigh quotient is bounded f Lr 2. This shows
FT
that the largest eigenvalue the normalized Cusp Laplacian L, is bounded by 2, completing the proof that eigenvalues of L, contained within the interval [0, 2).
20

---

Published as a conference paper at ICLR 2025
Generalized PageRank
Hidden state
feature extraction
Z
k-
Neural Net fo(.)
X
X-11
00
fo(F)
H (0)
(1)
H (X)
X
Figure 7: Architecture of GPRGNN.
7.4 GENERALISED PAGERANKS AND GPRGNN
Equivalence of the GPR method and polynomial graph filtering. If we truncate the infinite series in the GPR definition some integer K, Ei= Ar becomes a polynomial graph filter degree K. Consequently, optimizing the GPR weights is tantamount to optimizing the polynomial graph filter. is important to note that graph filter can be approximated using a polynomial graph filter, enabling the GPR method to handle wide variety of node label patterns. Additionally, increasing K enhances the approximation of the optimal graph filter. This again illustrates the advantage of large-step propagation.
GPRGNN architecture. GPR-GN initially derives hidden state features for each node and subsequently employs GPR to disseminate them. The GPR-GN EPR-GNN procedure can be represented as:
K
p softmax(Z)) Z
H
(4) H A H H fo().),
(25)
Here, fo(.) denotes a neural network paramctrized by (0), which produces the hidden state features H The GPR weights "Yk are optimized alongside {0} in an end-to-end manner. The GPR-GNN model is straightfor- ward to interpret: As previously mentioned, GPR-GNN is capable of adaptively managing the contribution of each propagation step fit the node label pattern. Analyzing the trained GPR weights also aids in understand- ing the topologiaal properties a graph, such as identifying the optimal polynomial graph filter.
7.4.1 PROOF OF THEOREM 1
We first state the formal version of Theorem 1
Theorem 6 (Formal version of Theorem Dp. Assume the graph G is connected. Let A 2 A2 2 > An and
X1 X2 ... I Xx be the eigenvalues of A., and Lmn, respectively, If vI f0, 1, L}. ΣL "
and 31' > 0 such that "/r 0, then (A))
< <1vi> 2. Also, if = (-a)', E (0, 1) and L + 0o, then
(9.0(11)
(Av) Ling (AT)
Vi
1. Note that (A4) (A1)
< 1 Vi 2 2 implies the low-pass case as after applying the graph filter L. the lowest frequency component (correspond to A1) further dominates.
2. Unfiltered case. Recall that in the unfiltered case, do not multiply with A.. It can also be viewed as Hence g,.2 acts like a pass Da
multiplying the identity matrix where the eigenvalue ratio [',]" filter in this case.
3. In contrast, limg= (A,,) Vi implies that after applying the graph filter, the lowest frequency component (correspond to A1) no longer dominates. This corresponds to the high pass filter case.
sim s5, (A1)
Proof. We with the low pass filter result. From Theorem know that X₁ 5o S S Rn Given the spectrum of A,, we know that A., has spectrum negatives of A., and - A,, adds one to each cigenvalue of - A, Hence, 1 2 d1 2 d2 2 2 An 2 -1 follows directly. Now, we know that A and |A.] < 1, vi 2 Further, we have assumed that gy, (Ar) D/ 7 Hence, proving Theorem equivalent to show
< 2.
<1vi>
21

---

Published as a conference paper at ICLR 2025
This is obvious since gr..( Σ yu is polynomial of order L with nonnegative coefficients. It easy to check that v/ 2 1, Ma|' < 1, VIIA < 1. Combine with the fact that all 7 's are nonnegative we have
19.2((a) S
1
Finally, note that the only possibility that the equality holds is m δo, since VA 1, |A/ 1 < 1. However, by assumption Ei=o 7 1 and 3I > 0 such that TV > 0 we know that this is impossible. Hence (a) is strict inequality
For the high pass filter result, can be observed that:
lim (A)
lim
nx
lim E( (-a)) 1 1+
1=0
where the last step due to the fact that E (0, 1) and thus lim (-ad)= ax)= = =0, V/A
Thus we have
lim 9r, (Ax)
1 1
lime-+ I (A1)
1 aA
The strict inequalities (b) is from the fact that | < 1, Vi 2 Notably, supxe(1,-1) T happens at the boundary À = -1, which corresoonds the the bipartite graph. further shows that the graph filter with respect the choice ? (-a)' emphasizes high frequency components and thus it indeed acting as a high pass filter.
7.4.2 WHY GPRGNN AS THE BACKBONE OF CUSP?
In this section, we elaborate on why GPR is ideal hackhone when compared to other Spectral GNNs.
Adaptive Filter Design. GPR learns filter coefficients directly, allowing the spectral response to adapt to the task and dataset. This flexibility is critical for modeling both homophilic and heterophilic graphs
2. Universality. Unlike fixed low-pass filters like ChebNet, which excel primarily in homophilic settings, GPR's s learnable filters enable balance low-pes ww--pas and high-pass components, making it suitable for both homophilic and heterophilic graphs. This is one the main goals our paper - achieve superior performance on homophilic and heterophilic tasks. Fixed polynomial filters in ChehNet and Bernstein- hased methods approximate spectral responses up to fixed order, limiting their ability model complex spectral properties.
3. GPRGNN escapes oversmoothing. GPR weights are adaptively learnable, which allows GPR-GNN to avoid over-smoothing and trade node and topology feature informativeness. See Section 4 of Chien ct al. (2020) for more thcoretical analysis on the same and proofs, which is beyond the scope of this work. GPR not only mitigates feature over-smoothing, but also works on highly diverse node label patterns (See Section and 5 of Chien et al. (2020))
4. Capturing node features and graph topology. In many important graph data processing applications, the acquired information includes both node features and observations of the graph topology. GPRGNN jointly optimizes node feature and topological information extraction, regardless of the extent which the node labels are homophilic or heterophilic.
5. Filter Bank Construction. Using GPR based spectral filters, helps us to effectively construct a filter bank where each adaptive filter contributes specific spectral protile, enabling the model to aggrogate information across different spectral bands. This approach captures diverse patterns node features and topology, unlike ChehNet or Bernstein- based methods, which rely on fixed polynomial approximations and lack such flexibility.
7.5 THEOREMS FOR CURVATURE ENCODING
Theorem 7 (Bochner's Theorem). Moeller et al. 2016 A continuous, translation-imvariant kernel K.xx, y) (x y) on R" is positive definite if and only if there exists non-negative measure B. such that Vp is the Fourier transform of the measure.
7.5.1 PROOF OF DEFINITION
2
Proof. Using the Bochner's theorem stated above, our curvature kernel Xas has the expression:
Ka(Ra, Ro) VR (n. Ra) = iutRo -Rs) RR) p(w)dd E.. (Fa (Fo "}
(26)
22

---

Published as a conference paper at ICLR 2025
where Eu (R) c. Since kernel KR and measure p(w) real, extract the real part of (6):
Ks (Ra; Rb)) B cos(w(Ra - R.))] Bu cos(waa) cos(wRs) + sin(wR. sin (w)))))))
(27)
The above formulation suggests approximating the expectation by the Monte Carlo integral, i.e. (R Ki) s ut de Σ cos(w>Ra) (Lo/6)) sin(wiRa) sin(w)nn), with wi...,, p(w). Therefore, we propose finite dimensional functional mapping to I2 as:
T gd R
cos(wi sin(w) cos(wae R), sin(wa
(28)
de
The unknown probability distribution p(w) is estimated using the inverse cumulative distribution function (CDF) transformation as in Xu et al. (2020). Since our GNN is operating in the mixed-curvature space, we must map defined curvature kernel based representations the product manifold. We do using the
exponential map, for a node with ORC curvature (xx)) as:
Pute (R(x))
[1== K(v)
( Rdc (R(z))))
(29)
= go 11==1
My (1)) (R(x))
(30)
MM (e) denotes the exponential map on the 9th component manifold with curvature K(g): || is the concatenation operator and go : pdr + pde is Riemannian projector. We need because we maintain single product manifold for CUSP with total dimension dy. So, upon taking the exponential map with respect this product manifold, required to project the curvature embeddings the required dimension de.
where expo ((0) Rdce
7.5.2 PROOF OF THEOREM 2
Proof. We begin by recalling that in Euclidean space, the curvature kernel AR is: ICa (Ra [6) (oRAc (Ra), Pade (Ri.) W/s (Ri. Ri). The key property here is translation invariance:
(R + 7 Rs 2) = Ka(Ka, Ra) VR Rt).
Next, move to the product manifold pdce which consists of multiple components of different curvatures, such hyperbolic, spherical, and Euclidean spaces.
each component manifold Ma with curvature K(g), the stereographic inner product (., T&M x T.M + R. is defined on the tangent plane of the Riemannian manifold as:
(u, v) n² g (Xi)² (u,
where the conformal factor X is defined as:
+ x||
This conformal factor modulates the stereographic projection in the curved space, and it ensures that distances are mapped correctly in the manifold space. Now, consider the inner product hetween the curvature embeddings ppec (Fa) and Pue (Ke) in the mixed-curvature space.
KC (K Ro)
to M, M ((o) (Ra), + MC (Ro))
where each component manifold M, A, A4) contributes the overall inner product in the product manifold pdc. Using the stereographic inner product in cach component, we can write:
KF Ra)
((t) X
2 (Paaic (Ra), Pade (Ra)).
q=1
We now need to show that translation invariance holds in the mixed-curvature product manifold. Since the conformal factor X depends only on the norm ||x||2, any translation by constant č does not affect the relative difference between curvature embeddings. Specifically, for any constant shift
Kr + Ro R +
(xx (x)w)) Wh (R + + - (Ro + 2) = Wo Ro)-
Thus, the kernel in the mixed-curvature space remains invariant to translation, completing the proof.
23

---

Published as a conference paper at ICLR 2025
7.6 EXPERIMENTATION
7.6.1 DATASETS
The performance of CUSP evaluated over eight benchmark datasets two primary tasks: Node Classifi- cation (NC) and Link Prediction (L2). These datasets encompass both homophilic and heterophilic domains. Detailed descriptions of each dataset are provided below.
1. Citation Networks. Cora. PubMed, and Citeseer (Sen et al. 2008 Yang et al. 2016 are citation networks in which nodes symbolize research papers, and edges denote citation links between them. Each node labeled with its subject category. This dataset is commonly utilized for node classification because of its pronounced homophilic properties.
2. Wikipedia grapht. Chameleon and Squirrel (Rozemberezki et al. 2021 are heterophilic graphs derived from Wikipedia articles. Nodes represent articles, and edges represent hyperlinks between them. Node labels correspond to website traffic levels.
3. Actor Co-occurrence Network. Actor (Tang et al. 2009) is heterophilic graph dataset where nodes depict and edges signify co-oceurrences the same Wikipedia page. The node labels correspond to the professional background the actors.
4. Webpage graphs. Texas and Cornel are parts of the WehKB dataset, and are sparsely connected het- erophilic graphs. Here, nodes represent web pages, and edges represent hyperlinks between them. Labels reflect different types of webpages.
7.6.2 BASELINES
This part offers an in-depth discussion of the baseline models against which CUSP compared. We classify the baseline models into three categories: Spatial, Riemannian, and Spectral methods, which each address distinct facet of graph neural network architectures.
Spatial baselines. The first kind of baselines includes the traditional spatial methods, which directly operate the node features and their immediate neighborhoods.
1. GCN (Kipf & Welling 2016). Graph Convolutional Networks (GCNs) represent one of the foundational graph neural networks that utilize spectral graph convolution in spatial domain. They derive node em- beddings by combining features from neighboring nodes via a linear combination involving the adjacency matrix and the nodes' features.
2. GAT VVhičković et al., 2017]. Graph Attention Network (GAT) introduces attention mechanisms to graph neural networks. Each node assigns learnable attention weights its neighbors and aggregates their fea- tures based on these weights.
3. GraphSAGE. (Hamilton et al. 2017). GraphSAGE is an inductive technique designed to learn node em- heddings by sampling and aggregating features from fixed set of neighboring nodes, instead of processing the entire graph. This method enables GraphSAGE to create embeddings for nodes encountered during training by using efficient neighborhood sampling.
Riemannian Baselines. Riemannian models function within non-Eute Euclidean spaces (such as hyperbolic or spherical manifolds) and are tailored for graph data characterized by intricate geometric properties (e.g. hicrarchical or cyclic structures).
1. HGCN (Chamn al. 2019). Hyperbolic Graph Convolutional Networks utilize hyperbolic geometry to represent the hierarchical and tree- like characteristics of graphs. This approach extends GCN to hyperbolic space by introducing a hyperbolic variant of the convolutional operation. is especially suitable for datasets that exhibit hierarchical or likelike configurations.
2. HGAT (Zhang et al. 202
Hyperbolic Graph Attention Network (HGAT) extends Graph Attention Networks (GAT) into hyperbolic space by integrating attention mechanisms with hyperbolic geometry, and calculates the attention weights among the nodes the hyperholic space enhance the aggregation of features.
3. RGCN (Bachmann et al. 2020). xGCN allows for learning the curvature of each node in a graph and generalizes GCN to operate in mixed-curvature spaces. The curvature parameter determines whether node lies in hyperbolic, spherical, Euclidean space. By learning curvature adaptively, xGCN offers flexibility modeling graphs with regions of different geometries, providing a better fit for graphs with complex structures.
http: /www/ cmu. www.w/wwww......./.. http://ww............cccc..../aa bttp:///hhooll////////bbbbb
24

---

Published as a conference paper at ICLR 2025
4. QGCN (Xiong al. 2022 enabling functionality in mixed-curvature spaces. This network capable of modeling graph regions with both positive and negative curvature.
GCN extends GCN a Riemadnnn manifold.
5. SelfMGNN (Sun et al. 2022). SelfMGNN generates embeddings within mixed-curvature space through self-supervision. dynamically allocates varied curvatures to different regions of the graph by utilizing a mixed-curvature embedding space. This approach incorporates both self-supervision and mixed-curvature learning to improve performance on heterogeneous graphs.
Spectral Baselines. These techniques utilize the eigenvalues of either the graph Laplacian or adjacency matrix to establish convolutional filters that function in the frequency domain.
1. ChebyNet (Defferrard al. 2016). ChebyNet implements spectral convolutions through polynomial approximation of the graph Laplacian, sidestepping the expensive process of eigenvalue decomposition. Instead, it approximates the convolution using Chebyshev polynomials. This approach allows ChebyNet to execute localized graph convolutions efficiently, making it well-suited for handling larger graphs.
2. BernNet (He et al. 2021), BerNeet BemNetemmloys Bersttein polynomials to approximate graph filters, providing flexible management over the filter's frequency response. This method extends polynomial-base -aasiall--aedddd-- graph filters and is adaptable to various frequency elements in graphs.
3. GPRGNN (Chien et al. 2020). The Generalized PageRank Graph Neural Network (GPRGNN) builds upon the Personalized PageRank (PPR) approach, integrating it into the framework of graph neural net- works. It propagates node features through the graph by using weighted sum of adjacency matrix powers, dynamically adjusting both homophilic and heterophilic graphs.
4. FiGURe (Ekbote al. 2024). FiGURe employs adaptive filters to capture various sections of the graph spectrum, enabling to learn both high-pat sass and low- pass filters specific to the task. It dynamically selects the optimal filter bank to accurately represent the graph's 's architecture.
7.6.3
EXPERIMENTAL RESULTS FOR LINK PREDICTION
Baseline
Cora
Citeseer
PubMed
Chameleon
Actor
Squirel
Texas
Comell
Av. A Gain
GCN
88.54_051
85, 85,42.009
90.31
86. 86.07
15.122
90.01 ao15
69.08
73.09
9.58
GAT
85.45-006
87.23-2011
87.65+004
88. 18.99
87.33-008
90.23+0.14
+8.7
75.17
9.31
SAGE
87.12
2007
90.0940m0
90.01
86.062071
91.02a001
76.54
77.98
6.97
HGCN
91.63_055
13:1ww
91.04
91 05
90.01 20:00
74.03 69.9
6.34
HGAT
90.43-0m
91.02:#0.u6
88, 88.99
89.77
90,99=00:
89.22+40.4
71.58
72.03+a022
7.66
RGCN
92,04_000
93.33
92.45
92.033:06
90.45.008
16.09
23.05
5.56
QGCN
92.17-00
92.75
92. 22.164000
91 11.67
91 20:0
90.98
75. 14.44
73. 89
5.65
SeiMGNN
93.12:004
92.99.0041
90.99
93.51
91.98:001
10.15
74.51
78. 28
4.28
ChebyNet
88.23
89.22:a006
86.5446.29
90.01
88.09:0044
13.45 92.13
79.01
7.33
BerNeet
86.34=0.13
$7.09=0000
85. 25.34
87.15#007
87. 87.22=0015
91.22
77. 77.65=057
78. 34.44.
8.12
GPRONN
91.16=072
93.05:00ai
92.03
91.22:0..6
89.76=0062
92.34-6.23
76.05
80.04::012
4.96
FiGURe
91,98=000
94.33
92.67a003
93.09
90.11:0299
95,43a006
76.99
80.12anns
3.82
CUSP
95.08_.11
96.88
96.01:991
97.66:2.33
96.04_.03s
97.17=am
81.23:2114
85.23
0
Imp.
1.96
3.34
4.15
4.06
1.74
3.58
Table 8: Performance comparision of CUSP with baselines for LP task (Mean AUC Score + 95% confidence interval). First, Second and Third best performing models are highlighted.
Dataset
CUse
CUS2
CUSFtop
CUSP
CUSP poo!
CUSP yd
Cora
95.0810.13
92,45
93.2110a2
93,781033
92, 13.030
93.0210.27
Citeseer
96.88=n4s
94.03=0030
95.34=022
94.01 94.08=029
#0.31
94.56+0.28
PubMed
96.01:m01
93.52=0.0
94.81=a.0
94.92+038
94.11
94.1610.39
Chameleon
97.6619.33
95.02.104
96,231052
96.
13.13.0
95.67
Actor
96.04+t..s
91.45
93.99=032
92.81
91.98+0.47
92. 92.13+0049
Squirrel
97.17...11
93.14:1022
95.561007
94.331..43
93.75.0.32
92.8910.14
Texas
81.23
78.45
79. 59
42
79.23:10.7
70.81
Cornell
85.23+005
82.8920.32
83.91
84.23+037
82.31
82.45+0422
Avg. A Gain
3.0437
1.5462
1.8625
2.8312
2.8262
Table Ablation study (LP) results. CUSP euc is the Euclidean variant, CUSP tap uses the traditional Laplacian, CUSP enc gets rid of curvature encoding, CUSP, pool replaces Cusp pooling with concate- nation, and CUSP fu uses a single filter instead of filter bank. Av. A Gain represents the average gain of CUSP over the ablation model in that column, averaged across the different datasets.
25

---

Published as a conference paper at ICLR 2025
CUSP
Cora
Citeseer
PuhMed
Chameleon
Actor
Squiree
Texas
Cornell
8 8"4
93. 10
94,33
25.4
97. 47
05.25500.4
26.05
75.43
a6
(1 (8*)2 E
00
95.11+025
94.52+0.3
96 66.66.9..99
95.344038
95.40
=0495=042
84,80:n43
E4 x 8 x g22
93. 20
93.25
95 35.65
97. 120.77
94.92a0.0
95. 51 2015
21123
85.23
E11 g
93.50+025
94.12+0.1
97.66:9.33 95.3220.45
97.17=a11 20=0000
80.30=045
78.02=047
(HI10)2 E
93.25
93.05
:6.01
96. 80 ap
96.04
96.15 15
79.50
34.60
EP 3:44
92.70
94.71
15.45
16.51
95.00
88 95 1n:s
79.70
81.20
g24 x 1224
88.50
91.23310:1
91.1230.47 49.99
91.20 19
83.75 29.08
E1 849 x 1210
95.08 0.13
96,88
95.55
94.44 94.44
96.25 25.55
:1.07:0.9
64.60:000
(8h)2 1922 (Hi6aa
88.05..000
90.351..4
86.30.0o4s
89.34
93.33
90,25,00
10
89.10:044
91.01
93.9340.55
96.1910550
95.25
92.30
77.77
79.44:055
Table 10: Performance comparison of CUSP with different manifold signatures for Link Prediction (LP). Best performing signatures are Bold, and cases with large decline in performance because of manifold mismatch are in Blue.
Dataset
Signature
Cora
[10(-0.21, 0.31) x (001)))=((00000 (-0.1900.8))
(0, 0.31)
Citeszer
[39(-0075,022) x89 ( (-0.5,...33)
PubMed
(0000000000
Chameleun
[116] -0.34,0.0) (.400)888((00)7)
(-0..1.710025) x (0.5 0.34)
Actor
(20.770.7,0.1) x (-"0
x 0.44).))
Squirrel E10(-0.17,00 0.23) x (-0.54,,
8 (40,888 0.339)
Texas B x 5 (-0.18 x ( 0.50)
Cornell
EP(-0.41, 0.19)
8 (P00009,00 x (20 0.30.5)
Table 11: Learning results of CUSP on Link Prediction (LP) task for the best performing product signature. Format of entries- - manifold type (dim) (learnt curvature, learnt manifold weight).
Dutaset
(1)
(
Z
(
(()
(())
(
(100)
Cora
0.1125
0,2393
0.0520
0.0504
0.0676
0.0272
0.1531
0.1251
0.0939
0,0095
0.0894
Citeseer
0.2131
0.0150
0.2195
0.0283
0.0922
0.1530
0.0350
0.0520
0.0282
0.1254
0,0582
PubMad
04279
0.1793
0,0285
0.0296
0.0563
0.3870
0.0603
0.0324
0.0622
0,0271
0.1104
Chameleon
0.0601
0.1136
0.1694
0.0924
0,1329
0.1605
0.1026
0.0157
0.0475
0.0344
0.8709
Actor
0.1230
0.032]
0,0324
0.1147
0.1287
0.3700
0.0136
0.0389
0.0604
0,0691
0,0172
Squirel
0.0289
0.2099
0.0854
0.0475
0.1042
0.1279
Texas
0.0890
0. 0.1983
0.0179
0.4570
0.0035
0.1429
0.0177
0.0087
0.0474
0.0131
0.0346
Comell
0,0886
0. 0,2026
0.0181
0.4460
0.0033
0,1472
0,0183
0.0089
0.0487
0,0134
0,0048
Table 12: Learned filter weights (Link Prediction) for the top-performing split, distinguishing be- tween homophilic (favoring low-pass filters) and heterophilic (favoring high-pass filters). First, second, and third highest filter weights are highlighted.
7.6.4 ESTIMATING PRODUCT MANIFOLD SIGNATURE
In our model, the mixed-curvature product manifold pdc is essential for representing the geometric structure of the data. The curvature configuration needed for each dataset depends the intrinsic geometry of its graph. To generalize across various datasets, we aim to determine the optimal signature of the product manifold, specifically the proportions of hyperbolic, spherical, and Euclidean components. This estimation is based on analyzing the Ollivier-Riee Ricci curvature (CRC) distribution as a heuristic. See Figures in Appendix 7.2. for the ORC distribution of multiple datasets. For datasets with many positively curved edges, we seleet Spherical component, and for those with negatively curved edges, we choose Hyperbolic component. For examplc, the curvature distribution of PubMed's edges in Figure [ shows two significant peaks around -0.45 and +0.25. Given this distribution, we opt for Spherical and Hyperbolic components when evaluating CUSP on PubMed. Empirically, the best performance for PubMed is achieved with the signature (1I E. We initialize the curvatures of PubMed's component manifolds with these prominent values: HI with 00.45 and with -0.25. We select two hyperbolic manifolds to capture different curvature ranges.
An overview of this simple idea is provided in Algorithm T By systematically analyzing the curvature distribu- tion, our heuristic-based algorithm identifies the manifold signature that best represents the dataset's underly- ing geometric structure. We heuristically cluster the curvature distribution and identify the centroid curvatures without altering their order frequencies. The use of predefined dimensions allows for flexibility based on experimental settings. Since optimal dimension allocations can vary and are complex to analyze, we manually set the dimensions of the component manifolds as a hyperparameter. This ensures fair and uniform comparison across multiple datasets, as different datasets may perform best with different configurations. We do not claim that this algorithm finds the best possible, optimal combination of component manifolds, rather, it estimates potential signature that might be good fit for a particular dataset.
26

---

Published as a conference paper at ICLR 2025
Algorithm Product manifold signature estimation and curvature initialisation
Require:
Edge curvature histogram C {[Nu, K
Threshold distinguish between curved and flat regions
Maximum number of Hyperbolic (Hmax) and Spherical (Smax) components.
Total product manifold dimension d.M
(Optional) Preferred component manifold dimensions &hy ( (e)
Ensure: Product manifold signature pdl = x M Mo
1: Normalize frequencies: J
Σ5-1
Construct weighted curvature set:
f()]
3: Determine optimal number of clusters using methods like the elbow method, constrained by K < b There can be only Euclidean component 4: Cluster C' into K clusters using weighted clustering (c.g., weighted K-means)
Hmax + Smax +1
5: Initialize empty lists H,
for each cluster e clusters
7: Compute cluster centroid curvature Ric Simgdffce ni
lc]
8: Compute total frequency weight = =E Emm.)eedl
9: if < -é and [H|| < Hmax then
D Negative curvature Curvature initialization
10:
Assign manifold component: M₁ 10 Add (Mg, w.) to H else if K. > and [S] S Smax then
12:
b Positive curvature D Curvature initialization
13:
Assign manifold component: M, KK Add (Mq, w.) S
14:
15:
else
16:
Assign manifold component: Mg = 17: Add (Mg, we) 8
b Approximate zero curvature, i.c. Kg E [-c,
18: end if
19: end for
20: Predefined dimensions dree gre gre
"(h)> (s) (e) are provided then
21: Assign dimensions d(g) each component as per predefined values
Dimension assignment
22: else
23:
Set total number of components Q = 7| + [ [8|
Dimension assignment
24: Allocate dimensions d(g) to each component d(,) dM x
We Eper up
Proportional to weights
25:
Adjust d( to ensure E d(a) = dm
26: end if
27: Formulate manifold signature:
pdm
(x) HH H (ossss)e))))
(x (x (o Rd(e)
7.6.5 MORE EXPERIMENTAL SETTINGS
Hyperparameter
Tuning Configurations
Description
L
[5, 10, 20, 25}
Total number graph filters.
(0.2,0.5,00 0.5, 0.7,
Neighbourhood weight distribution parameter for ORC Alpha (initialization) parameter GPR propagation
a
[0.1. 0.3, 0.5. 0.5.
de
16, 32,
Total dimension of curvature embeddings.
AM
{32, 48, 64, 128, 256)
Total dimension of the product manifold.
drepout
(0.2, 0.3, 0.5)
Dropout rate
opochs
[50, 300)
Number of training epochs
0.001.0.011
Learning
woight.dacay
{0, le 4, Se
Weight decay
Table 13: Hyperparameter configurations used in the experiments for all baselines. Some of the hyperparameters specific CUSP. We highlight the final configuration of CUSP for NC in Red.
27


Reviews:
[{"review_id": "NsuG7LHbM7", "reviewer": "Reviewer_nwYb", "summary": "This paper is the first attempt that unifies spectral and curvature signals in graph representation learning. CUSP, a mixed-curvature spectral GNN, introduces three novel components: a curvature-aware Cusp Laplacian operator, a mixed-curvature spectral graph filtering framework, Cusp Filtering, and a curvature embedding method using classical harmonic analysis and a hierarchical attention mechanism called Cusp Pooling. CUSP records state-of-the-art performance on eight real-world benchmarking datasets for Node Classification (NC) and Link Prediction (LP) tasks.", "questions": "In the appendix, the complexity of ORC is analyzed, and it is mentioned that an alternative method is provided to approximate edge ORC in linear time, which is applicable to very large (billion-scale) real-world graphs. How to prove that the proposed alternative method is useful in large real-world graphs? Are there any experiments? As far as I know, the dataset used in the experiment is on the order of 100,000.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Originality. I think the proposed CUSP is innovative in the paradign of graph representation learning. CUSP is well-motivated, and indeed improves the performance significantly.\n- Quality. The paper is well structured. A large number of experiments have been conducted, which are supportive and convincing.\n- Clarity. The method proposed is deeply explored and proofs are presented as well as a detailed description of the algorithm and the rational for the design consideration that were made. The experimental section is typically sufficient. And ablation experiments fully illustrate the effectiveness of each component.\n- Significance. The paper shows state-of-the-art in standard benchmarks. This paper explores how to integrate spectral and curvature signals in graph representation learning, and gives some valuable insights.", "weaknesses": "As mentioned in the questions, the proposed OCR alternative method should be described in detail, or the proposed method should be used in the experiment.", "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": "gsznCnAYqp", "reviewer": "Reviewer_UpZ1", "summary": "The paper introduces Spectro-Riemannian Graph Neural Networks (CUSP), a novel approach to graph representation learning that combines spectral and curvature information into a spectral graph neural network operating on a manifold arising as a product of Euclidean as well as hyperbolic and spherical spaces. Traditional graph neural networks (GNNs) often struggle with diverse graph topologies and varying graph geometries/curvatures. CUSP addresses these challenges by enabling to integrate (geometric) features from both negatively (hyperbolic) and positively (spherical) parts of a given graph. This allows for the creation of more natural node embeddings that better align with the underlying structure of real-world graphs.\nKey components of CUSP include (1) The Cusp Laplacian, which integrates Ollivier-Ricci curvature into the definition of a Laplacian-type matrix on the graph. (2) Cusp Filtering which allows for (high- and low-pass) filtering operatoions on a product manifold where each factor has constant positive, zero, or negative curvature. (3) Cusp Pooling A hierarchical attention mechanism that evaluates the importance of substructures with different curvature characteristics.\nIn the empirical evaluation CUSP's performance is investigated across eight datasets. Here CUSP achieves a good performance (in node classification and link prediction tasks), with sometimes substantial gains over baselines.\nThe research seems to be novel and highlights the potential that  combining geometric and spectral information harbours for the design of GNNs.", "questions": "1) What makes GPR special and why is this used as a backbone? I believe it is equivalent to any polynomial-filter spectral GNN. Why not e.g. use ChebNet, etc.?\n\n2) The (total) dimensions of the product manifolds  of e.g. Table 5 and Table 2 seem to always be  $d=48$. Yet in Table 13 of Appendix 6.6.4 it is indicated that $d = 64$ is the selected dimension of the product Manifold. Could the authors comment? Also, while I have seen Algorithm 1 in Appendix 7.6.5 (which seems to be used as an initial heuristic), it is still not clear to me how individual dimensions of product manifolds and respective factors are found/optimized. Is a grid search performed? If so what are the respective allowed values during this grid search? Could the authors clarify (again?)?\n\n3) In the ablation study on the impact of the CUSP Laplacian, performance using the CUSP Laplacian is compared to performance using the adjacency matrix instead. Could the authors repeat this ablation study comparing with the usual normalized and unnormalized graph Laplacians? This would shed light on whether the performance increase comes from using a Laplacian-type matrix vs. an adjacency type matrix, or indeed from the specific properties of the the Cusp Laplacian.\n\n4) Is it possible to include and discuss some basic spectral characteristics of the CUSP Laplacian (beyond self-adjointness and positivity)? As is, this new matrix is introduced without too much intuition beyond the heat-flow heuristic. Can something e.g. be said about the maximal eigenvalue or first-non-trivial eigenvalue (in a Cheeger-type fashion) for example? I realize the present paper is not mainly theoretical but introduces an architecture. However some additional theoretical foundation would indeed be nice.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well structured and mostly (please see next section) well written. A positive example is the explicit  description of the limitations of previous work that are addressed in this paper (i.e. L1-L3 in the introduction).\n\n Including the notation table in Appendix 7.1 helps to keep track of the various mathematical concepts.\n\nThe idea underlying the introduced CUSP Laplacian of including curvature information into the Laplacian-matrix describing the graph is neat. \n\nFurthermore the idea of taking into account locally varying curvature structures by allowing for factors of varying curvature in the product manifold is nice. \n\nThe performance of the proposed architecture in both the node-classification and link-prediction tasks on the considered datasets is solid. \n\nThe ablation study on the impact of the signature of the product manifold structure (c.f. Section 5.1) as well as the surrounding discussion is illuminating.", "weaknesses": "I do have _some_ concerns regarding readability. An easy fix is the image quality in Figure 1. Here the axis labeling of the histograms is not  readable if the paper is printed. Could the authors please fix this by including higher resolution images and/or using a larger font size for axis labeling. \n\nRegarding the paper itself, aside from some typos and grammatical errors that do not impede the flow of the paper too much, I had trouble understanding Section 4.3; especially from line 327 onward: The curvature kernel is defined twice: once using an inner product in an ambient space, and once as a translation invariant entity. I believe what the authors want to convey is that the former definition as utilized in the paper already leads to a translation invariant kernel. Is this correct?\n\nAlso the significance of the Bochner-Minlos theorem is not immediately apparent to me. I only gained some intuition about this after reading the proof of Theorem 2 and Theorem 3 in the Appendix. Could the authors comment more explicitly on the significance of Bochner's theorem here? \n\nIt might also be good to explain (to some extent) and motivate the k-stereographic model in the main text. \nWhile I have some background in differential geometry, I had only ever come across standard stereographic projections.\nEspecially for readers from a pure CS/EE background more details here might be useful, even if the model might be central to Riemannian GNNs. \n\nIn the same direction, it would also be good explain a bit more the respective operations in Table 8 in Appendix 7.2.4 and how they are natural.\n\n\nFinally, in the experimental sections, the datasets that are being used are somewhat old and fairly small. I strongly encourage the authors to also consider newer and much larger datasets  (e.g. using OGBN) and compare their approach with baselines there.", "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": "0hY4ED9919", "reviewer": "Reviewer_iwKN", "summary": "The paper introduces CUSP: integrating mixed-curvature representation learning with GPRGNN.", "questions": "- The authors keep using the term “curvature signal” throughout the paper. What does this term mathematically mean?\n- In κ-right-matrix-multiplication,  why do the authors choose to work with the projection between the manifold and tangent space at the origin? How does this choice affect the empirical results?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper introduces a new GNN model that considers spectral information and the curvature.", "weaknesses": "- The method is incremental. It’s hard to separate the new components in the paper and how they depend on the previous work. Also, there is no theoretical justification for integrating the spectral information in the frequency domain and the curvature in the spatial domain.\n- More details are needed for the heat diffusion equation and heat flow in Section 4.1. For example, as the cooling depends on the direction (from x to y), what is the role of direction in the heat diffusion equation? What is the definition of heat flow? What is the ORC distribution? What is the diffusion rate? How the Wasserstein-1 distance be interpreted as the resistance? Does the resistance depend on the direction?\n- It’s unclear what “$x \\sim y$ denotes adjacency between nodes x and y” means in Proposition 1 in the main text. Also, more details and motivation needed for how $\\\\bar{w}\\_{xy} = e^{\\\\frac{-1}{1-\\\\tilde{\\kappa}(x, y)}}$ is designed in main texts. Does this design have favorable properties? How does Cusp Laplacian operator act differently based on $\\\\bar{w}\\_{xy}$?\nThe explanation is only in the Appendix, but an overview or high-level explanation in the main texts can help in understanding the reason behind the proposed component.\n- The font size in Figure 3 is too small. It makes it very difficult to follow complicated figures.\n- More explanation is needed for how GPRGNN jointly optimizes node features and topological information extraction.\n- It’s unclear what does curvature domain $\\mathbb{K}_{\\mathbb{P}}$ represent in line 321-322. In addition, it’s unclear why in line 251, the product space is $\\\\mathbb{P}^{d\\_{\\\\mathcal{M}}}$ but in line 322 the authors are interested in the $d\\_{\\\\mathcal{C}}$-dimensional product space $\\mathbb{P}^{d\\_{\\\\mathcal{C}}}$.\n- Based on Eq. (4), $\\widetilde{\\kappa}\\in\\mathbb{K}$. However, it’s unclear what $\\widetilde{\\kappa}(x)$ represents in Eq.(5).\n- It’s unclear what the Riemannian projector is in line 347.\n- It’s unclear what M2 is in line 319. There is no M2 in the paper.\n- There is no theory in Theorem 2. It’s confusing to call it a theorem when the claims are only definitions.\n- It’s unclear why translation invariant is a desirable property in the functional curvature encoding in the proposed method.\n- It’s unclear how functional curvature encoding gives more attention to differently curved substructures.\n- It’s unclear which part of the implementation is adopted from Ni et al. (2019) in line 412.\n- It’s unclear what do the authors mean by they “heuristically determine the signature of our manifold $\\mathbb{P}$ (i.e. component manifolds) using the discrete ORC curvature of the input graph”. It’s unclear how many hyperbolic spaces and spherical spaces are considered.\n- It’s unclear what the hyperparameter L represents.\n- It’s unclear how many layers are considered in the experiments.\n- It’s unclear what the experimental configurations and hyperparameters of the competing methods are.\n- The spacing between the tables and the main texts in Section 5 is very tight and narrow.\n- The paper is missing important spectral GNNs: OptBasisGNN, ChebNetII, CayleyNet, APPNP, JacobiConv, and Specformer.\n- It’s unclear how L3 is resolved using the proposed method.\n- The paper needs more work on proofreading. For example:\n    - the English style is not consistent. Sometimes the authors use “normalised”, but sometimes they use “normalized”.\n    - The word “Laplacian” sometimes has the uppercase letter L, but sometimes it is lowercase l.\n    - The tangent space notation is not consistent. \n    - There is a comma in Eq.(15), but there is no sentence afterward.\n    - The exponential map and logarithmic map are defined using boldface letters, but these notations are not consistent in the appendix\n    - In line 366, the sentence is not finished. The punctuation in Eq. (6), Eq. (7), and Eq. (8) is missing.\n    - The notation of  Wasserstein-1 distance is not consistent in the main paper and appendix\n    - The reference pointer is missing in line 405\n\n## Minor\n- Unclear what is $\\mathbf{W}$ in line 141\n- In line 160, missing $\\times \\ldots \\times $ in $\\mathbb{P}$\n- A formal definition of Wasserstein-1 distance is missing\n- Unclear what is $\\psi_{xy}$ in Appendix 7.3\n- In line 996, it’s unclear what is the element-wise product between a matrix $\\mathbf{L}$ and a scalar $e^{\\frac{-1}{1-\\tilde{\\\\kappa}(x, y)}}$\n- In Eq.(25), $\\mathbf{X}_{i:}$ is not defined\n- $\\delta$ in line 172 and $\\delta_{vs}$ in line 181 are not defined\n- Unclear why $\\omega_{d_f}$ in line 341, there is no $d_f$ in Eq. (4)", "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": "k3P7SdXmFC", "reviewer": "Reviewer_JRrs", "summary": "This paper introduces CUSP, a graph representation learning model that integrates graph discrete curvature with a geometric extension of generalized PageRank. The method is comprehensively evaluated, demonstrating strong performance against several baselines.", "questions": "1. Do you use the same neural networks $f_\\theta$ in Line 263 for all component spaces?\n2. How is the Riemannian projector $g_\\theta$ in Line 347 defined?\n3. Could you clarify how Theorem 1 applies to CUSP? What insight does Theorem 1 provide?\n4. How does the runtime of your pipeline compare to other baselines?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(+++) **Novelty and Relevance**: The proposed method is new and of interest to the geometric machine learning community.\n\n(+++) **Strong Empirical Evaluation and Performance**: The method is thoroughly evaluated, demonstrating improved performance on downstream tasks over the considered baselines.", "weaknesses": "There are several issues with the presentation that detract from the strengths. These concerns should be straightforward to address.\n\n(----) **Presentation**: The paper’s presentation is dense and, at times, unclear. Examples include:\n* **Figure 3**: The figure is very busy. While each individual component is informative and of high quality, combining them without clear visual separators makes the overall figure difficult to interpret.\n* **Section 4**: This section is similarly dense, as it combines mathematical background, theoretical motivations, and the presentation of the CUSP architecture. Perhaps this section could focus on the method and architecture, with theoretical discussions (e.g., of heat diffusion) moved to Preliminaries or a new dedicated section.\n* **Notation**:\n  * The notation in Equations 2, 3, 5, 6, 7, and 8 is dense and may be difficult to parse for readers unfamiliar with geometric machine learning or the gyrovectorspace approach. (Also refer to \"Relation to Existing Literature\" below.) Adding equation annotations or using plain English function names (e.g., Enc for encoding) could improve readability.\n  * \"ORC for nodes\" is defined in line 176 without introducing the notation $\\tilde{\\kappa}(x)$ which is then used, e.g., in Equation 5. (There is a notation table in the appendix, but it does not cross reference the definition.)\n* **Baseline Taxonomy**: The classification of baselines in Section 5 into \"spatial\" and \"Riemannian\" is inaccurate, as the Riemannian baselines are also spatial. \"Spatial-Euclidean\" and \"Spatial-Riemannian\" could be more accurate.\n\n(---) **Mathematical Motivation**: The justification for the Cusp Laplacian (Proposition 1) and Functional Curvature Encoding (Theorem 2) are more of rationales or motivations than rigorous proofs. For example, Proposition 1 motivates the Cusp Laplacian by introducing a modified resistance term in a heat flow equation. This would perhaps become clearer if presented as a definition, framed as, “If one assumes a resistance of the form …,” which would help the reader recognize the principles from which the Cusp Laplacian is derived.\n\n(--) **Relation to Existing Literature**: Generalizing pipelines from Euclidean to Riemannian spaces by replacing Euclidean transformations with Moebius operations is a well-established pattern in geometric machine learning. Portions of this work follow this pattern, such as adapting PageRank GNN to product manifolds (Section 4.2) and using Moebius operations in the functional curvature encoding (Section 4.3) and cusp pooling (Section 4.4). Early works in hyperbolic graph neural networks such as [1] introduced these operations with clear motivation, via, e.g., illustrations of log and exp maps between manifolds and their tangent space. Since then, these operations have also been more broadly understood and interpreted within the framework of gyrovector spaces, aligning with Ungar's original work cited in the paper. See, e.g., [2-8]. In this work, however, the geometric components of the model are not similarly well-motivated. Perhaps a brief motivation for the operations would be helpful.\n\n\n[1] Chami, I., Ying, Z., Ré, C., & Leskovec, J. (2019). Hyperbolic graph convolutional neural networks. NeurIPS.\n\n[2] Hatori, O. (2017). Examples and Applications of Generalized Gyrovector Spaces. Results in Mathematics.\n\n[3] Kim, S. (2016). Gyrovector Spaces on the Open Convex Cone of Positive Definite Matrices. Mathematics Interdisciplinary Research.\n\n[4] López, F., Pozzetti, B., Trettel, S., Strube, M., & Wienhard, A. (2021). Vector-valued distance and gyrocalculus on SPD matrices. NeurIPS.\n\n[5] Nguyen, X. S. (2022). The Gyro-structure of some matrix manifolds. NeurIPS.\n\n[6] Nguyen, X. S., & Yang, S. (2023). Building neural networks on matrix manifolds: A Gyrovector space approach. ICML.\n\n[7] Nguyen, X. S., Yang, S., & Histace, A. (2024). Matrix Manifold Neural Networks++. ICLR.\n\n[8] Zhao, W., Lopez, F., Riestenberg, J. M., Strube, M., Taha, D., & Trettel, S. (2023). Modeling graphs beyond hyperbolic: GNNs in SPD matrices. ECML PKDD.", "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)