- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper learns overlapping groups and parent links from categorical records that arrive over time. Its core is a conditional MDL code that pays for the graph, the memberships and one owner per record-field cell, with column counts fixed. Theorem 1 turns this code into a compression test with false selection probability at most under a column-permutation null, and Theorem 2 gives a Ville-type bound for evidence collected on fresh blocks. Two prediction heads add co-occurrence smoothing and fixed-share expert weights. Experiments use synthetic hierarchies of depth 1 to 7 and 600-record samples of Amazon Berkeley Objects and Wikidata, against COBWEB, FISHDBC, classical clusterers and prompted LLMs.
Critical strengths
Cell ownership is a clean fix for double counting when groups overlap, and the Kraft argument behind Lemma 2 and Theorem 1 is simple and correct as far as I checked. The certifier also works well as a filter on other methods' proposals. In Figure 3 it lifts COBWEB from 0.415 to 0.936 F1 at depth one and returns zero groups on every null stream.
I also like that native and pruned graphs are reported side by side and losses are stated openly, such as k-means beating ESCROW at (0.755 vs 0.511 ARI).
Critical weaknesses
The streaming framing is not supported by the setup. Prefixes are 300 or 600 records, recursive search revisits the stored prefix at each repair, and recursive proposals take up to 4,923.8 seconds on 600 Wikidata records (Section 8). There is no drift and no memory bound, so this is batch structure learning on small samples. Categorical stream and drift work such as LIMBO (Andritsos et al., 2004), COOLCAT (Barbará et al., 2002) and Cao et al. (2010) is missing. MDL clustering of categorical data (van Leeuwen et al., 2009) and hierarchical latent class models (Zhang, 2004) would be closer baselines than DP-means or BIRCH on multi-hot vectors.
The guarantee is weaker than the abstract suggests. The null means no association at all, and it says nothing about spurious groups once real structure exists (Section 3). All 345 pruned decisions are unchanged for from 2 to 30 (Appendix D.10), so the margin does little work. Gains are mixed too. In Table 2 selected COBWEB has the best mean F1 (0.781), and on Wikidata selection drops parent-based ESCROW from to bits saved. Internal labels like EHR05 and R27 make the paper hard to follow.
Questions for authors
- What happens when the hierarchy changes mid-stream, for example a group splits? Can repairs remove groups that lose support?
- How do time and memory per record grow with n, and can certification avoid revisiting the full prefix?
- Could you add an MDL categorical clustering method or a latent class model as a proposer under the same certifier?
- Is there a weaker null than full column independence under which false selection of single groups can be bounded?
4 comments
5. The guarantee (Q4). We would like to clarify that the abstract states the null, and Section 3 adds the repeated-check result. For single groups inside a parent given by a rule fixed from the past, yes: new Proposition 3 (App. J) tests a child there on fresh iid records at level 2^-b, with false-discovery control across nodes. The tested fields may depend on the fields that define the parent; the null is that, inside the parent, they carry no further association. App. J.4 states the scope. It kept no child in 593 true leaves. With real structure present, the certifier kept the best searched split of a true leaf 0 of 600 times (App. K.11).
6. "The margin does little work." We read this result as a strength of the code: kept graphs score at least 35.3 bits and rejected non-empty graphs at most -16.59, so every b between gives the same 345 decisions (App. K.8).
7. Mixed gains. As your review notes, the certifier works well as a filter on other methods' proposals, and the paper's claim is the code, not one best proposer. Table 2's best mean F1 is that filter at work: certifying COBWEB lifts it from 0.676 to 0.781, above every native graph (best: FISHDBC, 0.761). On Wikidata, the selected value is negative against a reference that knows each block's counts; against background with the same heads, selected graphs of both ESCROW searches, COBWEB and FISHDBC gain on every variant, also on 2,000 unseen records per order (App. K.1). Selection tests support, not prediction; the paper reports both.
8. Labels. We agree. EHR05, R27 and the other run labels are removed; each method and selection rule now has one name.
Summary of your points and the evidence
- Streaming: one-pass insertion, and prefix and block guarantees; Section 4 defines both searches.
- Mid-stream change: a 300-record window drops a dead group and finds a split (K.12).
- Time and memory: 110 ms per record in 107 MB on 3,362 records; a leaf edit is priced in at most 1.6 ms up to n = 100,000 (K.13).
- Closest baselines: seven added, native and certified; LCA picks one class on all 40 real inputs (K.14).
- Single groups: Proposition 3 tests a child inside a past-fixed parent; 0 of 600 searched splits kept inside true leaves (App. J, K.11).
- The margin: any b between -16.59 and 35.3 gives the same 345 decisions (K.8).
- Mixed gains: the certifier gives Table 2's best F1; Wikidata gains against background (K.1).
- Labels: one name per method.
Thank you again for your time and your careful review. If any remaining concern is keeping your score at 2, we would welcome the chance to address it before the discussion ends.
Thank you for the detailed response and the new experiments. The drift study, the added categorical baselines and Proposition 3 address my main questions, so I am raising my score to weak accept. I still see the streaming evidence as small scale, and I encourage the authors to state this limit clearly in the final version.
Thank you very much for your thoughtful re-evaluation and for raising your score to weak accept. We appreciate the time you took to review the new experiments, the drift study, the added categorical baselines, and Proposition 3.
Our work is primarily theoretical, and the experiments were designed to validate the theoretical results rather than to serve as a large-scale empirical benchmark. We agree with your point on the scale of the streaming evidence, and we will state this limitation clearly in the "Scope and next steps" section of the final version.
Thank you again for your constructive feedback, which has helped strengthen the clarity and rigor of the paper.
Thank you for your careful review, for checking the Kraft argument behind Lemma 2 and Theorem 1, and for the pointers to related work. We are glad you found cell ownership a clean fix for double counting, and that you liked seeing native and pruned graphs side by side with the losses stated openly. We answer each point below; changes in the revised PDF are in blue.
1. Streaming. Section 4 now defines streaming for each search. Parent-based insertion is one pass: one descent per record, never revisited. Recursive search repairs over the stored prefix on a schedule, so its memory grows with n. The theory is built for arriving records: Theorem 1 certifies a graph at a declared prefix, and Theorem 2 adds evidence from each later block.
2. Mid-stream change (Q1). Full-prefix repairs keep a group that stops at record 600, since its old records still pay for it, and do not find a split's new children. Run fresh on the last 300 records, the same search and certifier track the change: the dead group is gone in 10 of 10 streams by record 900, both new children are found under their parent in 7 of 10 by 900 and 10 of 10 by 1,200, and no null stream keeps a group (App. K.12).
3. Time and memory (Q2). The 4,923.8 s is recursive search; certifying its graph took 0.41 s. On all 3,362 Wikidata records, parent-based insertion takes 110 ms per record in 107 MB, and certifying its 1,013-group pool from scratch takes 5,255 s. Without duplicate nodes, a leaf edit is priced from count tables and the leaf's rows alone (new Proposition 4, App. J): at most 1.6 ms for every n from 1,000 to 100,000 on synthetic 40-node graphs, against 0.04 to 6.4 s to recompute, with equal results (App. K.13).
4. Closest baselines (Q3). Thank you for these references. We added latent class analysis (LCA), COOLCAT, Squeezer, k-modes, LIMBO, ROCK and Bayesian hierarchical clustering, each checked first, native and certified on the 82 inputs (App. K.14). With BIC, a two-part description length, LCA picks one class (no group) on all 40 real inputs. Certified, none keeps a group on any null stream it finished. Section 9 now discusses COOLCAT, LIMBO, Cao et al. (2010), van Leeuwen et al. (2009) and Zhang (2004).