acceptodds
Under review as a conference paper at ICLR 2027

What Soft Clustering Objectives Compute, When They Are Tight, and What Softness Buys: The Case of Soft Structural Entropy

Abstract

Differentiable relaxations of discrete clustering objectives are standard in graph learning: DMoN, MinCutPool, Neuromap and structural-entropy (SE) methods (LSEnet, DeSE) relax modularity, normalized cut, the map equation and SE by substituting soft volumes and internal weights into the discrete formula. The resulting bilinear plug-in is read as the discrete objective. We ask what it computes, when it is tight and what the softness buys, with two-level SE as the running case. For a row-stochastic assignment we compare the plug-in , the multilinear extension under independent rounding, and a memoryless stochastic-encoder code length . All three agree at hard assignments, and exactly: the deployed objective is a bits-back net rate. The multilinear extension is an exact relaxation (its minimum is a vertex and equals the discrete minimum), whereas the plug-in is provably loose: at the uniform assignment it equals on every graph, so a strictly soft beats every partition whenever the discrete optimum lies above that floor, and local overlap makes it loose even when it does not (5-node bowtie: against bits). Beyond SE, the multilinear extension is exact for every partition objective; Neuromap's plug-in obeys the same bits-back identity but has no floor; pairwise objectives differ from their expectation by a degree-weighted Gini refund, which makes Markov stability at even times exactly tight and bounds modularity's looseness by . In an exhaustive census plug-ins deployed for SE, DMoN, MinCutPool and Dasgupta's cost beat every partition on 12, 14, 10 and 9 of 20 instances; the map equation's never did by more than bits. On the sparse graphs we tested the looseness does not bind: on Cora, CiteSeer and planted SBMs the plug-in optima are near-hard, the multilinear objective trained with its unbiased gradient finds no better partitions, and the soft-over-hard advantage of our encoder control largely vanishes against a Gumbel-softmax hard arm. Preregistered gates are reported verbatim, including the failures (a planted-overlap null control fails at 5 and at 20 seeds).

Primary area:
learning on graphs and other geometries & topologies
Keywords:
differentiable clustering, graph clustering, relaxation, bits-back coding, modularity, map equation, structural entropy

Reviews

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

The paper studies if differentiable relaxations of discrete graph-clustering objectives preserve their intended mathematical interpretation. It uses structural entropy as the primary example and differentiates three formulations: (1) The commonly used bilinear plug-in objective, (2) the multilinear extension that we get by independently sampling hard assignments, (3) proposed stochastic-encoder code length. Authors are able to derive relations between these objectives and also the exactness of the multilinear extension. By this, they show that the bilinear relaxation can achieve values strictly below every discrete partition.

The paper extends its analysis to several existing clustering objectives like modularity, normalized cut, the map equation, markov stability, and the Dasgupta’s cost. Authors conduct experiments on small graphs, overlapping-community fixtures, stochastic block models, Cora, and CiteSeer to investivate when exactly the theoretical looseness is observed in optimization. Authors also report the negative findings. They state that the multilinear formulation doesn’t consistently translate to better partitions, and some advantages of soft assignments disappear against stronger hard-assignment controls.

Critical strengths

1.⁠ ⁠Useful distinction between three soft objectives: The comparison between HbilH_{\mathrm{bil}}, HmulH_{\mathrm{mul}}, and HcodeH_{\mathrm{code}} exposes an ambiguity that is necessary to address, about how differentiable clustering losses are interpreted. Theorem 4’s uniform-assignment formulation is useful because it establishes looseness without being dependent on an optimizer or numerical approximation.

2.⁠ ⁠Convincing local-overlap counter-example: Example 2 is used to explain that looseness need not come up only from the uniform-assignment construction.

3.⁠ ⁠Extension beyond structural entropy adds value: Using relaxation behavior, proposition 1 connects several widely used clustering objectives. The modularity bound, exactness of even-time markov stability, and comparison with map equation help distinguish which phenomena are specific to SE and which are more general.

4.⁠ ⁠The transparency of authors in empirical reporting is appreciable. This significantly improves the credibility of the experimental conclusions.

Critical weaknesses

