Differentiable Cluster Graph Neural Network

Authors: Yanfei Dong, Mohammed Haroon Dupty, Lambert Deng, Zhuanghua Liu, Yong Liang Goh, Wee Sun Lee
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Graph Representation Learning, Node Classification

Abstract:
Graph Neural Networks often struggle with long-range information propagation and 
local heterophilous neighborhood aggregation. Inspired by the observation that cluster patterns manifest at  global and local levels, we propose to tackle both challenges with a unified framework that incorporates a clustering inductive bias into the message passing mechanism, using additional cluster-nodes.
Central to our approach is the formulation of an optimal transport based clustering objective. 
However, optimizing this objective in a differentiable way is non-trivial.
To navigate this, we adopt an iterative process, alternating between solving for the cluster assignments and updating the node/cluster-node embeddings. 
Notably, our derived optimization steps are themselves simple yet elegant message passing steps operating seamlessly on a bipartite graph of nodes and cluster-nodes.
Our clustering-based approach can effectively capture both local and global information,  
demonstrated by extensive experiments on  heterophilous and homophilous datasets.

Decision: reject
Reviewer scores: 6, 3, 8, 5

Reviews and discussion:
<thread>
creation date:
1730042643146

thread_type:
official_review

<thread_object>
creator: reviewer_wyzz

<content>
summary:
This paper incorporates a clustering inductive bias, combining nodes with "cluster nodes" in a bipartite structure and leveraging optimal transport for differentiable clustering. The framework iteratively optimizes node and cluster-node embeddings and integrates clustering directly within message passing, effectively capturing both global and local patterns.

strengths:
1. This work integrates clustering into message passing, allowing for both global and local pattern capture, which is effective for diverse graphs.
2.  This work demonstrates effectiveness on multiple datasets.

weaknesses:
1. The author claims that facilitating long-range interactions across distant nodes. Thus it should be tested on long-range graph datasets in [1].
2. The proposed method does not achieve the best performance in all cases in Table 2. More analysis on why performing poorly should be added.
3. [2] and [3] are related to this work. I think quoting them is needed.
4. The OT-based clustering and iterative optimization may add implementation complexity.

[1] Dwivedi, Vijay Prakash, et al. "Long range graph benchmark." Advances in Neural Information Processing Systems 35 (2022): 22326-22340.
[2] Kosmala, Arthur, et al. "Ewald-based long-range message passing for molecular graphs." International Conference on Machine Learning. PMLR, 2023.
[3] Chen, Dexiong, Till Hendrik Schulz, and Karsten Borgwardt. "Learning Long Range Dependencies on Graphs via Random Walks." arXiv preprint arXiv:2406.03386 (2024).

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730200797665

thread_type:
official_review

<thread_object>
creator: reviewer_29us

<content>
summary:
The paper proposes a differentiable cluster GNN to deal with the long-rage information propagation and local heterophilous neighborhood aggregation problem in graph domain. Specifically, the framework considers a clustering inductive bias into the message propagation by using additional cluster-nodes. Besides, authors adopt an iterative process to optimize the cluster assignments and node/cluster-node embeddings. Extensive experimental results show the effectiveness of the proposed framework.

strengths:
1.	The paper addresses two critical challenges—over-squashing and heterophilous neighborhood aggregation with a unified framework.
2.	The iterative optimization with soft cluster assignment makes it possible to learn both node and cluster-node embeddings efficiently.
3.	Experimental results are sufficient to demonstrate the effectiveness of the proposed model.

weaknesses:
1.	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.
2.	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. 
3.	The novelty of directly integrate clustering into the message-passing mechanism is somehow weak.

questions:
1.	The authors mention “cluster patterns” many times, but it is unclear what the definition of cluster patterns is?
2.	How does the construction of the bipartite graph scale for extremely large datasets?
3.	The paper uses soft cluster assignments but it lacks the sensitivity analysis of the entropic regularization \lambda and the number of clusters?
4.	From the ablation studies, the contributions of local and global clustering vary. It would be better to provide further intuition or guidelines on when one should prioritize local or global clusters for new datasets.
5.	As the bipartite graph grows with the addition of cluster-nodes, what are the memory implications?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730677042009

thread_type:
official_review

<thread_object>
creator: reviewer_dtqj

<content>
summary:
This paper proposes a GNN that uses cluster-based messaging passing to address the over-squashing and heterophily problems in graph representation learning.The author claims that their cluster-based method (DC-GNN) can handle both long-range dependencies and heterophilous aggregation, by projecting graphs and node neighbors into a bipartite graph of global clusters and local clusters. DC-GNN is different than the current methods by taking the bipartite graph as input instead of using the adjacency or graph Laplacian in the network.

strengths:
1. Converting the graph structure (adjacency or graph Laplacian) into a bipartite graph as GNN input is interesting.

weaknesses:
1. No model access, no code access. (major)

2. 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)

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

questions:
see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730711795432

thread_type:
official_review

<thread_object>
creator: reviewer_6te7

<content>
summary:
This paper presents a differentiable end-to-end clustering-based graph neural network for node classification tasks. The proposed model attempts to address over-squashing and heterogeneity. The model is carefully designed to make it differentiable and the authors provide theoretical guarantees on convergence and time complexity.

strengths:
1. The paper is clearly written and easy to read.
2. The proposed end-to-end differentiable model is convincing and the proposed model is trying to solve the important problems encountered in graph representation learning models such as over-squashing and heterophily.
3. Experimental results show that the model works well and experimental details are provided in the appendix.

weaknesses:
1. The model has multiple hyperparameters, which is very confusing for the potential user of the proposed model to select the optimal hyperparameters.
2. 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, and the code is not open-sourced.
3. $|\Omega|$ can not be removed from asymptotic time complexity $O(T|\mathcal{V}||\Omega|)$ simply because of $|\Omega| \ll |\mathcal{V}|$. ). 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. I suggest that the authors report in their experiments the training time and running time of DCGNN in comparison with classical models such as GCN.
4. For this reason and concerns about convergence speed, I am worried about the actual training-to-convergence time might be longer than expect. I note that run times are provided in Appendix D.3, but I would expect the authors to report training times and loss curves.

questions:
1.  How to choose model hyper-parameters in practice?
2. I expect the authors to provide the training time and loss curves for the model.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732372055526

thread_type:
official_comment

<thread_object>
creator: area_chair_dahb

<content>
comment:
Dear Reviewers,

The authors have uploaded their rebuttal. Please take this opportunity to discuss any concerns you may have with the authors.

Best regards,
AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a differentiable cluster-based GNN (DC-GNN) to address over-squashing and heterophily issues in graph neural networks. It integrates clustering into the message-passing mechanism, optimizing both node and cluster-node embeddings iteratively, and provides theoretical guarantees on convergence. The authors present experimental results demonstrating the model’s effectiveness across multiple datasets.

While the proposed DC-GNN model shows promising results, the reviewers have identified several weaknesses that need to be addressed:

1. The model's requirement for additional nodes and updates regarding clustering and assignment results in inefficiencies in both time and memory usage. This significantly limits its ability to handle large-scale datasets, making the trade-off between efficiency and performance unfavorable.
2. The paper lacks a comprehensive analysis of the convergence speed. The model may require more training rounds than initially expected. Additionally, no comparison of convergence behavior has been made between the proposed model and the baseline GNNs.
3. The experimental results are not convincing, as some baseline results are lower than commonly expected benchmarks. The model's improvement, particularly on heterophilic graphs, appears marginal. Additionally, the necessary artifact of the work is not submitted promptly for checking and reproduction.

Based on these weaknesses, we recommend rejecting this paper. We hope this feedback helps the authors improve their paper.