Effective Structural Encodings via Local Curvature Profiles
Authors: Lukas Fesser
Melanie Weber
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Discrete Curvature
Rewiring
Positional Encodings
Structural Encodings
Primary area: learning on graphs and other geometries & topologies

Abstract: Structural and Positional Encodings can significantly improve the performance of Graph Neural Networks in downstream tasks. Recent literature has begun to systematically investigate differences in the structural properties that these approaches encode, as well as performance trade-offs between them. However, the question of which structural properties yield the most effective encoding remains open. In this paper, we investigate this question from a geometric perspective. We propose a novel structural encoding based on discrete Ricci curvature (Local Curvature Profiles, short LCP) and show that it significantly outperforms existing encoding approaches. We further show that combining local structural encodings, such as LCP, with global positional encodings improves downstream performance, suggesting that they capture complementary geometric information. Finally, we compare different encoding types with (curvature-based) rewiring techniques. Rewiring has recently received a surge of interest due to its ability to improve the performance of Graph Neural Networks by mitigating over-smoothing and over-squashing effects. Our results suggest that utilizing curvature information for structural encodings delivers significantly larger performance increases than rewiring.

Published as a conference paper at ICLR 2024
EFFECTIVE STRUCTURAL ENCODINGS VIA LOCAL CURVATURE PROFILES
Lukas Fesser Faculty of Arts and Sciences
Melanie Weber
Department of Applied Mathematics Harvard University
Harvard University
lukas_ fas. harvard.eed
mweberêg. aararadd.ddd
ABSTRACT
Structural and Positional Encodings can significantly improve the performance of Graph Neural Networks in downstream tasks. Recent literature has begun systematically investigate differences in the structural properties that these ap- proaches encode, as well as performance trade-offs between them. However, the question of which structural properties yield the most effective encoding remains open. this paper, we investigate this question from a geometric perspective. We propose a novel structural encoding based on discrete Ricci curvature (Local Curvature Profiles, short LCP) and show that it significantly outperforms existing encoding approaches. We further show that combining local structural encod- ings, such as LCP, with global positional encodings improves downstream perfor- mance, suggesting that they capture complementary geometric information. Fi- nally, we compare different encoding types with (curvature-hart hased) rewiring tech- niques. Rewiring has recently received a surge of interest due to its ability to im- prove the performance of GNNs by mitigating over-smoothing and over-squashing effects. Our results suggest that utilizing curvature information for structural en- codings delivers significantly larger performance increases than rewiring.
INTRODUCTION
Graph Machine Learning has emerged powerful tool in the social and natural sciences, well as in engineering (Zitnik et al. 2018 Gligorijević et al. 2021 Shlomi et al., 2020 Wu et al. [022). Graph Neural Networks (GNN), which implement the bessage-passingg paradigm. have emerged as the dominating architecture. However, recent literature has revealed several shortcoming in their rep- resentational power, stemming from their inability to distinguish certain classes of non-isomorphic graphs (Xu et al.) 2018; Morris et al.) 2219)) and difficulties in accurately encoding long-range de- pendencies in the underlying graph (Alo Yahav] [021 Li et al. 2018). A potential remedy comes in the form of Structural (short: SE) and Positional Encodings (short: PE), which endow nodes or edges with additional information. This can be the form of local information, such as the structure of the subgraph to which node belongs its position within it. Other encoding types capture global information, such as the node's position in the graph or the types of substructures contained in the graph. Strong empirical evidence across different domains and architectures sug- gests that encoding such additional information improves the GNN's performance (Dwivedi et al., 2023 Bouritsas et al. 2022 Park al. (022).
Many examples of effective encodings are derived from classical tools in Graph Theory and Com- binatorics. This includes spectral encodings (Dwivedi et al. 2023 Kreuzer al.] (02T). which encode structural insights derived from the analysis of the Graph Laplacian and its spectrum. An- other popular encoding are (local) substructure counts (Bouritsas et al. 2022), which are inspired by the classical idea of network motif's (Holland & Leinhardi 1976). Both of those encodings can result in expensive subroutines, which can limit scalability in practise. In this work, we turn to a different classical tool: Discrete Ricci curvature. Notions of discrete Ricci curvature have been previously considered in the Graph Machine Learning literature, including for unsupervised node clustering (Ni
et al. 2019 Sia et al. 2019 Tian al. 2023), graph rewiring (Topping et al.) 2022 Nguyen al.
'Code available wwwptttppp... //tpt::///ttttt httpschww.....ceeeecceee www.//weeeeeeeeeeeeeeeeeeeeeeeee /ocaa ccraa__ccrtatrr__rrffi

---