1.⁠ The module and within-module codewords, as claimed in definition 3, form valid prefix codes because the probabilities within each codebook sum to one. But this doesn’t show that the combined transition code is prefix-decodable: the decoder must differentiate between a within module transmission and a module-switch transmission, without an explicit exit symbol symbol or switch indicator. For example, take K6, partitioned into two modules of 3 vertices. Conditional on the current vertex, the proposed code lengths give a Kraft sum of 2/3 + 3/6 = 7/6 > 1 over possible next vertices. Interpreting HcodeH_{\mathrm{code}} as an operational code length, and HbilH_{\mathrm{bil}} as an achievable bits-back net rate, requires a more explicit coding protocol in Theorem 2.

2.⁠ ⁠The demonstrated practical relevance of looseness is limited. The strongest violations occur in small, exhaustively enumerated examples. On the other hand, plug-ins remain near-hard on Cora, CiteSeer, and the large planted SBMs. The real-graph controls use only a small fraction of the available modules on the other hand. Additionally, the original LSEnet and DeSE architectures are not directly evaluated. Although, authors acknowledge these limitations, these experiments prove that looseness can occur much more convincingly than they prove how often it affects deployed graph-learning methods.

3.⁠ In Appendix C, the proposed covariance decomposition of Hmul−HbilH_{\mathrm{mul}}-H_{\mathrm{bil}} uses E[log⁡Vk]\mathbb E[\log V_k]. A module can be sometimes empty, which makes this expectation undefined as a finite quantity. Thats why, the argument needs regularization or a different decomposition.

4.⁠ ⁠While Proposition 2 only states Hbil(S)−H2(z^)≤CH_{\mathrm{bil}}(S)-H_2(\hat z)\le C, which does not bound the harmful direction of underestimation, its proof sketch seems to support an absolute-value bound instead. These discrepancies must be addressed and justified in the rebuttal.

Questions for authors

1.⁠ ⁠Authors should specify a complete uniquely decodable stochastic coding protocol for definition 3, that includes how module changes are identified and how assignment entropy is recovered. It must be worth commenting if the theorem 2 still remain valid for the newer definition.

2.⁠ ⁠Moving ahead from the small census, can authors analyze and identify a real and practical graph-learning setting where the plug-in’s looseness actually changes a clustering decision, model selection, or interpretation compared with a suitable hard-partition control?

3.⁠ ⁠Can Appendix C covariance argument be modified to make it work in the cases where modules are empty.

1 comment
AuthorsOpenReview ↗

You are right about decodability and Appendix C (a complete protocol is below); Proposition 2 is two-sided as printed

Thank you for the careful review. You are right on three of your four points.

1. Decodability of Definition 3 (weakness 1, question 1). You are right. Each codebook is a prefix code, but the combined stream cannot be decoded, because nothing tells the decoder whether the module changed. "Valid prefix codes" is true of each codebook but not of the stream, and "operational expected code length" is wrong as written.

Your K6 example is a hard partition, where Definition 3 is the two-level SE of Equation (1) (Theorem 1); its cost, 2.185 bits, is the H2∗H_2^\ast printed for K6 in Corollary 2. So the Kraft sum of 7/6 is already present in the discrete SE formula, which charges the module codeword when the walk changes module and nothing for signaling the change; we carried that accounting into the soft case without saying so.

A complete protocol with ideal code lengths (not in the submitted paper):

  • Shared once, outside the per-step rate: the graph and SS, which fix every codebook, and the first node with its label.
  • The label drawn for a node when the walk arrives is kept as its label for the next step. The per-step joint distribution of nodes and labels is unchanged, so HcodeH_{\rm code} is unchanged, and the decoder always knows the current module kk.
  • Each step sends a stay/switch flag from a binary codebook for module kk (stay probability wk/Vkw_k/V_k), then the new module's codeword after a switch, then the next node's codeword from the book of its module.

Every codeword is read from a book the decoder already knows, so the stream is uniquely decodable. Its expected length is Hcode(S)+F(S)H_{\rm code}(S)+F(S), with F(S)=∑k(Vk/2m)h(wk/Vk)F(S)=\sum_k (V_k/2m) h(w_k/V_k) and hh the binary entropy. The assignment entropy is recovered as follows: the encoder picks each label by decoding random bits of another, already compressed message with the node's row SjS_j; once the decoder has node jj and its label, it re-encodes the label with SjS_j and gets those bits back, H(Sj)\mathcal H(S_j) on average. The net rate is Hbil(S)+F(S)H_{\rm bil}(S)+F(S). On K6 split 3/3 this is 2.185 + 0.971 = 3.156 bits, above the walk's entropy rate log⁡25≈2.322\log_2 5\approx 2.322, and the Kraft sum over the five neighbors is 17/30.

