Differentiable Cluster Graph Neural Network

Yanfei Dong 1 2 Mohammed Haroon Dupty 2 Lambert Deng 1 Zhuanghua Liu 2 Yong Liang Goh 2
Wee Sun Lee 2

Abstract
Graph Neural Networks often struggle with longrange information propagation and may underperform in the presence of heterophilous neighborhoods. We address both of these challenges witha 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 optimaltransport 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 thecluster assignments and updating the node/clusternode 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. Ourclustering-based approach can effectively capture
both local and global information, demonstrated
by extensive experiments on both heterophilous
and homophilous datasets.

Figure 1: On the left is an instance where distant nodes are similar
to each other. On the right is the heterophilous ego-neighborhoodof node A where cluster patterns appear.

the graph’s bottlenecks, diminishing its impact on the target nodes. Second, some graphs exhibit heterophily, whereconnected nodes are likely to be dissimilar. In such cases,
aggregating information from the dissimilar neighbors could
potentially be harmful and hinder the graph representation
learning performance [11], [12].
In this paper, we focus on the task of supervised node classification and explore clustering as an inductive bias to address
both challenges. We observe that cluster patterns appear
globally when nodes that are far apart in the graph have similar features (see Fig. 1). By clustering nodes into multiple
global clusters based on their features, we can establish connections between these distant nodes. Additionally, clusters
may also be present locally among a node and its neighbours in the graph. Particularly for heterophilic graphs,
there are likely more than one cluster in the local neighbourhood. Leveraging these local clusters for information
aggregation, rather than across the entire neighborhood atonce, can potentially help to avoid the problems caused by
the heterophilic nature of the graph.

1. Introduction
Graph Neural Networks (GNNs) have emerged as prominent models for learning node representations on graphstructured data. Their architectures predominantly adhere
to the message passing paradigm, where node embeddings
are iteratively refined using features from its adjacent neighbors [1]–[3]. While this message passing paradigm has
proven effective in numerous applications [4], [5], two
prominent challenges have been observed. First, long-range
information propagation over a sparse graph can be challenging [6]–[8]. Expanding the network’s reach by increasing
the number of layers is often suboptimal as it could encounter issues such as over-squashing [9], [10], where valuable long-range information gets diluted as it passes throughTo embed the clustering inductive bias, we propose theuse of a differentiable clustering-based objective function
consisting of a weighted sum of global and local clusteringterms. The global objective encourages clustering on all
the nodes in the graph, while the local objective does so
on subsets of nodes, where each subset consists of a nodein the graph and its immediate neighbors. Optimizing theobjective function would produce a set of node embeddingsthat can then be used for classifying the nodes in the graph.

1
PayPal 2 National University of Singapore. Correspondence to:
Yanfei Dong <yanfei.dong43@gmail.com>.

To optimize the implicit clustering-based objective function, we employ a block coordinate descent approach byiteratively, (1) solving for a soft cluster assignment matrix
that probabilistically assigns a node to a cluster, followedby, (2) updating the node and cluster embeddings given the

Published at the 2 nd Differentiable Almost Everything Workshop
at the 41 st International Conference on Machine Learning, Vienna, Austria. July 2024. Copyright 2024 by the author(s).

1Differentiable Cluster Graph Neural NetworkPwith it. Hence, |C| = |Ω| + i∈V |Γi |. An illustration of
bipartite graph construction is provided in Appendix. D.

cluster assignment matrix. We view the first step of solving
for the assignment matrix as an Optimal Transport (OT)
problem [13], which aims to find the most cost-effective
way to move from one probability distribution to another.
In our context, the cost is defined as the distance between
nodes and cluster-centroids, and the goal is to transport
nodes to cluster centroids with minimum cost. We adopt theentropic regularized Sinkhorn distance [14] approximation
for solving the OT problem. This approximation utilizes
differentiable operations, ensuring end-to-end learning. For
the second step of updating the node and cluster embeddings, we derive a closed-form solution that minimizes theobjective function given the assignment matrix. The derived
algorithm can be viewed as a message passing algorithm ona bipartite graph with an additional set of cluster-nodes. The
cluster-nodes represent cluster centroids both globally of theentire graph and locally of each neighborhood. Importantly,
our message-passing steps act as optimization steps thatenforce the clustering inductive bias.

There are three components in our Diffentiable Cluster
Graph Neural Network (DC-GNN) architecture:
X = Transform(X̂)
Z = DC-MsgPassing(G, X)
Y = Readout(Z)Given X̂ as input node features, we first transform it with alearnable input transformation function to produce X. The
transformed features are then put through the clusteringbased message passing function to produce node embeddings Z. A learnable readout function is then used on Z
to produce the final output Y . Then, DC-GNN is trained
end-to-end with a loss function Ltrain via backpropagation.
At the core of our design is the iterative DC-MsgPassing
procedure, an implicit optimization algorithm that optimizes
a clustering-based objective function Lλcluster .

We name our method Differentiable Cluster Graph Neural
Network (DC-GNN) and show its convergence. Additionally, both types of cluster-nodes can be viewed as providing
new pathways among the original nodes. This helps tolower the graph’s total effective resistance, which is usefulin mitigating oversquashing [15].

2.2. Clustering-based objective function Lcluster
In this work, we aim to address over-squashing and heterophily by embedding a clustering inductive bias into thedesign of the GNN. One way to achieve this is by optimizing a clustering-based objective function. Motivated by
the theory of optimal transport, we propose a novel softclustering-based objective function.

DC-GNN is efficient and has a linear complexity with respect to the graph size (Appendix. F.1). We carry out comprehensive experiments on a variety of datasets, including
both heterophilous and homophilous types. The results
underscore the efficacy of our method, with our approachattaining state-of-the-art performance in multiple instances.

We conceptualize the cluster assignment problem as an optimal transport problem, where the cost is defined as the
distance between the embeddings of nodes and their cluster
centroids. Therefore, we propose to minimize the overall cost, weighted by the soft cluster assignment matrix P
which indicates the amount of assignment from a node toa cluster. Specifically, we have a single global soft cluster
assignment matrix P Ω ∈ R|V|×|Ω| and local soft cluster+
assignment matrices P Γi ∈ R|Ni |×|Γi | for each node i. Letd(u, v) represent the distance between two vectors u and v,
zi be the node embeddings to be learnt for each node i ∈ V,
xi be the node features after an initial transformation by a
Γimultilayer perceptron, and cΩ
j , cj be the embeddings ofthe j th global and local cluster-node respectively. Then we
define our objective function Lcluster as

2. Methodology
In this section, we introduce our unified clustering-based
GNN message passing method to address both long-range
interactions and heterophilous neighborhood aggregation.
2.1. DC-GNN formulation
We begin by constructing a bipartite graph, denoted as G =(V, C, E). This bipartite graph is derived from the originalgraph G = (V, E) and comprises two distinct sets of nodes.
The first set, V, is a direct copy of the nodes V from theoriginal graph. The second set, C, consists of cluster nodes
divided into two categories: global clusters (Ω) and local
clusters (Γ). In this bipartite graph, each node from theglobal clusters Ω connects to all nodes in V, facilitating
long-range interactions across distant nodes. Meanwhile,each node from the local clusters Γ is associated with a
specific node i in V, and connected to its ego-neighborhood,which includes node i and its one-hop neighbors. For anode i in V, Γi represents the set of local clusters associatedLcluster = αXXPijΩ d(zi , cΩj )+ β{z

global clustering+ (1 − α)d(zi , xi )i∈Vi∈V j∈Ω

|

X

X

}

X

|

X

{z

node fidelity}Γid(zu , cΓj i )
Puj

(1)

i∈V u∈i∪N (i) j∈Γi|{zlocal clustering}

The global clustering part optimizes the OT distance between node embeddings and global cluster-node embed2

Differentiable Cluster Graph Neural Network

dings. The local clustering term optimizes the OT distance between the embeddings of nodes and local clusternodes within each ego-neighborhood. The scalar parameterα ∈ [0, 1] is a balancing factor between the two terms.
Furthermore, the node fidelity term encourages the node
embeddings to retain some information from the original
node features [16], [17].

the optimal transport distance with additional entropic regularization, where λ > 0. Formally,⟨PλΩ , M ⟩, where PλΩ = arg min ⟨P Ω , M ⟩ −P Ω ∈U (u,v)

1h(P Ω ).
λ(3)

The benefit of having this entropic regularization termh(P Ω ) is that the solution PλΩ∗ now has the form PλΩ∗ =U BV [14], where B = e−λM , and U and V are diagonal
matrices. Now the OT problem reduces to the classicalmatrix scaling problem, for which the objective is to determine if there exist diagonal matrices U and V such thatthe ith row of the matrix U BV sums to ui and the j th column of U BV sums to vj . Since e−λM is strictly positive,
there exists a unique PλΩ∗ that belongs to U (u, v) [19], [20],which can be obtained by the well-known Sinkhorn–Knopp
algorithm [20], [21].

2.3. DC-MsgPassing: optimization via message passing
Since conventional OT solvers can be computationally prohibitive [18], we adopt the entropy regularized version of the
OT distance that is designed for efficiency and offers a good
approximation of OT distance [14].Specifically, let h(P )be the entropy of the assignment matrix P , we propose thefollowing refined objective function,α(1 − α) X
Lλcluster := Lcluster − h(P Ω )−h(P Γi ). (2)λλTo obtain PλΩ∗ , we run the Sinkhorn–Knopp algorithm
which iteratively updates the matrix B by scaling each row
of B by the respective row-sum, and each column of B by
the respective column-sum. Formally, we havei∈V

