PaperlayerView exact revision on arXiv

Source-linked AI summary

The Statistical Cost of Causal Discovery with Feedback

Sunmin Oh, Seungsu Han, Gunwoong Park

arXiv:2609.34050v1stat.MLcs.LG

TL;DR

Exact condensation recovery in cyclic LiNG models requires identifying the SCC partition and all edges between components, but its unavoidable sample costs had not been established. The paper derives separate lower bounds and characterizes recovery through block exogeneity and sparse adjustment; BlockExo attains a structurally matching sample bound under suitable conditions. The bounds distinguish the costs of SCC membership and external-parent selection.

  • Problem

    The paper asks which sample costs are unavoidable for exact condensation recovery in cyclic LiNG models, a target comprising the SCC partition and all edges between components.

    Source: §1 · p. 1

  • Method

    The paper proves lower bounds and develops block-exogeneity and sparse-adjustment characterizations that underpin BlockExo.

    Source: §1 · pp. 1–2

  • Results

    The necessary sample cost is of order smax log(ep/smax) + dB log(ep/dB), and BlockExo attains a structurally matching bound without knowing smax or dB under suitable conditions.

    Source: §1 · pp. 1–2, §7 · p. 9

  • Takeaways & Limitations

    The lower and achievable costs provide a concrete target for the design and analysis of exact condensation recovery methods.

    Source: §7 · p. 9

    The separation margins’ dependence on graph structure, coefficients, and noise distributions remains to be characterized.

    Source: §7 · p. 9

Abstract

from arXiv · show

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For $p$ variables, maximum SCC size $s_{\max}$, and maximum external-parent count $d_B$, any estimator requires order $s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B)$ samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing $s_{\max}$ or $d_B$ under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.

1 INTRODUCTION

The paper asks which sample costs are unavoidable for exact condensation recovery in cyclic LiNG models and which population principles support recovery. It establishes separate lower bounds and develops block-exogeneity and sparse-adjustment characterizations that yield BlockExo.

1 INTRODUCTION

  • Earlier approaches include GroupLiNGAM’s exogenous-set characterization under correlation faithfulness and Coarsening’s finite-sample guarantee for exact condensation recovery.The paper also situates its work alongside structural sample-cost results for LiNGAMs and distributional-equivalence characterizations; Appendix A gives detailed comparisons.Source: §1 · p. 2
  • The first lower bounds separate the unavoidable costs of identifying SCC membership and selecting external parents in exact condensation recovery.They are established over regular model classes.Source: §1 · p. 2
  • Under principal invertibility, residual independence and inclusion minimality identify root SCCs without correlation faithfulness.The characterization identifies ancestral blocks through residual independence.Source: §1 · pp. 1–2
  • Small adjustment sets identify ancestral blocks and their external parents; BlockExo achieves a structurally matching sample bound without knowing smax or dB under suitable conditions.The paper also establishes minimax optimality on a separated model class for fixed structural bounds.Source: §1 · p. 2

2 MODEL AND CONDENSATION RECOVERY TARGET

The paper studies cyclic LiNG models with independent non-Gaussian disturbances and defines exact condensation recovery as recovering the SCC partition and all edges between components. It specifies model regularity and structural parameters for the recovery problem.

2 MODEL AND CONDENSATION RECOVERY TARGET

  • The model assumes mutually independent, centered disturbances with positive finite variances, at most one Gaussian coordinate, and principal invertibility of I − B.The paper notes that principal invertibility is automatic for DAGs and follows from absolute stability.Source: §2 · p. 2
  • Exact condensation recovery requires the SCC partition and every direct edge between components, and the target is invariant across the relevant observational equivalence class.For a DAG, where every SCC is a singleton, this is equivalent to graph recovery.Source: §2 · p. 2
  • The structural parameters are maximum SCC size smax and maximum external-parent count dB, counting distinct parent variables regardless of their number of edges or parent SCC.For DAGs, smax = 1 and dB is the maximum indegree.Source: §2 · p. 3
  • The sample-complexity analysis assumes sub-Gaussianity and covariance eigenvalues bounded above and away from zero by constants independent of p, smax, and dB.The stated regularity condition bounds the covariance eigenvalues between λ^-1 and λ.Source: §2 · p. 3

