acceptodds
Under review as a conference paper at ICLR 2027

Soft Partition Markov Stability for Graph Clustering

Abstract

We propose soft partition Markov stability (SPMS), a novel, dynamics-based quality metric for graph clustering that offers greater interpretability than existing metrics. SPMS extends the ideas of traditional Markov stability to soft clusterings by describing the rate at which communities trap random walkers on the graph for a fixed time, while explicitly integrating information about cluster inhomogeneity. We argue that SPMS is a suitable objective function for graph clustering and analyze how the spectrum of the underlying graph influences its behavior. In our algorithmic framework, we describe a clustering with a set of localized probability distributions, which we call a soft partition, and maximize SPMS over the space of soft partitions to obtain a nuanced description of the community structure. The optimal soft partition yields information about intra-cluster degree inhomogeneity and naturally identifies ambiguous nodes, which may intuitively belong to multiple clusters or none at all. We describe an efficient method to optimize SPMS and demonstrate its empirical success on model graphs and large, real-world datasets. Finally, we propose and test a downstream algorithm for identifying core-periphery substructure within clusters.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Spectral Clustering, Markov Stability, Core-Periphery Structure

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_VCn6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a new quality function for soft clustering based on Markov Stability (MS). Spectral clustering algorithms are used for optimising the new quality function and applications on synthetic and real-world data show that the method can capture core-periphery structure.

Critical strengths
  • The paper deals with the important problem of extending the MS framework to soft clustering.
Critical weaknesses
  • The paper fails to demonstrate that existing variants of Markov Stability are not suitable for the clustering tasks considered. Similarly, lines 46 to 53 are not backed up by experiments or references.
  • The paper does not engage sufficiently with related literature. Note that the authors of MS have proposed a soft clustering method called Severability (Yu et al., 2020), which has been used for soft-clustering in semantic networks as part of the LGDE method and was shown to outperform other overlapping community detection methods (Schindler et al., 2025). As Severability is the closest to an extension of MS to soft clustering, the proposed method should be compared to it theoretically/numerically. In my opinion, the advantage of Severability over the proposed method is that the former is a fully local approach to community detection and has theoretical guarantees in terms of local time scale separation.
  • The intuition behind the proposed quality function is not well explained. Please motivate your core definition 2.2. Why did you change the null model? What are the important differences to MS? Compare this also to the quality function proposed in the Severability paper.
  • How do you select the robust scales tt for the different clusters? Do you have global time scale separation, i.e., there is a scale tt for which all clusters are robust descriptions of the data, or local time scale separation as in Severability? Why is it sufficient to fix tt in the experiments?
  • Section 4 is not sufficiently motivated. Does this section propose a downstream task? The experiments suggest that measuring core-periphery structure is the key contribution of the proposed method. However, in the introduction you argue that extending MS to soft clustering is the contribution of your paper, and in that case your tasks should establish that your method is better than baselines on appropriate clustering tasks, see below.
  • The experimental validation is very limited (classification task on 150 SBM graphs with N=500 nodes each). It would be good to benchmark the proposed method against relevant baseline methods (Markov Stability, Severability, local Modularity etc.) on graphs with various structures and sizes using cluster comparison indices such as extensions of the Rand index for soft clustering, see Denœux et al. (2017).
Questions for authors
  • Can your method be applied to directed graphs?
  • Could your method be integrated in the PyGenStability framework (Arnaudon et al., 2024) for Markov Stability analysis?
2 comments

We thank the reviewer for their detailed feedback, which we will incorporate as we revise this manuscript. We address your questions below.

Q1 - On directed graphs

Yes. There are variants of Markov Stability for directed graphs. One could extend these variants to soft partitioning similarly to the undirected setting. We agree that this is a useful future consideration.

Q2 - On PyGenStability

PyGenStability uses the Louvain method for identifying optimal partitions, which is not amenable to our framework.

We once again thank the reviewer for their time and feedback.

Dear authors, thanks for your answers to my questions. Unfortunately, you have not responded to the critical weaknesses I flagged in my review. Without thorough engagement with my review I cannot raise my scores.

Reviewer_RzZrOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This article introduces ‘soft partition Markov stability’ (SPMS), which generalises classical Markov stability to soft clustering of graphs. Communities are represented by probability distributions on the vertices, obtained through a parameterisation of the eigenspace of the normalised Laplacian and the optimisation of an objective function based on the random walk. The authors argue that the representation thus obtained captures the heterogeneous structure of communities and makes it possible to distinguish between vertices with overlapping memberships and those with weak affiliations. They also propose a downstream algorithm for detecting the core and the periphery. The approach is evaluated on synthetic graph models and several real-world road networks, with an additional theoretical analysis linking the stability objective to Markov chain mixing.

