Coarsening Linear Non-Gaussian Causal Models with Cycles Francisco Madaleno, Francisco C Pereira, Alex Markham Abstract Recent work on causal abstraction, in particular graphical approaches focusing on causal structure between clusters of variables, aims to summarize a high-dimensional causal structure in terms of a low-dimensional one. Existing methods for learning such summaries from data assume that both the high- and low-dimensional structures are acyclic, which is helpful for causal effect identification and reasoning but excludes many high-dimensional models and thus limits applicability. We show that in the linear non-Gaussian (LiNG) setting, the high-dimensional acyclicity assumption can be relaxed while still allowing recovery of a low-dimensional causal directed acyclic graph (DAG). We further connect identifiability of this low-dimensional DAG to existing results: LiNG models with cycles are observationally identifiable only up to an equivalence class whose members differ by reversals of directed cycles; our low-dimensional DAG, which is invariant across all members of a given equivalence class, thus forms a natural representative of the class. While existing approaches for learning this observational equivalence class over high-dimensional variables have exponential time complexity, our low-dimensional summary is learned in worst-case cubic time and comes with explicit bounds on the sample complexity. We provide open source code and experiments on synthetic data to corroborate our theoretical results. 1 Introduction Causal discovery from observational data has predominantly focused on directed acyclic graphs (DAGs) 32 ; 33 . Yet many systems of scientific interest contain feedback loops: gene-regulatory networks 29 and dynamical systems 24 exhibit directed cycles. A line of work on cyclic causal models has therefore developed, ranging from the structural-equation formulation of 34 ; 5 to the linear non-Gaussian models of 19 , which exploit standard ICA ( 15 ; 11 ) to recover the demixing matrix W=I-B of a linear cyclic Structural Causal Model (SCM) up to row permutation and scaling, from which the weighted adjacency matrix B —and hence the directed graph G —can be recovered up to a distributional equivalence class. Additionally, other approaches have tried to identify causal orderings among groups of variables: early extensions of linear non-Gaussian methods introduced techniques to estimate causal orderings among multidimensional, disjoint sets of variables 17 ; 10 . The GroupLiNGAM algorithm of 17 has worst-case complexity exponential in the number of variables. More recently, this perspective has been revisited for models containing disjoint cycles 9 , with identification results that rely on second- and third-order moments and thus require the noise distribution to be skewed. In contrast, our approach relies only on general non-Gaussianity via standard ICA, does not require disjoint cycles, and runs in polynomial time. We provide an empirical comparison with that line of work, even though their identification target (the full variable-level cyclic graph under disjoint cycles) differs from ours. The coarsening framework of 38 ; 21 characterizes when a DAG can be simplified by grouping variables into clusters. We show that this framework extends naturally to directed graphs with cycles: the strongly connected components (SCC) partition emerges as a structural floor on the coarsening lattice—the finest partition whose quotient is a DAG—and the resulting cluster-DAG is exactly the condensation G^{\mathrm{sc}} of G in the classical sense of graph theory ( 4 ) . This is the identification target that resolves the ambiguity in the equivalence class of 19 . Contributions. We extend the coarsening framework to directed graphs that may contain cycles, and connect it to the cyclic-SCM identification literature: • The SCC floor ( section 4.1 ). The coarsening lattice acquires a structural floor: any valid DAG-coarsening must group nodes in a common SCC, and the SCC partition is the finest valid one. • Condensation identifiability ( Theorem 1 , section 4.2 ). The condensation G^{\mathrm{sc}} of a linear non-Gaussian cyclic SCM is invariant across the distributional equivalence class of 19 , and is therefore identifiable from observational data alone, without invoking the stability and disjoint-cycles assumptions of that work. As a downstream payoff, identifying G^{\mathrm{sc}} from observations alone supplies the prerequisite of the C-DAG identification theorems of 2 , reducing cluster-level causal-effect identification in a cyclic system to the standard acyclic case. The paper is organized as follows: section 3 fixes notation and recalls the coarsening lattice and cyclic-SCM background; section 4 introduces DAG-coarsenings of cyclic graphs, proves the SCC-floor proposition, presents the learning procedure, proves condensation identifiability and discusses the implication for cluster-level causal-effect identification; section 5 reports the synthetic experiments 1 1 1 An open source implementation as well as scripts for reproducing all of the following experiments can be found at https://github.com/fmfsa/coarsening-cycles . ; section 6 concludes. 2 Related Work Cyclic generalisations of structural causal models date back to 34 , with rigorous foundations in 5 . 19 showed that linear non-Gaussian cyclic SCMs with no latent confounders can be identified via standard ICA: ICA recovers the demixing matrix \hat{W} , from which one obtains a candidate adjacency matrix \hat{B}=I-\mathrm{diag}(P\hat{W})^{-1}P\hat{W} for each admissible row permutation P , and thresholding yields the graph. Later work has extended this to latent-confounded settings via overcomplete ICA ( 30 ; 7 ) , extensions of LiNGAM ( 22 ) , and constraint-based methods using \sigma -separation ( 12 ) . 1 study structure learning for linear cyclic SCMs including the Gaussian case, while ( 36 ) adapt linear non-Gaussian models to learn graphs that are polytrees and 27 leverages interventional data. The condensation also appears in recent experiment-design work for linear non-Gaussian cyclic models ( 31 ) ; our contribution is to place this invariance inside the coarsening lattice as its structural floor, connecting it to the broader coarsening/abstraction literature and to C-DAG identification. Another line of work grounds causal models in stochastic differential equations 13 , rather than standard structural equations. Graphical Lyapunov models 37 ; 8 ; 25 ; 26 encode directed causal structure via a weighted adjacency matrix that solves either the continuous- and discrete-time Lyapunov equation, while naturally allowing for cycles. Coarsening of causal models has been approached from several angles: causal abstraction in the SCM sense ( 28 ; 3 ) , group-level structure under partial-order assumptions ( 38 ) and the partition-refinement approach of 21 that we extend here. The C-DAG identification theorems of 2 characterize which cluster-level interventional distributions are recoverable once an acyclic cluster-level graph is given; the condensation we identify in this paper is precisely such a graph, supplied from observational data. The condensation construction is standard in graph theory ; 35 gives a linear-time algorithm. Our use of the SCC partition as the finest valid DAG-coarsening is, to our knowledge, new in the causal-discovery context: it transforms a cyclic model into an acyclic surrogate to which the standard causal effect identification machinery for DAGs applies. 3 Background 3.1 Coarsening causal models Let G^{*}=(V^{*},E^{*}) be a DAG. A coarsening 21 of G^{*} is a partition \Pi=\{\pi_{1},\ldots,\pi_{k}\} of V^{*} such that the quotient graph G^{\prime}=(\Pi,E^{\prime}) with edges E^{\prime}=\{(\chi(u^{*}),\chi(v^{*}))\mid(u^{*},v^{*})\in E^{*},\ \chi(u^{*})\neq\chi(v^{*})\} is itself a DAG, where \chi:V^{*}\to\Pi sends each node to its part. We call G^{\prime} the quotient graph and the parts \pi_{i} clusters . The set of all coarsenings of G^{*} ordered by refinement forms a sublattice of the partition refinement lattice (Theorem 3 in 21 ); we generalize this construction to cyclic graphs in section 4 . 3.2 Cyclic structural causal models A linear cyclic SCM is defined by: X=BX+\varepsilon,\hskip 20.00003pt\text{solved as }X=(I-B)^{-1}\varepsilon, (1) where d=|V| is the number of variables, B\in\mathbb{R}^{d\times d} is the weighted adjacency matrix of a directed graph G=(V,E) (which may contain cycles), and the noise vector \varepsilon\in\mathbb{R}^{d} has mutually independent components. The spectral radius \rho(B)=\max_{i}|\lambda_{i}(B)| controls when ( 1 ) is solvable: existence and uniqueness require only \det(I-B)\neq 0 , while the stronger condition \rho(B)<1 additionally ensures dynamical stability of the underlying iteration and is the regime studied by 19 . Two matrices play distinct roles. The mixing matrix A=(I-B)^{-1} maps independent sources to observations, X=A\varepsilon ; its support encodes the transitive closure of G (i.e., total effects/reachability) under no exact cancellations. The demixing matrix W=I-B=A^{-1} recovers sources from observations via \varepsilon=WX ; its off-diagonal support encodes the direct adjacency of G . Throughout, \widehat{W} denotes the sample-level FastICA estimate of W . 4 Coarsening Directed Graphs with Cycles We first generalize the notion of coarsening from DAGs to directed graphs that may contain cycles. Definition 1 (DAG-coarsening of a directed graph) . Let G=(V,E) be a directed graph (possibly containing cycles), and let \Pi=\{\pi_{1},\ldots,\pi_{k}\} be a partition of V with associated surjection \chi:V\to\Pi . The quotient graph is G^{\prime}=(\Pi,E^{\prime}) with E^{\prime}=\{(\chi(u),\chi(v))\mid(u,v)\in E,\ \chi(u)\neq\chi(v)\}. We call \Pi a DAG-coarsening of G when G^{\prime} is acyclic. When G is a DAG this reduces to the original definition of 21 : the trivial singleton-per-node partition has an acyclic quotient, and so does any coarsening of it. For graphs containing cycles the acyclicity requirement is non-trivial and forces SCCs to be respected, as Proposition 1 below shows. 4.1 The SCC floor Definition 2 (SCC coarsening/condensation) . Given a directed graph G=(V,E) , the SCC coarsening of G is the DAG-coarsening whose partition surjection \chi satisfies \text{for all }v,w\in V,\hskip 10.00002pt\chi(v)=\chi(w)\iff\mathrm{sc}_{G}(v)=\mathrm{sc}_{G}(w), where \mathrm{sc}_{G}(v) is the strongly connected component of G containing v . The induced quotient is the condensation of G ( 4 ) , denoted G^{\mathrm{sc}} . The underlying partition coincides with the maximally acyclic partition of 38 (their Definition 8(ii)). Proposition 1 (SCC floor) . Let G=(V,E) be a directed graph. Nodes u,v\in V in the same SCC of G must lie in the same cluster of every DAG-coarsening of G . Consequently, the SCC coarsening of Definition 2 is the finest DAG-coarsening of G , and its quotient G^{\mathrm{sc}} is the structural floor of the DAG-coarsening sublattice. Proof. If u and v are in the same SCC, there exist directed paths u\to\cdots\to v and v\to\cdots\to u in G . If \chi(u)\neq\chi(v) in a coarsening, these paths induce directed paths \chi(u)\to\cdots\to\chi(v) and \chi(v)\to\cdots\to\chi(u) in the quotient, forming a cycle and violating the DAG requirement. ∎ Given G the SCC partition is computable via Tarjan’s algorithm ( 35 ) . Remark 1 (cyclic coarsenings) . Definitions 1 and 2 requires the coarsened graph to be a DAG, mirroring the original framework of 21 . A natural generalization drops this requirement and asks only that the coarsening preserves the partial order over SCCs of G : any partition \chi such that the quotient graph (a) does not reverse a non-cyclic ancestral relation in G , and (b) does not introduce a cycle between nodes that are not already in a common SCC, is a valid cyclic coarsening . The interventional and observational coarsenings considered below are all DAG-coarsenings (and hence cyclic coarsenings), so we focus on the DAG case throughout. Characterizing the general cyclic-coarsening lattice is left to future work. Example 1 (example of 19 ) . Consider the five-variable linear cyclic SCM X_{1}=\varepsilon_{1},\hskip 10.00002ptX_{2}=1.2\,X_{1}-0.3\,X_{4}+\varepsilon_{2},\hskip 10.00002ptX_{3}=2\,X_{2}+\varepsilon_{3},\hskip 10.00002ptX_{4}=-X_{3}+\varepsilon_{4},\hskip 10.00002ptX_{5}=3\,X_{2}+\varepsilon_{5}. The directed graph has edges X_{1}\!\to\!X_{2} , X_{2}\!\to\!X_{3} , X_{3}\!\to\!X_{4} , X_{4}\!\to\!X_{2} (a 3-cycle), and X_{2}\!\to\!X_{5} ( Figure 1 left). The cycle X_{2}\!\to\!X_{3}\!\to\!X_{4}\!\to\!X_{2} forms the unique non-trivial SCC \{X_{2},X_{3},X_{4}\} ; nodes X_{1} and X_{5} are singletons. Since any DAG-coarsening must absorb each SCC into a single cluster ( Proposition 1 ), the finest valid coarsening has three clusters \pi_{1}=\{X_{1}\} , \pi_{2}=\{X_{2},X_{3},X_{4}\} , \pi_{3}=\{X_{5}\} , yielding the chain condensation G^{\mathrm{sc}}=\pi_{1}\to\pi_{2}\to\pi_{3} in Figure 1 , right. Reversing the 3-cycle to X_{2}\to X_{4}\to X_{3}\to X_{2} ( Figure 1 , center) yields a second variable-level graph with re-weighted edges that induces the same observational distribution ( 19 , Theorem 4) : ICA cannot distinguish the two, but they share the condensation G^{\mathrm{sc}} —the invariance that Theorem 1 formalizes. \pi_{2} \pi_{2} X_{1} X_{2} X_{3} X_{4} X_{5} X_{1} X_{4} X_{2} X_{3} X_{5} \pi_{1} \pi_{2} \pi_{3} Figure 1 : Distributional equivalence and condensation for the five-variable cyclic SCM of 19 ( Example 1 ). (left, center) Two members of the distributional equivalence class recovered by ICA, differing only in the orientation of the 3-cycle inside the SCC \pi_{2}=\{X_{2},X_{3},X_{4}\} ; both correspond to admissible permutations of the demixing matrix \widehat{W} . (right) The shared condensation G^{\mathrm{sc}} with clusters \pi_{1}=\{X_{1}\} , \pi_{2}=\{X_{2},X_{3},X_{4}\} , \pi_{3}=\{X_{5}\} . ICA cannot distinguish (left) from (center), but G^{\mathrm{sc}} is identifiable ( Theorem 1 ). Note that the inter-SCC edge from X_{1} lands on X_{2} in (left) and on X_{4} in (center); the cluster-level edge \pi_{1}\to\pi_{2} of G^{\mathrm{sc}} is unchanged. Remark 2 (combinatorial structure) . For n=5 the partition lattice has B_{5}=\sum_{k=1}^{5}S(5,k)=1+15+25+10+1=52 partitions, where S(n,k) is the Stirling number of the second kind. Only 4 are valid DAG-coarsenings of Example 1 : the singleton, the SCC floor \{X_{1}\}\mid\{X_{2}X_{3}X_{4}\}\mid\{X_{5}\} , and the two intermediate 2 -clusters \{X_{1}\}\mid\{X_{2}X_{3}X_{4}X_{5}\} and \{X_{1}X_{2}X_{3}X_{4}\}\mid\{X_{5}\} . The remaining 48 are invalid for two reasons ( Figure 2 ): they either split the SCC \{X_{2},X_{3},X_{4}\} , or they merge across condensation layers (e.g. \{X_{1},X_{5}\}\mid\{X_{2},X_{3},X_{4}\} , where the edges X_{1}\!\to\!X_{2} and X_{2}\!\to\!X_{5} create a cycle in the quotient). X_{1}X_{2}X_{3}X_{4}X_{5} X_{1}\mid X_{2}X_{3}X_{4}X_{5} X_{1}X_{5}\mid X_{2}X_{3}X_{4} X_{1}X_{2}X_{3}X_{4}\mid X_{5} \dots 12 other invalid 2-clusters X_{1}\mid X_{2}X_{3}X_{4}\mid X_{5} \dots 24 other invalid 3-clusters \vdots \vdots X_{1}\mid X_{2}\mid X_{3}\mid X_{4}\mid X_{5} SCC Partition Floor Figure 2 : The valid DAG-coarsening sublattice (green) for the graph of Example 1 , embedded in the full partition lattice ( B_{5}=52 partitions). Only 4 of the 52 partitions are valid. The 2-cluster node \{X_{1},X_{5}\}\mid\{X_{2},X_{3},X_{4}\} is invalid not because it splits an SCC but because merging X_{1} and X_{5} creates a cycle between the two clusters. All partitions below the SCC floor split \{X_{2},X_{3},X_{4}\} and are likewise invalid. 4.2 Observational coarsening via linear non-Gaussian ICA We assume the linear cyclic SCM of ( 1 ) with mutually independent, non-Gaussian noise components \varepsilon_{i} and no latent confounders , so \varepsilon has the same dimension as X . Under these assumptions, standard ICA ( 11 ) recovers W=I-B up to row permutation and scaling—the regime exploited by 19 . Overcomplete ICA ( 20 ) is needed only when the number of independent sources exceeds the number of observed variables, which arises under latent confounding ( 30 ; 7 ) . The interventional case is discussed in Section A.1 . Let \hat{W} denote the ICA estimate. Each row permutation P such that P\hat{W} has nonzero diagonal entries yields an admissible candidate: \hat{B}_{P}\;=\;I\;-\;\mathrm{diag}(P\hat{W})^{-1}\,P\hat{W}. (2) The off-diagonal support of \hat{B}_{P} , after thresholding at \tau , gives a candidate directed graph \hat{G}_{P} . Different admissible permutations P yield different members of the distributional equivalence class. 19 resolve this ambiguity by selecting the first candidate with \rho(\hat{B}_{P})<1 , the first-stable filter , which under their stability assumption recovers the true B . Theorem 1 (Condensation identifiability) . Let G_{1},G_{2} be two directed graphs underlying linear cyclic SCMs of the form ( 1 ), both with no latent confounders, mutually independent noise terms and at most one Gaussian noise component. If they induce the same observational distribution over X , then their condensations are equal: G_{1}^{\mathrm{sc}}=G_{2}^{\mathrm{sc}} (same SCC partition, same set of inter-SCC edges). Proof. By Theorem 4 of 19 , equality of distributions implies G_{2} is obtained from G_{1} by a sequence of directed-cycle reversals. 2 2 2 Characterizations in the latent-variable/overcomplete-ICA setting: 7 . SCC partition. Each reversal acts only on edges that lie on a directed cycle and is therefore confined to a single SCC of G_{1} . Within that SCC, the reversal reassigns the structural equations of the nodes on the cycle but preserves mutual reachability: every node on the reversed cycle retains directed paths to and from every other node on it. Nodes outside the SCC are unaffected. Hence G_{1} and G_{2} have the same SCC partition. Inter-cluster edges of G^{\mathrm{sc}} . An inter-SCC edge u\to v of G lies on no directed cycle: any cycle through it would make u and v mutually reachable, hence in the same SCC. Cycle reversal acts only on edges that lie on directed cycles, so it cannot remove or add an inter-SCC edge. It can reassign the structural equation associated with a node inside an SCC, which shifts the variable-level endpoint of an incoming inter-SCC edge to a different node within the same SCC; the cluster-level edge of G^{\mathrm{sc}} is unchanged. Combined with the SCC equality above, this gives G_{1}^{\mathrm{sc}}=G_{2}^{\mathrm{sc}} . ∎ Corollary 1 . In the large-sample limit, G^{\mathrm{sc}} is recoverable by running FastICA to obtain \widehat{W} , picking one admissible row permutation via the Hungarian algorithm 18 to obtain a candidate \hat{B} via ( 2 ), and applying Tarjan’s algorithm to \operatorname{supp}(\hat{B}) . Theorem 1 guarantees that the choice of admissible representative does not affect the recovered condensation. Markov on the condensation. A second consequence of SCC aggregation is the validity of conditional-independence reasoning at the cluster level. Lemma 1 (Markov on the condensation) . Under the linear cyclic SCM of ( 1 ), the marginal joint distribution on cluster-level features is Markov to the condensation G^{\mathrm{sc}} . Linear cyclic SCMs are \sigma -Markov to G ( 34 ; 5 ) . Aggregating variables to their SCC clusters projects \sigma -separation statements about G onto separation statements about G^{\mathrm{sc}} ; since G^{\mathrm{sc}} is acyclic, \sigma -separation collapses to ordinary d-separation, so the cluster-level distribution is Markov to G^{\mathrm{sc}} . Furthermore our identification does not invoke faithfulness: Algorithm 1 recovers \widehat{G}^{\mathrm{sc}} by thresholding entries of \hat{B} , not by conditional-independence testing, so faithfulness plays no role in Theorem 1 . Nonetheless, Corollary 2 of 38 shows it transfers cleanly under the SCC partition: \sigma -Markovian and \sigma -faithful G implies the same for G^{\mathrm{sc}} . Algorithm 1 packages this as a procedure requiring only observational data, based on ICA-LiNG-D ( 19 ) composed with Tarjan, viewed through the coarsening lattice. Bounds on the sample complexity, in terms of \beta_{\mathrm{min}} the minimum nonzero entry of B , are provided in Section B.3 . In particular, recovering the data-generating G^{\mathrm{sc}} with probability at least 1-\delta requires sample size n=\Theta\left(\frac{d}{\beta_{\min}^{2}\,\sqrt{\delta}}\right) . Algorithm 1 Condensation recovery from observational data. 1: Observations X\in\mathbb{R}^{n\times d} ; threshold \tau>0 2: Condensation \widehat{G}^{\mathrm{sc}}=(\widehat{\Pi},\widehat{E}^{\prime}) 3: \hat{W}\leftarrow\textsc{FastICA}(X,d) \triangleright ( 16 ) , d components 4: P\leftarrow\textsc{Hungarian}(\hat{W}) \triangleright single admissible permutation; |(P\hat{W})_{ii}|>\eta for tolerance \eta 5: \hat{B}\leftarrow I-\operatorname{diag}(P\hat{W})^{-1}\,P\hat{W} \triangleright from ( 2 ) 6: \hat{B}_{ij}\leftarrow 0 whenever |\hat{B}_{ij}|<\tau \triangleright thresholding 7: \hat{\Pi}\leftarrow\textsc{Tarjan}(\operatorname{supp}(\hat{B})^{\top}) \triangleright SCCs ( 35 ) 8: \hat{E}^{\prime}\leftarrow\{\,(\pi^{\prime},\pi):\pi\neq\pi^{\prime},\ \exists\,(i,j)\in\operatorname{supp}(\hat{B})\text{ with }i\in\pi,\ j\in\pi^{\prime}\,\} \triangleright B_{ij}\neq 0 encodes X_{j}\to X_{i} 9: return \widehat{G}^{\mathrm{sc}}=(\widehat{\Pi},\widehat{E}^{\prime}) Enumerating all admissible permutations (the original recipe of 19 ) is unnecessary for our identification target: by Theorem 1 , \widehat{G}^{\mathrm{sc}} does not depend on the choice of admissible permutation, and Corollary 1 gives consistency of Algorithm 1 in the large-sample limit. Proposition 2 (Two failure modes of thresholding) . Finite-sample noise affects the recovered partition in two opposite directions. (a) A true intra-SCC edge whose magnitude falls below \tau is dropped; if this breaks reachability inside an SCC, the estimated partition splits a true SCC into multiple clusters. (b) A spurious entry surviving above \tau adds a false edge; if it closes a directed path between two distinct SCCs, the estimated partition merges them. Mode (b) yields a coarsening of the true SCC partition; mode (a) yields a refinement and the resulting quotient is, in general, not a valid DAG-coarsening of the true graph. We probe both failure modes empirically in Section C.2 and discuss their connection to the sample complexity in Section B.3 . Theorem 2 (Time Complexity) . Let d=|V| be the number of observed variables and n the sample size. Algorithm 1 recovers G^{\mathrm{sc}} in worst-case time \mathcal{O}(k\cdot n\cdot d^{2}+d^{3}) , where k denotes the number of FastICA iterations to convergence. The proof and a step-by-step breakdown are in Section B.1 . Because reliable ICA estimation requires n\gg d , the \mathcal{O}(k\cdot n\cdot d^{2}) term dominates in practice. By targeting G^{\mathrm{sc}} rather than enumerating the full distributional equivalence class, we avoid the worst-case \mathcal{O}(d!) N-rooks bottleneck. 4.3 Causal Effect Identification on the Condensation Interventions in cyclic SCMs. Under a soft (shift) intervention X^{I}=(I-B)^{-1}(\varepsilon+\delta) , effects propagate through the entire graph, including back through cycles. Hard ( \mathrm{do} ) interventions that set a single variable X_{k}=c are excluded: they sever the equation for X_{k} , breaking the cyclic mechanism and potentially rendering the system inconsistent. However, hard interventions that target every node of a cluster \pi respect the SCC structure and yield well-defined interventional distributions on G^{\mathrm{sc}} , which we describe next. Fix a cluster \pi\subseteq V and let \bar{\pi}=V\setminus\pi . Partition X , \varepsilon , and B accordingly: X=\begin{pmatrix}X_{\pi}\\ X_{\bar{\pi}}\end{pmatrix},\hskip 20.00003pt\varepsilon=\begin{pmatrix}\varepsilon_{\pi}\\ \varepsilon_{\bar{\pi}}\end{pmatrix},\hskip 20.00003ptB=\begin{pmatrix}B_{\pi\pi}&B_{\pi\bar{\pi}}\\ B_{\bar{\pi}\pi}&B_{\bar{\pi}\bar{\pi}}\end{pmatrix}. A hard cluster intervention \mathrm{do}(X_{\pi}=c) replaces the equations indexed by \pi with X_{\pi}=c . Solving the remaining |\bar{\pi}| -system gives X_{\bar{\pi}}=(I-B_{\bar{\pi}\bar{\pi}})^{-1}(B_{\bar{\pi}\pi}c+\varepsilon_{\bar{\pi}}) . When \pi is a union of SCCs, B_{\bar{\pi}\bar{\pi}} inherits its spectrum from a subset of B , so \det(I-B)\neq 0 already implies invertibility. A soft cluster intervention adds a deterministic offset \delta_{\pi}\in\mathbb{R}^{|\pi|} to the equations of X_{\pi} , replacing X_{\pi}=B_{\pi,V}\,X+\varepsilon_{\pi} with X_{\pi}=B_{\pi,V}\,X+\varepsilon_{\pi}+\delta_{\pi} . Soft interventions preserve the cyclic mechanism inside \pi and induce a cluster-level shift on G^{\mathrm{sc}} . C-DAG identification. Once G^{\mathrm{sc}} is in hand, the C-DAG identification theorems of 2 apply directly: for clusters \pi_{i},\pi_{j} of G^{\mathrm{sc}} , the interventional distribution P(X_{\pi_{j}}\mid\mathrm{do}(X_{\pi_{i}}=c)) is identifiable from P(X) whenever the standard ID conditions hold on G^{\mathrm{sc}} . 5 Experimental Results We illustrate Theorem 1 on synthetic linear non-Gaussian cyclic SCMs using the recipe of 19 from section 4.2 . The interventional case ( Section A.1 ) inherits the unmodified guarantees of 21 and is not explored empirically. All experiments ran on a single CPU workstation (AMD Ryzen 9 9950X, 128 GB RAM); fit times are reported in Figure 4 . 5.1 Setup Data-generating process. We generate linear non-Gaussian cyclic SCMs on d=10 variables with a controlled number \kappa\in\{3,4,5\} of non-trivial SCCs and edge densities \lambda\in\{0.3,0.5,0.8\} . For each (d,\kappa,\lambda) , the d nodes are randomly partitioned into \kappa non-trivial SCCs (each of size \geq 2 ) plus singleton nodes. Within each SCC a directed Hamilton cycle ensures mutual reachability and additional intra-SCC directed edges are sampled at probability \lambda . Between clusters, edges that respect a random topological order are sampled at probability \lambda . Edge weights are sampled in [0.5,0.95] with random sign. Noise components \varepsilon_{i} are mutually independent and Laplace-distributed. Sample sizes n\in[50,10^{5}] ; each cell is replicated across 10 random seeds. Each configuration is run under two spectral-radius regimes: Stable ( \rho(B)\approx 0.9 ): the first-stable filter can recover the true B . Unstable ( \rho(B)=1.5 ): the first-stable filter does not necessarily select the right equivalence-class member; by Theorem 1 the condensation is the same. Method (deliberately broader than Algorithm 1 ). Algorithm 1 recovers G^{\mathrm{sc}} from any single admissible permutation. For the experiments we instead run the full ICA-LiNG-D enumeration of 19 so that we can additionally report variable-level F_{1} and visualize the gap between the identifiable cluster-level structure and the unidentifiable intra-SCC structure. We pick the first-stable candidate (lowest-spectral-radius candidate if no stable one exists). By Theorem 1 , this choice does not affect the recovered \widehat{G}^{\mathrm{sc}} . We use threshold \tau=0.1 ; sensitivity to this choice is reported in Section C.2 . Metrics. Ground truth is the true SCC partition of G (Tarjan on the data-generating B ) and the corresponding condensation. All F_{1} scores are micro-averaged over directed edges. We report: • Adjusted Rand Index (ARI) 14 of the predicted partition versus the true SCC partition; • cluster-DAG F_{1} : F_{1} of the predicted edges projected onto the true SCC partition against the edges of G^{\mathrm{sc}} (the identifiable target of Theorem 1 ); • variable-level F_{1} : F_{1} over all directed edges (including intra-SCC), quantifying the gap between identifiable and unidentifiable structure. 5.2 Results Figure 3 shows partition and edge recovery as functions of sample size for both regimes and all three densities, faceted by \kappa . Three observations: • Partition recovery. ARI rises with n and approaches 1 in both regimes and at all densities, confirming consistency of LiNG-D + Tarjan under non-Gaussian noise. • Cluster-DAG F_{1} . Cluster-DAG F_{1} converges to 1 with n in both regimes, directly illustrating Theorem 1 : G^{\mathrm{sc}} is identifiable regardless of the stability condition. • Variable-level F_{1} . In the stable regime (solid lines), the true B is the unique stable representative of its equivalence class, so the first-stable filter recovers it and variable-level F_{1}\to 1 . In the unstable regime (dashed), the true B has \rho(B)=1.5 , so the filter does not necessarily select the right member of the equivalence class and variable-level F_{1} saturates below 1. The gap is the unidentifiable intra-SCC structure. The contrast between the two regimes is the key empirical message: the condensation (rows 1–2) is robustly recovered even when the variable-level graph (row 3) is not. This is the practical motivation for section 4.3 : rather than chasing the unidentifiable intra-SCC structure, work at the cluster level if possible, where the C-DAG is fully recovered and standard C-DAG identification machinery applies. Figure 3 : Synthetic-data evaluation of the first-stable ICA-LiNG-D recipe ( d=10 , 10 seeds per cell). Columns: number of SCCs \kappa . Densities \lambda\in\{0.3,0.5,0.8\} in progressively darker shades. Solid: stable regime ( \rho(B)\approx 0.9 ); dashed: unstable ( \rho(B)=1.5 ). Rows: ARI of the recovered partition; cluster-DAG F_{1} ; variable-level F_{1} . Shaded bands: 95\% CI across seeds. 5.3 Scalability vs disjoint-cycle baseline We compare against 9 . Their identification target differs from ours: they recover the full variable-level adjacency under the assumption that all cycles in G are pairwise disjoint, using third-order moments rather than ICA, and their guarantees additionally require the noise distribution to be skewed. The comparison is not strictly fair—they solve a harder problem under stronger assumptions—but it is the closest baseline available, so we project both methods onto our cluster-level metrics. Their procedure already returns a cluster partition: the layered topological ordering has layers that are themselves SCCs (singletons or cycles), which we read directly as the predicted partition. Cluster-DAG F_{1} is then computed identically for both methods by projecting the variable-level adjacency onto the predicted partition. We sweep d\in\{20,50,100\} at density \lambda=0.5 with \kappa=10 , n\in[10^{2},10^{5}] , 10 seeds per cell 3 3 3 Our generator can nonetheless create overlapping cycles inside each SCC of size \geq 3 This does not satisfy 9 assumption and might explain the results. See Section C.1 . . Unlike the main experiments of section 5 , which use symmetric Laplace noise, the scalability grid uses skewed exponential noise so that the baseline’s third-moment tests have nonzero signal; both methods operate inside their respective noise regimes. We run their procedure matching the configuration of their published simulations. Figure 4 shows the result. Our method saturates cluster-DAG F_{1} at n\geq 10^{4} for every d ; ARI saturates at n\geq 10^{5} . The baseline recovers the partition only at d=20 and plateaus below 0.3 in cluster-DAG F_{1} for d\in\{50,100\} even at n=10^{5} . Fit time grows steeply for the baseline, reaching 10^{4} s per seed at n=10^{5} , d=100 , while ours stays within 10^{1} s—consistent with the \mathcal{O}(k\,n\,d^{2}+d^{3}) bound of Theorem 2 . Figure 4 : Scalability vs the disjoint-cycle baseline of 9 ( d\in\{20,50,100\} , \lambda=0.5 , \kappa=10 SCCs, 10 seeds per cell). d encoded by colour intensity; solid: ours, dashed: disjointCycles. Left to right: ARI of the recovered partition, cluster-DAG F_{1} , fit time (s). Shaded bands: 95\% CI across seeds. 6 Discussion We have extended the coarsening framework of 21 to directed graphs with cycles, with the SCC partition as the lattice floor and the condensation G^{\mathrm{sc}} as the canonical identification target. Theorem 1 refines the cyclic-SCM identifiability picture of 19 : although the underlying micro-graph is identifiable only up to a distributional equivalence class, G^{\mathrm{sc}} is fully identifiable from the observational distribution, supplying the prerequisite of the C-DAG identification machinery of 2 . The observational approach requires linear non-Gaussian noise and no latent confounders, but with the practical advantage of requiring no interventional data. Hard \mathrm{do} -interventions on a single variable inside a non-trivial SCC sever the cyclic mechanism and are excluded throughout; only soft (shift) interventions and hard interventions on entire SCCs are well-defined in the cyclic SCM setting ( section 4.3 ). Open directions. (i) Latent-confounder generalisations via overcomplete ICA ( 30 ; 7 ) : the cycle-reversal argument carries over because cycle reversals are purely a graph-level operation, independent of the source/observed dimension. (ii) Mixed-Gaussian extension—ICA’s rotational ambiguity in the Gaussian subspace is global, not per-SCC: with two Gaussian sources in different SCCs, an orthogonal rotation can mix them, introducing inter-SCC entries in the equivalent demixing matrix and falsely merging the two SCCs in the recovered condensation. The condensation-invariance argument therefore survives only when at most one noise source is Gaussian overall ; lifting this restriction would address the open problem of ( 19 , § 6) on Gaussian/non-Gaussian mixtures and likely requires structural side information beyond ICA. (iii) Empirical cluster-level causal-effect estimation, applying the C-DAG ID algorithm of 2 to a recovered \widehat{G}^{\mathrm{sc}} on real data. Acknowledgments and Disclosure of Funding The work of FM and FCP was supported by Novo Nordisk Foundation grant number NNF23OC0085356. The work by AM was supported by Novo Nordisk Foundation grant number NNF20OC0062897. The authors thank Carlos Lima Azevedo and Serio Angelo Maria Agriesti for helpful discussions and feedback. Appendix A Additional Comments A.1 On Interventional Extensions Under soft interventions, the cyclic SCM becomes X^{I}=(I-B)^{-1}(\varepsilon+\delta) , so intervention effects propagate through the whole graph, including back through cycles. Nodes within the same SCC are mutual ancestors and therefore share identical intervened-ancestor signatures, so the RefineTest of [ 21 ] cannot split an SCC: RePaRe recovers G^{\mathrm{sc}} with the SCC partition as its floor without modification. Appendix B Additional Proofs B.1 Proof of Theorem 2 Proof. The overall time complexity of Algorithm 1 is governed by the sequential execution of statistical estimation and graph-theoretic aggregation. We break down the worst-case asymptotic time complexity by stage: Independent Component Analysis (FastICA): FastICA computes the unmixing matrix \hat{W} iteratively. The computational cost per iteration is dominated by matrix multiplications involving the n\times d data matrix, taking \mathcal{O}(k\cdot n\cdot d^{2}) time, where k represents the number of iterations until convergence. Admissible-permutation search (combinatorial bypass). A candidate adjacency requires a row permutation P making the diagonal of P\hat{W} nonzero. Exhaustive enumeration over the distributional equivalence class incurs an N-rooks worst-case cost of \mathcal{O}(d!) (in practice typically much smaller, depending on sparsity of \hat{W} ). By Theorem 1 , any admissible P yields the same G^{\mathrm{sc}} , so finding one P suffices: solving a single perfect matching with the Hungarian algorithm runs in \mathcal{O}(d^{3}) . Candidate Generation and Thresholding: Once an admissible permutation P is found, computing \hat{B}_{P}=I-\text{diag}(P\hat{W})^{-1}P\hat{W} and applying element-wise thresholding takes \mathcal{O}(d^{2}) time. If optional stability filtering is applied, computing the spectral radius \rho(\hat{B}_{P}) via eigenvalue decomposition bounds this step at \mathcal{O}(d^{3}) . SCC Partitioning: Extracting the Strongly Connected Components via Tarjan’s algorithm runs in linear time with respect to the candidate graph’s vertices and edges, taking \mathcal{O}(d+|E|)\subseteq\mathcal{O}(d^{2}) time. Condensation Edge Formation: Scanning the edge list to establish inter-cluster adjacencies requires a single pass over the nonzero elements of the adjacency matrix, taking \mathcal{O}(|E|)\subseteq\mathcal{O}(d^{2}) time. Summing these stages yields an overall worst-case time complexity strictly bounded by \mathcal{O}(k\cdot n\cdot d^{2}+d^{3}) . ∎ B.2 Transitive closure and SCCs For a directed graph G=(V,E) , denote the existence of a directed path from vertex u to vertex v by the reachability relation u\leadsto_{G}v . By convention, a vertex can always reach itself (paths of length 0), so u\leadsto_{G}u for all u\in V . Definition 3 (Strongly connected component) . Define a binary relation \sim_{G} on V by u\sim_{G}v\iff(u\leadsto_{G}v)\land(v\leadsto_{G}u). The relation \sim_{G} is an equivalence relation (reflexive, symmetric, transitive). A strongly connected component (SCC) of G is an equivalence class of V under \sim_{G} . The following result provides an alternative route to condensation identifiability via the mixing matrix A=(I-B)^{-1} and its transitive-closure interpretation. While the main proof of Theorem 1 uses the more direct cycle-reversal argument, the transitive-closure perspective is independently useful—for instance, it connects to the path-rank lemma of [ 7 ] and to settings where one works with A rather than W . Definition 4 (Transitive closure) . The transitive closure of a directed graph G=(V,E) is the graph G^{\mathrm{tc}}=(V,E^{\mathrm{tc}}) with edge set E^{\mathrm{tc}}=\{(u,v)\in V\times V\mid u\leadsto_{G}v\}. Theorem 3 (SCCs are preserved under transitive closure) . Let G=(V,E) be a directed graph and let G^{\mathrm{tc}}=(V,E^{\mathrm{tc}}) be its transitive closure. Then G and G^{\mathrm{tc}} have the same SCCs. Proof. It suffices to show u\sim_{G}v\iff u\sim_{G^{\mathrm{tc}}}v for all u,v\in V . ( \Rightarrow ) Suppose u\sim_{G}v , so u\leadsto_{G}v and v\leadsto_{G}u . By Definition 4 , (u,v)\in E^{\mathrm{tc}} and (v,u)\in E^{\mathrm{tc}} , hence u\leadsto_{G^{\mathrm{tc}}}v and v\leadsto_{G^{\mathrm{tc}}}u , i.e. u\sim_{G^{\mathrm{tc}}}v . ( \Leftarrow ) Suppose u\sim_{G^{\mathrm{tc}}}v , so there is a path u=x_{0},x_{1},\dots,x_{k}=v in G^{*} . Each step (x_{i},x_{i+1})\in E^{\mathrm{tc}} implies x_{i}\leadsto_{G}x_{i+1} by Definition 4 . Transitivity of \leadsto_{G} then gives u\leadsto_{G}v . Symmetric reasoning yields v\leadsto_{G}u , so u\sim_{G}v . The two implications give equality of equivalence classes, hence equality of SCCs. ∎ Remark. Theorem 3 means that if one recovers \operatorname{supp}(A)=\operatorname{adjacency}(G^{\mathrm{tc}}) —the transitive closure of G —from the mixing matrix A=(I-B)^{-1} , the SCC partition extracted from it is exactly the SCC partition of G . This provides an alternative proof route for the SCC-partition part of Theorem 1 , going through A rather than W . The main text uses the cycle-reversal argument because it also immediately handles inter-SCC edges without requiring a separate step. B.3 Sample complexity for exact condensation recovery Corollary 1 guarantees that Algorithm 1 returns the correct condensation in the large-sample limit . This subsection turns that asymptotic statement into a finite-sample bound on the sample complexity, that is, how many observations n are sufficient to exactly recover G^{\mathrm{sc}} with probability at least 1-\delta . Setup. Fix a linear non-Gaussian SCM X=BX+\varepsilon with mutually independent noise components, at most one Gaussian, and \det(I-B)\neq 0 . Let \beta_{\min}\;:=\;\min_{(i,j)\,:\,B_{ij}\neq 0}\,|B_{ij}| denote the smallest nonzero entry of the data-generating B . Let \hat{W}_{n} be the FastICA estimate from n i.i.d. samples and let \hat{B}_{n} be the candidate produced by Algorithm 1 at threshold \tau_{n} . Proposition 3 (Finite-sample exact recovery) . Assume the noise components have bounded fourth moments. There exist constants K_{1},K_{2}>0 depending on B and the noise distribution such that, for any threshold sequence \tau_{n} with \tau_{n}\to 0,\hskip 18.49988pt\sqrt{n}\,\tau_{n}\to\infty,\hskip 18.49988pt\tau_{n}<\frac{\beta_{\min}}{2}\text{ for all sufficiently large }n, the recovered condensation satisfies \Pr\bigl[\,\widehat{G}^{\mathrm{sc}}_{n}\neq G^{\mathrm{sc}}\,\bigr]\;\leq\;\Pr\bigl[\,\operatorname{supp}(\hat{B}_{n})\neq\operatorname{supp}(B)\,\bigr]\;\leq\;\frac{K_{1}}{n^{2}\,(\beta_{\min}-\tau_{n})^{4}}\;+\;\frac{K_{2}}{n^{2}\,\tau_{n}^{4}}. (3) The two terms correspond exactly to the two failure modes of Proposition 2 : the first to dropping a true edge (Mode (a), splitting an SCC), the second to keeping a spurious entry (Mode (b), merging two SCCs). Proof. The argument has three steps. Step 1 (entry-wise rates for \hat{B} ). Under bounded fourth moments and at most one Gaussian source, FastICA is \sqrt{n} -consistent for the unmixing matrix up to its canonical row-permutation/sign indeterminacy: with \Pi a permutation and D a diagonal sign matrix aligning \hat{W}_{n} with W^{\star} , \sqrt{n}\,(\hat{W}_{n}-W^{\star}\Pi D) is asymptotically normal with finite covariance [ 6 , 23 ] , and bounded fourth moments of the noise transfer to bounded fourth moments of each entry of \sqrt{n}\,(\hat{W}_{n}-W^{\star}\Pi D) . Hence there exists M>0 such that \mathbb{E}\bigl[(\hat{W}_{n,ij}-W^{\star}_{ij})^{4}\bigr]\;\leq\;\frac{M}{n^{2}} for all entries (i,j) and all n large enough. The map W\mapsto I-\mathrm{diag}(PW)^{-1}PW used in Algorithm 1 is smooth on the open set \{M:(PM)_{ii}\neq 0\,\forall i\} but has singularities on its boundary, so it is not globally Lipschitz. We therefore localize via a high-probability event. Pick a closed ball \mathcal{N} of radius r>0 around W^{\star} on which the map is L -Lipschitz (such an L exists by smoothness on the compact \mathcal{N} , with r,L depending only on B ), and define \mathcal{E}_{n}\;:=\;\bigl\{\,\hat{W}_{n}\in\mathcal{N}\,\bigr\}. By Markov’s inequality applied to the fourth moment of \|\hat{W}_{n}-W^{\star}\|_{\infty} and a union bound over the at most d^{2} entries, \Pr[\mathcal{E}_{n}^{c}]\;\leq\;\frac{d^{2}M}{n^{2}\,r^{4}}. Outside this event we have no control on \hat{B}_{n} , but the event itself is rare. Inside it, the Lipschitz bound gives |\hat{B}_{n,ij}-B_{ij}|\leq L\,\|\hat{W}_{n}-W^{\star}\|_{\infty} , so for any t>0 a union bound over entries combined with Markov on the fourth moment of \hat{W} yields \Pr\bigl[\,\{\,|\hat{B}_{n,ij}-B_{ij}|>t\,\}\cap\mathcal{E}_{n}\,\bigr]\;\leq\;\frac{d^{2}\,L^{4}M}{n^{2}\,t^{4}}. Combining the two contributions, \Pr\bigl[\,|\hat{B}_{n,ij}-B_{ij}|>t\,\bigr]\;\leq\;\frac{d^{2}\,L^{4}M}{n^{2}\,t^{4}}\;+\;\frac{d^{2}M}{n^{2}\,r^{4}}. Under the hypothesis \tau_{n}\to 0 and \tau_{n}<\frac{\beta_{\min}}{2} , both relevant deviations t\in\{\beta_{\min}-\tau_{n},\,\tau_{n}\} stay bounded above by a fixed constant for all large n , so the second summand is absorbed into the first up to a multiplicative constant: there exists K>0 (depending on B and the noise) such that, for all n large enough and all t\in\{\beta_{\min}-\tau_{n},\,\tau_{n}\} , \Pr\bigl[\,|\hat{B}_{n,ij}-B_{ij}|>t\,\bigr]\;\leq\;\frac{K}{n^{2}\,t^{4}}. Step 2 (support recovery via two opposing tails). • False negative. A true edge |B_{ij}|\geq\beta_{\min} is dropped, i.e. |\hat{B}_{n,ij}|<\tau_{n} . By the triangle inequality this requires |\hat{B}_{n,ij}-B_{ij}|>\beta_{\min}-\tau_{n} , and Step 1 bounds the probability by \frac{K}{n^{2}\,(\beta_{\min}-\tau_{n})^{4}} . • False positive. A true non-edge B_{ij}=0 is kept, i.e. |\hat{B}_{n,ij}|\geq\tau_{n} . By Step 1 this has probability at most \frac{K}{(n^{2}\,\tau_{n}^{4})} . A union bound over the at most d^{2} entries gives \Pr\bigl[\operatorname{supp}(\hat{B}_{n})\neq\operatorname{supp}(B)\bigr]\;\leq\;\frac{d^{2}K}{n^{2}\,(\beta_{\min}-\tau_{n})^{4}}\;+\;\frac{d^{2}K}{n^{2}\,\tau_{n}^{4}}, absorbing d^{2}K into K_{1},K_{2} . Step 3 (from \operatorname{supp}(B) to the condensation). Once \operatorname{supp}(\hat{B}_{n})=\operatorname{supp}(B) , the directed graph induced by \hat{B}_{n} is exactly G , so Tarjan’s algorithm returns the exact SCC partition and the exact condensation. This step is deterministic, hence \Pr\bigl[\widehat{G}^{\mathrm{sc}}_{n}\neq G^{\mathrm{sc}}\bigr]\;\leq\;\Pr\bigl[\operatorname{supp}(\hat{B}_{n})\neq\operatorname{supp}(B)\bigr], which combined with Step 2 yields ( 3 ). ∎ Sample complexity. The two terms in ( 3 ) are balanced when \tau_{n}=\frac{\beta_{\min}}{2} , in which case both reduce to a constant times \frac{1}{(n^{2}\,\beta_{\min}^{4})} . Inverting the bound yields: Corollary 2 (Sample complexity) . Under the assumptions of Proposition 3 , fix the threshold to \tau=\frac{\beta_{\min}}{2} . Then for any target error level \delta\in(0,1) , taking n\;\geq\;\frac{4}{\beta_{\min}^{2}}\,\sqrt{\frac{K_{1}+K_{2}}{\delta}} samples is sufficient for \Pr\bigl[\,\widehat{G}^{\mathrm{sc}}_{n}=G^{\mathrm{sc}}\,\bigr]\;\geq\;1-\delta. Proof. Substitute \tau_{n}=\frac{\beta_{\min}}{2} into ( 3 ): the sum of the two terms is bounded by \frac{16(K_{1}+K_{2})}{n^{2}\,\beta_{\min}^{4}} . Requiring this to be at most \delta and solving for n gives the stated bound. ∎ Three remarks on Corollary 2 . First, the sample complexity scales as n\asymp\frac{d}{\beta_{\min}^{2}\,\sqrt{\delta}} once the polynomial-in- d factor inside K_{1},K_{2} (namely K_{i}\asymp d^{2} ) is unpacked—linear in the dimension and quadratic in the inverse minimum-edge magnitude, with \frac{1}{\sqrt{\delta}} dependence on the failure probability. Stronger noise tails (e.g. sub-Gaussian) would replace the polynomial \delta -dependence with \log(\frac{1}{\delta}) via a Hoeffding-type bound, but bounded fourth moments alone yield the polynomial rate above. Second, the choice \tau=\frac{\beta_{\min}}{2} requires a priori knowledge of \beta_{\min} , which we do not have in practice; the alternative \tau_{n}\asymp n^{-\frac{1}{4}} (any sequence with \tau_{n}\to 0 and \sqrt{n}\,\tau_{n}\to\infty ) gives a \frac{1}{n} rate instead of \frac{1}{n^{2}} but is robust to misspecification of \beta_{\min} . Third, the bound ( 3 ) reproduces the threshold-sensitivity picture of Section C.2 term by term: the failure modes of Proposition 2 are exactly the two error events that the union bound in Step 2 controls. Empirical corroboration. Figure 5 reports a Monte-Carlo experiment that tests the rate of Proposition 3 on the same data-generating regime as the main-grid experiments of Section 5 ( d=10 , \kappa=4 non-trivial SCCs, \lambda=0.5 , weights uniform in [0.5,0.95] , Laplace noise; \beta_{\min}\approx 0.51 ). We fix one ground-truth SCM, threshold at \tau=\frac{\beta_{\min}}{2} as prescribed by Corollary 2 , and over 300 independent seeds per cell sweep n\in[10^{2},10^{5}] on a log-spaced grid. The left panel plots \mathbb{E}[d_{H}(\operatorname{supp}\hat{B},\,\operatorname{supp}B)] , a smooth proxy for the entry-wise tail probability. The right panel plots the binary exact-recovery probability \Pr[\operatorname{supp}\hat{B}=\operatorname{supp}B] with 95\% CI bands. An Ordinary Least Squares (OLS) log-log fit on the cells with non-trivial failure rate gives empirical slopes of -4.0 for mean Hamming distance and -2.9 for exact-recovery error in the transition window, both steeper than the -2 predicted by Proposition 3 . This is consistent with the proposition: the bound ( 3 ) is an upper bound under bounded fourth moments alone, and Laplace noise has faster-than-polynomial tails so the actual decay can be sharper. Recovery is exact in every seed by n=2000 . Figure 5: Empirical corroboration of Proposition 3 on the main-grid setup ( d=10 , \kappa=4 , \lambda=0.5 , \beta_{\min}\approx 0.51 , \tau=\frac{\beta_{\min}}{2} , 300 seeds per cell). Left: \mathbb{E}[d_{H}(\operatorname{supp}\hat{B},\,\operatorname{supp}B)] vs n on log-log; the dashed reference line has the predicted slope -2 and the empirical slope is steeper, consistent with the bound being a conservative upper bound under Laplace noise. Right: \Pr[\operatorname{supp}\hat{B}_{n}=\operatorname{supp}B] vs n with 95\% CI bands; the slope in the transition window n\in[200,1000] is -2.9 . Recovery is exact in every seed at n\geq 2000 . B.4 Proof of Proposition 2 Proof. (a) Each non-trivial SCC contains at least one directed cycle. Removing any edge that lies on every cycle of an SCC disconnects the strong-connectivity relation on that SCC, partitioning it into smaller SCCs. (b) A spurious edge \hat{B}_{ij}\neq 0 with i\in\pi,\ j\in\pi^{\prime} in the estimated graph, together with a path \pi^{\prime}\leadsto\pi already present in G , closes a directed cycle through the two clusters and merges them. ∎ Appendix C Additional Results C.1 Strict disjoint-cycles micro experiment The main scalability sweep of section 5.3 at density \lambda=0.5 , creates multiple overlapping cycles within each SCC of size \geq 3 , violating the disjoint-cycles assumption of [ 9 ] . To isolate the effect of that violation from the methodological gap, we run a complementary comparison whose data-generating process satisfies the assumption exactly by construction. Setup. We fix d=20 with \kappa=5 non-trivial SCCs, inter-block density \lambda=0.5 , and zero intra-SCC chord density: each SCC is generated as a single directed Hamilton cycle and no further intra-SCC edges are added. Inter-block edges respect a random DAG ordering over the \kappa=5 blocks. By construction, every directed simple cycle in the resulting graph lies inside a single SCC and is the unique cycle of that SCC, so all simple cycles are pairwise vertex-disjoint, which is the structural premise of [ 9 ] . We sweep n\in[10^{2},10^{5}] with 10 seeds per cell, in the stable weight regime ( w\in[0.5,0.95] , \rho(B)<1 ), and use skewed exponential noise so that the baseline’s third-moment tests carry signal. Both methods use the same fit configuration as the main scalability sweep. Results. Figure 6 reports ARI of the recovered partition, cluster-DAG F_{1} , and fit time. Our method saturates at ARI =1 and cluster-DAG F_{1}=1 from n\geq 10^{4} , with fit time staying within \sim 1 s across the full sweep. The disjoint-cycles baseline plateaus at median ARI \approx 0.13 and median cluster-DAG F_{1}\approx 0.60 even at n=10^{5} , with fit time growing to 10^{2} s. Inspection of the baseline’s predicted partitions explains the gap: at n\leq 10^{3} , every seed returns the trivial all-singletons partition (the procedure’s third-moment cycle tests at \alpha=0.01 have insufficient power and confirm no cycle); at n\geq 10^{4} , the output either contains seeds where some 2–3-cycles are correctly recovered and seeds where it merges most variables into a single cycle. Figure 6: Strict disjoint-cycles micro experiment ( d=20 , \kappa=5 , every SCC a single Hamilton cycle, \lambda=0.5 inter-block, 10 seeds per cell). Solid: ours. Dashed: disjointCycles [ 9 ] . Left to right: ARI of the recovered partition, cluster-DAG F_{1} , fit time (s, log). Shaded bands: 95\% CI across seeds. C.2 Threshold sensitivity and the two failure modes Algorithm 1 requires a threshold \tau>0 on |\hat{B}_{ij}| . Proposition 2 characterises two opposite failure modes; this subsection probes both empirically. We fix d=10 , \kappa=4 , \lambda=0.5 in the stable regime ( \rho(B)<1 ) and sweep \tau across three orders of magnitude on a synthetic grid with 10 seeds per cell. The number of non-trivial SCCs is exactly \kappa=4 in every seed, but the singletons absorbed into non-trivial SCCs vary, so the true partition size |\Pi| ranges over \{4,5,6\} across seeds (median 5 ). Metrics. Figure 7 reports three quantities. The first two are the same metrics used in Section 5 : ARI of the recovered SCC partition (left) and F_{1} of the recovered cluster-DAG edges (middle). The third is the size |\widehat{\Pi}| of the estimated partition (right) —the failure modes: • |\widehat{\Pi}|=1 (everything in one cluster): spurious entries above \tau closed paths between distinct true SCCs and merged everything (Mode (b) of Proposition 2 ). • |\widehat{\Pi}|=d=10 (every variable is a singleton): true intra-SCC edges fell below \tau and every SCC splintered (Mode (a)). • |\widehat{\Pi}|\in\{4,5,6\} (the \tau -independent range of the truth): the recovered partition agrees with the per-seed truth. Results. At n\geq 5000 the safe band is wide and roughly \tau\in[0.1,0.5] : ARI =1 and F_{1}=1 in every seed and |\widehat{\Pi}| matches the per-seed truth. Outside that band the figure shows the two failure modes unambiguously: at \tau\leq 0.01 the right panel collapses to |\widehat{\Pi}|=1 , at \tau=1 it climbs to |\widehat{\Pi}|=d=10 , and ARI / F_{1} collapse correspondingly. The plateau begins later as n shrinks (at n=500 it begins only at \tau\geq 0.2 ), reflecting the larger finite-sample fluctuations of \hat{B} . The default \tau=0.1 used throughout Section 5 sits well inside the safe band whenever n\geq 5000 . 4 4 4 The plateau at F_{1}\approx 2/3 for \tau\to 0 : At very small \tau the recovered \hat{B} is near-fully dense, so the predictor effectively guesses every directed cluster-pair as an edge: recall is 1 and precision is the fraction of cluster-pairs that are truly connected, which for \lambda=0.5 inter-block density gives precision \approx 1/2 and hence F_{1}\approx 2/3 . The plateau at 1 for moderate \tau is the regime of true recovery. Figure 7: Threshold sensitivity at d=10 , \kappa=4 , \lambda=0.5 (stable regime, 10 seeds). Left: ARI of the recovered SCC partition. Middle: F_{1} of the recovered cluster-DAG edges. Right: number of estimated clusters |\widehat{\Pi}| ; the true |\Pi| varies by seed across \{4,5,6\} with median 5 , and inside the safe band |\widehat{\Pi}| matches the per-seed truth. Curves are coloured by sample size. The right panel makes the two failure modes of Proposition 2 explicit: \tau\to 0 collapses to |\widehat{\Pi}|=1 (Mode (b)) and \tau\to 1 saturates at |\widehat{\Pi}|=d=10 (Mode (a)). Shaded bands: 95\% CI across seeds.