3 NECESSARY STRUCTURAL SAMPLE COSTS

The section establishes separate information-theoretic lower bounds for recovering SCC membership and selecting external parents. Its constructions vary these targets separately, and the bounds identify costs that remain in edge-free condensations and DAGs.

3 NECESSARY STRUCTURAL SAMPLE COSTS

  • The lower bounds distinguish SCC-partition recovery from external-parent identification and are stated over cyclic LiNG model classes with bounded structural parameters.The class is defined using principal invertibility and regularity assumptions, with smax ≤ s and dB ≤ d.Source: §3 · p. 3
  • The SCC-membership cost remains even when the condensation has no edges, while parent-selection cost arises even on DAGs with singleton SCCs.When sample size meets the stated lower-bound threshold, no estimator achieves worst-case error probability below δ.Source: §3 · p. 3
  • Figure 1 separates the lower-bound constructions: panel (a) varies SCC membership, while panel (b) varies parent selection with the SCC partition fixed.Both constructions scale connections to limit the information provided by each observation, yielding costs through Fano’s inequality.Source: Figure 1 · p. 3, §3 · p. 3

4 POPULATION PRINCIPLES FOR EXACT CONDENSATION RECOVERY

The section characterizes root SCCs through block residual independence and inclusion minimality, then shows that sparse adjustments identify SCCs and their external parents. These population principles yield an exact sequential recovery procedure.

4.1 BLOCK EXOGENEITY AND UNKNOWN ROOT SCCS

  • The inclusion-minimal nonempty blocks satisfying the residual-independence condition are exactly the root SCCs in the remaining graph.A root SCC may be distinguished from larger ancestral sets by inclusion minimality.Source: §4.1 · pp. 4–5
  • Under principal invertibility, block exogeneity characterizes ancestral blocks by residual independence, and scalar independence tests suffice without correlation faithfulness.The result applies after adjustment for an already recovered ancestral set.Source: §4.1 · pp. 4–5

4.2 SPARSE ADJUSTMENT AND EXTERNAL-PARENT IDENTIFICATION

  • For an ancestral block C, its external-parent set Pext(C) is the unique minimum-cardinality passing adjustment.A passing pair requires both UP and OUT; together these conditions hold exactly when C is ancestral and Pext(C) is contained in the adjustment.Source: §4.2 · p. 5
  • The invertible within-block factor preserves which recovered variables are direct external parents, so omitting a parent cannot be compensated by other adjustment variables.The regression coefficients are unique because Cov(XF) is positive definite.Source: §4.2 · p. 5

4.3 EXACT CONDENSATION RECOVERY

  • BlockExo repeatedly selects a minimum-total-size passing root block and adjustment, adding each recovered SCC to the ancestral set.With valid search bounds and correct decisions, the population procedure exactly recovers the condensation.Source: §4.3 · p. 6
  • With valid search bounds, regressions use at most smax + dB predictors and the procedure examines pO(smax+dB) candidate pairs, independently of the recovered-set size.In finite samples, estimation error can still cause failure; the number of candidate pairs remains bounded by pO(s+d).Source: §4.3 · p. 6

5 FINITE-SAMPLE RECOVERY AND STRUCTURAL OPTIMALITY

Algorithm 1 uses population scores to test candidate blocks and adjustments, then achieves the lower bound’s structural sample dependence under suitable conditions. With fixed structural bounds, recovery is minimax optimal on a separated model class.

5 FINITE-SAMPLE RECOVERY AND STRUCTURAL OPTIMALITY

  • The finite-sample recovery bound matches the lower bound’s structural dependence, and BlockExo does not need the exact smax or dB values.Source: §5 · p. 6, §5.3 · p. 8

5.1 SCORES AND SEPARATION

  • A candidate passes exactly when its block is ancestral in the remaining graph and its proposed adjustment set includes all external parents.Source: §5.1 · p. 6
  • The two separation margins measure residual upstream effect after insufficient adjustment and residual dependence for a sufficiently adjusted non-ancestral block.Source: §5.1 · p. 7

5.2 MAIN RECOVERY GUARANTEE

  • Under the stated regularity and uniform-estimation assumptions, Theorem 5.2 gives a uniform recovery guarantee for separated model classes.Source: §5.2 · pp. 7–8

