Commute Graph Neural Networks
Authors: Wei Zhuo
Han Yu
Guang Tan
Xiaoxiao Li
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Commute Time
Message Passing
Node Classification
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose an approach to integrate commute time into graph neural networks to enhance the analysis of directed graphs, effectively addressing the asymmetry and complex path interactions inherent in these structures.

Abstract: Graph Neural Networks (GNNs) have shown remarkable success in learning from graph-structured data. However, their application to directed graphs (digraphs) presents unique challenges, primarily due to the inherent asymmetry in node relationships. Traditional GNNs are adept at capturing unidirectional relations but fall short in encoding the mutual path dependencies between nodes, such as asymmetrical shortest paths typically found in digraphs. Recognizing this gap, we introduce Commute Graph Neural Networks (CGNN), an approach that seamlessly integrates node-wise commute time into the message passing scheme. The cornerstone of CGNN is an efficient method for computing commute time using a newly formulated digraph Laplacian. Commute time is then integrated into the neighborhood aggregation process, with neighbor contributions weighted according to their respective commute time to the central node in each layer. It enables CGNN to directly capture the mutual, asymmetric relationships in digraphs. Extensive experiments on 8 benchmarking datasets confirm the superiority of CGNN against 13 state-of-the-art methods.

Commute Graph Neural Networks
Wei Zhuo! 122
Han Yu
Guang Tan
Xiaoxiao Li
Abstract
Digraph
Undirected graph
Graph Neural Networks (GNNs) have shown remarkable success in learning from graph- structured data. However, their application to directed graphs (digraphs) presents unique chal- lenges, primarily due to the inherent asymmetry node relationships. Traditional GNNs are adept capturing unidirectional relations but fall short in encoding the mutual path dependencies between nodes, such as asymmetrical shortest paths typ- ically found in digraphs. Recognizing this gap. we introduce Commute Graph Neural Networks (CGNN), an approach that seamlessly integrates node-wise commute time into the message pass- ing scheme. The cornerstone of CGNN is an effi- cient method for computing commute time using newly formulated digraph Laplacian. Commute time is then integrated into the neighborhood ag- gregation process, with neighbor contributions weighted according to their respective commute time to the central node in each layer. It enables CGNN directly capture the mutual, asymmetric relationships in digraphs. Extensive experiments on 8 benchmarking datasets confirm the superior- ity of CGNN against 13 state-of-the theftthe-rt art methods.
U
Um
Ui
Um
Vi
Uk
SPD(e m1) (P. + vz)
SPD + ey) SPD v2) SPD(M, -e) (vD e,)
- -x) SPD v.)
asymmetric relntionships
symmettrc relationships
A digraph and its undirected counterpart. Blue arrows indicate unidirectional paths, together with longer paths in the gray area, forming commute closed loops be- tween the central node i; and outgoing neighbors dy and Vk. In the undirected graph, shortest path distances (SPD) between nodes symmetric. However, in the digraph, the fact that unidirectional SPDs are equal does not imply that mutual SPDs will also be equal. For instance, while the SPDs from v to Uy and 1k are identical, the reverse SPD from and Uk back to e do not necessarily match these distances.
Figure I:
2023). The essence of GNN-based digraph analysis lies in utilizing GNNs to learn expressive node representations that encode edge direction information.
1. Introduction
To achieve this, modern digraph neural networks de- signed to integrate edge direction information into the mes- sage passing process by distinguishing between incoming and outgoing edges. This distinction enables the central node to learn directionally discriminative information from neighbors. As illustrated in the digraph of Figure 1, given central node vú, 1-layer digraph neural network can aggregate messages from U, 's incoming neighbor um and outgoing neighbor 2y, and simultaneously capture edge directions by applying direction-speciie aggregation func- tions (Rossi et al., 2023), or by predefining edge-specific weights (Zhang et al., 2021; Tong et al., 2020b).
Directed graphs (digraphs) widely employed to model relational structures in diverse domains, such social networks (Cross et al., 2001) and recommendation sys- tems (Qiu et al., 2020). Recently, the advances of graph neural networks (GNNs) have inspired various attempts to adopt GNNs for analyzing digraphs (Tong et al., 2020a;b; 2021; Zhang et al., 2021; Rossi al.. 2023: Geisler al.,
Most of this work was done when Wei Zhuo zheo tattuuo@nt.eedu.g... was with Shenzhen Campus of Sun Yat-sen University. 'Shenzhen Campus of Sun Yat-sen Uni- versity, China "Nanyang Technological University, Singapore 'The University British Columbia, Canada VVector Institute, Canada. Correspondence to: Guang Tan <tanguang @ mail. mai..sys..co.. sys..cdu.cn.......
Despite the advancements, current digraph neural networks primarily capture unidirectional relationships between nodes, neglecting the complexity arising from path asymme-
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In "unidirectional" refers relationships in digraphs where edges have specific direction from one node to another.

---

Commute Graph Neural Networks
try. For instance, a k-layer GNN aggregates the neighbors within the shortest path l for the central node. If the graph is undirected, the shortest path between any two nodes is symmetric, as shown in the undirected graph of Figure 1. This symmetry simplifies the representation of node rela- tionships, implying that if the shortest path distances (SPDs) from one node to two other nodes are identical, then the SPDs from these two nodes back to the source node must also be the same. Conversely, such symmetry is absent in digraphs. Considering the digraph in Figure 1, the short- est paths between v and b/ are asymmetrie. Therefore, although 2 and Uy are both immediate outgoing neighbors of vi the strength of their relationships with the central node differs significantly. Existing methods (Rossi et al., 2023; Tong et al., 2020b: Zhang et al., 2021), by focusing solely on unidirectional shortest paths (blue and red arrows), fail to capture the asymmetry phenomenon, which conveys valuable information of node relationships. Take social net- works as an example: an ordinary user can directly follow a celebrity, yielding a short path to the celebrity, yet the reverse path from the celebrity to the follower might be much longer. Considering only the short path from the fol- lower to celebrity could falsely suggest a level of closeness that does not exist. In contrast, accounting for the mutual paths between users yields more precise and robust mea- sure of their relationship, with stronger mutual interactions implying stronger connections.
of labels for V. Let A E BNN be the adjacency matrix and D diag(d1, ... dN) RNNN be the degree ma- trix of A, where d; = -, Aij is the out-degree of vi. Let Á - A + I and D = D + I denote the adjacency and degree matrix with self-loops, respectively. The tran- sition probability matrix of the Markov chain associated with random walks on G' is defined as P = D D- where P = A /dgg(())) is the probability of a 1-step random walk starting from oy Vi- Graph Laplacian formalized as L = D A is defined on the undirected graph whose adjacency matrix is symmetric. The symmetrically normal- ized Laplacian with self-loops (Wu et al., 2019) is defined as f = DDD+ &, where L = D A.
Digraph Neural Networks DirGNN (Rossi et al., 2023) is general framework that generalizes the message pass- ing paradigm to digraphs by adapting to the directionality of edges. It involves separate aggregation processes for incoming and outgoing neighbors of each node as follows:
(e) i,in
= Agen
(1)
(f uy E E.,, }
Mi,ou = (2)
(e)
Aggout
((nfe-1) vg E eVouu)
(I)
(0) n Comb (t) (e-1) mimi: mi
where 7i and Noout are respectively incoming and outgoing neighbors of Uy. ( and Aggell (-) are specialized aggregation functions of A²t and .N!il at layer L, used to encode the directional characteristics of the edges connected to Ut.
To capture the mutual path interactions in GNNs, we adapt the concept of commute time, the expected number of steps to traverse from source node to a target and back, from the Markov chain theory to the domain of graph learning. To this end, we first generalize the graph Laplacian to the digraph by defining the divergence of the gradient on the di- graph. Utilizing this digraph-specific Laplacian, we develop an efficient method to compute commute time, ensuring sparsity and computational feasibility. Then we incorporate the commute-time bime---ed proximity measure into the mes- sage passing process by assigning aggregation weights to neighbors. The intuition behind is that the immediate and unidirectional neighboring relationships do not necessarily imply strong similarity, but the mutual proximity is a more reliable indicator of relationship closeness. Our experimen- tal results demonstrate the efficacy of CGNN. Particularly, compared with the best-performing baseline, it achieves an average improvement of 2.64% and 4.17% in accuracy the Squirrel and Citeseer datasets, respectively.
3. Random Walk Distance and GNNs
Based on the established notations, we then show that mes- sage passing based GNNs naturally capture the concept of hitting time during information propagation across the graph, due to the unidirectional nature of the neighborhood aggregation. Subsequently, we argue for the significance of commute time, highlighting it as a more compact measure of mutual node-wise interactions in random walks.
3.1. Can GNNs Capture Random Walk Distance?
In the context of random walks on a digraph, hitting time and commute time, collectively referred to as random walk distances, serve as key metrics for assessing node connec- tivity and interaction strength. Hitting time h(v; v2) the expected number of steps a random walk takes to reach specific target node vj for the first time, starting from a given source node Vt. Commute time c(e,, v/) is the ex- pected number of steps required for a random walk to start at v; reach Vy and come back. A high hitting (commute) time indicates difficulty in achieving unidirectional (mutual)
2. Preliminary
Notations Consider G = (V, E, X) as an unweighted di- graph comprising N nodes, where V {us) )ma, is the node set, E C (V V) is the edge set with size M, X E R is the node feature matrix. Y ". NN is the set
2

---

Commute Graph Neural Networks
visits each other in a random walk. As illustrated in the digraph of Figure 1, commute time c(v;, Uz) > c(vi, vk), while the hitting time h(um: vs) = h(v,, 0z) = h(v,, Uk).
ward paths. For instance, even though h( v2)) h( Ug). shorter commute time c(1,, Ub) < c(v;, V1) suggests stronger interaction from vk to t; compared to fj to vi.
Consequently, the contribution of neighbor dp to the repre- sentation of U; should be greater than that of vi-.
Motivation Given these definitions, two questions arise: How crucial is it to retain these measures in graph learn- ing? Also, are message- paaggggggggnggggg GNNs capable of preserving these characteristies? Firstly, both hitting time and commute time are critical in understanding the structural dynamies of graphs. Hitting time, analogous to the shortest path, mea- sures the cost of reaching one node from another, reflecting the directed influence or connectivity. Commute time, en- compassing the round-trip journey, offers insights into the mutual relationships between nodes, which is especially ev- ident in social networks, as illustrated by celebrity-followw relationships. Secondly, message- pasanigg GNNs are some- what effective in capturing hitting time, as they propagate information across the graph in a manner similar to a random walk, where quickly reached nodes are preferentially aggre- gated, and the influence of nodes exponentially diminishes with increasing distance (Topping et al., 2022). However, GNNs face challenges in preserving commute time due to their requirement for comprehending mutual path relations, which are inherently asymmetric and often involve longer- range interactions especially in digraphs, which are not naturally captured in the basic message-passing framework.
3.2. Commute Time Computation
Based on the standard Markov chain theory, a useful tool to study random walk distances is the fundamental matrix (Al- dous & Fill, 2002). We first establish the following assump- tions required to support the theorem.
Assumption 3.1. The digraph G is irreducible and aperi- odic.
These two properties pertain to the Markov chain's 'sii's station- ary probability distribution æ (i.e., Perron vector) corre- sponding to the given graph. Irreducibility ensures that it is possible to reach any node (state) from any other node, preventing π from converging to O. Aperiodicity ensures that the Markov chain does not get trapped in cycles of a fixed length, thus guaranteeing the existence of a unique x. Existence and uniqueness of π facilitate deterministic anal- ysis and computation. For more intuitive understanding of the assumptions, give the sufficient conditions of digraph under the irreducibility and aperiodicity assumptions.
Proposition 3.2. A strongly connected digraph, in which directed path exists between every pair of vertices, is irre- ducible. A digraph with self-loops in each node is aperiodic.
Taking the digraph in Figure 1 as an example, a I-layer DirGNN defined in Eq. (1) can encode Ums fy and iy into the representation of Us while also capturing the direc- tionality of edges from these neighbors by using distinct aggregation functions for incoming and outgoing neigh- bors. It shows that DirGNN can capture the hitting time, as neighbors with lower hitting times, l(,,, vx), h(re, vy) and fu(m, 0z). are aggregated preferentially. However, DirGNN inherently focuses on unidirectional interactions and over- looks mutual path dependencies. Notably, a 1-layer DirGNN is insufficient for capturing the asymmetric interactions in- dicated by the paths from U/ and e2 returning to the central node 2; (gray areas). One potential approach to address this limitation is to stack additional message passing lay- ers to encompass the entire commute path between nodes, thereby capturing mutual path interactions. Nevertheless, this strategy is non-trivial because the commute paths vary considerably across different node pairs, complicating the determination of an appropriate number of layers. Addi- tionally, stacking multiple layers to cover these paths can introduce irrelevant noc-l information and lead to over- smoothing.
Given the above assumption, the fundamental matrix Z is defined as the sum of an infinite matrix series:
Z =
(p' (p'-JIn JII
Σ (P'-eT") ) (2)
t=0
where is the all-one column vector, then we have J = e-E is the all-one matrix, and II = diag(T) is the diagonal matrix of π.
Theorem 3.3. (Li & Zhang, 2012) Given Assumption 3.1, the fundamental matrix Z defined in Eq. (2) converges to:
(I- JI) JII,
where I is an identity matrix.
The hitting time and commute time G can then be ex- pressed as Z (Aldous & Fill, 2002) as follows:
h(u, v2) Z₁j Zuj
c(vi, 0;) h(v,, u))+ uz).
J
(4)
Goal
We expect to directly encode node-wise commute time into the node representations to accurately reflect the true interaction strength between adjacent nodes during neighbor aggregation, accounting for both forward and back-
However, directly calculating the complete fundamental matrix Z and the commute times for all node pairs is com- putationally expensive and yields dense matrix. Moreover,
3

