Commute Graph Neural Networks

Thank you for the thoughtful feedback on our manuscript. We provide the following detailed responses to your major concerns.

Q1: The footnote on page 1 is not sensible, and it is not clear why the previous methods are undirectional during shortest path computation. What do you mean by the footnote on page 1?

A1: Thank you for your feedback. It appears there may have been a significant misunderstanding, particularly concerning the terminology used in our paper. To clarify the footnote on page 1: The term 'unidirectional' is used to describe relationships in directed graphs, where edges have a specific direction from one node to another. This is distinct from 'undirectional,' which implies that the edges do not have a specified direction. I acknowledge that these terms are quite similar and understand how this could lead to confusion. The correct understanding of these terms is crucial, as it directly impacts the interpretation of our research's motivation and framework.

Why do current digraph neural networks only capture unidirectional relationships between neighboring nodes? To answer this question, let's consider the directed graph in Figure 1. The central node, $v_i$, has three one-hop neighbors: $v_m$ as an in-neighbor and $v_j$ and $v_k$ as out-neighbors. $v_m$ is connected to $v_i$ via an incoming edge, while both $v_j$ and $v_k$ are connected to $v_i$ through outgoing edges. State-of-the-art digraph neural networks, such as MagNet and DirGNN, utilize one-layer directed message passing to differentiate between incoming and outgoing neighbors of $v_i$. Consequently, in the process of learning the representation of $v_i$, since both $v_j$ and $v_k$ share the same edge direction relative to $v_i$, these models treat them as structurally equivalent with respect to the central node. In other words, within these frameworks, $v_j$ and $v_k$ are considered unidirectionally equivalent to $v_i$ because they are both one-hop out-neighbors.

Why can our proposed CGNN model capture mutual relationships rather than just unidirectional relationships between neighboring nodes? Although both $v_j$ and $v_k$ are one-hop out-neighbors of $v_i$ and therefore unidirectionally equivalent, they differ significantly in their commute distances to $v_i$. Specifically, $v_j$ requires 5 hops to return to $v_i$, whereas $v_k$ only needs 3 hops to return to $v_i$ based on the directed nature of the graph. Despite their unidirectional equivalence, these differing commute distances suggest varying strengths in their relationships with $v_i$, i.e., nodes with shorter commute distances are deemed to have stronger relationships. Consequently, the relationship between $v_i$ and $v_k$ is stronger than that between $v_i$ and $v_j$. Our research integrates these commute relationships between nodes into the graph neural network model to better reflect the complexity of real-world interactions.

Q2: Why is the proposed Laplacian sparse? From Eq. (5), the matrix $\mathbf{P}$ seems to be a complete matrix.

A2: If the adjacency matrix $\mathbf{A}$ of a given graph is not complete, meaning the graph itself is not a complete graph, then its corresponding transition matrix $\mathbf{P}$ will not be a complete matrix either. This follows because $\mathbf{P}= \mathbf{D}^{-1}\mathbf{A}$ , where the degree matrix $\mathbf{D} \in \mathbb{R}^{N \times N}$ is a diagonal matrix whose diagonal elements represent the degrees of the nodes. Therefore, any zero entry in $\mathbf{A}$ will result in a corresponding zero entry in $\mathbf{P}$. In most real-world graphs, $\mathbf{A}$ is typically sparse, which consequently makes $\mathbf{P}$ a sparse matrix as well.

Q3: What is the relationship between Eq. (5) and $D^{-2}L$ and why do you should choose Eq. (5)?

A3: We apologize for the confusion in the definition and derivation of Eq.(5), i.e., the directed graph Laplacian (DiLap), in our initial submission. We have update the the definition of DiLap in Section 4.1 and its derivation in Appendix A.1. The DiLap defined in Eq. (5) does not have any relationship with $D^{-2}L$. For undirected graphs, the graph Laplacian is defined as the divergence of the gradient of a graph signal [1,2], which acts as a smoothness operator on the graph. Inspired by this, we define the divergence of the gradient for signals on directed graphs, as detailed in Appendix A.1. This definition allows the DiLap to serve similarly as a smoothness operator on directed graphs, demonstrating its rationality and adherence to the essence of the traditional graph Laplacian concept.