Critical strengths

This article draws an insightful parallel between the dynamics of random walks and flexible representations of communities. Modelling communities as probability distributions offers a convenient way of studying variations in membership strength and, possibly, of identifying different forms of node ambiguity.

Spectral parameterisation offers a practical means of constructing column-normalised, validated distributions, and the authors investigate the properties of the resulting stability objective. The connection to classical spectral clustering and Markov chain mixtures provides the proposed method with a sound mathematical foundation.

Critical weaknesses

1. Insufficiently established scientific or methodological contribution.

I do not see the incremental nature of the proposed approach per se as a problem; extending an established framework can be scientifically valuable if it yields new theoretical insights or meaningful methodological advances, but I find neither contribution sufficiently established here.

In terms of theoretical contribution, the results mostly link the proposed objective to established properties of spectral graph theory and Markov-chain mixing, but do not significantly advance our understanding of community structure or establish recovery properties of the proposed optimization.

Moreover, the parameterization in Section 3.1,

P=(VkQ)⊙2,Q∈SO(k),P=(V_kQ)^{\odot 2}, \qquad Q\in SO(k),

implies that

=\sum_{a=1}^{k}(V_kQ)_{ia}^{2} =|V_k(i,:)|_2^2.$$ Thus, the total membership mass assigned to each vertex is entirely determined by the initial embedding and independent of the optimization parameter $Q$; this seems particularly pertinent given that distinguishing strongly overlapping vertices from weakly affiliated vertices is one of the central motivations of the paper. Furthermore, Appendix E.7 suggests that the CPQR initialization is already largely optimal, but the paper fails to quantify the improvement of SPMS optimization on downstream clustering performance. Overall, the work fails to establish what additional theoretical understanding or methodological capability is gained from their approach compared to existing spectral clustering methods. **2. Insufficient experimental validation of the claimed advantages.** The experimental evaluation does not convincingly show that the approach provides significant advantages over existing methods. First, the experiments use simple stochastic block models and Gaussian random geometric graphs. The few additional experiments on real-world road networks are mostly qualitative and do not provide quantitative comparisons with existing community recovery approaches. The compared methods are also not comprehensive given the state-of-the-art techniques for soft and overlapping community detection. The manuscript does not mention existing variants of BigCLAM and OSLOM, and the usual benchmarks of overlapping communities are not used. In particular, the experiment in Section 5.2 uses different connection probabilities for strongly and weakly connected ambiguous vertices, resulting in vastly differing expected degrees. Without controls for degree or spectral-leverage-score, the results do not isolate the effect of SPMS from the spectral or graph information that may be encoded differently in the input. Finally, the application to core-periphery detection is not compelling given the main contribution of clustering. The evaluation does not show that it provides significantly more insights than simpler approaches based on vertex degree, centrality, or spectral ranking. As a result, the experiments are not convincing in showing that the proposed approach enables more informative community representations or clustering than existing approaches.
Questions for authors
  1. Contribution of optimisation: Appendix E.7 indicates that the CPQR initialisation is already close to the optimised solution. Could the authors evaluate the improvement due to the optimisation procedure in terms of the same clustering and ambiguity detection metrics employed in the experiments?

  2. Role of spectral immersion: Since ∑aPia=∣Vk(i,:)∣22\sum_a P_{ia}=|V_k(i,:)|_2^2 is independent of QQ, to what extent is the ability to distinguish between strongly overlapping vertices and weakly affiliated ones due to SPMS optimisation rather than the use of spectral lever scores? In other words, what accuracy would a naive classifier based on degree or spectral lever achieve in the task described in Section 5.2?

  3. Empirical significance: Could the authors comment on the empirical significance of their improvements over the existing approaches to overlapping community detection? In particular, could they report results on real-world networks other than the road graph beyond the toy example in Section 5.1 and quantitative comparisons with kernel-based methods of community detection? In other words, do the benefits of SPMS hold beyond the specific choice of the network and substantially better than the alternatives in terms of standard benchmark metrics?

2 comments

We thank the reviewer for their detailed feedback, which we will incorporate as we revise this manuscript. We address your questions below.

Q1 - On optimization

CPQR-based spectral clustering initializes SPMS close to the proposed solution and greatly facilitates convergence. Appendix E.7 also shows that this initialization is not strictly necessary, with random initializations converging to the same solution. The tunable cluster resolution of SPMS through the tt parameter constitutes the advantage of our method over using CPQR alone. We agree that a test that directly compares SPMS with its initialization would be a valuable improvement of this work.

