acceptodds
Under review as a conference paper at ICLR 2027

Temporal Hypergraph Coarsening with Local Repair and Static-Recomputation Guarantees

Abstract

Large hypergraphs are increasingly used to model higher-order machine learning data, including group recommendation sessions, temporal hyperlink events, biological co-activation sets, and evolving tag or topic groups. Existing hypergraph coarsening methods reduce hypergraph size, but they are usually applied to a fixed snapshot; when events arrive over time, the standard alternative is to recompute the coarsening from scratch. We study temporal hypergraph coarsening as an incremental maintenance problem. We propose THGC, a framework that maintains a coarsened hypergraph under timestamped event streams through a Temporal Update Engine and a Coarsening Strategy Interface. The repair step is driven by TAPS, a Temporally-Aware Proximity Score that combines recency-weighted Personalized PageRank with a local conductance signal so that repair decisions account for both temporal interaction history and cut structure. The maintained object remains a hypergraph, with coarse hyperedges and incidence structure; graph projections are used only as local scoring surrogates. We give stability bounds relating temporal score drift, coarsening error, and the deviation from full static recomputation. Experimental results on temporal hypergraph benchmarks demonstrate significant speedups in update time while preserving the quality of the coarsened representation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Temporal hypergraph coarsening, dynamic hypergraphs, incremental graph algorithms, hypergraph compression, streaming hypergraphs, local repair, personalized PageRank, structural preservation, hypergraph partitioning, scalable graph learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_ZUWLOpenReview ↗
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.

  1. 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.
  2. 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.
  3. 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.
  4. 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
  1. What is the motivation for the TAPS similarity score? Why should it be the 'correct' method for maintaining a hypergraph coarsening?
  2. As I understand it, the proposed algorithm does not really handle deletions, except by the occasional recomputation using the baseline algorithm.
  3. How were the parameters gamma (from PPR), alpha (from TAPS), and k and K (from THGC) chosen for the experiments?