---

Commute Graph Neural Networks
integrating the random walk distances computation, defined in Eq. (3) and Eq. (4), into the message passing framework is non-trivial, which concerns the scalability of the model.
the Weighted DiLap T:
(Ts): (IgDD)) =
Σ (GS)(s)e)) A
Σ (GS) BSEAAT
4. Commute Graph Neural Networks
T IIT
In this section, we present CGNN to encode the commute time information into message passing. We first establish the relationship between random walk distances and the digraph Laplacian.
(6)
Here we utilize the i-th element of the Perron vector π to quantify the structural importance of v, reflecting its eigen- vector centrality. This is based on the principle that a node's reachability is directly proportional to its corresponding value in the Perron vector (Xu et al., 2018). Therefore, x effectively indicates the centrality and influence over the long term in the graph. Ferron-Frobenius Theorem (Horn & Johnson, 2012) establishes that и satisfies Σ, ग. 1, is strictly positive, and converges to the left eigenvector of the dominant eigenvalue of P.
4.1. Digraph Laplacian (DiLap)
Contrary the traditional graph Laplacian, typically defined as symmetric positive semi-definite matrix derived from the symmetric adjacency matrix, our proposed Di is built upon the transition matrix to preserve the directed struc- ture. Specifically, the classical graph Laplacian -= D A is interpreted as the divergence the gradient of a signal on
4.2. Similarity- Graph Rewiring
an undirected graph (Shuman et al., 2013; Hamilton, 2020): given a graph signal s E R² (Ls); =GEN; Asy(s; sj)) Intuitively, graph Laplacian corresponds to the difference operator on the signal 8, and acts as a node-wise measure of local smoothness. In line with this conceptual foundation, we generalize the graph Laplacian to digraphs by defining the divergence of the gradient on digraphs with DiLap T:
Both the fundamental matrix defined in Eq. (3) and Weighted DiLap requires Assumption 3.1 to ensure the existence and uniqueness of the Perron vector æ,, conditions that are not universally met in general graphs. To fulfill the irreducibility and aperiodicity assumptions, Tong et al. (2020a) introduce a teleporting probability uniformly dis- tributed across all nodes. This method, inspired by PageR- ank (Page et al., 1999). amends the transition matrix to P Par > + (1 - 7) % where y E (0,1). P Per allows for the possibility that a random walker may choose non- neighbor node for the next step with probability of 1N2 This adjustment ensures that P is irreducible and aperi- odic, so it has a unique т. However, this approach leads to a complete graph represented by a dense matrix P Ppr. posing significant challenges for subsequent computational processes.
M Ts = =GDs, T= =Blia (Pry)oo. (oL,))E
B
(5)
where G is the gradient operator on graph signals, and D is the divergence operator. B E RNxM is an incidence matrix, where the dimensions represent nodes and edges, respectively. For edge indices {eI.... ,er} E. if e (vi, uz) E, then the k-th column of B corresponding to ek has +1 in row i and -1 in row j. diag (Pi)) M (v..)))R)) is a diagonal matrix whose entries are the transition prob- abilities corresponding to the edges in the graph. The de- tailed derivation of included in Appendix A. which illustrates how T functions as a measure of smoothness in directed graphs, taking into account their directional prop- erties. Although the structure of Di Lap depends the indices of edges and nodes, such as the ordering of edge transition probabilities in diag (Pij) (.))))))) the fol- lowing property holds (for proof, see Appendix A.2).
Rather than employing Ppr as the transition matrix, we in- troduce a graph rewiring method based on feature similarity to make given graph irreducible, while maintaining the sparsity. As outlined in Proposition 3.2, to transform the digraph into a strongly connected structure, it is essential that each node possesses directed path to every other node, To this end, we initially construct a simple and irreducible graph G' with all N nodes, then add all edges from G' to the original digraph G, thereby ensuring G's irreducibility. The construction of G' begins with the calculation of the mean of node features as the anchor vector a. Then we determine the similarity between each node and the anchor, sort the similarity values, and return the sorted node indices, denoted as E R.N:
Proposition 4.1. DiLap T is permutation equivariant w.r.t. node indices and permutation invariant w.r.t edge indices.
Given the Laplacian operator's role in assessing signal smoothness throughout the graph, it is essential to allocate greater weights to nodes of higher structural importance. This prioritization ensures that the smoothness at nodes cen- tral to the graph's 's structure more significantly influences the overall smoothness measurement. Thus, we further define
a = Σ X N
W = c.)(a,X,), S = arg sort (w, H
(7)
where cos(a, X,) the cosine similarity between node fea-
4

---

Commute Graph Neural Networks
Theorem 4.3. Given G, the hitting time and commute time from vú Vj on G can be computed follows:
Add edges to
T
h(0,, 03)
11
jj
[T
Figure 2: The sorted node indices in f2 are connected one by one with undirected edges to construct G', then adding all edges from G' to G to generate G.
T
T
c(v,, U/)
31
Jj
75
tures of u, and a, and ar) yields the indices of nodes that sort similarity values {4s [/ We then connect the nodes one by one with undirected (bidirectional) edges fol- lowing the order S to construct G", as shown in Figure 2. Given that G' is strongly connected, adding all its edges into G results in a strongly connected digraph G. which is irreducible. To achieve aperiodicity, self-loops are further added to G. This rewiring approach satisfies Assumption 3.1 and maintains graph sparsity. Additionally, adding edges between nodes with similar features only minimally alters the overall semantics of the original graph. Based on and its corresponding P. B, and II, we have the deterministic Weighted Di Lap
Then we can derive the matrix forms of the hitting time H and commute time C' as per Eq. (9):
H - (e (T e C 7 CH++
- T o (
(10)
where @ denotes Hadamard product, and & outer product. Hij and Cyy correspond the hitting and commute time from v to By respectively. The computation of commute times via D DiLap, in contrast to the method delineated in Theorem 3.3, is primarily motivated by efficiency concerns. Specifically, Eq. (3) necessitates the inversion of a dense matrix with complexity ((N3), whereas our Di DiLap-base method hinges on computing the pseudoinverse of a sparse matrix T. The pseudoinverse of T can be efficiently deter- mined using SVD, Given the sparse nature of T, we can employ rell-established techniques such as the randomized truncated SVD algorithm (Halko et al., 2011; Cai et al., 2023), which takes advantage of sparsity, to reduce the time complexity to (gg where |E| denotes the number of edges reflecting the sparsity (See Appendix A.4). Next, we present CGNN based on C.
Note that graph rewiring is a common strategy in graph analysis research. For instance, (Attali et al., 2024) rewires graphs to eliminate negatively curved edges and thus alle- viate over-squashing, while (Rubio-Madrigal et al., 2025) modifies the graph to enlarge the spectral gap and, in turn, adjust community structure for the same purpose. con- trast, we rewire the graph to ensure irreducibility and aperi- odicity, which guarantees that commute times are uniquely and deterministically defined. Hence, both the motivation and the objective of our approach differ fundamentally from previous work.
Connection with Over-squashing Commute time has been used to analyze the cause of over-squashing (Di Gio- vanni et al., 2023; Armaiz-Rodrigue et al., 2022), and ex- tending the analytical framework to digraphs a promising direction. While our work primarily focuses on using com- mute time encode the directional strength of relationships between nodes, rather than studying the over-squashing problem, we still see two ways that method might en- hance over-squashing analysis: 1) Direction- Aware Jaco- bian: Di Giovanni et al. (2023) model over- wee--squshing with a symmetric Jacobian suitable for undirected graphs. In contrast, our model captures the directionality edges, al- lowing us to construct an asymmetric Jacobian for more targeted analysis in digraphs. 2) Quantifying "Long Com- mutes": while previous over-squashing work identifies that over-squashing tends to occur between nodes that are far apart, it does not quantify exactly how large commute time triggers over-squashing Our method, anchored by the DiLap-based commute time computation can explicitly quantify these distances.
4.3. From DiLap to Commute Time
Given the Weighted D DiLap T, we can unify the commute time information into the message passing by building the connection between T and the fundamental matrix Z:
Lemma 4.2. Given the Weighted DiLap is defined as MBdiaa matrix Z of G can be solved by:
rewired graph G
M
{
(EE (
TT. Then the fundamental
z -
(8)
where the superscript means Moore-Penrose pseudoin- verse of the matrix.
Leveraging Lemma 4.2 and using Eq. (4), we can further compute the hitting times and commute times in terms T with the following theorem.
5

---

Commute Graph Neural Networks
4.4. CGNN
CE &NNN quantifies the strength of mutual relations be- tween node pairs in the random walk context. Notably, smaller values in C correspond to stronger mutual reachabil- ity, indicating stronger relations between node pairs. Thus, C is a positive symmetric matrix, and the node proximity matrix can be expressed as = exp(- Since the directed adjacency matrix A represents the outgo- ing edges of each node, A therefore accounts for all incom- ing edges. Then we have Cour- A @ C and (tn = A @ represent the proximity between adjacent nodes under out- going and incoming edges, respectively. We further perform row-wise max- nux-aaomalization on Comn and Çin to rescale the maximum value in each row to 1. Given the original graph G as input, we define the E-th layer of CGNN as:
IAt- Aaaa-aaa AT
500
400
Discance
300
200
A
A
1
100
1M
12
Chameleon
Scuree
Dataset
Dataset
(a) Hcterophilic graph.
(b) Homophilic graph.
Figure 3: Distance between M and A, and between M and C.
on the remaining ones, validating the superiority of CGNN. We provide more observations as follows. Firstly, while non- local GNNs have the potential to cover the commute paths between adjacent nodes by stacking multiple layers, they do not consistently outperform general, shallow GNN models. It suggests that coarsely aggregating all nodes in commute paths is ineffective. The reason is that deeper models may aggregate excessive irrelevant information for the central node. Our goal is to encode mutual relationships between adjacent nodes by considering their commute times. Aggre- gating all nodes along the entire path introduces excessive information about other nodes unrelated to the direct rela- tionship between the target nodes. Secondly, GNNs tailored for digraphs do not seem to bring substantial gains. Our results show that with careful hyper-parameter tuning, gen- eral GNNs can achieve results comparable to, or even better than, some of GNNs tailored for digraphs (DiGCN, MagNet and DiGCL), as evidenced in the Squirrel, Chameleon, and AM-Photo datasets. Thirdly, CGNN achieves saae-of-theeaat results both homophilic and heterophilic digraph bench- marks. Notably, DirGNN also performs comparably het- erophilic graphs (e.g., Squirrel and Chameleon), confirming the findings of Rossi et al. (2023) that distinguishing edge directionality during message passing enables the central node to adaptively balance information flows from both het- erophilic and homophilic neighbors, effectively mitigating the impact of heterophily. Moreover, CGNN, enhanced version of DirGNN, further improves performance these graphs by effectively incorporating commute times to re- fine the strength of relationships between nodes, enhancing model robustness under heterophily.
(E)
(2)
(f h h : E x(²))
mi Aggin
mo.ott Agguut
(f)
(2)
({ {Tom -hi n/("") Us E &Nggm))
(II)
h (1) Comb (1) (n (1 . m. mi,ou)
where Aggin (.) and Agg are mean aggregation func- tions with different feature transformation weights, and (o is mean operator. Within each layer, the in- fluence of by on the central node U/ is modulated by the commute-time-batt proximity Ć based on the edge direc- tionality. The pseudocode of CGNN is shown in Algorithm 1.
Complexity Analysis The randomized truncated SVD to compute Tt is (gl El) where is the required rank, and the message passing iteration has the same time complexity as DirGNN with El()) Therefore, the overall time complexity of CGNN is O(Ldd + 4)) El). In practice, q typically set to rendering the time complexity effee- tively linear with respect to the number of edges |E]_ In GNN domain, models with complexity less than ((N2) are generally considered feasible by researchers (Wu et al., 2020). Given that real-world networks are often extremely sparse, i.e. |E| < N CGNN demonstrates its feasibility as a model within the GNN family.
5. Experiments
We conduct extensive experiments to evaluate the effec- tiveness of CGNN on eight digraph datasets. Experimental details and data statistics are provided in Appendix C.1 and Appendix C.2.
To illustrate this, we further examine the relations between commute-time-bart proximity and label similarity along edges. As shown in Eq. (11), we use commute-tinn timet----ee---eedd proximity C to weigh the neighbors during neighbor aggre- gation. Then we define label similarity matrix M where My = 1 if vy E NN, and y = yy; otherwise Mi = O. Essentially, M extracts the edges connecting nodes with the same classes from the adjacency matrix A. Thus a higher value of ||M (A + A TT] indicates more pronounced
5.1. Overall Results and Analysis
Table reports the node classification results across eight digraph datasets. Our method CGNN achieves new of
are- results on 6 out of 8 datasets, and comparable results
6

---

Commute Graph Neural Networks
Table I: Node classification results. We highlight/underinee the best/second-best method. For general GNN and non-local GNN baselines, we conduct experiments on both symmetrized versions and their directed counterparts, reporting better results from these two settings. 00M indicates out-of-memory. In Table 9 and Table 10 of Appendix D.1, we present detailed experimental results for both directed and undirected settings of all available baselines.
Method
Squirrel
Chameleon
Citeseer
CoraMI.
AM-Photo
Snap-Patents
Roman-Empire
Arxiv-Year
GCN
52.43
67.96-182
66.03+1 88
70.92+t0.9
88.52+047
51.02+0.6
73.69=0.4
46.02+026
GAT
40.72
60.69=1.8 1199
65.58 1939
72.22+t0.57
88.36+1.25
OOM
49.18
45.30+o2s
GraphSAGE
41.61+0.74
62.01
66.81+118
14.16+1..5
89.71 +0.57
67.45
86.37
55.43+a7s
APPNP
+1.91
45.37 10 1.62
66.90
70.31 +0.67
87.43
51.23
72.96
50.31 +0.42
MixHop
1..80
60.50_2.53
26.0092200
15.89
87. 37.17
41 41.22++019
50.7620.14
45.30
GPRGNN
10.56
66.31 22.05
6..74
73.31
90.23+0.34
40. +0.00
64.85+0.27
45.07=021
GCNII
38.47
63.86
58.32++199
64.84
83.40+0.79
48. 48.09
74.27
57.36+0017
DGCN
37.16+1.72
50.77
66.37+1198
75.02++0.0
87.74+1.02
OOM
51.92+t043
OOM
DiGCN
33.44++2.0
50.37 44.31
64, +1.79
77.03
08.66+0.51
OOM
52.71 +0.32
48.37 +019
MagNet
39.01
58.22
1040
76.32.0010
86.801..8
OOM
88.07.0.21
60.29 1027
DUPLEX
57.60#6..s
61.25=004
67. 7777
72.26
87. 800
66.54
79.02+0..
64.37+027
DiGCL
35.82
56.45
67.42
77.53
89.41 +0.11
70.65
87.94+t0.1
63. 63.10 10
DirGNN
75.19
19.11-2.28
66.57
+5.33++0.2
88.09+0.6
73.95+a.u5
91.23
64.08 +0.66
CGNN
77.83+1.52
79.62-233
71.59
77.08+0.54
90.42++0.0
72.89+0.4
92.87=0.45
66.16=0.32
negative impact of heterophily on the model's performance On the other hand, we compute II- (Cutt >|2 to eval- uate the efficacy of C in filtering heterophilic information. The closer (ein + (ouN) is to M,, the more effectively it aids the model in discarding irrelevant heterophilic information. Figure visually demonstrates these relationships. We ob- serve that in heterophilic datasets, the commute-time-aase proximity matrix (Ctn + C aligns more closely with the label similarity matrix M than (A A It indicates that C effectively filters out irrelevant information during mes- sage passing by appropriately weighting neighbors, thereby explaining CGNN's 'ssei superior performance on heterophilic graphs as well as its strong results on homophilic graphs.
CCou)
APPMP
APPNP GPRENN
70
GPRGNN
GCMI
GCMI
DICC
86
DCCN
DICCK
DIGGN
50
Maglet
DICCE
Maghat
DIG.C
CONN
CGNN
34
30
120
120
140
150
180
200
100
120
140
160
150 200
Runninng Time (2)
Running Time
(a) Squirrel
(b) AM-PPhote
Figure 4: Accuracy vs. running time.
dencies.
In conclusion, in networks like citation networks where mu- tual relationships inherently do not exist, applying commute times is unnecessary. Our model is particularly effective in networks like webpage networks and social networks examples being Squirrel and AM-Photo where mutual relationships are prevalent. For instance, in a social net- work, an ordinary user may follow a celebrity, creating a short path to the celebrity. However, the reverse path from the celebrity back to the user might be considerably longer. For such cases, considering mutual relationships based on commute times can provide a more accurate description of node relationships.
Application scope analysis. Can commute times always enhance message passing on directed graphs? To answer this, we analyze the scope of use for CGNN based on Table For example, on the Snap-Patents and CoraMI. dataset, we observed that adding commute time-based weights during message passing did not significantly enhance performance. Now we can analyze the reason from the perspective of dataset. CoraML. is a directed citation network where nodes predominantly link to other nodes within the same research area. However, in such networks, reciprocal citations be- tween two papers are impossible due to their chronological sequence. Consequently, mutual path dependencies do not exist, and thus, incorporating commute times to adjust neighbor weights might (slightly) hurt performance. A sim- ilar situation exists with the Snap-Patents dataset, where each directed edge represents a citation from one patent to another, again indicating the absence of mutual path depen-
5.2. Efficiency Comparsion
Figure 4 compares the accuracy of different models along with running times. Despite the additional computational load of calculating commute- -ise--iee--ddddd proximity, the re-
7

---

Commute Graph Neural Networks
sults show that CGNN provides the best trade-off between effectiveness and efficiency. In particular, on the Squirrel dataset, CGNN has the third-fastest calculation speed while yielding accuracy nearly double that of all other methods. On AM-Photo, CGNN achieves the highest accuracy while maintaining moderate efficiency.
Table 3: Accuracy and running time (s) of CGNN and ppr-
Squirel
Chameloon
Citseer
CoraMi
AM-Photo
Method
Ace.
Time
Ave.
Time
Ace.
Time
Ace.
Time
Ace.
Time
COKN
77.83
99.25
79662
115.77
71.59
89.25
17.08
125.20
90.42
124.17
68.
257.84
71.69
253.05
68.59
137,82
76.23
192.00
86.52
203.04
5.3. Component Analysis
edges into undirected ones by adding their reverse counter- parts. This process results in a symmetric adjacency matrix, denoted as Aymm- Subsequently, the commute time calcu- lated based on the transition matrix derived from Asym- We refer this variant as 'CGNNaym' Table 4 shows the accuracy of CGNN and CGNNeym on three datasets. We find that edge direction can significantly influence the prediction accuracy for our model.
Comparison between graph rewiring and PPR. In Sec- tion 4.2, we construct a rewired graph G based on fea- ture similarity to guarantee the irreducibility and aperiodic- ity. This approach introduces at most two additional edges per node, specifically targeting those with the highest fea- ture similarity, while minimally altering the original graph structure to preserve semantic information. To investigate changes in commute times before and after rewiring, for the original graph, we use its largest connected component, removing absorbing nodes (i.e., nodes without outgoing edges) to ensure that we can compute meaningful and de- terministic commute times. We denote the average nor- malized commute time for the original graph Corigi For the rewired graph, we directly compute the commute time and denote this average normalized value as Crew. We then use 5 - to quantify the changes, which can ||corall
Table 4: Impact of directed structure.
Squirrel
CoraML
AM-Photo
CGNN
77.83
77.08 71.29
90.42
CGNNaym
72.37
88.53
Impact of the SVD rank q. To efficiently compute the pseudoinverse of T and obtain the fundamental matrix, we employ a randomized truncated SVD algorithm with rank g, detailed in Appendix A.4. We perform an ablation study to analyze the influence of the SVD rank g across three datasets of varying sizes in Table 5. The results indicate that increasing q beyond certain point does not yield continu- ous performance gains and incurs additional computational cost. Our findings suggest that setting q = 5 or 7 is optimal, as a small rank is sufficient for nodes to capture neighbor relationship strengths.
be intepretated as the proportion of commute information changed in the original graph. As shown in Table 2, the graph rewiring method can effectively preserve the original commute times of the graph.
Table 2: Changes in commute times before and after rewiring.
CoraML
CiteSeer
Chameleon
Roman-Emp Empire
0.03280
0.028746
0.00157
0.06242
Table 5: Impact of q.
In contrast, the classic PageRank transition matrix, defined as pr = 7P (1 - 7) N.
AM-Photo
Snap-Patent
Arxiv-Year
>> achieves similar objective but results in completely connected graph Gyr. However, this approach tends to overlook the sparse structure of the original graph, which may alter the semantic information in the graph. Additionally, computing commute times using a dense transition matrix incurs a high computational cost. To validate the effectiveness of the rewiring approach over the PPR method, conduct experiment where G is replaced with Ger in the computation of commute-time- based proximity. We denote this variant as 'CGNN and the results of accuracy and efficiency are reported in Table 3. The findings reveal that the PPR approach is suboptimal in terms of both accuracy and efficiency, thereby underscoring the effectiveness of our rewiring-baat approach.
3
88.36
71.53
64.20
5
90.42
72.89
66.16
7
90.19
73.01
66.21
10
90.37
72.97
66.45
Impact of rewiring on graph structure To explore how the rewiring procedure only minimally alters the overall semantics of the original graph, we define edge density as 8 M Mus. where Muax the maximum possible number of edges (N2 for both G and G) in the graph and M is the actual number of edges. We denote the edge density of the original graph G as ô and that of the rewired graph G as ő. Thus, the change of graph density after rewiring can ă-ô be represented as A = 5 E (0, 1), the smaller A indi- cates that the less effect of our methods on graph density, In the Table we calculate on AM-Photo, Snap-
Directed ys. Undirected To validate the critical role of directed structures in our model, we transform all directed
8

---

Commute Graph Neural Networks
and Arxiv-Year datasets. The results reveal that on the AM- Photo dataset, graph rewiring increases density by 10.3%, while on the Snap-Patent and Arxiv-Year datasets, the in- creases are only 6.7% and 3.2% respectively. These findings demonstrate that our rewiring method generally has a mod- est effect on graph density.
spectral properties of the digraph by performing spectral analysis based on the digraph Laplacian proposed by Chung (2005). Koke & Cremers (2024) introduce holomorphic filters as spectral filters for digraphs, and investigate their optimal filter-bank. MagNet (Zhang et al., 2021) and its extensions (Lin & Gao, 2023; Fiorini et al., 2023) utilize the Hermitian
magnetic Laplacian to derive a complex- matrix to encode the asymmetric nature of digraphs. Spatial GNNs also offer natural approach to capturing directed structures. Graph (Hamilton et al., 2017) allows for controlling the direction of information flow by considering in-neighbors or out-neighbors separately. DirGNN (Rossi et al., 2023) further extends GraphSAGE by segregating neighbor aggregation according to edge directions, offer- ing more refined method to handle the directed nature of graphs. DUPLEX (Ke et al., 2024) utilizes Hermitian adja- cency matrix decomposition for neighbor aggregation and incorporates dual GAT encoder for modeling directional neighbors. Transformer-based methods capture directed structure by specific positional encoding modules, such as directional random walk encoding (Geisler et al., 2023) and partial order encoding (Luo et al., 2024).
Table 6: Changes in graph structure before and after rewiring.
AM-Photo
Snap-Patent
Arxiv-Year
0.103
0.067
0.032
6. Related Work
6.1. Digraph Laplacian
While the Laplacian for undirected graphs has been exten- sively studied, the area of Laplace operator digraphs remains underexplored. Chung (2005) pioneers this area by defin- ing a normalized Laplace operator specifically for strongly connected directed graphs with nonnegative weights. This operator is expressed as I z1/2pa 1/2 1/2p">"/2 Key to this formulation is the use of the transition probability operator P and the Perron vector with the operator being self-adjoint. Building on the undirected graph Laplacian, Singh et al. (2016) adapt this concept to accommodate the directed structure, focusing particularly on the in-degree ma- trix. They define the directed graph Laplacian as Dn A,
7. Conclusion
Identifying and encoding asymmetric mutual path dependen- cies in digraphs is essential for accurately representing real relationships between entities. In this work, we utilize the concept of commute time to assess the strength asymmet- ric relationships in digraphs and introduce CGNN to enhance node representations. To achieve this, we propose D Lap, novel Laplacian formulation derived from the divergence of the gradient of signals on digraphs, along with an ef- ficient computational method for deterministic commute times. By integrating commute times into GNN message passing, CGNN effectively harnesses path asymmetry in di- graphs, significantly improving learning performance, as validated through extensive experiments.
N where D.n diag ((dm) fi=1) represents the in-degree ma-
trix. Li & Zhang (2012) uses stationary probabilities of the Markov chain governing random walks on digraphs to define the Laplacian as अ (I P) - which underscores the importance of random walks and their stationary dis- tributions in understanding digraph dynamies. Hermitian Laplacian (Furutani et al., 2020) consider the edge direction- ality and node connectivity separately, and encode the edge direction into the argument in the complex plane. Diverging from existing Laplacians, our proposed DiLap is grounded in graph signal processing principles, conceptualized as the divergence of signal's s gradient on the digraph. It encom- passes the degree matrix D preserve local connectivity, the transition matrix P to maintain the graph's directed structure, and the diagonalized Perron vector II, captur- ing critical global graph attributes such as node structural importance, global connectivity, and expected reachabil- ity (Chung, 1997).
Limitations and Future work CGNN'S primary limitation is its memory overhead. The commute time matrix C is dense by definition, incurring quadratic memory complexity relative to the number of nodes. A promising direction for future study is to compute and maintain commute times locally rather than globally. By restricting computations to each node's immediate neighborhood within limited number of hops, we may substantially reduce the memory footprint while still capturing the essential structural infor- mation needed for effective message passing.
6.2. Digraph Neural Networks
A Acknowledgements
To effectively capture the directed structure with GNNs, basetral-based methods (Zhang et al., 2021: Tong et al., 2020a;b) have been proposed to preserve the underlying
The research was supported in part by the Shenzhen Basic Research Fund (Grant No. SSYJ2024120211002555 W.
9

---

Commute Graph Neural Networks
Zhuo and H. Yu were supported by the Ministry of Educa- tion, Singapore, under its Academic Research Fund Tier (RG101/24); the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No. AISG2-RRP-220--019) X. Li was supported by Institute of Information Commu- nications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-
2021. URL httpttttt///ccc..... pettps://ppereeteee hwtp///ppprreeeeeeeeeeeee wetiiiewwweeeeeeeeeeee. www.:nettoooonne forum? id=n6j17fixr2
Chung, F. Laplacians and the cheeger inequality for directed
graphs. Annals of Combinatorics, 9(1):1-19, 2005.
Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
00445087).
Cross, R., Borgatti, S. P., and Parker, A. Beyond answers: Dimensions of the advice network. Social networks, 23 (3):115-235, 2001.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Di Giovanni, F., Giusti, L.. Barbero, F., Luise, G., Lio, P.. and Bronstein, M. M. On over-squashing in message passing neural networks: The impact of width, depth, and topology. International Conference on Machine Learning, pp. 7865-7885, PMLR, 2023.
References
Fiorini, S., Comiglio, S., Ciavotta, M., and Messina, E. Sig- manet: One laplacian to rule them all. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7568- 7576, 2023.
Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Gal- styan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In In- lernational Conference on Machine Learning, pp. 21-29. PMLR, 2019.
Furutani, S., Shibahara, T., Akiyama, M., Hato, K., and Aida, M. Graph signal processing for directed graphs based on the hermitian laplacian. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzhurg, Germany, September 16-20, 2019, Proceedings, Part I, pp. 447- 463. Springer, 2020.
Aldous, D. and Fill, J. Reversible markov chains and random walks on graphs, 2002.
Arnaiz-Ren Rodrii-Z A., Begga, A., Escolano, F., and Oliver, N. M. DiffWire: Inductive Graph Rewiring via the Lovász Bound. In Proceedings of the First Learning on Graphs Conference, Proceedings of Machine Learning Research. PMLR, 2022.
Geisler, S., Li, Y., Mankowitz, D. J., Cemgil, A. T. Günnemann, S., and Paduraru, C. Transformers meet directed graphs. In International Conference on Machine Learning, pp. 11144-11172 PMLR, 2023.
Attali, H., Buscaldi, D., and Pernelle, N. Delaunay graph: Addressing over-squashing and over-smoothing using de- launay triangulation. In Forty-first International Confer- ence on Muchine Learning, 2024.
Halko, N., Martinsson, P.-.., and Tropp. J. A. Finding
structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217-285 2011.
Bojchevski, A. and Günnemann, S. Deep gaussian em- bedding of attributed graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv: 1et.::777.0811111 2017.
Hamilton, W. L. Graph representation learning. Morgan & Claypool Publishers, 2020.
Hamilton, W. L., Ying, R., and Leskovee, Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 1025-1035, 2017.
Cai, X., Huang, C., Xia, L.,, and Ren, X. Lightgel: Simple yet effective graph contrastive learning for recommenda- tion. arXiv preprint orXiv:2302.068 230.08899, 2023.
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 1725-1735, PMLR, 2020.
Horn, R. A. and Johnson, C. R. Matrix analysis. Cambridge university press, 2012.
Ke, Z., Yu, H., Li, J., and Zhang, H. DUPLEX: Dual GAT for complex embedding of directed graphs. In Forty- first International Conference on Machine Learning, 2024. URL https: h //wperevieeeweeeeeeeeeeeeeeeeeee net/ forum? i dd=M3uvAgDKOL.
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations,
10

---

Commute Graph Neural Networks
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Sen, P., Namata, G., Bilgic, M., Getoor, L.,, Galligher, B., and Eliassi-Rad, T. Collective classification in network data. Al magazine, 29(3):3393,, 2008.
Kliepera, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personal- ized pagerank. In International Conference on Learning Representations (ICLR), 2019.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1 1.05668, 2018.
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. The emerging field of signal processing on graphs: Extending nigh-dimensional data analysis to networks and other irregular domains. JEEE signal processing magazine, 30(3):83-98, 2013.
Koke, C. andd Cremers, D. Holonets: Spectral convo- lutions do extend to directed graphs. In The Twelfth International Conference on Learning Representations, 2024. URL https::////.. ptattps://operrevviiii n forum? id Ed-EhmEwfavOi
Singh, R., Chakraborty, A., and Manoj, B. Graph fourier transform based on directed laplacian. In 2016 Interna- tional Conference on Signal Processing and Communica- tions (SPCOM), pp. 1-5. IEEE, 2016.
Li, Y. and Zhang, Z.-L. Digraph laplacian and the degree of asymmetry. Internet Mathematics, 8(4):381 4010, 2012.
Lin, L. and Gao, magnetic framelet-based convolutional neural network for directed graphs. ICASSP 2023-2023 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2023.
Tong, Z., Liang, Y., Sun, C., Li, X., Rosenblum, D., and Lim, A. Digraph inception convolutional networks. Advances in neural information processing systems, 33, 2020a.
Luo, Y., Thost, V., and Shi, L. Transformers over directed acyelic graphs. Advances in Neural Information Process- ing Systems, 36, 2024.
Tong, Z., Liang, Y., Sun, C., Rosenblum, D. S., and Lim, A. Directed graph convolutional network. arXiv preprint arXiv:2004 2004:0004.3999 13970, 2020b.
Page, L.., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Tong, Z., Liang, Y., Ding, H., Dai, Y., X., and Wang, C. Directed graph contrastive learning. Advances in neural information processing systems, 34:19580-19955 2021.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Qiu, R., Yin, H., Huang, Z., and Chen, T. Gag: Global attributed graph neural network for streaming session- based recommendation. In Proceedings of the 43rd Inter- national ACM SIGIR Conference on Research and Devel- opment in Information Retrieval, pp. 669-677 669-678, 2020.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph Attention Networks. International Conference on Learning Reprexentations, 2018. URL /tttps://openst id=rJXMpiXC2. accepted poster.
.nt// forrmm?
Rossi, E., Charpentier, B., Giovanni, F. D., Frasca, F., Günnemann, S., and Bronstein, M. M. Edge directionality improves learning on heterophilic graphs. In The Second Learning Gruphs Conference, 2023. URL https: //openreview weeiiiewweeeeeeeee / htr/m/ormmmmmmmmmm i d- Te00-44LEE 4LRBAMWFE..
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In International conference machine learning, pp. 6861- 6871. PMLR, 2019.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning sys- tems, 32(1):4-24, 2020.
Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale at- tributed node embedding. Journal of Complex Networks, 9()):naah014, 2021.
Rubio-Madrigal, C., Jamadandi, A., and Burkholz, R. GNNs getting comfy:
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In International confer- ence on machine learning, pp. 5453-5462 PMLR, 2018
Community and feature similarity guided rewiring. In The Thirteenth International Conference on Learning Representations, 2025.

---

Commute Graph Neural Networks
Zhang, X., He, Y., Brugnone, N., Perlmutter, M., and Hirn, M. Magnet: A neural network for directed graphs. Ad- vances in neural information processing systems, 34: 27003-27015, 2021.
Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Commute Graph Neural Networks
A. Proofs and Derivations
A.I. Derivation DiLap
The gradient operator maps signal defined on the nodes the graph to a signal on the edges. For a directed graph G and signal $ R.W on the nodes, the gradient Gs defined on the edges as:
(wrre))
Psy(s: 83)
(12)
for each directed edge (V,, U2) E E. This captures the difference in the signal between the source node e and the target node Vj.
The divergence operator D maps signal defined on the edges back to signal on the nodes. For a signal Gs RRM on the edges, the divergence at node is:
(D(Gs)); = Σ (G8)()))0))
Σ (g.)))))s)) UYEAT
(13)
EYEN?
This computes the "incoming" minus "outgoing" signal flow at each node. The digraph Laplacian DiLap T is then defined as the composition of the divergence and gradient operators the original signal
Ts = DGs
(14)
Eq. (12) and Eq. (13) demonstrate that the composed operator forming Di Lap effectively measures how the signal diverges from each node considering the graph's directionality. Therefore, analogous to the traditional Laplacian in undirected graphs, DiLap acts as a measure of smoothness specifically tailored for directed graphs.
To express T in matrix form, we initially define the incidence matrix E NxN which encapsulates both the connectivity and the directionality of the edges within the digraph:
+1, ek (Ui U2) Bis
1, e₁ (U), uz)
(15)
0, otherwise
where & {1..... .M} represents fixed edge indices, and each undirected edge is treated as comprising two unidirectional edges. Then We construct diagonal matrix representing the edge transition probabilities, denoted as diag (Po))o..
E MRM, where the principal diagonal elements are indexed according to the edge indices. Based
on the above definitions, the gradient operator can be represented diag (PP)) operator as D = B. Therefore, the DiLap becomes:
B and the divergence
T Bdiag (PNNOONEEEE))
B
(16)
A.2. Proof of Proposition 4.1
Proof. Let Quode NNN be node permutation matrix that reorders the nodes in G. The permuted incidence matrix be represented B' Qu B. Then have the permuted DiLap T
T B' B'diag (
B
(1..)))E
(QT B) diag (PD)eeL.))E)))
Tnndee)
(17)
Q TQ
Eq. (17) shows that is obtained by conjugating T with the node permutation matrix Quode- which means T' is T with its rows and columns permuted according to Quaie- Thus T is permutation equivariant up to relabeling of nodes.
13