Published as a conference paper at ICLR 2024
and for utilizing curvature information in Message-Passing GNNs (Ye et al. 2020 Lai al. Here, we propose a novel local structural encoding based on discrete Ricci curvature termed Local Curvature Profiles (short: LCP). We analyze the effectiveness of LCP through range of experiments, which reveal ICPP's superior performance in node- and graph-level tasks. We further provide theoretical analysis of LCP's computational efficiency and impact on expressivity.
2023
2023
Despite a plethora of proposed encodings, the question of which structural properties yield the most effective encoding remains open. In this paper, we investigate this question from a geometric per- spective. Specifically, we hypothesize that different encodings capture complementary information on the local and global properties of the graph. This would imply that combining different encoding types could lead to improvements in downstream performance. We will investigate this hypothesis experimentally, focusing on combinations of local structural and global positional encodings, which are expected to capture complementary structural properties (Tab. 2.1
Graph rewiring can be viewed as type relational encoding, in that it increases a node's awareness of information encoded in long-range connections during cressage-passingg Several graph rewiring techniques utilize curvature to identify edges to remove and artificial edges to add (Topping et al., 2022
Nguyen et al. (023). In this context, the question of the most effective use for curvature information (as rewiring or as structural encoding) arises. We investigate this question through systematic experiments.
1.1 SUMMARY OF CONTRIBUTIONS
The main contributions of this paper are as follows:
1. We introduce Local Curvature Profiles (short LCP) as novel structural encoding (sec. 3.1 Our approach encodes for each node characterization the geometry of its neighborhood. We show that encoding such information provably improves the expressivity of the GNN (sec. (.2) and enhances its performance in downstream tasks (sec. [.2.1].
2. We further show that combining local structural encodings, such as LCP, with global posi- tional encodings improves performance in node and graph classification tasks (sec. 4.2.2) Our results suggest that local structural and global positional encoding capture complemen- tary information.
3. We further compare LCP with curvature-based rewiring, a previous approach for encoding curvature characterizations into Graph Machine Learning frameworks. Our results sug- gest that encoding curvature via LCP leads to superior performance in downstream tasks (sec. 4.2.3)
We perform a range of ablation studies to investigate various design choices our framework, including the choice of the curvature notion (sec. 4.3)
1.2 RELATED WORK
plethora of structural and positional encodings have been proposed in the GNN literature; notable
examples include encodings of spectral information (Dwivedi et al.) 2022a 2023): 3 node distances
based on shortest paths, random walks and diffusion processes (Li et al. 2020 Mialon et al., 2021); local substructure counts (Bouritsas et al.. 2022 et 2022) and node degree distributions (Cai & Wann 2018). A recent taxonomy and benchmark on encodings in Graph Transformers can be found in (Rampasek al.) 2022). Notions of discrete Ricci curvature have been utilized previously in Graph Machine Learming, including for Graph Rewiring (Topping et al.) 2022 Nguyen et al. Fesser & Weber (023) or directly encoded into pessage-passing mechanisms (Ye et al,
2023
2020 or attention weights (Lai et al., (023). Beyond GNNs, discrete curvature has been applied
in community detection (Ni et al., [2019] Sia et al. 2019
Fesser et al., 2023 Tian et al.) [023)) Weber 2020 and graph subsampling (Weber et al.
representation learning (Lubold et al.] 2023
2017).
among others.
BACKGROUND AND NOTATION
Following standard convention, we denote GNN input graphs as G (X, E) with node attributes X Vl and edges F. C V V, where V is the set of vertices of G.
2

---

Published as a conference paper at ICLR 2024
2.1
GRAPH NEURAL NETWORKS
Message- Passing Graph Neural Networks. The blueprint of many state of the art Graph Machine Learning architectures are Message-Passing Graph Neural Networks (MPGNNs) (Gori al. 2005 Hamilton et al.) 2017). They learn node embeddings via an iterative scheme. where each node's 's representation iteratively updated based on its neighbors' representations, Formally, let x denote the representation of node v at layer 1, then the representation after one iteration of pessaae-passing given by
1+1 0i
A
th (xx)
(EA(,U(")
The number of such iterations is often called the depth of the GNN. The initial representations x are usually given by the node attributes in the input graph. The specific form of the func- tions dR, th varies across architectures. In this work, focus on three of the most popular instances of MPGNNs: Graph Convolutional Networks (short: GCN) (Kipf & Welling, (017)) Graph Isomorphism Networks (short: GIN) Xuu al. 2018 and Graph Atlention Networky (short: GAT) (Veličković et al., 2018).
One way of understanding the utility of GNN is by analyzing its repre- sentational power or expressivity. A classical tool is isomorphism testing, i.c., asking whether two non-isomorphic graphs can be distinguished by the GNN. A useful heuristic for this analysis the Weisfeiler-Lehmall (WL) test (Weisfeiler & Leman 1968), which iteratively aggregates labels from each node's neighbors into multi-sets. The multi-sets sets stabilize after few iterations; the WL test then certifies two graphs as non-isomorphic only if the final multi-sets of their nodes are not identical. Unfortunately, the test is only heuristic and may fail for certain classes of graphs; notable examples include regular graphs. A generalization of the test (k- WL test (Cai et al. 1989)) assigns multi-sets of labels to k-tuples of nodes. It can be shown that the k-WL test is strictly more powerful than the (k- 1)-WL test in that it can distinguish wider range of non-isomorphic graphs. Recent literature has demonstrated that the representational power of MPGNNs is limited to the expressivity of the 1-WL test, which stems from inability to trace back the origin of specific messages (Xu al., 2018 MMoris et al. 22019). However, it has been shown that certain changes in the GNN architecture, such the incorporation of high-order information (Morris et al.) 2019 Maron al. 2019) or the encoding of local or global structural features (Bouritsas et al. [222]] Feng et al. 2022 can improve the representational power of the resulting GNNs beyond that of classical MPGNNs. However, often
Representational Power.
the increase in expressivity comes at the cost of a significant increase in computational complexity.
Structural and Positional Encodings. Structural (SE) and Positional (PE) encodings endow MPGNNs with structural information that it cannot learn on its own, but which is crucial for down- stream performance. Encoding approaches can capture either local or global information. Local PE endow nodes with information its position within a local cluster or substructure, whereas global PE provide information on the nodes' global position in the graph. As such, PE are usually derived from distance notions. Examples of local PE include the distance of node to the centroid of cluster or community it is part of. Global PE often relate to spectral properties of the graph, such as the eigenvectors of the Graph Laplacian (Dwivedi et al. 2023) or random-walk based node similar- ities (Dwivedi et al., (2022)). Global PE are generally observed to be more effective than local PE. In contrast, SE encode structural similarity measures, either by endowing nodes with information about the subgraph they are part of or about the global topology of the graph. Notable examples of local SE are substructure counts (Bouritsas al. 2022, Zhao al. 2022), which are among the most popular encodings. Global SE often encode graph characteristics or summary statistics that an MPGNN is not able to learn on its own, e.g., its diameter, girth or the number of connected compo- nents (Loukas 2019). In this work, we focus on Global PE and Local SE, as well as combinations of both types of encodings.
Over-smoothing and Over-squashing. MPGNNs may also suffer from over-squashing and over- smoothing effects. Over-squashing, first described by Allnn & Yahav (202 characterizes difficulties in leveraging information encoded in long-range connections, which is often crucial for downstream performance. Ooor-smoot (Li et al. 2018) describes challenges in distinguishing node represen- tations of nearby nodes, which occurs in deeper GNNs. While over-squashing is known to particular affect graph-level tasks, difficulties related to over- weor-hno arise in particular in node-level tasks. Among the architectures considered here, GCN and GIN are prone both effects, as they imple-
3

---

Published as a conference paper at ICLR 2024
Geometric Information
Approach
Тype
Encoding
Complexity
Eigenvectors of Graph Laplacian.
LA
Dwivedi et al.
2023
Global PE
O(1V1*)
spectral
RW Dwivedi et al.
2022a
Global PE
Landing probability of k-random walk.
O(V (
k-hop commute time
SUB
Zhao et al.
2022
Local SE
k-substructure counts.
O
motifs (size k)
Node degree distribution
LDP Cai & Wang
2018
Local SE
O(1V)
node degrees
over neighborhood.
LCP (this paper)
Local SE
Curvature distribution
O O(E)
motifs, 2-hop commute time
over neighborhood.
Table Overview encoding approaches, where dmaxx denotes the highest node degree in the graph. (*: variants with lower complexity available)
ment sparse message-passing In contrast, GAT improves the encoding of long-range dependencies using attention scores, which alleviates over-smoothing and over-squashing. A common approach for mitigating both effects GCN, GIN and GAT graph rewiring (Karhadkar et al. 2023 Topping
et al. 2022 Nguyen et al. 2023 Fesser & Weber 2023).
2.2 DISCRETE CURVATURE
Throughout this paper we utilize discrete Ricci cuva- ture, central tool from Discrete Geometry that allows for characterizing (local) geometric properties graphs. Discrete Ricci curvatures defined via curvature analo- gies, mimicking classical properties of continuous Ricci curvature in the discrete setting. A number of such tions have been proposed in the literature; this work, mainly utilize notion by Ollivier (Ollivier, 2009). which we introduce below. Others include Forman's s Ricci curvature, which we introduce in appendix A.I.I
Wi (mm Me)
Figure 1: Computing ORC.
Ollivier's Ricci Curvature. Ollivier's 's notion of Ricci
curvature derives from connection of Ricci curvature and optimal transport. Suppose we endow the 1 l-hop neighborhoods of two neighboring vertices u, with uniform measures m, := deg(j> where z is neighbor of and E {u, v). The transportation cost between the two neighborhoods along the edge = (u, v) can be measured by the W distance between the measures, i.e.,
inf W1 (m m.) mmD(m.,
J d(z 22)m(m, 20))2,2))))))))) dz dzl
where I(m,, m..) denotes the set of all measures over V x V with marginals may Ma Ollivier's 's Ricci curvature (Ollivier] 2009) (short: ORC) is defined
n(u, v) = Wi (Mi,
(2)
do(u, 2)
where da v) denotes the distance between u and in the graph G. The computation ORC shown schematically in Fig.
Graph Rewiring. Previous applications of discrete Ricci curvature to GNNs include rewiring, ie., approaches that add and remove edges to mitigate over-smoothing and over-squashing ef- fects (Karhadkar et al., 2023 Topping et al.] 2022, Nguyen et al., [2033] Fesser Weber 2023). It has been observed that raage connections, which cause over-squashing effects, have low (negative) ORC (Topping et al. 2022), whereas oversmoothing is caused by edges of positive cur- vature in densely connected regions of the graph (Nguyen et al. 2023
Computational Aspects. The computation of ORC can expensive, as it requires solving an optimal transport problem for each edge in the graph, each of which is O (via the Hungarian

---

Published as a conference paper at ICLR 2024
algorithm). Faster approaches via Sinkhorn distances combinatorial approximations of ORC exist (Tia et al. 2023). , but can be much less accurate. In contrast, variants of Forman's curvature can be computed in as little as (dmaax per edge (see appendix A.I.II.
A.I.I.
ENCODING GEOMETRIC STRUCTURE WITH STRUCTURAL ENCODINGS
3.1 LOCAL CURVATURE PROFILE
Curvature-based rewiring methods generally only affect the most extreme regions of the graph. They compute the curvature of every edge in the graph, but only add edges to the neighborhoods of the most negatively curved edges resolve bottlenecks (Topping et al.) (2022)). Similarly, they only remove the most positively curved edges to reduce over-smoothing (gguyen et al. (2023). Fesser & Weber 2023 Regions of the graph that have no particularly positively or negatively curved edges are not affected by the rewiring process, even though the curvature of the edges in these neighborhoods has also been computed. We believe that the curvature information of edges away from the extremes of the curvature distribution, which is not being used by curvature-based rewiring methods, can be beneficial to GNN performance.
We therefore propose to use curvature more specifically the ORC structural node encoding. Our Local Curvature Profile (LCP) adds summary statistics of the local curvature distribution to each node's features. Formally, for given graph G (V, E) with vertex set V and edge set E, we denote the multiset of the curvature of all incident edges multiset), i.c. CMS(v) := {x(u, v) (u, v) E E}. We now define the Local Curvature Profile to consist of the following five summary statistics of the CMS:
node v E V by CMS (curvature
LCP(v)= = imin(CMS())), max(CMS(v)), mean (Cea((C((())) std (CMS(u) median (CMi())
While our experiments the main text are based on this notion the LCP, other quantities from the CMS could be included. We provide results based alternative notions of the LCP in ap- pendix A.4 Note that computing the LCP as a preprocessing step requires us to calculate the curva- ture of each edge in G exactly once. Our approach therefore has the same computational complexity as curvature-based rewiring methods, but uses curvature information everywhere in the graph.
3.2 THEORETICAL RESULTS
We will see below that encoding geometric charac- terization of substructures via LCP leads to an em- pirical benefit. Can we measure this advantage also with respect the representational power of the GNN?
Theorem 1. MPGNNs with LCP structural encod- ings are strictly more expressive than the 1-WL test and hence than MPGNNs without encodings.
Proof. Seminal work by (Xu et al. 2018 Morris
et al. (019)) has established that standard MPGNNs, such GIN,
Figure 2: Illustration of optimal transport
expressive as the 1-WL test. It can be shown via a simple adaption of (Xu et al. 2018 Thm. 3) that adding LCP encodings does not decrease their expressivity, i.c., MPGNNs with LCP are at least as expressive as the 1- test. To es- tablish strictly better expressivity, it is sufficient to identify a set of non-isomorphic graphs that cannot be distinguished by the 1-WL test, but that differ in their local curvature profiles. Consider the 4x4 Rooke and Shrikhande graphs, two non-isomorphic, strongly regular graphs. While nodes in both graphs have identical node degrees (e.g., could not be distinguished with classical MPGNNs), their 2-hop connectivities differ. This results in differ- ences in the optimal transport plan of the neighborhood measures that is used to compute ORC (see
plans for computing the ORC of (u, v) in the 4x4 Rooke (left) and Shrikhande (right) graphs. Edges along which mass of deg(u) deg(u) = is moved are marked in red. We see that <(u, v) = 1 in the Rooke and k(uu, v) = 0 in the Shrikhande graph.
5

---

Published as a conference paper at ICLR 2024
Fig. 2)
As result, the (local) ORC distribution across the two graphs varies, resulting in different
local curvature profiles.
Remark 1. It has been shown that encoding certain local substructure counts can allow MPGNNs to distinguish the 4x4 Rooke and Shrikhande graphs, establishing that such encodings lead to strictly more expressive MPGNNs (Bouritsas et al,, 2022). However, this relies on careful selection of the type of substructures to encode, a design choice that is expensive to fine-tune in practise, due to the combinatorial nature of the underlying optimization problem. In contrast, LCP implicitly characterizes substructure information via their impact on the local curvature distribution. This does not require fine-tuning of design choices. We note that spectral encodings cannot distinguish between the 4x4 Rooke and Shrikhande graphs, their spectra are identical. LDP encodings cannot distinguish them either, as they have identical node degree distributions. Positional encodings based on random walks distinguish them, but only stochastically.
We note that the relationship between the ORC curvature distribution and the WI. hierarchy has been recently discussed in (Southern et al. 2023). They show that the 4x4 Rooke and Shrikhande graphs cannot be distinguished by the 2- WL or 3-WL test, indicating that ORC, and hence LCP encodings, can distinguish some graphs that cannot be distinguished with higher-order WL tests. However, the relationship between ORC and the WL hierachy remains an open question.
EXPERIMENTS
In this section, we experimentally demonstrate the effectiveness of the LCP a structural encoding on a variety of tasks, including node and graph classification. In particular, we aim to answer the following questions:
Q1 Does LCP enhance the performance of GNNs on node- and graph-level tasks?
Q2 Are structural and positional encodings complementary? Do they encode different types of geometric information that can jointly enhance the performance of GNNs?
Q3 How does LCP compare to (curvature-based) rewiring in terms of accuracy?
We complement our main experiments with an investigation of other choices of curvature notions. In general, our experiments are meant ensure a high level of fairness and comprehensiveness Obtaining the best possible performance for each dataset presented is not our primary goal here.
4.1 EXPERIMENTAL SETUP
We treat the computation of encodings or rewiring a preprocessing step, which is first applied to all graphs in the data sets considered: positional or structural encodings are concatenated to the node feature vectors, unless stated otherwise. We then train a GNN on a part of the rewired graphs and evaluate its performance
a withheld set of test graphs. As GNN architectures, we consider GCN (Kipf & Welling 2017), GIN (Xu et al., 2018), and GAT(Veličkove et al. (0118). Settings and optimization hyperparamcters are held constant across tasks and baseline models for all encoding and rewiring methods, so that hyperparameter tuning can be ruled out as a source of per- formance gain. We obtain the settings for the individual encoding types via hyperparameter tuning. For rewiring, we use the heuristics introduced by (Fesser & Weber 2023). For all preprocessing methods and hyperparameter choices, record the test set accuracy of the settings with the highest validation accuracy. As there is certain stochasticity involved, especially when training GNNs, we accumulate experimental results across 100 random trials. We report the mean test accuracy, along with the 95% confidence interval. Details on all data sets, including summary statistics, can be found in appendix 10, Additional results on two of the long-range graph benchmark datasets introduced by (Dwivedi et al., 2022b) can also be found in appendix[A.6
4.2 RESULTS
4.2.1
PERFORMANCE OF LCP (Q1)
presentss the results of our experiments for graph classification (Enzymes, Imdb, Mutag, and Proteins datasets) and node classification (Cora and Citeseer) with only the original node features,

---

Published as a conference paper at ICLR 2024
Le. no additional encodings (NO), Laplacian eigenvectors (LA) (wiieddi al. 2023). Random
Walk transition probabilities (RW) Dwivedi et al. 2022a). substructures (SUB) (Zhao et al. 2022
and our Local Curvature Profile (LCP). LCP outperforms all other encoding methods all graph
classification datasets. The improvement gained from using ICP is particularly impressive for GCN and GAT: the mean accuracy increases by between 10 (Enzymes) and almost 20 percent (Imdh) compared to using no encodings, and between 4 (Enzymes) and 14 percent compared to the second best encoding method.
On the node classification data sets in Table 2 LCP is still competitive, but the performance gains are generally much smaller, and other encoding methods occasionally outperform LCP. Additional experiments on other node classification datasets with similar results can be found in appendix A.7
MODEL
ENZYMES
IMDB
MUTAG
PROTEINS
CORA
CITE.
GCN (NO)
25.4 1.
18.1=1.0
12.72.11
59.6 + 0.9
86.6 0.8
71.7 + 0.7
GCN (LA)
26.5
5.84
70.8 + 1.7
65.9 + 0.7
88.0 + 0.9
75.9 1.2
GCN (RW)
29.7
47.8 1.2
67.0 + 3.2
55.9 1.1
87.6
76.3 1.5
GCN (SUB)
2.2
51.2 1.0
69.0 = 2.8
61.1
8.9
76.9 + 1.1
GCN (LCP)
2.64
6..7
79.0 -
70.9 1.6
88.9
77.1 1.2
GIN (NO)
1.1
1..1
67.5
6.14
0.6
59.9 0.6
GIN (LA)
1.9
6..1
74.0
72.3 1.4
6..4 0.7
GIN (RW)
27.7
69.3
76.0
71.8 1.2
1.0
64.3 1.1
GIN (SUB)
2.1
68.2
2.9
71.5 1.1
79.3 1.1
62.1 1 1.3
GIN (LCP)
32.7
70.6 1.3
82.1
73.2 1 1.2
1.1
63.8 1 1.0
GAT (NO)
22.51.1
68.5 2.7 2.7
72.6 1 1.2
8.8
72.6 1 0.8
GAT (LA)
23.2
19.1
71.0 - 2.6
74.2 1 1.3
84.7
75.1 4 1.1
GAT (RW)
23.4
49.7
70.8 2.4
73.0 +: 1.2
0.9
75.8 1 1.4
GAT (SUB)
25.0
50.9
72.4 2.7
75.7
85.0 1.2
76.3 = 1.2
GAT (LCP)
3.0
1.1
82.0
78.5
85.7 L.
76.6 + 1.2
Table Graph (Enzymes, Imdb, Mutag, and Proteins) and node classification (Cora and Citeseer) accuracies of GCN, GIN, and GAT with positional, structural, or no encodings. Best results for each model highlighted in blue.
4.2.2 COMBINING STRUCTURAL AND POSITIONAL ENCODINGS (Q2)
To answer the question if and when structural and positional encodings are complimentary, we repeat the experiments from the previous subsection, only this time combine one of the two structural encodings considered (SUB and LCP) with one of the positional encodings (LA and RW). The re- sults are shown in Table While we find that the best performing combination always includes LCP in all scenarios, the performance gains achieved depend on the model used. Using GCN, combining LCP with Laplacian eigenvectors Random Walk transition probabilities improves performance on three of our six datasets, with Mutag showing the most significant gains (plus 7 percent). Us- ing GIN, we performance improvement five of our six datasets, with Proteins showing the largest gains (plus 3 percent). Finally, GAT shows performance gains on four of our six datasets, although those gains never exceed two percent.
When comparing the accuracies attained by combining positional and structural encodings (Table with the accuracies attained with only one positional or structural encoding (Table 2 we note that combinations generally result in better performance. However, we also note that the right choice of positional encoding seems to depend on the dataset: Random Walk transition probabilities lead to higher accuracy in 14 of 18 cases overall, Laplacian eigenvectors only in 4 cases. We believe that these differences stem from the different topologies of the graphs in our dataset, whose geometric properties may be captured better by certain encoding types than others (see also Table 2.1
4.2.3 COMPARING STRUCTURAL ENCODING AND REWIRING (Q3)
In the last set of experiments, we compare the LCP, i.e. the use of curvature as a structural encod- ing, with curvature- based rewiring. We apply BORF Nguyen et al. (202)), an ORC-based rewiring strategy, the data sets used far. Table 4 shows the performance of three model architec- tures on the rewired graphs without any positional encodings (NO) and with Laplacian eigenvectors (L.A) or Random Walk transition probabilities (RW). Comparing the (NO) rows in Table 4 with the

---

Published as a conference paper at ICLR 2024
MODEL
ENZYMES
IMDB
MUTAG
PROTHINS
CORA
CHE
GCN (LCP, LA)
2.1
60.
83.4 3.1
1.
76.7 8.
GCN (LCP, RW)
34.8
62.6=
86.1
1.57
14
77.5
GCN (SUB. LA)
2..
48.4=
3.3
1.
81
GCN (SUB, RW)
29.8
5..3
65.5
1..
87.8
74.4 1.5
GIN (LCP, LA)
2.7
70.8
79.2
1.2
1.
63.2 +
GIN (LCP, RW)
31.7
72.1
82.4 1.8
7..2
66.3 1 1.1
GIN (SUB, LA)
1.9
08.3=14
1.9
1.1
1.3
64.1 1.1+122 1.2
GIN (SUB, RW)
28.7
1.19
2.4
1.2
1.6
62.3
GAT (LCP, LA)
33.6 2.1
64.3 1.2
81.0
1.6
1.
77.2 1 1.3
GAT (LCP, RW)
35.1 2.4
1.8
81.2
1.74
1.5
77.4 1.5
GAT (SUB, LA)
22.9 1.8
50
72.5
2.9
1.6
1.3
76.9 = 1.6
GAT (SUB, RW)
26.5 1.3
48.0
71.2 2.8
1.7
8..7
77.1 + 1.4
Table 3: Graph (Enzymes, Imdb, Mutag, and Proteins) and node classification (Cora and Citeseer) accuracies of GCN, GIN, and GAT with combinations of positional and structural encodings. Best results for each model highlighted in blue.
(LPC) rows in Table 2 we see that using the ORC to compute the LCP results in significantly higher accuracy on all data sets, compared to using it to rewire the graph. We believe that an intuitive expla- nation for these performance differences might be that rewiring uses global curvature distribution, iee. compares the curvature values of edges and then adds or removes edge at the extremes of local curvature distribution, the LCP
the distribution. The LCP, on the other hand, is based could be considered more faithful to the idea that the Ricci curvature is an inherently local notion.
As extension, we also ask whether use them on the original graph before rewiring, to maintain some information of the original graph rewiring has added and removed edges. Comparing the (LA) and (RW) rows in Table 4 with the (LCP, LA) and (LCP, RW) rows in Table 3 we see that the LCP-based variant outperforms the rewiring- based encodings attains the best performance in only two cases on the node classification data sets.
should combine positional encodings with the LCP, or
all graph classification data sets. Combining rewiring and positional
MODEL
ENZYMES
IMDB
MUTAG
PROTEINS
CORA
CITE.
GCN (NO)
26.0 12
48.6 0.9
2.4
6..2
87.9
73.4 + 0.6
GCN (LA)
26.3 1.7
1.2
75.5
6.2
86.1
74.7 + 0.8
GCN (RW)
24.0 1.8
4.1
74.0 2.8
1.1
0.9
75.7 0.8
GIN (NO)
31.9 1.2
6..7
2.8
1.2
78.4
6.71
GIN (LA)
28.1 1.6
7.12
78.3
+.3
77.3
64.3 1.0
GIN (RW)
28.4 1.7
2.4
7.60
1.3
7..
6.1
GAT (NO)
21.7
1..1
2.11
73.6
73.4
GAT (LA)
25.
52.9 1.2
1.44
1.5
85.3
75.4
GAT (RW)
22.0 1.7
52.1 1 0.9
68.5
2.0
74.1 1.7
84.2 1.2
76.1 + 1.6
Table 4: Graph (Enzymes, Imdb, Mutag, and Proteins) and node classification (Cora and Citeseer) accuracies of GCN, GIN, and GAT with positional, structural, encodings, graphs rewired using BORF.
LCP and GNN depth. Rewiring strategies are often used to mitigate over-smoothing, for exam- ple by removing edges in particularly dense neighborhoods of the graph (Fesser Weber (2023), which in turn allows for the use of deeper GNNs. As Figure 4.3 shows, using the LCP as structural encoding can help in this regard as well: the average accuracy of GCN with LCP structural encod- ings (y-axis) does not decrease faster with the number of layers (x-axis) than the average accuracy of a GCN on a rewired graph. Both ways of using ORC lose between and 5 percent as we move from 5 GCN layers to 10.
4.3 DIFFERENT NOTIONS OF CURVATURE
So far, we have implemented LCP with Ollivier- curvature in all experiments. However, other notions of curvature have been considered in Graph Machine Learning applications, including in rewiring. (Fesser & Weber (2023) use the Augmented Forman-Rica curvature (AFRC), which enriches the Forman-Ricci curvature (FRC) by considering 3-cycles (AFRC-3) or 3- and 4-cycles
8

---

Published as a conference paper at ICLR 2024
AFRC-3 and AFRC-4 in particular are cheaper to compute than the ORC and have been show to result in competitive rewiring methods
(AFRC-4). For details FRC and AFRC, appendix A.I.1
(Fesser & Weber 2023 As such, one might ask if we could not also one of these curvature
notions to compute the I.C..
LCP Curvature
ENZYMES
IMDB
MUTAG
PROTEINS
FRC
1.1
1.1
7..0 +.
61.1 1.3 62.6 64.2 7.1
AFRC-3
28,0
50.7 1.
AFRC-4
2.4
ORC
2.6
6..7
7.9
7.69
Table 5: Graph classification accuracies of GCN with LCP structural encodings using FRC, AFRC- 3, AFRC-4, and ORC. Best results highlighted blue.
We train the same GCN used in the previ- ous sections with the LCP structural encoding
on our graph classification data sets. Table 5
shows the mean accuracies attained using dif-
Graph Clossification Accuracy
ferent curvatures to compute the LCP. We note
that all four curvatures improve upon the base-
line (no structural encoding), and that gener- ally, performance increases as we move from the FRC to its augmentations and finally to the ORC. This might not come as a surprise, be since the FRC and its augmentations thought of as low-level approximations of the ORC (Jost& & Münch (2021)) Our results there- fore seem to suggest that when we use curva- ture structural encoding, GNNs are gener- ally able to extract the additional information contained in the ORC. This does not seem to be true for curvature- based rewiring methods, where we can use AFRC-3 or AFRC-4 without
SCN Buin
Number Layers
Figure 3: Graph classification accuracy with in- creasing number of GCN layers. Dashed lines show accuracies using BORF, normal lines accu- racy using the LCP.
significant performance drops Nguuyen et al.) (2023). Fesser & Weber 2023
Our experimental results also suggest that the classical Forman curvature is surprisingly effective as faster substitute for ORC. The choice of which higher-order structures to encode (i.e., AFRC-3 vs. AFRC-4) impacts the ability of LCP to characterize substructures with higher-order cycles. Hence, depending the graph topology, the choice of FRC AFRC over ORC will affect performance. For example, the case of Imdb, using FRC seems to work well, which we attribute to the special topology of the graphs in the Imdb dataset (see appendix A.9 for more details).
5 DISCUSSION AND LIMITATIONS
In this paper we have introduced Local Curvature Profiles (LCP) as novel structural encoding. which endows nodes with a geometric characterization of their neighborhoods with respect to dis- crete curvature. Our experiments have demonstrated that LCP outperforms existing encoding ap- proaches and that further performance increases can be achieved by combining LCP with global positional encodings.
comparison with curvature-based rewiring, previously proposed tech- nique for utilizing discrete curvature in GNNs, LCP achieves superior performance.
While we establish that LCP improves the expressivity MPGNNs, the relationship between LCP and the k- hierachy remains open. Our experiments have revealed differences in the effective- ness encodings, including LCP, between GNN architectures. An important direction for future work is more detailed analysis of the influence of model design (type of layer, depths, choice of hyperparameter) with respect to the graph learning task (node- vs. graph-level) and the topology of the input graph(s). In addition, while have investigated the choice of curvature notion from computational complexity perspective, further research on the suitability of each notion for different tasks and graph topologies is needed.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
MW was partially supported by NSF award 21 12085.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trunsactions Pattern Analysis and Machine Intelligence, 45(1):657-668, 2022.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. ICRL Representation Learning Graphs and Manifolds, 2018.
J.-Y. Cai, M. Furer, and N. Immerman. An optimal lower bound the number of variables for graph identification. In 30th Annual Symposium on Foundations of Computer Science, pp. 612- 617, 1989.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representutions, 2022a.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2022b.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 35: 4776-4790, 2022.
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmenta- tions of Forman- Riccaii curvature. arXiv preprint SEti:2309.09384, 2023.
Lukas Fesser, Sergio Serrano de Haro Iváñez, Karel Devriendt, Melanie Weber, and Renaud Lam- biotte. Augmentations of Forman's Ricci curvature and their applications in community detection. arXiv preprint arXiv:2306.0644 064444 2023.
Robin Forman. Bochner's Method for Cell Complexes and Combinatorial Ricci Curvature. vol- ume 29, pp. 323-374, 2003.
Vladimir Gligorijevic, P Douglas Renfrew, Tomasz Kosciolek, Julia Kochler Leman, Daniel Beren- berg, Tommi Vatanen, Chris Chandler, Bryn C Taylor, Ian M Fisk, Hera Vlamakis, et al. Structure- based protein function prediction using graph convolutional networks. Nature communications, 12(1):3168, 2021.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2, pp. 729- 734, 2005.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In NIPS, pp. 1034-1034, 2017.
Paul W Holland and Samuel Leinhardt. Local structure in social networks. Sociological methodol-
ogy, 7:1-45, 1976.
Jost and S. Liu. Ollivier's Ricci curvature, local clustering and curvature- inequalities graphs. Discrete & Computational Geometry, 51(2)3300-322, 2014.
10

---

Published as a conference paper at ICLR 2024
Jürgen Jost and Florentin Münch. arXi::2110.0455, 2021.
Characterizations of forman curvature.
arXiv preprint
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works. In ICLR,,R.00 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21629, 2021.
Xin Lai, Yang Liu, Rui Qian, Yong Lin, and Qiwei Ye. Deeper exploiting graph structure information by discrete Ricci curvature in a graph transformer. Entropy, 25(6), 2023.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably
more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 0444465-4777,, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference on Learning Representations, 2019.
Shane Lubold, Arun G Chandrasekhar, and Tyler H McCormick. Identifying the latent space ge- ometry of network models through analysis of curvature. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(2):240-292, 2023.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Grégoire Mialon, Dexiong Chen, Margot Sclosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2 100.220066.666. 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, 2is/2007.0866.3 2020. [ttpsstts:///at
orrg/ abs/ http:////...a....ooa////000....0 08663
Khang Nguyen, Nong Minh Hieu, Vinh Due Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using Ollivier-Ricci eurvature. In In- ternational Conference on Machine Learning, pp. 25956-25979, PMLR, 2023.
Chien-Chun Ni, Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with Ricci flow. Scientific reports, 91):1-12, 2019.
Y. Ollivier. Ricci curvature of Markov chains on metric spaces. Journal of Functional Analysis, 256 (3):810-864, 2009.
Wonpyo Park, Woonggi Chang, Donggeon Lee, Juntae Kim, and Seung-won Hwang, Grpe: Relative positional encoding for graph transformer. arXiv preprint wwXiv:2201.12787 2022.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
11

---

Published as a conference paper at ICLR 2024
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-Ricci curvature-based method to com- munity detection in complex networks. Scientific reports, 9(1):1-12, 2019.
Joshua Southern, Jeremy Wayland, Michael Bronstein, and Bastian Rieck. On the expressive power of Ollivier-Ricci curvature on graphs. In TAG-ML Workshop, 2023.
Yu Tian, Zachary Lubberts, and Melanie Weber. Curvaturo-based clustering graphs. arXiv preprint urXiv:2307.10155, 2023.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M.
Bronstein. Understanding over-squashing and bottlenecks graphs via curvature. In Interna- tional Conference on Learning Representations, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. ICLR, 2018.
Melanie Weber. Neighborhood growth determines geometric priors for relational representation learning. In International Conference Artificial Intelligence and Statistics, volume 108, pp- 666,276,22 2020.
Melanie Weber, Emil Saucan, and Jürgen Jost. Characterizing complex networks with Forman-Ricoi curvature and associated geometric flows. Journal of Complex Networks, 5(4):527-550, 2017.
Weisfeiler and A Leman. The reduction of a graph canonical form and the algebra which Informatsia, vol. 2(9): 1968.
appears therein. Nauchno-Techhiccheee
Shiwen Wu, Fei Sun, Wentao Zhang. Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey, ACM Computing Surveys, 55(5):1-37, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint urXiv:1810.008206 2018.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting supi-super learning with graph embeddings. CoRR, abs/1603.088611 2016. URL http:://axii..oo abs/
6033 03861
Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, and Chao Chen. Curvature graph network. Interna- tional Conference on Learning Representations, 2020.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
Marinka Zitnik, Monica Agrawal, and Jure Leskovee. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i447-i446, 2018.
12

---

Published as a conference paper at ICLR 2024
A
APPENDIX
CONTENTS
Other curvature notions
14
Forman's ss Ricci curvature
14
A. 1.2
Augmented Ricei curvature.
14
A. 1.3
Combinatorial Approximation of ORC
14
A.1.4
Computational Complexity
14
A.2
Best hyperparameter choices
14
A.3
3
Model architectures
15
A.4
Alternative definitions the LCP
15
A.5
Comparison with Curvature Graph Network
15
A.6
Results on long-range graph benchmark datasets
16
A.7
Results other node classification datasets
17
A.8
Results on ZINC dataset
17
A.9
Additional figures
18
10
Statistics for datasets in the main text
18
A.10.1
General statistics for node classification datasets
18
A 10.2
Curvature distributions for node classification datasets
19
A.10.3
General statistics for graph classification datasets
19
A. 10.4 Curvature distributions for graph classification datasets
19
A. Hardware specifications and libraries
19
13

---

Published as a conference paper at ICLR 2024
A.1 OTHER CURVATURE NOTIONS
A.1.1 FORMAN'S 'S RICCI CURVATURE
Ricci curvature is classical tool in Differential Geometry, which establishes connection between the geometry of the manifold and local volume growth. Discrete notions of curvature have been pro- posed via curvature analogies, i.e., notions that maintain classical relationships with other geometric characteristics. Forman [Forman] 2003) introduced a notion of curvature on CW complexes, which allows for a discretization of a crucial relationship between Ricci curvature and Laplacians, the Bochner- Weizenböck equation. In the case of a simple, undirect, and unweighted graph G = (V, E), the Forman- Ricci curvature of edge (u, 2) E can be expressed as
FR(u, v) deg(u) deg(v)
A.1.2 AUGMENTED FORMAN-RICCE CURVATURE.
The edge-level version of Forman's 's curvature above also allows for evaluating curvature contribu- tions of higher-order structures. Specifically, (Fesser Weber (2023)) consider notions that evaluate higher-order information encoded in cycles of order ] k (denoted as A.Fx), focusing on the cases and
AF3(u, = - deg(u) - (v) + 3 v) AF
deg(u) deg(v) + 3/3 (u, v) + (0, v),
where Auu, v) and (u, u) denote the number of triangles and quadrangles containing the edge (u, v). The derivation of those notions follows directly from (Forman 2003) and can be found, e.g.. in (Tian et al. 2023).
A.1.3 COMBINATORIAL APPROXIMATION OF ORC
Below, we will utilize combinatorial upper and lower bounds on ORC for more efficiently com- putable approximation of local curvature profiles. The bounds were first proven by (Jost & Liu 2014), recall the result below for the convenience of the reader. A version for weighted graphs can be found in TTan et al., 2023).
Theorem 2. We denote with #(u, v) the number of triangles that include the edge (u, 2) and d, the degree of v. Then the following bounds hold:
-(1 do du du -1--2- #(u, r)
)
-(1
du du do ) du do S [n(u, & #(u, v)
1 #(u,
#(u, v)
du
Here, we have used the shorthand A b = min(a, b} and a V v= max(a, b}.
1.1.4 COMPUTATIONAL COMPLEXITY
As discussed in the main text, the computation of the ORC underlying the LCP complexity has complexity of ((EE)d In contrast, the combinatorial bounds in the previous section require only the computation of node degree and triangle counts, which results in reduction of the com- plexity to O[ (d)ax)) Classical Forman curvature (FR(..)) can be computed in O(VV), but the resulting geometric characterization is often less informative. The more informative augmented (AFz) and O E d2 (AF
notions have complexities
A.2 BEST HYPERPARAMETER CHOICES
Our hyperparameter choices for structural and positional encodings are largely based on the hyper- parameters reported in (Dwivedi et al. (002)), Dwivedi et al. (2022a), Zhao et al. (2022)). We used their values starting values for grid search, and found random walk length of 16 to work best for RWPE, eigenvectors to work best for LAPE, and a walk length of 10 to work best for SUB, with minimal differences across graph classification datasets. As mentioned in the main text, did not use hyperparameter tuning for BORF, both rather used the heuristics proposed in (Fesser & Weber (2023) )
14

---

Published as a conference paper at ICLR 2024
A.3 MODEL ARCHITECTURES
Node classification. We use GNN with 3 layers and hidden dimension 128. We further use dropout probability of 0.5, and ReLU activation. We this architecture for all node classification datasets in the paper.
Graph classification. We use GNN with 4 layers and hidden dimension 64, We further use dropout probability 0.5, and ReLU activation. We use this architecture for all graph classification datasets in the paper.
Unless explicitly stated otherwise, we train all models until we observe improvements in the validation accuracy for 100 epochs using the Adam optimizer with learning rate 1e-3 and batch size of 16. We use train/val/test split of 50/25/25.
A.4 ALTERNATIVE DEFINITIONS OF THE LCP
In this subsection, we investigate several alternative definitionso the LCP. As before, let CMS(v) : {x(u, u) vu E} denote the curvature multiset. Then define the Local Curvature Profll using extreme values as
LCP(e) = [(CMS(v)), (C)s (CMS(u)),, (CMS()))
where n == deg(v) and (CMS())) & (C)S())) S ... < (CMS(v)).. Similarly, we can define the LCP using the minimum and maximum of the CMS only, i.c.
LCP(e) = [min(CMS(v))) max(CMM(()))
or use the combinatorial upper and lower bounds for the ORC introduced earlier and then define the LCP using the minimum of the lower bounds and the maximum of the upper bounds. Formally, let CMS, = (u, v) : (u, v) E E} and CMSr = {nr(u, v) (u, v) E E}. where K. (u, v) and (u, v) are the combinatorial upper (lower) bounds of k(u, v). The LCP is then given by
LCP(c) == [min(CMS(())), max max(CMS,
We present the graph classification results attained using these alternative definitions of the LCP in Table 6
LCP
ENZYMES
IMDB
MUTAG
PROTEINS
All Summary Statistics
35.4
67.7
7.9
1.6
Mean, Med, and Std
30.2 2.5
64.8 1.3
+.00
69.7 1.1
Min and Max
3.9
1.4
2.4
7.11
Min only
1.70
1.3
2..
66.8
Max only
29.8 + 2.1
63.4
2.64
66.1 1.2
Extreme Values
36.2 + 1.9
65.6
80.1
70.4 1.5
Combinatorial Approx.
32.7 + 1.7
63.9 + 1.3
84.2 2.1 2.1
70.9 + 1.3
Table 6: Graph classification accuracies of GCN with LCP structural encodings using summary
statistics (top) and using the most extreme values (bottom).
A.5 COMPARISON WITH CURVATURE GRAPH NETWORK
Attention weights vs. Curvature. We remark on a previous work that utilizes discrete curvature in the design of MPGNN architectures, aside from the rewiring techniques discussed earlier. Curvature Graph Networks YYe et al.] (2020)) proposes to weight messages during the updating of the node representations by function of the curvature of the corresponding edge. Formally, their version of the previously introduced update given by
k+1 11 = dx
$ PEN.
T(opp w
x
15

---

Published as a conference paper at ICLR 2024
where W is learned weight matrix and (e.p) is function of the ORC of the edge (v, p), which is learned using MLP. We note that this is analogous to the weighting of messages in GAT Veličkovié et al. (2018)) where self attention plays the role 7 ((.pp) In fact, Curvature Graph Network attains similar performance to GAT, and even outperforms it on some node classification tasks. However, attain even better performance the same computational cost using the LCP (Table 7
CORA
CITESEER
CurvGN-1
0.8
1. 7.94 77.1
CurvGN-n
83.2 0.9
GCN (LCP)
88.9 1.0
GAT (LCP)
85.7 1.1
76.6 + 1.2
Table 7: Node classification accuracy of curvature graph network structural encodings.
GCN and GAT with LCP
A.6 RESULTS ON BANG-RANGE GRAPH BENCHMARK DATASETS
MODEL
FUNC
PEPTIDES-STRUCT
GCN (NO)
2..7
0.379 0.013
GCN (LA)
1.85
0.356 +: 0.014
GCN (RW)
4.1
1.854=0.00
GCN (SUB)
2.0
0.360 0.016
GCN (LCP)
44.4
0.352 + 0.017
GIN (NO)
2.2
0.387 = 0.023
GIN (LA)
1.6
0.364 # 0.021
GIN (RW)
48.0
0.368 0.023
GIN (SUB)
47.3 + 24
0.375 0.020
GIN (LCP)
49.6 + 2.2
0.361 + 0.022
Table 8: Mean classification accuracy (Peptides-fumm and mean absolute error (Peptides-stree of GCN and GIN with positional, structural, encodings. Best results for each model highlighted in blue. Note that for Peptides-struct, lower is better.
MODEL
PEPTIDES FUNC
PEPTIDES-STRUCT
GCN (NO)
43.8 1 2.6
0.365 = 0.018
GCN (LA)
45.2 + 2.3
0.348 0.021
GCN (RW)
44.5 2 2.2
0.341 = 0.022
GIN (NO)
19.3 + 1.8
0.378 = 0.025
GIN (LAA)
50.1 2.1
2.1
0.352 0.022
GIN (RW)
50.4
0.350 0.024
Table 9: Mean classification accuracy (Peptides-funce and mean absolute error (Peptides-struuct of GCN and GIN with positional encodings on graphs rewired using BORE, Note that for Peptides- struct, lower is better.
16

---

Published as a conference paper at ICLR 2024
A.7
RESULTS ON OTHER NODE CLASSIFICATION DATASETS
CORNELL
TEXAS
WISCONSIN
AMAZON
MINESWEEPER
TOLOKERS
(NO)
79.1
GCN (LA)
49.4 1:2. 2.1
50.5
2.1
47.3 11
4.3
0.3
79.2 0.4 TIMEOUT
GCN (RW)
48.3 2.4
49.2
2.3
47.1 = 1.3
47.1 07.4
6166 0.9
20.1..2111
GCN (LCP)
50.4 2:2.5
47.4
47.5
52.7
0.8
80.6 + 0.7"
GIN (ND)
36.7 2.3
54.1 3.0
08.0 10 22
47.5 0.4
78.2 4 0.4
78.6 0.2
49.6
62..2
19.2
TIMBOUT
GIN (SUB)
47.9
1.9
80.5
2.8
54.0
23
47.4
1.0
78.9
1.2
78.2 0.9
GIN (LCP)
50.5
+ 2.6
63.6
53.8
2.4
47.2
0.7
$0.1
0.9
79.2 0.0
Table 10: Node classification accuracies of GCN and GIN with positional, structural, codings. Best results for each model highlighted blue. "The LCP on the tolokers dataset was computed using the combinatorial approximations presented earlier. Computing the actual ORC takes longer than 60 minutes, which we consider timeout.
A.8 RESULTS ON ZINC DATASET
MODEL
ZINC
GCN (No)
0.397 0.001
GCN (LA)
0.002
GCN (RW)
0.371
GCN (SUB)
0.375
GCN (LCP)
0.363 +.01
GIN (NO)
+.56600055
GIN (LA)
0.522 + 0.058
GIN (RW)
0.514 0.067
GIN (SUB)
0.511
GIN (LCP)
0.502
GAT (NO)
0.404 0.007
GAT (LA)
0.388 0.011
GAT (RW)
0.382 0.014
GAT (SUB)
0.379 0.012
GAT (LCP)
0.372 0.015
Table 11: MAE GCN, GIN, and GAT with positional, structural, or positional and structural encodings. Best results for each model highlighted in blue.
17

---

Published as a conference paper at ICLR 2024
A.9
ADDITIONAL FIGURES
-01
-00
-04
Figure 4: Example networks from the mutag, enzymes, imdb, and proteins datasets, which for graph classification (top row). The middle row shows the same example networks with their edges colored according to their ORC values. We also depict the adjusted graphs after rewiring using BORF (bottom row).
A.10
STATISTICS FOR DATASETS THE MAIN TEXT
A.10.1
GENERAL STATISTICS FOR NODE CLASSIFICATION DATASETS
CORA
CITESEER
#NODES
2485
2120
#EDGES
5069
3679
# FEATURES
1433
3703
#CLASSES
7
DIRECTED
FALSE
FALSE
Table 12: Statistics of node classification datasets.
18

---

Published as a conference paper at ICLR 2024
A.10.2 CURVATURE DISTRIBUTIONS FOR NODE CLASSIFICATION DATASETS
DATASET
MIN.
MAX. 1.0
MEAN
STD
CORA 0.898
0.139
0.346
CITESEER
-08861
1.0
0.029
0.402
Table 13: Curvature (ORC) statistics of node classification datasets.
A. A.33
GENERAL STATISTICS FOR GRAPH CLASSIFICATION DATASETS
ENZYMES
IMDB
MUTAG
PROTEINS
#GRAPHS
600
1000
188
1113
#NODES
2-126
12-136
10-28
4-620
#EDGES
2-298
52-2498
20-66
10-2098
AVG #NODES
32.63
19.77
17.93
39.06
AVG #EDGES
124.27
193.062
39.58
145.63
#CLASSES
6
2
DIRECTED
FALSE
FALSE
FALSE
FALSE
Table 14: Statistics of graph classification datasets.
A. 10.4
CURVATURE DISTRIBUTIONS FOR GRAPH CLASSIFICATION DATASETS
DATASET MIN.
MAX.
MEAN
STD
ENZYMES
0.382
0.614
0.157
0.230
IMDB
0.007
0.606
0.394
0.223
MUTAG
0.334
0.344
-0.067
0.218
PROTEINS 0.335
0.624
0.185
0.228
Table 15: Curvature (ORC) statisties of graph classification datasets.
Datasets. We conduct our node classification experiments on the publicly available CORA and CITESEER Yang et al. (2016) datasets, and our graph classification experiments on the ENZYMES, IMDB, MUTAG and PROTEINS datasets from the TUDataset collection Morris et 2020
A.11 HARDWARE SPECIFICATIONS AND LIBRARIES
We implemented all experiments in this paper in Python using PyTorch, Numpy PyTorch Geometric, and Python Optimal Transport. We created the figures in the main text using inkscape.
Our experiments conducted local server with the specifications presented in the following table.
COMPONENTS ARCHITECTURE
SPECIFICATIONS
X86-64 UBUNTU 20.04.5 LTS x86 64 AMD EPYC 7742 64-CORE NVIDIA A100 TENSOR CORE 40GB
OS
CPU
GPU
RAM
Table 16:
19


Reviews:
[{"review_id": "seIrtSjaR6", "reviewer": "Reviewer_hevh", "summary": "The paper addresses the crucial issue of improving the performance of GNNs through structural encodings. The authors present a novel approach based on discrete Ricci curvature, termed Local Curvature Profiles (LCP), and demonstrate its significant effectiveness in enhancing GNN performance. They also investigate the combination of local structural encodings with global positional encodings and compare these encoding types with curvature-based rewiring techniques. The paper makes important contributions to the field of Graph Machine Learning and provides valuable insights into the potential of curvature-based encodings.\n\n==================================\n\nUpdate: I appreciate the authors for answering my questions and providing more experimental results. I would like to keep my scores.", "questions": "How well does LCP generalize across different domains, and what factors might influence its applicability in practical scenarios?\n\nAre there any computational bottlenecks when implementing LCP in large-scale graph datasets, and what strategies or optimizations could be considered to address these issues?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- LCP provides a unique way to encode the geometry of a node's neighborhood, and the paper convincingly demonstrates its superior performance in node and graph classification tasks.\n\n- The paper investigates the combination of local structural encodings with global positional encodings, showing that they capture complementary information about the graph. This finding is valuable as it suggests that using a combination of different encoding types can result in enhanced downstream performance. The authors provide empirical evidence to support this claim.\n\n- A theoretical analysis of LCP's computational efficiency and its impact on expressivity is included in the paper.", "weaknesses": "- Some parts of the introduction are a bit dense and may be challenging for readers not deeply familiar with the field. A clearer presentation of the background and motivation could benefit a wider audience.\n\n- Including experiments on a more diverse set of datasets and domains would be better.", "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": "ANRyw7FKun", "reviewer": "Reviewer_JWiJ", "summary": "This paper proposes improving graph neural networks, e.g. graph convnets. The idea is to encode structural information through Local Curvature Profiles, enabling each node to better characterize the geometry of its neighborhood. Instead of rewriting the graph, the proposed approach adds summary statistics about each node's local curvature to the features of each node.\n\nOn a variety of different tasks, this approach improves the performance of the resulting graph neural nets.", "questions": "How do the results compare versus model size? E.g. could making a GCN deeper allow it to implicitly compute these kinds of features itself? What's stopping it from doing that?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper seems reasonable to this reviewer, outperforming baseline encoding approaches or approaches that require rewiring. \n\nPerhaps most surprising to this reviewer is that it improves performance of GATs (seemingly similar to transforms in that they use self-attention?) as it would seem reasonable that such a network would be able to dynamically compute something similar to these statistics.\n\nThe experiments seem reasonably done at least to this reviewer (not an expert in this area at all), involving both LCP itself as well as combining it with positional encoding, and then later rewiring.", "weaknesses": "It's not obvious to this reviewer what the weaknesses are. The main concern to this reviewer is that some large pretrained transformer could do better than any of the proposed methods, but that's a very general concern these days. Possibly this approach or GNNs in general could work better on more specialized tasks where there are a very large number of nodes.", "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": "MoBWdhABQn", "reviewer": "Reviewer_GHx9", "summary": "The paper proposes to use local curvature profile (LCP) for structural encoding in graph neural networks. Several notions of local curvatures are investigated and superior experimental results are shown on several datasets as compared to the baseline.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The introduction of the local curvatures for structural encoding in graph neural networks is the key contribution of the paper.  A theoretical result (Theorem 1) is also established suggesting improved expressivity due to LCP. However the result is rather qualitative without a quantitative characterization of the extent to which the expressivity is improved. Thus the theoretical development is rather light.\n\nOverall the paper is very well written and, for most parts, easy to read. \n\nThe idea is sound and the experiments look convincing to this reviewer.", "weaknesses": "I do not see an obvious weakness in the paper, just like I do not see its development particularly striking.  To me, the paper falls into those works that have a sound intuitive idea, which is validated via empirical evaluation. The paper does not appear to touch on the studied problem (i.e., the issues of over-smoothing and over-squashing) at a fundamental level or at depth. But it is perhaps above the acceptance threshold.", "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": "c1iiND9Ryu", "reviewer": "Reviewer_pewF", "summary": "The paper explores the efficacy of various structural encodings, along with their integration with global positional encodings, to enhance the performance of Graph Neural Networks (GNNs) in downstream tasks. It introduces a novel structural encoding known as LCP, derived from discrete Ricci curvature, which demonstrates superior performance compared to existing encoding methods.", "questions": "1. Could the authors please provide a detailed explanation of the specific approach referred to as 'no encodings (NO)'?\n2. Could the authors please elaborate on how the combination of LCP encoding and position encoding is implemented in Section 4.2.2? I couldn't find any details regarding the actual implementation.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The article introduces LCP encoding which presents how curvature information may affect GNN performance, contributing to a better understanding of the research context and significance\n2. The article conducts comprehensive experiments on various datasets; however, it could benefit from additional experiments to investigate the underlying reasons why LCP is effective", "weaknesses": "1. The article lacks explanations for some crucial implementation steps, making it confusing to read. I suggest the author improve the presentation and logic of the article to enhance clarity (see question 1 and 2)\n2. Please provide definitions for variable names, such as 'd_max.' Currently, there are many variables in the article that are not explained, which can be challenging for newcomers to understand\n3. In spite of keeping settings and optimization hyperparameters consistent among different settings, the authors should still provide the corresponding parameter configurations. This would aid in experiment reproducibility and, as a result, make the results more robust.\n4. In Section 3.1, the authors mention, 'We believe that the curvature information of edges away from the extremes of the curvature distribution, which is not being used by curvature-based rewiring methods, can be beneficial to GNN performance.' I consider this assertion somewhat speculative, and I did not find any subsequent experiments that substantiate this claim. Would it be possible to include relevant ablation experiments to support this hypothesis?\n5. In Section 3.1, the authors define LCP as 'five summary statistics of the CMS.' I would appreciate a more detailed motivation for this particular definition. Additionally, it would be beneficial to include relevant ablation experiments that showcase the impact of removing specific summary statistics to demonstrate their significance in influencing the final results.", "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)