- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the hypergraph coarsening problem in the setting where the hypergraph is changing over time. Rather than the simpler dynamic model, it instead considers the case where each update has an associated timestamp.
The paper proposes an algorithm for updating a coarsening upon receiving an update (or a batch of updates). The algorithm is based on combining the notions of personalised PageRank and conductance to create a new similarity measure for any pair of vertices. Then, those vertices are contracted if their similarity is considered above some threshold.
The algorithms performance is evaluated by comparing closely its computed coarsening corresponds to a ground truth given by a baseline algorithm which is applied to each time step independently.
Critical strengths
The paper studies a natural problem which is of interest to the community - that of dynamic hypergraph coarsening. A fast and effective algorithm for this would be of interest and suitable for ICLR.
Critical weaknesses
The overall presentation of the paper and framing of the problem is a significant weakness of this paper.
- The problem is not well defined in the paper. The objective of hypergraph coarsening is not clearly stated. It is implied that in existing work, the conductance of the contracted nodes is used to evaluate static hypergraph coarsening methods. However, this paper states that 'Conductance is one structural metric, not the sole definition of coarsening quality', but no other definition of coarsening quality is given.
- The motivation for the given algorithm is unclear. The proposed TAPS similarity score combines personalised PageRank and conductance but without justification for why we should combine them in this way.
- The provided theoretical results do not relate to the quality of the hypergraph coarsening produced by the algorithm. Rather, they state properties of the TAPS similarity score. This does not justify or motivate the use of TAPS for hypergraph clustering.
- The experimental results are not convincing. I would hope the experiments to demonstrate two things: (a) that the proposed algorithm produces 'high quality' hypergraph coarsenings and (b) that the proposed algorithm is significantly faster than repeatedly running static algorithms. The first of these objectives is difficult since the paper does not state what is considered a high quaility coarsening result. Instead, the experiments measure the overlap between the generated coarsening and that of a baseline algorithm.
Questions for authors
- What is the motivation for the TAPS similarity score? Why should it be the 'correct' method for maintaining a hypergraph coarsening?
- As I understand it, the proposed algorithm does not really handle deletions, except by the occasional recomputation using the baseline algorithm.
- How were the parameters gamma (from PPR), alpha (from TAPS), and k and K (from THGC) chosen for the experiments?
Dear Reviewer,
Thank you for raising the central questions of objective, score design, theory, and controls. We clarify them directly.
Objective and quality criterion. Equation (1) gives the multiway normalized hypergraph conductance used as the structural criterion. The actual objective, defined immediately afterwards in Section 3, is temporal coarsening maintenance: maintain a coarsened hypergraph close to the selected full static reference Bt(Ht) while avoiding full reconstruction. Consequently, quality is evaluated jointly through structural conductance, pair disagreement from that reference, static-reference churn, timing, state size, and downstream preservation where valid. We will move this definition and the distinction between structural diagnostics and the full objective earlier in the main text.
Why PPR plus cut. TAPS is a local repair-ranking rule, not a claim of a new universal clustering objective. The recency-weighted PPR component captures repeated recent interaction in the dirty region; the cut component discourages contractions that damage the current boundary structure. The mixture is applied only to local candidate pairs, while the maintained object remains the hypergraph coarsening and its incidence structure. We will add a compression-matched endpoint ablation and limit the claim to the stated structural-maintenance trade-off rather than asserting universal superiority.
Theory. The theory does not prove global coarsening optimality. It bounds the score perturbation under temporal locality and restricted coarse-space fidelity; the margin corollary transfers this to merge eligibility outside a measurable decision band. We will state this limitation explicitly, report the realized diagnostic quantities behind the assumptions, and leave end-to-end coarsening fidelity to the matched empirical tracking measurements.
Deletions and hyperparameters. The event model includes node/hyperedge deletions and sliding-window expiration. The deletion-heavy experiment is intentionally a boundary case: when frequent expiry forces repeated resynchronization, static rebuilding can be preferable. Thus the manuscript does not require local repair to win in every regime. The controls are r (target ratio), τ (acceptance threshold), K (per-round work cap), k (resynchronization interval), α (mixture), and γ (PPR teleportation). We will add an explicit configuration/selection table for every main experiment, including whether a choice was fixed or selected on a disjoint prefix, so the protocol is fully reproducible and does not implicitly tune on its evaluation horizon.
Thank you again. In revision, we will foreground the static-reference maintenance objective, precisely limit the TAPS and theory claims, and document the deletion protocol and every control-selection choice.