Q4: Why does the rewiring procedure only minimally alters the overall semantics of the original graph?

A4: Our proposed similarity-based rewiring method involves two steps: initially generating a line graph, as shown in $G^\prime$ in Fig.2, where $G^\prime$ is a strongly connected graph with each node having at most two edges. We then combine $G^\prime$ and $G$. This approach minimally alters the main structural semantics of the original graph, because each node in the original graph at most be added at most two additional edges. To quantify the alterations brought from graph rewiring, we define edge density as $\delta = \frac{M}{M_{\text{max}}}$, where $M_{\text{max}}$ is the maximum possible number of edges ($N^2$ for both $G$ and $\widetilde{G}$) in the graph 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. In the below table we calculate $\Delta$ on AM-Photo, Snap-Patent 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 increases are only 6.7% and 3.2% respectively. These findings demonstrate that our rewiring method generally has a modest effect on graph density.

Q5: [3] mentions flow imbalance in directed graphs and is not discussed. It is also unclear whether the idea in [1] is considered undirectional by the authors.

A5: Thank you for bringing the DIGRAC to our attention. Upon thorough review of the literature, we confirm that DIGRAC primarily captures unidirectional relationships between nodes due to its reliance on the standard message passing framework. This framework inherently focuses on unidirectional interactions among nodes. However, it is important to note that DIGRAC's main objective is to enhance node clustering through a cluster-aware self-supervised loss, rather than to address commute time between nodes.

In contrast, our CGNN model is specifically designed to capture and utilize commute times, offering a unique perspective by integrating this aspect into the graph neural network. This capability allows CGNN to account for varying path lengths and directions in directed graphs, which is not addressed by the DIGRAC framework. This distinction is crucial for understanding the specific contributions and focus of our work compared to that cited in the literature.

Q6: Grammar issues: e.g., line 115.5 "notations. We" should be "notations, we"

A6: Thank you for pointing out the grammar issue. We will correct it in the next version of the manuscript.

[1] The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 2013

[2] Graph representation learning. Morgan & Claypool Publishers, 2020

[3] DIGRAC: digraph clustering based on flow imbalance. In Learning on Graphs Conference (pp. 21-1). PMLR.

I apologize for missing the letter "i" in your footnote. I have removed all comments in that regard and adjusted my score accordingly.

Regarding the statement of being sparse for P, I think your current statement in the paper needs to be modified to reflect that P is not a complete matrix.

Dear Reviewer EWXV

Thank you once again for your thorough and insightful feedback. We have endeavored to address all your concerns in our responses. As we near the end of this discussion phase, we are eager to know if our explanations have satisfactorily addressed your points.

If you have any more comments or questions about our rebuttal, we strongly welcome your feedback. Your guidance is crucial for improving our work, and we look forward to any additional thoughts you might have.

Warm regards, The Authors of Submission 6734.

Dear Reviewer EWXV,

As the discussion deadline approaches, we have uploaded a revised version of our manuscript that fully incorporates all your suggestions and has been thoroughly polished. Specifically, we have made the following improvements based on your feedback:

• In Section 2, we provide a detailed explanation demonstrating the sparsity of the transition probability matrix $\mathbf{P}$.
• In Appendix D.5, we present additional experiments to illustrate how the rewiring procedure influences the overall semantics of the original graph.
• We have corrected all grammatical issues and typos.

We look forward to your response and are eager to address any further questions you may have.

Best regards,

All authors

We sincerely appreciate the reviewer's constructive feedback and positive remarks on our work. We provide the following detailed responses to your major concerns. We will add all revisions into the next version of our paper.

Q1: It would be beneficial to also examine how rewiring affects graph density.

