PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Jingbang Chen, Chenhao Ma, Yingli Zhou

arXiv:2609.39778v1cs.DB

TL;DR

CAP addresses the cost of maintaining dense groups as hyperedges are inserted and deleted by retaining a candidate and an endpoint allocation, repairing only when their bounds no longer certify the approximation. It reports speedups of up to approximately 5.9 × 10^3 over evaluated dynamic hypergraph baselines and approximately 64× against specialized dynamic graph methods on tested workloads.

  • Problem

    Maintaining a dense group as hypergraph interactions are added or removed can require frequent, expensive changes to the underlying representation.

    Source: §1 · p. 1

  • Method

    CAP maintains a candidate set and endpoint allocation whose lower and upper density bounds guide whether local repair is needed after an update.

    Source: §1 · p. 1, §3.3 · p. 3

  • Results

    Up to approximately 5.9 × 10^3 speedup over dynamic hypergraph baselines and approximately 64× over specialized graph methods are reported.

    Source: §1 · p. 2

  • Takeaways & Limitations

    CAP’s useful regime is described by certificate slack, deletion-induced scale loss, and positive residual support; static recomputation remains competitive at fine precision on smaller streams.

    Source: §7 · p. 13

    The stated dynamic setting assumes a fixed vertex universe and legal hyperedge insertions and deletions.

    Source: §3.2 · p. 3

Abstract

from arXiv · show

Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+\epsilon)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads.

1 Introduction

The introduction motivates maintaining dense groups as hypergraph interactions change, then presents CAP’s candidate-guided allocation repair and analysis of when local maintenance is inexpensive. It reports speedups over dynamic hypergraph baselines and competitive performance against specialized graph methods.

1 Introduction

  • Hyperedges preserve group interactions that pairwise links can lose, and densest-subhypergraph methods seek groups containing many fully contained interactions.The motivation includes applications in collaboration, online activity, biology, and information systems.Source: §1 · p. 1
  • CAP maintains an explicit (1 + ε)-approximate densest subhypergraph after each insertion or deletion, using the candidate’s density to decide when allocation repair is needed.The candidate supplies a lower bound on optimum density, while endpoint allocation supplies an upper bound; local search redistributes load or finds a denser candidate.Source: §1 · p. 1
  • Maintenance can be inexpensive when searches reach only small high-load regions and the maintained solution loses only a small fraction of its density.The analysis relates search cost to the searched region and repair to density changes.Source: §1 · pp. 1–2
  • Up to approximately 5.9 × 10^3 speedup over dynamic hypergraph baselines and approximately 64× over specialized graph methods are reported.The hypergraph comparison covers completed comparisons; the graph result is on tested workloads.Source: §1 · p. 2

2 Related Work

Prior work addresses static densest-subhypergraph formulations and dynamic maintenance through orientations, allocations, decompositions, or retained dense sets. CAP distinguishes itself by maintaining an explicit approximate global solution and using its density to control allocation changes.

Densest-subgraph discovery

  • Densest-subgraph research spans peeling, core pruning, convex and spectral methods, local algorithms, and constrained or directed variants.The cited work also studies clique-based objectives and indexing multiple densest solutions.Source: §2 · p. 2

Densest subhypergraphs

  • Static hypergraph solvers address fully contained-edge density and can answer dynamic queries by recomputing on each snapshot, but do not reuse allocation across updates.Prior approaches include peeling, flow, localized methods, and exact global solvers.Source: §2 · p. 2

Dynamic densest subhypergraphs

  • CAP maintains an explicit approximate global solution and uses its density to govern endpoint-allocation changes, unlike dynamic methods that maintain density layers or local conditions.The related work notes that reusing useful solutions is established prior work; CAP’s policy uses solution density to control persistent allocation repair.Source: §2 · p. 2

3 Preliminaries

The preliminaries define the dynamic density objective and the primal–dual allocation certificate used by CAP. They then introduce integer endpoint shares and residual paths as allocation-maintenance tools.

3.1 Hypergraphs and Density

  • A hypergraph consists of vertices and hyperedges that may contain more than two vertices; the density counts edges only when all endpoints lie in the selected set.The model allows singleton and parallel hyperedges, which have distinct identifiers and count separately.Source: §3.1 · pp. 2–3