1 comment

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)B_t(\mathcal H_t) 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 rr (target ratio), τ\tau (acceptance threshold), KK (per-round work cap), kk (resynchronization interval), α\alpha (mixture), and γ\gamma (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.

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

This paper formulates temporal hypergraph coarsening as an incremental maintenance problem. Rather than recomputing the coarsening from scratch at every snapshot, THGC maintains a coarsened hypergraph and repairs it locally as timestamped events arrive. Changed hyperedges mark a dirty region, consisting of the affected coarse nodes and their one-hop coarse neighbors. The algorithm then uses TAPS to score candidate pairs in this region. TAPS combines a recency-weighted Personalized PageRank proximity term, computed on a clique-expansion projection, with a local conductance term. The algorithm greedily contracts at most k disjoint candidate pairs whose scores are at least τ, and performs global resynchronization every k updates.

Critical strengths
  1. The paper's evaluation protocol is stronger than that of most work in this area. Rather than reporting conductance alone, the authors measure the pair-disagreement between the incrementally maintained mapping and full static recomputation, and compare it with the static-vs-static pair-disagreement over the same horizon. This provides a reference scale for what "tracking" means.
  2. The paper reports regimes in which local repair is not advantageous. The bursty-update density sweep shows that the speedup drops from about 50x to less than 2x on NDC-classes as burst density increases. The sliding-window experiment shows that, on tags-math-sx, THGC with resynchronization actually takes longer than full static recomputation. These results are valuable to practitioners.
Critical weaknesses
  1. Structural quality is the paper's main quality claim, but it is unclear which definition of conductance is reported in different places. Some results are also internally inconsistent. Therefore, lower conductance cannot be directly interpreted as better structural preservation.
  • Equation 1 defines normalized conductance as the average of the per-cluster conductances over the k clusters.
  • Appendix J instead computes the total weight of cut hyperedges divided by min(vol(S), vol(V\S)) for a "best bipartition." This is a different metric. Yet the tables and figures are all labeled simply "conductance."
  • On tags-math-sx, TAPS conductance is reported as 0.9142 in Table 10; approximately 0.91, 0.92, and 0.26 under HyperEF, HyperSF, and SHyPar baseline forcing, respectively (Tables 16–18); visibly below 0.1 in Figure 8; and 0.000 in Figure 19.
  • Some of these differences may arise from different baseline-forcing settings, but Figure 8 and Table 18 both report averages across slices under SHyPar forcing and still disagree (approximately 0.07 vs. 0.26). Figure 7 and Table 18 show the same issue on NDC-classes (approximately 0.0036 vs. 0.05).
  • Figure 19 is labeled as using a logarithmic y-axis, yet its ticks are linearly spaced and it includes a bar with value 0.000.
  • Moreover, the compression ratios are not matched across methods: THGC ends with 170 / 176 coarse nodes, whereas periodic recomputation ends with 161 / 144 (Table 5).
  1. Several key claims are contradicted by the paper's own tables.
  • Appendix E claims that THGC's peak resident set size (peak RSS) is "consistently lower than static recomputation across all dataset sizes and temporal horizons." However, Table 5 contradicts this claim: on tags-math-sx, THGC uses 471.3 MB. Recomputation at every update (k=1, which the paper itself uses as an upper-cost reference) uses 399.0 MB. The other recomputation schedules use approximately 195 MB.
  • The caption of Figure 11 claims that the static-to-incremental peak RSS ratio "grows with more slices," but the actual values alternate between approximately 1.2, 2.7, 1.0, 2.4, and 1.1, rather than showing a sustained increase.
  • In the seeded coupling comparison (Table 12), TAPS deviates further from the static-recomputation reference than its own PPR-only ablation. In the tags-math-sx stream regime, TAPS has a deviation of 0.1238±0.0544, compared with only 0.0075±0.0007 for PPR-only; their hyperlink-prediction AUROC values are 0.524 and 0.771, respectively. In the tags-math-sx window regime, their deviations are 0.0907 and 0.0091, respectively. TAPS also performs worse than heavy-edge in both regimes. Given that Table 11 shows that the ranking induced by the blended score on NDC-classes is almost identical to that induced by the cut term (Spearman correlation 0.985), I do not see sufficient evidence that the TAPS coupling score itself constitutes an effective contribution. Thus, the paper's main empirical support comes from the THGC framework rather than TAPS.
Questions for authors
  1. Which conductance formula is used in each table and figure (Equation 1 or the version in Appendix J)? Please explain why Figures 7 and 8 and Table 18 differ under the same SHyPar forcing.

  2. Tables 13–15 report TAPS update times as 0.00 or approximately zero, whereas Table 10 reports 0.973 seconds and 2.051 seconds. Which operations are included in each timing (PPR computation, candidate-pair scoring, contraction, and resynchronization)? Do the "TAPS" columns in Tables 13–15 refer to full TAPS or to the TAPSCSI/TAPS-Lite variant?

  3. The CSI baselines in Appendix J only evaluate the conductance of a fixed mapping M*; Algorithms 2–4 do not perform any incremental update of the mapping. In what sense can these methods be called maintenance baselines? What exactly do the update-time comparisons in Tables 13–15 and Figures 2–5 measure?

  4. Is the 0.000 accuracy reported for THGC on tags-math-sx in Table 5 a genuine evaluation result or a missing value?

  5. In Table 3, the shuffled-order control produces almost the same static-recomputation churn as the original temporal order. How does this support the paper's claim that the static reference partition changes because of the temporal structure of the stream?

  6. Why does the TAPSCSI conductance curve on tags-ask-ubuntu in Figure 6 suddenly drop from approximately 0.76 to 0.45 at slice 15 and then remain flat?

  7. The bounds in Theorem 1, Theorem 2, and Corollary 1 are never instantiated or verified empirically. Could the authors report the empirically measured η_t, ε_t, and ||P(t+1)-P(t)||_1 on any dataset, as well as the fraction of candidate pairs falling within the ambiguity band A_t(η_t)? In addition, Theorem 1 treats C as fixed, but C is defined as the 1-hop coarse neighborhood of the dirty region and therefore changes with each update. Please clarify this point.

1 comment

Dear Reviewer,

Thank you for the detailed audit. The main issue is that the manuscript needs to distinguish its evaluation quantities and execution paths much more clearly; we clarify the intended interpretation below.

Conductance and quality. The paper's primary structural metric is the multiway normalized hypergraph conductance in Eq. (1), namely the average over coarse clusters of cut divided by minimum volume. The maintenance objective is not conductance alone: it is tracking the named static coarsening reference while reporting pair disagreement, static-to-static churn, update time, state size, and downstream checks where available (Section 3). The appendix also contains a fixed-mapping bipartition surrogate used inside structural CSI diagnostics. This is not the multiway value in Eq. (1), and the numerical scales therefore are not intended as interchangeable measurements. We will make that distinction explicit in every caption and display the primary metric with its complete configuration/provenance. The resulting revision will remove any possible ambiguity about which quantity is plotted.

What was timed. The near-zero values in the CSI timing tables are not full-TAPS times. Full temporal TAPS is the PPR-plus-conductance path, whose mean update times are reported separately in Appendix Table 10 (0.973 s and 2.051 s). The CSI suffix denotes a lightweight structural variant, not an incremental implementation of the complete static method; this is stated in the setup but was too easy to miss. We will rename these variants consistently, put the execution path in every caption, and separate full-TAPS timing from lightweight-structural timing.

CSI baselines. Algorithms 2--4 operate on a fixed mapping M⋆M^\star as a controlled structural diagnostic. They are not presented as new incremental implementations of HyperEF, HyperSF, or SHyPar. We will relabel them as fixed-mapping CSI diagnostics and reserve the actual maintenance comparisons for full or periodic static recomputation and local THGC repair.

Temporal order and the moving reference. The shuffled control does not support a claim that temporal ordering is the sole source of movement. Rather, similar static churn under temporal and shuffled order shows that the static reference changes as the evolving snapshot changes in either order. This still rules out the claim that the experiment is merely tracking a fixed reference, but the text will make this narrower interpretation explicit. We will also audit the abrupt trajectory before retaining it, and will report the requested restricted-error/operator, temporal-drift, ηt\eta_t, and ambiguity-band diagnostics for the theoretical regime.

Thank you again. The revision will separate metrics, variants, and timing paths unambiguously, and will make the temporal-tracking and theory evidence easier to audit.

Reviewer_CbM1OpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies temporal hypergraph coarsening and proposes THGC, an incremental framework that maintains a coarsened hypergraph under timestamped structural updates through localized repair rather than repeated full recomputation. THGC identifies dirty regions affected by updates and uses TAPS, which combines temporally weighted Personalized PageRank and conductance, to guide local merge decisions. The paper further provides theoretical analyses of score stability and merge eligibility, and evaluates THGC on multiple temporal hypergraph datasets in terms of runtime, structural fidelity, conductance, memory usage, and downstream tasks.

Critical strengths

1.The paper formulates temporal hypergraph coarsening as an incremental maintenance problem rather than repeatedly applying static coarsening to independent snapshots. Sections 3–5 provide a clear problem formulation and a concrete THGC framework based on dirty-region localization, local repair, and controlled resynchronization. This is a practically relevant direction for evolving hypergraphs where full recomputation can be expensive. 2.The experimental evaluation covers a relatively broad range of update regimes rather than reporting only favorable cases. Sections 8.1–8.5 and the appendix evaluate long-horizon tracking, bursty updates, sliding-window deletions, memory, and downstream preservation. In particular, the paper explicitly identifies regimes where local repair loses its computational advantage and global recomputation becomes preferable, which provides useful insight into the practical operating range of the method.

Critical weaknesses

1.Insufficient novelty positioning and validation. Section 2 does not adequately discuss closely related incremental hypergraph methods such as iHyperG [1]. Moreover, Section 8.5 and Appendix Tables 11–12 show that simpler scoring baselines sometimes outperform TAPS, leaving its independent contribution insufficiently established. 2.Limitations in theoretical guarantees and presentation. Theorem 2 in Section 6.1 relies on restricted spectral approximation and a random-walk operator bound, while Assumptions A4–A5 in Appendix C are not guaranteed by THGC/CSI itself, and the paper does not empirically validate these conditions or the magnitude of (\epsilon_t). Thus, the result is closer to a conditional guarantee than a direct end-to-end guarantee relative to static recomputation. Furthermore, the main text lacks intuitive figures, relying primarily on Table 1 in Section 8.5, which summarizes only two datasets and makes temporal trends, runtime trade-offs, and failure regimes difficult to assess. [1] Lee, W. L., Sarma, A. D., Chang, C., Chang, C. C., & Huang, T. W. (2026). iHyperG: Incremental Hypergraph Partitioning on GPU. In ACM/IEEE Design Automation Conference (DAC).

Questions for authors

1.What are the key differences between THGC and related incremental hypergraph methods such as iHyperG [1]? Does the main novelty of this work lie in maintaining the coarse hypergraph itself, the TAPS score, the local repair mechanism, or the theoretical analysis? 2.In Section 8.5 and Appendix Tables 11–12, PPR-only, conductance-only, or heavy-edge outperforms TAPS on some metrics. Could the authors further explain and experimentally demonstrate what stable and independent benefit is obtained by combining PPR and conductance into TAPS? 3.Theorem 2 relies on Assumptions A4–A5, which are not guaranteed by THGC/CSI itself. Could the authors validate these assumptions in actual THGC runs, for example by reporting (\epsilon_t) or the corresponding spectral/operator approximation error, to clarify when the theoretical guarantees hold in practice? 4.Could the authors add strictly compression-matched main experiments, controlling THGC and the static/periodic baselines to have the same or similar coarse-node ratio at each reporting slice, and then comparing runtime, deviation, and conductance? Appendix Table 10 shows that the coarse ratio of NDC-classes drifts from 0.200 to 0.085, so some of the current efficiency and quality differences may also be affected by different compression levels. [1] Lee, W. L., Sarma, A. D., Chang, C., Chang, C. C., & Huang, T. W. (2026). iHyperG: Incremental Hypergraph Partitioning on GPU. In ACM/IEEE Design Automation Conference (DAC).

1 comment

Dear Reviewer,

Thank you for the careful review. We clarify the relation to incremental hypergraph partitioning, the scope of the theory, and the role of TAPS below.

Relation to iHyperG and novelty. We appreciate this reference and will add iHyperG to the related-work discussion. iHyperG is an incremental GPU k-way hypergraph partitioner for modified circuit hypergraphs: it maintains a delta representation, rebalances partitions, and refines cut-critical vertices. THGC instead studies temporal coarsening maintenance: it maintains a fine-to-coarse map and induced coarse hyperedges/incidence structure under timestamped event streams, uses recency-weighted local repair, and explicitly tracks a moving full-static coarsening reference. The contributions are thus not incrementality in isolation, but this temporal coarsening objective, localized repair/resynchronization mechanism, and the corresponding tracking analysis. We will sharpen this positioning and avoid any wording that could suggest that incremental hypergraph partitioning itself is new.

TAPS ablation. TAPS is not claimed to be a universally best downstream predictor. It is a local structural-maintenance score combining temporally weighted diffusion proximity and a cut signal; the framework itself is not tied to this particular score. The ablations show that the two terms are not redundant: their candidate-pair rank correlation is 0.369 on NDC-classes and -0.190 on tags-math-sx at α=0.5\alpha=0.5 (Appendix Table 11). We will make the claim more precise: the mixture is a motivated repair policy with empirical trade-offs, not a uniform dominance result over PPR-only, cut-only, or heavy-edge repair. We will also add a compression-matched ablation to make that comparison directly interpretable.

Theory. Theorems 1--2 are deliberately conditional. Section 6 states that A4--A5 are conditions on the maintained coarse space, not guarantees supplied by every possible CSI. Under them, Theorem 2 bounds the distortion of the TAPS score; the threshold-margin corollary then shows that only candidates in the ηt\eta_t ambiguity band can change merge eligibility. This is not a theorem that every THGC run exactly equals a fully recomputed static coarsener. We will make that logical boundary more prominent and add empirical diagnostics for the restricted error/operator term, the temporal drift term, and ambiguity-band mass, so that the relevant regime is observable rather than implicit.

Thank you again. In revision, we will add iHyperG, tighten the novelty and TAPS claims, expose the theory diagnostics, and improve the main-text presentation of the temporal maintenance pipeline.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.