5.3 STRUCTURAL OPTIMALITY

  • For fixed structural bounds, the separated class has minimax sample complexity Θ(log p); valid larger search bounds preserve the optimal rate.Source: §5.3 · p. 8

6 SIMULATIONS

Across disjoint and overlapping cycle structures, BlockExo achieved exact recovery with fewer samples than or matching Coarsening in the reported settings. Normalizing by structural and separation factors aligned recovery curves more closely, especially when dimension varied.

6 SIMULATIONS

  • The comparison used sub-Gaussian linear SEMs, disjoint 2-cycles and overlapping 2-cycles, and exact-recovery rates across 20 replicates.Source: §6 · p. 8

6.1 STRUCTURAL SAMPLE COSTS

  • Recovery curves aligned more closely after normalization by structural and separation factors, with stronger alignment when dimension varied at fixed SCC size than when SCC size varied.Source: §6.1 · p. 8, Figure 3 · p. 9

6.2 SAMPLE EFFICIENCY COMPARISON ACROSS METHODS

  • At dB = 1, BlockExo recovered all 20 replicates at n = 384 for disjoint cycles and n = 512 for overlapping cycles, versus 12 and 13 for Coarsening 0.2.At dB = 2, BlockExo reached 20 of 20 at n = 512 for disjoint cycles, versus 14 of 20 for Coarsening 0.2, and matched Coarsening 0.2 at n = 768 for overlapping cycles.Source: §6.2 · p. 9, Figure 4 · p. 9

7 DISCUSSION

The discussion frames the lower and achievable sample costs as targets for exact condensation recovery. It highlights block exogeneity and sparse adjustment, while noting that explaining separation margins remains future work.

7 DISCUSSION

  • The lower bounds separate the unavoidable costs of SCC membership and external-parent selection, and BlockExo matches their structural dependence under suitable conditions.Source: §7 · p. 9
  • Block exogeneity identifies root SCCs without a known partition or correlation faithfulness, while sparse adjustment avoids regressing on all previously recovered variables.Source: §7 · p. 9
  • How separation margins depend on graph structure, coefficients, and noise distributions remains an important open step for explaining sample-cost differences.Source: §7 · p. 9
  • The theoretical results are evaluated using synthetic data, and substantive applications should assess modeling assumptions, including causal sufficiency.Source: ETHICS STATEMENT · p. 10
  • The authors report that implementation, experiment configurations, scripts, and data for reproducing the figures will be publicly released.Source: REPRODUCIBILITY STATEMENT · p. 10

A RELATED WORK: RECOVERY TARGETS AND STATISTICAL GUARANTEES

The related-work discussion contrasts methods for exogenous-block and cyclic-graph recovery, while the proof builds regularity controls and separate packings for SCC membership and external-parent selection.

A RELATED WORK: RECOVERY TARGETS AND STATISTICAL GUARANTEES

  • The displayed related-method rates omit confidence and distributional factors for OptLiNGAM and BlockExo, and other model-dependent constants for Coarsening.Coarsening’s displayed bound uses threshold βmin/2, with βmin defined as the smallest nonzero absolute entry of B.Source: A RELATED WORK: RECOVERY TARGETS AND… · p. 12
  • GroupLiNGAM uses block residual independence under correlation faithfulness; this characterization instead uses scalar-pair residual independence and principal invertibility, without correlation faithfulness.Inclusion minimality identifies root SCCs without a known partition, and sparse adjustment permits ancestry and direct-parent tests.Source: A RELATED WORK: RECOVERY TARGETS AND… · p. 13
  • DisjointCycles addresses disjoint cycles, whereas block-exogeneity also applies to SCCs with overlapping cycles; Coarsening recovers condensations, while this work adds lower bounds.The condensation is identifiable from observational data because its SCC partition and graph are invariant across distribution-equivalent graphs (Sharifian et al., 2025).Source: A RELATED WORK: RECOVERY TARGETS AND… · p. 13
  • StableSpIn targets a variable-level graph representative, whereas this work targets condensation under causal sufficiency; the comparison also reports methods’ computational costs.BlockExo’s candidate-pair count is p^O(smax+dB) under valid search bounds and correct decisions; Coarsening’s cost is O(knp^2 + p^3).Source: A RELATED WORK: RECOVERY TARGETS AND… · p. 13