Does Theorem 2 remain valid? Yes. It is an algebraic identity between the quantities as defined, and its proof does not use decodability; with the flag, both sides gain the same F(S)F(S). What changes is the reading: Theorem 2 does not make HbilH_{\rm bil} the rate of a decodable code. HbilH_{\rm bil} is the complete code's net rate minus the flag cost, just as H2H_2 is at a hard partition. The stochastic map code of Proposition 1(c) already has exit codewords, but it too must keep labels across steps. Theorem 4, Corollary 2, Example 2 and the census counts of loose instances do not use Definition 3.

2. Practical relevance (weakness 2, question 2). We cannot name such a setting. On Cora and CiteSeer the optimized plug-in is nearly hard (softness at most 0.007 with the GCN) and within 0.01 bits of its own rounding; on planted graphs up to N = 1024 no plug-in beat the best hard partition found (0 of 36 cells; Section 5.3). LSEnet and DeSE were not trained, and the SE runs with the GCN used only 2 to 4 of the 6 or 7 modules (Limitations, item 4). Reviewer ft4Y also shows that Definition 1 is not LSEnet's or DeSE's published formula; we concede this in our reply there. The paper shows that the looseness exists (exact examples and a census of graphs with at most 9 nodes), not that it changes a decision in a deployed method, and it should say so as plainly as you do.

3. Appendix C and empty modules (weakness 3, question 3). You are right: E[log⁡2Vk]\mathbb E[\log_2 V_k] is −∞-\infty whenever module kk can be empty, so the decomposition is undefined as written. It can be repaired. Wk=0W_k=0 whenever module kk has zero volume, so on that event log⁡2Vk\log_2 V_k can be replaced by any finite constant ckc_k without changing E[Wklog⁡2Vk]\mathbb E[W_k\log_2 V_k]. For the given SS, let pp, strictly between 0 and 1, be the probability that Vk>0V_k>0, and dmin⁡d_{\min} the smallest positive degree. If ckc_k is at most log⁡2dmin⁡\log_2 d_{\min} and at most log⁡2E[Vk]+(p/(1−p))log⁡2p\log_2\mathbb E[V_k]+(p/(1-p))\log_2 p, the new function is still nondecreasing in the indicators, so the covariance is finite and nonnegative by Harris's inequality, and the second term stays nonpositive. That paragraph only explains why Conjecture 1 is hard; the conjecture is still unproved.

4. Proposition 2 (weakness 4). The proposition is printed with absolute-value bars, ∣Hbil(S)−H2(z^)∣≤…|H_{\rm bil}(S)-H_2(\hat z)|\le\dots (Appendix C.1, page 13), so it bounds both directions, including the underestimation, and the proof sketch proves that two-sided statement. The check listed in Table 2 as "rounding bound at the optima" tested the absolute difference. We should also have said in words that it bounds both directions.

We have not uploaded a revised PDF; the corrections are stated in this reply only.

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

The paper compares three soft extensions of structural entropy and studies relaxation gaps through theoretical examples, exhaustive small-graph experiments, and limited real-data tests.

Critical strengths

Explicit counterexamples clarify why a lower soft objective need not yield a better hard partition. Negative empirical findings are reported candidly.

Critical weaknesses

Definition 3 does not explain how the decoder detects module switches. For the complete graph K8 split into two groups of four, the prescribed cost is 18/7 bits per step, below the random walk's entropy rate log2(7). Additional information must therefore be supplied. An algebraic entropy identity alone does not establish a realizable bits-back code. The claimed equivalence to the published LSEnet (arxiv:2405.11801v1) and DeSE(arxiv:2505.14040v1) objectives appears incorrect: their leaf terms take the logarithm of an average parent volume, whereas the manuscript averages logarithms. For a single edge with both membership rows (3/4, 1/4), I obtain 0.64154 bits for the manuscript's objective versus 0.77475 for their published formulas. This undermines the claimed applicability to those methods.

Dense terminology further obscures the contribution; notably, the uniform-assignment value is called a “floor” although it is not a lower bound.

Questions for authors
  1. Can you specify a lossless decoder and account for all switch signaling and side information?
  2. How do you reconcile the claimed objective equivalence with the counterexample above?
1 comment
AuthorsOpenReview ↗

Both objections are correct: Definition 3 is not decodable as stated, and Definition 1 is not LSEnet's or DeSE's formula

Thank you for checking both claims numerically. Both objections are correct, as is the remark about "floor".

Decoder (first weakness, question 1). For K8 split 4/4 the cost is 18/7 ≈ 2.571 bits, below log⁡27≈2.807\log_2 7\approx 2.807, as you say. This example is a hard partition, where Definition 3 equals the two-level SE of Equation (1) (Theorem 1); 2.571 is the H2∗H_2^\ast printed for K8 in Corollary 2. So the missing switch signal is already present in the discrete SE formula, which charges the module codeword when the walk changes module and nothing for signaling the change. We carried that accounting into the soft case and then called the result an "operational expected code length". That was wrong. Theorem 2 is correct algebra, but, as you say, an identity alone does not give a realizable code.

A lossless decoder with ideal code lengths (not in the submitted paper):

  • Shared once, outside the per-step rate: the graph and SS, which fix every codebook (as in the discrete case), and the first node with its label.
  • The label drawn for a node when the walk arrives is kept as its label for the next step, so the decoder always knows the current module kk. The per-step joint distribution, and hence HcodeH_{\rm code}, is unchanged.
  • Each step sends a stay/switch flag from a binary codebook for module kk (stay probability wk/Vkw_k/V_k), then the new module's codeword after a switch, then the next node's codeword from the book of its module.

The expected length is Hcode(S)+F(S)H_{\rm code}(S)+F(S), with F(S)=∑k(Vk/2m)h(wk/Vk)F(S)=\sum_k (V_k/2m) h(w_k/V_k) and hh the binary entropy. The encoder picks each label by decoding random bits of another, already compressed message with the node's row of SS; once the decoder has the node and its label, it re-encodes the label with the same row and gets those bits back. This is bits-back coding, and the net rate is Hbil(S)+F(S)H_{\rm bil}(S)+F(S). For K8 split 4/4 the flag costs 0.985 bits, so the complete code costs about 3.56 bits, above log⁡27\log_2 7. So Theorem 2 does not make HbilH_{\rm bil} the rate of a decodable code: HbilH_{\rm bil} is the complete code's net rate minus the flag cost, just as H2H_2 is at a hard partition. Theorem 4, Corollary 2, Example 2 and the census counts of loose instances do not use Definition 3.

LSEnet and DeSE (second weakness, question 2). It cannot be reconciled; our claim was wrong. We re-read both definitions (LSEnet, Definition 4.3 with its Equation 6; DeSE, Equation 6). In both, the parent volume inside the logarithm is the assignment-weighted sum of the parent volumes, so their leaf term is the logarithm of an average, while Definition 1 averages logarithms. Your one-edge values are correct: 0.64154 for Definition 1 and 0.77475 for theirs. The two forms agree at hard assignments and wherever all the modules a node is spread over have equal volume; elsewhere theirs is larger, by Jensen's inequality. The claim "algebraically identical" now rests only on the open-source library, the one case that Section 3 reports as checked numerically. We have not re-checked the corresponding statements for Neuromap, DMoN and MinCutPool here.

What this changes, for their published formula:

  • Still true: at the uniform assignment all module volumes are equal, so the value H1−log⁡2(K)/KH_1-\log_2(K)/K (Theorem 4) and Corollary 2 hold unchanged, and Theorem 5 is already written with averaged parent volumes. At the bowtie point of Example 2 both modules have volume 6, so the value log⁡23\log_2 3, below every partition, is unchanged. In the census, the 6 instances where the uniform assignment already beats every partition carry over, including the largest margin, 0.321 bits.
  • Fails: Theorem 2 as an equality (their objective is ours plus a nonnegative Jensen term), and the analogue of Hmul≥HbilH_{\rm mul}\ge H_{\rm bil} in Conjecture 1 (one edge, both rows (0.95, 0.05): 1.065 bits, above the rounding average of 1). The plug-in curves of Figures 1(a) and 3 change except at their endpoints and midpoint.
  • Not established: Proposition 2, and the other 6 of the 12 census instances counted as loose, which we have not recomputed. One carries over by hand: on the 8-cycle with K = 3 (Figure 2), take three blocks of two adjacent nodes and split each of the two remaining nodes 1/3 to 2/3 between its neighbors' blocks so that all volumes are 16/3; both formulas then give 2.009 bits, against 2.042 for the best partition.

Wherever the paper says that LSEnet and DeSE use Definition 1 (abstract, introduction, Section 3, Figure 1(b), Table 1, Section 6), it should refer to the library only.

"Floor". You are right, and it is one example of the dense terminology you mention. H1−log⁡2(K)/KH_1-\log_2(K)/K is the plug-in's value at the uniform assignment. It is an upper bound on the plug-in's minimum, not a lower bound, and Example 2 itself goes below it. "Uniform value" is the accurate name.

We have not uploaded a revised PDF; the corrections are stated in this reply only.

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

The paper compares and contrasts various differentiable relaxations of clustering objectives.

Critical strengths

n/a

Critical weaknesses
  • The paper is extremely hard to read. It's quite clear that the authors did not take the time to make this readable and just leveraged AI to write down results so it's hard to even understand what exactly the paper is about. Sentences like 'A deployed plug-in is not the objective it is named after; the multilinear extension is faithful to what a value means, though on the sparse real graphs tested not a better optimizer, and a reported plug-in value should be calibrated against its uniform-S value.' should be changed completely. The paper needs a major rewrite with a focus on actually presenting the results and explaining them to humans. Almost the entirety of section 3 is a cascade of definitions and theorems with no commentary. The motivation of the paper is unclear in the first place because the introduction is also poorly written.

  • Some of the main results such as Theorem 3 (exactness of multilinear extension) follow almost definitionally and have been well understood for a while

Questions for authors

n/a

1 comment
AuthorsOpenReview ↗

We agree on readability and on Theorem 3; what the paper says, in plain words

Thank you for the direct review. We agree with both points.

Readability. The paper is hard to read, and the sentence you quote is a fair example: it packs three claims into one. AI tools were used to draft and edit parts of the paper, as the AI Use Statement says, and the text was not edited enough for a human reader. That is our responsibility.

The motivation, in plain words: a low value of a soft clustering loss, or a value lower than on a randomized graph, is read as evidence of cluster structure. If a fully mixed assignment can score lower than any real clustering, a low value may say nothing about the graph.

What the paper says, and what the quoted sentence should have been:

  1. Soft clustering losses are built by putting fractional memberships into the formula for a hard clustering, and the value is then read as the score of a clustering. That reading can be wrong. On a graph with one edge and two clusters, every real clustering costs 1 bit, yet the half-and-half assignment scores 0.5 bits (Example 1).
  2. The average of the hard score over random rounding of the memberships can never go below the best real clustering (Theorem 3).
  3. On Cora and CiteSeer the first problem did not appear: the soft assignments found were almost hard, and each scored within 0.01 bits of its own rounding. With the same encoder, the second objective did not find lower-cost clusterings there (0 of 5 seeds on each dataset; Section 5.3). On PubMed, run without an encoder, it did on 4 of 5 seeds (mean 11.960 against 11.971 bits), and a plain local search was lower than both (Appendix D).
  4. So a soft loss value should be reported next to its value at the fully mixed assignment, which for the soft SE loss is H1−log⁡2(K)/KH_1-\log_2(K)/K on any graph (Theorem 4).

Section 3 gives only short explanations ("Coding interpretation", "Reading the identity" and Example 1) for three definitions and two theorems, and the introduction states its motivation in one dense paragraph.

Theorem 3. We agree that it is close to definitional and already understood. Section 6 says that Theorem 3 and Proposition 1(a) instantiate earlier results (Karalias and Loukas, 2020; Wang et al., 2022), and the text after Definition 2 cites the multilinear extension of Calinescu et al. (2011). Its role is to be the exact reference that the soft loss is compared with. The abstract and the contribution list should not present it as a main result. What we regard as the paper's own content is the other side: the value of the soft loss at the fully mixed assignment (Theorem 4), the cases where it falls below every partition, and the same comparison for seven other objectives (Proposition 1, Table 1).

For completeness: the other two reviews found three errors, which we concede in our replies to them. The code of Definition 3 is not decodable as stated; Definition 1 is not the formula published for LSEnet and DeSE (the two differ at most soft assignments); and a decomposition in Appendix C is undefined when a module can be empty. We have not uploaded a revised PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.