Modularity aided consistent attributed graph clustering via coarsening
Authors: Yukti Makhija
Samarth Bhatia
Manoj Kumar
Sandeep Kumar
Venue: Accepted by TMLR ()

Abstract: Graph clustering is an unsupervised learning technique for partitioning graphs with attributes and detecting communities.  However, current methods struggle to accurately capture true community structures and intra-cluster relations, be computationally efficient, and identify smaller communities. We address these challenges by integrating coarsening and modularity maximization, effectively leveraging both adjacency and node features to enhance clustering accuracy. We propose a loss function incorporating log-determinant, smoothness, and modularity components using a block majorization-minimization technique, resulting in superior clustering outcomes. The method is theoretically consistent under the Degree-Corrected Stochastic Block Model (DC-SBM), ensuring asymptotic error-free performance and complete label recovery. Our provably convergent and time-efficient algorithm seamlessly integrates with Graph Neural Networks (GNNs) and Variational Graph AutoEncoders (VGAEs) to learn enhanced node features and deliver exceptional clustering performance. Extensive experiments on benchmark datasets demonstrate its superiority over existing state-of-the-art methods for both attributed and non-attributed graphs.

Published in Transactions on Machine Learning Research (06/2025)
Modularity aided consistent attributed graph clustering via coarsening
Samarth Bhatia Indian Institute of Technology, Delhi
samarth Smmarhh..hattc2250aammi...
Yukti Makhija*
Indian Institute of Technology, Delhi
Manoj Kumar
manoj.kumarrlmmiit.ccoo
LNM Institute of Technology, Jaipur
Sandeep Kumar
Bsandeep@ee.n ötdd oc
Indian Institute of Technology, Delhi
denotes equal contribution
Reviewed on OpenReview: https: optp:/vveepre...e.e.mmmm net/ forum? id= jtSIjrpFut
Abstract
Graph clustering an unsupervised learning technique for partitioning graphs with attributes and detecting communities. However, current methods struggle to accurately capture true community structures and intra-cluster relations, be computationally efficient, and identify smaller communities. We address these challenges by integrating coarsening and modularity maximization, effectively leveraging both adjacency and node features to enhance clustering accuracy. We propose a loss function incorporating log-determinant, smoothness, and technique, resulting in
modularity components using block maaorizatiion-miiiiin superior clustering outcomes. The method theoretically consistent under the Degree- Corrected Stochastic Block Model (DC-SBM), ensuring asymptotic error-free performance and complete label recovery. Our provably convergent and Lime-efficien, algorithm seamlessly integrates with Graph Neural Networks (GNNs) and Variational Graph AutoEncoders (VGAEs) to learn enhanced node features and deliver exceptional clustering performance. Extensive experiments on benchmark datasets demonstrate its superiority over existing state-of-the-art methods for both attributed and non-attributed graphs.
1 Introduction
Clustering is an unsupervised learning method that groups nodes together based on their attributes or graph structure, without considering node labels. This versatile approach has numerous applications diverse fields, such as social network analysis TTang al. 2008), genetics, and bio-medicine (Cheng & Ma. 2022
Buterez et al. 2021). knowlodge graphs (Hamaguchi et al. (207); and computer vision (Mondal al. 2021
Caron al. 2018). The wide range of applications has led the development of numerous graph clustering algorithms designed for specific challenges within these domains. State-of-the-art graph clustering methods predominantly fall into cut-based, similarity-driven, or modularity-bascl categories.
Cut-based methods (Wei & Cheng 1989 Shi & Malik 2000 Bianchi et al. 2020), aiming to minimize the number of edges (or similar metric) in a cut, may fall short in capturing the true community structure if the cut's edge count docsn't significantly deviate from random graph expectations. This approach originated from the Fiedler vector, which yields a graph cut with minimal number of edges over all possible cuts (Fiedler) 1973: Newman 2006a). Similarity-based techniques, reliant pairwise node similarities, group nodes with

---

Published in Transactions on Machine Learning Research (06/2025)
shared characteristics. These can be computationally intensive and susceptible to noise, yielding suboptimal results, especially in sparse or noisy data scenarios. Modularity- methods rely on statistical approach, measuring the disparity in edge density between a graph and a random graph with the same degree sequence. These modularity maximization methods exhibit a resolution limit (Fortunato & Barthélemy (007). as they may inateente lead to the neglect of smaller community structures within the graph. Each clustering approach, whether cut-based, similarity-basee or modularity-based., bears its own set of limitations that necessitates careful consideration based on the characteristics of the underlying graph data.
Moreover, graph reduction techniques such as coarsening, summarization, condensation can also be utilized to facilitate the clustering task (Dhillon et al. 2007] Kumar et al. 2023 Loukas & Vandorgheynst, 2018 Loukas 2019). In the context of graph coarsening, the objective is to learn a reduced graph by merging similar nodes into supernodes. While this coarsening process is traditionally employed for graph reduction, it can be extended to clustering by reducing the original graph such that each class corresponds to a supernode. However, relying solely on coarsening may lead to suboptimal performance, particularly when the order of the reduction from the original graph size to the number of classes is large and results in significant loss of information.
In this study, we introduce an optimization- based framework designed to enhance clustering by leveraging both the adjacency and the node features of the graph. Our proposed framework strategically incorporates coarsening and modularity maximization, refining partitioning outcomes and bolstering the effectiveness of the clustering process. We refer to our method as Q-MAGC, where Q denotes the use of modularity in the Aidel Graph Coarsening process. The algorithm minimizes a nuanced loss function, Q-MAGC objectíve, encompassing a log det term, smoothness, and modularity components, ensure efficient. clustering. Formulated as a multi-block non-convex optimization problem, our approach is adeptly addressed maiooiization-miiiiiaaaioo technique Razaviyayn et al. (0013), wherein variables are updated individually while keeping others fixed. The resulting algorithm demonstrates convergence, showcasing its efficacy in efficiently solving the proposed optimization problem.
through block majorization- minimization
To enhance the clustering performance, we embed our Q-MAGC objective function into various Graph Neural Network (GNN) architectures, introducing the Q-GCN algorithm. This novel approach elevates the quality of learned representations by leveraging the message passing and aggregation mechanisms of Graph Convolutional Networks (GCNs), ultimately improving the clustering outcomes. An additional feature of our technique is its capacity to explore inter-cluster relationships. The node attributes derived from the coarsened graph at the conclusion of the process serve as cluster embeddings, shedding light on the distinct characteristics of each cluster. Simultancously, the edges within the coarsened graph unveil valuable insights into the relationships and connections between different clusters, providing a comprehensive understanding of the overall graph structure. This is contributing factor to the improvement observed over existing methods and is particularly significant for conducting first-hand analyses on large unlabelled datasets.
We introduce two additional algorithms, Q-VGAE and Q-GMM-VGAE, incorporating variational graph auto-cncoders to further enhance clustering accuracy. Through comprehensive experiments, we demonstrate the eveectiveness of our proposed algorithms, surpassing the performance of state-of-the-art methods on synthetic and real-world benchmark datasets, Our approach showcases notable improvements in clustering performance, solidifying the robustness and superiority of our proposed methods.
Key Contributions.
We present the first optimization-bnnt based framework for attributed graph clustering through coarsening via modularity maximization. Our approach demonstrates efficiency, theoretical convergence, and addresses limitations of cxisting methods. The paper offers comprehensive analysis and provides theoretical guarantees including KKT optimality, and convergence analysis which are often absent in prior research.
We show that our method is theoretically (weakly and strongly) consistent under a -orreeted SBM (DC-SBM) and shows asymptotically no errors (weakly consistent) and complete recovery of the original labels (strongly consistent).. Proving consistency increases the reliability of our method and makes it more robust.
2

---

Published in Transactions on Machine Learning Research (06/2025)
We demonstrate the scamless integration of the proposed clustering objective with GNN-based architectures, leveraging wessage-passsing to enhance our method, which is also backed up by experiments.
We perform thorough experimental validation on diverse range of real-world and synthetic datasets, encompassing both attributed and non-attributed graphs of varying sizes. The results demonstrate the superior performance of our method compared to existing state-of-the-ate approaches. We want to highlight that our method does not specialise for very large graphs, yet we present preliminary results in this regard.
We conduct ablation studies to evaluate the behavior of the loss terms, compare runtime and complexities, and perform comprehensive evaluation of modularity.
Graph clustering setup. Let G E,, be graph with node set V = {vi, u2,...; Up} (IVI p), edge set E c. V x V|[ e), weight (adjacency) matrix A and node feature matrix X R Also, let d = A 1 E Z., be the degree vector, where 1 is the vector of size p having all entries 1. Then, the graph Laplacian is θ = diag( d) - A and the set of all valid Laplacian matrices is defined as: Sg = {o E R Oi θji < 0 for + j. A Eド= Ozy]- The goal of clustering is to learn a cluster assignment matrix C C R where p is the number of nodes in the original graph and k is the number of clusters. In the following section, we explore the concept of graph coarsening and examine its inherent connection to graph clustering.
2 Background and Related Works
In this section, we will discuss existing graph clustering techniques, how graph coarsening can be utilized for the graph clustering task and its limitations, and finally, the proposed formulation for graph clustering.
Graph clustering a fundamental lask in unsupervised learning, aiming to partition nodes into meaningful communities based on structural and attribute similarities. Graph clustering methods can be broadly classified into traditional and deep learning- based approaches. Traditional methods include cut-based, similarity- -based, and modularity-baser techniques. Cut-based methods (Wei & Cheng 1989 Shi & Malik 2000 Bianchi et al. 2020) minimize edge cuts to separate clusters but often fail to capture true communit ies. Similarity-based approaches group nodes based on pairwise similarity but suffer from high computational costs and noise sensitivity. Modularity-bane
methods (Guimerà & Nuncs Amaral 2005 Salha-Galvan et al. 2022 Bhowmick let al. 2023 Tsitsulin et al. 2023) optimize modularity to enhance community detection but face resolution limits that hinder the identification of smaller clusters (Fortunato & Barthčlemy] 2007).
Next, deep learning-based methods leverage neural networks for graph clustering. Graph Autoencoders (GAEs) and Variational Graph Autoencoders (VGAEs) (Kipf & Welling 2016a) learn latent node representations through adjacency reconstruction. Contrastive learning methods (Hassani & Khasahmadi 2020 Zhao et al.,
Liu et al.) 2023a) improve these representations by distinguishing similar and dissimilar node pairs. GMM- VGAE (Hui et al. 2020 refines clustering by incorporating a Gaussian Mixture Model to model complex data distributions. Despite their effectiveness, deep learning-based methods struggle with scalability, high computational complexity, and instability in graph clustering. Furthermore, graph coarsening is also utilized to perform the clustering task. In the next subsection, we will discuss how graph coarsening can be leveraged for graph clustering. A more in-depth literature survey such methods can be found in Appendix B
2021
2.1 Graph Coarsening
Graph coarsening is graph dimensionality reduction technique used in large-scale machine learning to E, A, X) while preserving propertics of the original graph G. Graph coarsening aims to learn mapping matrix C R where p is the number of nodes in the original graph and & is the number of nodes in the coarsened graph. Each non-zero entry of the mapping matrix C, i.e., Cij, indicates that the i-th node of G is mapped to the j-th supernode. For C' E C, the relationship between the original graph Laplacian O, the coarsened graph Laplacian O,, and the mapping matrix C is given by θ = OC.. Also, the coarsened graph feature matrix is computed using
construct smaller or coarsened graph G. from the original graph G = EV,
Refer Appendix A for the code
3

---

Published in Transactions on Machine Learning Research (06/2025)
the relation X, =
Moreover, for balanced mapping, the mapping matrix C' belongs to the following
set (Kumar et al. 2023 Loukas & Vandergheynst 2018 Loukas
2019):
c c=(ce E R
(C, = d. |Cil 2 1 and |II" =1]
(1)
Graph coarsening can be extended to graph clustering by reducing the size of the coarsened graph to the number of classes (k). However, in most graphs, the number of classes is very small, and reducing the graph to this exlent may lead to poor clustering quality. Before moving lowards the problem formulation, we will also discuss spectral modularity.
2.2 Spectral Modularity Maximization
Spectral Clustering is the most direct approach to graph clustering, where we minimize the volume of inter-cluster edges. Modularity, introduced in Newman (2006b), is the difference between the number of edges within a cluster C and the expected number of such edges in random graph with an identical degree sequence. It is mathematically defined as:
Q=
1 2e
Σ 1,==1
Agj
d,dj 2
8(cr. cj)
(2)
where 8(c,,)) eg) is the Kronecker delta between clusters and j. Maximizing this form of modularity is NP-hard (Brandes al. 2008). However, we can approximate it using a spectral relaxation, which involves a modularity matrix B. The modularity matrix B and spectral modularity are defined as follows:
B= dd
1 - BC) 2e
A= Q
B is symmetric and is defined such that its row-sums and column-sums are zero, thereby making 1 one of its eigenvectors and 0 the corresponding eigenvalue. These spectral properties of the modularity matrix are also observed in the Laplacian, as noted in Newman (2006b), which is a crucial element in spectral clustering. Modularity maximized when uf is maximized, where u are the eigenvectors of B and s is the community assignment vector, ie., placing the majority of the summation in Q on the first (and largest) eigenvalue of B. Moreover, modularity is closely associated with community detection. These special spectral properties make B an ideal choice for graph clustering.
Next, we will discuss existing graph clustering studies that apply graph coarsening techniques or utilize modularity maximization. MinCutPool (Bianchi et al.) 2020) formulates a differentiable relaxation of spectral clustering via pooling by jointly optimizing over the clustering objective with an orthogonal regularization. DifiPool (Ying et al. 2018 learns soft cluster assignments al each layer of the GNN and optimizes two additional losses, an entropy to penalize the soft assignments and a link prediction based loss. Next, SAGPool Lee et al. 2 calculates attention scores and node embeddings to determine the nodes that need to be preserved or removed. Some disadvantages of these methods are instability and computational complexity in the case of SAGPool and DiffPool and convergence in MinCut Various heuristic algorithms have been established that solve the NP-hard problem of modularity maximization including sampling, simulated annealing (Guimerå & Nunes Amaral 2005 Guimerå & Amaral 2005) and the Newman-Girver algorithm with O(p²) time complexity. Greedy algorithms (Louvain Leiden) (Newman) 20044; Blondel et al. 2008) improve on this. These algorithms require intensive compute and don't use node fcatures. Modularity maximization using GNNs has also garnered attention recently. DMoN (Tsissulin al.) 2023) optimizes only for modularity with collapse regularization to prevent the trivial solution, but offers no theoretical guarantees about convergence. A more comprehensive literature review can be found in Appendix B
Current graph clustering methods often struggle to accurately capture both intra-cluster and inter-cluster relationships, achieve computational efficiency, and identify smaller communities, thereby limiting their offectiveness. These methods face significant challenges including instability and the lack of convergence guarantees, especially when employing coarsening techniques. Modularity maxinization, despite extensive study, relies computationally intensive heuristics and lacks theoretical convergence guarantees.
4