Q2 - On the role of the spectral immersion

We agree that a naive classifier based on node degree would easily separate the weak and strong blocks in Section 5.2. The purpose of Section 5.2 was to show that column normalization makes our method flexible enough to distinguish the planted blocks, based solely on the returned clustering information. This property was not observed for row-normalized methods. We agree that a comparison with other column-normalized spectral methods on this same task would be useful to identify the advantage of our method that arises specifically from the metric.

Q3 - On benchmarks and comparisons

We agree that our manuscript would benefit from more comparisons with competing clustering algorithms and evaluations on standard datasets. In our testing, we observed that SPMS achieves exact recovery on stochastic block models and performs well on classic networks with ground-truth community structure. Since our work is focused on soft partitioning, these tests were omitted from the final draft. As we revise our work, we will include thorough experiments addressing these points. Finally, we agree that SPMS ought to be compared to additional soft clustering baselines. We appreciate the suggestion of a quantitative comparison with kernel-based methods.

We once again thank the reviewer for their time and feedback.

Thanks to the authors for addressing my questions. While the response clarifies several points, my overall evaluation stands and I will retain my current rating.

Reviewer_wFvBOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

An extension of Markov Stability is introduced that obtains a soft partition (rather than a partition) where every cluster is represented by a probability distribution over the vertices. The authors define the clustering objective and optimize this using gradient descent. The advantage of this soft partition representation is that a vertex can be (partly) member of multiple clusters, or none at all. The common approach for soft partitioning is to obtain a label distribution for each verte, which does not allow for a vertex to not be part of any clusters.

Critical strengths

The idea to make the columns of P sum up to 1 rather than its rows (as done in most other soft partitioning methods) is interesting and allows for 'outlier' vertices that are not part of any community.

I can see that the bulk of the text was written by the authors with minimal LLM use, which I appreciate in this day and age. Overall, the paper is pleasant to read.

Critical weaknesses

The proposed method does not quite generalize MS. There is no way to choose P (or any other parameters) such that SPMS coincides with MS.

One of the main advantages of Markov Stability is that one does not have to specify the number of clusters kk, but that this will be determined during optimization. Your soft version does not have this advantage. The resolution proposed in lines 756-757 (optimizing MS to determine kk) is extremely ad-hoc. In particular since SPMS does not generalize MS.

As Remark 4 already explains, the probabilistic interpretation fails when a row sum of PP exceeds 1. Moreover, the optimization problem presented in (7) does not seem to enforce distinctness of the clusters. If we take the column that optimizes for k=1k=1, then it seems that for any k>1k>1, the optimal PP would just be that same column repeated k times. If we would add the constraint that rows of PP may not exceed 11, then the first problem is solved, while the second problem may also be alleviated. The resulting problem is a (nonconvex) quadratic program, and I would assume that there are better (more specialized) methods available for its optimization than gradient descent.

On that same note, the distinctness appears to just be enforced by the implementation of the optimization algorithm with the eigenvectors and not the optimization problem as defined in (7). I'm not sure if the eigenvector-trick with squaring has the desired effect in terms of distinctness: take for example the vectors (−1,1)/2(-1,1)/\sqrt{2} and (1,1)/2(1,1)/\sqrt{2}, which both equal (1,1)/2(1,1)/2 after squaring. Finally, the notation SO(k)SO(k) is not introduced anywhere. In Appendix C, the name "special orthogonal group" is used, but it is not explained what this is.

Questions for authors

QR and CPQR are referenced but not explained (nor is it explained what these acronyms mean). What do they mean and why do you use them for your initialization?

What is SO(k)SO(k)? Why do we use it?

Remark 1 says that "we often see that Tr[S(t,H)]\text{Tr}[S(t,H)] is monotonically increasing in tt". Do you mean "eventually monotonically increasing"? This seems like a rather casual way of introducing this structural property.

On this same note, instead of taking the minimum over 0≤τ≤t0\le\tau\le t, can't we just assume the graph is connected and not bipartite (or aperiodic?) or whatever is needed so that we can just minimize for tt instead of introducing this minimum.

Comparing (1) to (3), explain why you replace the product of π\pi's with π\pi repeated nn times. Also, do we really need a Kronecker product here? Is this not just 1πT1\pi^T?

Why do you use gradient descent? It appears that your problem has structure that would allow for more specialized optimization algorithms. It seems like you already make strong assumptions on the initialization, so why not assume that it is initialized in some convex region around the global minimum? Then the optimization problem defined in Defs 2.1-2.3 could be solved as a convex quadratic program in PP. Although I think you would encounter the problem that these definitions don't enforce distinctness, so that your optimum would be the same cluster repeated kk times.