3.2 Problem Specification

  • The dynamic problem is to maintain a vertex set whose density is at least ρ*/(1 + ε) after every update, with queries returning that set and its density.The setting uses a fixed vertex universe and legal hyperedge insertions and deletions.Source: §3.2 · p. 3

3.3 Linear Programming Formulation

  • A feasible fractional orientation assigns each hyperedge’s unit contribution among its endpoints, and its maximum vertex load upper-bounds optimal density.By strong duality, the minimum possible maximum load over fractional orientations equals ρ*; an induced set gives a lower bound.Source: §3.3 · p. 3

3.4 Allocation Bounds and Residual Paths

  • Integer endpoint shares encode fractional allocations as counters, and any feasible allocation gives an upper bound U on ρ*.The maintained witness has density L, and U ≤ (1 + ε)L certifies the required approximation.Source: §3.4 · p. 3, §3.2 · p. 3
  • A residual path transfers shares between endpoints while preserving each edge’s total allocation; intermediate vertex loads remain unchanged.In the illustrated two-edge path, one share changes loads from (16, 15, 14) to (15, 15, 15).Source: §3.4 · p. 4, Figure 1 · p. 4

4 Witness-Guided Dynamic Maintenance

CAP uses the maintained witness density to decide whether endpoint allocations need repair, then either redistributes load locally or improves the witness. Its repair procedure terminates after every legal update with an explicit (1 + 𝜖)-approximation certificate.

4 Witness-Guided Dynamic Maintenance

  • The witness density sets an outer capacity 𝑐 and a lower inner threshold 𝑡, which reserve destinations for load transfers.A search seeks a destination below 𝑡, while a transfer may raise its load as high as 𝑐.Source: §4 · p. 4
  • CAP maintains a witness as a lower bound and an endpoint allocation as an upper bound, repairing only when their gap cannot certify the requested accuracy.Queries return the maintained witness directly.Source: §4 · p. 4

4.2 Processing Insertions and Deletions

  • An update adjusts the inserted or deleted edge's endpoint shares, then enters repair only if the maximum load exceeds the witness-based capacity.Insertion uses discrete water filling; deleting an edge outside the witness leaves its density unchanged and needs no repair.Source: §4.2.1 · p. 4, §4.2.2 · p. 5

4.3 Residual Search

  • From an overloaded vertex, residual search finds a path to a lower-load destination or returns the reached set when no such destination exists.The path supports a load transfer; a failed search provides a replacement witness.Source: §4.2.3 · p. 5, §4.3.1 · p. 6

4.3.2 Effectiveness Analysis

  • Successful transfers reduce excess load, whereas failed searches improve the witness density and strictly raise the inner threshold.The improved witness also yields its induced-edge count from the reached-set load sum, without a separate containment scan.Source: §4.3.2 · p. 6

4.3.3 Time Analysis

  • A single residual search takes 𝑂(1 + 𝑃+ 𝐽) time, with 𝑃 and 𝐽 counting inspected incidences and endpoints; both are at most the current incidence volume 𝐼.Thus one search has an 𝑂(1 + 𝐼) worst-case bound; the analysis also bounds failed searches during an update.Source: §4.3.3 · p. 6

4.4 Maintaining and Refreshing the Witness

  • Normalization ensures a minimum witness density, and at most one budgeted peeling refresh per update can install a denser witness without lowering capacity.Refresh is triggered when accumulated positive scans exceed 4(𝑛+ 𝑟𝑚).Source: §4.4 · p. 7, §4.4.1 · p. 7, §4.4.2 · p. 7

4.5 Correctness

  • For 0 < 𝜖≤1 and 𝑏≥⌈2𝑟/𝜖⌉, every legal update terminates with a set 𝐶 satisfying 𝜌(𝐶) ≤𝜌∗≤𝑈≤(1 + 𝜖)𝜌(𝐶).The returned bounds certify the maintained witness's approximation.Source: §4.2.4 · p. 5, §4.5 · p. 7