---

Published in Transactions on Machine Learning Research (06/2025)
2.3 Proposed Problem Formulation
By incorporating both adjacency and node features, our approach aims to robustly capture intra-cluster and inter-cluster dynamics. This framework ensures stability, guarantees convergence, and consistently delivers superior clustering results with enhanced computational efficiency compared to existing methods. Given original graph G(V, A, X), the proposed optimization formulation is:
min LMAGO = + C
subject to C. Sc (C E TR 2 0, || 1 A 1.2...
(4)
Here, E RR represents the clustering matrix to be learned, where each non-zero entry Cj indicates that the i-th node assigned to the j-th cluster. The term XX denotes the graph coarsening objective which compresses similar nodes together while preserving structural properties. The function g(C, represents the modularity objective, improving clustering performance. Additionally, h(C, θ) is regularization term enforcing desirable properties in the clustering matrix, as defined in Equation 1 The overarching goal of the optimization problem| is to choose ((C,X, 0), g(C, A), and k(C, θ) such that nodes are optimally clustered and inter-cluster connectivity is maintained. In the next section, we will develop the clustering algorithm, leveraging the coarsening objective and modularity to enhance clustering performance.
3 MAGC Algorithm
Given a graph G = {V, F, A3, considering /c,
S(C, 0) = (x(x3C* g(C, A) - BC) dot d d= A- 1-1,, and ((C lo
(where B B= A
'd 2:
JJ, to obtain clustering matrix C
formulate the following optimization problem
B
min CMAGC CI Xe.C
Cr (CC) - - log det (C + +
2e
subject to C = {C e ko ||T < 1) Vi, = C.Cc where, J = b. Lexk
(5)
The torm (x(X)TTOCXc) represents the smoothness or Dirichlet energy of the coarsened graph while CT0C the Laplacian matrix of the coarsened graph. Minimizing smoothness ensures that the clusters or supernodes with similar features are linked with stronger weights. The term tr(C² BC) corresponds to the graph's modularity, enhancing the quality of the clusters formed. The term log det(CT + J) is crucial for maintaining inter-cluster edges in the coarsened graph. For connected graph matrix with k super-nodes or clusters, the rank of CT @C is k 1. Adding J to CTOC makes C eC + J a full-rank matrix without altering the row and column space of CC (Kumar et al. 2020). This is ensured because it can be written as - E, log \ where X are the eigenvalues the θc thus, minimizing this would result in minimizing the multiplicity of 0-eigenvalues, turn minimizing the number of connected components (which can't be loss than 1).
Problem 5 is multi-block non-convex optimization problem solved using the Block Successive Upper-bount bound Minimization (BSUM) framework. All terms except modularity convex in nature, which prove in Appendix C We iteratively update C' and X alternately while keeping the other constant. This process continues until convergence or the stopping criteria are met. Since the constraint. X = CX2 is hard and difficult to enforce, we relax it by adding the term x||X Cxc to the objective. This term ensures that each node is assigned to a cluster, leaving no node unassigned. Additionally, when needed, we can add an optional sparsity regularization term ||C which can be seen as ensuring that each node is assigned exactly cluster, avoiding any overlap in node assignments across clusters.
5

---

Published in Transactions on Machine Learning Research (06/2025)
Updating C
Treating X as constant and C' as a variable the sub-problem for is:
min S(C) (CXx) _ ( BC) - - log do JJ J)+ 2 || CXcll
2e
1
subject to C {C B 2 0, | - 1] Vi, where, J= 1ick
(6)
k
By using the first-order Taylor scries approximation, majorisod function for f(C) at Ct (C after itcrations) can be obtained as:
L -|
-(C)
where f(C) is L-Lisschitz continnous gradient function L max L2, Ls, La) with L1, L2, La, La the Lipschitz constants -ylog det(C "C' J), (CXx), |CXc c X1i tr(C" BC), respectively. We prove this in Appendix We can expand this as:
I "n((C- 2 (C- C*) = V[C"
=
(C Ct) +
(8)
( 10 L
Ignoring constant terms we gel
= =tr(C" - Ltr(C C*) ) tr(C
(9)
Now, the majorised problem of Equation 7 becomes
min Ir( "
c
1 -C--,v)())))
(10)
CESc
The optimal solution to Equation 10, found by using Karush-Konn Kuhn-Tucker Tucker (KKT) optimality conditions is (Proof deferred to the Appendix D):
c++ (ce |(("))
(11)
where, Vf(CC) -2700' ect + +)= aac''cc-xxxa 200 XoX" BC
(12)
Updating X
Treating C' fixed and X. as variable. The subproblem for updating Xe
minf(X) xc( + | - C'eell3
(13)
The closed form solution of problem Equation can be obtained by putting the gradient of f(X) to zero.
x 2 (2c c
CT
(14)
Convergence Analysis
Theorem 1. The sequence {O++1, xx++]] generated
Algorithm
converges to the set of
Krrush-Kuhn-Tiin (KKT) optimality points for Problem
Proof Sketch. We derive the majorized problem for L-Lipschitz continuous and differentiable functions. Then, we formulate the Lagrangian (Equation 25) of the majorized problem Equation 10 at the gth iteration and define the dual variables. The next step involves solving the KKT conditions that satisfy primal and dual feasibility, complementary slackness, and setting the gradient to zero. This allows us to obtain the optimal solution for ((++1), The detailed proof can be found in the Appendix E

---

Published in Transactions on Machine Learning Research (06/2025)
Complexity Analysis. The worst-case time com-
Algorithm 1 Q-MAGC Algorithm
plexity of a loop (i.e. one epoch) in Algorithm [ O(p²k + pkn) because of the matrix multiplication in the update rule of C Equation 11 Hcre, is the number of clusters and n the feature dimension. Note that & is much smaller than both p and n. This makes our method much faster than previous opti- mization based methods and faster than GCN-based clustering methods which have complexities around O(p2n pp²)) We discuss this more in Appendix F
Require:
2: while Stopping Criteria not met do
3: Update C++1 as in Equation 11
4: Update X- as in Equation 14
5: ++1+1
6: end while
7: return C
Consistency Analysis on Degree Corrected Stochastic Block Models (DC-SBM).
To evaluate the robustness of the proposed optimization objective, we aim to prove its consistency. By consistency we mean the objective can recover the cluster assiguments correctly. Strong consistency refers lo perfect recovery of cluster assignments, while weak consistency allows for c-margin of error in the assignments. To check whether the proposed objective (Equation 5) results in consistent clustering, we need to assume a random graph model. In this section, prove method is weakly and strongly consistent under Degree Corrected Stochastic Block Models (DC-SBM).
A graph G(V, E) is generated by a DC-SBM with p nodes which belong to k classes. Following the setup in Zhhao et al. (2012), each node 2 is associated with a label-degree pair (ys, tx) drawn from a discrete joint distriiutiin Mxxm- Here, & takes values 0 S 21 S .... S Im with E[4] = 1, and yi E [k]. Additionally, we have a symmetric is matrix that specifics the probabilities of inter-cluster edges. The edges betwoen each node pair (vi, Uy) are sampled as independent Bernoulli trials with probability B[A;j]] = LaljPu.s To ensure E[A,y] < 1, DC-SBMs must satisfy 2 (max,, P.)) S 1. The matrix P is allowed to scale with the number of nodes p and is reparametcrized as Pp = Pp where Pp = Pr[A,j = 1] - 0 as p increases, and P is fixed. The average degree of the DC-SBM graph is defined as Ap = PPp-
We select DC-SBM for our analysis because it incorporates a degree parameter for each node, which accommodates the heterogeneity of real-world graphs. This feature allows for high-degree nodes at the cluster centers, a common characteristic in practical graph structures. While DC-SBM effectively models real-world graphs, it remains analytically tractable, making it good choice for evaluating clustering behaviors.
Let hi denote the predicted cluster for node us. The assignment matrix C' is the one-hot encoding of such that C. = one-hot(y.). We define (ee) E z as the inter-cluster edge count matrix for a given cluster assignment e E [k]'_ Here, (gt(e) = Eij A = e,eg = 1} denotes the number of edges between clusters q and I. Also, We represent the class frequency distribution as 1),, where n, indicates the fraction of nodes assigned to cluster i.
Definition 1. (Strong and Weak Consistency). The clustering objective is defined to be strongly consistent if lim Pr(j y] + 1. A weaker notion of consistency is defined by lim Pr 10000
1 Σ p 100
+ vl < + 1 0.
p0000
Zhao et al. (2012) prove the consistency of multiple clustering objectives under the DC-SBM, including
Newman Girvan modularity (Theorem 3.1). They also provide general theorem (Theorem 4.1) for checking
consistency under DC-SBMs for any criterion L(e), which can be expressed as L(e) = F O(e) Ap .T) where
Mp pp Pp and [k]] is cluster assignment.
The consistency of an objective is evaluated by determining if the population version of L(e) is maximized by the true cluster assignment y. The population version of L(e) is obtained by taking its conditional expectations given y and t. We consider an array S E R and define a matrix H(S) E R as HS( = Eotvo In Parkkassss Additionally, we define a vector h(S) E I² as hx(S) = E Skan. Here, HS)) and hSS denote the population versions of (ee) and π, respectively, such that 1 EE H(S) and E[ C, t] = h(S).
",
7

---

Published in Transactions on Machine Learning Research (06/2025)
ny ,f(e),, if F is uniquely mazimized by 5 and n, P.F. F satisfy the regulariby conditions, then C is strongly consistent under DC-SBMs if Ap logy
Lemma 1. (Theorem 4.1 from Zhao et ol. (2012)) For any [(e) F( Ose)
oo and weakky consistent if Xy + oo:
is Lipschita in its arguments (H()),
2. The directional derivative 8² FMM + {M1 - Mo), to + +e(t1 - -oo))lmoo is continuous in (M1, t1) for all (Mo, to) in a neighborhood of (I))), x)
8z2
3. With G(S) F (()))))))))
8G(()-c)++ed
5= C <00
de
It is important to note that the paper focuses maximizing an objective function. Therefore, we consider the negative of our loss function, AGC. Additionally, only consider the objective function defined in Equation 5) as regularizers can be adjusted for different downstream tasks.
Theorem 2. Under the DC-SBM, LMAGC is strongly consistent when Xp/ logp + oo and weakly consistent when Xp + 00.
Proof Sketch. The proof is divided into two parts. First, we demonstrate that LMAGE can be expressed in terms of and (the class frequency). We do this by establishing relations between the various terms made up of C, A, and O. We show that O is equivalent to the the cluster-level adjacency matrix. Combining these relations, we are able to express AMAGE in the roquired form. Applying Lemma
show that LMAGE must be uniquely minimized at any point (v", AA*) s.l. [yp)( = T(y") and [A[A(P] A". Second, we verify that, in this form, the population version of AMAGC Equation 51) satisfies the regularity conditions specified in Lemmal ! It is important to note that DC-SBMs do not consider node features, so we treat X and Xe as constants. We defer the detailed proof to Appendix G
We also demonstrate experimental consistency of the optimization objective Equation 5 in Appendix H resulting in complete recovery of the labels. This consistency extends to the objective with additional regularization terms, as detailed therein. We want to emphasize that the consistency analysis for Equation holds regardless of how the objective is optimized: whether by integrating loss into Graph Neural Networks (GNNs) or by employing Block Majorizationn-Miiiizttee techniques.
4 Integrating with GNNs
Our optimization framework integrates seamlessly with Graph Neural Networks (GNNs) by incorporat- ing the objective Equation 5) into the loss function. This integration can be minimized using gradient descent. We demonstrate the effectiveness of this ap- proach on several popular GNN architectures, includ- ing Graph Convolutional Networks (GCNs) (Kipf & Welling 2016b), Variational Graph Auto-Fncoderr (VGAEs) (Kipf & Welling 2016a), and a variant
Algorithm 2 Q-GCN Algorithm
Require: G(X, Q), a, 7,
Require: k GCN layers weights ((I..))
1: t 6-00 0
2: while Stopping Criteria not met do
3:
C++1 + GCN(X, A)
4:
X + CiX
5:
t+
known as Gaussian Mixture Model VGAE (GMM-
6:
L+ LMAGO(C, X)
7: end while
VGAE) (Hui et al.
2020
8: return C* C6
We itcratively Icarn the matrix C' using gradient descent. From Equation I, we update Xe using the relation Xc C.X. It is important to note that the loss term CXc X will not necessarily be zero. This arises because we use "soft" version of C. (Ca.) is the probability E [oo, 1]) in the loss function to enable gradient flow, while a "hard' version of C (Ci, is the binary assignment E {0, 13) is used in the update step. This method ensures that C naturally becomes harder and exhibits a higher prediction probability.
Q-GCN. We integrate our loss function (GMAGG, as defined Equation 5) into a simple three-layer Graph Convolutional Network (GCN) model. The soft cluster assignments C are learned as the output of the final GCN layer. The detailed architecture and loss function are illustrated in Figure
8

---

Published in Transactions on Machine Learning Research (06/2025)
b)
X
X
GCN
GCN
GCN
GCN
X
Shared
A
GCN
Encuder
Decuder
MAGC Loss
X
trainable network
Divergence
GMM
fixed operation
MAGC Loss
variables
Reconstruction Lass
predicted
Figure 1: a) Architecture of Q-GCN. We want to train the encoder to learn the soft cluster assignment matrix C. The coarsened features Xe are obtained using the relation X = C++1x X. Finally, our proposed MAGC loss is then computed using C and Xc. b) Architecture of DAVGAE/Q-GMM-VGG
The three-layer GCN encoder takes X and A as inputs learn the latent representation Z of the graph. Z then passed through an inner-product decoder to reconstruct the adjacency matrix Á. The reconstruction loss is caleulated between Á and A, and the KI-divergence is applied to Z. In Q-VGAE (or Q-GMM-VGAE), Z is also passed through GCN layer (or GMM) to output the soft cluster assignments C. The MAGC loss is then computed as in Q-GCN.
Q-VGAE The VGAE loss can be written as
LVGAE = Arecon E
ARa KL(g(ZIX,A) [[)
Recoustruction
Kullbaok-Leibler divergence
where, Z represents the latent space of the VGAE, Å is the reconstructed adjacency matrix, and Xyecon and ds are hyperparameters. We add GCN layer on top of this architecture, which takes Z as input and predicts C. detailed summary of the VGAE loss terms provided Appendix II For the VGAE, minimize the sum of three losses: the reconstrue- tion loss, the KT.-divergence loss, and our loss. This combined loss function is expressed
Algorithm 3 Q-VGAE//QGGM--VGAR Algorithm Z is the latent space of the VGAE and Á is the recon- structed adjacency matrix.
Require: G(X, θ), a, 8,7,A
Require: Variational Encoder VarEnc (GCN, σ) Require: Prediction Head - Pred (GCN or GMM)
1: +
CQ-VGAE LMAGC LYGAE
2: while Stopping Criteria not met do
3:
Z VarEnc (X,
Å + 2zT
Q-GMM-VGAE. This variant of VGAE incorpo- rates a Gaussian Mixture Model (GMM) in the latent space to better capture data distributions. This ap- proach is elfective because it minimizes the evidence lower bound (ELBO) or variational lower bound (Hui et al.] 2020: Kingma Welling 2014 Kipf & Welling 20166a using multiple priors, rather than single Gaussian prior in standard VGAF. Hui et al. (2020) use number of priors equal to the number of clusters.
4:
5:
C++1 + Pred(Z,
X + Ctx
6:
1+1+1
8:
L LMAAGCC,,X) (vGAE((X,A,ZAA))
9: end while
10: return C.

---

Published in Transactions on Machine Learning Research (06/2025)
5 Experiments
5.1 Benchmark Datasets and Baselines
We evaluate our method on a diverse set of datasets, including small attributed datasels like Cora and CiteSeer, larger datasets like PubMed, and unattributed datasets such Airports (Brazil, Europe, and USA). summary of these can be seen in Table Additionally, we lest. method very large datasets like SoauthorCSSPPyssiie AmazonPhoto/PPe and ogbn-arxiv. A detailed summary of all the datasets used is provided in Appendix J
Name
((VI)
n ((X.))
e ()
k (y)
Cora
2708
1433
5278
7
CiteSeer
3327
3703
4614
6
PubMed
19717
500
44325
3
Brazil
131
0
1074
4
Europe
399
0
5995
4
USA
1190
13599
To assess the performance of our method, we compare it against three types of state-of-the-at methods based on the input and architecture type: methods that use only node attributes, methods that use only graph structure, and methods that use both graph structure and node altributes. The last category is further subdivided into graph coarsening methods, GCN-based archilectures, VGAE-based based architectures and contrastive methods, and heavily modified VGAE architectures. This comprehensive evaluation allows us to demonstrate the robustness and versatility of our approach across various data and model configurations. The details on hyperparameter tuning can be found in Appendix
Table 1: Datasets summary.
subsection K.1
5.2 Metrics
To evaluate the performance of our method, we utilize label alignment metrics that compare ground truth node labels with cluster assignments. Specifically, we measure Normalised Mutual Information (NMI), Adjusted Rand Index (ARI), and Accuracy (ACC), with higher values indicating superior performance. For detailed explanations of these metrics, please refer to AopApeedix J We selected NMT as the primary metric for evaluating model performance based on its prominence in graph clustering literature and its comprehensive ability to assess the quality of our cluster assignments. Training Details are available in the Appendix L
5.3 Attributed Graph Clustering
We present our key results the real datasets Cora, CiteSeer, and PubMed in Table 2
Our proposed method
outperforms all existing methods in terms of NMT and demonstrrtes competitive performance in Accuracy and ARI. The best models were selected based on NMI scores. Results for very large datasets are provided in Appendix M Unlike some methods such as S3GC (Devvrit et al. 2022), which use randomly-sampled batches that can introduce bias by breaking community structure, we perform full-batch training by passing the entire graph. For extremely large graphs, such as ogbn-arxiv, we have also utilized batching.
5.4 Non-Attributed Graph Clustering
Our results in Table 3 demonstrate that our mothod achioves competitive or superior performance in terms of NMI, even for non-attributed datasets. For these, we use a one-hol encoding of the degree vector as features. While this is a basic approach compared to learning- based methods like DeepWalk (Perozzi et al.) (0014) and node2vee (Grover & Leskoved 2016), it ensures fair comparison since other methods also this feature representation.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Cora
CiteSoer
PubMed
Method
ACC 1
NMI 1
ART 1
ACC
NMI 1 ART
ACC
NMI 1
ART
K-meaus
31.7
16.7
26.1
38.5
17.1
30.5
57.3
29.1
57.1
Spectral Clustering
34.2
19.5
30.2
25.9
11.8
29.5
39.7
3.5
52.0
DeepWalk
Perrooi
2014a
Louvain
Blonder
52.4
42.7
24.0
49.9
24.7
9.2
30.4
20.0
10.3
GAE NNurIPS 16]
Kipf & Welling 20168
61.3
14.4
38.1
15.2
22.7
19.2
63.2
21.9
21.6
DGI 19 (Velclovii et al.
2019
71.3
56.4
51.1
68.8
44.4
45.0
53.3
18.1
16.6
GIC [PAKDD"21 2
Mavromatis Wanng
Karylie
2021
72.5
53.7
50.8
15.3
67.3
31.9
29.1
DARGG (1CCAT"19)
2019
70.4
52.8
49.6
39.7
67.1
26.6
27.5
GALA 1C [lazic et mi 2
2713
74.5
57.6
51L11
69.3
44.1
44.6
69.3
32.1
32.1
AGE [KDD 20)
Cuu suy 2020
73.5
57.5
50.0
69.7 7
11.9
31.1
71.1
31.6
33.4
DCRN (AAAT22 [Lm
2022
61.9
45.1
70.8
45.8
69.8
32.2
31.4
FGC J23RR23 [Runne et
53.8
23.2
20.5
541.2
31.1
28.2
G7.1
26.6
27.8
Q-MAGC (Ours)
65.8
51.8
42.0
65.9
40.8
40.1
68.7
32.8
27.9
Q-GCN (Ours)
SOGG TEFE TNNI.S233 [Tu
2023a
73.8
51.7
71.0
45.2
46.2
MVGRL [CMLL"20) 220 Hassmm & Khieahnndd
2020
73.2
56.2
51.9
68.1
43.2
43.4
69.3
34.4
32.3
VGAE (S Kupl Welling 20166
61.7
13.4
37.5
51.9
21.9
23.8
69.6
28.6
31.7
ARGA [ICAAI18] (Pan
2018
64.0
35.2
61.9
59.1
29.1
ARVGA [UCAATS PTn ot
2018
63.8
37.4
62.7
54.4
24.5
52.0
58.2
20.6
22.5
R-VGAE [EFE TKDE22 Mrabah et al.
2022
71.3
49.8
48.0
44.9
19.9
12.5
69.2
30.3
30.9
Q-VGAE (Ours)
VGAFCD-OPT [Entropy"20 (Choong 2020
27.2
37.3
22.0
51.8
25.1
15.5
32.2
25.0
26.1
Mod-Aoare VGAE [NN]22] Sulmi-Galve Gaivan al
2022
67.1
52.4
44.8
51.8
25.1
15.5
30.0
29.1
GMM-VGAE (A)) et 2020
71.9
53.3
48.2
67.5
10.7
12.1
71.1
29.9
33.0
R-GMM-VGAE [EEE TKDE Mrabah
2022
76.7
57.3
37.9
42.0
74.0
33.4
37.9
Q-GMM-VGAB (Ours)
26.2
58.7
56.3
72.7
47.4
48.8
69.0
34.8
34.0
Table 2: Comparison of all methods attributed datasets. We classify the basclines into three primary groups: the first includes traditional clustering algorithms and GNN-free methods, serving relevant basclines for our Q-MAGC method. The second category compares GNN-basod methods with Q-GCN, and the last, comprising the most performant methods, consists of VGAE-based baselines for Q-VGAE and Q-GMM-VGAE.
5.5 Ablation Studies
Comparison of running times
Comparison of running times
Time (s) Cora and CiteSeer
Cora
100.
100
CiteSrer
(mm)) Publi
40
40
Timm
RGC/D PGCI--AAa MAGE
Q-GCN
Q-YGAE
GMM-VGAR
R-GMM-VGAR VGAE
Q-GMM VGAE
Methods
Figure Comparison of running times of methods. scale for PubMed (right axis): mins, scale for others (left axis): secs. Q-VGAE and Q-GMM-VGAF achieve better performance while needing 75% less runtime. Q-MAGC achieves <90% of this performance while needing less than half the runtime.
In Figure 2 we compare the running times of our method with other basclines. Our method consistently takes less than half the time across all datasets. Notably, on PubMed (large dataset), state-of-the-at methods GMM-VGAE, and R- R-GMM-VGAF, (unmodified) require approximately 60 minutes for clustering,
11

---

Published in Transactions on Machine Learning Research (06/2025)
Braxil
Europe
USA
Method
ACC
NMI
ARI 1
ACC
NMI
ARI
ACC 1
NMI
ARI
GAE 1Neur[PSS16]
62.6
37.8
30.8
47.6
19.9
12.7
43.9
13.6
11.8
DGT [[CLR'19]
64.9
31.0
30.4
48.6
16.1
12.3
52.2
22.9
21.7
GIC [PAKDD'21]
40.5
23.5
14.1
40.4
9.4
6.2
49.7
22.1
19.9
DAEGC [AAAT19]
71.0
47.4
41.2
53.6
30.9
23.3
46.4
27.2
18.4
Q-GCN (Ours)
51.1
31.9
23.7
45.5
30.8
25.1
43.8
19.1
14.8
VCAE [NcurIPS' 16]
64.1
38.0
30.7
49.9
23.5
45.8
23.1
Q-VGAE (Ours)
50.1
35.0
19.8
46.6
19.5
17.5
46.2
19.5
16.9
GMM-VGAR 2AT
70.2
46.0
41.9
53.1
31.1
24.4
48.1
21.9
13.2
R-GMM-VGAE [EEE 22DE
73.3
45.6
42.5
57.4
31.4
25.8
50.8
23.1
15.3
Q-GMM-VGAE (Ours)
68.4
46.0
42.4
47.9
32.2
23.5
46.6
23.1
13.1
Table 3: Comparison of all methods on non-attributed datasets.
whereas our Q-GMM-VGAE delivers superior performance in under 15 minutes, representing 75% reduction. Additionally, Q-MAGC runs even faster, completing in just 6 minutes PubMed, and achieves approximately 90% of the performance.
Modularity Metric Comparison with FGC and DMoN
Cora
CiteSeer
PubMed
et
NMI
C
Q
NMI f
4
Q
NMI f
DMoN
12.2
76.5
48.8
5.1
79.3
33.7
17.7
65.4
29.8
FGC
58.4
25
23.1
41.6
41.1
31
21.6
44.1
20.5
Q-MAGC
13.3
72.5
51.7
16.8
64.9
40.16
26
40.3
28.1
Q-GON
13.6
73.3
58.3
5.8
74.5
46.7
8.27
55
31.5
VGAE
17.6
60.8
38.1
12.8
55.8
21
13.5
45.8
26.9
Q-VGAE
9.5
71.5
58.4
4.6
72.4
47.3
9.4
52.12
31.8
Table 4: Comparison of modularity and conductance the best NMI with FGC and DMoN. Note that DMoN is optimizing only modularity, whereas optimizing other important terms well, mentioned in Equation 5, and thus gain lot on NMI by giving up small amount of modularity, making us closer to the ground truth.
We treat modularity as a metric and measure the gains observed in modularity over other baselines on the Cora, CiteSeer, and PubMed datasets. We report two types graph-based metries: modularity Q and conductance C, which do not require labels. Conductance measures the fraction of total edge volume pointing outside the cluster, with C being the average conductance across all clusters, where lower value is preferred.
we observe that although DMoN Tsitsulin et al. 2023) achieves the highest modularity, our method attains significantly higher NMI. For CiteSeer, we achieve a 40% improvement in NMI with only an 8% decrease in modularity, positioning us closer to the ground truth. Additionally, our methods outperform their foundational counterparis, with Q-MAGC outperforming FGC, and Q-VGAR putprrrriing VGAF. Although modularity is a valuable metric optimize, the maximum modularity labeling of graph does not always correspond to the ground truth labeling. Therefore, it is crucial to include the other terms in our formulation. While optimizing modularity helps approach the optimal model parameters (where NMI = 1), it can deviate slightly. The additional terms in our formulation correct this trajectory, improving results.
From Table 4
Importance of and Evolution of different loss terms We analyze the evolution of the different loss terms during training and empirically show in Figure 3b) that the value of each term converges and no terms are counteracting. We provide more details Appendix NJ Additionally, we measure the impact of cach term separately by removing terms from the loss one by one shown in Figure 3a This shows that the synergy of these terms when combined essential for clustering.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Cumulative Impact different parameters
Individual evolution of loss terms
00
variable Cara Coosoor
1,5
varsable
thesa
AboMaxx Normalzoo Value
gommo
0.-
NM
10
0.5-
01
-1.5
P+A. Active Parameters
50
100
150
2003
250
500
204
Epochs
Figure (3a): Impact of active parameters clustering performance. All terms in the loss Equalion 5) are repre- sented by their parameters, for example the modularity term by B. w represents the non-parameterized term.
Figure (3b): Evolution of the different loss terms while training on the Cora dataset. Each series has been normal- ized by its absolute maximum value to allow for observa- tion of convergence behavior. All terms show convergence except for y which remains almost constant.
Figure 3: Ablations independent loss terms. Each term is represented by its weight parameter.
Also, Appendix subsection K.2 we conduct a sensitivity study, and we find that ||CXc - X is the most sensitive to a change in its weight a, followed by the terms related to 7 3 and then A. This makes sense because if that constraint (relaxation) is not being met, then C would have errors. Even though some of the terms do the heavy lifting, the other regularization terms do contribute to performance and importantly, change the nature of C The smoothness term corresponds to smoothness of signals in the graph being transferred to the coarsened graph which encourages local 'patches' /groups of C to belong to the same cluster. The term 7 ensures that the coarsened graph is connected i.e. preserving cctuttr relations, which simple contrastive methods destroy; this affects C by making it so that Oc has minimal multiplicity O-eigenvalues.
Visualization of the latent space
a) Q-VGAE
Time
b) Q GMM -VGAE
miro
Figure 4: Evolution of the latent space of a) Q-VGAE and b) Q-GMM-VGAE over time for Cora. Colors represent clusters.
In F Figure 4 we visualize how the latent space of the Q-VGAE and Q-GMM-VGAE changes over time for the Cora dataset. Plots for the rest of the datasets can be found in the Appendix O We use UMAP (Uniform Manifold Approximation and Projection) (Mcinnes et al. 2018 for dimensionality reduction. Q-GGAE starts from random initialization whercas Q-GMM-VGAE initialized with the weights learnt from GMA- Both embeddings improve as training progresses. This shows that Q-GMM-VGC VGAE learns better representation iee. clusterable embeddings which improve time.
13

---

Published in Transactions on Machine Learning Research (06/2025)
6 Discussion
Performance. Our methods consistently outperform their counterparts. Q-MAGC demonstrates significant superiority over traditional algorithms and GNN-free approaches because of the inclusion of modularity, smoothness, and comnectedness terms in our objective. To compete with GNN-based methods, we leverage their powerful message- paaaaggg mechanisms. Q-GCN surpasses other SCCN-ased methods, such as AGE and DCRN. For the same reasons, Q-VGAE achieves better results than other VGAE-basch methods.
Efficiency. Our methods efficient in both complexity and implementation, demonstrated in the Complexity Analysis | and the Ablation Comparison of rumning times.
So, we conclude that Q-MAGC is well suited for light/edge applications where efficiency and reproducibility is key, since is deterministic.
The Q-GCN architecture assigns the role of both embedding the graph and predicting the assignment matrix the same network, so is understandably less performant.
In most cases, Q-VGAE should serve better, considcring the extra GMM pretraining that is required for the GMM-VGAE architecture. Depending on underlying data distribution, Q-GMM-VGAB might work better if the distribution is very complex and would help from separate priors being learnt for each cluster.
Limitations. If the modularity of a graph, calculated from the ground truth labeling, is low, our method may not perform optimally and can be slower to converge since maximizing modularity in such cases is not ideal. However, our method still manages dataset, where all graphs exhibit low modularity based on ground truth labels. This is due the other terms in our weighted loss function, which become the primary contributors to performance.
match or surpass state-of-the-art methods on the Airports
References
Georgios Arvanitidis, Lars Kai Hansen, and Soren Hauberg. Latent space oddity: on the curvature of deep generative models. In International Conference on Learning Representations, 2018. URL https //openreview.ner http://ww.....ttoooom///d/-//a/-
Aritra Bhowmick, Mert Kosan, Zexi Huang, Ambuj Singh, and Sourav Modya. Dgeluster: A neural framework for altributed graph clustering via modularity maximization, 2023.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th International Conference on Machine Learning, ICML JMLR.org, 2020.
Peter J. Bickel and Aiyou Chen. A nonparametric view of network models and newman girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068 21073, 2009. doi: 10.1073/ (41107//pnc http//aas..000 0m0.0999000.1.66 URL https://www pnas. wwtp///ggggg/////o///e/// 1tt.////pa...0000001111000 0907096106
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities large nerkorks. Journal of Statistionl Mechanics: Theory and Eaperiment, P00000)) oct 2008. ISSN 1742-5468. doi: 10.1088/1742-54466 2200//200////0 000////00000000//0000000 URL https://dxx /ww. org/10
Igor Bogdanov and Vladimir Shehur. Variational autoencoders with euclidean and hyperbolic latent spaces for population genetics. In 2021 XVII International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY), pp. 91 94, 2021. doi: 10.1109 10.1100//EOOUUDDA...... /EDDUUDDAACC113332222.....
Ulrik Brandes, Daniel Delling, Marco Gaertler, R. Gorke, Martin Hoefer, Zoran Nikoloski, and Dorothea Wagner. On modularity clustering. Knowledge and Data Engineering, IEEE Transactions on, 20:172 - 188, 03 2008. doi:
David Buterez, Ioana Bica, Ifrah Tariq. Helena Andrés-Terré, and Pietro Liò. CeIVVGE: an unsupervised scRNA-seq analysis workflow with graph attention networks. Bioinformatics, 38(5):1277-1288) 12 2021. ISSN
14

---

Published in Transactions on Machine Learning Research (06/2025)
1367-4803. doi: 111009//bonnfrrmttii//abbbb// URL httpp///////oooooo///////////ooo btab804]
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Europeann Conference Computer Vision, 2018.
Nutan Chen, Alexej Klushyn, Francesco Ferroni, Justin Bayer, and Patrick Van Der Smagt. Learning flat latent manifolds with VAËs. In Hal Daumé III and Aarti Singh (eds.), , Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1587-1596. PMLR, 13 18 Jul 2020. URL /ttp/t/tpp///ppoceeddig.... mlr www.ppressssee wttpa///1119/ceee...1111 html
Yi Cheng and Xiuli Ma. seGAC: a graph attentional architecture for clustering single-cell RNA-seq data. Bioinformatics, 38(8):2187 2193, 02 2022. ISSN 1367-4803. doi: 10.1093/ 10.:1000///bbiinnnoo thoinformatics/btaaalo URL
pttps://doi.org. htt.:////.....iooooaaaeee//aaaaa
Jun Jin Choong, Xin Liu, and Tsuyoshi Murata. Optimizing variational graph autoencoder for community detection with dual optimization. Entropy, 22(,), 2020. ISSN 1099-4300. URL
wwwp://dppcoomm
1099-4300/22/2199
Marissa Connor, Gregory Canal, and Christopher Rozell. Variational autoencoder with learned latent structure. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2359 2367.
PMLR, 13-15 Apr 2021. URL httts::/prooeeddnngs laiiigs.mr..ppp..... press//130/coonoo///
html
Ganqu Cui, Jie Zhou, Cheng Yang, and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. In Proceedings of the 26th ACM SIGKDD Internalional Conference Knowledge Discovery & Dala Mining, KDD '20, pp. 976 985, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984. doi: 10.1145/3394486..33 //////3994466343411444 URL https://dol.org/// http:://.66.l...00000111644444.0 3403140
Fnu Devvrit, Aditya Sinha, Inderjit S Dhillon, and Prateek Jain. S3GC: Scalable self-supervised graph clustering. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in
Neural Information Processing Systems, 2022. URL https::/ http:://pppaaaeeeeeeeeec//o/aaaa nwt./oorurriddd1111vssit..
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. TEEE Transactions on Pattern Analysis and Machine Intelligence, 20(11):1944-1957 2007. doi: 1ALL199/TPMM.20000
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch gcometrie, 2019. URL
http///bb/1990.../ 02428 cite arxiv:1903.02428.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2):298 305, 1973.
URL
Santo Fortunato and Mare Barthélemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36 2007. doi: 10.1073/ m60.00605961104 URL httpp::// https:://www.pttt pnas. pna..org/ org/ doi/abs/10 1tt.b///....1/////11 000da65166099551
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2083 2092. PMLR, 09 15 Jun 2019. URL https::/prooceeding.. mlr. press//97/ gao html
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '16, pp. 855 864, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 00.1145/293977..23377. URL https://doi.org/// http:///ooo..or//...111///2222. 2939754
Roger Guimerà and Luis A Nunes Amaral. Functional cartography of complex metabolic networks. Nature 433(7028):8955 900, February 2005. TSSN 0028-0836. doi: n0.1038//aaure00288..
15

---

Published in Transactions on Machine Learning Research (06/2025)
Roger Guimerå and Luis Amaral. Cartography of complex networks: Modules and universal roles. Journal of stalistical mechanics (Online), 2005:ihpaa3557, 03 2005. doi: 101188//74255/0882200/2/2222222
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge transfer for out-of- knowledge-basee entities: A graph neural network approach. In Proceedings of the Twenty-Sinth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 1802 1808, 2017. doi: 10. /1000////aai22171///// 24963/1jcai 2017/250
URL https:///oi.orgg
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In Proceedings of International Conference on Machine Learning, pp. 9451-3461. 2020.
Binyuan Hui, Penglei Zhu, and Qinghua Hu. Collaborative graph convolutional networks: Unsupervised
learning meets semi-supervised learning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):4211-44222 Apr. 2020. doi: 10.1600/aami..v34444..888 URL https://ojs. aaai orw/oorgger. php/ AMAT/articcle/viee//558.
Brian Karrer and M. E. J. Newman. Stochastic blockmodels and community structure in networks. Phys. Rev. E, 83:016107, Jan 2011. doi: 10.100//Plysseee.....011100 URL https://iink..ps.orrrt org.////oi/o/////0/
1103/PtysRevE.83.0.6..
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders, 2016a.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv, 020009
2016b. doi: 10.48550/ 10.48550/ARXIV. ARXIV, DEAXIV.1609.0220 16099.0297. URL
Manoj Kumar, Amurag Sharma, and Sandeep Kumar. A unified framework for optimization-based graph coarsening, Journal of Machine Learning Research, 24(118):1 50, 2023. URL http://jmlr /
v24/22-1085 html
Sandeep Kumar, Jiaxi Ying, José Vinícius de M Cardoso, and Daniel P Palomar. A unified framework for structured graph learning via spectral constraints. Journal of Machine Learning Research, 21(22):1-60, 2020.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning, 09 15 Jun 2019.
Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. Deep graph clustering via dual correlation reduction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7603-7611, 2022.
Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Siwei Wang, Ke Liang, Wenxuan Tu, and Liang Li. Simple contrastive graph clustering. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-12, 2023a. doi: 1..1109/TNNTS.... 202.3327777.
Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Zhen Wang, Ke Liang, Wenxuan Tu, Liang Li, Jingcan Duan, and Cancan Chen. Hard sample aware network for contrastive deep graph clustering. In Proc. of AAAI, 2023b.
Andreas Loukas Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(116):1 42, 2019. URL http:///aa...ooo/ppppes///////00
Andreas Loukas and Pierre Vandergheynst. Spectrally Approximating Large Graphs with Smaller Graphs. In Proceedings of the 35th International Conference on Machine Learning, pp.
PMLR, 2018. Costas Mavromatis and G. Karypis. Graph infoclust: Maximizing coarso-grain mutual information in graphs. In PAKDD, 2021.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Leland McInnes, John Healy, Nathanicl Saul, and Lukas Großberger. Umap: Uniform manifold approximation and projection. Journal of Open Source Sofbware, 3(29):861, 2018. doi: 10.21 105/ URL
https:://doi.org1100 /o0r////...0////..s..oooo 00861
Anindya Mondal, Shashant R. Jhony Н. Giraldo, Thierry Bouwmans, and Ananda S. Chowdhury, Moving object detection for event-based vision using graph spectral clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, pp. 876 176-884, October 2021.
Nairouz Mrabah, Mohamed Bouguessa, Mohamed Fawzi Touati, and Riadh Ksantini. Rethinking graph auto- encoder models for attributed graph clustering. IEFE Transactions on Knowledge and Data Engineering, pp. 1-15, 2022. doi: 10.1109/KKDD.2222..222222 322.094448...
M. E. J. Newman. Fast algorithm for detecting community structure in networks. Phys. Rec. E, 69:066133, Jun 2004. doi:
URL
aps http://///...1/////ppaaaa///////
066133
M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Phys. Rec.
E, 74:036104, Sep 2006a, doi: 10.1103 1A..10//Pyyseee227440000000 URL https::/link..g::: ortpp//orr/////1.110.... /ttpp//ttp//.........oooo////o/.
PhysRevE.74 74.036104
Mark E. J. Newman. Modularity and community structure networks. Proceedings of the National Academy of Sciences of the United States of America, 103 23:8577-82, 2006b.
Krzysztof Nowicki and Tom A. B Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96 (564)44111777100000 2001. doi: 10.1198/0162) 4501 753208735. URL
.or.orgg///0 10. /ttp://///oooooo//////////////10 11081//00/62445555533888333
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the Twenty- Sevent International Joint
Conference on Artificial Intelligence, IJCAI-18, pp. 6609-2615. International Joint Conferences on Artificial Intelligence Organization, 7 2018. doi: 10.24963/ 22//44//////ai./// 20jaai.201/// 2018/362. /362. 2018/362
URL htt.::tt:::/ htttp::/ddoi.rg//// 241.110.44421/jjoo...
J. Park, M. Lee, H. Chang, K. Lee, and J. Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In 2019 IEEE/CVF International Conference Computer Vision (ICCV), pp. 6518 6327, Los Alamitos, CA, USA, nov 2019. JEEE Computer Society, doi: 10.1009/1CCV.201900663 URL https://doi. www.compttersocciee.yoooooo www.:oiiiiitttto/ee..eo 10./ 1109/ICCV ICCV www.C...01..... 2069.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVilo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Newral Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http://papers..r nwwrors......p....e.. cc.paper/ 9015
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,
KDD '14. ACM, August 2014a. doi: 011145//623330222277333 URL http://dx.doo doi http://dx.ddi..o//1/1... org/10. 1145/
2623330 2623732
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '14, pp. 701-710, New York, NY, USA, 2014b. Association for Computing Machinery. ISBN 9781450329569. doi: 0..1145/623330.260
URL
111/////.114//223330 2623732
Ketan Rajawat and Sandeep Kumar. Stochastic multidimensional scaling. IEEE Transactions on Signal and Information Processing over Networks, 3(2):360-31) -753677775 2017. doi: 10.1 10.110//TSPPN.207..26661
17

---

Published in Transactions on Machine Learning Research (06/2025)
Mcisam Razaviyayn, Mingyi Hong, and Zhi-Qu Thi-Quan Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Oplimizalion, 23(2):1126-11 2013. doi: 10.1137/120891009. URL /ttppe///oo..rrgg10111////////// 3T1/10..113/122891000
Guillaume Salha-Galvan, Johannes F Lutzeyer, George Dasoulas, Romain Hennequin, and Michalis Vazir- giannis. Modularity-awaare graph autoencoders for joint community dctection and link prediction. Neural Networks, 153:474 495, 2022.
Jianbo Shi and J. Malik. Normalized cuts and image segmentation. IEEE Tronsactions on Pattern Analysis and Machine Intelligence, 22(8):888 905, 2000. doi: 10.1 7..1109/44.866888
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: Extraction and mining academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '08, pp. 990-998, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605581934. doi: 10.1145/1401890.4422222 1145/1401890 1402008
URL https://doi.
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Mllel Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1 2023. URL http://jmlr.org
papers/v24/20-998.15 html
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep Graph Infomax. In International Conference on Learning Representations, 2019. URL https :
//openreview. wtwp:/rrwweeeeeeeeoommm/d//////e nett/forum?Pd=xx222AAAd
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering:
A deep attentional embedding approach. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3670-3676. International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 10.24963) /ijc://caaai/// 2019//0999
URL /ttps://doi..rgg /ttp/////..........///////////// jaaii/jcaia/// 2019/509
Yen-Chuen Wei and Chung-Kuan Cheng, Towards efficient hicrarchical designs by ratio cut partitioning. In 1989 JEEE International Conference on Computer- Design. Digest of Technicol Papers, pp. 298-301, 1989. doi: 10.1 10.1109/ICCAM (009/CCCAD1199) 799777777777
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URI wtt.htttps//pprceedinng cetiigs.euriip... cc neurips.cc/paper files/paper. 0018///11e/777b0ff77997777666660
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAF19, pp. 4327 4333. AAAI Press, 2019. ISBN 9780999241141.
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtielh International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 3434 3440, International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10.24963 10.24963/jjcai.2009 2021/// URL httpss://oo..orgg/0..299// 2031/473 Main Track.
Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics, 40(4):2266 - 2292, 2012. doi: 10.1214/ 12-AOS1036. URL https://i /1t/:/..000000..1112/20100001110
1214/12-00100008
18

---

Published in Transactions on Machine Learning Research (06/2025)
Appendix
A Implementation
20
B Litcrature Survey
20
C Convexity of terms in the optimization objective
21
D Optimal Solution of Optimization Objective in Equation 6
22
E Proof of Theorem
(Convergence)
23
F Complexities of some graph clustering methods
24
G Proof of Theorem 2 (Consistency Analysis DC-SBMs)
24
Detailed Prool of heorem
24
G.2
Proof of Theorem 2 Conditions for Consistency
25
G.3
Required Condition a): Lipschitz Continuity
G.4
Required Condition b):
Continuity of directional second derivative
................................
31
G.5
Required Condition c): Upper bound of first derivative
32
H
Attributed SBM theory and results
33
VGAE
35
Dataset. Summaries and Metrics
35
K Hyperparameters
35
K.1 Hyperparameter Tuning
35
K.2 Sensitivity study
35
L Training Details
36
M Results on very large datasets
36
N Evolution of different loss terms throughout training
36
Visualization of evolution of latent space
36
P Explanation on why VAE manifolds are curved
37
19

---

Published in Transactions on Machine Learning Research (06/2025)
A Implementation
The implementations for all the experiments can be found at ottttpps//ggghhu...oo///luuuuuuu
We have extensively used the PyTorch (aaszke
(PazchpPaszzk et al. 2019) and PyTorch Geometric Fey & Lenssen 2019)
libraries in our implementations and would like to thank the authors and developers.
B Literature Survey
In this section, we review relevant existing works and highlight their limitations, thereby motivating the need for improved clustering formulation.
Graph Clustering via Coarsening. Graph coarsening can be extended to graph clustering by reducing the size of the coarsened graph to the number of classes (k). However, in most graphs, the number of classes is very small, and reducing the graph to this extent may lead to poor clustering quality. DiffPool (Ying et al. 2018) learns soft cluster assignments at each layer of the GNN and optimizes two additional losses, an entropy to penalize the soft assignments and a link prediction based loss. Next, SAGPool {Lee et al. 2019) calculates attention scores and node embeddings to determine the nodes that need to be preserved or removed. Top-k [aao & Jil 2019) also works by sparsifying the graph with the learned weights. MinCutPool (Bianchi et al. 2020) formulates a differentiable relaxation of spectral clustering via pooling. However, Tsitsulin et al. (2023 show that MinCutPool's orthogonal regularization dominates over the clustering objective and the objective is not optimized. Some disadvantages of these methods are instability and computational complexity in the case of SAGPool and DiffPool and convergence in MinCutPool. To address these challenges, we need a better loss function to perform the clustering task effectively.
Deep Graph Clustering. Previous literature can be classified based on contrastive and non-contrastive methods. On the non-contrastive side, Pan et al. (2018) proposed ARGA and ARVGA, enforcing the latent representations to align to prior using adversarial lcarning. By utilizing an attention-based graph encoder and a clustering alignment. loss, Wang et. al. (2019) propose DAEGC. Liu et al. (2022) design the DCRN model to alleviate reprosentation collapse by a propagation regularization term minimizing the Jensen Shannon Divergence (JSD) between the latent and its product with normalized A. Contrastive methods include AGE (Cui et al.) 2020) which builds a training set by adaptively selecting node pairs that are highly similar or dissimilar after filtering out high-frequency noises using Laplacian smoothing. Zhhoo et al. (0021 propose GDCL to correct the sampling bias by choosing negative samples based the clustering label.
VGAEs (Kipf & Welling, 2016a) are an increasingly popular class of GNNs that leverage variational inference (Kingma & Welling 2014) for learning latent graph representations in unsupervised settings. They reconstruct the adjacency matrix after passing the graph through an encoder-dccoder architecture. Many attempts have been made to use VGAEs with k-means on latent embeddingss, but il has been unsuitable for clustering. This is primarily because embedded manifolds obtained from VGAES are curved and must be flattened before any applicd. Refer to Appendix for detailed explanation. VGAEs only use a single Gaussian prior for the latent space, whereas clustering requires the integration of meta-priors. Additionally, the inner-product decoder fails to capture locality and cluster information in the formed edges. Several clustering-oriented variants of VGAEs (Mrabah et al. 2022 Hui et al., 2020) have been developed that overcome most of these challenges. GMM-YGAE (Hui et al. 2020 partitions the latent space using a Gaussian Mixture Model and assigns separate prior for each cluster to better model complex data distributions. Despite the improvement in performance, it's inner-product decoder cannot capture locality information.
clustering algorithms using Euclidean distance
Modularity Maximization. Various heuristic algorithms have been established that solve the NP-hard problem of modularity maximization including sampling, simulated anncaling (Guimerà & Nuncs Amaral Guimerà & Amaral 2005), and greedy algorithms (Louvain/Leiden (Newman) 2004]] Blondel et al.,
2005
2008 These algorithms require intensive compute and don't use node features. Modularity maximization using GNNs has also garnered attention recently. DMoN (Tsitsulin et al. 2023) optimizes only for modularity with a collapse regularization to prevent the trivial solution, but offers no theoretical guarantees about
convergence. Modularity-Awar Aware GAFs and VGAFs (Salha-Galvan et al. 2022 use a prior membership matrix
20

---

Published in Transactions on Machine Learning Research (06/2025)
using Louvain algorithm and optimize for modularity using RBF kernel as proxy for same-community assignment. DGCLUSTER (Bhowmick et al., 2023 is semi-supervised method that makes use of either a subset of labels or pairwise memberships as Auxiliary Information coupled with modularity.
C Convexity of terms in the optimization objective 5
When Xe is kept constant, LMAGC gets reduced to:
8 tr(C BC)
min f(C) = tx(x3 |CXc 1-c0--111 X||
(15)
20
y log J) A |
subject to C E S. where, J= k: loxk
(16)
The term MIXCCOOCX is convex function in C. This result can be derived easily using Cholesky Decomposition on the positive semi-definite matrix @ (i.e. = L)" tr ((Xxc))) cO LF LCXc)
([([LXX)) -
Frobenius norm is a convex function, and the simplified expression linear C. Hence we can deduce that the tr(.) term is convex in C. The terms |CXc -XI and ||TT|, are convex because Frobenius norm and h norm are convex in C.
For proving the convexity of - do + J) we restrict function to line. We define function g: (t) f(= + tu)where, t dom(g); 2 dom(f), RR. uE
A function f R= R is convex if g: R is convex.
The graph Laplacian matrix of the coarsened graph (0z) is symmetric and positive semi- having rank of k-1. To convert Oe to positive definite matrix, we add rank matrix J = 1 (0. + J = =I,"L)
f(L) - log det de J) log det L)
(17)
Now substituting L Z + 1U in the above equation.
g(t) log detedetteeae
log det( 20=
= log det (1(_:=/01100000110100001"1101010
substituting
P UZ-1
- (log det ( (TTZ) log det + + +PPTPP)
Eigenvalue decomposition ofP QAQ² andQQ" =
-
(log deddeel"""" 7) + log del (QQ" + 21QAQT + +1QNQQT))
(log (Teet(222 log det (Q +AA3)TT))
log del( (2TZ) log(1 l + 21A, + +(x))
Finding double derivative of 9t):
21 + 12,22
g²(1) Σ
(18)
(1+ 12X3)2
21

---

Published in Transactions on Machine Learning Research (06/2025)
Since 9²(t) 2 04 R. g(t is convex function in t. This implies fLL is convex in L. We know that,
C + J I. so,
L L= + 1
1xx
Vkp
Since linear in C and ((L) is convex in L, - log det C +C++) is convex in C.
Optimal Solution of Optimization Objective in Equation
We first show that the function f(C) is L Lipschitz continuous gradient function with L max(In, Lz, L,, L4, Is), where I,, T2, La, I4, andIs are the Tipschitz constants of Ir (x(x - -2- Ir(( BC), log de J), ||Cxc - (li..add ||
For the (=(x)C* term, we apply triangle incquality and employ the property of the norm of the trace operator:
||tr||
sup [tr([]
M²0 MM]
| -r
< http://0-CCC.Cccc/////////1/1/10 ||
-
(Frobenius Norm Property)
s 2//|||=|||XX|||||/||/|///// C2llF ([|il|>= (|C[||==|[Cal]) ||2/| = vp)
s L| C21l1
The term & ||CXc - I| can be written as:
マ - -xCXxcXX) x)x
x (x((x (
tr(x
All the sub-terms except (r(X"X) (constant with respect to C) obtained in the expression will follow similar proofs to tx(xTC*OCXc).
Next we consider the modularity term:
Ior BC) - (rC
(19)
BC1) BC) - tr( BC2)
(20)
BC1) -
ttr(C [|r]]][((I- - - CC) BC2llr
(21)
(22)
[|][]] Colle[[C[|]++ 1 (Frobenius Norm Property)
(23)
-
(24)
The Lipschitz constant for -y log det 0C JJ) )) linked to the smallest non-zero eigenvalue of the coarsened
Laplacian matrix (0z) and bounded by (A 1j2 Rajaaat & Kumar 2017) where 8 is the minimum non-zero weight of G..
tr(1 (1TCCTCO C1) can be proved be Ls Lipschitz like the modularity and Dirichlet energy (smoothness) terms. This concludes the proof.
22

---

Published in Transactions on Machine Learning Research (06/2025)
The majorized problem for L-Lipschitz and differentiable functions now be applied. The Lagrangian of the majorized problem, 10 is:
[(C,Xc, 1 c u +
ph ||T 1/2 1,.., ||c,,112 ,,,,,,I|,,,11- 1|c - I]?
(25)
where μ [M1, are the dual variables and ((++1) - [V is the unnormalized C' after th
majorizing ileration.
The corresponding KKT conditions (w.r.t C*) are:
C - in + 2/122 Co ... 12, C.. ... 122 0p
(26)
/ 1, | 1 - ,.... ...
c
2
1,
T
(27)
p
14 C
(28)
in 2
(29)
P2 00
(30)
C20
(31)
[ < Vi
(32)
The optimal solution these KKT conditions is the normalized version of C+++1)) 1)
(Cil+1)y
((++1)=
(33)
Σi [ 13
E Proof of Theorem 1
(Convergence)
In this section, we prove that the sequence {C'+1, [x+1] generated by Algorithm Karush Karush-Kuhn-Ta Kuhn-Tuckee (KKT) optimality points for Problem
converges to the set of
The Lagrangian of Problem
comes out to be:
B -Ir(CTBC)
f(C, ((,,X,,)) =) =I(EC""XXXX] |CC X|2
(34)
2e
lo =olg X
| 1 c C
Σ U25 ||
(35)
where μ [2] are the dual variables.
w.r.t. C, the KKT conditions are
20CXxX + +aCXXc XXXX 8
BC -0-2000 + J)
(36)
+ACI+XA - in + 2( C/ ...
..., 12 CT
12g CT1
0
1 ||cf112 1, | 1/2 c 2
0
(37)
C =
0
(38)
2 #l
(39)
2 #2
(40)
020
(41)
MA 1
(42)
23

---

Published in Transactions on Machine Learning Research (06/2025)
Now, C
lim C is found from Equation 11
C C + I
a(c 200 a -Xxx =C
(43)
(000 00 J)- 1 + X0 X0 1axk
0 XX a Xc x)X² _ B
(44)
-200000000 (cx* + +J- 1 + X0 1x
So, for μ 0, C satisfies the KKT conditions.
w.r.t. Xc, the KKT conditions are:
2CT OCXc + aC - X)
(45)
So, x lim X found from Equation 14 will satisfy this as that equation is just a rearrangement of the 1-000
KKT condition.
F
Complexities of some graph clustering methods
Some GCN-based clustering methods:
AGC AGC et al.
2019 Opp2nt + ent2))
where t is the number of iterations (within an epoch)
R- R-VGAE Mrabah et al. 2022 Oppk2n (p(n + k)) + e(p + k))
Sevvit et al. 2022) - Opm)ss)
where is the average degree
HSAN et al.) 2023b) OppBn)
they state it as OBd' but that is only for batch of size B and not the whole epoch VGAECD-OPT (Coong et al. 2020) O(p2nD4)
where D is the size of graph filter, is the number of lincar layers
G Proof of Theorem 2 (Consistency Analysis on DC-SBMs)
G.1 Detailed Proof of Theorem
Proof. The proof is divided into two parts. First, we demonstrate that LM AGG can be expressed in terms of O and Second, we verify that, in this form, LMAGE satisfies the regularity conditions specified in Theorem 4.1 of Zhao et al. (2012). Tt is important to note that DC-SBMs do not consider node features, so we treat X and Xc as constants. We start by noting that O = CT AC, i.c., the edge count matrix O is the
version of the adjacency malrix A. This has a good intuition behind it, as C is the mapping from nodes to classes, and it can also be proved easily.
F
{OT AC DC = (CD =
(46)
i13=1
i=1j=1
Ciy equals only when node is in cluster g, and Cjt equals only when node j is in cluster Therefore, this expression simplifies to the definition of O.
(CT AC Σ Σ A 1y: =1
(47)
24

---

Published in Transactions on Machine Learning Research (06/2025)
This can be viewed as the cluster-level adjacency matrix, which quantifies the edges between clusters. Next, we formalize the relationship between O and C DC, where D = diag(d) is the degree matrix.
P
P
{CT g0
CipiC
E CigdCaa [Dy= = =
(48)
;=1==
Since the of C are orthonormal, for the diagonal entries of C DC:
Ca = if and only if q = Thus, we obtain the following expression
p =
{C DCDDCm
Σ
O2 1q
Σ
Cipds
E-Cyeto.11
(49)
Now, we consider
[ (CCAA]]p
Cgn Ais
Cji = 1=1
Cig Aij 1=
1= Σ Cipd
(50)
:=1j=1
Thus, we showed that Ca Ef ACI,), which intuitively represents the cluster-level degree matriz because it the (diagonal of) row row/colum now/colum-suum of the C" AC or cluster-level adjacency matrix. We now express the Laplacian of the coarsened graph as function of O, Oc(O) CT CD A)C tr(C BC), and log det CC + J) in
diag(Ei= O₂) - O. This implics that the terms our clustering objective are functions (c()). Using Theorem 4.1 from Zhao al. (2012), we conclude that CMAGC must be uniquely minimiized at any point (v²,, Ar) s.t. Ep (yp) x and [A(] A'.
The Laplacian O can be written as function of the adjacency Oij -E
Al, (assuming no self-loops).
For the modularity term, this has been proven in Theorem 3.1 of Zhao et al. (212)). For the constraint relaxation term CXC - x we see that Xe is a function of only O(y") and (AA)) from it's update
rule equation 14 so we get term, θ) = {I(C(u") X""""
X tr tr(XoCTer (CXx) is already just a function of Xc, C, θ which we have shown above to be functions of only A', By the same logic, - log det (C (C OC + J) is also a function of only y", A (J a constant [(xk). Thus, IMAGe can be written as required above.
Next, compute the population version of LMAGC-
F(H(S),h(S)) = El-LM C,t] = (I(H()) M()) + ((H(S)) + ((((S))))
(51)
smoothness
log-determinant
modularity
where, (()) = un,r(x - diag(
((S))))Xo)
(52)
j=1
(((H()))(8)) b
Pr (H()) diag(
1 H(S):s)
+ klog
(53)
1=1
(((H())))())) tr(H
( H)))
(54)
Po
Po
and, Po
Po=) Σ=>nn Hato : #o Σ
xallon with Σ # 1, since E[t.]
(55)
ab
For brevity, denote ((H h(S)) by F(S). Now for the second part of the proof, it is easy to prove that F(S) satisfies the regularity conditions stated in Lemma I The detailed proof is presented in the following
subsections. This concludes the proof that LMAGO is strongly and weakly consistent under the DC-SBM. ]
G.2 Proof of Theorem Conditions for Consistency
As previously defined in Theorem 2 O = C AC and
1 [[
Pp
25

---

Published in Transactions on Machine Learning Research (06/2025)
We need to find "population version' of the loss function in terms of (S).
B|O|C, B[C" - - 1s)
(56)
(CTDCIC, t - diag(
A1j)C1,,
Eldiag Σ 01
(57)
==1
#pdiagg
Σ Hıy)
(58)
j=1
So, for tr( tr(X²
[[xxX(C" = (CX
(CI DC ACIC,(Xx)
(eXXXlup Hτ)) -HH(())
()trrXX(ddiag'
Hij)
-(S))XX))
(59)
Next, we have 1 tr BC), which has alroady been solved in the paper Zhao et al. 2012 in their Appendix 2n (Page 25 of the full document).
Elir(c BC)]=
ΣE
[lkk Pa
HR
2c
Po
For log det(CC J): where J = f
We write log(det(C" + J)) tr(loo(C*TCC J)) since, det(A) etr(log(A)),
-=
(60)
So,
(61)
tr(log(VAV tr(V log( (oV(A)
(62)
log A = log(bl) log [ -1)
(63)
Using the first-order Taylor expansion of log(I [ + X) X, need to choose b such that
A
<
(64)
And for the expansion to be good approximation, we need I - 0. We will enforce this later in Equation 74
26

---

Published in Transactions on Machine Learning Research (06/2025)
tr(V log(bT) +og
T+ A
1 V-)
(65)
A
tr(V [oog(b))
1
V-11
(66)
b
Lr(Vlog(b/)V - + +
tr(1)
(67)
tr(log(bl))
5 tr(( url)
(68)
1 log(bb) + , (r (.) k
(69)
Finding the expectation of from Equation 63
= k log(b) +
tr Z)) ct -
(70)
log(b) [ e, e]()) k
(71)
log((b)
tr (r(EE(" OC J| t)) - k
(72)
b
Using θ D A. Equation 56 and Equation 58
= & log(b) + tr Mpdiag Σ Hig) - 14 (()) k
(73)
which is a linear function in H(S).
For the approximation to be good, we can now simplify I as defined in Equation 64
1
(74)
1 A 11 1
A
$ AIk
A21
5 A22 -
8 A2*
(75)
$ Aui
1 A
Writing out this norm, get quadratic expression in ;
27

---

Published in Transactions on Machine Learning Research (06/2025)
1
2
Xse)
+
k
(76)
6²
b
j=1
w=1
or concisely, = |A|| 82 2tr(A)
+
(77)
Since, is a diagonal matrix, tr(A) = ~
(78)
(79)
Also, since A is the eigenvalue matrix for z²
(80)
|||l = Σ x3 = =r(
(81)
1= t= 1 2tr(z) +h
(82)
Since, << = 1-1<0 = 1 = has real roots. Using simple quadratic analysis (in b), the
discriminant should be positive.
= 4tr(2)² - 4((k 1)tr(22) > 0
(83)
tr(2)² ir( (r(2)) > k -
(84)
The minimum value of == min occurs at
(85)
b tr(23) tr(Z)
tr(2²)
(86)
tr(
tr(2)²
tr tr(Z)²
mmn 1 will exist when
k
(87)
tr(22)
which holds for Lr
(88)
h:
2k-
So we can always choose b <
(89)
k
since min (Z) = 2k [proved in 91
(90)
min mintr(CT J) min mCn) tr(J)
(91)
min (CC AC)) +1
AC)
(92)
2c 2(c (k- 1)) +1
(93)
2k - 1
(94)
Additionally, define n. = E. Iyllon with E. #. = 1, since E[t.] 1.
G.3 Required Condition a): Lipschitz Continuity
Condition 1: We need to show that [F(S)) - F(Sa) < al|S Sall (Lipschitz)
[F(S)) - F(S)) < (S,))) f((S2) (S)( f222 + (fa(8) fa(S2)
(95)
28

---

Published in Transactions on Machine Learning Research (06/2025)
Let's first find [{{)s:) F
H(S) = (Sx)
(96)
[H(()) H(S))lIr (((),))(((Ix) -(52x) 1[55:0((113""5555p((()))
(97)
= =1(())))P((S, -82)x)" + ((S) (()x))
(98)
Next, we see (Eliag()))) ()) - diag(E) H(S)) = ||diag ([jing()= H(S2),)))l
For the first term, (f)(H()))) - ((((((()))(((((()))) define H(S); = =E H(S)
= =mbor((3(H(()) - diag(
diag( Σ
H(S2):)]Xo)
(99)
1=1
5=1
- H - - =Imp (MXXII((S)-H(()))))))
(12) ((S))))
(100)
< 1pp
( (Sx))xo))
tr diag (
(101)
< 1ppl
[rl| (((H(()) (S))) Xc
-||r||l X ((())())()))))))))))))
(102)
|t|||| |t|||| diag diag((H(()):: - 1)
< 1ppl
||||||/ H(S)) H(Sa))
(103)
Taking the first sub-term,
upl ||tr||
||
((S)) - H(S2)
(104)
= =||t||| ||Xc| (Six) - -2)xa)" + - ((S)- S,)x))
(105)
F
< ||tr|] ||Xc|| |P|r (1181=/1 + (|520]1r) [1(5: S2)x21
(106)
< ||t]] ||Xc|]
|P|r (1[S1>/1e [[52=]1e) ||||| [|(S; -2)]lr
(107)
[Sl S2)lFF
(108)
For the second sub-term, define Sea En Fz Skau (Sxx ke
29

---

Published in Transactions on Machine Learning Research (06/2025)
H(S), = E H(S)
Σ
#t Sis =
Σ uo
(109)
==1
08
088
[H(S):: H(S2)xl
Σ T. Pa.Paatinn Paa ian
Σ
TaPasste Pastiii
(110)
esu
Σ Fg Pa (ui -S2)iau
(111)
asu
n. Pa as Tu -2))aul
(112)
T. Pa Tu Jul
1(S2 - S2)iaul
(113)
088
it PasTTll
Σ ((S) S2)iaul
(114)
089
au
aj
Σ
I(S) S2)inul
(115)
au
H(S2):)) So, [[diag((H(S)). - =
H(Si) H(S2)
(116)
a²
(S) S2)
(117)
1=1
au
af e|1| S S2 1.1,2
(118)
For the second term, (s2(H(S))) (2(H))))
Mp (r() diag (H((())))))) ding())))))((((((())))
(119)
b
Hg (S())())) H(S)))
tr (())..))
(120)
b
[n(((()))- -H(()))
tr diag (iag(((((ss)) (((2))1) )
(121)
+ ||tz|| diag (H))) ((S2)a)) )
Mg
||r||| - H(22)
(122)
As shown above,
(123)
ag 02 S2)llr
abll(S: S2)
(124)
For the third term, it has alrcady been proven Zhao et al. (2012). but we also prove it here: (s((H)))) - (a(()))))
30

