Mutable structure dependence
The exact baseline keeps correctness by editing the clique tree and the vertex-to-leaf index after every peel step. That couples support maintenance to structural mutation.
Pivoter R1 paper framing
Exact R1 peeling without mutable clique-tree updates.
This page turns the current R1 algorithm into a conference-style paper pitch: the challenge, the new technique stack, the correctness spine, and the evidence that the specialization is both exact and materially faster.
Paper claim
The exact baseline edits the tree to reflect every peel event. This algorithm keeps the tree fixed and moves all dynamics into a compact per-leaf state plus closed-form support deltas.
Technique stack below
6.16xgeometric mean speedup
5.49xmedian speedup over REF_R1
505paired benchmark runs completed
Hero image by Visax on Unsplash
The bottleneck
Why the exact baseline becomes expensive.
The R1 reference path keeps exactness by performing real structural work after each peel batch: sorting removed pivots, editing the vertex-to-leaf index, rewriting the leaf, and deleting dead leaves. That is faithful, but it entangles exact support maintenance with mutable clique-tree updates.
The paper should position the new algorithm as a reframing of that dependency. The win does not come from approximate peeling or relaxed semantics. It comes from recognizing that the tree mutation is stronger than what correctness actually needs.
Batch interaction inside one leaf
A single batch can remove several pivots and several keep vertices that touch the same leaf. The update must stay exact under joint removal, not just under one-vertex-at-a-time reasoning.
Local work without global rescans
If the tree stops mutating, the algorithm still needs a way to touch only affected leaves. Otherwise the win disappears into repeated full scans.
Technique stack
Four moves define the new algorithm.
Technique 01
Immutable leaf state replaces leaf mutation
Each stored leaf keeps only the state that matters for future support: how many pivots remain, how many pivots are needed to reach size s, and whether the leaf is still alive. The clique tree itself stops changing.
leafRemainPivots[L]
leafNeedPivot[L] = s - |keep(L)|
leafAlive[L] in {0, 1}Technique 02
Flat CSR incidence localizes every update
A compact vertex-to-leaf CSR index replaces dynamic hash-style adjacency maintenance. When a batch removes vertices, the algorithm can enumerate exactly the leaves touched by that batch and no others.
vtxLeafOff[v] ... vtxLeafOff[v + 1]
vtxLeafData[pos] = { leafId, isPivot }
affectedLeaves <- union over removed verticesTechnique 03
Closed-form support deltas avoid re-editing the leaf
For every affected leaf, support loss is computed by combinatorial deltas instead of by rebuilding the leaf. The keep and pivot contributions are updated directly from old and new pivot counts.
deltaKeep = C(oldRP, need) - C(newRP, need)
deltaPivot = C(oldRP - 1, need - 1) - C(newRP - 1, need - 1)
dead leaf => remove its full previous contributionTechnique 04
Batch-pop exact peeling stays aligned with REF
The optimized variant still peels the current minimum-support frontier exactly. The priority queue changes and the updates are cheaper, but the peel order invariant and the final core values remain the same.
pop all vertices with support <= current level
aggregate leaf effects once per batch
apply exact deltas, then update the queueClosed-form update
The paper needs these formulas at the center.
State per leaf
oldRP = remaining pivots before the batch
newRP = oldRP - removedPivots
need = s - |keep(L)|
dies = removedKeep || need > newRP || newRP < 0Support loss
if dies:
deltaKeep = C(oldRP, need)
deltaPivot = C(oldRP - 1, need - 1)
else:
deltaKeep = C(oldRP, need) - C(newRP, need)
deltaPivot = C(oldRP - 1, need - 1)
- C(newRP - 1, need - 1)Operational meaning
The new algorithm never edits the leaf and never reconstructs it. It computes exactly how much support disappears from each live vertex and updates the queue once, after the leaf has been summarized.
Correctness spine
Three statements carry the theory.
Sufficient-state lemma
A leaf does not need its explicit pivot subset rewritten after each batch. Future support depends only on the surviving pivot count, the fixed keep set size, the alive flag, and the static incidence list.
Closed-form delta lemma
For both keep vertices and pivot vertices, the support loss caused by a batch is a difference of binomial terms. No re-enumeration of size-s cliques is required.
Batch equivalence theorem
If the batch contains exactly the minimum-support frontier, then the optimized peel assigns the same core values as the reference algorithm. The implementation changes the state representation, not the semantics.
Evidence
The current R1 results are already strong enough to anchor the story.
1.78x to 39.41xMeasured speedup range over REF_R1.
1.03x to 2.21xReference-to-ST memory ratio across matched runs.
High-s advantage grows sharplyThe optimization pays most when support updates become structurally expensive in the baseline.
datasetmedianmaxmem
com-youtube16 matched runs
22.93x
1.79x
web-Stanford60 matched runs
39.41x
1.25x
web-it-2004429 matched runs
28.05x
1.14x
Representative settings
com-youtubes = 2
ST 735.7 msREF 1,347.9 ms
1.83xcom-youtubes = 17
ST 8.682 msREF 195.9 ms
22.57xweb-Stanfords = 2
ST 213.4 msREF 380.9 ms
1.79xweb-Stanfords = 61
ST 1.385 msREF 54.6 ms
39.41xweb-it-2004s = 2
ST 381.3 msREF 679.6 ms
1.78xweb-it-2004s = 430
ST 4.080 msREF 78.6 ms
19.27xWhat the paper should claim
Keep the contribution narrow, exact, and defensible.
A new exact state model for R1 peeling
The paper claims that exact R1 peeling can be reformulated as immutable-state transition rather than dynamic tree editing.
Closed-form support maintenance
The update rule becomes direct arithmetic on combinatorial counts, which is the real source of the algorithmic simplification.
A specialized exact implementation that is measurably stronger
The current results show consistent wins over REF_R1 across all measured pairings, with lower memory footprints and a much larger advantage at high s.
Do say
This is a specialized exact algorithm for R1 nucleus decomposition that replaces dynamic clique-tree mutation with immutable state transitions.
Do not say
This is not yet a universal theory for all r and it is not a claim of a new general asymptotic framework for every nucleus decomposition regime.
Reproducibility snapshot
Ground the page in commands and measured artifacts.
bash benchmark_all.shenv PIVOTER_RUN_ST=1 PIVOTER_COMPARE=1 ./build/bin/degeneracy_cliques graphs/email-Eu-core.edges 1 4env PIVOTER_RUN_ST=1 PIVOTER_COMPARE=1 ./build/bin/degeneracy_cliques graphs/web-Stanford.edges 1 6Server benchmark summary came from the current benchmark_all_results.csv run on tods2 at commit b51f24d. Local exactness checks were re-run with compare mode on small and medium instances before this page was written.