5 Analysis of Solution-Guided Maintenance

CAP’s analysis bounds maintenance by the work of local searches and the repair they require, rather than charging every update for the whole hypergraph. It identifies small high-load regions and limited density losses as conditions for inexpensive repair.

5 Analysis of Solution-Guided Maintenance

  • CAP maintains a set of density at least ρ*/(1 + ε) after every update, while its maintenance analysis counts update, search, and fallback-normalization work.Reading the maintained density takes O(1) time; reporting its vertices takes Θ(1 + |C|) per query.Source: §5 · p. 7
  • The analysis also bounds compacted storage by O(n + I) words and gives O(1) density queries and Θ(1 + |C|) vertex reporting.Here I is the current incidence volume.Source: §5 · pp. 7–8

5.1 Bounding Search Work by Locality

  • A small high-load region limits the work of each search, and the total bound depends on the number of searches and transported load.Only vertices reaching the destination threshold are expanded; large crossing edges need only be scanned up to the first eligible destination.Source: §5.1 · p. 8

5.2 Bounding Transport by Density Changes

  • Insertions transport load according to new mass, while deletion-related transport is bounded by density loss and the load exposed to the lowered threshold.Deleting an edge outside the maintained solution gives zero exposure; losing one edge from a 100-edge solution incurs at most a 1/99 relative-scale charge.Source: §5.2 · p. 8

5.3 From Repair Work to Running Time

  • The combined running-time bound consists of updated-edge work, local search work, and fallback-normalization cost, with the latter depending on how often fallback occurs.Failed searches raise the inner threshold by at least a factor of 1 + ε/4, and an edge deletion outside the witness can finish without search or normalization.Source: §5.3 · p. 9

6 Evaluation

The evaluation tests CAP’s running time, solution quality, and scalability on real-world hypergraphs and ordinary graph streams. It also examines accuracy, repair design, and performance against dynamic and static baselines.

6.1 Experiment Setting

  • The evaluation uses five real-world hypergraphs and six graph streams, with calendar-based query schedules and dynamic and exact snapshot baselines.Experiments use three independently validated repetitions and report mean total running times.Source: §6.1 · pp. 9–10

6.2 Efficiency on Dynamic Hypergraphs

  • CAP has the lowest running time in all 25 settings, meeting the requested approximation and achieving up to 5926.6× speedups over completed dynamic-baseline comparisons.At epsilon=0.1, it is also 3.4–259.6× faster than DI and 5.4–246.9× faster than ExactFlow.Source: §6.2 · p. 10, Table 2 · p. 11

6.3 Quality Validation

  • Across tested datasets and accuracy settings, CAP’s minimum density ratio meets 1/(1 + epsilon), including between scheduled queries; completed CQ runs also meet their requested ratio.The validation compares returned densities with exact snapshot optima.Source: Table 3 · p. 11, §6.3 · p. 11

6.4 Scalability with Query Frequency

  • A sixteenfold increase in query frequency leaves CAP’s running time almost unchanged on DW and GE; with 512 DW queries, it is 551.9× faster than Udshp.With a size-only query after every update, the 15.9-million-update SO stream takes 37.27 seconds at epsilon=0.1 and 1586.63 seconds at epsilon=0.01.Source: Table 4 · p. 11, §6.4 · pp. 11–12, Table 5 · p. 11

6.5 Scalability with Data Size

  • On SO, the full stream completes in 36.44 seconds; from 20% to 100% vertex retention, updates grow 96.2× while running time grows 38.7×.Vertex-induced sampling changes both the edge set and its rank distribution, so the horizontal axis is a sampling fraction, not direct input volume.Source: Figure 2 · p. 12, §6.5 · p. 12

6.6 Effect of the Accuracy Parameter

  • On GE, tightening epsilon by two orders raises CAP’s time 2.6×; at epsilon=0.01 it finishes in 6.36 seconds, 151.0× and 143.5× faster than DI and ExactFlow.This advantage is dataset-dependent: at epsilon=0.01, DI is faster on DW, MA, and AU, while ExactFlow is faster on MA and AU.Source: Figure 3 · p. 12, §6.6 · p. 12