---

Published in Transactions on Machine Learning Research (06/2025)
tr(H(S:))
E H(S))ss) tr(H((22)
(Ej H (S2)
(125)
Po
Po
Po
Po
(S)) - H(22))
Σi=1 HS)), HS2))
(126)
Po
Po
2
1
$ (S)) H(2)))
+ -
(127)
Po.
Po
1=1
As shown above,
(128)
Sasl((2 S2)lle +
H(S:); H(S2)d) (H(S)), H(S2)a)
(129)
Po
i=1
&
Sasl(s1 S2)llr +
H(()): + H(S.))
Σ ((5))-H(SS))
(130)
Po 1=1
aal((S)
F2)1 + 033 Σ
[S
(131)
aall(S) S2)l F + a S1 S2111,1,1
(132)
G.4
Required Condition b): Continuity of directional second derivative
Condition 2: HD)
8²
052 PMM + s -Mo), to + e(t to))
(133)
-=
02
8²
0²
05 (Mo + e(Mi Mo)) + 022 f2 + - Mo)) + Joz fa + = Mo))
(134)
1t
Finding the directional derivative for f1;
(M + 5(M1 Mo)) Mot + -Mo) diag
(Mo + +(M - Mo)),
(135)
j=1
-Ho (r((XX +E t Mo)Xe)
(136)
- -tr(X (Mo) tr(gg
(M1 Mo)xs1)xo))
(137)
1=1
02
k 06 [MD + =(Mi -Mo) 14 ( Mo) tr (X
Σ (M, Mo)s,l)Xo)
(138)
0²
0e // (Mo + +(MM MMo -
(139)
31

---

Published in Transactions on Machine Learning Research (06/2025)
Finding the directional derivative for f2.
f2 + +(MM Mo))
(140)
Met Mo =((M MM) diag( Σ
b
(Mo + E(M, Mol)
1
b
k -logg
(141)
j=1
0
(Mo + Mb))
M
tr
Mo)
He
diag >
(Mi Molis)
(142)
05
b
b
j=1
0² 0= MM + + - Mo))
(143)
Finding the directional derivative for f3.
+ - -Ma) tr(Mo e(M, - Mo))
EE (Mo + +c(M1 Mo))is²
(144)
Po
Po 2
tr(Mo *E(M1 - Mo))
Σ ( ose Pas (Mo + +c(M] Mo)) )uu))
(145)
Po
Po
2
0
fM + +[(M2 Mo))
0e
tr(M1 - -Mo)
H.P Pasaas (M - Mooiau) x E1=1 (Earn H.Past In (Mo + E(M1 - Moo)sau)?
+ >
Σ
Po
Po
1=1
asu
(146)
02
El= 21E eeen te PaPastuMM - Moliau)
dez fo + =(M1 -Mo)
(147)
PO
Adding up these three,
0² a=a FMMo + e(M - Mo). to + = to)) = Et 25,2(Eas T. P. Pas Mo)
Po
which is continuous in (M,,t, t+) for all (Mo. to) in neighborhood of (W. m)
G.5 Required Condition c): Upper bound of first derivative
With G(S) ((S(S), BG((1=s)D+sS) de
< -C < <OVT,
2=0+
G(S) = (((H(S)) + (2(H(S)) + (S))
Let S ((S ((D-D)))P(D)T + PDt
Dt)
For f1
32

---

Published in Transactions on Machine Learning Research (06/2025)
k
((H(LL=)D++ - diag
H((1- + =))
(148)
j=1
H(S) (Sx)
(149)
H(( + =5) ((1 ((1-8) (DDr ( + +St)
(150)
D)z)²
(151)
(eD (()))))))))))
(152)
+5((S- D)((S-) ( D)z) D)x)²
(153)
Finally, f1((1 - =)D + E5) = ((D +e
(r(x (e
(D))
(154)
+ tr P())) Xc) + + tr(x D)x) D)z)
Xc)
(155)
tr tx diag (H(D).) ( + tix (iig P(Dx) + (Tz)) (z))))
+ + tr tr(X (HH(S D).1)xc)
(156)
(157)
0fi
Now, 0= -=
=tr tr diag( (S)
(158)
For f2,
Het (([1 ([[[-))D++)
+ +s5)al)
1 b
f2(H((1 =)D +ES))
+ ES) diag([H((1 - +)I++
+ klogb (159)
0f2
My
5- diagg(S:))
(160)
0e
b
==01
For Sar
{(M((IE)D++ = tr
((D)) ((( -D)
(161)
Po
+E((S - -D)))((D)) + +E2((S ()s))(((s-())))))))
(162)
[IDD)P(DAN +E (())))))
(163)
) is
=(S ((Do) E D(x) ((S-))((
(164)
0f3 dz -=
2
5
(Lz) ((Dx? T
>iSk))
(165)
Po
Po
From here, the proof followed as Appendix of ZZhoo al. (012 (in Proof of Theorem 3.1) which also borrows from Bickel & Chen (2009).
H Attributed SBM theory and results
We validate the robustness and sensitivity of proposed methods variance in the node features and graph structure. We also generating features using multivariate mixture generative model such that the node
33

---

Published in Transactions on Machine Learning Research (06/2025)
features of each block are sampled from normal distributions where the centers of clusters vertices of hypercube.
SBM. The Stochastic Block Model (SBM) Nowicki & Suijders 2001 is a generative model for graphs that incorporates probabilistic relationships between nodes based on their community assignments. In the basic SBM, a network with p nodes is divided into & communities or blocks denoted by C,, where i= 1,2, ,.. The SBM defines symmetric block probability matrix / with size (k k), where each entry B,j represents the probability of an edge between node in community C. and node in community Cj. Diagonal entries of this matrix represents the probabilities of intra-cluster edges. This matrix B captures the intra- and inter-community connections and is assumed to be constant. P(i + j|C; = a, C; = b) = Bub denotes the probability of an edge existing between nodes i and j when node i belongs to community a and node j belongs to community Using these probabilities, the SBM generates a network by independently sampling the presence or absence of an edge for each pair nodes basod on their community assignments and the block probability matrix B.
Degree Corrected SBM. DC-SBM(Karee & Newman, 2011 takes extra set of parameters 0 controlling the expected degree of vertex i. Now, the probability of edge between two nodes (using the same notation as above) becomes , This was introduced to handle the heterogeneity of real-world graphs. We selected this widely used and studied model for our analysis primarily because it considers a degree parameter for all nodes, resembling a key characteristic of real-world graphs. Therefore, the DC-SBM is closer to real-world graphs than the simpler SBM while still being analyzable, making it relevant here.
ADC-SBM Generation. We make of the graph_tool library to generate the DC-SBM adjacency matrix, with 1000, k 4. To generate the B matrix, follow the procedure in (Titssulin et al. 2023 by taking expected degree for each node d = 20 and expected sub-degree dans 2. This gives us B as:
18
2
2
2
18
2
2
2
18
2
2
2
2
18
Also, is generated by sampling a power-law distribution with exponent a = 2. We constrain the generated vector to dmiin = 2 and dmaz
To generate features, we use the make_ make_ classification function in the sklearn library. We generate a 128-dimensional feature vector for each node, with redundant channels. These belong to ky groups, where ky might not be equal to k. We test three scenarios: a) matched clusters (ky k) b) nested features (ky k) c) grouped features (ky < k) visualized in Figure 5] Note that for better visualization, class_sep was increased to (however, the results are given with value of 1, which is harder problem).
Adjacency
703
200
200
200
Wode Index
Node Index
600
100
Node
Figure (5a): Adjacency Ma- Figure (5b): Feature Covari- Figure (5c): Feature Covari- Figure (5d): Feature Covari-
trix
ance
ance Matrix ky &
ance Matrix ky k
Matrix
ky
Figure 5: Visualization of the generated adjacency and feature covariance matrices for the ADC-SBM
34

---

Published in Transactions on Machine Learning Research (06/2025)
Additionally, also consider both cases, with and without the coarsening constraint term.
Results. Our objective is able to completely recover the ground truth labels (NMI/ARI/ACC = 1) under all the specified conditions.
VGAE
In a VGAE, the encoder learns mean (μ) and variance (o): (X,, A)andlog = GCN, (X, A) By using the reparamcterization trick, get the distribution of the latent space (Z| A) -==11 (2, Ih N (zilu, diag(a?)) common choice for decoder is inner Lnner-product of the latent space with itself which giving us the reconstructed A. p(ÁlZ) 1P I1 ((Aggzz, zg), with p(Ag 1 2j) sigmoid(=? 23)
J Dataset Summaries and Metrics
Refer to Table for the dataset summary. We use datasets directly from the pytorch_ _geometriccccco pack- age, 80 no preprocessing is needed.
Name
([Vl)
((X+))
([EI)
(3)
Cora
2708
1433
5278
7
Metrics, pair of nodes are said to agree- ment they belong the same class and are as- signed to the same cluster, or they belong to differ- ent classes and have been assigned different clusters. For a particular partitioning, ARI is the fraction of agreeable nodes in the graph. Accuracy is ob- tained by performing a maximum weight bipartite matching between clusters and labels. NMI mea- sures the normalized similarity between the clus- and the labels, and is robust class imbal- ances. Mutual Information between two labellings X and Y of the same data is defined as MI(X, Y) ! |Y| |x,nk log N|X,nYi and is scaled be- [Xi]XX]
CiteSeer
3327
3703
4614
6
PubMed
19717
500
44325
3
Coauthor CS
18333
6805
163788
15
Coauthor Physics
34493
8415
495924
5
Amazon Photo
7650
745
238162
8
Amazon PC
13752
767
491722
10
ogbn-arxiv
169343
128
1166243
40
Brazil
1074
Europe
399
0
5995
USA
1190
0
13599
4
==1 N tween 0 to 1.
Table 5: Datasets summary.
Hyperparameters
K.1 Hyperparameter Tuning
We performed hyperparameter tuning using the comet optimizer library. A mixture of grid search and Bayesian search was used for the various hyperparameters. These were the broad ranges searched for each hyperparameter:
Learning Rate: [0.001, 0.1]
A: [0, 100)
a: [500, 10000]
Arecon: [10, 250]
8: [10, 250]
[100, 1000]
Awi [0.001, 0.1]
K.2 Sensitivity study
We also conducted small hyperparameter sensitivity study, the resutls of which presented in Table 6
35

---

Published in Transactions on Machine Learning Research (06/2025)
(k Coarsening Constraint
Coarsened Connectedness
8 Modularity
NMT
5000
1000
100
58.6
5000
100
100
57.1
5000
100
10
57.4
1000
1000
100
53.5
1000
100
100
52.7
1000
100
10
52.5
10000
100
10
53.5
10000
1000
100
54.7
Table 6: Hyperparameter sensitivity ablation study
L
Training Details
All experiments were run on an NVIDIA A100 GPU and Intel Xeon 2680 CPUs. We are usually running 4-16 experiments together to utilize resources (for example, in 40GB GPU memory, can run 8 experiments on PubMed simultaneously). Again, the memory costs are more than dominated by the dataset. All experiments used the same environment running CentOS 7, Python 3.9.12, PyTorch 2.0, PyTorch Geometric 2.2.0.
M Results on very large datasets
The results are presented in Table 7
CouthouCS
CauilooPPiiios
AmsosaPlulo
AmsunPC
aple-ansii
Methad
ACC
NMI
70.1
61.55
36.5
8.5
9.1
Q-MAGC (Ours)
70.2
76.4
000.2
75.8
07.22
196.1
70.4
66.6
68.0
62.4
61
31.1
35.8
24.4
15.6
Q-GUN (Ours)
65.4
73.6
70.7
55.2
72
81.0
662.3
57.6
45.3
06.7
42.4
25.8
34.4
27.1
19.7
Q D-VGAE (Ours)
70.9
81.6
62.3
301.4
24.7
Q-GMM (Ours)
72.5
61.6
57.5
25.0
12.7
Table 7: Comparison of methods on large attributed datasets.
N Evolution of different loss terms throughout training
Each separate series has been normalized by its absolute maximum value to see convergence behavior on the same graph casily. Every series decrrasing/conveeggee Thus, we can be assured that no terms are counteracting and hurting the performance. The legend is provided in the graph itself. This plot Figure is on the Cora dataset.
(except gamma, which remains almost constant).
Visualization of evolution of latent space
Refer to Figure and Figure
We see the clusters forming in the latent space of the VGAEs. In the case of Q-VGAE, since GCN is used on this space, it can learn non-lincarities and the latent space shows different structures (like starfish in CiteSeer). Moreoever, these structures have their geometric centres at the origin and grow out from there. In contrast, for Q-GMM-VGAA be normally distributed in their independent clustors, all of which have different means and comparable standard deviations. So, we see multiple 'blobs", which more or less follow a normal distribution. This plot effectively shows why GMM-VGAF, is more expressive than VGAF.
since a GMM being learnt over the latent space, the samples are encouraged
36

---

Published in Transactions on Machine Learning Research (06/2025)
Individual evolution of loss terms
1.5
variable
X_tAT theta_c X_t
alpha
AbsMax-Normalize Value
gamma
lambda
0.5
beta
0
-0.5
-1
-1.5
50
100
150
200
250
300
350
Epochs
Figure 6: Evolution of the different loss terms throughout training, denoted by their weight paramcters. Also the term x_t theta_C X_t term is the smoothness term (XX
P Explanation on why VAE manifolds are curved
Embedded manifolds obtained from VGAEs are curved and must be flattened before any clustering algorithms using Euclidean distance are applied.
The latent space of a VAE is not constrainod to be Euclidean. Connor al. (2021) point out that the variational posterior is selected to be multivariate Gaussian, and that the prior modeled zero-mean isotropic normal distribution which encourages grouping of latent points around the origin. Works such as (Chen et al. 2020 Bogdanov & Shchur 2021 Arvanitidis et al. 2018 make the VAE latent space to be Euclidean/ Haae//yypere typerbolicc Rieiianiinnnnnnn, and show good visuals. Moreover, it can be observed in our own work Fiiuuee 4a and Appendix Figure 7b) that the latent manifolds are curved and so, are not suitable for conventional methods such as k-means clustering, which need Euclidean distance.
37

---

Published in Transactions on Machine Learning Research (06/2025)
Q-VGAE
Time
Q-GMM -VGAE
CiteSeer
miro
a) Q-VGAE
Time
b) Q GMM -VGAE
PubMed
Q-VGAE
Time
b) Q-GMM -VGAE
Brazil
Q-VGAE
Time
Q-GMM VGAD
tu
Europe
miro
Figure 7: Plots of evolution of latent space for Q-VGAR and Q-GMM-VGAE methods for CiteSeer, PubMed,
Brazil (Air Traffic) and Europe (Air Traffic) datasets.
38


Reviews:
[{"review_id": "2sWdslhmmr", "reviewer": "Reviewer_mKbj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths and Contributions]\n- The paper provides theoretical soundness and convergence guarantee of the proposed optimization framework: Karush-Kuhn-Tucker(KKT) optimality, theoretical convergence of the proposed algorithm. \n- The authors establish strong and weak consistency under DC-SBM, ensuring that the method asymptotically recovers the true cluster labels.\n- The method is extensively tested on benchmark datasets (Cora, CiteSeer, PubMed), as well as larger real-world datasets. And the results highlight the method’s superiority over both GNN-free methods and GNN-based architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This paper presents an optimization-based framework for attributed graph clustering that integrates graph coarsening with modularity maximization. Traditional methods, such as cut-based, similarity-based, and modularity-based approaches, often face challenges in accurately capturing community structures, handling computational complexity, and detecting smaller communities.\n\n- To address these limitations, this work introduces the Q-MAGC loss function, which combines modularity maximization, graph smoothness, and log-determinant regularization. This formulation enhances clustering performance and guarantees asymptotically error-free clustering under the Degree-Corrected Stochastic Block Model (DC-SBM).\n\n- The proposed approach is modeled as a multi-block non-convex optimization problem and is solved using the Block Majorization-Minimization technique.\n\n- The method is implemented in GNNs and VGAEs, introducing three models—Q-GCN, Q-VGAE, and Q-GMM-VGAE—which demonstrate state-of-the-art performance on benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[Limitations requiring Revision]\n\n<Major Concerns>\n\n(1) The paper reads more like a Ph.D. thesis rather than a journal article. The attempt to cover too many aspects makes it difficult to read smoothly, and it is challenging to follow through to the end. A better approach might be to feature the core findings in this paper and consider splitting other aspects, such as convergence analysis and consistency analysis, into a sequel paper.\n\n(2) The proposed optimization framework is quite similar to Kumar's (2023, JMLR), except for the addition of the modularity term \\( tr(C^TBC) \\) in the objective function—Eq. (5). By incorporating this term, the problem is no longer convex, leading the authors to propose an optimization approach using MM. Therefore, the distinction from Featured Graph Coarsening (FGC) in Kumar’s work should be clearly highlighted. Additionally, comparative studies should be conducted more thoroughly, rather than treating FGC as merely one of the comparative methods in the current experimental setup.\n\n(3) Particularly, the ablation study for each term in the loss function needs to be emphasized more clearly, rather than being placed in the Appendix as in the current paper. Additionally, the legends in Figure 7 are difficult to recognize. Please improve their readability and check the font size of other figures to ensure clarity.\n            \n(4) The related works presented in the Introduction and Section 2: Related Works are somewhat confusing. Narrow the scope, present them in a more integrated manner, and explicitly explain their relevance to the proposed method.\n            \n(5) In the paragraph below Eq.(4), the coarsening objective \\( f \\) is described as preserving inter-connectivity, while in Eq.(5), \\( h \\) is stated to maintain inter-connectivity. This is confusing. Simply put, in the coarsened graph, \\( f \\) should be responsible for maintaining the smoothness of node features, while \\( h \\) should preserve inter-connectivity. However, why does increasing \\( -\\log \\det (C^\\top \\Theta C + J) \\) lead to such effects? Please provide a more detailed explanation.\n    \n(6) To show the \\(f(C)\\) in Eq.(6) is `L-Lipschitz continuous gradient function', each term of which is proved as a `L-Lipschitz continuous' in Appendix B. However, Lipschitz continuity does not necessarily means Lipschitz-Continuous Gradient of \\(f(C)\\). So the more explanation is needed.\n\n(7) It is difficult to follow the transition to Eq(8). How is Eq.(8) formulated as a majorized problem of Eq.(5)? Since one of the main contributions of the proposed method is the majorization of the objective function, a more detailed explanation of the procedure should be provided.\n             \n(8) In Appendix B, Equation (62) defines the optimal solution satisfying the KKT conditions as:\n            \\[ C = \\frac{(A)^+}{\\sum_i ||[A^T]_i||_2} \\].\n            However, \\( A \\), as defined below Equation (55), is given by:\n            \\[ A = \\left( C - \\frac{1}{L} \\nabla f(C) \\right)^+\\]\n            which is a recursive formulation. How can this be solved?\n             \n(9) Moving the Lagrangian equation (Eq. 55) from Appendix B to the main manuscript will enhance the readability of the proposed method.\n    \n(10) The section on consistency analysis with DC-SBM takes up too much space. It would be better to shorten this part, similar to how convergence analysis and complexity analysis are presented.\n       \n(11) Hyperparameter tuning and data preprocessing details are not sufficiently discussed, making replication and comparison more difficult.\n      \n(12) Important figures and tables for key experiments are placed in the appendix. Switching the proofs to Appendix and moving the experimental setup and results to the main text would provide better accessibility for a wider range of readers.\n    \n(13) The authors acknowledge that the proposed approach relies heavily on modularity.  In datasets where modularity is naturally low (e.g., the Airports dataset), the performance advantage over other methods diminishes.  This raises concerns about the generalizability of the method to graphs with weakly modular structures.\n            \n(14)  Please revise the reference list to follow a standard format, either chronological or alphabetical, to improve clarity. Currently, it is difficult to locate specific citations within the list.\n    \n(15) Magnify the font size of markers and legends in Figure 2 for better readability. Additionally, Figure 2(a) is presented as a figure, but it is actually a table.  The misuse of object types due to space constraints should be avoided. A similar issue is found in Figure 3, which should also be corrected. Ensure that figures and tables are appropriately categorized to maintain clarity and accuracy in presentation.\n            \n(16) Align the appendix sections to match their order of appearance in the main manuscript.\n\n\n<Minors>\n\n(17) On page 2, when Q-MAGC first appears, write out its full name and provide appropriate references.\n\n(18) On page 3, provide appropriate references for block maorization-minimization (Block MM) techniques.\n\n(19) Provide the full name for DC-SBM when it first appears.\n\n(20) On page 5, when Q-MAGC first appears, write out its full name to ensure clarity for readers encountering it for the first time\n\n(21) Eq. (5),(6)  Typo: \\(C \\in R^{p \\times l}\\) \\( l \\) is not correct.\n\n(22) In Appendix A, Equation (29), add a `+' sign before the last term.\n\n(23) In Appendix A, Equation (31), replace \\( V \\) with \\( U \\).\n\n(24) It is recommended that the Lipschitz constants \\( L_1, L_2, L_3, L_4 \\) be assigned in the order in which they appear in either equation (5) or (6).", "broader_impact_concerns": "There are no significant ethical concerns in this work, as it focuses on methodological advancements in graph clustering without involving sensitive data, privacy issues, or societal harm", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IOSDRhu6wT", "reviewer": "Reviewer_33er", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper proposed new graph clustering methods to combine graph coarsening and spectral modularity maximization, showed the theoretical background of the proposed method. Furthermore, the authors demonstrated the potential to improve performance by integrating their proposed method with various deep learning-based approaches.\nHowever, there is no discussion on what the theoretical background means and how it can be utilized. Additionally, it might be better to reorganize the overall structure, and it seems that the results section does not adequately show the superiority of the proposed method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a graph clustering method which combined graph coarsening and spectral modularity maximization. The authors showed the theoretical background of the proposed method including KKT optimality, convergence analysis, and consistency analysis on degree corrected stochastic block models (DC-SBM). The proposed method could be integrated with graph neural network (GNN), graph convolutional network (GCN), variational graph auto-encoders (VGAE), and Gaussian Mixture Model VGAE (GMM-VGAE). In the experimental results, the proposed method was applied to real-world datasets such as Cora, CiteSeer, PubMed, and Airports (Brazil, Europe, and USA) for attributed or non-attributed graph clustering.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The authors wrote that both graph coarsening and modularity maximization lacked theoretical convergence guarantees in p. 4. The proposed method seems to simply combine graph coarsening method and modularity maximization method - how did it achieve convergence? \n2) What improvements can we expect from being consistent on DC-SBM? \n3) It might be better to omit the section 3 background. The undefined terminologies in equations (1) and (2) adds to the confusion, and it would be easier to understand if equation (4) is explained alongside equation (5).\n4) The consistency analysis on DC-SBM in the section 4 takes up too much space in the paper. It would be better to move this part to the appendix and mention the meaning and advantages of consistency analysis. \n5) It would be helpful to include the following items in the results section. \n- The explanations for the figures and tables were lacking. \n- It would be better to provide more details about the dataset in the results section. \n- Where can we find the results for the very large datasets, CoauthorCS/Physics, AmazonPhoto/PC, and ogbn-arxiv?\n- The authors proposed 4 new methods, Q-MAGC, Q-GCN, Q-VGAE, and Q-GMM-VGAE in Table 1. So, it is difficult to find which one is superior. It would be better to demonstrate the results and comparisons to indicate when and how to use the 4 different proposed methods in the results section.\n- Figures 2 and 3 are too small, making it difficult to read the text.   \n- The most important aspect of this paper seems to be demonstrating that combining the graph coarsening term and the modularity maximization term in equation (5) improved performance without significantly affecting the running time. However, this is only briefly mentioned in the results section and refers the reader to the appendix. Additionally, it's unclear what the figures in the appendix are showing.\n- Figure 4 showed the latent spaces of Q-VGAE and Q-GMM-VGAE. What did they mean?", "broader_impact_concerns": "There is no related concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eTbNoE33L8", "reviewer": "Reviewer_BtxT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nS1 - The paper presents a method that tackles a real-world and relevant problem. \n\nS2 - The numerical results validate the utility of the proposed method. \n\nS3 - The authors show theoretical results which provides evidence of why their method works.\n\nWeaknesses\nW1 - The paper is not well written. There are plenty of grammar mistakes, even in the appendix. Besides, the paper does not present the topics in order. For example, it mentions Q-MAGC before defining it. This forces the reader to go back and forth. \n\nW2 - The concepts are not well presented. For example, in the Proposed method section, g(C,A), does not use A, but it uses B. It is unclear if it should use A, or B, and even who is B? Same with h(C,\\Theta), which uses J, who is J? The authors should be more careful about the math presentation. \n\nW3 - There seems to be a mismatch between theory and experiments. The theory works under certain assumptions over the matrices, which do not hold once the GNNs and VGAEs are introduced. Besides, the authors say things such as “using a “soft” and “hard” version of C”. The authors should mathematically define what they mean by this. \n\nW4 - The contribution of the paper seems to be the problem formulation. However, this is nothing but an addition to existing loss functions. That is to say, the authors simply put three loss functions together, and claim things about it. This is problematic in my opinion for several reasons. In terms of novelty, the author's contribution is minor. Even more so, the authors simply put the three pieces together, without even showing why this makes sense from a magnitude standpoint. That is to say, why of the three terms govern the minimization? And by how much? The authors never show the loss per term in the appendix. When looking at Figure 7, it is clear that all losses converge very fast and to different values. I suggest the authors explore a better way of combining the terms. \n\nW5 - The authors should elaborate more on the DC-SBM definition. It seems to be a very simple model for graphs, can the authors explain why such a simplistic model is relevant in practice? Also, can the authors provide synthetic experiments showcasing their method on it?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel graph clustering method via integrating coarsening and modularity maximization. The method leverages adjacency and node features,  using a loss function that consists of 3 terms, one for smoothness, one for modularity, and a log-determinant term. The authors show consistency and asymptotic error-free solutions. The authors show how to adapt the method for GNNs and VGAEs. The authors present numerical results that validate the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Strengths and Weaknesses.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: First of all, I would like to thank the authors for their patience during the unusually long review process. 
For various reasons, it took a long time to find reviewers, as many invitees either did not respond or declined the invitation.
Finally, I am pleased to provide a positive feedback to you.
Decision: Accept (poster)