EC-SBM v2

One owner per edge, one repair path per invalid sample.

v2 keeps v1's mincut guarantee but changes the accounting discipline. Each stage receives a residual problem, writes only its own edges, and hands explicit leftovers to the next stage.

Step 1. Profile measures the clustered core. Outliers are excluded while assignment, degree, block counts, and mincut are measured on real clusters; stage 3 later adds OUT back before the residual SBM, so outlier-incident stubs are absent only from the early vectors.

Step 2. Construct only the \(K_{k+1}\) core. The stage spends intra-cluster degree and block budget on required connectivity edges, then attaches later nodes by availability-weighted sampling. --no-sbm-overlay means no second sampler writes into the same cell, though large \(k\) can still overspend a diagonal that residual accounting must clamp later.

Step 3. Fold outliers into one block. The residual stage re-reads the empirical graph, maps nodes 19 and 20 in the shared example into a combined OUT block, and builds the 4x4 ledger. OUT is pooled: individual outlier labels are not a structural target beyond their node degrees.

Step 4. Compute the residual SBM problem. prepare_sbm_inputs subtracts stage-2 edges from node degrees and block counts, recomputes out_degs, fills probs, bumps odd diagonals when graph-tool needs even half-edge mass, and zeroes overspent diagonals because the SBM can only add.

Step 5. Repair invalid residual samples by swapping, not dropping. A loop or duplicate proposal picks a valid edge from the same block-pair bucket and tests the two swapped pairs before committing; if retry limits strand it, v2 drops that edge with a warning.

Step 6. Top up with budget gates. The block-aware true_greedy matcher accepts an edge only if both endpoints have positive deficit, the pair is a non-neighbor, and the relevant block-pair counter still has room. The block gates can gridlock earlier than a global matcher, but the shortfall is logged.

Step 7. Keep provenance visible. Final diagnostics color surviving edge pairs by producing stage, which explains whether a shared dnc edge came from the core, residual SBM, rewire repair, match-degree, or only one version.

Shared input graph: 18 clustered + 2 singletons.

The 20-node synthetic this page builds on, drawn under the shared singleton view: C1 (8), C2 (6), C3 (4), plus outliers 19 + 20 each in their own 1-node cluster. EC-SBM v2 then forces outlier_mode=excluded in the next stage, dropping outliers from the profile-time partition; stage 3 folds them back as a combined block. This view is the universal baseline before either move.

Per-node block label. Outliers excluded now, folded back at stage 3.

Profile writes the same seven CSVs as v1: node_id, cluster_id, assignment, degree, edge_counts, mincut, and com. v2 also forces outlier_mode=excluded, so profile's tables cover only the clustered sub-network. The difference shows up later: at stage 3, v2 re-reads the empirical edgelist and folds every outlier into one combined pseudo-block, while v1 creates one singleton block per outlier.

Step 1. Profile records clustered vertices only. The profile-time assignment has C1, C2, and C3; outliers receive no block id in this pass.

Step 2. Exclusion keeps the mincut promise focused on real clusters. Singleton outliers would only add zero-connectivity rows, so ProfileKernel.runProfile(... outlier_mode: "excluded") writes the profile CSVs first.

Step 3. Stage 3 later re-runs the assignment with combined, mapping every outlier iid to the fourth block before building probs.

In the combined view, nodes 19 and 20 share OUT when residual edges are sampled. That keeps the matrix learnable: outlier-outlier and cluster-outlier relations are represented as counts, not as many sparse singleton cells.

Per-node target degree, post-exclusion.

Same as v1: degree.csv carries \(k_u\) counted on the post-exclusion graph. The constructive phase uses these numbers; stage 3 then bumps per-node out_degs by each node's outlier-incident count after re-reading the original edgelist.

Edge count per block pair. 3x3 now, 4x4 at stage 3.

Same half-edge convention as v1 / SBM:

At profile time v2's matrix is the same compact 3x3 as v1 (outliers excluded). Stage 3 then rebuilds a 4x4 by re-reading the original edgelist and adding the combined outlier block on the fourth row/column.

One new scalar per cluster: \(k(C)\).

Same profile addition as v1. mincut.csv records the minimum edge cut of each cluster's induced subgraph in the input, measured via pymincut's Nagamochi-Ono-Ibaraki algorithm with a bucket-queue heap. Singleton clusters get \(k = 0\).

Each cluster's mincut on this synthetic, highlighted in red-dashed on the graph below. C1 has a non-trivial internal cut: two subsets of 4 nodes joined by a thin bridge of 2 edges. C2 and C3 isolate a single low-degree vertex.

Same \(K_{k+1}\) seed as v1. Nothing else samples here.

Stage 2 calls exactly the same gen_kec_core.generate_cluster as v1, with one change: v2 passes --no-sbm-overlay, so the constructive pass ends with the cores + attach-by-availability and nothing more. No gt.generate_sbm here, no overlay, no dedup. probs and deg carry exactly the budget the construction used.

The walker below follows the current gen_kec_core rule: sort each cluster by residual degree, form the first \(K_{k+1}\) by connecting each phase-1 arrival to all processed predecessors, then attach each later node to \(k\) distinct processed nodes with sample_by_availability. That sampler is weighted without replacement over positive residual int_deg values; only if fewer than \(k\) candidates have positive availability does it fill the rest uniformly from exhausted candidates. random step re-samples the current attach draw only; random all re-samples every attach draw.