B STRUCTURAL LOWER-BOUND PROOFS

  • The lower-bound proof restricts to a fixed i.i.d. noise distribution, establishes common KL and regularity bounds, then applies separate packings for SCCs and external parents.The generalized-Fano argument follows a sparse-DAG lower-bound framework.Source: B STRUCTURAL LOWER-BOUND PROOFS · p. 14

B.1 COMMON KL AND REGULARITY BOUNDS

  • The common bounds establish local KL control and uniform packing regularity for coefficient matrices with bounded operator norm.These controls support the packing-based lower-bound arguments.Source: §B.1 · pp. 14–15

B.2 SCC AND EXTERNAL-PARENT PACKINGS

  • A reciprocal-star construction packs distinct nontrivial SCCs without external parents, while a parent-star construction packs distinct external-parent sets in acyclic models.The constructions isolate SCC-membership and external-parent selection costs, respectively.Source: §B.2 · pp. 15–16

B.3 PROOF OF THEOREM 3.1

The proof combines separate SCC-membership and external-parent lower bounds using generalized Fano arguments. Together, they yield the stated structural sample-cost dependence over the full model class.

B.3 PROOF OF THEOREM 3.1

  • The combined lower bound has structural dependence s log(ep/s) + d log(ep/d) across the full model class.The proof handles s = 1 separately because the SCC packing is unavailable there.Source: §B.3 · pp. 17–18
  • Generalized Fano’s inequality is applied separately to the two packings, whose models have distinct condensations.The proof combines the resulting bounds over the full model class.Source: §B.3 · p. 17
  • Separate packings establish necessity for SCC recovery with dB = 0 and external-parent selection on acyclic models.The SCC packing applies for s ≥ 2; the parent packing applies for s ≥ 1.Source: §B.3 · p. 17

C POPULATION PROOF DETAILS

The population proofs characterize root SCCs and external parents through residual-independence tests and establish exact recovery, candidate-count bounds, and uniform residual-estimation and UP covariance-approximation guarantees under explicit sample-size conditions.

C.1 BLOCK EXOGENEITY AND ROOT SCCS

  • Residual independence with zero cross-covariance forces a set to be ancestral, and the inclusion-minimal nonempty ancestral sets are exactly the root SCCs.Every nonempty ancestral set contains a root SCC.Source: §C.1 · pp. 18–19

C.2 SPARSE ADJUSTMENT AND EXTERNAL PARENTS

  • Sparse passing adjustments characterize ancestral sets whose external parents are contained in the adjustment set; the minimum passing adjustment is exactly the external-parent set.For an ancestral set C, the passing adjustments are precisely the supersets of Pext(C).Source: §C.2 · p. 20

C.3 MINIMUM PASSERS AND POPULATION RECOVERY

  • Minimum-size passing pairs identify root SCCs and their exact external parents, and population recovery returns the full SCC partition and condensation edges within |Π| rounds.The minimizing objective is |S| + |Pext(S)| over root SCCs S.Source: §C.3 · pp. 20–21

C.4 POPULATION RECOVERY WITH ARBITRARY SEARCH BOUNDS

  • With population PASS decisions, Algorithm 1 fails exactly when its search bounds undershoot smax or dB.The bounds must satisfy s ≥ smax and d ≥ dB.Source: §C.4 · p. 21

D.1 CANDIDATE COUNT

  • For finite-sample analysis, the candidate-size penalty ℓ(h; α) increases with h and is at least α and h + 1, alongside uniform bounds for same-sample residuals.The proof combines candidate-size bounds over the sizes required for recovery.Source: §D.1 · p. 22, D FINITE-SAMPLE PROOF DETAILS · p. 22
  • When s + d > p, the candidate-count term J is bounded by 2p because x log(ep/x) increases on (0, p].Source: §D.1 · p. 23

D.2 RESIDUAL ESTIMATION ON THE SAME OBSERVATIONS

  • Under Assumption 2.2, n ≥ c_resℓ(h; α) yields an event of probability at least 1 − α with simultaneous residual-prediction and scale bounds and nonsingular required regressions.Source: §D.2 · p. 24

D.3 UNIFORM UP APPROXIMATION

  • For 0 < δ < 1, n ≥ c_upℓ(h; δ) ensures the stated uniform UP covariance approximation, with c_up depending only on (K, λ).Source: §D.3 · p. 26

