degree matchers

Every matcher walker shows the same bookkeeping.

The algorithms differ in how they choose the next partner, but every panel is driven by the same residual state. The graph shows which edge is being placed, the bars show what each node still needs, and the optional block-budget table shows how much cluster-preserving capacity remains.

The walkers are tied to one shared 20-node deficit. Re-roll the input once, and every algorithm below restarts from the same missing-stub state so the family comparisons are apples-to-apples. A placed edge decrements both endpoint bars; an abandoned stub stays visible as unplaced residual. Captions name the source, the accepted partner, and the ordering rule: id sort, largest residual, weighted draw, or shuffled stub pair.

All families reject self-loops and existing edges. Cluster-preserving twins also reject exhausted block-pair buckets. When no legal partner remains, modern algorithms log the stuck residual; legacy greedy silently drops it.

Where the deficit comes from. Re-roll for a fresh draw.

The deficit drawn here drives every walker on this page. Source: configuration-model pairing on the 20-node fixture's degree sequence, then drop self-loops and parallel edges (the same dedup pass the SBM generator runs). Hubs lose more stubs because collisions scale with degree squared; leaves rarely lose any. Re-roll redraws the shuffle and resets every walker.

Two edgelists in. Top-up edges out.

Two inputs sharing a node set: the current graph and a reference graph. The per-node residual deficit is

The matcher adds edges to drive \(d_u^{\text{out}} \to d_u^{\text{ref}}\). It only adds; never removes. Cluster-preserving steps additionally consume the reference clustering plus a derived per-(block, block) edge budget. Pipelines attach the clustering files automatically when any step in the stack is cluster-preserving.

Step 1. Measure the missing stubs by building residual[u] from degree differences and discarding non-positive entries. Step 2. Choose a source with residual, using the active family's heap, weighted draw, or shuffled stub list. Step 3. Filter legal partners with v != u, residual[v] > 0, and an absent edge key. Step 4. Add the edge and decrement both bars, or move the source's remaining mass into unplaced[u] when no legal partner exists.

Different ways to drain the same deficit pile.

All four families share the same outer loop: pick a node with positive deficit, pick a partner that also still has room and is not already adjacent, add the edge, decrement both. They differ on the picking order, on whether the partner is chosen deterministically or by a weighted random draw, and on what they do when the loop stalls.

Before a matcher compares scores or draws a random number, it applies the same legality screen. This screen is what makes degree matching a simple-graph post-processor rather than a free stub-pairing exercise.

Greedy and true_greedy are deterministic; random_greedy and rewire sample fresh draws per seed. Plain true_greedy is the bare-CLI default; clustered generators (sbm, ec-sbm-v2, ec-sbm-v3) override to cluster_preserving_true_greedy, the practical default whenever a clustering is available.

Each family has a cluster-preserving twin. The twin runs the same outer loop but rejects any candidate whose (block, block) bucket is exhausted. The bucket budget is the per-(block, block) deficit: how many extra edges each (r, s) pair is expected to absorb if the residual stubs paired up uniformly at random. Built once from the reference clustering at frame start; decrements on every accept. Family sections below show each algorithm's walker followed by its twin's walker; the stacking section composes them.

Step 1. Aggregate residual by block, \(\sigma_r = \sum_{u:b_u=r} r_u\), to find where the missing degree mass lives. Step 2. Convert that stub mass into an upper-triangular bpBudget table. Step 3. Gate every accepted edge on that budget, even when the edge is excellent by degree priority. Step 4. Spend exactly one (min(blocks), max(blocks)) key whenever an edge lands.

Computation: total residual stubs in block \(r\) is \(\sigma_r = \sum_{u : b_u = r} r_u\). Expected new-edge count per bp under configuration-model pairing is \(\sigma_r \sigma_s / \sigma_{\text{tot}}\) for \(r \neq s\) and \((\sigma_r(\sigma_r - 1)) / (2\sigma_{\text{tot}})\) for \(r = s\), rounded with a floor of one on any bp the deficit can land in. The pipeline reads its bp budget straight off the reference edgelist on real inputs; this small fixture has no separate reference, so the page estimates the budget from the residual mass.

Take the most-needy node. Drain it against an id-sorted partner list.

Pop the node with the largest deficit. Build its candidate list (every other deficit-positive node that is not already adjacent), sort by id ascending, walk down adding edges until the source is drained or the list runs out. Move on to the next source. Source order, partner sort, and tie-break are fixed; output is deterministic. Stubs left when no partner is available drop without logging (silent gridlock).