Step 1. Guarantee first. Each cluster gets a \(K_{k+1}\) seed plus \(k\) edges from every later vertex back into the processed set.

Step 2. Sample by availability because residual degree is capacity. Nodes with more remaining int_deg are more likely partners, but no partner can be selected twice for the same arrival.

Step 3. np.random.choice(... replace=False, p=availability/sum) draws the positive-availability partners. ensure_edge_capacity inflates degree and block budget before any mandatory edge that would underflow.

Compute what the SBM still owes each block.

Before the SBM call, prepare_sbm_inputs re-reads the original edgelist and rebuilds out_degs + probs on all four blocks (three real clusters + one combined outlier block). It subtracts the constructive contribution from out_degs and populates probs inter-cells from the original edge list. Finally it reconciles each diagonal against the block's residual stub budget:

Step 1. Reconcile node deficits and block-pair counts. Stage 2 already spent some stubs, so the SBM receives only the remaining half-edges and cells.

Step 2. Do this before the SBM so one sampler owns the residual. Without the ledger, a later sampler can place an edge the core already owns and dedup would erase budget silently.

Step 3. prepare_sbm_inputs computes \(D_k\), subtracts inter-block commitments, writes the diagonal residual, and applies the even-parity bump if required.

\(D_k\) is "residual half-edges block \(k\) still owes", \(E^{\text{inter}}_k\) is "inter-block half-edges block \(k\) is already committed to". The intra-block budget the SBM still needs to sample is

If \(\text{diff}_k \ge 0\), set \(\texttt{probs}[k, k] = \text{diff}_k\) (bump by 1 if odd, to satisfy graph-tool's even-half-edges-per-block rule, and add the bump back to one node's out_degs). If \(\text{diff}_k < 0\), the construction already over-spent the block's out-budget; add \(|\text{diff}_k|\) back to out_degs and set \(\texttt{probs}[k, k] = 0\) (the SBM can only add, never subtract).

On the synthetic, after the verified stage 2 run, the residual looks like:

C1 has already spent its full intra budget during construction, so the SBM sees 0 intra residual there. C2, C3, and OUT each still owe 2 half-edges (one intra edge per block). All four diffs are even on this synthetic, so no parity bump fires; the bump path triggers only on odd diffs (e.g. when an outlier-incident OO edge mismatches block-pair parity).

One SBM call. Block-preserving swaps repair invalid edges without losing the block count.

With the residual probs, out_degs, and the combined-outlier block assignment ready, v2 calls gt.generate_sbm(b, probs, out_degs, micro_ers=True, micro_degs=True) once. The sampler can still emit self-loops (two of a node's stubs pair together) and parallel edges (the same pair drawn twice). v1 dedupped both and accepted the degree loss. v2 tries to fix each one via a block-preserving 2-opt swap.

The swap: bucket every valid edge by its unordered block-pair \((A, B)\); for each invalid edge, pick a random valid edge in the same bucket and swap endpoints so each node stays in its home block. That preserves both the block-pair count and every node's block membership. Up to 10 retry passes with a stagnation detector. Edges still invalid after that are dropped with a WARN.

Step 1. The SBM proposes a residual multigraph. The sample matches the residual degree and block matrix in expectation, but it may include loops or duplicate pairs.

Step 2. Rewire instead of dedup because a duplicate still consumed one block-pair draw. Swapping tries to keep that draw alive as a simple edge.

Step 3. rewireInvalidEdges queues invalid edges, samples a same-bucket partner, tests the two swapped edges, and commits only if both are simple.

Step through; hit random to resample stage 3.

Block-aware top-up by default. Logs gridlock; does not silently drop.

After the residual SBM + rewire, some nodes may still be short of their target. v2 hands the leftovers to a block-aware top-up that spends edges out of a per-block-pair budget read from the reference clustering, rather than letting stubs leak across cluster boundaries. Anything still unplaced is logged, never silently dropped the way v1's plain greedy does. The viz below runs the simpler global sibling so the heap mechanics stay readable; see the degree matcher page for the full menu.

Step 1. true_greedy always tries the largest deficits first. A dynamic heap repeatedly picks the node with the most remaining stubs and pairs it with the best valid partner.

Step 2. The block gates keep degree repair from rewriting communities. The cluster-preserving version rejects any candidate edge whose block-pair budget is already full.

Step 3. The production default is block-aware true_greedy: candidate edges must be non-neighbors, consume positive deficits, and pass the per-block-pair counter before acceptance.

Toggle apply match_degree to watch the per-node deficit pile shrink. Click random for a different realization.

What you get on the shipped example.

Default run on dnc + sbm-flat-best+cc at seed 1, with the residual-SBM rewire and the block-aware top-up:

v1 and v2 share the same \(K_{k+1}\) cores edge-for-edge; everything else gets reshuffled. The flow chart below pairs each edge with the stage that placed it on each side.

Step 1. Provenance records stage ownership per edge: every final edge is tagged as core, residual SBM, or match-degree, and one-sided edges become marginals.

Step 2. This matters because metrics alone hide mechanisms. The same edge count can come from preserved core edges, repaired SBM edges, or late degree top-up.

Step 3. Read the ribbons from the v1 stage that owned an edge to the v2 stage that owns the same pair; bottom segments are edges present in only one version.