D.4 PROOF OF THEOREM 5.2

The proof establishes recovery by uniform control of candidate scores, then verifies concrete dependence-score estimators and examines when separation is necessary. In particular, vanishing cyclic separation precludes uniform SCC recovery at sufficiently small sample sizes.

D.4 PROOF OF THEOREM 5.2

  • Uniform score control makes the empirical search select a population passer at each round, yielding exact condensation recovery with probability at least 1−δ.The proof controls all required regressions, residual scales, and score approximations on one event, then applies induction over recovery rounds.Source: §D.4 · p. 27

E SEPARATION AND OPTIMALITY

  • With fixed structural bounds and target error probability, the separated class has minimax sample complexity Θ(log p).The proof combines the uniform recovery bound with a lower bound on the same class.Source: §D.4 · p. 28

D.5 CONCRETE DEPENDENCE-SCORE ESTIMATORS

  • The proof verifies that normalized distance covariance and Gaussian HSIC satisfy the score-approximation condition required by the recovery guarantee.For each estimator, it bounds oracle-statistic error and then controls the effects of fitted residuals and empirical standardization.Source: §D.5 · p. 28, §D.5.1 · p. 30, §D.5.2 · p. 32

D.5.1 NORMALIZED DISTANCE COVARIANCE

  • The normalized distance-covariance score vanishes exactly under independence and its estimator satisfies the required approximation condition under the stated regularity.The approximation constant depends only on (K, λ).Source: §D.5.1 · pp. 28, 30

D.5.2 GAUSSIAN HSIC

  • The Gaussian HSIC estimator satisfies the required approximation condition, with its constant depending on (K, λ, b−).The proof establishes a uniform error bound with failure probability below δ/3.Source: §D.5.2 · pp. 32–33

E.1 VANISHING CYCLIC SEPARATION

  • Without cyclic separation, no estimator uniformly recovers the SCC partition at sample sizes n ≤ (16cKLγ²)⁻¹, where the two models have different partitions.The models differ between two singleton SCCs and one two-node SCC.Source: §E.1 · pp. 33–34

E.2 LOWER BOUND WITH FIXED SEPARATION

The fixed-separation lower bound uses padded finite motifs to keep separation independent of dimension, then applies packing arguments to obtain structural sample costs. The experimental protocol evaluates exact condensation recovery across shared datasets and specified graph constructions.

E.2 LOWER BOUND WITH FIXED SEPARATION

  • Padding a fixed motif with isolated variables keeps both separation margins positive or infinite and independent of p and the motif’s embedding.The margins depend only on the fixed motif, size bounds, and dependence functional.Source: §E.2 · pp. 34–35
  • The separated class yields a lower bound for every estimator by packing cyclic-SCC and external-parent families with cardinalities tied to their respective structural costs.The cyclic family has smax = s0 and no external parents; the parent family is acyclic with dB = d0.Source: §E.2 · p. 35

F.1 EXPERIMENTAL PROTOCOL

  • The experiments use graph constructions with one or four cyclic SCCs, while varying dimension by adding singleton children and holding cyclic cores fixed.External edges are scaled by 0.8/√dB in the described constructions.Source: §F.1 · p. 36
  • Baseline thresholds are selected on separate datasets; the exact GroupLiNGAM search is omitted at p = 50 under the 48 GiB memory budget.Its large-graph approximation targets approximate block ordering rather than exact condensation recovery.Source: §F.1 · p. 37
  • Exact recovery requires both the SCC partition and every condensation edge to be correct; incomplete fits count as failures.Methods are evaluated on the same datasets across 20 replicates.Source: §F.1 · p. 37

F.2 SEPARATION AND SAMPLE COST

The experiments examine how structural complexity and separation relate to recovery across dimensions, external-parent counts, edge strengths, and noise laws. Normalization by the structural term aligns dimension-varying recovery transitions more closely, while dependence margins can vary independently of parent margins.

