Affinity-Aware Graph Networks
Authors: Ameya Velingker
Ali Kemal Sinop
Ira Ktena
Petar Veličković
Sreenivas Gollapudi
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
message passing
effective resistance
hitting time
TL;DR: We propose the use of affinity measures (e.g., effective resistances, resistive embeddings, hitting times) as features in graph neural networks and show that they provide good empirical performance.

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. Our architecture has low computational complexity, while our features are invariant to the permutations of the underlying graph. The measures we compute allow the network to exploit the connectivity properties of the graph, thereby allowing us to outperform relevant benchmarks for a wide variety of tasks, often with significantly fewer message passing steps. On one of the largest publicly available graph regression datasets, OGB-LSC-PCQM4Mv1, we obtain the best known single-model validation MAE at the time of writing.

Affinit-Aware Graph Networks
Ameya Velingker'
Ali Kemal Sinop' Google Research asinop@google.com
Google Research ameyav@google..o com
Ira Ktena
Petar Veličkovié Google DeepMind
Sreenivas Gollapudi Google Research sgollapudgoogle.c com
Google Deep traktena@google.co com
petarvogoogle.c com
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. 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 these features and evaluate their performance 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, DGB-LSC-PCQMANO
we obtain the best known single-model validation MAE at the time of writing.
Introduction
Graph Neural Networks (GNNs) constitute a powerful tool for learning meaningful representations in
non-Bucliddan domains. GNN models have achieved significant successes wide variety of node
prediction [8] 31, link prediction [55] (52). and graph prediction (0] tasks. These tasks naturally
emerge a wide range of applications, including autonomous driving [8]. neuroimaging [36],
combinatorial optimization [14 [34, and recommender systems [5I]. while they have enabled
significant scientific advances the fields of biomedicine [45] structural biology (23, molecular
chemistry 42 and physics 3
Despite the predictive power of GNNs, it is known that the expressive power of standard GNNs is limited by the 1-Weisfeiler-Lehmaa (1-WL) test [47]. Intuitively, GNNs possess at most the same power in terms of distinguishing between non-isomorphie (sub-)graphs, while having the added benefit of adapting to the given data distribution. For some architectures, two nodes with different local structures have the same computational graph, thus thwarting distinguishability in a standard GNN. Even though some attempts have been made to address this limitation with higher-order GNNs 32), 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, distance- approaches form the basis for works such as
Eqqua contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Position-ad rosition-aware Graph Neural Networks [521. which capture positions/locations of nodes with respect set of anchor nodes, as well as Distance Encoding Networks [29], which use the first few powers of the normalized adjacency matrix as 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 seneral-purpos. node and edge features without the need for specifying any anchor or target nodes.
We propose the use of affinity metrics as features a GNN. Specifically, we consider statisties that arise from random walks in graphs, such hitting time and commute time between pairs of vertices (see Sections 3.1 and 3.2). We present a means of incorporating these statistics as scalar edge features in message passing neural network (MPNN) [15] (see Section 3.4). In addition to these scalar features, we present richer vector-valued resistive embeddings (see Section (.3)) which can be incorporated as node edge feature vectors in the network. Resistive embeddings are natural way of embedding each node into Fuclidean space such that the squared 1,2 dii-distance between nodes recovers the commute time. We show that such embeddings can be incorporated into MPNNs, even for larger graphs, by efficiently approximating them using sketching and dimensionality reduction techniques and prove novel additive approximation for hitting time (see Section
Contributions:
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 [9], which includes 6 node and graph algorithmic tasks, showing the ability of affinity measures to exploit structural properties of graphs. We also evaluate the performance on a number of graph and node tasks for datasets in the Open Graph Benchmark (OGB) collection (21, including molecular and citation graphs. In particular, our networks with scalar effective resistance edge features achieve the state of the art on the OGB-LSC PCQM4My1 I dataset, which was featured in KDD Cup 2021 competition for large scale graph representation learning.
Finally, we provide intuition for why affinity-based measures are fundamentally different from aforementioned distance-based approaches (see Section 3.5) and bolster it with detailed theoretical and empirical results (see Appendix D) showing favorable results for affinity-basee measures.
2 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 or spatial, we abstain from this division as recent research has demonstrated some equivalence of the graph convolution process regardless of the choice of convolution kernels 22 7 Speotrally-motivatee methods are often theoretically founded on the eigendecomposition the graph Laplacian matrix (or an approximation thereof) and, hence, corresponding convolutions capture different frequencies of the graph signal. Early works in this space include ChebNet [10] and its more efficient l-hop version by Kipf et al. [24]. which offers a linear function on the graph Laplacian spectrum. Levie et al. (28) proposed CayleyNets, an alternative rational filter.
Message passing neural networks (MPNNs) [5] perform transformation of node and edge repre- sentations before and after an arbitrary aggregator (e.g. sum). Graph attention networks (GATs) 44 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. A. i.e. directional graph networks (DGN). DGN uses the gradients of the low- low-frequency cigenvectors 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 (32) used higher-order (k- (A-dimensional) GNNs, based on k-WL, and hierarchical variant and proved theoretically and experimentally the improved expressivity in comparison to other models.
Other notable works include Graph Isomorphism Networks (GINs) 47 which represent a simple, mokimally--poertiie GNN over iiscrete-featured inputs. Hamilton et al. [[]] proposed a method to construct node representations by sampling fixed-size neighborhood of each node and then perform- ing aggregation over it, which led to impressive performance on large-scale inductive benchmarks. Bouritsas et al. [6] use topologically-avee aware message passing to detect and count graph substructures.

---

while Bodnar et al. [5] propose paassage-pssiing procedure on cell complexes motivated by a novel color refinement algorithm that proves be powerful for molecular benchmarks. Meanwhile, Homn et al. 19 propose layer based on persistent homology to incorporate global topological information.
Expressivity. Techniques that improve a GNN's expressive power largely fall under three broad directions. While we focus on the feature- based direction in this paper, we also acknowledge that it in no way compels the GNN use the additional provided features. Hence, we brielly 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 44 and LSPE (12). DGNs leverage the graph's 's Laplacian cigenvectors, but they do not merely use them input features; instead, they define a directional vector field based on the eigenvectors, and use explicitly to anisotropically aggregate neighbourhoods. LSPE features "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 (32), which explicitly performs message passing over k-tuples of nodes at once. Recently, scalable efforts in this direction focus on carefully chosen substructures, e.g., junction trees [3], cellular complexes (5].
3 Affinity Measures and GNNs
3.1 Random Walks, Hitting and Commute Times
Let G = (V, E) be graph of vertices V and edges E C V x V between them. We define several natural properties of graph that arise from random walk. random walk on G starting from a node ti is a Markov chain on the vertex set V such that the initial vertex is u, and at 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 T. degree of node u. and M the sum of edge weights.
de where dy is the weighted 2M
The hitting time Huv from u to u is defined as the expected number of steps for a random walk starting at u to hit v. We can also define the commute time between u and as Ka Has + H Heus the expected round-trip time for a random walk starting at u to reach 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 was replaced with circuit where each edge becomes a resistor with resistance equal to the reciprocal of its weight. We will use Res(u, (u, v) to denote the effective resistance between nodes u and v. For undirected graphs, it is known that 330 the effective resistance proportional to the commute time, Res(u, v) 2M Kuv-
Our broad goal is to incorporate effective resistances and hitting times as edge features in an MPNN. In Section 3.4 we will show they can provably improve MPNNs' expressivity.
3.3 Resistive Embeddings
Efffective 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 specifyy the resistive embedding, we define a few terms. Let L = D - A be the graph Laplacian of G. where D E gnxa the diagonal matrix containing the weighted degree of each node and A E RR is the adjacency matrix, whose ( entry is equal to the edge weight between i and j. if it exists; and 0 otherwise. Let be the m X n edge-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 ut column and a -1 in the vitth column, while all other entries are zero. Finally we will use C' E mx to denote the conductance matrix, which is diagonal matrix with C; being the weight of 7th edge. It is easy to verify that CB = L.. Even though I, is not invertible, its null-space consists of the indicator vectors for every connected component of G. For example, if G is
3

---

connected. then L's nullspace is spanned by the all-1's vector Hence, for any vector x orthogonal all-1's, L- L z, where L is the pseudo-inverse.
We can express effective resistance between any pair of nodes using Laplacian matrices 30 as Res(u, 2) = (I, 1, I. (1.. 1,), where 1, is an n-dimensional vector specifying the indicator for node v. We are now ready to define the resistive embedding.
Definition 3.1. (Effective Resistance Embedding) r, = C1/2
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, v, 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, U is an orthonormal matrix, then Ur also a valid resistive embedding. This poses challenge if we want to use the resistive embeddings as node or edge features: we want a way to enforce that a (G)NN using them will do so a 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. While data augmentation is a popular approach for promoting invariant and equivariant predictions, is only hinting to the network that such predictions are favourable. also possible, in the spirit of the geometric deep learning blueprint [7]. to combine ER embeddings with O (nn)- equivariant GNN, which rigorously enforces rotational equivariance. popular approach to building equivariant GNNs has been proposed by (39, though it focuses on the full Euclidean group E(n) rather than (n)) We leave this exploration to future work.
Definition 3.3. Let p = E. Tu be the mean of effective resistance embedding.
of We might view p "weighted mean of r. We will define the hitting time radius, Maxx of given graph as the maximum hitting time between any two nodes: Definition 3.4 (Hitting Time Radius). Hmax == max,, Hu,
We will need the following to bound the hitting times we computed:
Lemma 3.5. For any node u, [|r, p11 <
Hans.
Ad
The proof follows easily from the fact that p is convex combination of r's and Jensen's 's inequality.
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 measures into GNN computations.
In the simplest instance, 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 't (casily) be able to. These features are then appended to the GNN's inputs for further processing. For example. it has been shown that endowing nodes with one-hot based identity already sufficient for improving expressive power 33 this was then relaxed any madomly-sampled scalar feature by 38 It is, of course, possible to create dedicated features that even count substructures of interest [6) Further, the adjacency information can be factorised [7 or eigendecomposed [12) to provide useful structural embeddings for the GNN.
We will focus our attention on exactly this class of methods, demonstrating improvements from these computations. Hence, our baselines will all be instances of the MPNN framework (15), which we will attempt to improve by endowing them with affinity-based features. We start by theoretically proving that these features indeed improve expressive power:
is a lightweight and direct way of
Theorem 3.6. 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.
Throouhhuu this section, we will assume that our graph is connected. However everything applies to disconnected graphs, too.
Note that the average of all r. 's will be O. If the graph regular, then p will also be 0.

---

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 to 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 a standard GNN (limited by the 1-WL 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 is limited by the I-WL test cannot distinguish any pair of nodes a 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 V; and node in Vj, for i * j. We note that the hitting time from to b depends only on the isomorphism classes of and b. Thus, we write ri as the effective resistance between node in V, and node in Vg, Note that rigj Tj and it is easy to verify that:
T,,1 2/, = 15/28, r3,3 = 4/7
F1.2 = 2211 = 185/336
F2,3 = r3,2 209/336.
Hence, it follows that in a message passing step of an MPNN that uses effective resistances, vertices in Vi, V2, and V/3 will aggregate feature multisets (ri,i- {r2,1, 22,2, 32,, respectively, all of which are all distinct multisets. Hence, such MPNN can distinguish nodes in + V; and Vg, i j for suitable aggregation function.
{2/3, 185/336, 185/336), {185/336 15/28, 209/336), and {r2.3, F2,3, 33.3 {209/338 /336, 209/336, 4/7].
If, instead of effective resistance, hold. This is because, as we showed previously, the effective resistance between nodes is a function of the two hitting times in either direction, 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 an 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.
hitting time features resistive embeddings, our results still
3.5 Effective Resistance vs. Shortest Path Distance
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 (e.g., 44 52 29 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).
Degree 3 graph on 8 nodes, with isomorphism classes indicated by colors. While nodes of the same color are structurally identical, nodes of different col- ors are not. A standard GNN lim- ited by the 1-WL cannot distin- guish between nodes of different colors. However, affinity based networks that use effective resis- tances, hitting times, or resistive embeddings can distinguish every pair of such nodes.
Figure 1:
An alternative edge features would be to use (a) SPDs to a small set of anchor nodes features in an MPNN (e.g., P-GNN (52) or (b) a dense featurization incorporating shortest paths between all pairs of nodes (e.g., the dense attention mechanism in Graphormer (49).. ). We remark that the latter approach typically incurs an O(n²) overhead, which our MPNN-based approach avoids.
We empirically compare our models to MPNNs that use ap- proaches (a) and (b). Results on the PNA dataset show that our effective resistance- based GNNs outperform these approaches. Furthermore, we complement the empirical results with a theoret- ical result (see Appendix D) showing that under limited number of pressag-passsng steps, effective resistance features can allow one to distinguish structures that cannot be done using shortest path features. This provides some insight into why effective resistances can capture structure in GNNs
5

---

that SPDs are unable to. We describe the result below. We point the reader to Appendix for a proof of Theorem D.I
4 Efficient Computation of Affinity Measures
In order to use our features, important that they be computable efficiently. this section, we show how to compute approximate the various random walk- based affinity measures. We share the results of our method on large-scale graphs in Section 5.4
4.1 Reducing Dimensionality Resistive Embeddings
Given their higher dimensionalityy we might find it beneficial to use
Table I: (og(MSE) on the PNA test dataset.
resistive embeddings as GNN fea-
tures instead of the effective resis-
Model
SSSP
Nudu
Graph
tance. Now, the difficulty with us-
GAT
-1.730
-2.313
-1.935
-2.644
-0.615
-1.430
-1.535
ing resistive embeddings directly as GNN features is the fact that the embeddings have dimension m, which can quite large, e-g- up to n² for dense graphs. It was shown by [41] that one can reduce the dimensionality of the embed- ding while approximately preserving Euclidean distances. The idea is to use a random projection Lemma:
GUN MPNN MENN (uad feat.)
-2665
1.592
-2.235
-2.281
-2.419
-1.578
-1,698
-3.116
-1.387
02618
-2.681
-3.433
-3.652
-1.541
-2440
-2.135
-1.808
-3,873
-1.696
-2.614
-2.813
DGN (frnness)
-2.94
-2.105
-4.184
-1.858
-3.98
DGN (festurea)
-2.18
-2.100
-1.689
-1.344
-2658
-2.255
-3533
-3.14
KRR (rdgri smbre..
-2759
-2.765
-2.125
-4.25
-1.907
-3677
Hatting Times
-2816
28.18
11.004
-4.97
1.388
-1. 797
-3.730
All ER frarures
-3.006
-2.789
-3182
-1.077
-1.358
-3.895
-3962
constructive version of the Johnson-Lindenstrnn
Lemma 4.1 (Constructive Johnson- Lindenstrauss)), Let I1. .g...., In Id be set of n points; and let a1 ........ amm E R. be fixed linear combinations, Suppose II is a l x d matrix whose entries are chosen i.i.d. from a Gaussian N 1) and consider vk Ilx,,
Then, it follows that for k 2 Cllo(mmn)/e,, with probability 1- o(1), we have (1 c)ll E, ول.zر for every 1 I
Using triangle inequality, we can see that the inner products between fixed linear combinations are preserved up to additive error:
Corollary 4.2. For any fixed vectors a, B E IR,, if we let X = E, EnT X = E, a, and similarly Y = E, 3,0r, y = B,a,, then:
(x. - (8, S (1X|++ +V[1))
Therefore, we can choose desired and k = Ollog(n)/e)) and instead use F V R* as the embedding, where
F
LIBL e. Vk
(I)
for a randomly chosen & x d matrix II whose entries are i.i.d. Gaussians from (O 1). Then, by lemma 3.2 and lemma 4.1 have that for every edge (u, v) e E,
[F F. (1 + Res(u,
with probability at least 1
So the computation of random embeddings, F, requires solving O(1 + m) logn/e //22) many Lapla- cian linear systems. By using of the nearly linear time Laplacian solvers [26], can pute the random embeddings in the near-linear time. Hence the total running time becomes O (nn + m) log upoly log log m/e2).

---

4.2 Fast Computation of Hitting Times
Note that it not clear whether there is fast method for computing hitting times similar to commute times / effective resistances. The naive approach involves solving linear system for each edge, resulting in a running time of at least ((mm). which is prohibitive. One of our technical contributions in this paper is novel method for fast computation of hitting times. In particular, will show how to use the approximate effective resistance embeddings, F, to obtain an estimate for hitting times with additive error. Proofs can be found in Appendix
Let p :p E. a.Fa. Just like being an approximation of r, P an approximation of p. Consider the following quantity:
Hu = 2M. - Fu. F, -p. P):
We will use this quantity as an approximation of Ha,v- In the following part, we will bound the difference between H and Hu,y- Our starting point will be expressing Hu, in terms of the effective resistance embeddings.
Lemma 4.3. Hu,v = 2M Fu, Fo - pp) where p == En Tu.u-
Given Lemma 4.3 we can establish the desired additive approximation property of Hu,e-
Lemma 4.4. H Hu,el S 3eH
Experiments
As previously discussed, our empirical evaluation seeks show benefits from endowing standard expressive GNNs with additional affinity-basse -baee features. All architectures we experiment with will
therefore conform to the MPNN blueprint [15), which we describe Appendix B When relevant, we may also note results that a particular strong baseline (e.g., DGN 4 Graphormer [48] achieves on a dataset of interest. Note that these baselines modulate the message passing procedure rather than appending features and are hence different category to our method-their performance is provided for indicative reasons only. Where appropriate, we use "DGN (features)" to refer to an MPNN that
uses eigenvector flows additional edge features, without modulating the mechanism. We also use "ER (GNN)" to refer to the use scalar effective resistance features.
5.1 PNA dataset
The first dataset we explore is the PNA dataset (9. which captures a multimodal setting. This consists of collection of node tasks, i.e. (1) Single-source shortest paths, (2) Eccentricity and (3) Laplacian features, as well as graph tasks, i.e. (4) Connectivity, (5) Diameter and (6) Spectral radius. PNA dataset is set of structured graph tasks, and it complements our other datasets. As can see in Table I even adding a 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 we combine all ER features, which include effective resistances, hitting times as well node and edge embeddings, get the best scores. On these structured tasks, we can see that the affinity based measures provide a significant advantage.
We also note that incorporating affinity measures additional features to the "DGN (features)" MPNN model also provides improvement over the standard "DGN (features)" baseline. We have accordingly included the results of model that uses (both node and edge) ER embeddings and hitting time features along with DGN features.
5.2 Small molecule classification: ogbg-molhiv
The ogbg-molhiv molhiv dataset molecular property prediction dataset comprised of molecular graphs without spatial information (such as atom coordinates). Each graph corresponds to molecule, with nodes representing atoms and edges representing chemical bonds. Each node has an associated 9-dimensional feature, containing atomic number and chirality, as well other additional atom features such as formal charge and whether the atom is in the ring or not. The goal to predict whether molecule inhibits HIV virus replication not. Our results given in Table 2
7

---

On this dataset, effective resistances provide an improvement over the standard MPNN. We achieve the best performance using ER node embeddings and hitting times with random rotations. With these features, our network achieves 79.13% + 0.358 test accuracy, which is close to DGN.
Note that provide GSN (6), HIMP [3] and GR-
WNN (35] as baselines. HIMP and GSN exploit struc- tural/toplogical properties; the former is specifically de- signed for learning on molecular graphs, while the latter incorporates graph substructures. In addition to the com- parison to GSN as baseline, we additionally train an MPNN with substructure counts as additional features, namely counts of k-cycles (k = 3, 4) and k-paths (k- = 3) as motifs (in the same vein as the approach of ( ob- taining a test ROC-AUC of 76.41 % + 0.42 (note that this improves on the base MPNN test ROC-AUC of 74.67% + 0.19). Furthermore, if we also add affinity measures (in addition to the aforementioned substructure counts), we obtain a test ROC-AUC of 78.50% + 0.51. This suggests that affinity measures provide a performance or expressiv- ity lift beyond that of substructure counts.
Table 2: Test % AUC-ROC on the Mol- HIV dataset. Our results are averaged over five seeds.
MolHIV
Test ROC-AUC
GCN
76.06 : 0.97
GIN
75.58 = 1.40
MPNN
74.67 + 0.19
DGN
79.70 + 0.97
GSN (GIN + VN)
77.99 + 1.00
HIMP
78.80 + 0.82
GRWNN
78.38 0.99
ER GNN
77.75 = 0.426
ER (node) embed. HT
79.13 + 0.358
(with random rotations)
5.3 Multi-task molecular classification: ogbg-molpeba
The ogbg-molpcba dataset comprises molecular graphs without spatial information (such atom coordinates). The aim is to classify them across 128 different biological activities. We follow the baseline MPNN architecture from [17. including the use of Noisy Nodes.
Mirroring the evaluation protocol of [17.. 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 utilising affinity- -ased features are capable of reaching as well as exceeding peak test performance (in terms of mean average precision). However, what'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 HT features. This result illustrates the potential benefit affinity- based computations can have on molecular benchmarks, especially when no spatial geometry is provided as input.
Table 3: ogbg-molpeba performance for various model depths. Best performance across all models is underlined. NN refers to Noisy Nodes.
Table 4:
ogbg-molpcha perfor- mance compared to other baselines.
Test Mean Average Precision layers
Model
Test Mean AP
Model
layers
16 leyers
GCN (w/ virtual node)
24.24 0.34
MPNN [+]
27.75% = 0.20
27.91% + 0,22
27.64% = 0.25
GIN (w/ virtual node)
27.03 = 0.23
MPNN NN
27.92% 0.11
28.07% 1 0.14
28.29% 0.13
DeeperGCN HIMP
27.81 0.38
MPNN + NN ER (ours)
28.11% = 0.19
28.27%
+ 0.17
28.28% = 0.14
27.39 0.17
MPNN NN HT (ours)
28.03% = 0.15
28.32% + 0.13
28.20% 0.19
MPNN NN HT (ours)
28.32% 0.13
5.4 Scaling to larger graphs
Next, we present results on ogbn-arxiv and ogbn-mag, transductive datasets with large graphs.
5.4.1 Large citation network: 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 size- makemn them inapplicable even for modest-sized 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 of 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 27 25), we constructed the effective resistances this graph in hour on standard MacBook Pro 2019 laptop.
8

---

As MPNN models overfit this transductive dataset quite easily, the dominant approach to tackling it are graph attention networks (GATs) 4 Accordingly, we trained a simple four-layer GAT on this dataset, achieving 72.02% 0.05 test accuracy. This compares with 71.97% + 0.24 reported for a related attentional baseline on the leaderboard [54] indicating that our baseline performance relevant.
ER embeddings on ogbn-arxiv need to be exceptionally high-dimensional achieve accurate ER estimates (~11,,0 1,000 dimensions), hence we were unable to use them here. However, incorporating improvement of 72. 14.% +
ER scalar features into our GAT model yielded a statisticall-siinnffe 0.03 test accuracy. Hirring time features improve this result further to 72.25% = 0.04 test accuracy. This demonstrates that our affinity-basee -bseed metries can yield useful improvements even on larger scale graphs, which are traditionally out of reach for methods like DGN 4 due to computational complexity limitations.
Reliable global leaderboarding with respect to ogbn-arxiv is difficult, as state-of-the art approaches rely either on privileged information (such as raw text of the paper abstracts), incorporating node labels as features [46). post-processing the predictions (22), or various related tricks [46]. With that in mind, report for convenience that the current state-of-the-art performance for ogbn-arxiv without using raw text is 76. 1 % + 0.09 test accuracy, achieved by GIANT-XRT-DRGAT.
5.4.2 Heterogeneous citation network: ogbn-mag
We additionally present experiments on an even larger-scale network, ogbn-mag, a heterogeneous network derived from the Microsoft Academic Graph whose nodes consist of four types of entities (papers, authors, institutions, fields of study) and whose edges capture directed relations (e.g., a paper cites another paper, an author is affiliated with an institution, etc.). The task is to predict the venues of papers. The ogbn mag dataset consists of I 111,059,95 nodes and 1,615,685,872 edges.
As in the case of ogbn-arxiv, ER embeddings require an exceptionally high number of dimensions, given the large size of the network. Hence, we incorporated ER scalar features. As baseline, we used a GraphSAINT (33) model that uses R-GCN aggregation [40], which reported a test accuracy of 47.51 = 0.22 in a relevant leaderboard entry. After incorporating ER scalar features into the same model, we obtained
improvement of 47.99% + 0.23 in test accuracy.
5.5 Large scale graph regression: OGB-LSC PCQM4Mv1
We finally include experimental results for one of the largest-scale publicly available graph regression tasks: the PCQM4Mv1 dataset from the OGB Large Scale Challenge [20]. PCQM4M is quantum chemistry dataset spanning million small molecules, with task to predict the HOMO-LUMO gap, an important quantun-chemical property. It is anticipated that structural features such as ER could be of great help on this task, as the vI version of it provided without any structural information, and the molecule's geometry is assumed critical for predicting the gap. We report the single-model validation performance on this dataset, in line with previous works [7 48 I.
PCQM4Mv1 comprises molecular graphs which consist of bonds and atom types, and no 3D or 2D coordinates. We reuse the experimental setup and architecture from [17), with only one difference: appending the effective resis- tance to the edge features. Additionally, we compare against an equivalent model which uses molecular conformations estimated by RDKit as additional feature. This gives bascline which leverages an explicit estimate of the molecular geometry.
Table 5: mingle-model OGB-LSC PCQM4Mv1 results.
Model
#Layers
Noley Nodes
Validation MAE
MPNI MPNN
16
Yes
0.1249 1 0.0003 0.1236 0.0001
Gruphoemer MPNN
0.1234
50
Yes
0.1218 + 0. 0.0011
MPNN + Confommers
32
Yes
0.1212
+ 0.0001
MPNN ER (ouns)
32
Yes
0.1197 1. 0.0002
Our results are summarised in Table 5] We once again see powerful synergy of effective resistance- endowed GNNs and Noisy Nodes 17]. allowing us significantly reduce the number of layers (to 32) and outperform the 50-layer MPNN result in (I7]. Further, we improve on the single- model performance of both the Graphormer ensembling), and an equivalent model to ours which uses molecular conformers from RDKit. This illustrates how ER features can be competitive in geoeetry tasks even against features that inherently encode an estimate of the molecule's spatial geometry.
48 (which won the original PCQM4M contest after

---

Lastly, we remark that, to the best of our knowledge, our result is the best published single-model result on the large-scale PCQM4M-vl benchmark date, and the only single model result with validation MAE under 0.120. We hope this will inspire future investigation on affinity-rlatted GNNs for molecular tasks, especially in settings where spatial geometry is not reliably available.
6 Conclusions
In this paper, we proposed a 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 toolbox. Our proposal carefully balances theoretical expressive power, empirical performance, and scalability to large graphs. While adding affinity measures as node/edge features provides the most direct route to incorporating them in graph network, an interesting future direction would be to explore variants of GNN message functions that explicitly make use of affinity-bsse based computations.
Acknowledgments and Disclosure of Funding
We would like to specially thank Jonathan Godwin for his extensive support in setting up the codebase for large-scale GNNs, and Gabriele Corso for his support in setting up the PNA dataset. Additionally, we would like to thank Beatrice Bevilacqua, Wilfried Bounsi, Larisa Markeeva and Pete Battaglia for reviewing the paper prior to submission.
This research was funded by Google Research and Google DeepMind.
References
[1] Ravichandra Addanki, Peter W Battaglia, David Budden, Andreca Deac, Jonathan Godwin, Thomas Keck, Wai Lok Sibon Li, Alvaro Sanchez-Gonzaler Jacklynn Stott, Shantanu Thakoor, al. Large-scale graph representation learning with very deep gnns and self-supervision. arXiv preprint arXiv:2 2021.
[2] 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 on Learning Representations, 2021.
[3] Victor Bapst, Thomas Keck, A Grabska- BaabbkkaBarwiikka, 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- 454, 2020.
[4] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning (ICML), pages 748-758. PMLR, 2021.
[5] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34, 2021.
[6] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint 20Xi::2006.0255.. 2020.
[7] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković, Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2 204. 13478, 2021.
[8] Siheng Chen, Sufeng Niu, Tian Lan, and Baoan Liu. Pet: Large-scale 3d point cloud represen- tations via graph inception networks with applications to autonomous driving. In 2019 IEEE international conference image processing (ICIP), pages 4395-4399, IEEE, 2019.
10

---

[9] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 33, 2020.
[10] 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.
[11] 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-2233 2015.
[12] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint w 2021.
[13] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical mnter-message passing for learning molecular graphs. arXiv preprint ar arXiv:2006. 100:2006.1119,, 2020.
[14] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Ex- act combinatorial optimization with graph convolutional neural networks. arXiv preprins arXiv:1906.01629 2019.
[15] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), pages 1263-1272 1272. PMLR, 2017.
[16] Jonathan Godwin, Thomas Keck, Peter Battaglia, Victor Bapst, Thomas Kipf, Yujia Li, Kimberly Stachenfeld, Petar Veličković, and Alvaro Sanchez-Gonzalez. Jraph: A library for graph neural networks in jax., 2020.
[17] Jonathan Godwin, Michael Schaarschmidt, Alexander L Gaunt, Alvaro Sanchez-Gonzalee 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 on Learning Representationss, 2022.
[18] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31 International Conference Neural Information Processing Systems, pages 1025-1035, 2017.
[19] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten M. Borgwardt. Topological graph neural networks. In The Tenth International Conference on Learning Representations ICLR 2022, Virtual Event, April 25-29, 2022. Open 2022.
[20] 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 2rXiv:2133.094 2021.
[21] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00667 2020.
[22] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010. 13993, 2020.
[23] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakoo, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-88) 2021.
[24] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
11

---

[25] Ioannis Koutis and Gary L. Miller. CMG: Combinatorial Multigrid.
com/
ikoutis/cme crneiiissmmssolveer solver
[26]
Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD
linear systems. SIAM J. Comput., 43(1):337 (33433337335, 2014.
[27] loannis Koutis, Gary L. Miller, and David Tolliver. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Computer Vision and Image Understanding, 1 (15(12):1688-1644) 2011. Special issue on Optimization for Vision, Graphies and Medical Imaging: Theory and Applications.
[28] Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1))97-109, 2018.
[29] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Ad- vances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurLPS 2020, December 6-12. 2020, virtual, 2020.
[30] László Lovász. Random walks on graphs: A survey. Combinatorics, 2:1-46, 1993.
[31] Sitao Luan, Mingde Zhao, Kiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. Advances Neural Information Processing 32:10945-109955 2019.
3
[32] Christopher Morris, Martin Ritzert, Matthias Fey, William 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, pages 4602 4609, 2019.
[33] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663 4673. PMLR, 2019.
[34] 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.13339, 2020.
[35] Giannis Nikolentzos and Michalis Vazirgiannis. Geometric random walk graph neural networks via implicit layers. 2022.
[36] Sarah Parisot, Sofia Ira Ktena, Enzo Ferrante, Matthew Lee, Ricardo Guerrero, Ben Glocker, and Daniel Rueckert. Disease prediction using graph convolutional networks: application to autism spectrum disorder and alzheimer's 's disease. Medical image analysis, 48: 18:117,, 2018.
[37] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459-467, 2018.
[38] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[39] Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling, E(n) equivariant graph neural networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, ICMI. 2021, 18 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9323 93322922.22 PMLR, 2021.
[40] Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli, -atier Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna
12

---

Tordai, and Mehwish Alam, editors, The Semantic Web 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7. 2018, Proceedings, volume 10843 of Lecture Notes in Computer Science, pages 593-607. Springer, 2018.
[41] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913 1926, 2011.
[42] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-702 2020.
[43] Prasad Tetali. Random walks and effective resistance of networks. J. Theoretical Probability, 1:101-109, 1991.
[44] 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.
[45] Juexin Wang, Anjun Ma, Yuzhou Chang, Jianting Gong, Yuexu Jiang, Ren Qi, Cankun Wang, Hongjun Fu, Qin Ma, and Dong Xu. segnn is novel graph neural network framework for single-cell ma-seq analyses. Nature communications, 12(1):1-11, 2021.
[46] 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 103.::5003 2021.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[48] 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/2 106.05444,, 2021.
[49] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 28877-28888, 2021.
[50] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovee. GNNexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
[51] 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, pages 9744983,222 2018.
[52] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Interna- tional Conference on Machine Learning, pages 7134-7143. PMLR, 2019.
[53] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Confer- ence on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[54] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint 1rX1v:1803.07224. 2018.
[55] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5177 2018
13

---

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 3 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 T
Table 6: Training hyperparameters for PNA dataset
Model
#llidden size
L. rate
#MP steps
#Rotation matrices
#Same Examples
GAT
10-4
GCN
10-4
DGN
256
10-3
MPNN ER GNN ER (node) embed.
256
10-3
2
128
10-3
2
64
10-3
1
ER (edge) embed.
256
10-3
2
(edge) emhed,
10-3
All ER features
256
10
2
23
HT ER (rand rot)
512
10-4
2
23
B Details of MPNN Framework
As discussed previously, the architectures used in the experiments conform to the MPNN framework, which allows affinity measures to be added as additional node and edge features. We describe the details here for completeness.
Assume that our input graph, G = EV,E), has node features X. E R", edge features Xav R and graph-level features Xg E R!, for nodes v E V and edges (u, v) E &. We provide encoders + I and fg R¹ + I² that transform these inputs into a latent space:
fn : 12" + I fe 1.mh
h (0) (x,)
h (X
h (x()
Our MPNN then performs several message passing steps:
H (++1)
(H
(( h
where (( =
has
hg
contains all of the latents at a particular process-
NEv"
(a.V)
ing step / 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- Je and Ig:
Ya = 9n (h (T)
You = (h
Yę = 9y (h
(5)
Generally, ff and g are simple MLPs, 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) =1b1 (h() h ho)
((+1)
Φ.+1
h
Σ
((+1)) ou
(++1)
(6)
WEN,
The message function 1 and the update function Φe+1 are both MLPs. All of our models have been implemented using the jraph library (16).
We incorporate edge-based affinity features (e.g., effective resistances and hitting times) in fa and bode- affinity features (e.g., resistive embeddings) in fn. Note that node-based affinity
14

---

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 (see 66 In these cases, resort assuming that d factorises into attention mechanism:
m (++1) dc++1 (n h h
dht1 (h()
where the attention function is scalar-valued. We will refer to this particular MPNN baseline graph attention network (GA7) [44].
C Omitted Proofs
Lemma 3.2. For any pair of nodes u, U, we have |r rull Res(u, v).
Proof.
Fru -rel2 = =| BLG (1u - 1.)1l
(1n 1,) CB) 1.)
(1n 1.) (
= =(1 - (1,) Lt - 11,) Res(u, v).
Corollary 4.2. For any fixed vectors a, B E IR, if we let = Ei Ortts, 8 = E, og and
similarly Y := E, Bi Y = Brb; then:
(x-Y) (8, 82 [|X|++1|X18)) (
Proof. Since (X, - (IIX + 2112 - -|X - Y1) we can bound A = (XX,)) - (8, f) from above as:
= (IX Y12 - 1 + 812 X 211 + 1 - -11p)
4
< ( + - + +r + || 81p | Y112))
$ (c-11X Y| +e |
(8)
(IIX + 2 -
(1X112 + ||
where 8 follows from Lemma 4.1 with probability 1 o(1), ) by our choice of k (as Lemma 4.1
guarantees that each of || + 1 (1 + e)|l + 2 and | - l| (1 e) - Y holds with probability (1), and one can take union bound over the events).
Lemma 4.3. Hu,,- 2M (r. Tus
p) where p = Σ. Tu.
Proof. Consider the following expression of hitting times in terms of commute times by 43
H
1
Ka + Σ T (Ku,i Kn.i)
(9)
Dividing both sides of eq.
9 and using the relation Kn = 2M Res u, v), we see that:
H H.,
Res(u, v) + Σ Ts (Res(u,)) i) - Res(u, i))
2M
2
||r, rell + Σ (1|r,- - r1112 Ir. r=llz)
(10)
2
15

---

Let's focus on the inner summation. After expanding out the squared norms, we see that:
Σ Rs (I|r
ry|1² ||r - r ( = Σ Ts
(1|re|l' ||rul())
2 Σ To (rV Iu: r:))
= (1|x0/1 ||rul] 2)
2/r ras Σ TrKi)
= -11x=112 |||u|l 2(r rus p).
Substituting this back into eq.
10 we can express
1 2M
Ha,v as:
2 (1r rull2+ ||r=112 1 ||u
2(r
Tu: P\)
||ro11 1
(ru,
(ro Fu. P) (r. ru, P)-
Lemma 4.4. [Ha, Hupel S 3eH
Proof. Using Lemma
4.3
we see that
Hu Hu,el = 2M (TT. -T,, Fu - -p) (r. Fu: To p)
S eM (I|r, rall 3 ||,, pll²)
< HeHmax:
where we used Corollary 4.2 in the first inequality and Definition 3.4 in the last inequality.
L
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 to ask how effective resistance features compare to SPD features in GNNs, especially as there have been number of recent model architectures that make use of SPD features (c.g., Graphormer [49]. Position-Are Aware GNNs (52). DE-GNN (29). 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 as features in our MPNNs. However, since our networks only use ER features along edges of the given graph, the corresponding SPD features would then be trivial (as the SPD between two nodes directly connected by an edge in the graph is 1, resulting in a constant feature on every edge)!
As result, graph learning architectures that use SPDs typically either (a.) use a densely-connected network (e.g.. Graphormer [49], which uses a densely-connectee O(n²) overhead, or (b.) pick a small set of anchor nodes or landmark nodes to which SPDs from all other nodes are computed and incorporated as node features (c.g.. Position-Aware GNNs (52). DE-GNN (29). 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.
attention mechanism) that incurs
Furthermore, we note that DE-GNNs are arguably one of the closest proposals to ours, they compute distance-encoded 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, [29] only use powers of A up to 3, which would not be able to reliably approximate affinity-basee based features. We also
16

---

observe that the DE-GNN paper is concerned with learning representations of small sets of nodes (e.g,, node-, link-, and triangle- prediccorri and does not show how to handle graph prediction tasks, which the authors mention as possible future work. This makes direct comparison of our methods with DE-GNNs difficult.
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-based features. More precisely, is densely-connected MPNN with SPDs from the original graph edge features. In order to retain the structure of the original graph, we also use additional edge features to indicate whether or not an edge in the dense (complete) graph is true edge of the original graph. We also explore the use of the centrality encoding (in-degree and out-degree embeddings) from Graphormer as additional node features.
The second baseline is the Position-Aware 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.
Table Results on the PNA dataset for MPNNs with Graphormer-based features (yellow) well as baseb P-GNNs (orange). Here, CE refers to the centrality encoding, which is incorporated in the relevant MPNNs 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 in the input graph. Therefore, the MPNN baselines are all variants of the same model with additional node/edge features. Similarly, P-GNN 52 uses SPD features with respect to set of chosen anchor nodes. The average score metric is, as before, the average of the log( (SFF) metric over all six tasks, as in Table !
Model
Average score
*MPNN CE *MPNN (dense) SPD
-2.728
-2.157
*PPNN (dense) + CE + SPD
-2.107
*P-GNN
-2.650
MPNN w/ resistive (edge) embeddings
-2.789
MPNN w/ all affinity measure features
-3.106
D.2 Theory: ER 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 to.
We will call an initialization function u + (0) on nodes of a graph node-based if 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 = O and h too for all * s).
Consider the task of computing "single-source effective resistances," i.e., the effective resistance from a 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 nearby nodes.
Theorem D.I. Suppose we fix k: > 0. Then, given any
initialization function h (U) it impossible for GNN to compute single-source effective resistances from given node w to any nodes within k-hop neighborhood.
17

---

More specifically, for any update rule
m r1++1 (1() fe (X(())
(II)
h((+1) ØL+1 h (fmm: :(EN)))))
there exists a graph (V, E) and a E V such that after rounds of message passing, he Res(u, v) for some * within k-hop neighborhood of u.
+
On the other hand, there exists an initialization with respect which k rounds of message passing will compute the correct shortest path distances to all nodes within k-hop neighborhood.
Note that the assumption the initialization function in the above theorem is reasonable because enabling the use arbitrary, unrestricted functions would allow for the possibility of precomputing effective resistances in the graph and trivially incorporating them node features, which would defeat the purpose of computing them using pesssage-passingg
Proof. Consider the following set of graphs, each on 4k nodes:
Figure 2: Both of the above graphs are on 4k + vertices, labeled vo, Vi...., Vak- The only difference single edge, i.e., the graph on the left has an edge between U2A and U2 while the one on the right does not have this edge.
V4k
U1
V4
V2k
U2k+1
U2k
02k+1
Let V {vo, U1y.... vAR). The first graph G EV, is cycle, while the second graph G' (V, E') is a path, obtained by removing single edge from the first graph (namely, the one between eg and vx+1). Suppose the edge weights are all 1 in the above graphs.
"local" node feature initializa- tion. Note that for any GNN (i.e., update and aggregation rules in (II. add the formal update rule somewhere), the computation tree after rounds of message passing is identical for nodes No. 01..... Uk: 13841,vsk+2: ... Uib (i.e., the nodes within the k-hop neighborhood of vg) in both G and G". This because the only difference between and G' is the existence the edge between V2A and 024+1, and this edge is beyond a k k-hop neighborhood centered at any of the aforementioned nodes. Therefore, we will necessarily have that (k) is identical both G and G' for i i= 1,....,, hi 3k + 1,3k 2....,4k 4k.
Let w vo be the source and let (h: (0)
E V}
However, is easy to calculate the effective resistances in both graphs. In G. have Resc(vb, v4) (4k+1-() while in G', we have Res (vo, vi) min (i, 4k + i}. Therefore, Resc (vo, vz) o 1k+1
Reso (v0, v)) for all i = 1,2, k. 3k + 1, 3k + 2, 4k.
It follows that for any 1,2,..., 3k 1, + .... 4k, the execution of k message passing steps of a GNN cannot result in (.(8) Res(vo, vx) for both G and G", which proves the first claim of the theorem.
18

---

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 all nodes within k-hop neighborhood. Specifically, for source w, we can use the following setup: Take b = O and h, oo for all o w. Moreover, for any edge (u, v), let the edge feature Xae E IR simply the weight of (u, v) in the graph. Then, take the update rule [I] with fer t/++1 as identity functions and
fe(wwv) = -Nov
t441 (n()) h fe fe(xxu)) = =h + Xuv
1(5) = min E 5}
Φt+1 (a, b) min (an b}.
is clear that the above update rule simply simulates the execution of an iteration of the Bellman- algorithm. Therefore, & message passing steps will simulate iterations of Bellman-Fordd resulting
in correct shortest path distances from the source wo for every node within k-hop neighborhood. L
19


Reviews:
[{"review_id": "hONxLcHoFJ", "reviewer": "Reviewer_8Ddc", "summary": "In this paper, the authors present MPNN using affinity measures as node and edge features. As the affinity measures, the authors propose effective resistance, hitting times, and resistive embeddings. The authors demonstrate the effectiveness of using the affinity measures through experiments on various datasets. Experimental results on large graph datasets prove the good scalability of the scheme.", "questions": "Q1. Do the authors think that the experiments with the current hyper-parameter setting are fair?\n\nQ2. Could the authors explain on what basis they set the hyper-parameters for each method?\n\nQ3. Is it possible to improve performance by adding the proposed features to DGN?", "limitations": "The authors do not describe the potential negative social impact of their work while present future work to develop the work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. I \bconsidered the need for a comparison with shortest path distances (SPDs), however, the related description in Section D (in the supplementary material) is convincing.\n\n2. The proposed scheme has low computational complexity and good scalability.\n\n3. The paper is well-written and easy to understand.", "weaknesses": "It appears that the setting for MPNN models used in the experiments is not fair. According to Table 6 in the supplementary material, the number of layers is set to 3 for all models. Do the authors consider this setting to be fair? Furthermore, the hidden size of each layer is set differently for each method. What is the basis for setting the hidden size for each method? For example, the hidden size for GAT is set to 64 while that for HT + ER (rand rot) is set to 512.\n\nminor comment\n- fom -> from (Line 112)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1. Do the authors think that the experiments with the current hyper-parameter setting are fair?\n\nWe note that the hyperparameters for each model/baseline were chosen via a hyperparameter sweep. This includes, for instance, the hidden size. For each model in the table, we provide the best setting of hyperparameters, i.e., the setting that results in the best score. Therefore, we believe that the experiments do indeed provide a fair comparison. We thank the reviewer for raising this important question, and we will make sure to clarify these experimental details regarding the hyperparameter sweep.\n\n> Q2. Could the authors explain on what basis they set the hyper-parameters for each method?\n\nWe swept over hyperparameters as follows:\n\n- Hidden size: {64, 128, 256, 512}\n- Learning rate: {1e-4, 1e-3, 5e-3}\n- Number of layers (for MLP): {2, 3}\n- Message passing steps: {1, 2, 3}\n\nAll combinations of the above hyperparameters were tried out (with repetition over multiple seeds) for every model/baseline, and the best setting of hyperparameters was reported for each model.\n\nWe will, once again, add further clarification to the paper on the details of the hyperparameter sweep.\n\n> Q3. Is it possible to improve performance by adding the proposed features to DGN?\n\nIndeed, it is possible to add affinity features to DGN. We have not tested this out here, as DGN requires significantly altering the model architecture by modulating the message passing mechanism. However, in order to give some indication of how affinity measures can work in tandem with the features considered in DGN, below we report a new set of experimental results on the PNA dataset for an MPNN model that uses affinity features along with  _DGN features_ (note that use of _DGN features_ without affinity features was already reported in Table 1 of the submission):\n\n- **DGN features + affinity measures: -2.938**\n- DGN features only (already reported in Table 1): -2.743\n\nAs in the paper, the above results on the PNA dataset denote the average score (log(MSE)) over the relevant set of six tasks, and the results are averaged over 10 random seeds. The above numbers show that adding affinity measures results in an improvement over _DGN features_.\n"}, {"review_id": "BG6kzJezRM", "reviewer": "Reviewer_YKRe", "summary": "This paper proposes to use affinity measures as additional features that can incorporate in common standard MPNNs and theoretically and empirically shows the improvement in expressiveness and performance in some datasets without loss of much scalability. The main contributions are listed below.\n1. Generality. The proposed approach can be adopted in standard MPNNs.\n\n2. Expressiveness. Incorporating the proposed features can make standard MPNNs more powerful than the 1-WL test.\n\n3. Scalability. The affinity measures used in this paper are based on the random walk. By approximation, the features derived from the proposed measures can be incorporated with high scalability.\n\n4. Performance. MPNNs equipped with the proposed additional features can make progress or even rank 1 in some datasets.", "questions": "1. It’s said in Sec. 5.4 that ER embedding dimension become impractically high and authors alter to use ER scalar features. What are the theoretical and empirical (experimental) differences between the two kinds of features? If ER scalar features in small graphs can make the same progress with ER embedding? If not, why?\n\n2. Incorporating hitting time features, resistive embeddings, and effective resistance are all proven to be more powerful than 1-WL in Sec. 3.4. Why does using ER/HT in experiments have different results? Is there any suggestion about selecting which feature?\n\n3. The performance of the proposed method does not surpass the DGN in Table 2 and does not show advantages when more layers are in Table 3. More explanations are expected although the proposed method shows advantages in other aspects.\n\n4. How the proposed features help in heterogeneous networks may be interesting. Possible explanations are expected.", "limitations": "1. As said in W3, the actual runtime in large graphs may be much higher than (scalable) baseline methods.\n\n2. As said in Q2, experiments use different features (ER embedding/HT …), thus suggestion about selecting feature is needed.\n\n3. When demonstrating the expressiveness of the proposed approach, experiments on some datasets tailored for evaluating expressive power are expected. For instance, one can synthesize a dataset containing instances indistinguishable by 1-WL(e.g. [1][2]) to see if the proposed approach can distinguish.\n\n[1] Sato R, Yamada M, Kashima H. Random features strengthen graph neural networks[C]//Proceedings of the 2021 SIAM international conference on data mining (SDM). Society for Industrial and Applied Mathematics, 2021: 333-341.\n[2] Abboud R, Ceylan I I, Grohe M, et al. The surprising power of graph neural networks with random node initialization[J]. arXiv preprint arXiv:2010.01179, 2020.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper was inspired by effective resistances and proposed HT, ER and resistive embeddings all help common MPNNs in both performance and expressiveness. As a feature-based approach, it can adapt to many standard MPNNs and does not need to specify any anchor or target nodes to capture both distance and connectivity information using general-purpose node and edge features.\n\n2. By Approximation and fast computation of Resistive Embeddings and HT, the proposed features can scale up to large graphs in time and space complexity.\n\n3. The experimental results are impressive. With relatively low computation cost, the proposed method can have a competitive performance on small datasets and higher performance on homogeneous/heterogeneous citation networks. Further, the best performance achieved on PCQM4M-v1 is impressive.\n\n4. Both theoretical proof and empirical evaluations are provided.", "weaknesses": "1. The motivation needs to be clarified more clearly. What the main drawbacks of the existing approaches are and which the proposed one surmounts? It’s said that the proposed approach “without the need for specifying any anchor or target nodes” and the scalability problem is mentioned in the experiments section. However, the advantages should be clarified further and organized better since there are other feature-based works and other categories of works aiming at a similar goal. Some practical evaluation or comparison may help if possible.\n\n2. To demonstrate the superiority and necessity of the proposed affinity feature-based approach, other similar approaches need to be compared. Similar to the proposed affinity-based features, approaches incorporating other additional features (e.g. Random features or other dedicated designed features), and other methods that can improve GNNs’ expressiveness (e.g. other 2 directions mentioned in Expressivity para in Sec. 2) should also be compared in scalability and performance.\n\n3. Although by approximation, the computation of random embeddings can be done in near-linear time and can be scaled to a large dataset, it’s better to provide the actual runtime of the proposed and baseline methods.\n\n4. Theorem 3.6 claims that MPNNs that make use of any one of the proposed features are strictly more powerful than the WL-1 test. However, the experiments for it are not enough. Experiments on ogbg-molhiv show that it outperforms substructure counts, but the reasons are not clear. Experiments on some (artificial) datasets (e.g. [1][2]) which are designed for testing expressiveness would be better.\n\n5. More well-organized writing should be considered. The notations scattering in Sec. 3.1-3.3 bring some difficulty in reading. The different baselines, settings, and experimental results in each subsection in Sec. 5 are scattered, either in the tables or in the text, which may weaken the empirical demonstration effects of experiments and cause some confusion. Some nouns or notations are introduced but not explained clearly, such as ER scalar features, node or edge features used in experiments, e_v in Eq. (1), and random rotations. Introducing them in a centralized and unified manner may help. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. The motivation needs...\n\nFeatures in GNNs are typically subject to a tradeoff between (a.) efficiency and (b.) high expressivity. For instance, random features or node index features address (a.) at the cost of (b.), while other features such as substructure counts help with (b.) but fall short in (a.), e.g., computation can be superquadratic in the number of nodes. Our work is _motivated by this tradeoff and addresses the challenge of bridging (a) and (b)_. We highlight that our approach is also general in nature, something often not true for structural features where one needs to identify the (domain-specific) structures of interest.\n\n> 2. To demonstrate...\n\nWe note that the submission includes some comparisons to approaches you mention. For the PNA dataset, the results in Table 1 include MPNN baselines with (a) random features and (b) DGN features. Furthermore, for the molecular datasets (ogbg-molhiv, ogbg-molpcba), we have included comparisons to both the junction tree-based HIMP baseline (mentioned as [13] in Section 2) as well as the substructure-based GSN baseline ([6] in Section 2). We have additionally included random walk-based baselines such as GRWNN (see Table 2).\n\n> 3. Although by...\n\nComputation times for the ogbn-arxiv dataset are provided on page 8. We further highlight that the computation of effective resistances proceeds via computation of the embeddings, followed by a quick computation of L2-squared distances between pairs of embeddings (see Lemma 3.2). Without the use of approximate random embeddings, the computation would require an expensive matrix inversion that would be infeasible for the size of the dataset (169,343 nodes).\n\n> 4. Theorem 3.6 claims...\n\nThank you for the suggestion. As mentioned in the global response to all reviewers, we have now included results on the synthetic datasets, TRIANGLE(N) and LSC(N) in [1]. Once again, the results (test ROC-AUC score, higher is better) are as follows (see global response for experimental details):\n\n_TRIANGLE (N)_:\n\nGIN:\n- GIN: 0.5\n- GIN + rand feats: 0.924\n- **GIN + res embeddings: 0.911**\n\nGCN:\n- GCN: 0.5\n- GCN + rand feats: 0.857\n- **GCN + res embeddings: 0.879**\n\n_LSC (N)_:\n\nGIN:\n- GIN: 0.5\n- GIN + rand feats: 0.847\n- **GIN + res embeddings: 0.935**\n\nGCN:\n- GCN: 0.5\n- GCN + random features: 0.794\n- **GCN + res embeddings: 0.873**\n\n> 5. More well-organized writing...\n\nWe will work on improving the organization and writing in the final version.\n\n> Q1.\n\nThere are two potential sources of scalability bottlenecks: **computational complexity** and **GPU memory**. The impracticality referred to in Sec. 5.4 concerns the latter, not the former. Indeed, even on ogbn-arxiv, we are able to compute resistive embeddings without any problem and, in fact, use them to obtain ER scalar values (via Lemma 3.2) to **avoid computationally infeasible matrix inversions**. However,  the high dimensionality of the embeddings makes them infeasible to use in GPU memory.\n\nWe note that resistive embeddings are still richer than ER/HT scalar values (the latter can be computed from the former) and have observed empirical improvements on the datasets where we try them. In addition to Table 1 for the PNA dataset, which shows lift from using embeddings along with scalar features, we note that for ogbg-molhiv, using ER scalar features yields a Test % ROC-AUC of 77.75 ± 0.426, while using hitting time scalar features yields 76.56 ± 0.915. However, as reported in Table 2, additionally _using embeddings produces a much higher Test % ROC-AUC of 79.13 ± 0.358_.\n\n> Q2.\n\nWhile it is indeed true that any of the features (ER, HT, resistive embeddings) results in more power than 1-WL, it is not _a priori_ clear that including these features would necessarily give better empirical test accuracy. We nevertheless show that affinity measures do improve empirical performance to varying degrees. It should also be noted that we generally use the scalar features as _edge features_, while embeddings are incorporated as both _node features_ and _edge features_. This can result in differing test performance, as MPNNs use node and edge features differently.\n\nRegarding selection of features, we have generally found that _using both embeddings and scalar features (ER and HT) results in the best performance_. However, for very large graphs (thousands of nodes), we stick to using just scalar features due to GPU memory bottlenecks.\n\n> Q3.\n\nApproaches to improve expressivity and performance of GNNs fall into three categories, viz., feature augmentation, message passing modulation, and graph modification — our technique falls under the first approach, while DGN falls under the second. While our approach has been to augment affinity measures as features, one is not by any means limited to this approach — an exciting future direction would be to use affinity measures to modulate the message passing, which would provide a fairer comparison to DGN. In order to give some indication of an apples-to-apples comparison to DGN, in Table 1 we have provided a “DGN (features)” baseline, which (instead of modulating the message passing mechanism of the MPNN) incorporates the relevant features via feature augmentation.\n\n> Q4.\n\nHeterogeneous networks may be viewed as graphs with multiple node and/or edge types. One can apply our techniques based on affinity measures in a few different ways. One way is to consider all types of nodes/edges together and compute affinity measures on the combined graph in the usual way, then incorporating them in the desired message-passing architecture (this is, for instance, our approach for experimentation on ogbg-molhiv, which has multiple edge types arising from different bond types). Another way is to consider the various node or edge types separately and compute affinity measures for separate graphs in isolation. Furthermore, with either approach, one can optionally aggregate different edge types separately, e.g., using an architecture like R-GCN).\n"}, {"review_id": "c6x6En6W45", "reviewer": "Reviewer_vQdB", "summary": "The paper proposes a strategy to strengthen the node and edge features in order to enhance the expressiveness of a message passing neural network. In particular, the paper introduces a set of effective resistance (ER) features, including node-level resistive embedding, which further derives two edge-level affinity measures: hitting time and commuting time/effective resistance. Additionally, the paper employs Constructive Johnson-Lindenstrauss to randomly project resistive embeddings to a lower-dimensional space, which is utilized to expedite the computation of hitting time and commuting time. Finally, the paper present the empirical evaluations on the proposed ER features.", "questions": "1. I would like to seek clarification from the authors regarding the connection between \"1-WL\" and \"standard GNN\" in the context of node classification, as demonstrated in the paper to support the claim made by Theorem 3.6. The provided example gives me the impression that a \"standard GNN\" represents each node using a spanning tree rooted at the node of interest (referred to as a computation tree) and distinguishes nodes based on the isomorphism of these spanning trees.\n\n   To facilitate readers' understanding of this concept, I kindly request the authors to provide a specific example of the computation tree that a standard GNN employs to represent a node. It would also be helpful if the authors could provide some justification or reference regarding the connection between the node representation learned by standard GNNs and the utilization of spanning trees.\n\n2. By utilizing the initial node feature as the one-hot encoding of the node's index, denoted as $\\textbf{h}_v^{(0)} = \\textbf{e}_v$, and employing the forward function $\\mathbf{H}^{(t+1)} = \\mathbf{A}\\mathbf{H}^{(t)}$, we can observe that after 4 layers, the node embeddings generated by the standard GNN successfully differentiate the 3 color categories. Specifically, if we define a score $s_v = <\\textbf{h}_v^{(4)}, \\textbf{e}_v>$, the value for nodes {1,2} is 15, for nodes {3,4,7,8} it is 17, and for nodes {5,6} it is 19. This observation contradicts the claim that \"a standard GNN that is limited by the 1-WL test cannot distinguish any pair of nodes in a regular graph.\" Consequently, I have some follow-up questions based on this discrepancy.\n  \n   (1) What is the specific constraint on the input features to a standard GNN?\n   \n   (2)  Will the benefit from resistive embedding become less evident as we increase the depth of an MPNN?\n\n3. In Appendix D.2, a comparison is conducted between resistive embedding and shortest-path-distance embedding in terms of their ability to differentiate nodes within a cycle and the corresponding nodes in the path obtained by removing one edge from the cycle. \nThe example effectively illustrates that node embeddings based on shortest-path-distance are insufficient in capturing the divergence that can be successfully captured by resistive embeddings. However, this raises a valid concern regarding real-life networks where edges may be lost due to noise. In such cases, will the strong ability of resistive embeddings to distinguish between graphs that are close in terms of edit distance potentially make them susceptible to overfitting the noise?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written: the motivation is clearly presented, and most sections are straightforward to follow.\n2. The fast approximation of computing hitting time and commuting time is novel. The dimensionality of resistive embedding is reduced without the requirement of specifying a set of anchor nodes.\n3. The experiment on large graphs demonstrates that the computation cost of adding these features to MPNN is manageable.", "weaknesses": "1. The paper would benefit from providing stronger evidence to support certain claims made throughout the text. Please refer to the \"Questions\" section for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. I would like to seek clarification from the authors regarding the connection between...\n\nIndeed, the message passing mechanism of a GNN gives rise to a computation tree with depth given by the number of message passing steps. As an example, for the graph in Figure 1, if we use two rounds of message passing (i.e., 2 MPNN layers), the resulting node representation for node 1 would arise from the following depth-2 computation tree rooted at 1:\n\n```\n1\n├── 2\n│   ├── 1\n│   ├── 3\n│   └── 4\n├── 7\n│   ├── 1\n│   ├── 6\n│   └── 8\n└── 8\n    ├── 1\n    ├── 5\n    └── 7\n```\n\nWe would be happy to provide any further examples or clarification if needed during the discussion phase and can incorporate them in the camera-ready version.\n\n\n> 2. By utilizing the initial node feature as the one-hot encoding of the node's index...\n\nThe standard setting for comparing GNNs to the 1-WL test is the one in which all nodes start with the same representation/color before the series of updates. Therefore, in the case of a regular graph, if one starts with the same representation for every node, updates (whether aggregation in a GNN or color/hashing updates in 1-WL) will leave every node with the same representation after every step.\n\nYou note correctly that starting with one-hot encodings of the node index as initial node features will allow nodes to be distinguished by a GNN; however, in this case the appropriate comparison is the 1-WL procedure which _also starts with one-hot encodings as initial ‘colors’_, which allows all nodes to be trivially distinguished from each other. The fact that node indices can improve GNN expressivity has been well documented: even random node features (essentially a more scalable way of providing node indices, as one typically does not want the node feature dimensionality to scale with the number of nodes n, as one-hot encodings of nodes would do) improve GNN expressivity (see [1], [2]).\n\nSpecifically, we answer your questions as follows:\n\n1. In the “standard” setting, one starts with the same representation for every node (i.e., no use of distinguishing node features). However, one can also start with more general node representations/colorings, but in this case the 1-WL test being compared to must also use the same initial node colorings.\n2. Increasing the depth of an MPNN too much can pose various general issues, such as vanishing gradient or oversquashing (see [3], [4], [5]). We expect these to still be the case when using resistive embeddings, so the benefit for large depths could be muted, as is the case more broadly for MPNNs.\n\n[1] Ryoma Sato. “A Survey on The Expressive Power of Graph Neural Networks.”\n\n[2] Ryoma Sato, Makoto Yamada, Hisashi Kashima. “Random Features Strengthen Graph Neural Networks.”\n\n[3] Uri Alon, Eran Yahav. “On the Bottleneck of Graph Neural Networks and its Practical Implications.”\n\n[4] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, Michael M. Bronstein. “Understanding over-squashing and bottlenecks on graphs via curvature.”\n\n[5] Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Lio', Michael Bronstein. “On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology.”\n\n\n> 3. In Appendix D.2, a comparison is conducted between resistive embedding and shortest-path-distance embedding...\n\nIn a worst-case scenario, removing an edge can change the effective resistance between a given pair of nodes appreciably. However, this is not a phenomenon limited to effective resistance—even in the case of shortest path distance, adding/removing a single edge can change the distance between the endpoints by an arbitrarily large factor.\n\nNevertheless, we observe that in **real-world networks**, effective resistance tends to be a fairly _robust_ measure. Note that removing an existing edge $e$ can never decrease any effective resistances, and for a connected graph, one can show that it can only increase the effective resistance between any pair of nodes by at most a factor of $1/(1-R_e)$. (Note that we necessarily have $R_e \\leq 1$ for any existing edge of the graph, and as long as e is not a bridge edge whose removal disconnects the graph, the inequality is strict.) Applying this fact to the underlying graph of the ogbn-arxiv dataset, we observe that 95% of the edges in the graph have $R_e < 0.5$, which implies that the removal of any such edge will increase the effective resistance between any pair of nodes by a factor of $< 2$ (this property does not, however, hold for shortest path distance). Similarly, it can be shown that adding an edge $(u,v)$ can only decrease the effective resistances by a factor of $1/(1+R_{uv})$. Thus, adding an edge between nearby nodes will also not affect the effective resistances much. \n\n\n"}, {"review_id": "dhYsoU1Otw", "reviewer": "Reviewer_2Foc", "summary": "This work proposes to incorporate affinity measures as features into message-passing networks (MPNNs) in order to enhance the expressivity without enlarging the computational cost notably.\nThe authors introduce three examples of random-walk-based affinity measures, e.g., effective resistance, hitting, and commute times, and provide efficient computation and low-rank approximation for them.\nOn multiple graph benchmarks, ranging from graph-level tasks to transductive node-classification on large-scale graphs, the proposed affinity measures can remarkably improve the performance of MPNNs and reach state-of-the-art performance among models without privileged information.\n", "questions": "(Loukas, 2020; Dwivedi et al., 2021) mention that encoding can enhance the ability of MPNNs to uniquely distinguish nodes and hence improve the expressive power of MPNNs.\nI am curious whether the affinity measures enhance MPNNs in a similar way. Or they can provide extra valuable information that non-affinity-based encoding can not provide. \nIn other words, if there exists a non-affinity-based encoding able to distinguish isomorphic graphs as well as the proposed affinity measures, such as subgraph counting (Bouritsas et al., 2022), will incorporating the proposed affinity measures into MPNNs enjoy extra advantages over such an encoding? Whether graph-level tasks and node-level tasks have different conclusions regarding this?\n\nIf possible, it would be perfect if you could provide more comparisons theoretically/empirically against several PE-enhanced MPNNs (Dwivedi et al., 2021; Zhang et al., 2021; Wang et al., 2022; Lim et al., 2022; Li et al., 2020; Bouritsas et al., 2022) and potentially the PE for Graph Transformers (Zhang et al., 2023; Ma et al., 2023).\n\n\n\n\n- Loukas, A. (2020). How hard is to distinguish graphs with graph neural networks? Adv. Neural Inf. Process. Syst.\n- Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph Neural Networks with Learnable Structural and Positional Representations. Proc. Int. Conf. Learn. Representations. \n- Bouritsas, G., Frasca, F., Zafeiriou, S. P., & Bronstein, M. (2022). Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1–1.\n- Zhang, Z., Cui, P., Pei, J., Wang, X., & Zhu, W. (2021). Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs. IEEE Transactions on Knowledge and Data Engineering.\n- Wang, H., Yin, H., Zhang, M., & Li, P. (2022). Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. Proc. Int. Conf. Learn. Representations.\n- Lim, D., Robinson, J. D., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and Basis Invariant Networks for Spectral Graph Representation Learning. ICLR 2022 Workshop on Geometrical and Topological Representation Learning. \n- Li, P., Wang, Y., Wang, H., & Leskovec, J. (2020). Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. Adv. Neural Inf. Process. Syst. \n- Zhang, B., Luo, S., Wang, L., & He, D. (2023). Rethinking the Expressive Power of GNNs via Graph Biconnectivity. Proc. Int. Conf. Learn. Representations. \n- Ma, L., Lin, C., Lim, D., Romero-Soriano, A., K. Dokania, Coates, M., H.S. Torr, P., & Lim, S.-N. (2023). Graph Inductive Biases in Transformers without Message Passing. Proc. Int. Conf. Mach. Learn.\n\n\n\n\n\n\n", "limitations": "No limitations are provided. \n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. According to my best knowledge, this work is the first to propose that incorporating affinity-based measures into MPNNs can improve the expressive power of MPNNs, going beyond the 1-WL algorithm.\n2. This work also provides several techniques to improve the efficiency of the introduced affinity-based measures.\n3. The authors show that MPNNs+affinity measures are strictly more powerful than the 1-WL algorithm via the example of regular graphs.\n4. The empirical experiments demonstrate the effectiveness of the proposed methods on graph-level tasks and transductive node-level tasks. The experiment on large-scale graphs also shows the efficiency of the proposed technique.", "weaknesses": "1. The paper does not have more throughout comparisons with other positional encoding enhanced graph neural networks, theoretically and empirically. For details, please see the question section.\n2. The baselines in empirical comparisons seem to have different numbers of parameters compared to the proposed method. It will be better to have a more detailed explanation on the choices of hyperparameters.\n\n\n\n\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. The paper does not have more throughout comparisons with other positional encoding enhanced graph neural networks...\n>  If possible, it would be perfect if you could provide more comparisons...\n\nWe note that we have already provided comparisons to the GSN model of Bouritsas et. al. for ogbg-molhiv.\n\nRegarding the DE-GNN model of Li et al., we note that it is difficult to compare our method with theirs, as their paper does not handle graph prediction tasks. In fact, the DE-GNN paper is concerned with learning structural representations of small sets of nodes and notes: To quote the paper, _“Our approaches may also help other tasks based on structural representation learning, such as graph-level classification/regression [14, 16, 23, 25, 30] and subgraph counting [59], which we leave for future study.”_ The fact that most experiments in our paper concern graph prediction makes a proper comparison with DE-GNN elusive. However, we have nevertheless attempted to compare our work to the key ideas of Li et al. and have included comparisons to distance-based features in Appendix D.\n\nBelow, we provide some additional comparisons to PE-enhanced MPNNs:\n\nDwivedi et al., 2021: On ogbg-molpcba, we note that the authors’ PNA-LSPE model (on 4 layers) obtains a test AP of 28.4 ± 0.2, while their GatedGCN-LSPE model obtains a test AP of 26.7 ± 0.2. We note that our best 4-layer, 8-layer, 16-layer models are competitive with the former (within the margin of error) while surpassing the latter.\n\n> 2. The baselines in empirical comparisons seem to have different numbers of parameters compared to the proposed method. It will be better to have a more detailed explanation on the choices of hyperparameters.\n\nWhen we add scalar features (e.g., ER or HT), there are only 2-3 extra features added, so this does not appreciably increase the number of hyperparameters.\n\nEven when we add the vector resistive embeddings in addition to the scalar features, we find that the number of hyperparameters increases by less than 10% (e.g., for the PNA dataset, the comparable MPNN models with and without affinity measures have around 9.7M and 8.9M hyperparameters, respectively, representing a 9% increase). \n\nRegarding the choice of hyperparameters, we find that using all affinity measures together (both ER and HT scalar features as well as vector resistive embeddings) generally works the best; however, on larger datasets for which GPU memory is a bottleneck, we stick to using just the scalar features.\n\n> Q. (Loukas, 2020; Dwivedi et al., 2021) mention that encoding can enhance the ability of MPNNs to uniquely distinguish nodes...\n\nAppendix D shows some experiments comparing affinity measures to other positional/structural encodings such as shortest path distance encodings and centrality encoding (which has been used in graph transformer architectures such as Graphormer (Ying et al. 2021)), providing evidence that affinity-based encodings can provide extra information that other encodings cannot. We further note that the experiments in Appendix D are on a collection of graph-level and node-level tasks, providing indication that affinity-based encodings can be beneficial in both settings.\n\nWe nevertheless note that the question of whether affinity-based encodings can provide advantages via approaches other than feature augmentation is a scintillating one. While we have primarily incorporated affinity measures as features to an MPNN, one need not be limited by this route. Positional encodings (that allow nodes to be located/distinguished within a graph) have proved to be particularly important for non-message passing architectures such as Graph Transformers, which crucially rely on positional and structural encodings to make up for the loss of inductive bias arising from the separation of the computation graph from the input graph. A fascinating direction for future work would be to explore the use of affinity-based positional encodings in such architectures.\n\n"}]

Author rebuttal:
We thank the reviewers for taking the time to look through our submission and provide insightful comments and questions. In light of the comments raised by reviewers, we have provided further results and addressed several concerns. We respond to each reviewer individually.

There is one **experimental update** that we would like to highlight to all the reviewers:

In response to questions about expressivity, we are now providing new experimental results with comparisons to the synthetic datasets, _TRIANGLE(N)_ and _LSC(N)_ (from [1]) to show stronger evidence that affinity measures exhibit improved expressivity. For both datasets, we follow the setup in [1] and use GIN and GCN models, which we augment with resistive embedding node features and compare to both (a.) vanilla models and (b.) models augmented with random features (the main contribution of [1]). The results (test ROC-AUC score, higher is better) are as follows:


_TRIANGLE (N)_:

GIN:
- GIN: 0.5
- GIN + random features: 0.924
- **GIN + resistive embeddings: 0.911**

GCN:
- GCN baseline: 0.5
- GCN + random features: 0.857
- **GCN + resistive embeddings: 0.879**


_LSC (N)_:

GIN:
- GIN baseline: 0.5
- GIN + random features: 0.847
- **GIN + resistive embeddings: 0.935**

GCN:
- GCN baseline: 0.5
- GCN + random features: 0.794
- **GCN + resistive embeddings: 0.873**


We find that using resistive embeddings results in the highest ROC-AUC scores in all cases except for GIN on TRIANGLE, in which case random features and resistive embeddings are comparable. This provides strong evidence that the given affinity measures indeed provide enhanced expressivity.

[1] Sato R, Yamada M, Kashima H. Random features strengthen graph neural networks[C]//Proceedings of the 2021 SIAM international conference on data mining (SDM). Society for Industrial and Applied Mathematics, 2021: 333-341.


Meta-review: This paper provides a steady technical contribution to graph neural networks. Many of the concerns raised by the reviewers were addressed through discussions with the authors.
Decision: Accept (poster)