- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper solves a problem of multi-scale clustering that arise in Markov-chains as they evolve in time. A chain may remain within small clusters over short times, while larger groups of clusters emerge over longer times. The authors identify these groupings by applying a structural entropy clustering objective to the -step transition matrix , varying . They compare the resulting scores against randomized chains that preserve the stationary distribution and self-loop probabilities, to assess whether the detected structure exceeds this baseline.
Critical strengths
None
Critical weaknesses
The paper is not very well written. There is a lot of superfluous technical detail that makes it very hard to follow. I suspect that large parts of it are entirely AI generated. While the results seem to be interesting, the paper is almost unreadable.
Questions for authors
-
What is reasoning behind subtracting the null baseline from the structural entropy? I understand that this allows the authors to interpret the calibrated quantity as a kind of additional compression induced by the markov chain when compared to the null chain. But, is this subtraction required for clustering?
-
What precisely is meant by an identified “timescale” in this framework? I understand that changing (k) reveals different optimal partitions. However, the locations at which these partitions change depend on the clustering objective. How should we distinguish a physical relaxation timescale of the Markov chain from a scale selected by the particular compression objective?
-
What motivates the choice of structural entropy over other clustering objectives? The paper demonstrates that the same null calibration also works with the map equation, which additionally recovers the balanced two-block example where structural entropy fails. Does structural entropy offer a particular advantage for identifying dynamical organization, or is the main contribution the calibration framework, independently of the chosen objective?
On the writing, and answers to your three questions
Thank you for the review, and for three questions that go to the centre of the paper.
The writing. You are right that the paper is hard to read, and Reviewer mGEB says the same of the experimental sections. Those sections put several numbers into most sentences, label the experiments with codes instead of saying what they test, and keep detail in the main text that belongs in an appendix. On AI: yes, AI tools were used to draft and edit parts of the text. The AI Use Statement before the references lists every use, including help with proofs and code, and we are responsible for all of it. It also says every proof was checked line by line; Lemma 5 was nevertheless wrong as stated (found by Reviewer bjbx, corrected in our reply there).
1. Why subtract the null, and is it needed for clustering? It is not needed for clustering. The partition at each step count k is found by minimising structural entropy on Pk alone (Definition 1); the null plays no part in choosing it. The subtraction answers a different question: is this partition worth reporting at this k? The raw saving cannot answer that, because it is positive even for a chain with no structure: a walk that lands in the same module twice by chance still saves code length (Lemma 3; about 0.53 bits for three equal modules). The null chains have the same stationary distribution and so the same chance level, which cancels in the difference. The difference tends to zero once the chain and its null chains have mixed, and it stayed below 0.1 bits on the two structureless graphs of the main text (Sections 4.2 and 4.6); the one with heavy self-loops reached 0.10–0.19 bits once they were removed (Appendix D). Figure 1(d) is the example: at k=1024 the optimizer still returns the three planted super-blocks, but the calibrated value is 0.00, so that scale is not reported.
2. What is a "timescale" here? On the planted chain it is a range of step counts over which one partition is the optimum and significant (it beats every null draw, and the null average by at least 0.1 bits). On the world-model graphs, where the partition coarsens smoothly and no range is stable, we used the word for the step count at which the calibrated value peaks (Section 4.6). Neither is a relaxation time. Relaxation times belong to the chain alone and are read from its eigenvalues, with no clustering objective involved (0.9, 10.7 and 56.9 steps for the planted chain with its 0.01 teleport, Section 4.1). You are right that where the partition changes also depends on the objective. On that chain structural entropy keeps the nine fine clusters up to k=11 and has handed over to the three super-blocks by k=23, that is, at 1.03 to 2.1 times the middle relaxation time; Markov stability and the map equation keep the nine only to k=4–6 (Sections 4.1 and 4.5). So the boundaries lie, on this chain, within a small factor of the relaxation times, but they are not equal to them, and the factor depends on the objective. All three objectives return the two planted partitions, in the same order. To tell the two apart: the eigenvalues give the relaxation times; the spectrum adds which partition goes with each range of steps and whether it is significant.
3. Why structural entropy? The calibration is the main contribution, and it is not specific to structural entropy. The paper's own comparison shows this (Section 4.5, Table 2): under the same null the map equation passes every test in that table, including two equal blocks, where structural entropy fails by construction (5/5 against 0/5); Markov stability fails the expander control (3/5) and did not pass from trajectories of up to 3,000 steps; it passes the rest. We did not show that structural entropy is better at finding dynamical structure; in one case it did better than both alternatives (the planted chain with self-loops removed, Appendix D). We used it for two reasons. It already builds state abstractions in reinforcement learning (Zeng et al., 2023) and had no notion of timescale. And it allows exact statements: its saving equals k-step persistence times module code length (Lemma 1), which explains why it holds the fine level longer and gives, for an idealized chain with no leakage between blocks, a sharp condition for the blocks to be the optimum (each below half the stationary mass; Lemma 4, Remark 1).
We have not uploaded a revised PDF: a rewrite, a full proof and further checks of the null are more than we can do properly before the deadline, so the corrections are stated in these replies.