6.7 Ablation Study

  • With the larger outer capacity and reserve destinations, CAP is 2.0–57.9× faster and uses 3.6–158.0× fewer positive-incidence scans where both variants complete.CAP-Tight exceeds 300 seconds on SO, while CAP completes.Source: Figure 4 · p. 12, §6.7 · p. 12

6.8 Results on Ordinary Graphs

  • On ordinary graphs, CAP is 1.4–63.8× faster than INS/DEL on all six streams and 2.2–29.3× faster than ImprovedDynOpt on four, which is modestly faster on AS and SW.Table 6 reports average total running time in seconds.Source: §6.8 · pp. 12–13, Table 6 · p. 13

7 Conclusion

CAP uses witness-conditioned repair to maintain a certified dense set on graphs and hypergraphs. Its useful regime depends on certificate slack, deletion-induced scale loss, and positive residual support; experiments also show substantial running-time savings on evaluated hypergraphs.

7 Conclusion

  • CAP’s witness-conditioned repair provides a unified way to maintain a certified dense set on graphs and hypergraphs.The method combines larger outer capacity with reserve destinations, reducing repair work on the evaluated hypergraphs.Source: §7 · p. 13
  • The useful regime is characterized by certificate slack, actual deletion-induced scale loss, and positive residual support.Source: §7 · p. 13
  • Native-parameter experiments show substantial running-time savings over the released hypergraph implementation on evaluated sources, while static recomputation remains competitive at fine precision on smaller streams.Source: §7 · p. 13
  • The ablation study finds that larger outer capacity combined with reserve destinations reduces repair work on the evaluated hypergraphs.Source: §7 · p. 13

AI Acknowledgment

The authors acknowledge OpenAI GPT Astra’s assistance across literature search, algorithm and proof development, implementation, experiments, analysis, and drafting. They take responsibility for the paper’s claims, results, and other content.

AI Acknowledgment

  • OpenAI GPT Astra assisted with literature search, algorithm and proof development, implementation, experimental orchestration, analysis, and manuscript drafting.Source: AI Acknowledgment · p. 13
  • The authors take full responsibility for the mathematical claims, proofs, experimental results, and all other paper content.Source: AI Acknowledgment · p. 13
  • The acknowledgment does not attribute correctness responsibility to the tool; the authors retain it for the paper’s content.Source: AI Acknowledgment · p. 13

A Transport Bounds and Supporting Derivations

The appendix collects supporting derivations for the search-work and transport bounds, along with update-charge inequalities and a degree-tail bound.

A Transport Bounds and Supporting Derivations

A.1 Proof of the Local Search-Work Bound

The appendix bounds local-search work by the load in the high-load region and relates transport repairs to decreases in a potential. It also establishes that increasing the witness scale with fixed allocation cannot increase that potential.

A.1 Proof of the Local Search-Work Bound

  • For a search, inspected positive incidences are bounded by hQ, and expanded edges by the number of inspected incidences; successful searches are bounded by transported integer amount A.The argument uses the high-load set H of size at most h, with each vertex load at least t.Source: §A.1 · p. 15

A.2.1 Potential Decrease under a Transfer.

  • A shifted, quadratic load potential decreases by at least δa for a successful reserve transfer of amount a, enabling repair sequences to be charged to potential introduced by updates.The potential charges loads above βs−1; an eligible destination contributes zero before transfer.Source: §A.2.1 · p. 15
  • With allocation fixed, increasing witness scale s cannot increase the shifted potential, including when a coordinate becomes inactive.The appendix also establishes bounds for stable loads under the chosen scale and precision parameters.Source: §A.2.1 · p. 15

A.2.3 Single-Update Charges.

The analysis charges repair work to insertion mass, deletion exposure, and changes in stable potential, then telescopes these charges across updates. It also gives a transport guarantee when the degree tail near the repair threshold is small.

A.2.3 Single-Update Charges.

  • Insertions transport at most b units and increase stable potential by at most 2δb.The insertion transport bound is independent of the number of other edges in the graph.Source: §A.2.3 · p. 15
  • Deletion repair is charged to new exposure bZ_d and a decrease in stored potential, allowing potential changes to cancel across consecutive updates.The exposure charge bounds the increase caused by lowering the scale after a deletion.Source: §A.2.3 · p. 16, §A.2.4 · p. 16

