- 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 , , and 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 as an operational code length, and 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 uses . 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 , 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.
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∗ 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):
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), with F(S)=∑k(Vk/2m)h(wk/Vk) and h 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 Sj; once the decoder has node j and its label, it re-encodes the label with Sj and gets those bits back, H(Sj) on average. The net rate is Hbil(S)+F(S). On K6 split 3/3 this is 2.185 + 0.971 = 3.156 bits, above the walk's entropy rate log25≈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). What changes is the reading: Theorem 2 does not make Hbil the rate of a decodable code. Hbil is the complete code's net rate minus the flag cost, just as H2 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[log2Vk] is −∞ whenever module k can be empty, so the decomposition is undefined as written. It can be repaired. Wk=0 whenever module k has zero volume, so on that event log2Vk can be replaced by any finite constant ck without changing E[Wklog2Vk]. For the given S, let p, strictly between 0 and 1, be the probability that Vk>0, and dmin the smallest positive degree. If ck is at most log2dmin and at most log2E[Vk]+(p/(1−p))log2p, 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^)∣≤… (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.