Direct optimization of Lλcluster as a training objective is
intractable due to the presence of unobserved assignment
matrices P Ω and P Γi , since we cannot compute Eq. (2) without estimating the cluster assignment values. To overcome
this, we propose an iterative block coordinate descent algorithm called DC-MsgPassing that alternatively update
the assignment matrices P Ω , P Γi and embeddings Z, C.

(t)

(t−1)

Bij
(t)
Bij = P (t−1) ui ,
j Bij

(t+1)

Bij

Bij
= P (t) vj .
i Bij

(4)

After T steps, we update PijΩ by the value of Bij . Similarly,
we update P Γi in the local clustering term. The scaling
operations in Sinkhorn–Knopp are fully differentiable, enabling end-to-end learning.

2.3.1. A SSIGNMENT UPDATE
Update for assignment matrices P Ω , P Γi : With nodeand cluster-node embeddings kept constant, we aim to update the P Ω , P Γi minimizing Lcluster . We approach thiscluster assignment problem from the perspective of optimal transport theory, and use P Ω as an example without loss of generality. Our objective is to determine|V|×|Ω|
for a
the optimal assignment matrix P Ω∗ ∈ R+
|V|×|Ω|
given cost matrix M ∈ R+
, aligning with a target clustering distribution. Assuming a uniform distribution of data points across all clusters, we aim
 to finda mapping from u⊤ = |V|−1 · · · |V|−1 1×|V| tov⊤ = |Ω|−1 · · · |Ω|−1 1×|Ω| , minimizing the overall cost. To formalize, optimizing Lcluster with respect
to P Ω is tantamount to solving: minP Ω ∈U (u,v) ⟨P Ω , M ⟩,2.3.2. E MBEDDINGS UPDATEWith the updated assignment matrices P Ω , P Γi , we now
derive the update functions for cluster-node and node embeddings. If we choose the distance function d(·) to be
the squared Euclidean norm, Lλcluster is a quadratic modelof node embeddings zi , cj . Then we can update the embeddings by minimizing the Lλcluster with respect to eachvariable, which admits the following closed-form solution:
Update for cluster-node embeddings C:
C = diag(k)P ⊤ Z,

|V|×|Ω|
where U (u, v) = {P ∈ R+
: P 1|Ω| = u, P ⊤ 1|V| =Ω·⟩ is the Frobenius dot-product, and ⟨P , M ⟩ =v}.
P ⟨·,PΩΩΩi∈Vj∈Ω Pij d(zi , cj ). Importantly, Mij = d(zi , cj )can be seen as the cost of assigning node i to cluster j, andPijΩ indicates the amount of assignment from node i to cluster j. This is a classical optimal transport problem.While
such problems are typically solved via linear programming
techniques, these approaches are computationally expensive [18]. To overcome it, we opt for the Sinkhorn distance [14] instead, which offers a good approximation to(5)

Update for node embeddings Z:ihXP̂ Γu C Γu , (6)Z = γ βX + αP Ω C Ω + (1 − α)u∈Ni+where k⊤=|V|×|C||Ω|1|Ω| ; |Γi |1|Γi | ; · · · ; |Γ|V| |1|Γi | 1×|C| ,P ∈ R+
is the overall assignment matrix, γ =|V|×|Γu |−1(α|V| + β + 1 − α)−1 is a constant, and P̂ Γu ∈ R+
3

Differentiable Cluster Graph Neural Network

Table 1: Classification performance comparison across various heterophilous and homophilous datasets.
Heterophilous

Homophilous

Penn94

GeniusCornell5

Amherst41

US-election

Wisconsin

Cora

Citeseer

PubmedMLP
GCN
GAT
MixHopGCNII
H2 GCNWRGAT
GPR-GNN
GGCN
ACM-GCN
LINKX
GloGNN++73.61 (0.40)
82.47 (0.27)
81.53 (0.55)
83.47 (0.71)
82.92 (0.59)
81.31 (0.60)
74.32 (0.53)
81.38 (0.16)
73.62 (0.61)
82.52 (0.96)
84.71 (0.52)
85.74 (0.42)

86.68 (0.09)
87.42 (0.37)
55.80 (0.87)
90.58 (0.16)
90.24 (0.09)
OOM
OOM
90.05 (0.31)
OOM
80.33 (3.91)
90.77 (0.27)
90.91 (0.13)

68.86 (1.83)
80.15 (0.37)
78.96 (1.57)
78.52 (1.22)
78.85 (0.78)
78.46 (0.75)
71.11 (0.48)
73.30 (1.87)
71.35 (0.81)
78.17 (1.42)
83.46 (0.61)
83.96 (0.46)

60.43 (1.26)
81.41 (1.70)
79.33 (2.09)
76.26 (2.56)
76.02 (1.38)
79.64 (1.63)
62.59 (2.46)
67.00 (1.92)
66.53 (1.61)
70.11 (2.10)
81.73 (1.94)
81.81 (1.50)

81.92 (1.01)
82.07 (1.65)
84.17 (0.98)
85.90 (1.55)
82.90 (0.29)
85.53 (0.77)
84.45 (0.56)
84.49 (1.09)
84.71 (2.60)
85.14 (1.33)
84.08 (0.67)
85.48 (1.19)

85.29 (3.31)
51.76 (3.06)
49.41 (4.09)
75.88 (4.90)
80.39 (3.40)
87.65 (4.98)
86.98 (3.78)
82.94 (4.21)
86.86 (3.29)
88.43 (3.22)
75.49 (5.72)
88.04 (3.22)

75.69 (2.00)
86.98 (1.27)
87.30 (1.10)
87.61 (0.85)
88.37 (1.25)
87.87 (1.20)
88.20 (2.26)
87.95 (1.18)
87.95 (1.05)
87.91 (0.95)
84.64 (1.13)
88.33 (1.09)

74.02 (1.90)
76.50 (1.36)
76.55 (1.23)
76.26 (1.33)
77.33 (1.48)
77.11 (1.57)
76.81 (1.89)
77.13 (1.67)
77.14 (1.45)
77.32 (1.70)
73.19 (0.99)
77.22 (1.78)

87.16 (0.37)
88.42 (0.50)
86.33 (0.48)
85.31 (0.61)
90.15 (0.43)
89.49 (0.38)
88.52 (0.92)
87.54 (0.38)
89.15 (0.37)
90.00 (0.52)
87.86 (0.77)
89.24 (0.39)

DC-GNN86.69 (0.22)

91.70 (0.08)

84.68 (0.24)

82.94 (1.59)

89.59 (1.60)

91.67 (1.95)

89.13 (1.18)

77.93 (1.82)

91.00 (1.28)

is the broadcasted local assignment matrix from P Γu ∈|N + |×|Γu |. See Appendix C.2, C.3 and C.4 for notation
R+ u
and full derivation. Intriguingly, this closed-form solution
reveals that Z is updated by a linear combination of global
and local cluster-node embeddings, weighted by cluster assignment probabilities. α balances the influence of local
and long-range interactions while β scales the original nodefeatures that provide the initial residual [17].

details are in App. G.6 and G.7. We also conduct experiments on additional heterophilous datasets (App.G.1), insparse label settings (App.G.2), oversquashing alleviation(App.G.3) and ablation studies (App.G.4).
3.1. Comparison with baselines on heterophilous graphs
We conduct experiments on heterophilous datasets wherelong-range information is beneficial and neighborhood aggregation needs special attention. We achieve state-of-theart on all six datasets in Tab. 1. The performance uplift is especially pronounced on US-election and Wisconsin, where
it outperforms by more than 3%. We also achieve state-ofthe-art on four other heterophilous graphs(App. Tab. 3).

Remark. Viewing cluster assignment probabilities asedge weights, Eq. (5) serves as message passing from nodes
to cluster-nodes and Eq. (6) represents the message passing
from cluster-nodes back to original nodes.
In summary, DC-MsgPassing is the key to our method.
Each iteration of DC-MsgPassing is one optimization
step towards minimizing Lλcluster . Thus our message passing
mechanism provides the needed inductive bias in learning
the local and global clusters present in the data, while simultaneously learning node embeddings using the clustering
information. DC-MsgPassing is generally well behaved,
converging when enough iterations are performed.

3.2. Comparison with baselines on homophilous graphs
We further run DC-GNN on three homophilous datasets,
where it outperforming both general-purpose and heterophilous baselines (Tab. 1). Our strong performance on
both homophilous and heterophilous graphs shows that DCGNN is flexible and adaptive, capable of effective information aggregation on various homophily levels.

Theorem 2.1 (Convergence of DC-MsgPassing). Assuming the Sinkhorn–Knopp algorithm is run to convergence ineach iteration, for any λ > 0, the value of Lλcluster produced
by DC-MsgPassing is guaranteed to converge.

4. Conclusion
This paper tackles two challenges in GNNs: long-range
information propagation and heterophilous neighborhood
aggregation. We proposed a novel differentiable frameworkthat seamlessly embeds a clustering inductive bias into themessage passing mechanism, facilitated by the introductionof cluster-nodes. Central to our approach is an optimal transport based clustering objective, which we optimize throughan iterative strategy, alternating between the computationof cluster assignments and the refinement of node/clusternode embeddings. Importantly, the derived optimization
steps effectively function as message passing operations
on the bipartite graph. Our effectiveness in capturing both
local nuances and global structures is validated by extensive
experiments on various datasets.

Proof can be found in the Appendix C.1.
2.4. Training objective function Ltrain
Our task is supervised node-classification. We use cross entropy loss Lce to train DC-GNN along with two regularizing
losses to facilitate clustering: Ltrain = Lce + ω1 Lortho +ω2 Lsim . (See App. E for Lortho and Lsim ).

