acceptodds
Under review as a conference paper at ICLR 2027

Identifiable Hierarchy Depth: An MDL Tree Cost for Structural Entropy

Abstract

Hierarchical clustering, community detection and world models need the number of levels, which their objectives do not provide. Dasgupta's cost, hierarchical modularity and structural entropy (SE) never get worse when a level is added, so their optimizers add levels even to graphs with no hierarchy. Depth becomes identifiable with two ingredients: a per-level null-model test around any hierarchy builder and score, and, for SE, a completed code whose minimizer has finite depth. For SE the failure is exact: any multiway encoding tree can be refined to a binary tree without increasing . We give SE a two-part minimum-description-length (MDL) objective , whose terms are all prefix-code lengths: is exactly the cost of coding each directed edge endpoint by its Li–Pan tree codeword, is the up-addressing cost SE leaves unpaid, and is an Elias-gamma size-list code for the tree topology. We derive the exact condition under which a coarse -way split strictly beats its binary refinement — collapse improves iff — and prove that no -optimal tree contains a null refinement, so depth is well defined. We then prove a boundary result: because the SE code fixes its probabilities by volumes, its gains are linear in cut fluctuations, so on sparse random null graphs a spurious level survives any topology cost of scale . No such tree cost makes nulls flat; the null test, part of the method, has false-positive rate per level under exchangeability, which swap-chain resamples satisfy only approximately. On planted hierarchical SBMs with vertices at hierarchy strength , the calibrated depth recovers in every seed, where pure SE returns binary dendrograms of depth – and neither multilevel Infomap nor the nested SBM recovers all three; it calls of degree-matched nulls flat (both rivals call all flat) and misses a fourth level of -vertex blocks, which it recovers at vertices, where it instead keeps a spurious sub-level on flat two-block graphs. Around Dasgupta's cost, hierarchical modularity, the map equation and plain SE, the test keeps – of nulls flat where the raw rules of all but the map equation call none flat, and with sparsest-cut bisection it recovers to in at least of seeds each; builders that merge planted levels, and the map equation, which prefers shallower trees, are not rescued. Code, raw results and preregistrations are in the supplement.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
hierarchical clustering, community detection, model selection, minimum description length, null models, structural entropy

Reviews

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

The paper argues that hierarchy objectives such as structural entropy (SE) and others cannot choose the number of levels, because adding one level never increases them. It propose to add two terms to the SE: U(T)U(T) that charges 1 bit per level climbed and C(T)C(T) that charges an Elias-gamma code for the tree topology. The paper provide a theoretical analysis: Theorem 2 for the increase of cost when collapsing a node to it's parent in the tree. It also shows that even on a random graph with no clusters, some split of the vertices has fewer cut edges than average, and this split lowers the score by far more than the cost of one level (Proposition 1). To fix the problem, the paper propose to derive an algorithm where each level is tested separetely and kept only it it's improve the score.

Critical strengths
  • The paper proves why SE alone is not enough to choose the depth of a hierarchy.
  • Proposition 1 is a negative result of interest within the framework presented in the paper.
  • The experiments are detailed and on synthetic datasets the work-around of the paper alows to recover the true depth in certain regimes.
Critical weaknesses
  • Overall, he paper is hard to read: many symbols are used before they are defined, some have several meanings...
  • I do think that Limitation (2) is wrong. The paper says that any prefix code would give the same theorem with the term gag_a replaced by the cost of the considered code. However, I do think this does only hold if the code length grows linearly with the climb.
  • The experiments are limited: the considered graph are synthetic with at most 640 vertices and the run time are not compared against the other methods which would be of interest.
Questions for authors
  1. Would increasing the price per added level make the method work better? If not, how much of the depth selection is done by the null test and how much by the price?
  2. Can you prove the method finds the true number of levels on a given hierarchy at least asymptotically?
  3. Why does the test keep an extra level on large flat graphs and would it be possible to predict theoretically when does it happen?
1 comment
AuthorsOpenReview ↗

Limitation (2) was wrong and is corrected; notation fixed in the revised PDF; answers to the three questions

Thank you. The revised PDF marks every change in blue.

Limitation (2). You are right: it holds only when the code length grows linearly with the climb. Collapsing aa lowers by one the climb of every directed edge that leaves aa and leaves all other climbs unchanged. For a climb code with lengths ℓ(h)\ell(h), UU therefore changes by −∑e leaving awe[ℓ(he)−ℓ(he−1)]-\sum_{e\text{ leaving }a} w_e[\ell(h_e)-\ell(h_e-1)], which equals −c ga-c\,g_a only when ℓ\ell is linear in hh plus a constant (the unary code has c=1c=1). For other codes Theorem 2 holds with this sum in place of gag_a, and the collapse rule is no longer local to aa. Corollary 1 (i)–(ii) still hold for any code whose lengths do not decrease with hh, and (iii) with the same sum in place of gag_a. Section 8 now states this in place of the old item (2).