A1: We appreciate your suggestion to examine how our rewiring strategy affects graph density. Our approach, as illustrated in Figure 2, involves a two-step process: initially, we generate a line graph $G^\prime$, , which is a strongly connected graph where each node has at most two edges. We then merge $G^\prime$ with the original graph $G$ to create the rewired graph $\widetilde{G}$. This method minimally alters the main structural semantics of the original graph, as it adds at most two additional edges per node. To quantify these changes, we define edge density as $\delta = \frac{M}{M_{\text{max}}}$, where $M_{\text{max}}$ is the maximum possible number of edges ($N^2$ for both $G$ and $\widetilde{G}$) in the graph 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. In the below table we calculate $\Delta$ on AM-Photo, Snap-Patent 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 increases are only 6.7% and 3.2% respectively. These findings demonstrate that our rewiring method generally has a modest effect on graph density.

Q2: Unobserved Edges in Definition of $m_{i,in}^{(l)}$ and $m_{i,out}^{(l)}$.

A2: Thank you for your insightful suggestion regarding the treatment of unobserved edges. It is important to clarify that our model operates under the assumption that all edges within the graph data are observed, meaning that we have complete knowledge of all edges and their respective directions. The primary objective of our model is to leverage this complete edge information to learn node relationships effectively, utilizing directed edges with commute times to enhance our understanding of graph dynamics.

Q3: Inclusion of Synthetic Datasets.

A3: Thank you for this valuable suggestion, which enhances the interpretability of incorporating commute time into GNNs. Reviewer WWVp also emphasized this point. Thus, we generate synthetic graph data as follows: The dataset will be used for binary classification on synthetic directed graphs, consisting of 3,000 nodes divided evenly between two classes (1,500 nodes per class). The features of these classes are drawn from Gaussian distributions: $\mathcal{N}(0,1)$ for the first class and $\mathcal{N}(3,1)$ for the second. To construct the edges, nodes within the same class are connected with an edge with a probability of 0.2, while nodes from different classes have a much lower connection probability of 0.02. These connections are assigned random directions. Additionally, we specify a predefined commute path length range of [2, 7]. This method allows us to create a graph where each node has an asymmetric commute path with its neighbors, facilitating a detailed examination of how graph neural networks perform under varying structural conditions. On this graph, we first apply CGNN to learn node representations. Subsequently, we calculate the Mutual Information (MI) between the central node and its neighbors with short commute times, denoted as $\alpha_s$, and between the central node and its neighbors 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 on such graphs, CGNN achieved $\overline{\alpha}_s = 13.2974$ and $\overline{\alpha}_l = 6.5521$, which aligns with our model's purpose.

Q4: Reordering Related Work.

A4: Thank you for your suggestion. In the revised version of the paper, we will incorporate your feedback and reorganize the structure of the paper accordingly.

We greatly appreciate your valuable time and constructive comments. We hope our answers can fully address your concerns.

Q1: To this reviewer, the biggest weakness of the paper was that although weighing neighbors by commute time is sensible, it is not necessarily principled. Is there any reason to a priori expect that neighbors of a node that have shorter commute times to that node somehow contain more relevant features for learning on graphs? This seems to depend on the nature of the learning problem and the data set. As outline in the weaknesses above, can the authors provide a principled reason for why features aggregated from a node's neighbors should be weighed by the commute distance of the node to its neighbors? Can the authors provide any theoretical justification for using commute distance for such weighing?

A1: We recognize that the rationale for incorporating commute time in GNNs is based more on empirical observations and intuitive reasoning than on established principles. We also acknowledge that incorporating commute times, which highlight mutual relationships between nodes, may not always help and sometimes provide only marginal benefits. For example, on the SNAP-PATENTS and CoraML 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 between 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 similar 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 dependencies.

However, in many real-world directed graph scenarios, the use of commute times proves beneficial. Our experiments, as illustrated in Figures 3 and 6, demonstrate the value of commute time in enhancing GNN performance across various datasets. The results indicate that leveraging commute time to weigh neighbor interactions can effectively help the model filter out irrelevant heterophilic information, thereby improving the relevance and quality of the information propagated during message passing.

Although the utility of commute time is conditional and our approach may not be always applicable, we believe that our work contributes new insights to the analysis of directed graphs. Our model is pioneering in its identification and handling of mutual path dependencies in directed graphs, which is vital for representing real-world relationships between entities—an aspect largely neglected in previous research. This represents a contribution to the directed graph analysis community and underscores the innovative nature of our study.

Q4: Can the authors apply their approach a real world problem on directed graphs that requires long range information transmission, such as power grids or traffic flow data?

A4: We believe that our model has the potential to address real-world problems on directed graphs. However, specific domains such as traffic flow involve temporal graph data, which would require further adaptations or the addition of tailored modules to effectively apply CGNN to these contexts. In our current research, we have utilized datasets such as middle-scale datasets like AM-Photo and Squirrel, and large-scale datasets like Snap-Patents and Roman-Empire, which are commonly used in the literature on directed graph neural networks. These applications demonstrate the versatility of our model across various scales and types of directed graphs, providing a foundation for future extensions to more complex scenarios like power grids or dynamic traffic networks.

Q5: Can the authors try alternative methods for graph rewiring that also produce sparse graphs, such as constructing a kNN graph using the node features? The authors should include an empirical comparison or provide theoretical justification for their method. Is the proposed similarity-based rewiring mode optimal?

A5: We opted not to use kNN for sparsifying the graphs for two main reasons: First and the most intrinsic problem of kNN graph is that kNN graph inherently do not guarantee irreducibility. In the other words, kNN graph constructed based on node features may not be strongly connected, thus we can not compute meaningful and deterministic commute time based on kNN graph. Secondly, reconstructing the graph using kNN fundamentally alters the original structure of the graph. This significant change can adversely affect the performance on downstream prediction tasks, as it may discard important structural information inherent to the original graph. In contrast, our proposed similarity-based rewiring method involves two steps: initially generating a line graph, as shown in $G^\prime$ in Fig.2, where $G^\prime$ is a strongly connected graph with each node having at most two edges. We then combine $G^\prime$ and $G$. This approach minimally alters the main structural semantics of the original graph, because each node in the original graph at most be added two more edges. Moreover, because $G^\prime$ is irreducible, thus the rewired graph $\widetilde{G}$ also retains irreducibility. Thus we can use our proposed similarity-based rewiring strategy to compute meaningful and deterministic commute time. These reasons underscore why our similarity-based rewiring strategy is more suitable for our objectives than using a kNN-based method.

Q6: How much of the improvement is coming from the fact that the Laplacian proposed by the authors is weighted by the stationary probability of random walks on the graph? Can the authors do an ablation study to disentangle this from the commute distance?

A6: In our study, the integration of node importance (stationary probability) into the DiLap operator is aimed not only at enriching the structural information captured by DiLap but also at facilitating a simplified formulation of the fundamental matrix $\mathbf{Z}$ (as detailed in the proof of Lemma 4.1 in Appendix A3). However, we recognize the value of your suggestion to conduct an ablation study to disentangle this from the commute distance. To this end, we introduce $\mathrm{CGNN}\_{\text{un}}$, which utilizes an unweighted version of the DiLap operator. We will compare the node classification results between $\mathrm{CGNN}\_{\text{un}}$ and the original CGNN model to specifically assess the impact of weighting by the stationary probability on the performance. We show the experimental results as follows:

Q7: This reviewer was confused by the comment that general GNNs can outperform models tailored for directed graphs with hyper-parameter tuning. In Table 1, DirGNN, a model tailored for directed graphs, outperforms GCN. Can the authors clarify what they mean by this comment?

A7: We apologize for the confusion caused by our previous statement. Our intention was to convey that, with careful hyper-parameter tuning, general 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. While it is true that DirGNN outperforms GCN, our results in Table 1 of our paper shows that other directed graph models like DiGCN, MagNet, and DiGCL do not always perform better than a well-tuned vanilla GCN such as on Squirrel dataset. We have revised this statement in the latest version of our paper.

Q2.2: Can the authors look at properties of longer hops and how information is aggregated across nodes within or outside the same class?

A2.2: For the second question, your suggestion to explore the effects of longer hops and the aggregation of information across nodes within or outside the same class is compelling. In our proposed CGNN model, similar to many existing GNNs, the number of layers—which corresponds to the number of hops to be aggregated—is treated as a hyperparameter. This hyperparameter is adjusted based on the characteristics of different datasets to optimize performance. Our empirical findings, as detailed in Table 6, show that for homophilic datasets such as Citeseer and AM-Photo, fewer hops are generally sufficient to yield the best results. In contrast, for heterophilic datasets like Squirrel and Chameleon, where neighboring nodes often belong to different classes, our model benefits from more layers to effectively retrieve useful information from longer hops. To quantitatively assess the impact of varying hops on learning node representations, we introduced the metric $\overline{\delta}\_{\text{heter}}$ , which measures the average Mutual Information (MI) between the central nodes' representations and their heterophilic neighbors (those outside their class). We then calculate the ratio $\frac{\overline{\delta}}{\overline{\delta}\_{\text{heter}} + \overline{\delta}}$ to quantify the relative contribution of homophilic (within the same class) versus heterophilic (outside the same class) information in the node representation. The following table indicate that in heterophilic graphs, incorporating more hops allows the model to capture more useful information from broader neighborhood contexts. Conversely, fewer hops are generally sufficient in homophilic graphs to achieve optimal learning outcomes.

Q2.3: Can the authors look at properties of longer hops (going beyond one-hop neighbors) and how information is aggregated across nodes within or outside the same class?

A2.3: For the synthetic dataset, we propose the following generation process: The dataset will be used for binary classification on synthetic directed graphs, consisting of 3,000 nodes divided evenly between two classes (1,500 nodes per class). The features of these classes are drawn from Gaussian distributions: $\mathcal{N}(0,1)$ for the first class and $\mathcal{N}(3,1)$ for the second. To construct the edges, nodes within the same class are connected with an edge with a probability of 0.2, while nodes from different classes have a much lower connection probability of 0.02. These connections are assigned random directions. Additionally, we specify a predefined commute path length range of [2, 7]. This method allows us to create a graph where each node has an asymmetric commute path with its neighbors, facilitating a detailed examination of how graph neural networks perform under varying structural conditions. On this graph, we first apply CGNN to learn node representations. Subsequently, we calculate the Mutual Information (MI) between the central node and its neighbors with short commute times, denoted as $\alpha_s$, and between the central node and its neighbors 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 on such graphs, CGNN achieved $\overline{\alpha}\_s = 13.2974$ and $\overline{\alpha}\_l = 6.5521$, which aligns with our model's purpose.

Q3: How does the proposed model's performance change with depth?

A3: Thank you for your insightful observation. Our model is designed to accurately capture the strength of relationships between neighboring nodes. However, we agree that investigating model's capacity to handle oversmoothing is also interesting. Thus, we have conducted experiments to assess this. Specifically, we tested the CGNN with varying depths of 1, 3, 5, and 10 layers on the AM-Photo dataset and compared the results with those of a standard GCN and DirGNN. These experiments demonstrate how our model suffer from oversmoothing as it increases in depth. The results indicate that while GCN, DirGNN, and CGNN all exhibit some degree of oversmoothing, CGNN consistently outperforms the baseline models even as the number of layers increases.

We will add the whole experiment including more baselines and datasets in the revised version of our paper.

Q2.1: Can the authors include other empirical measures of how the weighting of neighbors can improve performance of GNNs?

A2.1: Thank you for your suggestions. For the first question, as indicated in Section 5.1, Figure 3, we assess the effectiveness of commute time in enhancing message passing by comparing the squared Frobenius norm of differences between the label similarity matrix, $\mathcal{M}$, and two propagation matrices: the commute-time-based propagation matrix $\widetilde{\mathcal{C}}^{\text{in}} + \widetilde{\mathcal{C}}^{\text{out}}$, and the original propagation matrix $\mathbf{A}+\mathbf{A}^\top$. This comparison helps to illustrate how commute time aids in filtering out irrelevant heterophilic information during message passing. o further address your query regarding the weighting of neighbors and its impact on GNN performance, we have expanded our analysis in Appendix D.3, Figures 6(a) through 6(e). In this section, we compare our proposed commute-time-based message passing with the propagation mechanisms used in GCN and PPRGo. This comparison is designed to showcase our model's proficiency in managing both homophilic and heterophilic graphs, and its ability to effectively filter noise from neighbors.

To address the request for other empirical measures of neighbor re-weighting, we propose utilizing Mutual Information (MI) as a metric. This measure would compute the mutual information between the aggregated features of neighbors (after weighting) and the target labels. A higher mutual information between the representations of neighboring nodes with the same label suggests that the weighted aggregation effectively captures more relevant information for the prediction task. This approach could provide an understanding of how well the neighbor weighting strategy enhances the performance of the GNN in various learning scenarios. Specifically, given the node representation $\mathbf{Z}$ learned by the CGNN with re-weighted neighbors, and compare it to $\mathbf{Z}^\prime$ , the representation learned by a standard GCN without edge re-weighting. We define the average MI between a central node $v_i$ and its homophilic neighbors $\mathcal{N}^{\text{homo}}\_i$ as $\delta_i = \frac{1}{|\mathcal{N}^{\text{homo}}\_i|}\sum_{v_j \in \mathcal{N}^{\text{homo}}\_i}\mathrm{MI}(\mathbf{Z}\_i, \mathbf{Z}\_j)$ for CGNN with edge re-weighting. Considering all $N$ nodes, the average MI across the graph can be expressed as $\overline{\delta} = \frac{1}{N}\sum_i \delta_i$. Similarly, for GCN without edge re-weighting, the MI between homophilic neighboring nodes is represented as $\delta^\prime_i = \frac{1}{|\mathcal{N}^{\text{homo}}\_i|}\sum_{v_j \in \mathcal{N}^{\text{homo}}\_i}\mathrm{MI}(\mathbf{Z}\_i^\prime, \mathbf{Z}\_j^\prime)$, and the graph average MI is denoted as $\overline{\delta}^\prime = \frac{1}{N}\sum_i \delta^\prime_i$. Our experiments on directed graph datasets in the below table demonstrate that our proposed commute-time-based edge re-weighting method more effectively captures relevant information from homophilic neighbors, thereby enhancing the model’s predictive accuracy for tasks involving nodes with similar labels.

Dear Reviewer WWVp,

We would like to express our deep gratitude for your comprehensive and insightful review of our paper. In response to the points you raised, we have provided detailed, point-by-point explanations and additional experiments to address your concerns thoroughly.

Since the discussion due is approaching, would you mind checking the response to confirm where you have any further questions?

We are looking forward to your reply and happy to answer your further questions.

Warm regards,

The Authors of Submission 6734.

Dear Reviewer WWVp,

Thank you once again for your insightful feedback on our submission. We would like to remind you that the discussion period is concluding. Considering the borderline score given during the initial review, your final decision is very crucial to the fate of our paper. Thus, We kindly urge you to review our responses.

Below, we reiterate the key elements of our response to your comments, hoping to ensure that all your concerns have been thoroughly addressed.

• We clarified the non-principled nature of our method and defined the specific application scope of our work.
• We introduced a new empirical measure for re-weighting neighbor interactions.
• We carried out additional experiments to explore the effects of longer hops and varying model depths.
• We proposed and detailed a synthetic dataset to demonstrate how commute time facilitates the filtering of heterophilic information by our model.
• We discussed why kNN-based rewiring cannot substitute for our proposed similarity-based rewiring technique.
• We conducted further experiments involving different measures of node importance.

We are eager to confirm whether our responses have adequately addressed your concerns. We look forward to any additional input you may provide.

Warm regards,

The Authors of Submission 6734.

Q3: Your method appears to be relatively memory intensive.

A3: Thank you for your valuable feedback regarding the memory intensity of our method. Indeed, we totally acknowledge that the commute time matrix $\mathcal{C}$ is a dense matri, designed to preserve commute times between all pairs of nodes, resulting in a memory complexity that is quadratic with respect to the number of nodes, specifically $\mathcal{O} (N^2)$. In contrast, baseline methods such as GCN, GAT, and DirGNN primarily depend on memory proportional to the number of edges, $\mathcal{O}(|E|)$. This inherent difference underscores the increased memory demands of our method. On the other hand, exponential function on $\mathcal{C}$ can be efficiently computed by first using $\mathbf{A}$ to sparsify it.

Our complexity analysis in Section 4.4 demonstrates that the time complexity of our method is within a feasible range, consistent with most existing GNN models. We understand that memory cost is a crucial factor for scalability, especially on large graphs, and recognize that this remains a challenge for our CGNN. However, this challenge also presents a compelling opportunity for future research. We plan to explore this in our future work.

Q4: The ablation study should be extended in scope to also extend to homophilic datasets and to also include other commonly used message passing operators, such as the symmetrically normalised adjacency matrix used in the GCN and the PageRank matrix used in the PPRGo model .

A4: Thank you for your insightful suggestions. In response, we have included additional analyses in Figure 6 of Appendix D.3, which is highlighted in blue in the revised version of our paper. We conducted an ablation study on homophilic graphs, specifically analyzing label similarity in CoraML and Citeseer. The results, as shown in Figure 6a, confirm that our model also effectively filters and enhances useful information in these homophilic settings. Moreover, we have expanded our comparative framework by incorporating two other propagation matrices: $\widehat{\widetilde{\mathbf{A}}}$ from vanilla GCN, and the approximate personalized PageRank $\mathrm{APPR}$ from PPRGo. Figures 6b and 6d illustrate that while GCN and PPRGo manage to slightly reduce heterophilic information from neighbors during message passing, CGNN achieves significantly more substantial reductions. These findings underscore the robustness of CGNN in handling both homophilic and heterophilic information.

Q5: It seems to be fairer to either compare dense versions of both matrices or sparse versions of both matrices.

A5: This suggestion is valuable. Similar to our approach with the commute-time-based propagation matrix $\mathcal{C}$ , where we use the adjacency matrix $\mathbf{A}$ to sparse it,, we have applied the same method to sparsify the PPR-based propagation matrix. The resulting model is denoted as $\text{CGNN}\_{\text{sppr}}$. In the table below, we present a comparison of node classification results between $\text{CGNN}$ and $\text{CGNN}\_{\text{sppr}}$.

Q6.1: The abbreviation "SPD" is used in Line 45 before its definition.

A6.1: We have modified it to "shortest path distance (SPD)".

Q6.2: The contributions of your paper are not explicitly listed.

A6.2: Thank you for your feedback. Here we list the contributions of our work.

(1) We identify and address mutual path dependencies in directed graphs, which is crucial for representing real-world relationships between entities, a factor ignored in prior work. Further, we propose to use commute times to quantify the strength of node-wise mutual path dependencies.

(2) We extend the traditional graph Laplacian to directed graphs by introducing DiLap, a novel Laplacian based on signal processing principles tailored for digraphs. Leveraging DiLap, we develop an efficient and theoretically sound method for computing commute times that enhances computational feasibility.

(3) We propose the Commute Graph Neural Networks (CGNN), which incorporate commute-time-weighted message passing into their architecture. Through comprehensive experiments across various digraph datasets, we demonstrate the effectiveness of CGNN.

We have outlined the contributions of our work in the Introduction section, specifically from lines 88 to 99.

We are grateful for your insightful comments and positive feedback on our paper. Below are our detailed response. All modifications have been highlighted in blue in our revised manuscript.

Q1: The derivation of your DiLap operator appears to be flawed.

A1: We apologize for the errors in the definition and derivation of the directed graph Laplacian (DiLap) in our initial submission. We recognize that the random walk Laplacian does not adequately represent the divergence of the gradient on directed graphs. In the revised version of our paper, we have rigorously redefined the divergence of the gradient on digraphs as $\mathbf{T} = \mathcal{D}\mathcal{G}$, where $\mathcal{D}$ is the divergence operator and $\mathcal{G}$ is the gradient operator. Specifically, $\mathcal{G}$ maps a signal defined on the nodes of the graph to a signal on the edges, with $(\mathcal{G}s)\_{(v_i,v_j)} = \mathbf{P}\_{ij} (s_i - s_j)$ and $\mathcal{D}$ maps a signal defined on the edges back to a signal on the nodes, where $\left(\mathcal{D}(\mathcal{G}s)\right)\_i = \sum\_{v_j \in \mathcal{N}\_i^{\text{in}}} (\mathcal{G}s)\_{(v_j,v_i)} - \sum\_{v_j \in \mathcal{N}\_i^{\text{out}}} (\mathcal{G}s)\_{(v_i,v_j)}$. Consequently, the new DiLap can be represented in matrix form of the composed operator $\mathcal{D}\mathcal{G}$ as \mathbf{T} = \mathbf{B} \mathrm{diag}\left(\left\\{\mathbf{P}\_{ij}\right\\}\_{(v_i, v_j) \in E} ^ M \right) \mathbf{B}^\top, with $\mathbf{B}$ serving as the incidence matrix.

We have detailed these corrections and elaborated on the derivation in Appendix A of the revised manuscript. The respective changes have been highlighted in blue in Section 4.1. Additionally, we have updated the experimental results to reflect these adjustments. We appreciate your feedback and believe these modifications have significantly strengthened the paper.

Q2: Are you using the adjacency matrix $\widetilde{\mathcal{C}}$ corresponding to the graph in which you have added the node feature similarity edges? Could you hypothesise how severe the impact may be of calculating the commute times on a rewired graph and to then message pass with the original graph.

A2: Thank you for pointing out the ambiguity in the sparsification of $\widetilde{\mathcal{C}}$. In our work, the adjacency matrix used for sparsifying $\widetilde{\mathcal{C}}$ originates from the original graph $\mathbf{A}$, not the rewired one. The purpose of the similarity-based graph rewiring is solely to ensuring that the new graph remains both irreducible and aperiodic. It allows us to compute meaningful (non-zero) and deterministic node-wise commute times with the rewired graph. We then leverage these computed commute times to strengthen node relationships between neighboring nodes in the original graph, enhancing and refining the information flow during message passing. Thus, we use original adjacency matrix $\mathbf{A}$ to sparsify $\widetilde{\mathcal{C}}$, which can filter the relations in the original graph.

For the second question, we address this both intuitively and empirically. Intuitively, as detailed in Section 4.2 and illustrated in Figure 2, our similarity-based rewiring method introduces at most two additional edges per node, targeting those nodes with the highest feature similarity. This strategy is designed to minimally alter the original graph structure. Consequently, the overall results are likely similar whether using the original or the rewired graph. We here conduct empirical analyses which also support this assertion, indicating minimal impact on the outcomes due to the restrained scope of modifications. Specifically, we use the original adjacency matrix $\mathbf{A}$ and the rewired one $\widetilde{\mathbf{A}}$ to sparsify the $\widetilde{\mathcal{C}}$ respectively and report the average accuracy in the following table.

Dear Reviewer rah7,

Thank you once again for your insightful feedback on our submission. We would like to remind you that the discussion period is concluding. To facilitate your review, we have provided a concise summary below, outlining our responses to each of your concerns:

• We have re-derived the directed graph Laplacian matrix based on the divergence of the gradient on the digraph signal, and adjusted the experiments.

• We have conducted further experiments focused on graph rewiring, and performed an ablation study on message passing operators and the sparsified PPR.

• We have made extensive revisions to enhance the clarity and polish of our paper.

Warm regards,

The Authors of Submission 6734.

Dear Reviewer rah7,

As the discussion deadline approaches, we have meticulously addressed your feedback and incorporated these insights into the revised version of our paper. We are confident that this updated manuscript comprehensively addresses all of your concerns.

We sincerely hope that you can take a moment to check out our latest manuscript. Thank you once again for your expertise.

Best regards,

All authors