Commute Graph Neural Networks

Thanks for your insightful feedback. We've consolidated your comments into 8 questions and provided responses to each.

Q1: The definition of Moore–Penrose Pseudoinverse (MPP) in Lemma 4.2, and a detailed derivation of Theorem 4.3

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$.

Regarding 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.

Q2: More discussion or experiments on large-scale graphs to understand limitations in memory usage

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.

Q3: The individual codebase files are not accessible

A3: Here we provide the download link for code files: https://drive.google.com/file/d/1lu-od07JgmQK9OsLxlePeOwHYiN4kp2r/view?usp=sharing

Q4: Essential references not discussed

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.

Q5: Scenarios or applications where CGNN's benefits over directed GNN were more pronounced

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.

Q6: Differences between our feature-based rewiring strategy and those in the [4,5]

A6: Although [4, 5] also propose rewiring strategies, their motivations and methodologies differ from ours:

[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.

Our 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].

[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.

Our 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.

Q7: How does the integration of commute time in directed GNNs build upon or differ from [2,3]?

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.

[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.

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

A8: We address the hyperparameter ablation studies and comparison requests in link: https://anonymous.4open.science/r/K5269.

Thanks for your insightful review. We have summarized all your feedback into 6 key questions and address below.

Q1: Why computing commute time rather than hitting time twice with different source and target nodes

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.

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

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.

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.

Q3: Proof for Prop 3.2

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.

Q4: Suggestion on including synthetic datasets

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.

Q5: Performance of using DiLap as a graph shift operator (GSO) w/o commute times

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.

Q6: Justification on motivation

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.

Thanks for your feedback. Our detailed responses follow.

Q1: Clarify how to maintain effectiveness given that the commute time information is partially preserved

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.

[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.

[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.

Q2: Ablation study on q

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.

Q3: Timing results for the Snap-Patents dataset

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.

Q4: How the hyperparameters (hps.) for DirGNN were tuned and whether they were optimized in a manner similar to those for CGNN

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.

Q5: Concern regarding the scalability on dense graphs, as the dimensions of the matrix B may impose limitations.

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.

Q6: Other cmts. or suggs

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.

Q1: Alternative ways of using the commute time in designing a directed GNN, e.g., regularisation or a non-MPNN?

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.

It 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.

Q2: Should we consider the task-specific information in assessing importance?

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.

Q3: Extending the use of commute time to analyze over-squashing in digraphs

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.

Q4: Other ways to convert commute time into a similarity measure

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.

Q5: Other Weakness: Utilisation of commute time is straightforward

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.

Line 138:Thanks! We will correct the typo in revision.