3. Experiments
In this section, we empirically validate the capabilities of
DC-GNN . Dataset, baselines, implementation and training4Differentiable Cluster Graph Neural Network

References
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]
[14]

[15]

[16]

[17]

[18]

T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” arXiv preprint
arXiv:1609.02907, 2016.
M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized
spectral filtering,” NeurIPS, vol. 29, pp. 3844–3852, 2016.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, andG. E. Dahl, “Neural message passing for quantum chemistry,” in International conference on machine learning,
PMLR, 2017, pp. 1263–1272.
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton,
and J. Leskovec, “Graph convolutional neural networks forweb-scale recommender systems,” in Proceedings of the24th ACM SIGKDD international conference on knowledge
discovery & data mining, 2018, pp. 974–983.
J. Zhou, G. Cui, S. Hu, et al., “Graph neural networks:
A review of methods and applications,” AI Open, vol. 1,
pp. 57–81, 2020.
Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graphconvolutional networks for semi-supervised learning,” inProceedings of the AAAI conference on artificial intelligence, vol. 32, 2018.
K. Zhou, Y. Dong, K. Wang, et al., “Understanding andresolving performance degradation in deep graph convolutional networks,” in Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021, pp. 2728–2737.
T. K. Rusch, M. M. Bronstein, and S. Mishra, “A survey onoversmoothing in graph neural networks,” arXiv preprint
arXiv:2303.10993, 2023.
U. Alon and E. Yahav, “On the bottleneck of graph neuralnetworks and its practical implications,” arXiv preprint
arXiv:2006.05205, 2020.
J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong,and M. M. Bronstein, “Understanding over-squashingand bottlenecks on graphs via curvature,” arXiv preprint
arXiv:2111.14522, 2021.
J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, andD. Koutra, “Beyond homophily in graph neural networks:
Current limitations and effective designs,” Advances in
Neural Information Processing Systems, vol. 33, pp. 7793–
7804, 2020.
J. Zhu, R. A. Rossi, A. Rao, et al., “Graph neural networks
with heterophily,” in Proceedings of the AAAI Conferenceon Artificial Intelligence, vol. 35, 2021, pp. 11 168–11 176.
C. Villani et al., Optimal transport: old and new. Springer,
2009, vol. 338.
M. Cuturi, “Sinkhorn distances: Lightspeed computationof optimal transport,” Advances in neural information processing systems, vol. 26, 2013.
M. Black, Z. Wan, A. Nayyeri, and Y. Wang, “Understanding oversquashing in gnns through the lens of effective
resistance,” in International Conference on Machine Learning, PMLR, 2023, pp. 2528–2547.
J. Klicpera, A. Bojchevski, and S. Günnemann, “Predict
then propagate: Graph neural networks meet personalized
pagerank,” arXiv preprint arXiv:1810.05997, 2018.
M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, “Simple
and deep graph convolutional networks,” in ICML, PMLR,
2020, pp. 1725–1735.

[19]

[20]

[21]

[22]

[23]

[24]

[25]
[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

5

O. Pele and M. Werman, “Fast and robust earth mover’s
distances,” in 2009 IEEE 12th international conference on
computer vision, IEEE, 2009, pp. 460–467.
M. Menon, “Matrix links, an extremization problem, andthe reduction of a non-negative matrix to one with prescribed row and column sums,” Canadian Journal of Mathematics, vol. 20, pp. 225–232, 1968.
R. Sinkhorn, “Diagonal equivalence to matrices with prescribed row and column sums,” The American Mathematical Monthly, vol. 74, no. 4, pp. 402–405, 1967.
R. Sinkhorn and P. Knopp, “Concerning nonnegative matrices and doubly stochastic matrices,” Pacific Journal of
Mathematics, vol. 21, no. 2, pp. 343–348, 1967.
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral
networks and locally connected networks on graphs,” arXiv
preprint arXiv:1312.6203, 2013.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio,and Y. Bengio, “Graph attention networks,” arXiv preprint
arXiv:1710.10903, 2017.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “Howpowerful are graph neural networks?” arXiv preprint
arXiv:1810.00826, 2018.
C. Cai and Y. Wang, “A note on over-smoothing for graphneural networks,” arXiv preprint arXiv:2006.13318, 2020.
P. K. Banerjee, K. Karhadkar, Y. G. Wang, U. Alon, and
G. Montúfar, “Oversquashing in gnns through the lens of
information contraction and graph expansion,” in 2022 58th
Annual Allerton Conference on Communication, Control,and Computing (Allerton), IEEE, 2022, pp. 1–8.
K. Karhadkar, P. K. Banerjee, and G. Montúfar, “Fosr:
First-order spectral rewiring for addressing oversquashingin gnns,” arXiv preprint arXiv:2210.11790, 2022.
K. Nguyen, N. M. Hieu, V. D. Nguyen, N. Ho, S. Osher, and T. M. Nguyen, “Revisiting over-smoothing andover-squashing using ollivier-ricci curvature,” in International Conference on Machine Learning, PMLR, 2023,
pp. 25 956–25 979.
A. Arnaiz-Rodrı́guez, A. Begga, F. Escolano, and N. M.
Oliver, “Diffwire: Inductive graph rewiring via the lovász
bound,” in The First Learning on Graphs Conference, 2022.
E. Chien, J. Peng, P. Li, and O. Milenkovic, “Adaptive universal generalized pagerank graph neural network,” arXiv
preprint arXiv:2006.07988, 2020.
G. Fu, P. Zhao, and Y. Bian, “P-laplacian based graphneural networks,” in International Conference on Machine
Learning, vol. 162, PMLR, 2022, pp. 6878–6917.
Y. Dong, K. Ding, B. Jalaian, S. Ji, and J. Li, “Adagnn:
Graph neural networks with adaptive frequency response
filter,” in International Conference on Information andKnowledge Management, ACM, 2021, pp. 392–401.
J. Xu, E. Dai, X. Zhang, and S. Wang, “Hp-gmn: Graphmemory networks for heterophilous graphs,” arXiv preprint
arXiv:2210.08195, 2022.
D. Jin, Z. Yu, C. Huo, et al., “Universal graph convolutional
networks,” in Advances in Neural Information Processing
Systems, 2021, pp. 10 654–10 664.
X. Li, R. Zhu, Y. Cheng, et al., “Finding global homophilyin graph neural networks when meeting heterophily,” arXiv
preprint arXiv:2205.07308, 2022.

Differentiable Cluster Graph Neural Network
[36]

[37]

[38]
[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

S. Abu-El-Haija, B. Perozzi, A. Kapoor, et al., “Mixhop:
Higher-order graph convolutional architectures via sparsified neighborhood mixing,” in ICML, PMLR, 2019, pp. 21–
29.
H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang,“Geom-gcn: Geometric graph convolutional networks,”
arXiv preprint arXiv:2002.05287, 2020.
J. Zhu, R. A. Rossi, A. Rao, et al., “Graph neural networks
with heterophily,” arXiv preprint arXiv:2009.13566, 2020.
D. Lim, F. Hohne, X. Li, et al., “Large scale learning on
non-homophilous graphs: New benchmarks and strong simple methods,” Advances in Neural Information Processing
Systems, vol. 34, pp. 20 887–20 902, 2021.
Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra,“Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks,” arXiv preprint
arXiv:2102.06462, 2021.
A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller,“Graph clustering with graph neural networks,” Journalof Machine Learning Research, vol. 24, no. 127, pp. 1–21,
2023.
F. Tian, B. Gao, Q. Cui, E. Chen, and T.-Y. Liu, “Learning
deep representations for graph clustering,” in Proceedingsof the AAAI conference on artificial intelligence, vol. 28,
2014.
F. M. Bianchi, D. Grattarola, and C. Alippi, “Spectral clustering with graph neural networks for graph pooling,” inInternational Conference on Machine Learning, PMLR,
2020, pp. 874–883.
A. Duval and F. Malliaros, “Higher-order clustering andpooling for graph neural networks,” in Proceedings ofthe 31st ACM International Conference on Information& Knowledge Management, 2022, pp. 426–435.
J. Feng, Y. Chen, F. Li, A. Sarkar, and M. Zhang, “Howpowerful are k-hop message passing graph neural networks,” Advances in Neural Information Processing Systems, vol. 35, pp. 4776–4790, 2022.
B. Saha, D. Krotov, M. J. Zaki, and P. Ram, “End-to-end
differentiable clustering with associative memories,” inInternational Conference on Machine Learning, PMLR,
2023, pp. 29 649–29 670.
M. Caron, P. Bojanowski, A. Joulin, and M. Douze, “Deepclustering for unsupervised learning of visual features,”in Proceedings of the European conference on computer
vision (ECCV), 2018, pp. 132–149.
L. Stewart, F. Bach, F. Llinares-López, and Q. Berthet, “Differentiable clustering with perturbed spanning forests,” Advances in Neural Information Processing Systems, vol. 36,
2024.
G. Bécigneul, O.-E. Ganea, B. Chen, R. Barzilay, and T.
Jaakkola, “Optimal transport graph neural networks,” arXiv
preprint arXiv:2006.04804, 2020.
C. Vincent-Cuaz, R. Flamary, M. Corneli, T. Vayer, and
N. Courty, “Template based graph neural network with optimal transport distances,” Advances in Neural Information
Processing Systems, vol. 35, pp. 11 800–11 814, 2022.
L. Yang, J. Gu, C. Wang, et al., “Toward unsupervised
graph neural network: Interactive clustering and embedding via optimal transport,” in 2020 IEEE international
conference on data mining (ICDM), IEEE, 2020, pp. 1358–
1363.

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

6

X. Li, Y. Grandvalet, R. Flamary, N. Courty, and D.
Dou, “Representation transfer by optimal transport,” arXiv
preprint arXiv:2007.06737, 2020.
Z. Zhang, F. Wu, and W. S. Lee, “Factor graph neuralnetworks,” Advances in Neural Information Processing
Systems, vol. 33, pp. 8577–8587, 2020.
Z. Zhang, M. H. Dupty, F. Wu, J. Q. Shi, and W. S. Lee,
“Factor graph neural networks,” Journal of Machine Learning Research, vol. 24, no. 181, pp. 1–54, 2023. [Online].
Available: http://jmlr.org/papers/v24/210434.html.
M. H. Dupty and W. S. Lee, “Neuralizing efficient higher-order belief propagation,” arXiv preprint
arXiv:2010.09283, 2020.
M. H. Dupty, Y. Dong, S. Leng, et al., “Constrained layout generation with factor graphs,” in Proceedings of theIEEE/CVF Conference on Computer Vision and Pattern
Recognition, 2024, pp. 12 851–12 860.
V. G. Satorras and M. Welling, “Neural enhanced belief
propagation on factor graphs,” in International Conference on Artificial Intelligence and Statistics, PMLR, 2021,
pp. 685–693.
K. Yoon, R. Liao, Y. Xiong, et al., “Inference in probabilistic graphical models by graph neural networks,” in2019 53rd Asilomar Conference on Signals, Systems, andComputers, IEEE, 2019, pp. 868–875.
J. Franklin and J. Lorenz, “On the scaling of multidimensional matrices,” Linear Algebra and its applications,vol. 114, pp. 717–735, 1989.
G. W. Soules, “The rate of convergence of sinkhorn balancing,” Linear algebra and its applications, vol. 150, pp. 3–
40, 1991.
D. Chakrabarty and S. Khanna, “Better and simpler error
analysis of the sinkhorn–knopp algorithm for matrix scaling,” Mathematical Programming, vol. 188, no. 1, pp. 395–
407, 2021.
O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, andL. Prokhorenkova, “A critical look at the evaluation of gnns
under heterophily: Are we really making progress?” arXiv
preprint arXiv:2302.11640, 2023.
L. Müller, M. Galkin, C. Morris, and L. Rampášek,“Attending to graph transformers,” arXiv preprint
arXiv:2302.04181, 2023.
M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” arXiv preprint
arXiv:1903.02428, 2019.
J. Jia and A. R. Benson, “Residual correlation in graphneural network regression,” in Proceedings of the 26th
ACM SIGKDD International Conference on Knowledge
Discovery & Data Mining, 2020, pp. 588–598.
Z. Yang, W. Cohen, and R. Salakhudinov, “Revisiting
semi-supervised learning with graph embeddings,” in International conference on machine learning, PMLR, 2016,
pp. 40–48.

Differentiable Cluster Graph Neural Network

A. Notations
All notations are listed in Tab. 2.

B. Related Work
Prominent GNN models typically follow a message passing paradigm that iteratively aggregates information in a node’s
neighborhood [1]–[3], [22]–[24]. This local message passing, however, requires the stacking of multiple layers to pursue
long-range information and can encounter issues such as over-smoothing [6], [8], [25] and over-squashing [9], [10], [26],[27]. To tackle oversquashing, existing works design graph rewiring techniques that change graph topology [10], [27]–[29].
Similar to some existing methods [15], our approach of adding cluster-nodes also changes graph topology and is shown to
reduce effective resistance, thereby helpful in mitigating oversquashing [15].
Additionally, some graphs contain heterophilous neighborhoods, in which traditional aggregation promoting similarity
among neighbors is suboptimal. [11], [12]. There are three types of approaches to address this, including design of high-passfilters in message passing [30]–[32], exploring global neighborhoods [33]–[36], and use of auxiliary graph structures [37]–[40]. Many of these approaches are often computationally expensive and may struggle on homophilous graphs. Our methodseeks to explore global neighborhoods by introducing cluster-nodes as auxiliary structures and conduct clustered aggregation
in local neighborhoods, with linear complexity.
Our work focuses on using a clustering inductive bias to enhance the supervised node classification task. This differs fromtasks like graph clustering [41], [42] and graph pooling [43], [44], which are constrained by graph typology and aim topartition a graph into substructures. Instead, our approach primarily utilizes feature information for global clustering. Unlike
previous methods, we also explore clustering within local neighborhoods, which has not been explored before. Additionally,
we integrate the clustering bias into the message passing mechanism in an end-to-end differentiable framework.
Clustering with a differentiable pipeline has been explored in some works including in unsupervised and self-supervised
settings [45]–[48]. However, these works do not explore application on graph structured data. Central to our approachis an Optimal Transport based clustering objective. OT has been recently applied to graph learning for tasks like graphclassification [49], [50], regularizing node representations [51] and finetuning [52]. However, most of these methods leverage
OT as a separate component and do not integrate it within message passing. Distinct from these approaches, we implicitly
optimize an OT-based clustering objective function via message passing.
Our approach of message passing with additional cluster-nodes can also be viewed as the construction of factor graph neuralnetwork with the cluster-nodes representing factors, which has been effective in learning representation on structured data[53]–[58]. Our approach provides further evidence for the usefulness of factor graph based approaches.

7Differentiable Cluster Graph Neural Network

Table 2: Table for notations.
Variable

Definition

G
G
V
V
E
E
Ni
Ni+
C
Ω
Γ
Γi
C
Z
Y
XinputX
P
PΩ

bipartite graph, denoted as (V, C, E)
original graph, denoted as (V , E)
set of nodes from the original graph G
vertices of G, direct copy of V
set of edges from the original graph G
set of edges in the bipartite graph G
set of one-hop neighbors of node i
node i and its one-hop neighbors (ego-neighborhood of i)set of cluster-nodes in the bipartite graph G
set of global cluster-nodes
set of local cluster-nodes
set of local cluster-nodes associated with Ni+
set of cluster-node embeddings
set of node embeddings
predicted class probabilities
input featurestransformed input features|V|×|C|
overall cluster assignment matrix. P ∈ R+
|V|×|Ω|
global cluster assignment matrix. P Ω ∈ R+

PΓ
d(·)
zi
xi
cΩ
j
cΓj i
α
β
h(·)
P Ω∗
Mij
M
u⊤
v⊤
U (u, v)⟨·, ·⟩
PijΩ
λ
B
U
V
T
k
τ
τ′
Ωτ
L
cτj
ziL
γ
P̂ Γu

|N + |×|Γ |ifor each node i
local cluster assignment matrix. P Γi ∈ R+ i
distance function
node embeddings of node i
node features of node i after initial transformation
node embeddings of j th global cluster-node
node embeddings of j th local cluster-node for Ni+
scalar parameter that balances global and local clustering objectives.
α ∈ [0, 1]
scalar parameter for node fidelity term
entropy function|V|×|Ω|
optimal global soft-assignment matrix. P Ω∗ ∈ R+
cost of assigning node i to cluster jcost matrixu⊤ = |V|−1 · · · |V|−1 1×|V|
 −1

−1
⊤
· · · |Ω| 1×|Ω|
v = |Ω||V|×|Ω|U (u, v) = {P ∈ R+
: P 1|Ω| = u, P ⊤ 1|V| = v}
Frobenius dot productthe amount of assignment from node i ∈ V to cluster j ∈ Ωscalar for entropy regularization
initial value e−λM
diagonal matrix
diagonal matrix
number of iterations for Sinkhorn-Knoppalgorithmk⊤ = |Ω|1|Ω| ; |Γi |1|Γi | ; · · · ; |Γ|V| |1|Γi | 1×|C|class τ for our node classification task
class that is not class τ
set of global cluster-nodes associated with class τ
number of DC-MsgPassing iterations
the j th cluster embedding associated with class τembeddings for node i after L iterations
a constant. γ = (αN −1 + β + 1 − α)−1
|V|×|Γu |broadcasted local cluster assignment matrix fromP̂ Γu ∈ R+
|N + |×|Γ |∥ · ∥FΛ(·)
V+i
P Γu ∈ R+ i
, defined in Eq.(13)
Frobenius norm
similarity function
set of training nodes8Differentiable Cluster Graph Neural Network

C. Proof and derivation
C.1. Proof of Theorem 2.1
To prove Theorem 2.1, we first introduce the following Lemma.
Lemma C.1. Let Lλcluster be the loss function optimized by the DC-MsgPassing algorithm when the optimal transportcomponents are replaced by the entropic regularized versions. Then, Lλcluster is lower-bounded by:
Lλcluster ≥

1
1
1−α X
α
log
log
+
.
+
λ
|V||Ω|
λ|Ni ||Γi |i∈V

Proof. Recall that Ω is the set of global cluster-nodes, and Γi refers to the set of local cluster-nodes associated with a node i.
+
V is a direct copy of the nodes V from the original graph. P Ω ∈ R|V|×|Ω| and P Γi ∈ R|Ni |×|Γi | are the global and local
soft cluster assignment matrices respectively. Ni+ refers to the ego neighborhood of node i.
Let p(P Ω ) be the probability of assignment matrix P Ω and h(P Ω ) be its entropy, we can upper bound its entropy by:1h(P Ω ) = E logp(P Ω )

1(by Jensen’s inequality)≤ log Ep(P Ω )X
1
p(PijΩ )= log(7)p(PijΩ )i∈V,j∈Ω
= log |V| × |Ω| .
(8)

The inequality is due to uniform distribution having the maximum entropy.
Similarly, for local assignment matrices P Γi , we have:h(P Γi ) ≤ log |Ni+ | × |Γi | .

Note that distance d(·, ·) ≥ 0, with the above results we obtain:


XX
X
1
Ω 
PijΩ d(zi , cΩd(zi , xi )+β
Lλcluster = α j ) − h(P )λi∈V j∈Ω
i∈V


X X X
1
Γi

+ (1 − α)Pkj
d(zk , cΓj i ) − h(P Γi )
λ
+
i∈V

k∈Ni

(9)

(10)

(11)

j∈Γi

α
(1 − α) X≥ − h(P Ω ) −h(P Γi )λλ(by d(·, ·) ≥ 0)≥ −(by (8) and (9))

i∈V

=


 (1 − α) X
αlog |Ni+ | × |Γi |
log |V| × |Ω| −
λ
λ
i∈V

1
1
(1 − α) X
α
log
log
+
,
+
λ
|V| × |Ω|
λ|Ni | × |Γi |

(12)

i∈V

which concludes the proof.
By Lemma C.1, there exists a lower bound of Lλcluster . Therefore, to prove the convergence of our algorithm, we only needto show that the loss function is guaranteed to decrease monotonically in each iteration until convergence for the assignment
update step and for the embeddings update step.
9

Differentiable Cluster Graph Neural Network

For the assignment update step, let P Ω be the current assignment from the previous iteration and P Ω∗ be the new assignment
obtained as1
P Ω∗ ∈ arg min ⟨P Ω∗ , M ⟩ − h(P Ω∗ ).
λΩP ∈U (r,c)
The change in the loss function after this assignment step is then given by
Lλcluster (P Ω∗ ) − Lλcluster (P Ω ) ≤ 0,
where the inequality holds by the convergence of Sinkhorn–Knopp algorithm [20], [21], [59]–[61]. Similarly, we haveLλcluster (P Γi ∗ ) − Lλcluster (P Γi ) ≤ 0.
For the embeddings update step, let Z and C be the current embeddings from the previous iteration, and Z ∗ and C ∗ be thenew embeddings obtained by Eq. (5) and Eq. (6). Let the d(·, ·) be the squared Euclidean distance, then since P is a positive
constant in this step, the loss function is convex. Eq. (5) and Eq. (6) are closed form solutions to the loss function, then wehave
Lλcluster (Z ∗ , C ∗ ) − Lλcluster (Z, C) ≤ 0.
Since Lλcluster has a lower bound and it decreases monotonically in each iteration, the value of Lλcluster produced by themessage passing algorithm is guaranteed to converge.
C.2. Broadcasted assignment matrices
Let f : Z × Z → Z be a mapping from the index k of a node in the ego-neighborhood of the node u to the index i of the|N + |×|Γu |same node in the node set V. Let P Γu ∈ R+ u
be the local assignment matrix for the ego-neighborhood of node
|V|×|Γu |asu ∈ V. For any u ∈ V, we define the broadcasted local assignment matrix P̂ Γu ∈ R+
P̂ijΓu =

(

Γu
Pkj
,
0,

if i = f (u, k).
otherwise|V|×|C|

Then, we can define the the overall assignment matrix P ∈ R+h
P = PΩ

P̂ Γ1, where |C| = |Ω| + |Γ| and |Γ| =···iP̂ Γ|V| .

(13)

Pi∈V |Γi |, as(14)Note that each element Pij can be viewed as the edge weights of a node i ∈ V and a specific cluster-node j ∈ C. In simple
words, P includes all the global and local cluster assignment matrices, collated in a single matrix. This allows us to unify themessage passing update in Eq.( 6) for both local and global clustering terms.
C.3. Update for cluster-node embeddings C: derivation of Eq. (5)Without loss of generality, we provide the full derivation for global cluster-node embeddings update function. With squared
Euclidean norm as the distance function, i.e., d(u, v) = ∥u − v∥2 , we can derive that
∂Lλcluster∂ X Ω2P ∥zi − cΩ= Ωj ∥ =0Ω∂cj∂cj i∈V ij
Then we have
2

X
i∈V

PijΩ (cΩj − zi ) = 0

By rearranging the terms
10Differentiable Cluster Graph Neural Network

X

PijΩ cΩj =Since P Ω ∈ U (u, v), we haveP

PijΩ zii∈V

i∈V

Then one has

XPP Ω ziPi∈V ijΩcΩ=ji∈V Pij

1Ωi Pij = |Ω| where |Ω| is the number of global clusters. Therefore,cΩ
j = |Ω|

X

PijΩ zi(15)

i∈V

Similarly, with |Γi | denoting the number of local clusters within the ego-neighborhood of node i, we haveXcΓj i = |Γi |PijΓi zu

(16)

u∈Ni+



Let k⊤ = |Ω|1|Ω| ; |Γi |1|Γi | ; · · · ; |Γ|V| |1|Γi | 1×|C| , where ; denotes concatenation. Then we can combine Eq. (15) andEq. (16) together in one matrix equation,
C = diag(k)P ⊤ Z,
(17)
where the overall assignment matrix P is defined in Eq. (14),C.4. Update for node embeddings Z: derivation of Eq. (6)We provide the full derivation of the node embeddings update function. This manifests as message passing from cluster-nodes
to nodes. With squared Euclidean norm as the distance function, i.e., d(u, v) = ∥u − v∥2 , we can derive that
X X
X
∂Lλcluster
2PijΓu (zi − cj ) = 0
2PijΩ (zi − cj ) + 2β(zi − xi ) + (1 − α)=α∂zi+u∈Ni j∈Γuj∈Ω

From Eq. (18), we obtain
α

X

j∈Ω

PijΩ zi − αXj∈ΩPijΩ cj + βzi − βxi + (1 − α)X Xu∈Ni+ j∈Γu

PijΓu zi − (1 − α)X X

PijΓu cj = 0u∈Ni+ j∈Γu

By rearranging the terms, we have
X X
X
X X
X
PijΓu cj
PijΩ cj + βxi + (1 − α)PijΓu )zi = α
PijΩ + β + (1 − α)(αu∈Ni+ j∈Γuj∈Ω

Since P Ω ∈ U (u, v), we have
(

P

1
Ω
j Pij = |V| . Similarly,

P

P

Γu
1
j∈Γu Pij = |N + | . Therefore, we can deduce that
i

X
X X
X
1
α
+ β + (1 − α)PijΩ cj + βxi + (1 − α)PijΓu cj+ )zi = α
|V|
|N
|
i
+
+
j∈Ω

u∈Ni

With

u∈Ni+ j∈Γuj∈Ωu∈Ni j∈Γu

1u∈Ni+ |N + | = 1, we have
i

(

X X
X
α
PijΓu cj
PijΩ cj + βxi + (1 − α)+ β + 1 − α)zi = α
|V|
+
j∈Ω

u∈Ni j∈Γu

11

(18)

Differentiable Cluster Graph Neural Network

This leads tozi =1PijΓu cj ]PijΩ cj + βxi + (1 − α)
[α
α
+
β
+
1
−
α
|V|
j∈Ω
u∈N + j∈Γu
X X

X

i

Finally, expressing in matrix form admits the following closed-form solution
Z=|V|×|Γu |where P̂ Γu ∈ R+

1

[αP
α
|V| + β + 1 − αΩC Ω + βX + (1 − α)XP̂ Γu C Γu ]u∈Ni+
|N + |×|Γu |is the broadcasted local cluster assignment matrix from P̂ Γu ∈ R+ u

as defined in Eq.(13).

D. Illustration of bipartite graph formulation
We construct a bipartite graph, denoted as G = (V, C, E). The graph is derived from the original graph G = (V, E) andcomprises two distinct sets of nodes. The first set, V, is a direct copy of the nodes V from the original graph. The second set,C, consists of cluster nodes divided into two categories: global clusters (Ω) and local clusters (Γ).
In this bipartite graph, each node from the global clusters Ω connects to all nodes in V. Meanwhile, each node from thelocal clusters Γ is associated with a specific node i in V, and connected to its ego-neighborhood, which includes node i andits one-hop neighbors. For a node i in V, Γi represents the set of local clusters associatedwith it. The total number of nodesP
in C is the sum of nodes in Ω and the nodes in all local clusters i.e., |C| = |Ω| + i∈V |Γi |. An illustration of the bipartite
graph is provided in Fig. 2.

Figure 2: Based on the original graph on the left, we construct a bipartite graph on the right by adding local and global
cluster-nodes. For each node in the original graph, a set of local cluster-nodes, represented by the blue boxes at the top, isconnected to its ego-neighborhood. For example, the ego-neighborhood of node a includes itself and its one-hop neighbornode b. Therefore the local cluster-nodes for node a are connected to a and b. Meanwhile, a set of global cluster-nodes areadded and connected to all nodes in the original graph, as represented by the blue boxes at the bottom.

E. More on training loss
E.1. Orthogonality loss (Lortho )To encourage the clusters to be distinct, we adopt a regularizing orthogonality loss function [43] Lortho =
I|Ω|
√

|Ω|

F

C⊤C
∥C ⊤ C∥F−, where ∥ · ∥F is the Frobenius norm. This pushes the cluster-nodes to be orthogonal to each other.

E.2. Similarity loss (Lsim )To further enhance the clustering process, we introduce Lsim that encourages node similarity to only a single cluster. To
achieve this, we set |Ω| to be multiple of the number of classes and associate a set of cluster-nodes Ωτ with each class τ . We
then compute distances between the node embedding and the cluster-node embeddings associated with its labelled class,12

Differentiable Cluster Graph Neural Network

select the cluster-node embedding that is most similar to the node with a max operator, and push them closer. If a training
node i belongs to class τ , cτj is the j th cluster embedding associated with class τ . Let Λ be a similarity function, and V+ be
the set of training nodes, then Lsim is defined as
1
Lsim =|Ω||V+ |X"

sτi + logXτ ′ ̸=τi∈V+τexp − si

′

#

,



where sτi = maxτ Λ ziL , cτj .
j∈|Ω |(19)(20)

F. More on DC-MsgPassing Algorithm
Algorithm of DC-MsgPassing can be found in Algo. 1.
Each iteration of DC-MsgPassing consists of two alternative steps. First, with fixed embeddings Z and C,
optimal clustering assignment matrices are calculated via
Sinkhorn-Knopp algorithm (Eq. (4)). Then, the clusternode and node embeddings are refined through message
passing with the updated assignment matrices via Eq. (5)and Eq. (6). In practice, we could also add learnable components such as linear transformation matrices or MLPs
for the messages in Eq. (5) and Eq. (6) to allow the network to fit the data distribution better.
F.1. Complexity analysis

Algorithm 1 DC-MsgPassing
Input: Bipartite graph G = (V, C, E), Node features X, hyperparameters α, β, λOutput: [zi ]i∈V
1: Z = X
2: Initialize cluster embeddings C
3: // Optimize Lλcluster via DC-MsgPassing
4: for l = 1, 2, . . . , L do
5:
Update Cluster Assignment Matrices:6:
Mij = d(zi , cj ) ∀i ∈ V, j ∈ C
7:
B {Ω,Γi } = e−λM
8:// Run Sinkhorn algorithm for T steps (Eq. 4)
9:P {Ω,Γi } = B {Ω,Γi }10:Update Node and Cluster-node Embeddings:
11:
Calculate C as per Eq. (5)12:Calculate Z as per Eq. (6)13: end for
14: Return: Z

The complexity of the global assignment update step isO(T |V||Ω|) = O(|V|) as |Ω| ≪ |V| and T are small constants. Both the complexity of the local assignment update
step O(T |E|) = O(|E|) and the embeddings update stepO(|E|) = O(|E|) are linear w.r.t. the number of edges.
Thus the overall computational complexity is linear w.r.t.
the size of the original graph O(|E|), same order as standard GNNs. Runtime of DC-MsgPassing is measured inAppendix G.5.

G. Experiments
G.1. More results on heterophilous datasets
DC-GNN achieves state-of-the-art on four out of five heterophilous datasets proposed by [62], as shown in Tab. 3. Our
performance is especially strong on Minesweeper, where we surpass existing baselines by 5%.
G.2. Benefit of capturing long range information in sparse label settings
Our method introduces shortcuts between distant nodes via the cluster-nodes. To empirically evaluate the effects of shortcut
construction, we consider a generalized scenario on homophilous graphs where information from labeled nodes needs topropagate over a long distance to reach most unlabeled nodes. Specifically, we evaluate our method with only a small
number of training labels per class.
Our hypothesis is that information propagation becomes
more challenging when useful training information is more
C ORA
C ITESEERP UBMEDscarce, making the effects of shortcut construction more
GCN
69.23 (3.39) 63.03 (4.48) 68.00 (3.75)
pronounced in sparsely-annotated graph datasets. The hyDC-GNN 72.17 (1.76) 62.14 (2.65) 75.07 (0.82)
pothesis is confirmed by experiment results in Tab. 4, where
our method outperforms vanilla GCN on Cora and Pubmed with substantial improvements.
Table 4: Classification accuracy with 5 labels per class.

13

Differentiable Cluster Graph Neural Network

Table 3: Classification performance comparison on more recent heterophilous datasets [62]. Following [62], we report accuracy for
Roman-empire and Amazon-ratings, and ROC AUC for the rest.
Roman-empire

Amazon-ratings

Minesweeper

Tolokers

Questions

ResNetResNet+SGC
ResNet+adj

65.88 (0.38)
73.90 (0.51)
52.25 (0.40)

45.90 (0.52)
50.66 (0.48)
51.83 (0.57)

50.89 (1.39)
70.88 (0.90)
50.42 (0.83)

72.95 (1.06)
80.70 (0.97)
78.78 (1.11)

70.34 (0.76)
75.81 (0.96)
75.77 (1.24)

GCN
SAGE
GAT
GAT-sepGT
GT-sep
GPSGAT+Performer

73.69 (0.74)
85.74 (0.67)
80.87 (0.30)
88.75 (0.41)
86.51 (0.73)
87.32 (0.39)
87.04 (0.58)

48.70 (0.63)
53.63 (0.39)
49.09 (0.63)
52.70 (0.62)
51.17 (0.66)
52.18 (0.80)
49.92 (0.68)

89.75 (0.52)
93.51 (0.57)
92.01 (0.68)
93.91 (0.35)
91.85 (0.76)
92.29 (0.47)
91.08 (0.58)

83.64 (0.67)
82.43 (0.44)
83.70 (0.47)
83.78 (0.43)
83.23 (0.64)
82.52 (0.92)
84.38 (0.91)

76.09 (1.27)
76.44 (0.62)
77.43 (1.20)
76.79 (0.71)
77.95 (0.68)
78.05 (0.93)
77.14 (1.49)

H2 GCNCPGNN
GPR-GNN
FSGNN
GloGNNFAGCN
GBK-GNN
JacobiConv

60.11 (0.52)
63.96 (0.62)
64.85 (0.27)
79.92 (0.56)
59.63 (0.69)
65.22 (0.56)
74.57 (0.47)
71.14 (0.42)

36.47 (0.23)
39.79 (0.77)
44.88 (0.34)
52.74 (0.83)
36.89 (0.14)
44.12 (0.30)
45.98 (0.71)
43.55 (0.48)

89.71 (0.31)
52.03 (5.46)
86.24 (0.61)
90.08 (0.70)
51.08 (1.23)
88.17 (0.73)
90.85 (0.58)
89.66 (0.40)

73.35 (1.01)
73.36 (1.01)
72.94 (0.97)
82.76 (0.61)
73.39 (1.17)
77.75 (1.05)
81.01 (0.67)
68.66 (0.65)

63.59 (1.46)
65.96 (1.95)
55.48 (0.91)
78.86 (0.92)
65.74 (1.19)
77.24 (1.26)
74.47 (0.86)
73.88 (1.16)

DC-GNN89.96 (0.35)

51.11 (0.47)

98.50 (0.21)

85.88 (0.81)

78.96 (0.60)

G.3. Alleviating oversquashing
G.3.1. D EFINITION OF EFFECTIVE RESISTANCE
Let u and v be vertices of G. The effective resistance between u and v is defined as
Ru,v = (1u − 1v )T L+ (1u − 1v ),where 1v is the indicator vector of the vertex v [15]. Let A be the adjacency matrix and D be the degree matrix. The
Laplacian is L = D − A and L+ is the pseudoinverse of L. The total effective resistance (Rtot ) of a graph is therefore thetotal sum of effective resistance between every pair of nodes.
G.3.2. E XPERIMENTS TO VALIDATE OVERSQUASHING MITIGATION(a) Amherst41(b) Wisconsin(c) Tree-NeighborsMatch

Figure 3: (a)-(b) Total effective resistance heatmap. (c) Accuracy for Tree-NeighborsMatch dataset.
Total effective resistance (Rtot ) is established as an indicator of oversquashing [15], prompting the development of various
graph rewiring strategies to diminish Rtot within the underlying graph and thus address oversquashing. Our approachcontributes to this endeavor by introducing cluster-nodes. This effectively creates new pathways among the original nodes,
thereby reducing the graph’s Rtot and aiding in mitigating the oversquashing issue [15]. To validate this, we conduct anempirical analysis of the total pairwise effective resistance among the original nodes in our bipartite graph, with varying
number of global and local clusters. Fig. 3(a) and Fig. 3(b) display a heatmap of Rtot , with darker shades representing higher
Rtot values. The results indicate that Rtot decreases sharply as we increase the number of both global and local clusters.
14

Differentiable Cluster Graph Neural Network

To further validate the oversquashing mitigation capability, we conduct experiments on Tree-NeighborsMatch dataset [9],which requires long-range interaction between leaf nodes and the root node of tree graphs with varying depths. In Fig. 3(c),DC-GNN achieves perfect performance along with GT [63] on all depth settings, significantly outperforming other message
passing GNNs.

(a) edge probability = 0.2(b) edge probability = 0.3(c) edge probability = 0.5(d) edge probability = 0.8

Figure 4: Total effective resistance heatmap of Erdos-Renyi random graphs at different sparsity levels. Number of nodes is
10 for all settings.
We also measure effective resistance (Rtot ) in synthetic random graphs with different degrees of sparsity. Results in Fig. 4
show that both global and local cluster-nodes contribute to reducing effective resistance, as demonstrated by decreasing
Rtot values in both row and column directions. Additionally, the more drastic Rtot decrease from the first to last column inheatmap (a) compared to heatmap (d) show that global cluster-nodes play a more pronounced role in reducing effective
resistance at a higher edge sparsity setting.
G.4. Ablation studies
G.4.1. E FFECTS OF EACH TERM IN Lλcluster
To validate the effectiveness of our DC-MsgPassing algorithm, we conduct an ablation study on the individual componentsof our objective function Lλcluster . Specifically, we vary the parameters by setting (1) α to 0, (2) α to 1 and (3) β to 0, aiming
to ablate the contributions of the global clustering term, local clustering term and the node fidelity term respectively.
Results from Tab. 5 indicate that the contributions
Table 5: Effects of each term in Lλcluster .
of global and local clustering vary on different
G ENIUSUS- ELECTION P ENN 94 A MHERST 41
datasets. Specifically, the contribution of local
DC-GNN91.70 (0.08) 89.59 (1.60) 86.69(0.22) 82.94 (1.59)
clustering is dominant on Genius, US-election(-)G LOBAL 91.62 (0.07) 88.77 (2.21) 84.61 (0.42) 81.43 (1.53)
and Amherst41. This is expected as local cluster(-)L OCAL
87.05 (0.09) 83.26 (1.77) 86.69 (0.22) 80.77 (2.04)
ing facilitates message passing via adjacent nodes(-)F IDELITY 91.08 (0.04) 87.84 (2.67) 86.69 (0.22) 82.28 (1.32)
and embeds graph structure information into themodel. The contribution of global clustering is most pronounced on Penn94, indicating the usefulness of long-range
information in Penn94 captured by global clustering term. Additionally, The results show that all three terms—local
clustering, global clustering, and node fidelity—contribute to the overall efficacy of our model.
G.4.2. E FFECTS OF Lortho AND Lsim
We introduced orthogonality (Lortho ) and simiTable 6: Effects of Lortho and Lsim .
larity (Lsim ) losses to regularize and assist the
G ENIUSUS- ELECTION P ENN 94 A MHERST 41
clustering process. In this ablation, we evaluate
DC-GNN91.70 (0.08) 89.59 (1.60) 86.69 (0.22) 82.94 (1.59)
the effects of these losses on model performance.
(-) Lsim
91.70 (0.08) 89.08 (1.46) 86.65 (0.15) 82.22 (1.03)
As shown in Tab. 6, Lortho and Lsim generally(-) Lortho
91.68 (0.08) 88.72 (1.20) 86.64 (0.27) 82.35 (1.25)
help to improve the scores across datasets. The(-)Lsim , Lortho 91.68 (0.08) 88.61 (1.57) 86.40 (0.25) 81.75 (1.07)
results provide some evidence that the two losses
indeed facilitate the clustering process, plausibly by encouraging distinct cluster representations and node-cluster alignment
as hypothesized.
G.4.3. AGGREGATION OPERATION IN SIMILARITY LOSS
15

Differentiable Cluster Graph Neural Network

Table 7: Effects of aggregator function in
After computing the similarity between a node and each of the multiple clusters
Lsim .
from the same class, the choice of aggregation method is crucial. We evaluate
AGG
P ENN 94 A MHERST 41
the effectiveness of using the aggregation operator on Amherst41 and Penn94
MEAN 86.13 (0.12) 81.23 (1.34)
datasets. Tab. 7 shows the effects of replacing the max aggregator with mean
SUM 85.84 (0.26) 81.26 (1.58)
and sum in computing similarity loss. On both datasets, max outperforms both
MAX 86.69(0.22) 82.94 (1.59)
sum and mean, indicating the effectiveness of using max as the aggregation
operation. Intuitively, taking the average of all similarity scores (mean) is sub-optimal. mean tends to make the node
embeddings closer to the average of all clusters belonging to a same class, undermining the purpose of using multiple
clusters . Similar to mean, summing up all similarity scores (sum) is more powerful yet requires more data to learn. max
selects the maximum similarity score to compute similarity loss and guides the node embeddings closer to one of the clusters,
thus preserving the power of diversity in representation.
G.4.4. E FFECTS OF NODE FIDELITY TERM
Table 8: Dirichlet Energy (DE) with different β values. Higher DE indicates increased node distinctiveness.

Wisconsin
CiteseerCora

β = 0.0

β = 0.5

β = 1.0

0.7412880.110083
0.218658

0.963261
0.151699
0.294024

0.978465
0.206022
0.330234

The node fidelity term encourages the node embeddings to retain some information from the original node features, which
serve as initial residual. This technique can also potentially help to alleviate oversmoothing as shown in [16], [17]. To
validate this, we conduct additional experiments to measure the normalized Dirichlet Energy (DE) [27] for DC-GNN on
Wisconsin, Cora and Citeseer, using the implementation from [27].
We set β to 0, 0.5 and 1 for each dataset to measure how increased weightage of the node fidelity term influences DE, while
keeping α constant at 0.5. As observed in Tab. 8, DE positively correlates with β on all datasets.
G.5. Runtime experiments
We measure the average runtime of a DC-MsgPassing layer on the three largest datasets used in our experiments against
Pytorch Geometric [64] implementation of GATConv and GCNConv. DC-MsgPassing takes less than 4x times GCN
and is faster than GAT on these datasets. The results show that DC-MsgPassing is competitive in terms of runtime,
confirming our complexity analysis.
Table 9: Runtime and dataset statistics comparison on three large-scale datasets. Runtime results are in seconds.
Penn94

Cornell5

Genius# Nodes# Edges

41,554
1,362,229

18,660790,777

421,961
984,979

DC-MsgPassing
GATConv
GCNConv
Multiples of GATMultiples of GCN

0.00852
0.012420.00220
0.69x
3.88x

0.008200.01685
0.00242
0.49x
3.38x

0.007080.016360.00207
0.43x
3.42x

G.6. Dataset details
We conduct experiments on fourteen datasets, a mix of small-scale and large-scale datasets. Eleven of them are nonhomophilous, including: (1) Roman-empire, Amazon-ratings, Minesweeper, Tolokers, Questions [62]; (2) Penn94, Genius,Cornell5, Amherst41 [39]; (3) Wisconsin [37]; (4) a US election dataset [65]. Three are homophilous citation networks:
Cora, Citeseer and Pubmed [37]. We use the original train/validation/test splits when they exist. Otherwise we follow the
splits specified in [17], [39], [62]. Descriptions and statistics of the datasets are below.
16Differentiable Cluster Graph Neural Network

G.6.1. DATASET DESCRIPTION
Roman-empire, Amazon-ratings, Minesweeper, Tolokers and Questions are five datasets proposed in [62] to better
evaluate the performance of GNNs under heterophilous settings. The description of each dataset is as follows.
Roman-empire is based on the Roman Empire article from English Wikipedia. Each node in the graph represents one wordin the text, and each edge between two words represents either one word following another word or if the two words areconnected in the dependency tree. Node features is its FastText word embeddings. The task is to predict a node’s syntacticrole.
Amazon-ratings is based on the Amazon product co-purchasing network metadata. Nodes represent products and edges
connect products frequently purchased together. Node features are the mean of FastText embeddings for words in productdescription. The task is to predict the class of products’ ratings.
Minesweeper is a synthetic dataset inspired by the Minesweeper game. The graph is a regular 100x100 grid where eachnode is connected its eight neighboring nodes. 20% of the nodes are randomly assgined as mines. The node features are
one-hot-encoded numbers of the neighboring mines. The task is to predict if the nodes are mines.
Tolokers is based on data from the Toloka crowdsourcing platform. Nodes represent workers who have participated in theselected projects, while edges connect two workers who work on the same task. Node features are based on worker’s profile
information and task performance. The task is to predict which workers have been banned.
Questions is based on question-answering data from website Yandex Q. Nodes represent users and edges connect an answer
provider to a question provider. Node features are the mean of FastText word embeddings of user profile description, withan additional binary feature indicating users with no descriptions. The task is to predict if the users remain active on thewebsite.
Penn94, Cornell5 and Amherst41 [39] are friendship network datasets extracted from Facebook of students from selected
universities from 2005. Each node in the datasets represent a student, while node label represents the reported gender of thestudent. Node features include major, second major/minor, dorm/house, year, and high school.
Wisconsin [37] is a web page dataset collected from the computer science department of Wisconsin Madison. In thisdataset, nodes represent web pages and edges are hyperlinks between them. Feature vectors of nodes are bag-of-words
representations. The task is to classify the web pages into one of the five categories including student, project, course, staff
and faculty.
Genius [39] is a sub-network from website genius.com, a crowd-sourced website of song lyrics annotations. Nodes represent
users while edges connect users that follow each other. Node features include expertise scores expertise scores, counts ofcontributions and roles held by users. Around 20% of the users are marked with a ”gone” label, indicating that they are
more likely to be spam users. The task is to predict which users are marked.
US-election [65] is a geographical dataset extracted from statistics of Unite States election of year 2012. Nodes represent
US counties, while edges connect bordering counties. Node features include income, education, population etc. The task isa binary classification to predict election outcome.
Cora, Citeseer and Pubmed [37] are citation graphs, where each node represents a scientific paper and two papers areconnected when a paper cites the other. Each node is labeled with the research field and the task is to predict which field thepaper belongs to. All three datasets are homophilous.
G.6.2. DATASET STATISTICS
Tab. 10 covers statistics of datasets in Tab. 1. Tab. 11 covers statistics of datasets in Tab. 3.
Homophily matrix Homophily refers to the degree of similarity between connected neighboring nodes in terms of
their features or labels. There are many types of homophily measures proposed, including edge homophily [11], node
homophily [37], and improved edge homophily [39]. Homophily matrix proposed in [39] is an important metric, since it canbetter reflect class-wise homophily. The homophiliy matrix is defined as:
Hc1 ,c2 =|(u, v) ∈ E : cu = c1 , cv = c2 |,|(u, v) ∈ E : cu = c1 |
17

(21)

Differentiable Cluster Graph Neural Network

Table 10: Dataset statistics for Tab. 1.

Edge Hom.
Improved Edge Hom. [39]# Nodes# Edges# Node Features# Classes

Penn94

Cornell5

Amherst41

GeniusUS-election

Wisconsin

Cora

Citeseer

Pubmed0.47
0.046
41,554
1,362,229
4814
2

0.47
0.09
18,660790,777
4735
2

0.46
0.05
2,235
90,954
1193
2

0.61
0.08
421,961
984,979
12
2

0.83
0.54
3,234
11,100
6
2

0.21
0.094
251
466
1,703
5

0.81
0.766
2,708
5,278
1,433
6

0.74
0.627
3,327
4,676
3,703
7

0.80
0.664
19,71744,327500
3Table 11: Dataset statistics for Tab. 3.

Edge Hom.
Improved Edge Hom. [39]# Nodes# Edges# Node Features# Classes

Roman-Empire

Amazon-Ratings

Minesweeper

Tolokers

Questions

0.05
0.01
22,662
32,927
300
18

0.38
0.12
24,492
93,050
300
5

0.68
0.009
10,00039,402
7
2

0.59
0.17
11,758519,000
10
2

0.84
0.08
48,921
153,540301
2

for classes c1 and c2 , Hc1 c2 denotes the proportion of edges between from nodes of class c1 to nodes of class c2 . A
homophilous graph has high values on the diagonal entries of H.
Fig. 5 are the homophily matrices for three well-known homophilous datasets: Cora, Citeseer and Pubmed [66]. Highhomophily is signified by the high numbers in diagonal cells, whereas values of non-diagonal cells are mostly less than 0.1.
This is different from the homophily matrices of heterophilous datasets, where values of non-diagonal cells are similar oreven higher than diagonal cells.

(a) Cora(b) Citeseer(c) Pubmed

Figure 5: Homophily matrix for three homophilous datasets.
We show in Fig. 6 the homophily matrices for some heterophilous datasets for comparison.
G.7. Implementation details
Implementation details. For global cluster-nodes, we use trainable lookup embeddings to initialize the embeddings.
For local cluster-nodes, we fix the number of local clusters to be 2 for every ego-neighborhoods, and initialize the twocluster-node embeddings by the central node features and the average of neighboring node features respectively. In practice,
for local clustering cost matrices M, we rescale and normalize the distance before running the Sinkhorn-Knopp algorithm
for numerical stability.
Training Settings We conduct each experiment of DC-GNN using three distinct data splits and present the corresponding
mean and standard deviation of the performance metrics. The experiments are executed on a range of GPUs—specifically,
the V100, A100, GeForce RTX 2080, or 3090—based on their availability at the time the experiments are conducted. For
optimization, we employ the Adam algorithm and undertake a grid search of hyperparameters, the specifics of which are in
Tab. 12 and Tab. 13. Should the baseline results be publicly accessible, we directly incorporate them into our report. For thedatasets where baseline results are missing (Cornell5, Amherst41, US-election), we reproduced them following the code18

Differentiable Cluster Graph Neural Network(a) Penn94(b) Genius(c) Cornell5(d) Amherst41(e) US-election(f) Wisconsin

Figure 6: Homophily matrix for heterophilous datasets.

in [35].
Hyperparameters for DC-GNN For experiments in Tab. 1 and Tab. 3, we fix some hyperparameters and perform gridsearch for other hyperparameters. To facilitate reproducibility, we document the details of the hyperparameters and search
space in Tab. 12 and Tab. 13 respectively. T Ω refer to the number of iterations of Sinkhorn-Knopp algorithm when solving
P Ω , and T Γ is the number of Sinkhorn-Knopp iterations for solving P Γ . We set |Ω| to be multiples of the number of classes
in a dataset.
Table 12: Hyper-parameter search space of DC-GNN for datasets in Tab. 1
.
lr
λ
TΩ
TΓ
|Γi |
|Ω|
α
β
# layers in MLP
L : # layers
ω1ω2
epochsweight decay
aggregation
dropout
normalization
hidden channels

Penn94

Cornell5

Amherst41

GeniusUS-election

Wisconsin

Cora

Citeseer

Pubmed0.005
2
10,5,35, 3, 1
2
2,4, 8, 16, 30
0. 0.2, 0.5, 0.8, 10, 0.2, 0.5, 0.8
1,22, 50.001, 0.01
0.005, 0.0530
5e-4
mean, sum0.5
None16, 32, 64, 128

0.005
2, 5
10,5,35, 3, 1
2
2,4, 8, 16, 30
0. 0.2, 0.5, 0.8, 10, 0.2, 0.5, 0.8
1,22, 50.001, 0.01
0.005, 0.0530
5e-4
mean, sum0.5
None16, 32, 64, 128

0.005
2
10,5,35, 3, 1
2
2,4, 8, 16, 30
0. 0.2, 0.5, 0.8, 10, 0.2, 0.5, 0.8
1,22, 50.001, 0.01
0.005, 0.0530
5e-4
mean, sum0.5
None16, 32, 64, 128

0.005
2
10,5,35, 3, 1
2
2,4,8
0. 0.2, 0.5, 0.8, 10, 0.2, 0.5, 0.8
1,22, 4, 8,160.001,0.01
0,0.005,0.05
3000
5e-4
mean, sum0.5
LN16, 320.005
2,5
10,5,35, 3, 1
2
2,4, 8, 16, 30
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 50.001, 0.01
0.005, 0.05500
5e-4
mean, sum0.5
None16, 32, 64, 128

0.01
2
10,5,35, 3, 1
2
5, 10, 20
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 50.001, 0.01
0.005, 0.05200
1e-3
mean, sum0.5
None16, 32, 64, 128

0.005
2
10,5,35, 3, 1
2
6,12,24,48
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,2
2,4,8,100, 0.001, 0.01, 0.05
0.005, 0.05, 0.08, 0.1200
5e-4mean, sum0.5
None16, 32, 64, 128

0.001, 0.002
2
10,5,35, 3, 1
2
7, 14, 28
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,2
2,4,8
0.001, 0.01
0.005, 0.05
50
5e-4
mean, sum0.5
None16, 32, 64, 128

0.005
2
10,5,35, 3, 1
26, 12
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,2
2,4,8
0.001, 0.01
0.005, 0.05500
5e-4
mean, sum0.5
None16, 32, 64, 128

Table 13: Hyper-parameter search space of DC-GNN for datasets in Tab. 3

lr
λ
TΩ
TΓ
KΓ
KΩ
α
β
# layers in MLP
L : # layers
ω1ω2
epochsweight decay
aggregation
dropout
normalization
hidden channels

Roman-Empire

Amazon-Ratings

Minesweeper

Tolokers

Questions

0.005
2
5
3
2
18
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 4, 8,16,20
0.001, 0.01
0.005, 0.05
3000
5e-4
mean, sum
0.2
None, LN
16, 32, 64

0.005
2
5
3
2
5, 10
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 4, 80.001, 0.01
0.005, 0.05
3000
5e-4
mean, sum
0.2
None, LN
16, 32, 64

0.005
2
5
3
2
2,4,8
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 4, 80.001, 0.01
0.005, 0.05
3000
5e-4
mean, sum
0.2
None, LN
16, 32, 64

0.005
2
5
3
2
8, 16
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 4, 8
0.02
0.001
3000
5e-4
mean, sum
0.2
None, LN
16, 32, 64

0.001
2
5
3
2
2,4,8
0.2, 0.5, 0.8
0.2, 0.5, 0.8
1,22, 4, 8, 160.001, 0.01
0.001
3000
5e-4
mean, sum
0.2
None, LN
16, 32, 64

Hyperparameters for baselines We used the code provided by GloGNN [35] to reproduce the baseline results for dataset
Cornell5, Amherst41, and US-election. The grid search space for hyper-parameters are listed below. Note that some
hyper-parameters only apply to a subset of baselines. All other baselines results are obtained from [35] and [62].
19Differentiable Cluster Graph Neural Network• MLP: hidden dimension ∈ {16, 32, 64}, number of layers ∈ {2, 3}. Activation function is ReLU.
• GCN: lr ∈ {.01, .001}, hidden dimension ∈ {4, 8, 16, 32, 64}. Activation function is ReLU.
• GAT: lr ∈ {.01, .001}. hidden channels ∈ {4, 8, 12, 32} and gat heads ∈ {2, 4, 8}. number of layers ∈ {2}. We use
the ELU as activation.
• MixHop: hidden dimension ∈ {8, 16, 32}, number of layers ∈ {2}.
• GCNII: number of layers ∈ {2, 8, 16, 32, 64}, strength of initial residual connection α ∈ {0.1, 0.2, 0.5}, hyperparameter for strength of the identity mapping θ ∈ {0.5, 1.0, 1.5}.
• H2 GCN: hidden dimension ∈ {16, 32}, dropout ∈ {0, .5}, number of layers ∈ {1, 2}. Model architecture follows
Section 3.2 of [11].
• WRGAT: lr ∈ {.01}, hidden dimension ∈ {32}.
• GPR-GNN: lr ∈ {.01, .05, .002}, hidden dimension ∈ {16, 32}.
• GGCN: lr ∈ {.01}, hidden channels ∈ {16, 32, 64}, number of layers ∈ {1, 2, 3}, weight decay ∈ {1e−7 , 1e−2 },decay rate ∈ {0, 1.5}, dropout rate ∈ {0, .7},
• ACM-GCN: lr ∈ {.01}, weight decay ∈ {5e−5 , 5e−4 , 5e−3 }, dropout ∈ {0.1, 0.3, 0.5, 0.7, 0.9}, hidden channels∈ {64}, number of layers ∈ {2}, display step ∈ {1}.
• LINKX: hidden dimension ∈ {16, 32, 64}, number of layers ∈ {1, 2}. Rest of the hyper-parameter settings follow[39].
• GloGNN++: lr ∈ {.001, .005, .01} , weight decay ∈ {0, .01, .1}, dropout ∈ {0, .5, .8}, hidden channels ∈ {128, 256},
number of layers ∈ {1, 2}, α ∈ {0, 1}, β ∈ {0.1, 1}, γ ∈ {0.2, 0.5, 0.9}, δ ∈ {0.2, 0.5}, number of normalization
layers ∈ {1, 2}, orders ∈ {1, 2, 3}.

20