- 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: that charges 1 bit per level climbed and 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 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
- 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?
- Can you prove the method finds the true number of levels on a given hierarchy at least asymptotically?
- Why does the test keep an extra level on large flat graphs and would it be possible to predict theoretically when does it happen?
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 a lowers by one the climb of every directed edge that leaves a and leaves all other climbs unchanged. For a climb code with lengths ℓ(h), U therefore changes by −∑e leaving awe[ℓ(he)−ℓ(he−1)], which equals −cga only when ℓ is linear in h plus a constant (the unary code has c=1). For other codes Theorem 2 holds with this sum in place of ga, and the collapse rule is no longer local to a. Corollary 1 (i)–(ii) still hold for any code whose lengths do not decrease with h, and (iii) with the same sum in place of ga. Section 8 now states this in place of the old item (2).
Readability. Several symbols had more than one meaning: d was both a depth and the mean degree in Proposition 1; k was both the number of resamples and a node's number of children; P was a level partition, a tree path and a constant. The revision uses ν for the mean degree, K for the number of resamples and π(u,v) for the path, and adds a notation sentence in Section 2 (Figure 3's axis labels still say k; its caption says this is K). 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=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 K 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=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=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ν (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=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 U 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); 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 nB vertices should support a fluctuation split worth on the order of nB 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=160, r≥4; 320 at n=640). The test should then remove it, because its resamples keep the same blocks. It does not on 4 of 5 d=1 graphs at n=160, r=4, on 4 of 5 one-level three-block graphs at n=486, and on 5 of 5 at n=640, and we do not know why. One candidate is the estimated coarse partition: on one d=1 graph at n=160, r=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.