F.2 SEPARATION AND SAMPLE COST

  • At fixed smax = 3 and dB, hybrid margins agree across p = 10, 30, 50, and normalization by L brings dimension-varying recovery curves closer together.Figure 3(b) shows stronger alignment after normalization than on the raw sample-size axis.Source: §F.2 · p. 37
  • For smax = 3 and p = 50, increasing dB from 1 to 2 raises L from approximately 28.5 to 32.0 and lowers the hybrid margin from 0.201 to 0.132.Together, these changes increase L/b∆hyb² by approximately 2.58, consistent with a later recovery transition for dB = 2.Source: §F.2 · p. 38

F.3 DIMENSION COMPARISON WITH TWO CYCLIC SCCS

  • With two cyclic SCCs, normalization by L brings recovery transitions across dimensions closer together; hybrid margins are approximately 0.0946 for dB = 1 and 0.0624 for dB = 2.These margins remain unchanged across p = 10, 30, 50, even though the estimated dependence margin decreases with dimension at dB = 2.Source: §F.3 · p. 38, Figure 5 · p. 38

F.4 EXTERNAL-EDGE STRENGTH AND DEPENDENCE SEPARATION

  • Figure 6(a) shows that the parent margin increases with external-edge strength while the estimated dependence margin does not, so stronger edges do not necessarily imply greater dependence separation.The plotted margins are medians across four coefficient variants at each scale.Source: §F.4 · p. 39, Figure 6 · p. 39
  • With graph and covariance fixed, the parent margin remains 0.223 while the dependence margin ranges from 0.00092 for uniform noise to 0.0471 for the skewed Gaussian mixture.This is a roughly 51-fold difference in estimated dependence margin.Source: §F.4 · p. 39

F.5 ADDITIONAL SAMPLE-EFFICIENCY COMPARISONS

Across noise distributions and DAG settings, BlockExo recovers exact condensations at sample sizes comparable to or smaller than the Coarsening thresholds, with outcomes depending on cycle structure and external-parent count. Search-bound sensitivity and runtime comparisons further qualify its performance.

F.5 ADDITIONAL SAMPLE-EFFICIENCY COMPARISONS

  • 15/20 and 13/20 exact recoveries at n = 512 for disjoint cycles under symmetric Gaussian mixture noise, while both Coarsening thresholds achieve none; BlockExo reaches 20/20 in all four settings at n = 1024.For overlapping cycles, Coarsening 0.2 reaches high recovery earlier at dB = 2.Source: §F.5 · p. 39, Figure 7 · p. 40
  • Under uniform noise, BlockExo reaches 20/20 exact recoveries in all four settings at n = 3072, though Coarsening 0.2 reaches 20/20 earlier for disjoint cycles at dB = 1.For overlapping cycles, Coarsening 0.2 reaches high recovery earlier at dB = 1, while the methods perform similarly at dB = 2.Source: §F.5 · pp. 39–40, Figure 8 · p. 40
  • With identical graphs, coefficients, and covariance, BlockExo needs more samples as noise changes from skewed Gaussian mixture to symmetric Gaussian mixture to uniform, consistent with decreasing dependence margins.The ordering highlights distribution-dependent separation as a source of recovery difficulty beyond SCC size and external-parent count.Source: §F.5 · p. 40
  • For DAGs with p = 50, BlockExo reaches 20/20 exact recoveries at smaller sample sizes than either Coarsening threshold for dB = 1 and at the same sample size as Coarsening 0.2 for dB = 2.The search bounds are (s, d) = (3, 2), even though they allow cyclic blocks.Source: Figure 9 · p. 40, §F.5 · p. 40

F.6 SENSITIVITY TO SEARCH BOUNDS

  • With common search bounds, BlockExo still reaches 20/20 exact recoveries in every setting, but needs more samples at dB = 1; at n = 192 and n = 384, exact recovery falls from 18/20 to 1/20 and from 20/20 to 3/20, respectively.At (smax, dB) = (2, 2), common and exact bounds yield the same exact-recovery outcome for every replicate.Source: Figure 10 · p. 41, §F.6 · p. 41

F.7 RUNTIME

  • BlockExo’s median runtime is 8–34 seconds across the four Figure 4 settings; it is slower than Coarsening, but on disjoint cycles comparable to DisjointCycles and shorter than StableSpIn.Table 2 pools median runtimes across sample sizes on inputs where BlockExo completed, regardless of recovery accuracy.Source: Table 2 · p. 41, §F.7 · p. 41
Loading 2609.34050v1…