Affinity-Aware Graph Networks
Authors: Ameya Velingker
Ali Kemal Sinop
Ira Ktena
Petar Veličković
Sreenivas Gollapudi
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
message passing networks
effective resistance

Abstract: Graph Neural Networks (GNNs) have emerged as a powerful technique for learning on relational data. Owing to the relatively limited number of message passing steps they perform—and hence a smaller receptive field—there has been significant interest in improving their expressivity by incorporating structural aspects of the underlying graph. In this paper, we explore the use of affinity measures as features in graph neural networks, in particular measures arising from random walks, including effective resistance, hitting and commute times. We propose message passing networks based on these features and evaluate their performance on a variety of node and graph property prediction tasks.

Under review as a conference paper at ICLR 2023
AFFINITY-AWARE GRAPH NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have emerged as a powerful technique for learning relational data. Owing to the relatively limited number of message passing steps they perform-and hence a smaller receptive field-there has been significant interest in improving their expressivity by incorporating structural aspects of the underlying graph. In this puper, we explore the use of affinity measures as features in graph neural networks, in particular measures arising from random walks, including effective resistance, hitting and commute times. We propose message passing networks based these features and evaluate their performance on a variety of node and graph property prediction tasks, Our architecture has low computational complexity, while our features are invariant the permutations of the underlying graph. The measures we compute allow the network to exploit the connectivity properties of the graph, thereby allowing us outperform relevant benchmarks for wide variety of tasks, often with significantly fewer message passing steps. On one of the largest publicly available graph regression datasets, SE----S--POMMMT
we obtain the best known single- model validation MAE at the time of writing.
INTRODUCTION
Graph Neural Networks (GNNs) constitute powerful tool for learning meaningful representations in Euclidean domains. GNN models have achieved significant successes in a wide variety of node prediction Hamilton et al. 2017);] Luan et al. (2019), link prediction [hhag & Chen (0118);
You al. 2019). , and graph prediction Duvenaud et al. (2015); Ying et al.) (2019) tasks. These tasks naturally emerge in wide range of applications, including autonomous driving Chen et al. (2019).
neuroimaging Parisot et al. (2018), combinatorial optimization Gasse et al. (2019); Nair et al. 2020),
and recommender systems Ying et al. (0018), while they have enabled significant seientific ad vances in the fields of biomedicine Wang et al. (202 structural biology Jumper et al. (2021), molecular
chemistry Stokes al. (2020) and physics Bapst et (022)).
Despite the predictive power of GNNs, it is known that the expressive power of standard GNNs is limited by the L-Weisfeiler-Lehmmn (1-WL.) test Xu et al. (2018). Intuitively, GNNs possess most the same power in terms of distinguishing between non-isomorphic (sub-)graphs, while having the added benefit of adapting the given data distribution. For some architectures, two nodes with different local structures have the same computational graph, thus thwarting distinguishability in standard GNN. Even though some attempts have been made to address this limitation with higher- order GNNs Morris et al. (2019), most traditional GNN architectures fail to distinguish between such nodes.
A common approach to improving the expressive power of GNNs involves encoding richer struc- tural/positional properties. For example, bistance-based approaches form the basis for works such as Position- -awtie Graph Neural Networks You et al. (2019), which capture positions/locations of nodes with respect to a set of anchor nodes, as well as Distance Encoding Networks Li et al. (2020), which the first few powers of the normalized adjacency matrix node features associated with set of target nodes.
Here, take an approach that is inspired by this line of work but departs from it in some crucial ways: we seek to capture both distance and connectivity information using general-purpose node and edge features without the need for specifying any anchor target nodes.

---