2 comments

We thank the reviewer for their detailed feedback, which we will incorporate as we revise this manuscript. We address your questions below.

Q1 - On CPQR

CPQR stands for "Column-Pivoted QR factorization." For k≤nk\leq n, CPQR factors a full-rank matrix B∈Rn×kB\in\mathbb{R}^{n\times k}, up to right multiplication by a permutation matrix, as Q[R1 R2]Q[R_1\text{ }R_2] where QQ is orthogonal and R1∈Rk×kR_1\in\mathbb{R}^{k\times k} upper-triangular. It is shown in the associated reference that one may use CPQR factorizations to build an efficient spectral clustering algorithm. Since our method already requires computation of the eigenspace and the CPQR spectral clustering is efficient, this was a natural choice of initialization.

Q2 - On SO(k)

SO(k) refers to the special orthogonal group. It is the group formed by orthogonal matrices with determinant 1 under matrix multiplication. Such matrices describe rotations in Euclidean space. It is established in the literature that rotations of the dominant eigenspace yield good clustering.

Q3 - On the monotonicity of Tr[S(t,H)]Tr[S(t,H)]

We claim that it is often the case that Tr[S(t,H)]Tr[S(t,H)] is monotonically decreasing in tt. This claim is justified by our numerical testing. Intuitively, as a random walk is free to take more steps, the probability of remaining its starting cluster decreases. It is unclear if explicit conditions can be imposed on the graph to alleviate the need for the minimum. As a modeling consideration, the minimum is taken solely to ensure our metric makes sense for a wide class of graphs.

Q4 - On eq. (3)

This change was made to obtain the probabilistic interpretation given in the appendix. You are correct - the expression with the Kronecker product is the same as 1πT1\pi^T.

Q5 - On gradient descent

We have not encountered any issues with gradient descent in our testing. We agree that further consideration into specialized optimization methods may be useful.

We once again thank the reviewer for their time and feedback.

I thank the authors for their response. I will keep my rating.

Reviewer_NwkMOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper focuses on the graph clustering/partition tasks. They propose one metric based on the Markov stability for measuring the decomposition property of the given graph. This is a paper that focuses more on the theoretical side which proves many convergence theorems for showing the guarantees of their metric and proposed algorithm. They also utilize some experiments to show their metric is actually working for this task.

Critical strengths
  1. The definition of the task is clear. Easy to follow for readers to know what the task is.

  2. Many theorems are proved for showing the theoretical guarantees of their proposed algorithm. Making their proposed framework solid.

Critical weaknesses

The graph parition/clustering is not a new task in the research area. Actually, there are many papers/references the authors may miss. For instance, the paper Ju, Wei, et al. "Compactness and consistency: A conjoint framework for deep graph clustering." (ICLR) 2026 and the paper Tan, Yuze, et al. "Sample-level multi-view graph clustering." (CVPR) 2023 both focus on the graph clustering paper. In their papers, the experiments include some real-world datasets to show their graph clustering frameworks' effectiveness. As far as I read from your paper, the main experiments included in this paper cares about the random geometric graphs and roadmap datas, however, many baselines on graph clustering paper also run their experiments on human face, digit number datasets. As a result of this, current experiments' contents make the whole framework and story less solid and convincing.

Questions for authors
  1. Can you discuss your framework with the relevant literatures in the graph clustering/partition area? I think there are many papers in this research direction, and the the authors missed a lot of these works. A more thorough discussion of relevant works are suggested for a more complete research work.

  2. Your experiments mainly sit in the synthetic datasets and some less well-known real-world datasets like OpenStreetMap, can you also run some extra experiments on the real-world datsets like [1,2] to further show your model/metric's effectiveness and give some analysis?

[1] Ju, Wei, et al. "Compactness and consistency: A conjoint framework for deep graph clustering." (ICLR) 2026

[2] Tan, Yuze, et al. "Sample-level multi-view graph clustering." (CVPR) 2023

2 comments

We thank the reviewer for their detailed feedback, which we will incorporate as we revise this manuscript. We address your questions below.

Q1 - On related work

We positioned our work around existing dynamics-based clustering methods. We agree that our manuscript would benefit from a more thorough literature review, focusing on modern graph clustering methods.

Q2 - On real-world data

We agree that our work would benefit from additional tests on more standard real-world datasets. We will consider the provided references as we improve this manuscript.

We once again thank the reviewer for their time and feedback.

Currently, no added experiments for highly relevant baselines. I keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.