Readability. Several symbols had more than one meaning: dd was both a depth and the mean degree in Proposition 1; kk was both the number of resamples and a node's number of children; PP was a level partition, a tree path and a constant. The revision uses ν\nu for the mean degree, KK for the number of resamples and π(u,v)\pi(u,v) for the path, and adds a notation sentence in Section 2 (Figure 3's axis labels still say kk; its caption says this is KK). It is not a full rewrite: the abstract still uses a few symbols before Section 2 defines them.

Experiments. We agree the graphs are small (at most 640 vertices; a calibrated run there took 4–11 minutes on one core) and that real graphs serve only as null controls, because their depth is unknown. One optimization takes about 0.3 CPU-seconds at n=160n=160, and a calibrated run about 8–11 CPU-seconds on four seed-0 graphs, because it costs one optimizer run on the graph plus KK runs per tested level (Limitation (3)). We did not time the other methods on the same machine, so the paper makes no run-time comparison.

Q1. A higher price per level. We did not run a priced objective (and a level's statistic counts all levels below it, so the comparison is approximate), but the submitted results at n=160n=160, strength 6, show where a price would have to sit. On the 40 nulls the optimizer's tree gains 586 to 835 bits over the flat tree. On the planted graphs, the statistic for level 2 (bits gained beyond level 1) is 1191 or more, and for level 3 it is 642 to 1587, with one value below 835, on a d=4d=4 graph. So at this one size a price near 840 bits per level would separate the null gains from all planted level-2 and level-3 statistics but that one (we did not check the fluctuation sub-levels below the planted ones). But that price is the null's own gain, which Proposition 1 bounds below by order nνn\sqrt{\nu} (proved for Erdős–Rényi graphs, Limitation (1)), so it changes with size and density and has to be measured from a null; the resample test is that measurement. The split between price and test: the uncalibrated tree has depth at least 1 on all 100 nulls of the grid (Section 4.2), so on all 40 at r=6r=6, where the calibrated depth calls 34 of 40 flat (Table 2); on the preregistered criteria of Table 1 the counts are 0 of 30 uncalibrated against 25 of 30 calibrated. In a small ablation (three graphs), removing UU gives uncalibrated depth 6 but calibrated depth 2.

Q2. Proof of recovery. We have no consistency proof, and the paper does not claim one; Section 1 now says so. What is proved is local: the exact collapse condition, that optimal trees contain no null refinement, and Proposition 1 (a spurious level on random graphs). The revision adds one conditional guarantee, against extra levels only: in a planted hierarchical SBM without degree correction, with the true coarser partitions supplied and exchangeable resamples, a spurious extra level is accepted with probability at most 1/(K+1)1/(K{+}1); with estimated partitions the probability that they are wrong adds to this, and we do not bound it (Remark 1, Section 4.2). Nothing bounds missed levels.

Q3. The extra level on large one-level graphs. Part of it is predictable, though not proved. By the same mechanism as Proposition 1 (not proved inside a block), a block of nBn_B vertices should support a fluctuation split worth on the order of nBn_B times the square root of its internal mean degree, so the uncalibrated tree keeps a sub-level when blocks are large (80 vertices at n=160n=160, r≥4r\ge4; 320 at n=640n=640). The test should then remove it, because its resamples keep the same blocks. It does not on 4 of 5 d=1d=1 graphs at n=160n=160, r=4r=4, on 4 of 5 one-level three-block graphs at n=486n=486, and on 5 of 5 at n=640n=640, and we do not know why. One candidate is the estimated coarse partition: on one d=1d=1 graph at n=160n=160, r=6r=6, the split misplaces 13 of 160 vertices, although there the test did remove the sub-level. We have not tested this, and we have no theory that predicts when the test fails.

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

This paper addresses the problem of determining the appropriate number of levels in hierarchical community structures of networks. The authors show that conventional structural entropy (SE) cannot determine hierarchy depth because refining a hierarchy never increases the objective. To address this issue, they propose a minimum description length (MDL) objective that supplements SE with the coding costs of specifying the starting ancestor of an edge traversal and describing the tree topology. They derive exact conditions for when merging hierarchical levels reduces the description length.

The authors further demonstrate that the proposed MDL objective alone can still detect spurious hierarchical structures in random graphs due to statistical fluctuations. To mitigate this problem, they introduce a per-level calibration procedure that compares improvements in the objective against degree-preserving randomized graphs while preserving previously accepted hierarchical levels. This calibration procedure can also be applied to other hierarchical clustering objectives.

The method is evaluated primarily on synthetic hierarchical stochastic block models with known hierarchy depths, using comparisons with Infomap, nested SBM, and other hierarchical clustering methods. The proposed approach successfully recovers one to three hierarchical levels under sufficiently strong hierarchical structure, but its performance deteriorates for weaker structures or certain larger and deeper networks. Experiments on real networks are limited to evaluating false-positive behavior on randomized counterparts, since their true hierarchy depths are unknown.

Critical strengths

Clarification of the flaws of structural entropy: It attributes the inability of structural entropy to determine the number of hierarchy levels to the absence of information necessary for encoding. In particular, the distinction drawn between downward encoding from the lowest common ancestor and upward encoding--which specifies the starting position--is clear from an information-theoretic perspective.

Derivation of conditions for selecting the number of hierarchy levels using MDL: We have rigorously calculated the change in description length resulting from the subdivision of the hierarchy and established the conditions under which such subdivision is adopted. However, this result evaluates local changes in the objective function and does not constitute a proof of statistical consistency regarding the true hierarchical structure.

Critical weaknesses

Why is it necessary to start with structural entropy?: This is the most fundamental question. Methods based on generative models and statistical inference--such as hierarchical SBMs and nested SBMs--already exist for the problem of estimating the hierarchical structure of networks. Although structural entropy is defined as the code length of a random walk, minimizing it does not generally guarantee that the true hierarchical structure will be obtained. The authors attempt to determine the number of hierarchy levels by compensating for the imperfect encoding associated with structural entropy. However, the question remains as to whether minimizing the code length of a random walk is, in the first place, a suitable principle for estimating hierarchical structure. This question is particularly significant given that the proposed MDL method alone tends to over-partition random graphs.

Questions for authors

What fundamental advantages does the two-step approach--combining a code-length penalty with structural entropy and subsequently applying a correction via a randomization test--offer compared to methods based on statistical generative models such as the hierarchical SBM?

1 comment
AuthorsOpenReview ↗

Why start from structural entropy, and what the nested SBM does better

Thank you. We agree with the premise of your question: minimizing the code length of a random walk does not by itself target the true hierarchy. Proposition 1 shows exactly this on random graphs, which is why the null test is part of the method. We do not claim the random-walk code is a better principle than a generative model.

Our claim is narrower. SE is used to build hierarchies, for example in hierarchical graph pooling, and recent models fix the number of levels by hand; Dasgupta's cost and hierarchical modularity give no depth rule either (the map equation selects depth itself, but scores trees shallower than the planted ones higher, Section 6). For them the question is how many levels the score's own tree supports. The per-level test is not tied to SE: Table 3 wraps it unchanged around plain SE, Dasgupta's cost, hierarchical modularity and the map equation, which then keep 35 to 40 of 40 nulls flat, where the raw rules of all but the map equation call none flat. SE is the case where we can also say why depth fails and repair the code so that its minimizer has finite depth.

Compared with the hierarchical SBM, the test needs a null model only for "no further level" (degree-preserving resamples that keep the accepted levels), not a generative model of the hierarchy, so it applies to scores that are not likelihoods. We test on planted SBMs only because their depth is known. At strength 6 the calibrated depth recovers d=1,2,3d=1,2,3 in every seed, while the nested SBM recovers d=2d=2 on 1 of 10 graphs and d≥3d\ge3 on none, with or without degree correction and with five restarts (Tables 2 and 9). The nested SBM is better at strength 4 with d=1d=1 (5 of 5 graphs against 1 of 5 for ours) and at strength 8 with d=2d=2 (5 of 5 against 4 of 5; Table 2). These are small synthetic graphs, so we read this as a difference in behaviour there, not as a general ranking.

The nested SBM does better in two further ways. It is flatter on nulls: all 40 at strength 6, against 34 of 40 for our method (two-sided Fisher exact p=0.026p=0.026). And it comes with a likelihood and statistical theory. Our method has no consistency guarantee, and its false-positive bound holds only under exchangeability: at the first level for a resampling scheme that our reported runs only approximate, and at deeper levels only in a planted block model without degree correction, with the true coarser levels supplied. The revised PDF (changes in blue) adds a scope paragraph at the end of Section 1 that says this, and states the guarantee in a new Remark 1 (Section 4.2).

Reviewer_GGxmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to select the number of levels in graph hierarchies. For structural entropy (SE), it proposes the objective L(T)=vol⋅HT(G)+U(T)+C(T)L(T)=\mathrm{vol}\cdot H^T(G)+U(T)+C(T), where UU charges for upward addressing and CC is a topology-coding term. It derives local refinement and collapse identities, shows that LL-optimal trees exclude refinements with zero SE gain, and argues that random cut fluctuations can nevertheless favor nontrivial trees on null graphs. The proposed method combines multi-start local search with sequential null comparisons using degree-preserving resamples, additionally preserving coarser block-pair edge counts at deeper levels. The calibration is also evaluated with other hierarchy objectives. Experiments mainly use hierarchical stochastic block models. At n=160n=160, branching factor b=2b=2, and hierarchy strength r=6r=6, the paper reports correct depth recovery for each of d=1,2,3d=1,2,3 in all ten seeds, while documenting underestimation and overestimation in other regimes. These results concern depth recovery, rather than necessarily exact recovery of the hierarchy's partitions.

Critical strengths
  1. The proposed objective has interpretable local optimization rules. Theorem 2 gives an exact expression for the change in the objective when collapsing a node, separating the contributions of structural entropy, upward addressing, and topology. Corollary 1 consequently excludes refinements with zero structural-entropy gain from LL-optimal trees. These formulas make the effect of the additional terms transparent. The distinction between such zero-gain refinements and spurious structure arising from random graph fluctuations is also informative.

  2. The experimental evaluation includes relevant comparisons and explicitly reports failure modes. The paper compares with multilevel Infomap and the nested SBM, evaluates calibration with several hierarchy builders, and includes branching and degree-heterogeneity checks. The reported recovery of depths 1, 2, and 3 in all ten seeds each at n=160,r=6n=160,r=6 provides evidence of the method's usefulness in that setting. The authors also explicitly report false positives on null graphs, missed levels, and persistent extra levels in larger-block settings, which helps assess the scope and limitations of the method.

Critical weaknesses
  1. The depth guarantee is not justified for the adaptive estimator. Definition 2’s rank argument requires exchangeability, which is not established after estimating PℓP_\ell from the same graph, as acknowledged in Limitation (5). Incorrect coarser partitions can also leave genuine structure unresolved.

  2. Novelty and the full objective’s added value need clearer support. Theorem 1’s binary-refinement conclusion already appears in SuperTAD’s Lemma 3 and Eq. (4), while Lemma 1’s edge-LCA identity appears in Pan et al.’s proof of Theorem 2.1. SuperTAD is uncited, and the overlap with Pan et al. is unexplained. These precedents should be distinguished from the potentially new objective and calibration.

References

Questions for authors
  1. Adaptive calibration. What assumptions justify exchangeability after estimating PℓP_\ell and the claimed depth-overestimation bound? Does using the true coarser partitions resolve the failures in Table 7?

  2. Novelty. How do Lemma 1 and Theorem 1 extend the edge-LCA identity of Pan et al. (2021) and the binary-refinement result of Zhang et al. (2021)?

  3. Proposition 1. How is the gap between vertex-balanced and volume-balanced bisections controlled? Why does excluding topology costs of scale o(nd)o(n\sqrt d) justify Appendix C’s broader necessity claim?

  4. Objective versus optimization. Can broader paired ablations isolate the benefits of UU and CC after calibration? Is the missed fourth level at n=160n=160 caused by the objective or the local search?

1 comment
AuthorsOpenReview ↗

You are right on the guarantee, the two precedents and the Proposition 1 step; the revised PDF narrows the first and fixes the others

We agree with both weaknesses; the revised PDF marks every change in blue.

W1 / Q1. Exchangeability after estimating PℓP_\ell. Definition 2 claimed more than we prove. A new Remark 1 (Section 4.2) states the guarantee as follows, and the abstract and contribution 1 summarise it.

  • First level. If, under the null, GG is a uniform simple graph with its degrees, the test is exact when GG and its KK resamples are exchangeable. Independent swap chains started at GG, which our runs used, give this only approximately. If GG follows the chain's stationary law, drawing all resamples from one intermediate graph reached from GG makes GG and the resamples exchangeable for any chain length (Besag and Clifford, 1989); for the uniform null this needs a chain whose stationary law is uniform. We also found that our swap routine counts only accepted swaps, so its stationary law is not exactly uniform and the condition above fails for it. Condition C3 of Table 6 draws the tested null and its resamples independently from one graph, so they are exchangeable whatever the chain; its false-positive rate is 0.095 (95% CI [0.058, 0.144]). Remark 1 says this; the printed numbers use the routine as it was.
  • Deeper levels. In a planted hierarchical SBM without degree correction the likelihood depends on GG only through the edge counts between bottom-block pairs, so given the true PdP_d and its degrees, GG is uniform on the set our within-class swaps move on. With the planted PdP_d supplied and exchangeable resamples, the test of level d+1d{+}1 is therefore exact. With estimated partitions the test coincides with that one when P^1..d=P1..d\hat P_{1..d}=P_{1..d}, so Pr⁡[d^cal>d]≤1/(K+1)+Pr⁡[P^1..d≠P1..d]\Pr[\hat d_{\rm cal}>d]\le 1/(K{+}1)+\Pr[\hat P_{1..d}\ne P_{1..d}]. We do not bound the second term, so for the estimator as used the bound is not proved; Remark 1 now says this.
  • Wrong coarse partitions. Agreed: they can hide real levels, and the test can only remove levels (Remark 1 (iii); scope paragraph, end of Section 1).
  • Table 7 with the true partitions. Not run, so we cannot say whether it removes those extra levels.

W2 / Q2. Prior work. We read both papers; you are right on both. The proof of Pan et al.'s Theorem 2.1 writes SE edge by edge with the volume of the lowest common ancestor, which is our Lemma 1. SuperTAD's Lemma 3 shows that a minimum-SE coding tree can be taken binary, and its Eq. (4) gives the exact SE change for grouping all children of a node but one, which is our Theorem 1 for that grouping. Our Theorem 1 only extends this to any group of children and says when the decrease is strict. The revision credits both (after Lemma 1 and Theorem 1, in the contributions and Section 7) and cites SuperTAD. What remains ours: reading the identity as a prefix code that pays for each descent but not for where it starts, which defines U(T)U(T); the objective LL; Theorem 2 and Corollary 1; Proposition 1; and the calibration.

Q3. Proposition 1. (a) You found a missing step: Dembo et al.'s bisections are vertex-balanced, and −2m+4 cut-2m+4\,{\rm cut} assumed equal volumes. With Vi=(vol/2)(1+εi)V_i=({\rm vol}/2)(1+\varepsilon_i) and ε2=−ε1\varepsilon_2=-\varepsilon_1, the exact identity adds R=2∑iEin(Bi)log⁡2(1+εi)R=2\sum_i E_{\rm in}(B_i)\log_2(1+\varepsilon_i). Since log⁡2(1+x)≤x/ln⁡2\log_2(1+x)\le x/\ln 2 and Ein(B1)−Ein(B2)=mε1E_{\rm in}(B_1)-E_{\rm in}(B_2)=m\varepsilon_1, R≤(V1−V2)2/(2mln⁡2)R\le (V_1-V_2)^2/(2m\ln 2). For G(n,ν/n)G(n,\nu/n), every equal-size split has ∣V1−V2∣≤nν (1+o(1))|V_1-V_2|\le n\sqrt{\nu}\,(1+o(1)) w.h.p., so R≤n(1+o(1))/ln⁡2R\le n(1+o(1))/\ln 2 against a gain of 4c nν4c\,n\sqrt{\nu}, and the sign stays negative once 4cν>1/ln⁡24c\sqrt{\nu}>1/\ln 2, i.e. for ν0\nu_0 large enough. Appendix A now has this step. (dd no longer denotes the mean degree; that is now ν\nu.) (b) Appendix C claimed more than the proposition shows. The proposition rules out per-level costs of order o(nν)o(n\sqrt\nu), which includes every universal code for the topology, such as our Elias-gamma code (O(log⁡n)O(\log n) bits for a two-block level). A charge of order nνn\sqrt\nu could flatten nulls, but it would have to be set from the null's fluctuation scale, that is, by a null comparison done analytically. Section 4.1, contribution 4 and Remark 2 (formerly Remark 1) now say this; Remark 2 reads "We consider three code families" instead of claiming they exhaust the design space.

Q4. Objective versus search; ablations. We cannot say which of the two loses the fourth level at n=160n=160: we never scored the planted four-level tree. Section 6 now says so, instead of "a limit of the LL minimiser". The n=160n=160 graphs carry the level: calibrated bisection recovers d=4d=4 on 10 of 10 (Table 3); calibrated LL finds it at n=640n=640 (5 of 5, Table 7). The ablation covers three d=2d=2 seeds only. Without UU the raw depth is 6 (96–98 internal nodes, against 12–15 with UU); without CC it is 2, 3, 3; the calibrated depth is 2 in all six runs. So here the ablation does not demonstrate a benefit of UU or CC after calibration; it shows UU's effect on the raw tree. We did not extend it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.