Under review as a conference paper at ICLR 2023
Contributions: We propose the use of affinity metrics features in graph neural network. Specifi- cally, we consider statistics that arise from random walks in graphs, such as hitting time and commute time between pairs of vertices (see Sections 3.1 and 3.2 We present means of incorporating these statistics as scalar edge features in a message passing neural network (MPNN) Gilmer et al. (2017) (see Section (.44). In addition to these scalar features, we present richer vector-va valued resistive embed- dings (see Section 3.3), which can be incorporated as node or edge feature vectors in the network. Resistive embeddings are a natural way of embedding each node into Euclidean space such that the squared L distancee between nodes recovers the commute time. We show that such embeddings can be efficiently approximated, even for larger graphs, using sketching and dimensionality reduction techniques (see Section
Moreover, we evaluate our networks on a number of benchmark datasets of diverse scales (see Section 5 First, we show that our networks outperform other baselines on the PNA dataset Corso et al. (2020). which includes node and graph algorithmic tasks, showing the ability of affinity measures to exploit structural properties of graphs. We also evaluate the performance
number of
graph and node tasks for datasets in the Open Graph Benchmark (OGB) collection Hu et al. (2020), including molecular and citation graphs. In particular, edge features achieve the state of the art on the OGB-LSC PCQM4Mv1 dataset, which was featured in KDD Cup 2021 competition for large scale graph representation learning.
networks with scalar effective resistance
Finally, we provide intuition for why affinity-based measures are fundamentally different from aforementioned distance-based approaches (see Section (35) and bolster it with detailed theoretical and empirical results (see Appendix D) showing favorable results for affinity-based measures.
RELATED WORK
Our work builds upon a wealth of graph theoretic and graph representation learning works, while focus on a supervised, inductive setting.
Even though GNN architectures were originally classified spectral spatial, we abstain from this division as recent research has demonstrated some equivalence of the graph convolution process regardless of the choice of convolution kemnels (Balcilar al. 2021 Bronstein et al. 2021). Spectrally- motivated methods are often theoretically founded on the eigendecomposition of the graph Laplacian matrix (or an approximation thereof) and, hence, corresponding convolutions capture different frequencies of the graph signal. Farly works in this space include ChebNet Defferrard et al. (2016) and its more efficient 1-hop version by Kipf et al. (Kipf & Welling 2017). which offers a linear function on the graph Laplacian spectrum. Levie et al. (Levie et al. 2018 8) proposed CayleyNets, an alternative rational filter.
Message passing neural networks (MPNNs) Gilmer et al. (0117) perform a transformation of node and edge representations before and after an arbitrary aggregator (e.g. sum). Graph attention networks (GATs) Veličković et al. 2018) aimed to augment the computations of GNNs by allowing graph nodes to "attend" differently to different edges, inspired by the success of transformers in NLP tasks. One of the most relevant works was proposed by Beaini et al. (Beaini al. 2021). i.e. directional graph networks (DGN). DGN uses the gradients of the low-frequency eigenvectors of the graph Laplacian, which are known to capture key information about the global structure of the graph and prove that the aggregators they construct using these gradients lead to more discriminative models than standard GNNs according to the 1-WL test. Prior work Morris et al. (2019) used higher-order (k- (t-dimensional) GNNs, based on k- LL, and a hierarchical variant and proved theoretically and experimentally the improved expressivity in comparison to other models.
Other notable works include Graph Isomorphism Networks (GINs) Xu et al. (018)), which represent a simple, maximally-pone -pwwerll GNN over suscreee-featuree inputs. This work also brought to light the expressivity limitations of GNNs. Hamilton et al. (Hamilton et al. (017) proposed a method to constuct node representations by sampling a fixed-size neighborhood of each node, and then performing a specific aggregator over it, which led to impressive performance on large-scale inductive benchmarks. Bouritsas et al. (Bouritsas et al. 2020) use topologically-awaat detect and count graph substructures, while Bodnar et al. (Bodnar et al. 2021) propose message- passing procedure on cell complexes motivated by a novel colour refinement algorithm to test their isomorphism which prove to be powerful for molecular benchmarks.
message passing to
2

---

Under review as a conference paper at ICLR 2023
Expressivity. Techniques that improve GNN's expressive power largely fall under three broad directions. While we focus on the feature-base direction in this paper, we also acknowledge that it in no way compels the GNN use the additional provided features. Hence, briefly survey the other two, as an indication of the future research in affinity- -based GNNs we hope this work will inspire.
Another avenue involves modulating the message passing rule to make advantage of the desired computations. Popular recent examples of this include DGN (Beaini et al. 2021) and LSPE (Dwivedi) al. 202T). DGNs leverage the graph's Laplacian eigenvectors, but they do not merely use them as input features; instead, they define a directional vector field based on the eigenvectors, and use explicitly anisotropically aggregate neighbourhoods. LSPE features a "bespoke pipeline" for processing positional inputs.
The final direction is to modulate the graph over which messages are passed, usually by adding new nodes that correspond to desired substructures. An early proponent of this is the work of (Morris) al., 2019), which explicitly performs message passing over k-tuples of nodes once. Recently, scalable efforts in this direction focus on carefully chosen substructures, e.g., junction trees (Fey ct al. 2020), cellular complexes (Bodnar et al. 2021.
AFFINITY MEASURES AND GNNS
3.1 RANDOM WALKS, HITTING AND COMMUTE TIMES
Let G = (V, E) be graph of vertices V and edges S V V between them. We define several natural properties of graph that arise from random walk. A random walk on G starting from node u a Markov chain on the vertex set V such that the initial vertex is u, and each time step, one moves from the current vertex to neighbor, chosen with probability proportional to the weight of outgoing edges. We will use π to denote the stationary distribution of this Markov Chain. For random walks on weighted, undirected graphs, we know that n. = 2M degree of node u. and M is the sum of edge weights.
d_ where dy the weighted
The hitting time Huv fom to v defined as the expected number of steps for a random walk starting at u to hit c. We can also define the commute time between u and as K.. H + Hous the expected round-trip time for a random walk starting at u to reach v and then return to u.
3.2 EFFECTIVE RESISTANCE
closely related quantity is the measure of effective resistances in undirected graphs. This quantity corresponds to the effective resistance if the whole graph replaced with circuit where each edge becomes a resistor with resistance equal to the reciprocal of its weight. We will use Res u, v) to denote the effective resistance between nodes and v. For undirected graphs, it is known that Lovász (993) the effective resistance is proportional to the commute time, Res uu v) = 2M Kuv-
Our broad goal is to incorporate effective resistances and hitting times as edge features in MPNN. In Section 3.4 we will show they can provably improve MPNNs' expressivity.
3.3 RESISTIVE EMBEDDINGS
Effective resistances allow us to define the resistive embedding, a mapping that associates each node of a graph G = (V, E, W). where W are the non-negative edge weights, with an embedding vector, Before we specify the resistive embedding, we define a few terms. Let L D - A be the graph Laplacian of G. where D E R=xa the diagonal matrix containing the weighted degree of each node and A E R is the adjacency matrix, whose (i.j)th entry is equal to the edge weight between and j. if exists; and 0 otherwise. Let be the m X n odge-node incidence matrix, where [V] = n and [E] = m, defined as follows: The i-th row of B corresponds to the i-th edge e, (u, 22) of G and has +1 in the u, column and a -1 in the vt-th column, while all other entries are zero. Finally we will use C' E mom to denote the conductance matrix, which is diagonal matrix with Ci being the weight of 7th edge. It is easy to verify that BTCB- = L. Even though L is not invertible, its null-space consists of the indicator vectors for every connected component of G. For example, if G is connected, then L's nullspace is spanned by the all-1's vector Hence, for any vector x orthogonal all-1's, 1's, L- Ltx x, where L is the pseudo-inverse.
'Throughout this section, we will assume that our graph is connected. However everything applics to disconnected graphs, too.
3

---

Under review as a conference paper at ICLR 2023
We can express effective resistance between any pair of nodes using Laplacian matrices Lovász (1993) as (u, v) = (1, LL - 1,), where 1, is an n-dimensional vector specifying the indicator for node We now ready to define the resistive embedding.
Definition 3.1. (Rffective Resistance Embedding) r, C
A key property is that the effective resistance between nodes in the graph he obtained easily from the distance between their corresponding embeddings (see proof in Appendix C):
Lemma 3.2. For any pair of nodes u, U, we have |[r, rel Res(u, v).
One can easily check that any rotation of r also satisfies Lemma 3.2 since rotations preserve Euclidean distances; more generally, if U is an orthonormal matrix, then Ur is also a valid resistive embedding. This poses challenge if we want to use the resistive embeddings as node or edge features: want way to enforce that a (G)NN using them will do so in way that is invariant or equivariant to any rotations of the embeddings. In our current work, we rely on data augmentation: at every training iteration, we apply random rotations to the input ER embeddings.
Remark 3.3. While data augmentation a popular approach for promoting invariant and equivariant predictions, it is only hinting to the network that such predictions are favourable. It is also possible, in the spirit of the geometric deep learning blueprint (Bronstein et al., 2021). to combine ER embeddings with an ((n))-quivvarian GNN, which rigorously enforces rotational equivariance. A popular approach to building equivariant GNNs has been proposed by (Satorras et al. (02T), though it focuses the full Euclidean group (n)) rather than (n). We leave this exploration to future work.
Definition 3.4. Letp:= := E. Tuta be the mean of effective resistance embedding.
We might view as "weighted mean" of r. We will define the hitting time radius, H Hmax, of a given graph as the maximum hitting time between any two nodes:
Definition 3.5 (Hitting Time Radius). Hmax == max H
We will need the following to bound the hitting times we computed:
Lemma 3.6. For any node ||r, pl1
Haaxx
M
The proof follows easily from the fact that p is a convex combination of all r's and Jensen's 's inequality.
Figure 1: Degree 3 graph on 8 nodes, with isomor- phism classes indicated by col- ors. While nodes of the same color are structurally identical, nodes of different colors not. standard GNN lim- ited by the I-WI. cannot distin- guish between nodes of differ- ent colors. However, affinity based networks that use effec- tive resistances, hitting times, or resistive embeddings can distinguish every pair of such nodes.
3.4 INCORPORATING FEATURES INTO MPNNS
We reiterate that our main aim is to demonstrate (theoretically and empirically) that there are good reasons to incorporate affinity-based based measures into GNN computations.
In the simplest instance, a method that improves GNN's expressive power may compute additional features (positional or structural) which would assist the GNN in discriminating between examples otherwise wouldn't (easily) be able to. These features are then appended to the GNN's inputs for further processing. For example, has been shown that endowing nodes with one-hot based identity already sufficient for improving expressive power (Murphy et al. scalar feature Sato et al, (201)) is, of course, possible to create dedicated features that count substructures of interest (Bouritsas et al.] 2020). Further, the adjacency information can be factorised (Qiu et al.) 2018) or eigendecomposed (Dwivedi et al. 202 to provide useful structural embeddings for the GNN.
2019); this was then relaxed to any mandomly-sample
We will focus our attention on exactly this class of methods, it is lightweight and direct way of demonstrating improvements from these computations. Hence, our baselines will all be instances of
Note that the average of all r. 's will be 0. If the graph regular, then p will also be 0.
4

---

Under review as a conference paper at ICLR 2023
the MPNN framework (Gilmer et al. 2017). ) which we will attempt improve by endowing them with affinity- based features. We start by theoretically proving that these features indeed improve expressive power:
Theorem 3.7. MPNNs that make use of any one of (a.) effective resistances, (b.) hitting times, (c.) resistive embeddings are strictly more powerful than the WL-1 test.
Proof. Since the networks in question arise from augmenting standard MPNNS with additional node/edge features, we have that these networks are at least as powerful as the 1-WL test.
In order show that these networks are strictly more powerful than the 1-WL test, it suffices to show the existence of a graph for which our affinity measure based networks can distinguish between certain nodes that standard GNN (limited by the 1-WI. test) cannot.
We present an example of a 3-regular graph on 8 nodes in Figure [] It is well-known that a standard GNN that limited by the I-WL test cannot distinguish any pair of nodes regular graph, as the computation tree rooted at any node in the graph looks identical. However, there are three isomorphism classes of nodes in the above graph (denoted by different colors), namely, V1 = [1,2]. V/2 = {3, 4, 7, 8). and V3= = (5, 6}.
We now show that GNNs with affinity based measures can distinguish between node in V and node in Vj. for * j. We note that the hitting time from to b depends only on the isomorphism classes of and b. Thus, we write ri,j as the effective resistance between node V; and node in Vg. Note that ri.j = Jj and it is easy to verify that:
T1,1 2/3, 15/28, r3,3 4/7, T2. 185/336, 72,3
F3,2 209/336.
Hence, it follows that in message passing step of an MPNN that uses effective resistances, vertices
in V1, V2, and V will aggregate feature multisets V1.1,71.2,71.22 = {2/3, 185/336, 185/ (85/ r2,2, 32.33
(185/336, 15/28, 209/336) and {r2,3, 12,3, r3,3) {209/33 /336/ 209/336, 4/7). respectively, all of which are all distinct multisets. Hence, such an MPNN can distinguish nodes in V1 and Vg. i # j for suitable aggregation function.
If, instead of effective resistance, we use hitting time features or resistive embeddings, our results still hold. This is because, as we showed previously, the effective resistance between nodes is a function of the two hitting times in either direction, as well as of the resistive embeddings of the nodes. In other words, if either hitting time features or resistive embeddings are used as input features for MPNN, this MPNN would be able to compute the effective resistance features by applying an appropriate function (e.g.. Lemma 3.2 for the case of resistive embeddings). Having computed these features, the MPNN can distinguish any two graphs that the MPNN with effective resistance features can.
3.5 EFFECTIVE RESISTANCE VS. SHORTEST PATH DISTANCE
It is interesting to ask how effective resistances compare with shortest path distances (SPDs) in GNNs. given the plethora of recent works that make use of SPDs (c.g., (Ying al.) 2021b You al. 2019 Li et al. 20200). The most direct comparison of our effective resistance-based MPNNs would be to use SPDs as edge features in the MPNNs. However, note that SPDs along graph edges are trivial (unlike effective resistances, which incorporate useful information about the global graph structure).
An alternative to edge features would be use (a) SPDs to a small set of anchor nodes as features in an MPNN (e.g.. P-GNN You et al. (2019) or (b) dense featurization incorporating shortest paths between all pairs of nodes (e.g., the dense attention mechanism in Graphormer Ving et al. (202Tb)). We remark that the latter approach typically incurs O(n²) overhead, which our MPNN-based approach avoids.
We empirically compare models to MPNNs that use approaches (a) and (b). Results on the PNA dataset show that our effective resistance-batt based GNNs outperform these approaches. Furthermore, complement these empirical results with theoretical result showing that under limited number of message- -aassaggp steps, effective resistance features can allow one to distinguish structures that cannot be done using shortest path features. We point the reader to Appendix D for these results.
5

---

Under review as a conference paper at ICLR 2023
4 EFFICIENT COMPUTATION OF AFFINITY MEASURES
In order to use our features, important that they be computable efficiently. In this section, we show how compute approximate the various random walk-based affinity measures. We share results of our method on large-scale graphs in Appendix
4.1 REDUCING DIMENSIONALITY OF RESISTIVE EMBEDDINGS
Given their higher dimensionality, we might find it beneficial to use resistive embeddings as GNN features instead of the effective resistance. Now, the difficulty with using resistive embeddings directly as GNN features is the fact that the embeddings have dimension m, which can be quite large, e.g., up to nt² for dense graphs. It was shown by (Spielman & Srivastava 2011) that one can reduce the dimensionality the embedding while upproximately preserving Euclidean distances. The idea Lemma:
to random projection via a constructive version of the Johnsso--Lndeesttren
Lemma 4.1 (Constructive Johnson- cohnson-Lindenstin Lindenstrauss), Let 22...., Fn E IR be a set of n points; and let an .e...... am E R" be fixed linear combinations. Suppose II is a k x d matrix whose entries are chosen i..dd. from a Gaussian N0,, 1) and consider f, := II
Vk
Then, it follows that for Cllo(mnn)/e? with probability o(1), we huve a, (1 + c)ll E, o1 for every 1 I m.
Using triangle inequality, we can see that the inner products between fixed linear combinations are preserved up to some additive error:
Corollary 4.2. For any fixed vectors B E IR", if we let X = E, 0.0 8 = E, and similarly Y = E, Y = E, then:
(x-)) - (8,
The proof of Corollary 4.2 can be found in Appendix
Therefore, choose desired and k Ollog())/2) and instead use F V - R the embedding, where
f IIBLte. Vi
(I)
for a randomly chosen k x d matrix II whose entries are i.i.d. Gaussians from (0, 1). Then, by Lemma 3.2 and Lemma 4.1 we have that every edge (u, v) E E.
||F. F (1 = Res
with probability at least 1
So the computation of random embeddings. F, requires solving O( (()+m)) logn/e2) many Laplacian linear systems. By using one of the nearly linear time Laplacian solvers Koutis (2014), can compute the random embeddings in the near-linear time. Hence the total running time becomes (n + m) log npoly log log n/e?)
4.2 FAST COMPUTATION OF HITTING TIMES
Note that it is clear whether there is fast method for computing hitting times similar commute times / effective resistances. The naive approach involves solving linear system for each edge, resulting a rumning time of at least Q(nm). which is prohibitive. One of our technical contributions in this paper is method for fast computation of hitting times. In particular, we will show how to use the approximate effective resistance embeddings, F, obtain an estimate for hitting times with additive enror.
Let p E. F.. Just like f being an approximation of r, P an approximation of p. Consider the following quantity:
n 2M Fu, F. p)
(2)

