Identifiable Hierarchy Depth: An MDL Tree Cost for Structural Entropy

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 $H^T(G)$. We give SE a two-part minimum-description-length (MDL) objective $L(T)=\mathrm{vol}\cdot H^T(G)+U(T)+C(T)$, whose terms are all prefix-code lengths: $\mathrm{vol}\cdot H^T$ is exactly the cost of coding each directed edge endpoint by its Li–Pan tree codeword, $U$ is the up-addressing cost SE leaves unpaid, and $C$ is an Elias-gamma size-list code for the tree topology. We derive the exact condition under which a coarse $k$-way split strictly beats its binary refinement — collapse improves $L$ iff $2E_{\mathrm{int}}(a){\log }_2(V_p/V_a)<g_a+{\ell }_{\gamma }(s_a)$ — and prove that no $L$-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 $o(n\sqrt{d})$. No such tree cost makes nulls flat; the null test, part of the method, has false-positive rate $\le 1/(k+1)$ per level under exchangeability, which swap-chain resamples satisfy only approximately. On planted hierarchical SBMs with $160$ vertices at hierarchy strength $6$, the calibrated depth recovers $d=1,2,3$ in every seed, where pure SE returns binary dendrograms of depth $6$–$9$ and neither multilevel Infomap nor the nested SBM recovers all three; it calls $34$ of $40$ degree-matched nulls flat (both rivals call all $40$ flat) and misses a fourth level of $10$-vertex blocks, which it recovers at $640$ 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 $35$–$40$ of $40$ nulls flat where the raw rules of all but the map equation call none flat, and with sparsest-cut bisection it recovers $d=1$ to $4$ in at least $7$ of $10$ 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.