---

Commute Graph Neural Networks
Let Qodge IR-x be edge permutation matrix that reorders the edges of G. The permuted incidence matrix can be rep- (Pis) (B..))EE
resented as B' = eudge and the permuted diagonal matrix diag (Piy)annessE)) Then we have the permuted DiLap T
Redgo
Quige
T B' diag (Po ( (EIN))E
) B
(BQggo))
) Q Oudgee diag
(P (o.,)))))
Qodgo) (Qelge B
(18)
Bdiag
(Pay)
B
T
Eq. (18) shows that ' remains unchanged under edge permutation when B and diag (Pi)) 1 (M.e))E) adjusted accordingly. Thus T is fully invariant to the ordering of edges.
A.3. Proof of Lemma 4.2
(TTE,,,,) P.j {
Proof. We first define the weighted out-transition matrix as F diag
Based on F, the weight Di Lap
T can be written as T = IIP. P can be expressed as:
P PF -
(19)
Since the transition matrix P row-stochastic, follows that P'J J. In light of Eq. (2) and considering that n stochastic, have ZJ 0nxn and II -I- FII =
Let - 3, J JIIS, and Z II ZII=S 5, we have J2 J. As x Z 0, have ZJ II ZJII = NNx and JZ = ONXN. Since TJ = ONXN. TJ = ONNN and JT= =NNN holds. Incorporating these into Eq. (3), we have:
+ J = (K + -
(20)
By post-multiplying Eq. (20) from the right by (KC + J), have:
I I- J ZK JK,
(21)
where JK = JIT (II (TI--
JIII = =ONXN- Then we have:
I-=
(22)
Similarly, by multiplying from the left, we establish that K.2 = I- Since JZ ONXN, ZK2 2. Furthermore, KJJ +)) have (ZK)T = ZK. Similarly, (KZ)T KZZ. These derivations satisfy the sufficient conditions for the MloorePPenrose pseudoinverse, such that
J.
ONX leads to KZK K. Considering the symmetry of the left part of Eq. (22),
2 = Kt
(23)
Finally, recovering 2 and as:
= TtM
(24)
which concludes the proof.
A.4. SVD for T
Given matrix T NxN, its Moore-Pennene Pwweeeeneeeeeuooionnnnneeoo pseudoinverse be directly computed with SVD-based method. Specifically, we first perform truncated SVD on T & V, where U, E Nxx and V, gxxx contains the first columns of U and V. Mn E _ is the diagonal matrix of largest singular values. It is a q-rank approximation of T. which holds that rank(R)= q. Then the Moore- Peorose pseudoinverse of T can be easily computed follows:
T UU--IV
(25)
14

---

Commute Graph Neural Networks
To leverage sparsity of ' to avoid ((N)) complexity, we adopt the randomized SVD algorithm proposed by (Halko et al., 2011; Cai al., 2023) first approximate the range of the input matrix with low-rank orthonormal matrix, and then perform SVD this smaller matrix:
Ú go ApproxSVD(T.o)) TSVD U UgS.V.
V q
(26)
where Üg. Eg and V. are the approximated versions of Ug. Egp. and qg Then the Moore-Penrose pseudoinverse of T can be computed by:
= U
(27)
The computation cost of randomized truncated SVD takes OggK), where K is the number of non-zero elements in T, so we have K = |Fl Thus, the sparsity degree of T can determine the time complexity of its Moore- Moore-Penrose pseudoinverse, which demonstrates the importance of Lemma 4.2.
B. Pseudo Code for CGNN
Algorithm 1 CGNN
Input: Digraph G (V, E, X); Depth L; Hidden size d'; Number of classes K
Output: Logits Y E ggNx
1: Compute the anchor a and node-anchor similarities to construct G' with Eq. (7),
2: Add all edges from G' to G to generate G.
3: Compute the Weight Dipap T for G with Eq. (6).
4: Compute R and its Moore- Penrose pseudoinverse with Eq. (8) and Eq. (27).
5: Compute the commute time matrix C with Eq. (10).
6: Compute the normalized proximity matrix C with Coer A o C and Či" A TOč.
7: for & E (1,... 1.} do
8: Layer-wise message passing with Eq. (11).
9: end for
10: H = (2))
11: Y Softmax (H).
C. Implementation Details
C.1. Experimental Settings
We provide performance comparison with 12 baselines including 1) General GNNs: GCN (Kipf & Welling, 2017),
GAT (Veličković et al., 2018), and GraphSAGE (Hamilton et al., 2017); 2) Non-local GNNs: APPNP (Klicpera et al., 2019). MixHop (Abu-El-Haija et al., 2019), GPRGNN (Chien et al., 20,1), and GCNII (Chen et al., 2020); 3) Digraph NNs: DGCN (Tong et al., 2020b), DiGCN (Tong et al., 2020a), MagNet (Zhang et al., 2021), DiGCL (Tong et al., 2021), DUPLEX (Ke et al., 2024), and DirGNN (Rossi et al., 2023). We evaluate the performance by node classification accuracy with standard deviation for 10 runs in the semi-supervised setting. For Squirrel and Chameleon, we use 10 public splits (48%/32%/205 for sainingg/alidaatooo//ssnngg) provided by (Pei et al., 2019). For the remaining datasets, we adopt the same splits (Tong al., 2020a; 2021), which chooses 20 nodes per class for the training set, 500 for the validation set, and allocates the rest to the test set. We conduct our experiments on 2 Intel Xeon Gold 5215 CPUs and NVIDIA GeForce RTX 3090 GPU.
C.2. Data Statistics
The datasets used in Section 5 are Squirrel, Chameleon (Rozemberczki et al., 2021), Citeseer (Sen et al., 2008), CoraML (Bo- jchevski & Günnemann, 2017), AM-Photo (Shchur et al., 2018), Snap-Patents, Roman -mmire, and Arxiv- Arxiv-Year (Rossi et al., 2023). We summarize their statistics in Table 7. homo ratio represents the homophily ratio, a metric proposed by Zhu et al. (2020). which is employed to gauge the degree of homophily within the graph. lower homo_ratio ratio signifies a greater degree of heterophily, indicating a higher prevalence of edges that connect nodes of differing classes.
15

---

Commute Graph Neural Networks
Table 7: Statistics of the datasets.
Dataset
N
E
# Feat.
# Classes
homo_ratio ratio
Squirel
5,201
217,073
2,089
5
0.22
Chameleon
2.277
36,101
2,325
5
0.23
Cora-ML
2,995
8,416
2.879
7
0.79
Cileseer
3,312
4,715
3,703
6
0.74
A.- Photo
7,650
238,162
745
R
0.83
Snup-Patents
2,923,922
13,9757911
269
5
0.22
Roman-Empire
22,662
44,363
300
18
0.05
Araiv Year
169,343
1,166,243
128
40
0.22
C.3. Hyperparameter Settings
For our model, we tune the hyperparameters based on the highest average validation accuracy. We utilize the randomized truncated SVD algorithm for computing the Moore-Penrose pseudoinverse of matrix R, setting the required rank & to for all datasets. The learning rate selected from {0.01, 0.005]. and the weight decay wd from {0, 5e 5, 5e - 4]. In the model architecture, the number of layers L vary among {1, 2, 3, 4, 5) and the dimension d' is selected from {32, 64, 128, 256, 512]. The comprehensive hyperparameter configurations for CGNN are detailed in Table 8.
Table 8: Hyperparameters specifications.
Dataset
Ir
wd
L
d'
Squirrel
0.005
0
5
128
Chameleon
0.01
0
128
CoraML
0.01
0
2
64
Citeseer
0.01
0
2
128
AM-Photo
0.005
0
2
512
Cnap-Patents
0.01
0
2
32
Roman-Emmn Empire
0.01
64
Arxiv- Year
0.01
5e
4
2
64
D. Additional Experiments
D.1. Detailed Experimental Results on Node Classification
Table 1 in Section 5 presents the results from experiments conducted all eight directed graph datasets. For each baseline, experiments were carried out both the original directed graph datasets and their undirected counterparts, which feature symmetrized adjacency matrices. The superior accuracy results from these two settings are reported in Table 1. This section provides a detailed exposition the experimental outcomes for these configurations in Table 9 and Table 10. is important to note that while GCN is traditionally spectral method suited only for undirected graphs, can be adapted to directed graphs by interpreting from a spatial perspective, specifically, by aggregating outgoing neighbors with the weight fd,d,"
This adaptation allows GCN to be applicable in both experimental settings. Additionally, APPNP, GPRGNN, and GCNII are spectral methods that require symmetrized adjacency matrices for spectral filters. Therefore, we only report their results under the undirected settings in Table For DirGNN and CGNN, the case of undirected graphs, these models degenerate GraphSAGE.
D.2. Sensitivity Analysis
We investigate the sensitivity of CGNN to key hyperparameters that influence its performance, specifically focusing on the number of layers L and the dimension of the hidden layer d'. We explore range of values for L, considering 21 4, 5). and for d', considering {32, 64, 128, 256, 512). From Figure 5, observe that we observe that CGNN achieves optimal performance with L 5 and d' 128 on Squirrel, and with L 2 and d' = 64 on CoraML. This suggests that deeper models are necessary to effectively aggregate valuable information in heterophilic graphs, whereas in homophilic graphs, leveraging local neighborhood information generally adequate.
16

---

Commute Graph Neural Networks
74.01
71.36
74.92
76.01
72.18
76.88
76.64
75.82
75.81
76.18
72.85
73.82
74.16
74.
71.99
76.99
77.08
76.24
76.15
74.22
74.20
74.19
74.64
74.51
76.13
76.66
76.84
75.52
76.55
73.81
73.15
73.89
73.38
75.62
74.11
74.56
75.83
75.83
75.74
74.88
72:10
72.11
72.88
3/
64
128 d'
256
5i2
128
256
512
(a) Squirrel
(b) CoraML
Figure 5: Sensitivity analysis on Squirrel and CoraML.
Table 9: Comparison of node classification accuracy between original directed graphs and their undirected counterparts Squirrel, Chameleon, Citeseer, and CoraMI..
Squirel
Chameleon
Citeseer
CoraML
Method
Dir.
Undir
Dir.
Undir.
Dir.
Undir.
Dir.
Undir.
GCN
52.43_am
51.932119
63.37
67. 67.962141
64.271156
66.0321
68. 68.731aa
70.92.1..
GAT
40.72
40.502147
60.69218
59.37
65.58
54.221a
72.22.1.1 22.20
GraphSAGE
35.19=a54
41.61
58 58.20+1.9
62.01=1.0
62.57+a71
66.81+133
74.16+1.5
72.98
MixHop
39.25=nm1
43 1448
60.50+255
10.15
56.09 +200
54.71 +0.50
61.20++..1 65.89+
DGCN
37.16
18.24
50.7+331
48.26-1197
66.37+193
+5.15
75.02+
73.1 Houss
DIGCN
33.44=2m
28.17
50.37
43.08
64.99
64.35
77.03
76.98 10000
MagNet
39.01=1.
35.20
58.22#237
55.46
65.04+s47
64.90=asi
76.32
76.29::0.a
DUPLEX
57.60
55.26
61.25
61.20
67.60
67.35
72.26
72.21 20.6
DIGCL
35.82
33.10
56.45
51.16:1a5
67.42
66.53
77.53
76.24
Table 10: Comparison of node classification accuracy between original directed graphs and their undirected counterparts on AM-P MM-Photo, Snap-Patents, Roman- EemnaneEmppre,,. and Arxiy- Year.
AM-Photo
Snap-Pater Patents
Roman-Empire Empire
Arxiv-Yed
Method
Dir.
Undir.
Dir.
Undir:
Dir.
Undir.
Dir.
Undir.
GCN
88.52
51.0210m a5. OOM
50.15
23.69
73.582087
46.02_gm
44.81
GAT
88.36
87 mm
OOM
49.18
43.37
45.30_mm
43.27
GraphSAGE
89.71 10:7
26.23
67. 17.45
60.10..m
86.37
84.26102
55.43
MixHop
27.17
85.50
40. 17..m
41.22
43.00
50.762m1
45.30
41 41.25
DGCN
87.74
86.53
OOM
OOM
51.92an43
40.50
OOM
OOM
DIGCN
88.66a051
87, 94.
OOM
OOM
22.7
50.43gm21
28.37
47.26
MagNet
86.80
85.2 1::0
0OM
OOM
88. 88.072am7
82,99
60.29
55,25
DUPLEX
19
87,80 87.80
66.54gmm 64.92aam
79.02aum 77.64
64.37
12an1s
DIGCL
89.41 2011
87.36
70.65
68. 68.624mo
87. 87.94
24
63.10
59.02.sm
17


Reviews:
[{"review_id": "2vkEoyzx9w", "reviewer": "Reviewer_9WJX", "summary": "This paper proposes a novel method for learning on directed graphs. The authors argued that it is important to preserve a notion of mutual closeness in directed graphs via commute time, and introduced a method to compute/approximate this efficiently. They then encode this information into the design of message passing blocks in a directed graph neural network. Experimental results demonstrate the effectiveness of the proposed method, and detailed analyses are carried out to understand its behaviour.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Alternative ways of using the commute time in designing a directed GNN, e.g., regularisation or a non-MPNN?**\n\n**A1**: We appreciate your suggestion. While alternative approaches like incorporating commute time as a regularization term or exploring non-MPNN frameworks are interesting thoughts, our design was intentional to explicitly leverage commute time to **directly modulate** neighbor importance within the message-passing, thus ensuring nodes connected via shorter commute times **inherently** produce more similar embeddings. To rigorously evaluate your suggested alternative, we implemented a regularization-based variant ($CGNN_{reg}$). Specifically, we removed weighting coefficients ($\\widetilde{C}$) from Eq. (11) and instead introduced a commute-time regularization term ($\\lambda L_{CT}$) to be added to cross‐entropy loss $L_{CE}$. The new term, $L_{CT}$, penalizes pairs of nodes with long commute times if they end up with too similar representations, while encouraging similarity for pairs with short commute times by $L_{CT} = \\sum\\_{(u, v) \\in E} \\widetilde{C}\\_{uv}\\|\\|h_u-h_v\\|\\|\\_2^2$. We also included a simpler non‐MPNN baseline, denoted as $MLP_{reg}$ with $L_{CT}$ computed using MLP embeddings. Results are shown in the table below.\n||Chameleon|Roman|\n|-|-|-|\n|$MLP$|34.92|48.30|\n|$MLP_{reg}$|**45.69**|**52.98**|\n|$CGNN_{reg}$ |78.33| 90.62|\n|$CGNN$|**79.62**|**92.87**|\n\nIt shows, our original design choice not only aligns with the intended theoretical rationale but also empirically demonstrates superior performance -- weighting neighbors during message passing appears to be more effective than relying on the regularization‐based approach.\n\n**Q2: Should we consider the task-specific information in assessing importance?**\n\n**A2**: Thanks for raising this point. While we acknowledge that task-specific signals can indeed enhance targeted model performance, we'd like to **highlight our focus** is to demonstrate utilizing commute time is intentionally rooted in capturing fundamental structural properties inherent to graph topology—particularly critical in digraphs. The topology-driven nature of commute time allows our model to robustly encode essential structural relationships independent of specific downstream tasks, enhancing generalizability and interpretability. Moreover, commute time has the potential to serve as a complementary enhancement to existing task-aware methods like Label Propagation(LP). We used GCN‐LPA (Wang et al., TOIS 2021), an LP-based GNN, for evaluating. Integrating commute time improved accuracy by 2.74% on the Roman dataset. Thus, our method strategically leverages commute time to provide a solid structural foundation, while still enabling targeted task-specific refinements where advantageous.\n\n**Q3: Extending the use of commute time to analyze over-squashing in digraphs**\n\n**A3**: As you mentioned, commute time has been used to analyze the cause of over-squashing (OS), and extending the analytical framework to digraphs is a promising direction. While our work primarily focuses on using commute time to encode the directional strength of relationships between nodes, rather than studying the OS problem, we still see two ways that our method might enhance OS analysis: 1) **Direction‐Aware Jacobian:** The referenced paper models OS with a symmetric Jacobian suitable for undirected graphs. In contrast, our model captures the directionality of edges, allowing us to construct an asymmetric Jacobian for more targeted analysis in digraphs. 2) **Quantifying “Long Commutes”**: While previous OS work identifies that OS tends to occur between nodes that are “far apart,” it does not quantify exactly how large a commute time triggers OS. Our method, anchored by the DiLap‐based commute time computation, can explicitly quantify these distances. \n\n**Q4: Other ways to convert commute time into a similarity measure**\n\n**A4**: Yes, converting commute time into a similarity measure is analogous to turning distances into similarities, and multiple alternatives are possible. Beyond the negative exponential mapping (NEM) used in our paper, we also experimented with a shifted inverse function $\\frac{1}{C+\\epsilon}$. In empirical evaluations, NEM consistently performed better in continuous embedding spaces and boosted accuracy across datasets of various sizes. \n\n**Q5: Other Weakness: Utilisation of commute time is straightforward**\n\n**A5**: Although weighting neighbors by commute time appears straightforward, it provides an intuitive choice that allows us to isolate the effect of commute time while minimizing other interference factors. The primary innovation of our method lies not merely in the weighting scheme itself but fundamentally in identifying and exploiting the notion of mutual path dependencies. Moreover, demonstrating effectiveness via a intuitive implementation is the basic for exploring more sophisticated designs.\n\n**Line 138**:Thanks! We will correct the typo in revision.", "claims_and_evidence": "The main claims of the paper are that taking into account mutual closeness between a pair of nodes in a directed graph is beneficial in certain learning tasks, and commute time (or its approximation) is a useful tool to encode such relationship. I found this well supported both conceptually and empirically.", "methods_and_evaluation_criteria": "While the CGNN introduced in 4.4 is entirely reasonable, the commute time is used there only to moderate neighbour importance. I wonder whether the authors can think about alternative ways of making use of the commute time in designing a directed GNN, eg using it in a regularisation term to penalise message passing, or even defining a non-MPNN based framework (given that commute time is of general interest)?\n\nThe commute time is a measure entirely dependent on the graph topology, and importantly not on the specific downstream task. One may ask whether we should take into account the later in assessing importance of a node i to j and vice versa? \n\nThe Commute time has also recently been used to characterise the issue of over-squashing in undirected GNNs (see for example https://arxiv.org/pdf/2302.02941). I wonder if the authors can think about using commute time on directed graphs for similar analysis?", "theoretical_claims": "The theoretical results seem correct to me.", "experimental_designs_or_analyses": "Apart from an exponential function, have the authors tried other ways to convert commute time into a similarity measure? How stable is the exponential transformation?", "relation_to_broader_scientific_literature": "The key contribution of the paper is to take into account commute time in designing the message passing framework in a directed GNN. As far as I know this aspect is missing in previous literature.", "essential_references_not_discussed": "The references seem adequate to me.", "other_strengths_and_weaknesses": "Strengths:\n- the paper addresses a relatively under-explored but important problem in graph machine learning\n- the proposed approach is novel, well motivated, and technically sound\n- empirical results and analyses are comprehensive and convincing\n- the paper is well written and easy to follow\n\nWeaknesses: \n- while the analysis on commute time is sound and interesting, its utilisation in designing the directed GNNs is rather straightforward. One might argue this design seems a straightforward extension to existing methods such as DirGNN, however it is also understandable the authors choose to stick to the conventional message passing paradigm", "other_comments_or_suggestions": "Line 138: it looks like one of the h should be h(v_i, v_j)?", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5BAlmZJsSa", "reviewer": "Reviewer_951e", "summary": "The paper presents a new approach to embed commute time information when learning on directed graphs, for the task of node property prediction. It gives a nice introduction for commute time and a motivation for it. Then, the work proposes to approximate commute time information which is usually computed in O(|V||E|) at O(q|E|) where q is constant. Based on the tested benchmakrs embedding the commute time information achieve state-of-the-art results.\n\n## Update after rebuttal\n\nAlthough some issues were addressed in the authors’ response, others still remain unresolved. For example, why does q = 5 perform better than q = 10 in the ablation study, and how should a subgraph/neighborhood/sampled graph be chosen to compute B? It is also not clear from the response how the provided clarifications will be incorporated into the manuscript. For these reasons, I choose to maintain my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback. Our detailed responses follow.\n\n**Q1: Clarify how to maintain effectiveness given that the commute time information is partially preserved**\n\n**A1**: The effectiveness can be well maintained, as the proposed graph rewiring approach **does not drastically alter** the original graph’s structural semantics and commute time information. Specifically, our similarity-based rewiring method first generates a line graph  $G^\\prime$ (see Fig.2) based on feature similarity. Then merging $G^\\prime$ with $G$ adds at most two new edges per node, resulting in only minor changes to the original graph’s structural semantics. Moreover, since many real‐world graphs already link nodes with similar features, these newly added edges often overlap with existing ones, further narrowing the semantic shift caused by rewiring. Below, we verify that both the structural semantics and commute times are well maintained from two perspectives.\n\n**[Changes of structure]** To quantify the changes brought from graph rewiring, we define edge density as  $\\delta=\\frac{M}{M_{max}}$, where $M_{max}$ is the maximum possible number of edges and $M$ is the actual number of edges. We denote the edge density of the original graph $G$ as $\\delta$ and that of the rewired graph  $\\widetilde{G}$ as $\\widetilde{\\delta}$. Thus the change of graph density after rewiring can be represented as $\\Delta=\\frac{\\widetilde{\\delta}-\\delta}{\\delta} \\in (0,1)$, the smaller $\\Delta$ indicates that the less effect of our methods on graph density. The results in the below table reveal that on the AM-Photo dataset, graph rewiring increases density by 10.3%, while on the Snap-Patent and Arxiv-Year, the increases are only 6.7% and 3.2% respectively. These findings show our rewiring method has a modest effect on structure.\n||AM-Photo|Snap-Patent|Arxiv-Year|\n|-|-|-|-|\n|$\\Delta$|0.103|0.067|0.032|\n\n**[Changes of commute time]** Since we cannot directly compute the commute time on the original graph, rewiring is necessary. We extract its largest connected component and remove absorbing nodes to ensure meaningful commute times. Denoting the average normalized commute times for the original and rewired graphs as $c_{o}$ and $c_{r}$ respectively, we quantify the change using  $\\delta=\\frac{||c_o-c_r||^2_2}{||c_o||^2_2}$, representing the proportion of commute information altered. The results show that the rewiring method effectively preserves the original commute times.\n||AM-Photo|Snap-Patent|Arxiv-Year|\n|-|-|-|-|\n|$\\delta$|0.0227|0.0013|0.0125|\n\n**Q2: Ablation study on q**\n\n**A2:** We conducted an ablation study on the SVD rank q across three datasets of varying sizes. The results indicate that increasing q beyond a certain point does not yield continuous performance gains and incurs additional computational cost. Our findings suggest that setting q=5 or 7 is optimal, as a small rank is sufficient for nodes to capture neighbor relationship strengths.\n|$q$|AM-Photo|Snap-Patent|Arxiv-Year|\n|-|-|-|-|\n|3|88.36|71.53|64.20|\n|5|90.42|72.89|66.16|\n|7|90.19|73.01|66.21|\n|10|90.37|72.97|66.45|\n\n**Q3: Timing results for the Snap-Patents dataset**\n\n**A3:** Below are the timing results on the Snap-Patents dataset. Due to its large scale, models like GAT, DGCN, DiGCN, and Magnet ran out of memory. Among the remaining models, APPNP was the fastest at 10.75 mins, followed by GPRGNN at 13.89 mins, CGNN at 20.90 mins, and GCNII at 21.25 mins. Although CGNN requires extra commute time computation, it converges faster with only 80 training epochs are needed to achieve optimal validation accuracy.\n\n**Q4: How the hyperparameters (hps.) for DirGNN were tuned and whether they were optimized in a manner similar to those for CGNN**\n\n**A4:** We treat DirGNN and CGNN as separate models and tune their hps. independently. For datasets used in the original DirGNN paper, we follow its recommended settings; for other datasets, we carefully perform our own tuning. Because CGNN integrates commute‐time‐based weights, we cannot simply transfer DirGNN’s hps. For instance, on the Arxiv‐Year dataset, DirGNN uses a hidden dim of 256, whereas CGNN achieves optimal performance with 64.\n\n**Q5: Concern regarding the scalability on dense graphs, as the dimensions of the matrix B may impose limitations.**\n\n**A5:** Indeed, the dimensions of the matrix $B$ scales with the number of edges, which can become problematic for dense graphs. One could localize the commute time computation, approximating it within subgraphs or neighborhoods, rather than computing a global matrix. Another option involves applying sampling or sparsification to reduce edge density. We plan to explore these strategies in future work.\n\n**Q6: Other cmts. or suggs**\n\n**A6:** Thanks for pointing out these issues. In the revised manuscript, we have 1) corrected $h(v_i, v_k)$ to $h(v_i, v_j)$ on line 139; 2) added supporting references (Oversmoothing and non-local GNN papers) to lines 150–154; 3) modified the header on each page.", "claims_and_evidence": "Overall, the claims presented by the authors are convincing and clearly articulated. However, one point of concern remains. The manuscript motivates the importance of preserving the original commute time information. Yet, in practice, the proposed method introduces new edges from G′ to G, thereby altering the original commute time characteristics. Additionally, the commute time matrix is computed via a low-rank approximation of Z with rank q. It would be beneficial if the authors could clarify how their method maintains effectiveness given that the commute time information is only partially preserved.", "methods_and_evaluation_criteria": "I believe that the evaluation is ok. Please refer to my point in the strengths and weaknesses section about the hyperparameter tuning of DirGNN .", "theoretical_claims": "I did not find any issues with the proofs.", "experimental_designs_or_analyses": "I did not find any issues with the  experimental design or analyses.", "relation_to_broader_scientific_literature": "Developing symmetric matrices for directed graphs (to be used later by spectral techniques) such as the normalized directed Laplacian (Chung, 2005) is an exciting topic. Computing the commute time matrix in an efficient manner might contribute to this field of research.", "essential_references_not_discussed": "I believe that the authors covered most of the relevant literature. I would like to point out favorably the refence for the work of Chung (2005).", "other_strengths_and_weaknesses": "Strengths\n\nThe paper demonstrates that the proposed weighting based on commute time yields state-of-the-art results on several directed graph benchmarks.\n\nBy approximating the full commute time matrix via the matrix Z, the method offers a promising alternative to traditional, more computationally expensive approaches.\n\nThe proposed CGNN model is shown to be relatively efficient, with its time complexity being proportional to |E| when q is treated as a constant.\n\n\nWeaknesses\n\nThe paper does not include an ablation study on the parameter q. Given that increasing the rank q in the SVD could potentially yield more accurate commute time computations, such a study would help clarify whether the improvements in CGNN performance can be attributed directly to the enhanced commute time information.\n\nTiming experiments are reported for only a subset of datasets. In particular, it would be beneficial to see timing results for the Snap-Patents dataset, which has the largest number of nodes and edges.\n\nThe paper does not provide sufficient details on how the hyperparameters for DirGNN were tuned and whether they were optimized in a manner similar to those for CGNN.\n\nThere is a potential concern regarding the scalability of the method to dense graphs, as the dimensions of the matrix B may impose limitations.", "other_comments_or_suggestions": "The expression  ℎ(𝑣𝑖,𝑣𝑘) is repeated on line 139 and should be corrected.\n\nLines 150–154 discuss an aspect that either requires experimental validation or a citation to existing literature.\n\nPlease fix the title at the beginning of each new page, currently its \"Submission and Formatting Instructions for ICML 2025\".", "questions_for_authors": "I have no further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c1Frg9v4Q2", "reviewer": "Reviewer_V223", "summary": "This paper proposes a directed graph Laplacian based on the commute time between nodes. The paper also proposes a commute graph neural network model based on rewiring the graph to satisfy model assumptions and the Laplacian matrix. Experiments are conducted to validate the model's efficacy, together with ablation studies and discussions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful review. We have summarized all your feedback into 6 key questions and address below.\n\n**Q1: Why computing commute time rather than hitting time twice with different source and target nodes**\n\n**A1:** In fact, our method precisely aligns with your suggestion -- “computing hitting time twice with different source and target nodes.” By definition, commute time is the expected number of steps to travel from one node to another and return. It equals the sum of hitting times in both directions. Our approach also follows this principle. Specifically, the proposed efficient commute time computation method first computes the hitting time $H$ based on the DiLap as **Eq.(10)**. We then obtain commute time by summing up the mutual hitting time between source and target nodes with $C=H+H^T$. Thus, you can indeed view our method as computing hitting time for both directions and summing them to get commute time.\n\n**Q2: [Q2.1] Why the proposed rewiring is minimally altering the overall semantics; [Q2.2] Check whether omitting the graph structure or using a KNN graph is sufficient**\n\n**A2.1:** Our similarity-based rewiring method first generates a line graph $G^\\prime$ (see Fig.2) based on feature similarity. Then merging $G^\\prime$ with $G$ adds **at most two new edges per node**, resulting in only minor changes to the original graph’s structural semantics. Moreover, since many real‐world graphs already link nodes with similar features, these newly added edges often overlap with existing ones, further narrowing the semantic shift caused by rewiring. Table 9 in Appendix D.3 confirms that the rewiring does not substantially change the graph.\n\n**A2.2:** If we entirely ignore the graph structure and rely solely on node features, a natural baseline is MLP. The performance gap between MLP and our methods underscores the importance of structural information. Alternatively, omitting the original structure and reconstructing the graph as a KNN graph based solely on node features, yielding a KNN-GCN baseline. We compare the performance of MLP, KNN-GCN, and CGNN. Results are presented in https://anonymous.4open.science/r/Rebuttal-107E/Q1.md, which shows that CGNN achieves the best performance, confirming the crucial role of the original graph structure.\n\n**Q3: Proof for Prop 3.2**\n\n**A3:** Prop 3.2 states standard definitions from Markov chain theory, which are well-established in the literature (e.g., Aldous & Fill, 2002). Thus, this proposition serves to clarify these terminologies and does not require additional proof. We will add the reference in the revised manuscript.\n\n**Q4: Suggestion on including synthetic datasets**\n\n**A4:** While our paper prioritized experiments on established real-world datasets to highlight the practical significance of CGNN, synthetic datasets can indeed enhance the interpretability of CGNN. To address your request, we have now constructed a binary‐classification dataset of 3000 nodes (1500 per class), with features drawn from Gaussian distributions (class one: $N(0,1)$, class two: $N(3,1)$). Within-class edges are created with a 0.2 probability, while across-class edges have a 0.02 probability, with random edge directions. We predefine a commute‐path range of [2,7], thus capturing asymmetric node‐to‐node relationships. We apply CGNN on this graph and compute the Mutual Information between the central node and its neighbors with short commute times denoted as $\\alpha_s$, and with long commute times denoted as $\\alpha_l$. If the average $\\overline{\\alpha}_s>\\overline{\\alpha}_l$, it confirms that our model effectively preserves commute relationships. In our experiments, CGNN achieves $\\overline{\\alpha}_s=13.297$ and $\\overline{\\alpha}_l=6.552$, showing that CGNN does capture the intended asymmetry.\n\n**Q5: Performance of using DiLap as a graph shift operator (GSO) w/o commute times**\n\n**A5:** To treat DiLap $T$ as a GSO, we need to decompose it into $T_{in}$ and $T_{ou}$ based on incoming and outgoing edges. These sub-GSOs yield node embeddings $H_{in}$ and $H_{ou}$, which are then combined using a learnable weight. This variant called DiLapGNN allows us to evaluate DiLap-induced GNNs without commute times. Please refer to https://anonymous.4open.science/r/Rebuttal-107E for a performance comparison.\n\n**Q6: Justification on motivation**\n\n**A6:** Thank you for raising this concern. We respectfully note that other reviewers found our work clearly motivated—reviewer 951e stated it provides a \"nice introduction for commute time and a motivation for it,\" and reviewer 9WJX described our approach as \"novel, well motivated, and technically sound.\" Our motivation is twofold: practically, commute time naturally captures real-world asymmetries (e.g., celebrity-follower relationships) common in directed social networks. Algorithmically, current GNNs fail to model such directional asymmetry effectively (Sec. 3.1). These insights motivated us to leverage commute time to enhance directed GNNs.", "claims_and_evidence": "1. It is not clear at first glance why we should compute commute time rather than hitting time twice but with different source and target nodes, as these two are indeed related. The paper provides some sort of explanation only till the end of the main text.\n2. It is not clear why the proposed rewiring is only minimally altering the overall semantics at first glance. The explanation provided at the end of the ablation study sheds some lights, but this rewiring is highly dependent on feature similarity. The rewiring should only be helpful if features play a large role in the prediction. It is better to check whether even not using the graph structure at all, or using a generated graph merely based on feature similarity already suffices.", "methods_and_evaluation_criteria": "1. The datasets seem fine.\n2. It is not clear why the proposed rewiring is only minimally altering the overall semantics at first glance. The explanation provided at the end of the ablation study sheds some lights, but this rewiring is highly dependent on feature similarity. The rewiring should only be helpful if features play a large role in the prediction. It is better to check whether even not using the graph structure at all, or using a generated graph merely based on feature similarity already suffices.", "theoretical_claims": "There is no proof or reference of proof for Proposition 3.2.", "experimental_designs_or_analyses": "1. To better demonstrate the discussion claims, the authors could include some synthetic datasets.\n2. What is the performance of using DiLap directly as a graph shift operator without considering commute times?", "relation_to_broader_scientific_literature": "The paper is well connected to the wider literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is not very well motivated.", "other_comments_or_suggestions": "There should be a \"tp\" after $G'$ on the RHS of line 198.", "questions_for_authors": "1. What is the performance of using DiLap directly as a graph shift operator without considering commute times?\n2. It is not clear why the proposed rewiring is only minimally altering the overall semantics at first glance. The explanation provided at the end of the ablation study sheds some lights, but this rewiring is highly dependent on feature similarity. The rewiring should only be helpful if features play a large role in the prediction. It is better to check whether even not using the graph structure at all, or using a generated graph merely based on feature similarity already suffices. Could you check whether on these datasets, constructing graphs merely based on KNN graphs from features suffices?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3kMhGuSUAP", "reviewer": "Reviewer_jNKj", "summary": "The paper introduces Commute Graph Neural Networks (CGNN), a framework designed to improve learning on directed graphs by incorporating bidirectional path information.\n\nKey components of CGNN include a digraph Laplacian (DiLap) leveraging random walk transition probabilities, efficient computation of node-wise commute times via Markov chain theory, integration of commute times into GNN message passing for refined aggregation, and a feature-based graph rewiring strategy to ensure the digraph remains irreducible, aperiodic, and sparse.\n\nExtensive experiments demonstrate that CGNN outperforms existing methods, particularly in scenarios with important mutual relationships, while scaling efficiently with sparse graphs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful feedback. We've consolidated your comments into 8 questions and provided responses to each.\n\n**Q1: The definition of Moore–Penrose Pseudoinverse (MPP) in Lemma 4.2, and a detailed derivation of Theorem 4.3**\n\n**A1:** Here we provide the definition of MMP. In linear algebra, MPP of a matrix $K$ is a unique generalized inverse satisfying 4 conditions:$KZK=K$, $ZKZ=Z$, $(KZ)^T=KZ$ and $(ZK)^T=ZK$, then $Z$ is the MPP of $K$.\n\nRegarding Theorem 4.3, its derivation is straightforward. Specifically, Eq.(4) shows that the fundamental matrix $Z$ can be directly used to compute commute time. Since Lemma 4.2 provides an efficient method for obtaining $Z=\\widetilde{T}^\\dagger$, substituting $\\widetilde{T}^\\dagger$ into Eq.(4) yields the expression in Theorem 4.3. We will include a detailed derivation in the revised manuscript.\n\n**Q2: More discussion or experiments on large-scale graphs to understand limitations in memory usage**\n\n**A2:** We acknowledge that memory consumption is a limitation of CGNN due to the quadratic complexity of storing pairwise commute times. Although we threshold small entries to zero and optimize matrix storage, memory improvements remain limited. In contrast, vanilla GCN’s memory usage scales with the number of edges, making it more efficient. In the experiments of the large-scale Snap-Patents dataset(~3 million nodes), CGNN requires 13GB memory compared to GCN's 6GB. Future work will explore localization, sampling, or sparsification methods to reduce memory demands. Following your suggestion, we will add these potential strategies in the part of future work.\n\n**Q3: The individual codebase files are not accessible**\n\n**A3:** Here we provide the download link for code files: https://drive.google.com/file/d/1lu-od07JgmQK9OsLxlePeOwHYiN4kp2r/view?usp=sharing\n\n**Q4: Essential references not discussed**\n\n**A4:** Thank you for highlighting these relevant works. We will include a discussion in Section 4.2 about the rewiring methods used in these studies and clarify how they differ from ours.\n\n**Q5: Scenarios or applications where CGNN's benefits over directed GNN were more pronounced**\n\n**A5:** We emphasize that CGNN demonstrates substantial advantages in scenarios characterized by asymmetric mutual relationships—conditions prevalent in real-world networks such as webpage and social networks (e.g., Squirrel and AM-Photo datasets). In these networks, directional relationships (e.g., celebrity-follower structures) create significant path asymmetry, making traditional directed GNN methods inadequate, as they inherently fail to capture the mutual dependencies of node interactions.\n\n**Q6: Differences between our feature-based rewiring strategy and those in the [4,5]**\n\n**A6:** Although [4, 5] also propose rewiring strategies, their **motivations** and **methodologies** differ from ours:\n\n**[Motivation]** [4] rewires the graph to reduce negatively curved edges, thereby mitigating over-squashing(OS). [5] rewires the graph to optimize the spectral gap, thereby modifying the community structure to mitigate OS.\n\nOur method rewires the graph to make it irreducible and aperiodic, thereby deterministic commute time can be computed. Both the motivation and goal differ from [4,5].\n\n**[Methodology]** [4] rewires the graph by performing Delaunay triangulation on node features. [5] rewires the graph by perturbing inter/intra-cluster edges and adding edges between similar nodes.\n\nOur method rewires the graph by generating a strongly connected line graph ($G^{'}$ in Fig.2) and combine it to the original graph. Although [5] also uses feature similarity, our approach ensures the rewired graph is irreducible and aperiodic, which [5] does not achieve.\n\n**Q7: How does the integration of commute time in directed GNNs build upon or differ from [2,3]?**\n\n**A7:** They are different. In [2], commute time is used as an analytical tool to investigate over-squashing (OS) without directly computing it or use it to enhance message passing. In contrast, our work explicitly computes commute time to encode directional relationships between neighboring nodes, it enhances message passing. Besides, our method focuses on adjacent nodes without considering distant nodes, and thus is not an OS study.\n\n[3] also targets OS alleviation. Although it also embedding commute time into node embeddings, its optimization objective differs from ours. Specifically, [3] assumes undirected graphs, aiming for uniformly small commute times among neighbors (see Eq (4) in [3]). Conversely, our method uses commute time to weight neighbor aggregation, accommodating varying commute time scales inherent to digraphs.\n\n**Q8: [Q8.1] Impact of hyperparameters $q$ in SVD approximation; [Q8.2] the number of additional edges in the rewiring strategy, and [Q8.3] the comparison with Transformer-based model**\n\n**A8:** We address the hyperparameter ablation studies and comparison requests in link: https://anonymous.4open.science/r/K5269.", "claims_and_evidence": "The claims regarding DiLap's derivation and its connection to the fundamental matrix are supported by theoretical evidence, providing a sound basis for computing commute times.\n\nExperimental evidence, including accuracy comparisons in Table 1 and accuracy versus runtime tradeoff analysis in Figure 4 across eight datasets, supports the claim that CGNN surpasses multiple baseline methods in performance.\n\nThe paper also validates its rewiring strategy to ensure the graph meets irreducibility and aperiodicity conditions, with experimental evidence in Table 2.", "methods_and_evaluation_criteria": "By integrating commute times through DiLap into the message passing scheme CGNN directly addresses the issue of capturing asymmetric relationships in digraphs.\n\nEmpirical evaluation on eight benchmark datasets, encompassing both homophilic and heterophilic networks, is diverse and compelling.\n\nRuntime comparisons and ablation studies, e.g. assessing the impact of graph rewiring and directed vs. undirected variants, further validate that the method is practically robust.", "theoretical_claims": "All main theoretical claims, including Proposition 3.2, Theorem 3.3, Proposition 4.1, Lemma 4.2, and Theorem 4.3, are mathematically sound under the stated assumptions, with no significant issues identified.\n\nHowever, more detailed steps in Lemma 4.2 and Theorem 4.3 would improve clarity.\n\nSpecifically, the definition of Moore–Penrose pseudoinverse of a matrix, as well as a detailed step-by-step derivation of Theorem 4.3 would aid clarity.", "experimental_designs_or_analyses": "The experimental analyses, including node classification baseline comparison in Table 1, tradeoff analyses in in Figure 4 and Table 3, ablation studies in Tables 2 and 4, and analyses of commute-time proximity related to label similarity in Figure 3 are thoughtfully constructed.\n\nAlthough the experiments validate the core claims, the impact of hyperparameters—such as the rank (q) in the SVD approximation and the number of additional edges in the rewiring strategy—on CGNN's performance is not thoroughly examined, and further analysis could enhance understanding of its robustness.\n\nThe scalability analysis is promising, but since the commute time matrix is dense by nature, it would be beneficial to see more discussion or experiments on very large-scale graphs to fully understand potential limitations in memory usage.", "relation_to_broader_scientific_literature": "Recent advances in GNNs for directed graphs focus on edge directions but usually handle one-way interactions, while this submission highlights the integration of mutual path dependencies.\n\nBuilding on existing work that used transition probabilities and stationary distributions for directed graph Laplacians, this paper introduces a weighted digraph Laplacian (DiLap) derived from the signal's gradient divergence.\n\nInspired by PageRank and diffusion, the authors introduce a sparse rewiring strategy for computing commute times in CGNNs.", "essential_references_not_discussed": "Both commute times and rewiring strategies are well-recognized in the graph neural network literature [1], particularly in relation to the over-squashing phenomenon.\n\nPrior findings have established that over‐squashing stems from high commute times [2] and that topology-aware rewiring can effectively mitigate such limitations [3].\n\nRewiring strategies based on node features have recently been a trend [4, 5] in addressing over-squashing, albeit not specifically in the context of directed graphs.\n\nReferences:\n1. Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey, arXiv:2411.17429, 2024,\n2. On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology, ICML 2024,\n3. DiffWire: Inductive Graph Rewiring via the Lovász Bound, In LoG 2022,\n4. Delaunay Graph: Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation, ICML 2024,\n5. GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring, In ICLR 2025.", "other_strengths_and_weaknesses": "Strengths:\n\n[+] The paper is well-written and organised with clarity.\n\n[+] Additional experimental details, e.g. hyperaprameters, visualisation, and sensitivity, in the appendix strengthen the submission\n\n\nWeaknesses:\n\n[-] The improvements over directed GNNs shown in Table 1 are minimal.", "other_comments_or_suggestions": "This submission references recent research [6] on transformer models for directed graphs. \n\nHowever, it does not discuss the trade-offs between CGNN and transformers on directed graphs. \n\nMoreover, there is no empirical comparison with transformer baselines.\n\n[6] Transformers meet directed graphs, In ICML 2023.", "questions_for_authors": "1. Were there specific scenarios or applications where CGNN's benefits over directed GNN were more pronounced than the incremental improvements reported in Table 1? Understanding these scenarios will help highlight the unique strengths and potential use cases of CGNN, indicating situations where its deployment would be most advantageous.\n2. What are the main differences between feature-based rewiring strategy proposed in this submission and those in the existing literature [4, 5]? Clarifying these differences allows for a better assessment of the method's novelty and its contribution to the ongoing advancements in GNN research.\n3. How does the integration of commute time in directed graph neural networks build upon or differ from existing publications [2, 3] that utilise commute times for addressing the over-squashing phenomenon in undirected graphs? This will provide insight into whether the approach leverages or innovates upon established methodologies, specifically addressing challenges unique to directed graphs.\n4. Were there considerations on examining the impact of hyperparameters, such as the rank in SVD approximation and the number of additional edges in the rewiring strategy, on the performance and robustness of CGNN? Understanding the influence of hyperparameters is crucial for optimizing CGNN’s performance and can inform best practices for its implementation in different contexts.\n5. How does CGNN compare with transformer-based approaches for directed graphs, particularly regarding performance and scalability? Such a comparison provides a clearer picture of how CGNN stands relative to cutting-edge methods, potentially influencing researchers' choice of tools for tackling directed graph problems.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a neural architecture for directed graphs. The main idea is to re-weight the messages of in-/out-edges by commute time to integrate longer-range structure into the message passing. To compute commute time efficiently, the authors use a specific directed Laplacian, and approximate the computation of the required pseudoinverse with truncated SVD. The proposed method performs well when compared to other approaches, including one transformer for directed graphs. 
One weakness is the scalability to dense graphs, as some computations scale with the number of edges.
During the discussion, the reviewers raised a number of questions, e.g., on hyperparameter tuning, additional comparisons (e.g. to transformers) and ablations. The authors answered these well, but should definitely include the experiments from the rebuttal in the main paper. 
Optional: In addition, I would be curious how the derived commute times would perform when used for positional encodings instead of re-weighting the message passing (but I did not take this into account for the decision).
Decision: Accept (poster)