Step 1. Freeze the source order from largest initial residual downward. Step 2. For the active source, scan legal partners and sort them by node id rather than current need. Step 3. Add the first legal pairs from that list until the source bar reaches zero or the list runs out. Step 4. If the source still needs degree, legacy greedy abandons those stubs without a warning.

Silent gridlock leaves no log line when stubs drop. The other three families log gridlock as a warning.

cluster-preserving twin

Same outer loop, plus one filter: candidates whose (block, block) bucket is empty drop out of the partner list. Each accepted edge decrements its bucket. Budget exhaustion is amplified by greedy's silent gridlock, so this twin can lose a noticeable number of stubs on inputs whose deficit lands in a few blocks. The walker captions name the bucket touched and the remaining budget.

The bucket gate can make greedy's silent leftovers larger: a source may have degree-positive partners, but none in an unspent block-pair bucket.

Take the most-needy node. Pair it with the partner that itself is most needy.

Same source pick as greedy. Partner choice is the deficit-positive candidate with the largest residual, ties broken by id ascending. Both endpoints' updated residuals go back into the priority order before the next pick. Greedy commits to one source until drained or stuck; true_greedy re-shuffles after every edge, so it always works on the currently neediest pair. On uneven deficits the gap closes with fewer dropped stubs. Gridlock is logged as a warning.

Step 1. Pop the current neediest source from the live residual state. Step 2. Score all legal partners and take the one with the largest current residual, with id as the tie-break. Step 3. Reinsert both endpoints after every edge, because their bars have changed. Step 4. When a source has residual but no legal partner, transfer that mass to unplaced and log gridlock.

cluster-preserving twin

Same priority-driven source and partner picks; the candidate list is filtered to the in-budget pairs first. Gridlock triggers when every remaining candidate's bucket is empty, and is logged. The dynamic re-shuffle saves more stubs than the cluster-preserving greedy does. Whatever the budget gate still refuses can be picked up by chaining a plain pass after this one (see the stack section below).

Budget exhaustion can gridlock a source even when a plain true-greedy partner exists. Chain a plain pass afterward only when degree closure matters more than strict block-budget fidelity.

Pick both endpoints by weighted random draw.

Source and partner are independent weighted draws over current deficits. Useful as a control: running across several seeds reveals which output features come from the input deficit and which come from greedy / true_greedy's tie-break rules. Gridlock is logged. Step count varies between seeds since the order in which nodes get starved shifts.

Step 1. Draw a source by residual weight, so a node with twice the residual has twice the chance of being selected. Step 2. Draw a legal partner by the same residual weighting after legality filters remove impossible choices. Step 3. Use repeated seeds to separate robust closures from deterministic ordering effects. Step 4. If randomness strands a source, log the abandoned mass as gridlock.

cluster-preserving twin

Same weighted source and partner draws; partner draws are restricted to in-budget candidates. Each accept consumes one unit of budget. If the in-budget candidate set is empty for the chosen source, gridlock is logged and the source is abandoned.

Random choices can spend scarce block-pair buckets on low-value pairs before a large residual reaches them. The walker exposes that as seed-dependent gridlock.

Make a stub per missing edge, shuffle, pair adjacent. Repair conflicts.

Configuration-model approach. Each node drops one stub per missing edge into a bag; shuffle, pair adjacent stubs. Self-loops, parallels, and intra-pairing duplicates queue for repair. Repair is 2-opt: pull a random valid edge from the placed pile, try the four endpoint recombinations, accept the swap if any pair of resulting edges is valid; otherwise requeue. Run for a fixed retry budget. Whatever still conflicts at the end is logged and dropped. The shuffle is the only RNG; dense inputs almost always settle on the first pass, hub-heavy inputs walk the queue.

Step 1. Materialize one stub per missing edge, making the remaining degree mass visible as a bag of half-edges. Step 2. Shuffle the bag and pair adjacent stubs for a configuration-model draw over the residual. Step 3. Commit valid pairs and queue self-loops, existing edges, and duplicate proposed edges. Step 4. Repair the queue by 2-opt endpoint swaps until each queued pair becomes legal or the retry budget is exhausted.

cluster-preserving twin

Stubs are partitioned by (block, block) bucket up front and drawn per bucket independently, capped at the bucket budget. The 2-opt repair only swaps endpoints in ways that keep both resulting pairs inside their original buckets.