---

Under review as a conference paper at ICLR 2023
We will use this quantity upproximation of Ha,v- In the following part, will bound the difference between H,, and Hu, (proofs of can be found Appendix Our starting point will be expressing Hu, in terms of the effective resistance embeddings.
Lemma 4.3. Hu 2M (rv Tu, No -p- p) where p == E. T..a-
Lemma 4.4. |fa.v Ha,el S 3e -mxx
EXPERIMENTS
As previously discussed, our empirical evaluation seeks show benefits from endowing standard expressive GNNs with additional affinitybbased features. All architectures we experiment with will therefore conform to the message passing neural network (MPNN) blueprint (Gilmer al. 2017). which we now briefly describe for convenience.
Assume that our input graph, G = (V,E), has node features xa E R", edge features Xav R and graph-level features Xg E R for nodes u, E V and edges (u, v) E E. We provide encoders fn : R" + RR, fe Rm + R* and fg R' + I2 that transform these inputs into a latent space:
h (x,)
(0) = (Xav)
he = fo (xx)
(3)
Our MPNN then performs several message passing steps:
H ((+1) (
(4)
where ((t)
=(1n (t)
ham
(0)
hg contains all of the latents at particular process-
(a.
ing step / 2 0.
This process is iterated for 7 steps, recovering final latents H These can then be decoded into node-, edge-, and graph-level predictions (as required), using analogous decoder functions In. De. and 9g:
Ya = 9n (h(())
You ge (h (3)
Yg Og (hg
Generally, f and g are simple MIPs, whereas we use the MPNN update rule for P. It computes message vectors, muv, to be sent across the edge (u, v), and then aggregates them in the receiver nodes as follows:
(++1) m ue
thtt (2, h 12
(6)
h h(+11) 1141
h
Σ
m(+11)
(++1)
(7)
NEN.
The message function uh+1 and the update function d++1 are both MLPs. All of our models have been implemented using the jraph library (Godwin et al. 2020).
We incorporate edge-based affinity features (e.g., effective resistances and hitting times) in fa and node-basd based affinity features (e.g., resistive embeddings) in fn- Note that node-based affinity features may also naturally be incorporated as edge features by concatenating the node features at the endpoints.
Occasionally, the dataset in question will be easy to overfit with the most general form of message function (Equation 6). In these cases, we resort to assuming that & factorises into an attention mechanism:
m ((+1) ac+1 h h()) h!!))
th (n(")
where the attention function is scalar-valued. We will refer to this particular MPNN baseline as graph attention network (GAT) (Veličković et al. 2018).
When relevant, we may also recall the results that particular strong baseline (such as DGN (Beaini et al. 2021) Graphormer (Ying et al.) a02 achieves dataset of interest. Note that these baselines modulate the message passing procedure rather than appending features, and are hence a different category
method their performance is provided for indicative reasons only. Where appropriate, we will use "DGN (features)" to refer to an MPNN that uses the eigenvector flows as additional edge features, without modulating the mechanism.
7

---

Under review as a conference paper at ICLR 2023
5.1 PNA DATASET
The first dataset we explore is the PNA dataset Corso et al. (2020), which captures multimodal setting, This consists of a col- lection of node tasks, ie. (1) Single-source shortest paths, (2) Ec- centricity and (3) Lapla- cian features, as well as graph tasks, i.e. (4) Connectivity, (5) Diam- eter and (6) Spectral ra-
Node tasks
Graph tasks
Model
Avg
SSSP
Ece
Lap feat
Conn
Diam
Spec rad
GAT
-1.730
-2.213
-1,935
-2.644
-1.618
-1.430
-1.538
GCN
-1,592
-2.283
-1.978
-1.698
-0.618
-1.432
-1.541
MPNN
-2.665
-2.235
-2.419
-3.116
-1.887
-2,681
-3.652
MPNN (cand. feat.)
-2.490
-2.136
-1,808
-3.873
-1.69
-2.614
-2813
DGN (features)
-2.743
-2.165
-1.911
-.184
-1.858
-2.814
-3,528
-2.779
-2.146
-1.869
-3.945
-1.922
-2.940
-3881
ER (node) embed.
-2.658
-2.245
-2.493
-3.533
-1.649
-2.886
-3.144
ER (edge) embed.
-2.789
-2.266
-2.125
-4,253
-1.664
-2.807
-3.617
Hitting Times
22816
-2.189
-1.904
-4.397
-1.888
-2.79
-3.720
All ER features
-3.00
-2.789
-3.082
-4.047
-1.858
-2,894
-3.962
Table 1: log(MSE) on the PNA test dataset
dius. PNA dataset is a set of structured graph tasks, and it complements our other datasets. As we can see in Table [ even adding single feature, effective resistance (ER GNN), yields the best average score compared to other models. Using hitting times as edge features improve upon effective resistances. However once combine all ER features, which include effective resistances, hitting times as well as node and edge embeddings, we get the best scores. On these structured tasks, we can that the affinity based measures provide a significant advantage.
5.2 SMALL MOLECULE CLASSIFICATION! OGBG-MOLHIV
The ogbg-mot meog-molhiv dataset is molecular property pre- diction dataset comprised of molecular graphs without spatial information (such atom coordinates). Each
MolHIV
Test % ROC-AUC
GCN
76.06 + 0.97
graph corresponds to a molecule, with nodes repre- senting atoms and edges representing chemical bonds. Each node has an associated 9-dimensional feature, con-
GIN
75,58 + 1.40
MPNN
74.67 = 0.19
DGN
79.70 + 0.97
GSN (GIN VN)
77.99 +: 1.00
taining atomic number and chirality, as well as other additional atom features such as formal charge and whether the atom predict whether a molecule inhibits HIV virus repli- cation or not. Our results are given in Table 2 Note that we provide topological and random walk methods as baselines, including GSN (Bouritsas et al.) 2020). HIMP (Fey et al. 2020), and GRWNN (Nikolentzos & Vazirgiannis 2022).
HIMP
78.80 + 0.82
GRWNN
78.38 0.99
the ring or not. The goal to
ER GNN
77.75 0.426
Hitting Times
76.56 0.915
ER (node) embed.
77.77 1: 0.339
ER (edge) embed.
76,18 + 0.992
ER (node) embed. + HT
78.16 + 0.792
ER (node) embed. (with random rotations)
76.28 1 0.341
ER (node) embed. (with random rotations)
79.13 ::: 0.358
On this dataset, effective resistances provide im- provement over the standard MPNN. We achieve the best performance using ER node embeddings and hit- ting times with random rotations. With these features, our network achieves 79.13% 0.358 test accuracy, which is close to DGN.
Table 2: Test % AUC-ROC the MolHIV dataset. Our results are averaged over seeds.
5.3 MULTI-TASK MOLECULAR CLASSIFICATION OGRG-MOLPCBA
Test Mean Average Precision
Model
Test Mean AP
Model
4 layery
8 liyees
16 layerr
GCN (w/ virtual node)
24.24 + 0.34
MPNN (Godwin al. 2022
27.75%
0.20
27.91%
0.22
27.64% 0.25
GIN (w/ virtual node)
27.03 0.23
SIPIIN FNN
0.11 27.92%
28.07%
0.14
28.29% 1: 0.13
DeeperGCN
27.81 0.38
MPNN NN ER (ours)
28.11% 0.19
28.27%
0.17
28.28%
0.14
HIMP
27.39 + 0.17
MPNN NN HTT (ours)
28.03%
+ 0.15
28.32%
1 0.13
28.20% & 0.19
MPNN NN HT (ours)
28.32% + 0.13
Table 3: oolg-mo performance for various model depths. Best performance across all models is underlined. NN refers to Noisy Nodes.
Table 4: ogbg-molpcha per- formance compared other baselines.
8

---

Under review as a conference paper at ICLR 2023
The ogbg-molpebar dataset comprises molecular graphs without spatial information (such atom coordinates). The aim to classify them across 128 different biological activities. We follow the baseline MPNN architecture from Godwin et al. (2022). including the use of Noisy Nodes.
Mirroring the evaluation protocol of Godwin et al. (002), Table 3 compares the performance of incorporating ER and hitting time (HT) features into the baseline MPNN models with Noisy Nodes, at various depths. What can be noticed is that models utillising affinity- based features are capable of reaching well as exceeding peak test performance (in terms of mean average precision). However, what's s important is the effect of these features at lower depths: it is possible to achieve comparable or better levels of performance with half the layers, when utilising ER or HT features. This result illustrates the potential benefit affinity-basee computations can have on molecular benchmarks, especially when no spatial geometry is provided as input.
5.4 LARGE SCALE GRAPH REGRESSION: OGB-LSC PCQM4MV1
We finally include experi- mental results for one of the largest-scale publicly avail- able graph regression tasks:
Model
#Layers
Noisy Nodes
Validation MAE
MPNN Godwin et
2022
Yes
0.1249 0.0003
MPNN Godwin et
2022
50
No
0.1236 + 0.0001
Gruphormer Ying el m.
23/10
0.1234 0,1218 0.0001
the PCQM4Mv1 dataset from the OGB Large Scale Challenge Hu al. (202T). PCQM4M is quantum chemistry dataset spanning 4 million small molecules, with task to predict the HOMO-LUMO gap, an important quantum- chemical property. It is antici- pated that structural features such as ER could be of great help on this task, the vl version of it provided without any structural information, and the molecule's is geometry is assumed critical for predicting the gap. We report the model validation performance this dataset, in line with previous works Godwin et al. 2022);; Ying et al. (2021a); Addanki et al. (202I).
MPNN Godwin
Yes
MPNN Conformers Aoaain of
2021
32
Yes
0.1212 # 0.0001
MPNN + FR (ours)
32
Yes
0.1197 + 0.0002
Table 5: Single-model OGBG-PCQM4MV Results
PCQM4Mv1 comprises molecular graphs which consist of bonds and atom types, and no 3D 2D coordinates. We reuse the experimental setup and architecture from Godwin et al. (2022), with only compare
one difference: appending the effective resistance to the edge features. Additionally. against an equivalent model which uses molecular conformations estimated by RDKit as an additional feature. This gives baseline which leverages an explicit estimate of the molecular geometry.
Our results are summarised in Table We once again see a powerful synergy of effective resistance- endowed GNNs and Noisy SodeesGodwinnne et a (2022), allowing us to significantly reduce the number of layers (to 32) and outperform the 50-layer MPNN result in Godwin et al.) (0022). Further, we improve on the single-model performance of both the Graphormer Ying al. (202 la) (which won the original PCQM4M contest after ensembling), and an equivalent model to ours which uses molecular conformers from RDKit. This illustrates how ER features can be competitive in geometry-relevan relevant tasks even against features that inherently encode an estimate of the molecule's 's spatial geometry.
Lastly, we remark that, to the best of our knowledge, our result is the best published single-mode result on the large-scale PCQM4M-vI benchmark to date, and the only single model result with validation MAE under 0.0 We hope this will inspire future investigation on affinity-reaated GNNs for molecular tasks, especially in settings where spatial geometry is not reliably available.
6 CONCLUSIONS
In this paper, proposed message passing network based on random walk based affinity measures.
We believe that the comprehensive theoretical and practical results presented in our paper have solidified affinity-based computations as a strong component of a graph representation learner's s toolbox. Our proposal carefully balances theoretical expressive power, empirical performance, and scalability to large graphs Specifically, in future work we would like to see variants of GNN message functions that explicitly make use of affinity-bann based computations, rather than providing them as additional hints to the model.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ravichandra Addanki, Peter W Battaglia, David Budden, Andreea Deac, Jonathan Godwin, Thomas Keck, Wai Lok Sibon Li, Alvaro Sanchez-Gonzale Jacklynn Stott, Shantanu Thakoor, al. Large-scale graph representation learning with very deep gnns and self-supervision. arXiv preprint arX14::210.09422 2021.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference Learning Representations, 2021. URL https://openrees
hett/forum?ide -00.:dddd000000000mm0000
Victor Bapst, Thomas Keek, A wrabska-Barwinsse Craig Donner, Ekin Dogus Cubuk, Samuel Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448 4544,,54455- 2020.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning (ICML), pp. 748-758. PMLR, 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pictro Liò, Guido Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252 2020.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13473 13478, 2021.
Siheng Chen, Sufeng Niu, Tian Lan, and Baoan Liu. Pet: Large-scale 3d point cloud representations via graph inception networks with applications to autonomous driving. In 2019 IEEE international conference on image processing (ICIP), pp. 4395-4399. IEEE, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
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:3844-3852 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in Neural Information Processing Systems, 28:2224-2232, 2015.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with Iearnable structural and positional representations. arXiv preprint arXiv:21 10.020750077555 2021.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs arXiv preprinl urXiv:2006. 12179, 2020.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. arXiv preprint arXiv: 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), pp. 1263-1272. PMLR, 2017.
Jonathan Godwin, Thomas Keck. Peter Battaglia, Victor Bapst, Thomas Kipf, Yujia Li, Kimberly Stachenfeld, Petar Veličković, and Alvaro Sanchez-Gonzzlezz Jraph: A library for graph neural networks in jax., 2020. http://::///tttbbcco///e/tte///e
rrah
10

---

Under review as a conference paper at ICLR 2023
Jonathan Godwin, Michael Schaarschmidt, Alexander L Gaunt, Alvaro Sanchez-Gonzale Yulia Rubanova, Petar Veličković, James Kirkpatrick, and Peter Battaglia. Simple GNN regularisation for 3d molecular property prediction and beyond. In The Tenth International Conference Learning Representations, 2022.
htt.ttspps//peeeeeeeeeeeeeeeeeee net/ www.:eeefffrrrome forum? f w
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint (rXiv:2005000687 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec, Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.094300 2021.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propa- gation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010. 13993, 2020.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-588) 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
In International Conference on Learning Representations (ICLR), 2017.
Ioannis Koutis and Gary L. Miller. CMG: Combinatorial Multigrid. https://github.. 1koutis/cmqg-at
Ioannis Koutis, Gary L. Miller, and David Tolliver. Combinatorial preconditioners and multilevel solvers for problems computer vision and image processing. Computer Vision and Image Understanding, 115(12):1638-II) 1646, 2011. Special issue Optimization for Vision, Graphics and Medical Imaging: Theory and Applications.
Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337-354, 2014.
Ron Levie, Federico Monti, Xavier Bresson, and Michael Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1)997-109, 2018.
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design prov- ably more powerful neural networks for graph representation learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Process- ing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
László Lovász. Random walks graphs: A survey, Combinatorics, 2:1-46, 1993.
Sitao Luan, Mingde Zhao, Xiao-Was Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. Advances in Neural Information Processing Systems, 32: 10945-10955, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L 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 on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4673-4673, PMLR, 2019.
11

---

Under review as a conference paper at ICLR 2023
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang. et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13344 2020.
Giannis Nikolentzos and Michalis Vazirgiannis. Geometric random walk graph neural networks via implicit layers. 2022. URL httpstt::/ wttp:///wwppe..eeeeeeeeoo wwwpat//ooommmmtmm fow.:mmmmmeee1111111
Sarah Parisot, Sofia Ira Ktena, Enzo Ferrante, Matthew Lee, Ricardo Guerrero, Ben Glocker, and Daniel Rueckert. Disease prediction using graph convolutional networks: application autism spectrum disorder and alzheimer's ' disease. Medical image analysis, 48: 1 17-130, 2018.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang. and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 459-467, 2018.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E(n) equivariant graph neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 9323 9332. PMLR, 2021.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J.
Comput., 1016):111311966, 2011.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey Carfrae, Zohar Gloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4);688-702, 2020.
Prasad Tetali. Random walks and effective resistance of networks. J. Theoretical Probability, 1: 101-109, 1991.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018
Juexin Wang, Anjun Ma, Yuzhou Chang, Jianting Gong, Yuexu Jiang, Ren Qi, Cankun Wang, Hongjun Fu, Qin Ma, and Dong Xu. segnn is a novel graph neural network framework for single-cell ma-seq analyses. Nature communications, 12(1):1-11, 2021a.
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXiv:2103. 103.:22003./3355, /3355, 2021b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform bad for graph representation? ArXiv, abs/2106.05234, 2021a.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yae Liu. Do transformers really perform badly for graph representation? In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021. December 6-14, 2021, virtual, pp. 28877-28888 2021b. URL httptttt///pppeeeiingg www.ips..pp... cc http:ippp..pppppp////2222 ht2a:/22c338881222300aaaeaess3s3
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 974-983, 2018.
12

---

Under review as a conference paper at ICLR 2023
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitiik and Jure Leskovec. GNNexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143. PMLR, 2019.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated atten- tion networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv: 2018.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175, 2018.
13

---

Under review as a conference paper at ICLR 2023
Table Training hyperparameters for PNA dataset
Model
#Hidden size
L. rate
#MP steps
#Rotation matrices
#Same Examples
GAT
64
10
GCN
64
10 10-4
DGN
256
10-3
MPNN ER GNN ER (node) embed.
256
10-3
2
128
10-3
2
64
10-3
ER (edge) embed.
256
10-3
2
ER (edge) embed.
256
10
2
All ER features
256
10
2
23
9
HT + ER (rand rot)
512
10
2
23
4
A HYPERPARAMETERS FOR PNA DATASET.
In this section we provide the hyperparameters used for the different models on the PNA multitask benchmark. We train all models for 2000 steps and with layers. The remaining hyperparameters for hidden size of each layer, learning rate, number of message passing steps (only valid for MPNN models), number of rotation matrices and same example frequency (when relevant) are provided in Table (6]
B SCALING TO LARGER GRAPHS: OGBN-ARXIV
Most expressive GNNs that rely on computation of structural features have not been scaled beyond small molecular datasets (such as the ones discussed in prior sections). This due to the fact that computing them requires (time or storage) complexity which is at least quadratic in the graph fize-making them inapplicable even for modest- graphs. This is, however, not the case for our proposed affinity-based metrics. We demonstrate this by scalably computing them on a larger-scale node classification benchmark, ogbn-arXiv (a citation network with the goal predicting the arXiv category of each paper). ogbn-arXiv has 169.343 nodes and 1.166.243 edges, making quadratic approaches infeasible. Using the combinatorial multigrid preconditioner Koutis et al. (201T): Koutis & Miller, constructed the effective resistances this graph in hour on standard MacBook Pro 2019 laptop.
As MPNN models overfit this transductive dataset quite easily, the dominant approach to tackling it are graph attention networks (GATs) (Veličković et al.) 20188.. Accordingly, we trained a simple four-layer GAT this dataset, achieving 72.02% + 0.05 test accuracy. This compares with 71.97% + 0.24 reported for a related attentional bascline on the leaderboard (Zhang et al. 2018), indicating that our baseline performance relevant.
ER embeddings on ogbn-arXiv need to be exceptionally high-dimensional to achieve accurate ER estimates (~11,0000 dimensions), hence we were unable them here. However, incorporating ER scalar features into our GAT model yielded statistically-sinnffeee. 0.03 test accuracy. Hitting time features improve this result further to 72.25% + 0.04 test accuracy. This demonstrates that our fffinity-based metrics can yield useful improvements even on larger scale graphs, which are traditionally out of reach for methods like DGN (Beaini et al. 2021) due to computational complexity limitations.
improvement of 72% +
Reliable global leaderboarding with respect to ogbn-arXiv is difficult, as state-of-the art approaches rely either privileged information (such raw text of the paper abstracts), incorporating node labels as features (Wang et al.) (2021b) proc-procsssing the predictions (Huang et al. 2020), or various related tricks (Wang al. 2021bb. With that in mind, report for convenience that the current state-of-the-ant performance for ogbn-arXin without using raw text is 76. 1% + 0.09 test accuracy, achieved by GIANT-XRT+DRGH
14

---

Under review as a conference paper at ICLR 2023
C
OMITTED PROOFS
Lemma 3.2. For any pair of nodes u, v, we have || rull = Res(u, v).
Proof.
|rw ro ||C BICL/2BL (lu
= =1,, - 1,)) (BB
= (1n - 1,) ( 11,
= =(1, 1.) I - 1,) Res(u, v).
Corollary 4.2. For any fixed vectors a E R", if we let X = E, agti 8 = E, a,ã; and
similarly Y = Bi0 A == E, then:
(x,1) - (8, 8)
(|XII + |)
2
Proof.
Since (X,Y) = (IIX + Y11 - - )1 we can bound (X,Y) - -xx, 8)
from above
as:
2112+ + 1| 811²) - = (Ix + 11 1 1X
(1I + [
x11 +11/+ -1
-|X - -112)
S (e- IXX + +1|1+ + || -1
(9)
(IIX r1p + X - Y11²)
(1X11 ||||3)
where equation followw from Lemma 4.1 with probability 1- o1), by choice of (as Lemma 4.1 guarantees that each of || 1 + I|| + 1 and | 2 (1 + +) Y 2 holds
with probability 1 - o(1), and one can take union bound over the two events).
Lemma 4.3. Hu,v = 2M (r, Fus Nv - p) where p = Σn, TT Tu-
Proof. Consider the following expression of hitting times in terms of commute times by Tetali (1991).
H 2 Ku + Σ (Kr,i - Ku,e)
(10)
Dividing both sides of Equation
10 and using the relation Ka = 2M Res u, v), we see that:
2M Hu,
Res(u, (1 v) + Σ Ty. (Res(v, i) Res(u, i))
2
Iru lol + Σ (Irr, - -ril I|r. - (r:l);
(11)
2
Let's focus on the inner summation. After expanding out the squared norms, we see that:
Σ (Irr,
r:l12 ||r. r.113)
Σ T (||r, 2 ||r,,11)) 2
Σ (r. Fu, rz)
Σ m (||r,112- - -||ra11))
> (To Fu, rs)
(11r,11? - ||ra|1?) - -2(re- .a. Σ ntpr))
(Ilr,]12 ||r=|l?) - -2(r, r.. p).
15

---

Under review as a conference paper at ICLR 2023
Substituting this back into Equation 11 can express 2M Hu,v
2 (Il - rull? 112+ + ||r ||r/] 2(ro Fu. pi) rull
=||xo|1 (Fa, )) (rv Twu -w, P) = (rr -u,, p)-
Lemma 4.4. Hau, Hu,el I ScHaax-
Proof. Using Lemma 4.3 that |Hu,e Hu,el is equal to:
2M [TT F. p) (re Tu, p)l s eM (I|r, r.ll² 1 ||,, -pl?) S 3e
where we used Corollary
4.2 in the first inequality and Definition 3.5 in the last inequality.
D COMPARISON: EFFECTIVE RESISTANCES vs. SHORTEST PATH DISTANCES
Given that effective resistance (ER) captures times associated with random walks in a graph, it is tempting ask how effective resistances compare shortest path distances (SPDs) between nodes in a graph. Indeed, for some simple graphs, e.g., trees, shortest path distances and effective resistances turn out be identical. However, in general, effective resistances and shortest path distances behave quite differently.
Nevertheless, it is tempting ask how effective resistance features compare SPD features in GNNs, especially as there have been a number of recent model architectures that make use of SPD features (e.g., Graphormer (Ying et al.] (02Tb), Position-Awes -wware GNNs (You al., 2019), DE-GNN (Li et al. 20200). We first note that the most natural direct comparison of our ER-based MPNNs with SPD-based networks does not quite make sense. The reason is that the analogous comparison would be to determine the effect of replace ERs with SPDs features in our MPNNs. However, since our networks only use ER features along edges the given graph, the corresponding SPD features would then be trivial (as the SPD between two nodes directly connected by edge in the graph is 1, resulting in constant feature on every edge)!
As result, graph learning architectures that use SPDs typically either (a.) use densely-connected network (e.g., Graphormer (Ying et al. 2021b), which uses a densely-connectee attention mechanism) that incurs ((n²) overhead, (b.) pick small set of anchor nodes landmark nodes to which SPDs from all other nodes are computed and incorporated as node features (e.g., Position-Aware GNNs YYuu et al.) (2019). DE-GNN (Li et al.) 2020 We stress that the former approach generally modifies the graph (by connecting all pairs of nodes) and therefore does not fall within the standard MPNN approach, while the latter includes architectures that fall within the MPNN paradigm.
Furthermore, we note that DE-GNNs are arguably one of the closest proposals to ours, they compute eetaanc--ncodde features. These features can be at least as powerful as our proposed affinity-based features if polynomially many powers of the adjacency matrix are used. However, for all but the smallest graphs, using this many powers will be impractical-in fact, (Li et al. 2020) only use powers of A up to 3, which would not be able to reliably approximate affinity-based features. We also observe that the DE-GNN paper is concerned with learning representations of small sets of nodes (e.g., node-, link-, and tasks, which the authors mention as possible future work. This makes a direct comparison of our methods with DE-GNNs difficult.
and does not show how to handle graph prediction
D.1 EMPIRICAL RESULTS
In an effort to empirically compare the expressivity of ER features with that of SPD features, we once again perform experiments on the PNA dataset, picking the following baselines that make use of SPD features:
The first baseline is roughly an MPNN with Graphormer-base features. More precisely, is densely-connectee MPNN with SPDs from the original graph edge features. In order to retain the structure the original graph, we also use additional edge features to indicate whether not edge in the dense (complete) graph is true edge of the original graph.
16

---

Under review as a conference paper at ICLR 2023
We also explore the of the centrality encoding (in-degree and out-degree embeddings) from Graphormer as additional node features.
The second baseline is the Position-Awant GNN (P-GNN), which makes use of "anchor sets" of nodes and encodes distances to these nodes.
The results of these baselines are shown in Table 7 In particular, we note that our ER-based MPNNS outperform all aforementioned baselines.
Model
Average score
*MPNN + CE
-2.728
"MPNN (dense) SPD
-2.157
*MPNN (dense) CF+ *P-GNN
-2.107
-2,650
MPNN w/ resistive (edge) embeddings
-2.789
MPNN w/ all affinity measure features
-3.106
Table 7: Results on the PNA dataset for MPNNs with Graphormer-based features (yellow) as well SPD-based P-GNNs (orange). Here, CE refers the centrality encoding, which is incorporated in the relevant MPNNs as additional node features. Similarly, SPD refers to shortest path distance features - in the relevant MPNNs, shortest path distances between all pairs of nodes in the graph are incorporated as edge features, along with an additional edge feature indicating whether an edge exists the input graph. Therefore, the MPNN baselines are all variants the same model with additional node/edge features. Similarly, P-GNN (You et al., 2019) uses SPD features with respect to set of chosen anchor nodes. The average score metric is, as before, the average the log( (SFF) metric over all six tasks, as in Table I
D.2 THEORY: ER VS. SPD
In addition to experimental results, we would like to provide some theory for why effective resistances can capture structure in GNNs that SPDs are unable
We will call an initialization function u + (0) on nodes of a graph node-based if it assigns values that are independent of the edges of the graph. Such initialization is, however, allowed to depend on node identities (e.g., for the single-source shortest path problem from a source s, one might find natural to define h = 0 and h +oo for all + s).
Consider the task of computing "single-soure effective resistances." i.e., the effective resistance from particular node to every other node. We show that GNN with a limited number of message passing steps cannot possibly learn single-source effective resistances, even to nearby nodes.
Theorem D.1. Suppose we fix k: > O. Then, given any node-based initialization function ha (0) it impossible for GNN to compute single-source effective resistances from given node w to any nodes within k-hop neighborhood.
More specifically, for any update rule
m (++1) = 1/++1 ((()) fe fe((xu)))
uu
(12)
h((+)) = dc+1 h (fm (EN(())))
there exists a graph G (V, E) and u E V such that after rounds of message passing, (1) Res(u, v) for some 4 within k-hop neighborhood of u.
+
On the other hand, there exists an initialization with respect to which k rounds of message pussing will compute the correct shortest path distances to all nodes within k-hop neighborhood.
Note that the assumption on the initialization function in the above theorem is reasonable because enabling the use of arbitrary, unrestricted functions would allow for the possibility of precomputing effective resistances in the graph and trivially incorporating them as node features, which would defeat the purpose of computing them using passage-passing
17

---

Under review as a conference paper at ICLR 2023
We now prove the theorem.
Proof. Consider the following set of graphs, each on 4h nodes:
VO
U1
U4k
U1
U4k
U2
1/2
U2k
02k+1
U2k
12k+1
Figure 2: Both of the above graphs on 4k + vertices, labeled uo, 01 ....... Bak- The only difference a single edge, ie.. the graph on the left has an edge between U22 and U2 while the one on the right does not have this edge.
Let V = {vo, U,,..., J. The first graph EV) is a cycle, while the second graph G" (V, E²) is a path, obtained by removing single edge from the first graph (namely, the one between 2g and tx+1). Suppose the edge weights are all the above graphs.
V} be "local" node feature initialization. Note that for any GNN (i.e., update and aggregation rules equation 12 add the formal update rule somewhere), the computation tree after k rounds of message passing is identical for nodes Vo U1..... Uk. U3k+1, U34+2;.... Usk (i.e.. the nodes within the k-hop neighborhood of un) in both G' and G'. This is because the only difference between G and G' is the existence of the edge between 222 and 12k+1, and this edge is beyond a k-hop neighborhood centered at any one of the aforementioned nodes. Therefore, we will necessarily have that h!! i l...., 3k + 3k 2,...,,kk. 4k:
Let
be the source and let {hr (0)
(k) is identical in both G and G' for
However, it is easy to calculate the effective resistances in both graphs In G, have Reso vz) 1-k+ while in G², we have Reso (6o, v.) min 4h - i}. Therefore, Resor (vo, v.) + 4k+1
Rese (U,, v;) for all 1,2, k 3k + 1, 34 + 2, 4k.
It follows that for any 1,2, 3k 1, 3k: ... 4k, the execution of k message passing steps of a GNN cannot result in h((9) Res(vo, v.) for both G and G", which proves the first claim of the thcorem.
For the second part (regarding single-source shortest paths), observe that single-source shortest path distances can, indeed, be realized via aggregation and update rules for message passing network. In particular, for rounds of message passing, it is possible to learn shortest path distances of nodes within k-hop neighborhood. Specifically, for source h = O and h, do for all u + w. Moreover, for any edge (u, v), let the edge feature x E R simply be the weight of (u, u) in the graph. Then, take the update rule equation 12 with fex th+ as
the following setup: Take
18

---

Under review as a conference paper at ICLR 2023
identity functions and
fe(Nuv) = -xy
det1 (9) h()) fo (x(()))) = h + Xur
f(S) min(s (s E $}
01+1 (a, b) = min(a, b).
is clear that the above update rule simply simulates the execution of an iteration of the Bellman-Ford algorithm. Therefore, & message passing steps will simulate iterations of Bellman-Forte resulting
in correct shortest path distances from the source uo for every node within k-hop neighborhood. [
19


Reviews:
[{"review_id": "jUJYKkW_7T", "reviewer": "Reviewer_gd3D", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose using using hitting times, commute times and resistive embeddings as features in a GNN. They show that using using this makes the network more powerful than 1-WL. They also show that this can be approximated by sketching techniques in large graphs. Then they show that empirically these networks do better on four datasets.", "summary_of_the_review": "This paper presents a new bunch of features that can be used in GNN. It is well written. I recommend acceptance.", "strength_and_weaknesses": "The idea is neat, as is the counter example showing that the networks beat 1-WL. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gqEqFeItgA", "reviewer": "Reviewer_cQm4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new MPNN variant that leverages affinity-based features. Specifically, they consider random walk-based statistics such as hitting time between nodes in order to augment edge features in the graph. To make this approach scalable to large datasets, the paper proposes to employ random projections using Gaussian matrices for these affinity-based features to remain of manageable dimensionality. The paper claims that expressivity beyond WL-1 can be achieved, which is a nice property, however there are existing GNN variants that achieve this as well, so the novelty of this property for a new GNN variant is limited.\nIn the experiments, improvements over the vanilla MPNN can be seen, while the method seems to perform reasonable across several datasets, in particular showing new SOTA results on the OGBG-PCQM4Mv1 benchmark which I think is interesting. At the same time, the OGB benchmark page states that v1 is outdated, and that v2 should be used. So it would be interesting to see, if the proposed method also performs competitive on the current v2 (where probably most new methods are tested on), compared to the older v1 version.\n\n\n\n\n", "summary_of_the_review": "\nOverall, the paper makes an interesting point that random-walk based features can be used to augment GNNs to improve performance. Random walks have been around in Graph ML for decades, e.g. with random walk kernels, which suffered from excessive runtimes. Therefore, the fact that random-walked based features show beneficial results on a large-scale benchmark is indeed promising.\nHowever, there are several issues with the current submission, that I believe the authors need to address before publication is warranted:\n\n- Either show (e.g. with synthetic experiment on graphs that are hard to distinguish) that the proposed method performs better than previous methods that increase expressivity (e.g. topology-aware GNN variants) to then more strongly claim that this method (of increased expressivity) is superior to existing works. Else, tone down the expressivity content, as simply going beyond 1-WL on its own is not a major novel finding at this time, albeit a nice side-property to mention.\n\n- Several related pieces of literature are not mentioned nor compared to: in terms of expressiveness, TopoGNN (ICLR 2022), re random walks: random walk kernels, and random walk GNNs (Neurips 2020). It would be interesting to see how random walk GNNs perform as a baseline. Also, GIN would be a stronger baseline than simply GCN. \n\n", "strength_and_weaknesses": "Strengths:\n- Good contribution to scale random walk-based features to large-scale GNNs\n- Paper is clearly written.\n- Mixed-Ok experiments, but new SOTA on a large-scale benchmark (although it's an outdated version)\n\nWeaknesses:\n- Slightly out of touch with literature, amongst others e.g. Topological Graph Neural Networks have previously shown expressivity beyond 1-WL, plausibly could also solve the same example graph (Fig 1). This paper used a mini experiment on synthetic graphs to demonstrate that it can distinguish graphs that previous methods couldn't. This would be an easy way to credibly demonstrate the superiority of the proposed method against existing methods that improve expressivity. If this is not the case, then the claims about improving expressivty need to be toned down, e.g. it could be a nice property, but is it not a novel contribution to the GNN literature.\n- previous Random walk based methods are not discussed. At least refer to Random walk kernels, and ideally compare to previous GNN variant that leverage random walks, e.g. Random Walk Graph Neural Networks (Neurips 2020). \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fvPNTZ4PvA", "reviewer": "Reviewer_46iR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this work, the authors propose a strategy to include scalar and vector features reliant on random walks to message passing GNNs. The authors the show that these features can be computed/ approximated efficiently and provide results of augmenting MPNNs with their affinity metrics on multiple graph datasets.", "summary_of_the_review": "Currently the weaknesses slightly out weigh the strengths of the paper - but if the authors can address the weaknesses and questions listed above - I would be happy to increase my scores appropriately.", "strength_and_weaknesses": "**Strengths:**\n1. The paper is well written and easy to understand\n2. The idea to capture affinity without the use of anchor sets - and how to incorporate them into existing MPNNs is novel\n3. The authors provide principled techniques to efficiently compute the aforementioned affinity metrics\n\n**Weakness, corresponding questions and suggestions:**\n1. Looking at the results (for instance the PNA dataset) where the authors have multiple variant models - in the case of an unseen test - it is unclear how we pick the variant to use. That is, what should we looking at in the data to identify which variant to use?\n2. Lack of clarity in section 3.5 and how the performance is compared with what are referred to SPD based methods. Please explicitly elucidate them in the tables\n3. Add comparison with methods which include subgraph features as nodes features (e.g. Bouritsas, et al. 2020). Also in this case, provide an increase in performance by combining affinity metrics with such methods (i.e. increase in perf when adding affinity metrics to the above method compared to without it)\n4. Provide timing numbers associated with the efficient computation of affinity measures (Sec 4) for the different datasets.\n5. Given that most real world graphs are obtained from crawls on the web - and the data is extremely noisy - the use of random walk approaches can further enhance the effect of noise - it would be nice if the authors can provide an analysis (either qualitative/ quantitative) on the impact of noise in the graph (e.g. one way could be deliberately corrupt the adjacency structure of the graph and look at the impact on performance - all else remaining the same)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YWGAcgqRrI", "reviewer": "Reviewer_siZ1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In order to increase the expressive power of GNNs, a lot of strategies used in many research have been seen, e.g., augmenting node/edge features by position/structural information. This paper focuses on the affinity metrics to achieve this purpose. Specifically the paper considers the statistics that arise from random walks in graphs, by exploring hitting/commute time between pairs of vertices, so that such a feature can be incorporated in the standard graph message passing neural network. It has been found that the richer vector-valued resistive embedding is quite effective in discriminating nodes etc.  In fact the distances between these embedding can reveal the hitting time etc, or in other words, the embedding method provides an alternative way to calculate the hitting/commute time according to the theoretical proof presented in the paper.", "summary_of_the_review": "Overall, the paper does not provide sufficient novelty for ICLR. It can be regarded as re-interpretation of the early work from Lovasz (1993). ", "strength_and_weaknesses": "Strength:\n\n1. By defining the resistive embedding, the paper claims that the resistive embedding can be used to calculate the hitting time (Lemma 4.3)\n2. Thus instead of directly using hitting/commute time as node/edge features, the embedding has replace them in MPNN\n\nWeakness:\n\n1. The novelty is incremental. All the conclusion can trace back to Lovasz (1993), that is, the very important conclusion Res(u,v) = K_{uv}/2M and Res(u,v) = (1_u-1_v)L^*(1_u-1_v) where L^* is the pseudo-inverse of L.  As Res(u,v) = (1_u-1_v) L^{*/2}L^{*/2}(1_u-1_v), thus Definition 3.1 is straightforward. It is in fact r_v = L^{*/2}1_v or simply r_v = L^{-1/2}1_v.  Thus, all the conclusions in Section 4 are trivial.\n\n2. Although the paper uses an example in Figure 1 to show that a MPNN using Res(u,v) can distinguish nodes in this particular graph, this does not prove it will be more expressive than MPNN without using these features. The reason is, we cannot simply say in all cases MPNN using Res(u,v) are always better than MPNN without using Res(u,v).  Unless I have missed something, I believe that the general claim (Theorem 3.7) cannot hold.\n\n3. In the experiments, it is not clear how the new features are used in MPNN.  It is better to have detailed description. For example, (3)-7) in Section 5 do not clearly specify where the new features Res(u,v) and Embedding are used.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject