Differentiable Cluster Graph Neural Network

Thank you very much for your valuable feedback. We highly appreciate the comments and suggestions for improvement and will incorporate them into our revised manuscript. The reply to the questions is enclosed below.

The author claims that facilitating long-range interactions across distant nodes. Thus it should be tested on long-range graph datasets in [1].

Ans: In Table 13 of the Appendix, we have evaluated our methods on Peptides-func and Peptides-struct datasets from long range graph benchmarks(LRGB) [1]. More discussion can be found in Appendix D.4. Note that our current formulation of the bipartitie graph and implementation of message passing does not incorporate edge features which exist in LRGB datasets, and so we have removed the edge feature information in our LRGB experiments.

The proposed method does not achieve the best performance in all cases in Table 2. More analysis on why performing poorly should be added.

Ans: We consider our method’s performance to be competitive, as it achieves the best results on 12 out of 14 datasets and ranks third-best on another. Our method remains competitive even when compared to the most recent baselines.

The variation in performance across different datasets may stem from the degree of alignment between the global and local clustering inductive biases and the specific task. This alignment is challenging to quantify due to the latent nature of feature representations. We acknowledge this limitation and identify it as an important future research direction.

[2] and [3] are related to this work. I think quoting them is needed.

Ans: Thank you for your suggestion. We will ensure that [2] and [3] are properly cited. Additionally, we observed that [3] conducted experiments on some of the same datasets as our study. To provide a more comprehensive comparison, we have incorporated [3] as an additional baseline in Table 2 and Table 13.

The OT-based clustering and iterative optimization may add implementation complexity.

Ans: One of the key contributions of our work is introducing a simple yet effective solution to optimize OT-based clustering by leveraging straightforward matrix scaling and iterative message passing on graphs.

While OT-based clustering is often considered challenging to implement, our approach simplifies it by updating the assignment matrices using basic matrix scaling via the Sinkhorn–Knopp algorithm. This is made feasible by adopting the entropy-regularized version of the objective function, which significantly reduces implementation complexity.

Additionally, we seamlessly translate the iterative optimization steps into classical iterative message-passing steps. This design choice ensures that no additional complexity is introduced, making our method both practical and easy to implement.

Thanks for your question and engagement.

In Table 2, we observe that DC-GNN is outperformed by Neural Walker[3] on 2 out of 5 datasets , while DCGNN maintains competitive advantage on the other 3. This variation in performance could be arguably attributed to the different inductive biases inherent in the two methods.

According to the No-Free-Lunch Theorem [1], no single algorithm performs best on all possible problems/datasets. The effectiveness of an algorithm depends on how well its inductive bias aligns with the underlying structure of the specific problem.

• Neural Walker's Inductive Bias: Neural Walker leverages random walks to capture sequence information within graphs. By treating random walks as sequences and employing positional encodings on nodes within these sequences, it learns sequence embeddings that capture multi-hop interactions and long-range dependencies. This approach can be more expressive than the 1-WL test and is particularly effective on datasets where such multi-hop information is crucial.

• DC-GNN's Inductive Bias: DC-GNN is designed to capture clustering patterns in the latent space. It focuses on connecting similar nodes while disconnecting dissimilar ones, effectively capturing cluster structures within the data, both globally for long range information and locally for heterophilous neighborhood. This makes DC-GNN especially suited for datasets where such cluster patterns are prominent and more informative than the explicit graph connectivity.

Orthogonality: We also note that the inductive biases of DC-GNN and NeuralWalker are orthogonal. It's possible to consider integrating the two inductive biases. For instance, DC-GNN could be used as the MPNN component in the main update function(Eqn.(3)) of Neural Walker. This combination could leverage the strengths of both methods, although exploring this integration is beyond the scope of our current work.

We appreciate the opportunity to discuss these nuances and believe that both methods contribute valuable perspectives to graph representation learning.

References:

[1] No-Free-Lunch Theorem: Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67-82.

Thank you very much for your valuable feedback. We highly appreciate the comments and suggestions for improvement and will incorporate them into our revised manuscript. The reply to the questions is enclosed below.

Weaknesses:

The complexity analysis is very rough, the preprocessing of constructing bipartite graph may cost time, so it would be better to supplement the complexity of preprocessing data.

Ans: For the preprocessing of bipartite graph construction, the time needed is negligible, since we only need to modify the adjacency matrix (edge_index in Pytorch Geometric), and initialize the embeddings for cluster-nodes. It is linear in number of nodes and doesn't add to the training cost at each step.

The introduction of so-called “cluster nodes” is basically assigning a pseudo label to each node, which is quite common among methods on graph heterophily.

Ans: We understand the reviewer may be refering to approaches like [1]. If the reviewer meant other types of approaches, we would appreciate clarification.

Our approach is fundamentally different from assigning a pseudo-label to each node (as in [1]) in several key ways:

1. First, we assign multiple cluster-nodes per class based on the insight that datasets tend to exhibit multi-modal feature distribution even within one class (we added Figure 5 for visualization). A single cluster per class would be inaccurate or insufficient, as it may only represent an average or a dominant cluster.

2. Second, corresponding to our finding that cluster patterns can arise at both global and local levels, we are the first to devise both global and local cluster-nodes that connect to global neighborhood and local ego-neighborhood respectively.

3. Third, cluster-node are not just nodes with assigned labels, importantly the embeddings of cluster-nodes are learned in a principled way to have physical meaning that represents cluster centroids, which significantly differs from other approaches and, to our knowledge, has not been explored to tackle heterophily.

Reference: [1] Dai, Enyan, et al. "Label-wise graph convolutional network for heterophilic graphs." Learning on Graphs Conference. PMLR, 2022.

The novelty of directly integrate clustering into the message-passing mechanism is somehow weak.

Ans：We respectfully disagree. Direct integration of clustering into the message passing introduces several meaningful advancements:

1. End-to-end design: Previous methods in graph learning that incorporated clustering treated it as a separate component, limiting their ability to leverage the benefits of end-to-end learning. Our direct integration of clustering into the message-passing mechanism addresses the issue of non-differentiability of clustering and enables seamless end-to-end optimization.
2. Principled framework: Our approach is developed in principled manner with additional convergence properties.
3. Unified inductive bias in training and inference: Importantly, due to this direct integration into the message passing mechanism, the clustering inductive-bias is applied both in learning and inference phase. This is unlike the models which introduce the clustering bias with an auxillary loss function, which cannot enforce it during test time.

We appreciate your effort in reviewing our paper. Please find our responses below, which we hope adequately address your concerns.

No model access, no code access. (major)

Ans: As the code is proprietary, we require internal clearance before making it publicly accessible. To support the review process, we have shared a private link to the code for your review. We hope this addresses your concerns and are happy to assist further if needed. Please let us know if there is anything else we can provide to facilitate the process.

We have also added a reproducibility statement before the references to provide pointers to sections of the paper on reproducibility.

Most baseline results reported in Table1 do not align with the results reported in original papers. Where did you get the baseline results? If you run the baselines, please provide codes/loggers or any proof. If not, please cite the sources that you used. (major)

Ans: As stated in Appendix (line 1505 to 1508), all baseline results in Table 1 are obtained from Li et al. (2022), except for dataset Cornell5, Amherst41 and US-election where the original paper does not contain the baseline results. We have double checked and verified that baseline results are identical to those reported in Li et al. (2022)

For dataset Cornell5, Amherst41 and US-election, we reproduced the results using the official repo (https://github.com/RecklessRonan/GloGNN) of Li et al. (2022) due to absence of such results in their paper, as stated in Appendix (line 1505 to 1508). To faciliate reproducibility, we have also provided the hyperparameter search space for these datasets, as stated in Appendix (line 1509 to 1511, 1566 to 1587).

Reference:

Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. ICML 2022.

Overall contribution is not much, not so exciting. (minor)

Ans: While we value the reviewers opinion, we respectfully disagree. Our work provides a novel way of addressing the issues of heterophily and long-range interactions in a principled way, integerating the clustering appraoch within message passing. We believe this provides value to the understanding of these issues and provides a new perspective to viewing the ways to solve them, which future works can build upon. To list down the main contributions below.

1. Unified clustering-based approach tackles two issues in graph learning, - (1) to capture the long range interactions while mitigating oversquashing, and (2) to effectively aggregate local information in heterophilic neighbourhoods, where connected nodes in the graph are likely to be dissimilar.
2. We leverage Optimal Transport theory in the formulation of clustering based objective function, that involves both global and local clustering terms. We derive novel closed-form message passing functions between nodes and cluster-centroids, as optimization solutions for the entropic-regularized clustering based objective function. Our DC-GNN is then an optimization framework which is end-to-end differentiable.
3. We prove the convergence of our algorithm and show strong empirical results across a variety of benchmark datasets.

Thank you very much for your valuable feedback. We highly appreciate the comments and suggestions for improvement and will incorporate them into our revised manuscript. The reply to the questions is enclosed below.

How to choose model hyper-parameters in practice?

Ans: While the model has multiple hyperparameters, the most critical ones are $\alpha$ and $\beta$, which govern the clustering-based objective function $O_{cluster}$. Other key hyperparameters include the number of iterations (corresponding to the number of layers in the GNN) and the hidden dimension, similar to other GNNs.

Experiments in Section 4.5.2, along with the new sensitivity analysis for other hyperparameters in Appendix E.7 (Figure 10) show that the model performance is stable in the neighbourhood of the optimal hyperparameters and not sensitive to small changes.

The proposed model seems difficult to train and converge despite Theorem 3.3 can provide some guarantee for convergence. I'm not sure if the model can converge only in a very narrow range of hyperparameters,

Ans: After reviewing the experimental logs, we found that the model successfully converges for all hyperparameter configurations explored in 12 out of the 14 datasets. For the Cornell5 dataset, the model converges for 82% of the hyperparameter configurations we tested. For the Minesweepers dataset, the model converges in all cases except when $\alpha = 1$.

the code is not open-sourced.

Ans: The code is proprietary, and we need internal clearance to release it publicly.

Complexity Analysis: I suggest that the authors keep the original complexity with these hyperparameters, and then provide a simplified complexity when these hyperparameters are considered as constants.

Ans: Thanks for your suggestion. We have revised it in the paper accordingly.

Training time, Loss curves

Ans: Thank you for your suggestion. In response, we have included the training time (Tables 20–22) and loss curves (Figure 11) in Appendix E.7.

The loss curves clearly demonstrate the model’s convergence.

Regarding training time, the model requires the same number of steps as other GNN models. However, each step takes longer compared to classical GCN. For your convenience, we have also summarized the results here.

We measured the average training time per step on the three largest datasets used in our experiments, varying |$\Omega$|. The training time ranges from 3x to 5x that of GCN, indicating reasonable time for convergence.