Dynamic Hypergraph Analysis Project

A CUDA-based implementation for motif counting in dynamic hypergraphs using Complete Binary Search Trees (CBSTs; ESCHER / ESCHER+) and parallel processing.

Quick Start

# Build all executables (GPU architecture defaults to sm_86)
make all-types            # or: make all-types ARCH=sm_80

# Build and run the test suite (oracles, see "Testing")
make test

# Original demo: 8 random hyperedges, one batch of 2 deletions + 3 insertions
make run

# Synthetic hypergraph: 1M hyperedges, up to 10 vertices each, vertex ids 1..333333,
# three consecutive batches of 50,000 changes (25,000 deletions + 25,000 insertions)
./build/main 1000000 10 1 333333 --batches 3 --batch-size 50000

# Hypergraph from a file (one hyperedge per line, whitespace-separated vertex ids).
# bench/datasets/get_coauth.sh downloads coauth-DBLP and writes data/coauth.hg.
bench/datasets/get_coauth.sh
./build/main --input data/coauth.hg --batches 3 --batch-size 50000 --timing coauth.json

Executables

• build/main - dynamic 30-bin hypergraph motif (h-motif) counting of the triangles of the line graph
• build/type1 - StatHyper type 1: sum_e C(|e|, 3)
• build/type2 - StatHyper type 2: pairs of hyperedges sharing >= 2 vertices, C(a,2)*b*c
• build/type3 - StatHyper type 3: line-graph triangles, x*y*z of the pairwise-only overlaps
• build/coarseTriangle - paper-style coarse counts: inner, outer, hybrid and hyperedge triangles

All executables share the same pipeline (src/driver.cu): load or generate the hypergraph, build the ESCHER structures, compute the full counts, then for each batch subtract the triads that disappear, update the data structures on the GPU and add the triads that appear.

Command line

<exe> <num_hyperedges> <max_vertices_per_hyperedge> <min_vertex_id> <max_vertex_id> [payload_capacity] [alignment=4] [options]
<exe> --input FILE [payload_capacity] [alignment] [options]

payload_capacity is optional (0 = automatic); if given it is the minimum initial payload capacity of the trees updated in place, which grow on demand.

Option	Meaning
--input FILE	read the hypergraph from FILE (one hyperedge per line; vertex ids in 1..2147483646 separated by spaces, tabs or commas; #/% comment lines)
--batches N	number of consecutive update batches (default 1)
--batch-size N	N changes per batch: N/2 deletions + N - N/2 insertions
--deletions N, --insertions N	explicit batch composition (default without batch options: 2 deletions, 3 insertions)
--insert-mode random|sample	inserted hyperedges are fresh random hyperedges (default for synthetic graphs) or copies of live hyperedges (default for --input)
--seed S	seed of the single RNG used for graph generation and all batches (default 1)
--check	after every batch, compare every CBST row with a host model and the incremental counts with a full GPU recount
--reference	also compare the counts with the CPU reference counter (small and medium graphs)
--timing FILE	write stage timings to FILE (.csv or .json)
--verbose	print the original debug output (tree dumps, flattened arrays)

Vertex-indexed structures (V2H, and V2V for coarseTriangle) have one row per id up to the largest vertex id, so their memory grows with the largest id rather than with the number of distinct vertices: relabel sparse vertex ids densely (1..|V|) before loading. A run whose largest vertex id, hyperedge count or insertions per batch need more GPU or host memory than the machine has is rejected at start-up with an error.

Numeric arguments are checked against their ranges (counts are non-negative and fit in 32 bits, vertex ids are in 1..2147483646), and the --timing file must be writable when the run starts.

Deleted hyperedges are chosen uniformly among the live ones. A batch replaces whole hyperedges; an incident-vertex edit is a deletion plus an insertion. Checks exit with status 3 on any mismatch.

The default output is the counts, the per-batch deltas and a timing summary on stderr: update is the paper-timed region per batch (processing the updates, maintaining the hypergraph and updating the counts = subtract + maintain + add). bench/run.sh and bench/summarize.py run and summarize timed benchmarks (see results/README.md).

What is counted (scope)

• main counts the closed hyperedge triads: triangles of the line graph (three pairwise-intersecting hyperedges), classified by the Venn regions of their vertex sets with the 30-bin table of include/motif_table.hpp. Closed triads fall into bins 1-20 and 27-30 (0-based 0-19 and 26-29).
• Open triads are not counted. Bins 21-26 (0-based 20-25) of the table are the triples in which one pair of hyperedges is disjoint; they are never enumerated and always print 0. MoCHy's h-motif definition also includes such open h-motifs; this implementation deliberately covers closed triads only.
• Deltas are exact: a triad changes only if it contains a changed hyperedge, so the delta is minus the old triads containing a deleted hyperedge plus the new triads containing an inserted one, each counted once at its smallest changed member. The same frontier-incident delta is used by every executable (the coarse outer/hybrid vertex triangles use the vertices of the changed hyperedges as the frontier).

Data structures

• H2V (hyperedge -> vertices) and V2H (vertex -> hyperedges) are CBSTs updated in place with the ESCHER operations: delete, best-fit reuse insert (ESCHER+), and fill / unfill of incident entries with degree-binned thread / warp / block kernels.
• H2H (the line graph; and V2V, the pairwise vertex graph, for coarseTriangle) is maintained on the GPU with an exact, out-of-place sorted delta merge after each batch, and its CBST is rebuilt over the merged payload.
• The counting kernels read rows through key-indexed row views built from the CBST nodes (one pass per tree change) and run one thread per oriented wedge.

Testing

make test runs:

• build/cbst_test: CBST construction and BST search for every key, n = 1..1024 and sizes up to 2^24;
• every executable on small and 100K-hyperedge graphs over three consecutive batches of several sizes and shapes with --check --reference, i.e. every CBST row equals the host model, baseline + deltas equals a full GPU recount, and the counts equal the CPU reference counter (utils/reference.cpp);
• a skewed graph and a medium-degree graph whose batches drive the block-level and the warp-level fill / reuse-insert / unfill kernels; the launch counts printed by --check are asserted to be non-zero for the targeted level.

Project Structure

See PROJECT_STRUCTURE.md. The list of fixes and optimizations relative to the original code is in CHANGES.md.

Requirements

• CUDA Toolkit 12.5+ (tested with CUDA 13.1; ARCH must be supported by the toolkit)
• NVIDIA GPU with CUDA support
• g++ with OpenMP
• Thrust library (included with CUDA)

License

This project is part of academic research in hypergraph analysis.