Same pair distribution as production; specific edges differ because the browser cannot share graph-tool's RNG.

Bucket-preserving 2-opt has fewer legal swaps than plain rewire. It may abandon stubs a plain repair could place, because every replacement edge must stay inside its original block-pair budget.

Gridlock is not a bug. It is the certificate that no legal local move remains.

A residual stub means the target degree still wants an edge. A legal candidate means the simple graph can accept one. Gridlock is the moment those two facts disagree: the source still needs degree, but every possible partner is illegal under the active constraints.

Step 1. The source bar stays red after candidate generation, so the degree target has not been fully satisfied. Step 2. Every potential partner fails a self-loop, existing-edge, zero-residual, or block-budget check. Step 3. The page moves that mass into unplaced[u], then clears residual[u] so active and abandoned residual are visible separately. Step 4. greedy preserves the legacy silent behavior; the other families emit gridlock_logged.

Chain matchers. Each one cleans up what the previous left behind.

Stacks compose any of the eight algorithms in a comma-separated list. Each step runs on the residual the previous step left behind. A single name is a one-step stack. Two-step chains pair a bulk drain with a finishing pass; longer chains compose cluster-preserving and plain passes when both block structure and degree mass matter.

Each step uses its own random seed, derived from the matcher's overall seed, so randomness in one step does not bleed into the priorities of the next. The shared state across steps is the running graph itself plus the deficit dictionary, both updated as edges land. Cluster-preserving steps additionally share the per-(block, block) edge budget, which every cluster-preserving step in the chain decrements; non-cluster-preserving steps ignore the budget entirely. Putting a non-cluster-preserving step after a cluster-preserving one is the way to recover degree mass that the budget gate refused, at the cost of letting that final step place a few edges in buckets the cluster-preserving steps would have refused.

Step 1. Start with the current graph, residual dictionary, unplaced dictionary, and initial block-pair budget. Step 2. Run one matcher to terminal state, not just one edge. Step 3. Pass the final graph, residual, unplaced counts, and budget forward to the next frame. Step 4. Trade fidelity for closure deliberately: gated frames decrement bpBudget, while plain frames ignore it.

Build a stack

Pick algorithms one at a time. Each pick runs on whatever residual the previous picks left behind. back pops the most recent step and reverts its edges + budget. rand step rerolls the top stochastic frame; rand all rerolls every stochastic frame in the stack.

A plain step after a cluster-preserving one trades budget fidelity for residual closure: the new edges land in buckets the gated steps already exhausted, so block-shape stats drift while the degree gap closes. Pick the gated step alone when block fidelity is the priority and the residual stubs are tolerable; chain a plain step at the end when degree exactness matters more.

Pick the matcher off a graph that loses 29% of its edges to dedup.

The dnc network has 1,891 nodes, 5 reference clusters, and 10,429 reference edges. Run the standalone SBM generator with seed 1: graph-tool's stub-pair sampler hits enough collisions on the dense intra-cluster blocks that, after self-loops and duplicates are removed, only 7,438 edges survive. The matcher tops up 2,991 missing edges (a 29% deficit), almost entirely concentrated inside cluster interiors where the parallel-edge collisions cluster.

Four matcher choices, same SBM output, same seed:

Numbers from run_generator.sh --generator sbm on dnc, seed 1, with the four --degree-matcher values. SBM output is identical across all four runs (same graph-tool seed), so the differences are purely matcher behaviour.

Pair by degree rank for gens that emit fresh node IDs.

ABCD, ABCD+o, LFR, and nPSO emit integer node IDs unrelated to the input's. Diffing degrees against input IDs is meaningless. --remap pairs nodes by descending-degree rank: input rank \(i\) maps to output rank \(i\), and the deficit is computed on that pairing. The pairing is L1- and L2-optimal for matching two non-identical degree sequences (rearrangement inequality). The matcher still places edges in the input's ID space; no on-disk re-ID happens.

Cluster-preserving variants compose with --remap via two clustering inputs: --input-clustering labels the input-side blocks, --ref-clustering supplies the per-(block, block) edge budget. In direct mode (shared ID space) the two flags collapse to the same file.

Use --remap whenever the generator's output IDs do not align with the input's. The simple-gen wrappers turn it on by default whenever they enable --match-degree. The SBM family already emits in the input's ID space, so it does not need it.