A.3 Boundary States and Witness Destruction

  • Summing update charges from an empty start cancels intermediate potentials and retains the initial and final stable-state potentials in the transport bound.The boundary-state bound applies to every finite prefix of the update sequence when b ≥ ⌈2r/ε⌉ and 0 < ε ≤ 1.Source: §A.3 · pp. 16–17
  • In an r-uniform hypergraph, deleting the sole induced edge of a normalized witness contributes zero exposure.A one-edge normalized witness has size r and density 1/r; any surviving edge supplies at least that density.Source: §A.3 · pp. 16–17

A.4 A Degree-Tail Specialization

  • When each internal deletion has a degree tail |H_d| ≤ η|C_d|, transport is O((r/ε)N+ + (rη/ε^2)N−) for an empty start and b = Θ(r/ε).η is the relevant degree-tail size relative to the witness; the condition need not follow from a fitted power-law exponent, and the bound covers transport rather than all search and endpoint costs.Source: §A.4 · p. 17

B Search Counts and Complete Time Accounting

The section bounds search counts and accounts for update time by separating transport, search exploration, fallback work, heap maintenance, and peeling. Its guarantees depend on bounds for high-load regions and the update sequence.

Search counts

  • If every search reaches a high-load region of at most h vertices, transport and failed-search counts can be bounded using insertion mass, capacity decreases, and threshold progress.Successful transport on deletions is charged to the high-load region and the capacity decrease; failed searches increase the threshold, with deletions the updates that can require repeating that progress.Source: B Search Counts and Complete Time… · pp. 17–18

Complete time accounting

  • The detailed time accounting separates edge updates, search inspections, fallbacks and heap changes, receiving-share lookup, and peeling.The stated accounting assumes compact or preallocated edge identifiers.Source: B Search Counts and Complete Time… · p. 18
  • Updating an edge of size s_e costs O(s_e log(r + 1) + s_e log(b + 1) + s_e log(n + 1)) for sorting and slot lookup, discrete water filling, and heap changes.Summing edge sizes gives the R_up term; endpoint-share changes use inverse positions and amortized constant time apart from slot lookup.Source: B Search Counts and Complete Time… · p. 18
  • Search exploration is charged to inspected incidences and endpoints; a successful path changes only two heap keys, while fallback and peeling passes supply witnesses.Peeling scans are charged to disjoint debt intervals, and query materialization costs Θ(1 + |C|) per reported set.Source: B Search Counts and Complete Time… · p. 18
  • From an empty start, substituting scan and update bounds yields Equation (7), including peeling; the approximation follows from Theorem 4.3 and the stored density and witness support the stated query costs.The coarse search bound charges at most 2I* inspections per search, while failed searches grow the threshold geometrically.Source: B Search Counts and Complete Time… · p. 19

C CQ Reconstruction and Evaluation Protocol

The section describes how the CQ baseline is reconstructed and how reported results are admitted. It also distinguishes that implementation from the original algorithm's guarantees.

C CQ Reconstruction and Evaluation Protocol

  • The CQ baseline reconstructs a graph-core, nested label buckets, and shared-copy representation, with each logical update executing K unit-copy operations.Copies with the same hyperedge and head share multiplicity and endpoint labels; the implementation uses no bulk transfers or empirically tuned copy counts.Source: C CQ Reconstruction and Evaluation… · p. 19
  • The hypergraph deletion worklist is a completion of the preliminary description, but general termination and the original amortized update-time bound are not established.The implementation also omits the deamortized or full worst-case construction.Source: C CQ Reconstruction and Evaluation… · p. 19
  • A CQ mean is reported only after three complete repetitions process the full update stream and scheduled queries, with independent replay checking returned densities against exact snapshot optima.The 1,800-second wall limit includes input loading, invariant checks, and allocation output, which are excluded from running time.Source: C CQ Reconstruction and Evaluation… · p. 19
Loading 2609.39778v1…