Near-Optimal Experiment Design in Linear non-Gaussian Cyclic Models
Authors: Ehsan Sharifian
Saber Salehkaleybar
Negar Kiyavash
Venue: NeurIPS 2025 spotlight ()
Keywords: Causal Discovery
Adaptive Experiment Design
Linear Non-Gaussian SCMs
Cyclic Causal Models
Adaptive Submodularity
Greedy Optimization
Primary area: probabilistic_methods

Abstract: We study the problem of causal structure learning from a combination of observational and interventional data generated by a linear non-Gaussian structural equation model that might contain cycles. Recent results show that using mere observational data identifies the causal graph only up to a permutation-equivalence class. We obtain a combinatorial characterization of this class by showing that each equivalence class corresponds to a perfect matching in a bipartite graph. This bipartite representation allows us to analyze how interventions modify or constrain the matchings. Specifically, we show that each atomic intervention reveals one edge of the true matching and eliminates all incompatible causal graphs. Consequently, we formalize the optimal experiment design task as an adaptive stochastic optimization problem over the set of equivalence classes with a natural reward function that quantifies how many graphs are eliminated from the equivalence class by an intervention. We show that this reward function is adaptive submodular and provide a greedy policy with a provable near-optimal performance guarantee. A key technical challenge is to efficiently estimate the reward function without having to explicitly enumerate all the graphs in the equivalence class. We propose a sampling-based estimator using random matchings and analyze its bias and concentration behavior. Our simulation results show that performing a small number of interventions guided by our stochastic optimization framework recovers the true underlying causal structure.

Near-Optimal Experiment Design in Linear
non-Gaussian Cyclic Models
Ehsan Sharifian EPFL, Lausanne, Switzerland ehsan. wwwrishaaaseeeeeee Sharifian@epf..cm ch
Saber Salehkaleybar Leiden University, Leiden, The Netherlands
s. saleehkaleybar@liac.. Leidenuniv. nn1
Negar Kiyavash
EPFL, Lausanne, Switzerland negar www.wvassepplllccoomm
Abstract
We study the problem of causal structure learning from combination of obser- vational and interventional data generated by linear non- non-Gaussian structural equation model that might contain cycles. Recent results show that using mere observational data identifies the causal graph only up to a cermuuation-qquialenne class. We obtain a combinatorial characterization of this class by showing that each graph in equivalence class corresponds to perfect matching in bipartite graph. This bipartite representation allows us analyze how interventions modify constrain the matchings. Specifically, we show that each atomic intervention reveals one edge of the true matching and eliminates all incompatible causal graphs. Consequently, we formalize the optimal experiment design task as an adaptive stochastic optimization problem over the set of equivalence classes with a natural reward function that quantifies how many graphs climinated from the equiv- alence class by an intervention. We show that this reward function adaptive submodular and provide greedy policy with provable near-optimal performance guarantee. key technical challenge is to efficiently estimate the reward function without having explicitly enumerate all the graphs in the equivalence class. We propose a sampling- estimator using random matchings and analyze its bias and concentration behavior. Our simulation results show that performing small number of interventions guided by our stochastic optimization framework recovers the true underlying causal structure.
Introduction
Learning causal relationships among variables of interest in complex system is central goal in empirical sciences, forming the foundation for prediction, intervention, and explanation [25]. These relationships are typically represented by causal graphs in which edge from variable X to variable Y indicates that X is a direct cause of Y. Much of the existing literature on causal structure learning assumes that the underlying causal graph Directed Acyclic Graph (DAG). However, many natural and engineered systems include feedback mechanisms that give rise to cycles their causal representations, Such cyclic structures emerge in equilibrium models, low-frequency temporal sampling of dynamical systems, and various biological networks 3
In acyclic settings, a variety of methods (such as those based conditional independence tests) allow us to recover the skeleton and orientations of the causal graph from observational data. These methods often fail when applied graphs with cycles. More specifically, observational data alone does not even suffice for learning the skeleton, let alone orienting the edges the graph 23
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Interventions, i.c., actively perturbing the system and observing the resulting distributional changes can allow us to learn the graphs even with cycles. The experiment design problem studies how to best design interventions in order to maximize the information gained about the causal structure. Again, unlike the case of DAGs, where body of work on experiment design exist, the work in the cyclic setting (23) is few and far in between. This is in part due to the fact that, unlike in DAGs, where an intervention on a subset of the vertices orients all the edges incident to them, in cyclic directed graphs, performing experiments in some cases, neither leads to learning the presence of edges nor orienting them [23].
In this work, we study the problem of causal structure learning from combination of observational and interventional data in systems governed by linear non- Gaussian structural causal models (SCMs) that may contain cycles. Our main contributions are as follows:
We establish that, under linear non-Gaussian assumptions, the causal graph can be identified from observational data only up to an equivalence class. We further provide a combinatorial characterization of the equivalence class, where each graph corresponds to a perfect matching in a bipartite graph (Section 4.2). Additionally, we show that the condensation graph, or Strongly Connected Components (SCCs), of the true causal graph can also be identified (..1).
The bipartite representation allows us to analyze how atomic interventions constrain the space of causal graphs. Specifically, we show that each intervention reveals one edge of the true matching and eliminates all incompatible graphs from the equivalence class (Section 5 Therefore, we can formulate the optimal experiment design problem as adaptive stochastic optimization over the space of equivalence classes, using a reward function that quantifies the number of eliminated graphs following intervention. We prove that this reward function is adaptive submodular and hence a greedy policy has provably near-optimal performance guarantees for intervention design (Section 6).
To address the computational challenge of reward estimation, we propose a sampling-basee estimator based on random matchings and provide a theoretical analysis of its bias and concentration properties (Section 7
Experiments show that our adaptive strategy outperforms other heuristic methods and closely matches the feedback vertex set (FVS) lower bound (see more details in Section ??).
2
Related Work
Causal discovery is concerned with learning the underlying causal graph which encodes both the
existence and direction of edges among variables of interest in a system. From observational data
alone, the causal graph can be recovered only up to its Markov equivalence class (MEC). [29] provided necessary and sufficient conditions for Markov equivalence of directed graphs (DGs) and
proposed an algorithm for structure learning up to the MEC (28). [24] extended the applicability of a
classic algorithms for constraint-bod based causal discovery (i.c., FCI (32 to cyclic DGs and showed
that it can recover the structure up to the MEC in this more general setting.
To address latent confounding and nonlinear mechanisms, 6 introduced o-connection graphs (a- CGs) flexible class of mixed graphs and developed a discovery algorithm that handles both latent variables and interventional data. [10] focused on distributional equivalence for linear Gaussian models, providing necessary and sufficient conditions and proposing a score-based learning method. In the context of linear non-Gaussian models, [1]] extended the Independent Component Analysis (ICA)-based approach of [31] to cyclic graphs to learn the equivalence class from the observational data.
The research on experiment design in acyelic models has focused on various aspects, including cost minimization and efficient learning under budget constraints. [5] provided worst-case bounds on the number of experiments to identify the graph. [14 introduced adaptive and exact non-adaptive algorithms for singleton interventions. [13] proposed optimal one-shot and adaptive heuristics to minimize undirected edges. (3 offered lower bounds for experiment design using separating
systems, and (20) introduced a stage-wist wise approach in the presence of latent variables. In cost-aware settings, [19 developed an optimal algorithm for variable-cost interventions without size constraints.
12 and 33 designed approximation algorithms for trees and general graphs, respectively.

---

Fixed-budges design was initiated by [8] with a greedy Monte Carlo-based approach. [ improved MEC sampling efficiency, and 77] developed an exact experiment design algorithm for tree structures. 2 proposed an exact method to enumerate DAGs post-intervention. 36 37 showed that MEC counting and sampling can be done in polynomial time. Bayesian methods include the adaptive submodular algorithm [ and its extension [3 to optimize both intervention targets and their assigned values.
To the best of our knowledge, only a handful of work on experiment design in cyclic graphs exists. For general SCMs, [23] proposed an experiment design approach that can learn both cyclic and acyelic graphs. They provided lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Our approach differs from 23 three key aspects. First, their framework is non-adaptive, that is, all interventions are selected in advance based solely on observational data. In contrast, our method is adaptive each
experiment is selected based on the outcomes of prior interventions. Second, 223 allow intervening on multiple variables in single experiment. Although they also considered the setup where the number of interventions per experiment is bounded, this bound should be greater than the size of the largest strongly connected component in the graph minus one. By contrast, our framework limits each experiment to a Single-variable intervention, making it more practical settings where fine- one-grained or limited interventions
preferred. Third, the approach in [23) is designed for general SCMs and relies on conditional independence testing to recover the causal structure. In our work, we focus specifically on linear non- -an-Gaasiian models, which enables us to use results from ICA to infer the underlying graph.
3 Preliminaries and Problem Formulation
Consider Structural Causal Model (SCM) C == (S, where consists of structural equations and Pe is the joint distribution over exogenous noise terms [26). In a linear SCM (LSCM), the structural equations take the following form:
Wx+
(1)
where x E X' C R. denotes the vector of observable variables, e E & C R" represents the vector of independent exogenous noises, and W E R=*x the matrix of linear coefficients. The directed graph G = (V, E)) induced by the SCM captures the causal structure: node corresponds to the variable r; and for any nonzero coefficient Wij * O, a directed edge (j. E E is drawn. The binary adjacency matrix B& E [0,1)TxM is defined as [Bali = L(W., /00. and the "free parameters" are the nonzero entries su)) {i.j) We * 0}. We impose the following assumptions:
Assumption 3.1. The model has no self-loops: W = for all E [m].
Remark. This assumption be made without loss of generality, as any self-loop be algebraically removed by reparametrizing the structural equations. For detailed explanation, see 22
Assumption 3.2. The matrix 1 W is invertible.
Assumption 3.3. The components of are jointly independent, and at most one component is Gaussian. That is,
Po P PPEP(E) = Pe P. II Pays with most one Pa. Gaussian
Under these assumptions, the model admits a unique solution: x = (I - -1e = Ae. The
observational distribution Px thus given by the fush-forward measure Px = - (I-Tw) (Pa), where Ti denotes the linear map associated with W.
We consider perfect interventions, in which the causal mechanism for a variable r; is replaced with an exogenous noise é, removing all incoming edges to 24. The interventional SCM is given by:
l x + (8)
x
where the i-th row of (+) is zeroed out and the noise in the i-th of is replaced with the new independent noise ē, We denote the new noise vector by (f)) While (I w(() might not always
3

---

be invertible, we assume that the probability it becomes singular is zero under mild randomness conditions on the rows of W. Thus, we treat (I - W as invertible so that the interventional distribution P(x))o(x:) = (I - -www) (Pat) is well defined.
In interventional structure learning, we perform K distinct experiments to reduce uncertainty over the underlying causal graph. Each experiment involves perfect intervention on single variable. We denote the set of intervention targets by I {i1, i2, i2....,, S [n], where i, E [n] indicates that the j-th experiment intervenes on variable Tiy- In the single-intervention setting we consider, each experiment replaces the structural assignment of the target variable with a new exogenous noise term (cf. Equation 2). As result, data from the j-th experiment is drawn from the interventional distribution (z.)).
Each such experiment provides partial information about the true structural matrix W by revealing the causal parents of the intervened variable. The overall objective is to combine observational data with strategically designed interventions to eliminate incorrect graph candidates and recover the true causal structure with minimal experimentation.
Before formulating an optimization strategy for experiment design, we first investigate the extent which the observational distribution constrains the underlying causal graph and matrix W. This characterizes the observational equivalence class of graphs, that is, the set of causal structures that cannot be distinguished based on observational data alone.
4 Distribution Equivalent Graphs
We aim to characterize the class of linear structural causal models (LSCMs) and their associated graphs that generate the same distribution over observable variables. There are two related but distinct notions in the literature:
Distribution-entailnes equivalence, which considers whether two parameterized LSCMs yield the same observational distribution.
Distribution equivalence, which concerns whether two graph structures admit the same set of observable distributions across compatible LSCMs.
These concepts are formally defined and compared in Appendix A In our setting- -inear SCMs with non-Gaussian noise-the the two notions coincide due identifiabiltty guarantees from ICA. For detailed discussion, see also Lacerda et al. (22)
In the remainder of this section, we focus on graph operation that connects distribution--quiialelr graphs.
Definition 4.1 (Cycle Reversion). Let C' be cycle in the graph G. The cycle reversion (CR) operation involves swapping the rows of each member of C in I + Bg with the row corresponding its subsequent node the cycle. This operation reverses the direction of the cycle C. Moreover, any edge from a node outside C' that was originally a parent of some X E C will now point to the predecessor of X in the original cycle C' (see Figure Tap.
Propositions A.3 and A.4 (see Appendix A shows that distribution graphs be trans- formed into one another through a sequence of cycle reversions.
4.1 Strongly Connected Components
In this section, we examine an important property that remains invariant under cycle reversion. To establish this, we first define strongly connected components (SCCs) in directed graphs.
Definition 4.2 (Strongly Connected Component (SCC)), Two vertices and in a directed graph G are said to be strongly connected if there are directed paths from u to and from v to u. This defines an equivalence relation on the vertex set, whose equivalence classes are called strongly connected components (SCCs). Each SCC is maximal subgraph in which every pair of vertices is strongly connected, and no additional vertex from G can be added without violating this property. The collection of SCCs forms partition of the vertex set of G. See 4 Section 22.5]

---

Cycle Racenaon
(a) Cycle reversion operation
(b) SCCs are preserved after CR
Figure 1: (a) Graph representation of cycle reversion. (b) The figure highlights representative nodes from an SCC show that their reachability maintained, although the full SCC not depicted.
Definition 4.3 (Condensation Graph). The condensation graph of directed graph obtained by contracting each SCC into a single vertex and mapping all edges between SCCs to a single edge. The resulting graph directed acyclic graph (DAG).
Theorem 4.4. Strongly connected components remain unchanged in distribution graphs.
Figure Tb illustrates the core idea behind the proof by showing how cycle reversion operations preserve strongly connected components. The following corollary is a direct consequence of the above theorem and the definition of the condensation graph in 4.3
Corollary 4.5. The condensation graphs of all distribution-equivall graphs identical.
Additionally, note that for a subset of vertices in the condensation graph that correspond to single vertices in the original graph, their corresponding row in the recovered matrix via ICA can be identified. This is because cycles only occur within an SCC, and an SCC consists of a single vertex, no cycle passes through eliminating any CR ambiguity. Therefore, the corresponding row can be determined. Furthermore. if the original graph is acyclic, all its SCCs contain only one vertex, meaning that row permutation ambiguity entirely resolved. As result, the original data-generating graph can be inferred purely from observational data, result previously established Linear Non- Non-Gaussian Acyclic Models (LiNGAM) (31
4.2 Matching in Bipartite Graphs
Graphs in distribution-entaiinee graph. Given 1 WICA, recovered ICA from observational data, any equivalent graph can be written as P, D(T - WICA), where P, is row permutation matrix such that its diagonal entries remain nonzero.
equivalence class correspond to perfect matchings in a bipartite
Define a bipartite graph G, = (fri...., [n], E),, where each node r; represents the i-th row of the matrix WICA, and an edge (ri.)) exists if and only if WicA * Each valid permutation æ defines perfect matching + (i), and vice versa. Thus, distribution- equivalent graphs correspond row permutations consistent with matchings in G2, (see an example in Appendix A.4).
This bipartite view provides combinatorial handle equivalence classes and forms the foundation for analyzing how interventions restrict the matching space.
Interventional Distribution
We now investigate how interventional data, when combined with observational data, provides additional knowledge about the causal structure. In particular, show that intervention single variable enables the identification of its causal parents.
All proof's provided in the appendix.
5

---

Proposition 5.1. Given the observational distribution generated by the model in ① and the inter- ventional distribution from model (2), the i-th row of the matrix W can be recovered. Consequentl, the parents of zi and their causal effects are identifiable
5.1 Recovering Edge of the True Matching in the Bipartite Graph
Proposition 5.1 has natural interpretation in the bipartite graph of 4.2 Recall that each perfect matching in the bipartite graph G2 (fri..... .pr1....TTT....... [m], E), E), with edges (rr. E iff WiCA [icA o
0, corresponds to a valid permutation matrix Pa defining a distribution-equivllenn graph.
Intervening on variable 2i, identifies the row corresponding to 2;. In the bipartite graph, this identifies the matching edge (ra-*(a) i) corresponding to the true permutation. This eliminates ambiguity for row (() and restricts the possible options for matching the remaining vertices in the bipartite graph (see an example in Appendix B.2
6 Adaptive Experiment Design
In previous sections, we showed that observational data alone allows us to recover the causal structure only up to an equivalence class of graphs, denoted by Gag- Each member of this class corresponds to different row permutation of the matrix T WICA which is itself associated with a valid matching in the bipartite graph introduced in Section 4.2
To uniquely identify the causal structure, we need to perform interventions. As demonstrated in Proposition 5.1 an intervention on variable 2, reveals the row corresponding to Hg, thereby identifies the correct matching edge (x)- i) in the bipartite graph. Each such intervention removes all graphs from Gog that are incompatible with the identified edge, shrinking the equivalence class.
We now define an adaptive experiment design framework tailored to this setting. Our objective is to strategically select sequence of intervention targets maximally reduce the size of the equivalence class Gey, with the goal of identifying the true causal graph G* using as few interventions as possible.
Let I = {ú1, i2...... .......... } [r]] be the set of selected variables for intervention. For each ij E I. collect the interventional data from the distribution x(1)) ~ P(x[do(zz;)) )), and perform ICA to estimate the corresponding interventional matrix / W()), By comparing this estimate with the observational estimate I WICA. we recover the row of zi, and hence the corresponding matching edge. We then eliminate all graphs in Gog that are incompatible with this edge.
Let Ω = Gog denote the initial equivalence class. For a given intervention set I C [m]] and true graph á E Ω let (TIT.) C Ω denote the set of all graphs that are compatible with the result of interventions on variables in I. The objective is find the set I that minimizes the size of the reduced equivalence class [[(2.))]. In the absence of prior on the true graph á E Q we consider uniform prior over Ω. This leads to an expected-sizz size criterion for selecting the next intervention.
6.1 Adaptive Stochastic Optimization
Our aim is to eliminate as many candidate graphs as possible adaptively, by choosing each intervention based the outcomes observed so far. Let the unknown true graph be random variable drawn uniformly from the set of observationally equivalent graphs, i.e., $ ~ Uni
Following the Adaptive Stochastic Optimization framework
define:
A policy v is adaptive strategy that, at each step f, selects intervention π ((i,, ..).... (iz-1, Oz-1)), based on the history of past interventions i,,..., h-- and their observed outcomes 0 ....., Or-1- Here, each outcome O corresponds the infor- mation gained from intervening on variable for example, the index π -i..) of the true row recovered via ICA, or equivalently, the bipartite matching edge ((.)) i.) that was identified.
For given realization & E Ω and policy æ, let I(TT, Φ) =(ū, fi.,, ix be the (ran- dom) set of variables on which æ intervenes before terminating (subject to a budget of K interventions).
..,,...

---

Define the reward function
f(I, :- [6] 122
(3)
where I S [rx] denotes the set of intervened variables, and Q( S Q is the set of graphs that agree with & on the outcomes of all interventions in I.
The utility of policy ग is the expected reward:
F(x) = En-Uni(()) (),
(4)
Our goal find an adaptive policy æ, subject a budget K interventions, that maximizes F(T).
6.2 Adaptive Monotonicity and Submodularity
We now review some relavent definitions from the adaptive submodularity framework and show that our reward function satisfies these properties.
Definition 6.1 (Universe and Random Realization). Let S be the finite set of all possible true graphs (realizations) consistent with the observational data. We treat the true graph as random variable c ~ Unif(
Definition 6.2 (Partial Realization). Let & = 21. denote the set of variables eligible for intervention, which, in most cases, coincides with the full set of observed variables, and let O denote the set of possible outcomes from each intervention. A partial realization ab is function
v : dom(t) O, dom(v) C E
where (1) E O records the observed outcome (e.g., recovered matching edge) for intervention i. We write 1 & denote the posterior distribution over realizations conditioned on consistency with all observations in 4b, i.e..
+ x {
s agrees with v/ otherwise.
Pr[p of
Definition 6.3 (Conditional Expected Marginal Benefit). Let f 2 X - R20 be reward function and let zb be a partial realization. For any e & dom(()). define the conditional expected marginal benefit
A(ulv) == E (d(om())) U {v}, 4) (((dom())))p)
v6.
(5)
Definition 6.4 (Adaptive Monotonicity). reward function is adaptive monotone if
2
(6)
for every partial realization and item u & dom(w).
Definition 6.5 (Adaptive Submodularity). A reward function f is adaptive submodular if, for all partial realizations & vé' and v & dom(()")
((vlv) A(tlv")
Φ) be the number of graphs eliminated after performing interventions I under Theorem 6.6. Let (I,
realization 6, defined in Equation (3). Then f is adaptive monotone and adaptive submodular with respect to the uniform prior distribution over realizations.
Let F(T) Es- [I x) Φ) denote the expected number of eliminated graphs under
an adaptive policy n, as defined in Equation 44p. Then the adaptive greedy policy achieves
(1 - 1/e) 11)e-xiipiiiimattii to the optimal value of F.
7 Estimating the Reward Function by Sampling
Based on Theorem 6.6 each step (after observing the results of previous interventions), we greedily intervene the variable that maximally reduces the size of the remaining equivalence class. Thus, it sufficient to compute the conditional expected marginal benefit A ((v(1)) for each candidate variable &f dom(

---

Let Φ be any realization consistent with e and define N = (2(dom(())))) In the representation of the problem, the column vertex the bipartite graph may be matched different rows across the candidate graphs in 52 ()d)m) Concretely, recall that each graph in this equivalence class corresponds to a perfect matching in the bipartite graph Go, whose left nodes are rows 71...... . and whose right nodes are column indices 1, ,,.... n. Before intervening on variable v, the right-hand node v may be matched to different row nodes T'., ..... Tzx across the N graphs. Denote these distinct row indices by 21, 22.
, 2k. Therefore, the set of candidate edges for node v is
(F
1....... k
Each graph E () ()) selects exactly one of these edges in its matching, Let
T4 K Q ((dom(().))
matches v to 31
Σ m
Therefore, prior to an intervention, the probability that e matched to row Cx2 is pt := n./N. Once we intervene on v and recover its true row, we identify the correct edge (T=,, v) and eliminate all graphs that do not contain this edge. edge (rz,, e) observed, exactly n, graphs survive, and the number of eliminated graphs is N n2. Hence, the conditional expected marginal benefit under t is:
((vlv) Σ P.(N -n)) -2)= = P; Pp).
To compute (vvl)) via Equation 8 we need to know the full equivalence class (d)mm())) (This necessary for evaluating n, and N). Since explicitly enumerating all graphs in this class is computationally infeasible due to the exponential number of perfect matchings, we estimate (vvlv) by sampling from 52 ((dom(()).))
Let p [Pt.....PPll Pk]" and define the normalized marginal benefit as L(p) : E P: P:). Although p is not directly accessible, we assume a sampling oracle S that returns i.i.d. samples from p. This corresponds to sampling perfect matching uniformly at random and observing the edge incident to A single batch of such samples allows us to estimate (p(p) for all intervention candidates.
The existence of polynomial-time approximate uniform sampler is ensured by the FPRAS of Jerrum, Sinclair, and Vigoda [16]. While their method offers theoretical guarantees, we also consider faster heuristic alternatives in practice. For the sake of analysis, it suffices to assume access such sampler.
Given samples XI,..., XM p, where each X, [k] indicates the row matched to v, we construct an empirical estimate p and use it to approximate A (vl)).
7.1 Statistical Accuracy of Sampling-Bas Based Estimation
We now quantify the accuracy of estimating the marginal benefit ( NL(p) =
N
- E (1 p4) via empirical sampling.
Let h = (pI...., Pk) be the unknown categorical distribution over candidate rows (i.e., the edges
connected in the bipartite graph). Let X1 iI..... XM
iid
p. and define the empirical distribution:
M
$ = (pr,.. .k),
Pk),
P. =
1x,
M
3=1
We use the estimator T.p) = x==
P:(1 -
P.). The following theorem provides an estimation ervor
bound on L(p) - L(p)].
Theorem 7.1. Given M i.i.d samples XI...., Xas
ild for the estimsator L(D), we have:
1
2
2
P (L(D) L(D)
>
+
log
Se
(10)
M
M
8

---

Stategy Conpatton Hunto tamplles
Strtep Or errorenn la Verialess
Sample mode: approximate matching sampler.
(b) Exact mode; full cnumcration of matchings.
Figure 2: Comparison of intervention strategies assuming an ideal ICA oracle. Our method (Adaptive) consistently performs close the feedback vertex set (FVS) lower bound.
In particular, picking e = M implies that with probability at least 1 the error satisfies Mr
0(V
(L()) L(D) S M
1
2log(2M)
0
log M
Ö
V M
1
M
M
8 Experimental Results
We evaluate the performance of our adaptive experiment design method for identifying causal graphs under the linear non-Gaussian structural causal model assumption. Experiments are conducted on synthetic data generated from Erdōs-Rényi random directed graphs, where each possible directed edge (excluding self-loops) is included independently with a fixed probability. To ensure identifiability, we enforce that the resulting matrix I - W is invertible. We measure the average number of interventions required for full causal identification.
8.1 Performance with an Ideal ICA Oracle
To evaluate the intervention strategy on its own, isolating it from statistical estimation errors, we assume access to ideal ICA procedure that returns row-permuted and scaled version of the true matrix W. The adaptive method uses a bipartite representation of the graph and samples perfect matchings using two modes: exact, where all matchings
enumerated, and sample, where fast greedy heuristic used E.2.. We compare our adaptive strategy against two baselines: Random, which selects target uniformly random, and Max Degree, which chooses the node with the highest degree in the bipartite graph.
As theoretical baseline, compute the feedback vertex sel (FVS) of each true graph. The FVS size represents a fundamental lower bound on the number interventions required to break all cycles. Although computing the FVS is NP-hard, solve it exactly to obtain the best possible benchmark.
Figures 2a and 2b show that our adaptive method consistently outperforms the basclines and operates remarkably close to the intractable FVS lower bound, despite having no knowledge of the true graph structure. This demonstrates the near-optimality of our greedy approach an ideal setting. For more details, please refer to
8.2 Robustness in Practical Setting with Finite-Sample ICA
To assess the practical viability of our method, we evaluate its performance in more realistic setting without an ideal ICA oracle. Instead, we apply the FastICA algorithm (I5] finite samples generated from both observational and interventional distributions. This introduces estimation noise, which can corrupt the recovered matrices. To handle these challenges, we introduce two key algorithmic modifications for robustness: adaptive thresholding of matrix entries and safe matching procedure to prevent incorrect row assignments. A detailed description of these modifications provided in Appendix E.3

---

In this setting, our adaptive strategy continues to exhibit performance trend similar to the ideal case, consistently outperforming the Random and Max Degree baselines and remaining remarkably close to the FVS lower bound (see Figure Appendix E.3) confirming its effectiveness even under estimation noise of ICA.
Furthermore, to analyze the quality of the recovered structure, we measured the relative error (Erel W-w"!l
between the estimated matrix W and the ground-truth W*, Our result, presented in Appendix E.3 shows that the algorithm achieves a high-fidelity recovery of the true causal structure in the vast majority of runs.
9 Extensions
Our core framework focuses adaptive, single-variable, perfect interventions in linear non-Gaussian models. Here, we briefly discuss how the proposed method can be extended to more general settings. We defer detailed derivations and proofs Appendix F
9.1 Multi-Node Interventions
The proposed method can be generalized handle simultancous interventions on set of variables E = (f,....., }.). Such an intervention is always informative, as it localizes the www-peruttation ambiguity to the intervened set and effectively disambiguates it from the rest of the graph. Furthermore, if the subgraph induced by the variables in E is acyclic, the internal cycle reversion ambiguity within E fully resolved. This allows for the unique recovery of the true row for each variable in F, enabling the safe parallelization of experiments to accelerate the causal discovery process. We provide detailed analysis in Appendix
9.2 Imperfect Interventions
Our approach is also robust to imperfect interventions. The core requirement for identifying a variable's corresponding is that the intervention sufficiently perturbs its causal mechanism. As long as the post-intervention row is distinguishable from the set of observational rows after ICA estimation, the intervention is informative. This condition holds for some realistic noisy incomplete intervention types, enhancing the practical applicability of our method. Further details are discussed in Appendix F2
9.3 Generalization to Non-linear Models
While focused the linear case, our experimental design strategy could be extended non-linear structural causal models. Recent advances in non-linear ICA can recover the Jacobian of the model's inverse function, whose sparsity pattern reveals the underlying causal graph structure up to the same permutation ambiguity found in the linear setting (27). Our bipartite matching formulation and reward function could then be applied to resolve this ambiguity. We outline this potential generalization in Appendix
F33
10
Conclusion
We introduced framework for causal structure learning in linear non-Gaussian models with cycles, leveraging a combinatorial characterization of equivalence classes via bipartite matchings. By formalizing experiment design as adaptive submodular optimization problem, developed near- optimal greedy policy that incrementally resolves causal ambiguity through targeted interventions. Our sampling-bei based estimator enables practical implementation without exhaustive enumeration. Empirical results confirm that our method recovers the true graph with few interventions, often matching the feedback vertex set lower bound, despite having access to the true structure.
References
[1] Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed-strategy: Budgeted experimental design for targeted causal structure discovery. In
10

---

International Conference on Artificial Intelligence and Statistics, pages 3400-3409. PMLR, 2019.
[2] Ali AhmadiTeshnizi, Saber Salchkaleybar, and Negar Kiyavash. Lazyiter: fast algorithm for counting markov equivalent dags and designing experiments. In International Conference on Machine Learning, pages 125-133. 133. PMLR, 2020.
[3] Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M Mooij. Foundations of structural causal models with cycles and latent variables. The Annals of Statistics, 49(5):285-22155, 2021.
[4] Thomas H Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
[5] Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. In Conference Uncertainty and Artificial Intelligence, pages 178-1884 2005.
[6] Patrick Forré and Joris M Mooij. Constraint-based causal discovery for non-linear structural causal models with cycles and latent confounders. In Conference on Uncertainty in Artificial Intelligence, 2018
[7] AmirEmad Ghassami, Saber Salchkaleybar, and Negar Kiyavash. Interventional experiment design for causal structure learning. arXiv preprint arXiv:1910.0566 2019.
[8] AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference on Machine Learning, pages 1724-1733. PMLR, 2018.
[9] AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Kun Zhang. Counting and sampling from markov equivalent dags using clique trees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3664-3671, 2019.
[10] AmirEmad Ghassami, Alan Yang. Negar Kiyavash, and Kun Zhang. Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs. In International Conference on Machine Learning, pages -504-3504. PMLR, 2020.
[11] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486. 2011.
[12] Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Ko- caoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. Advances Neural Information Processing Systems, 32, 2019.
[13] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
[14] Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov) 2547, 2008
[15] Aapo Hyvärinen and Erkki Oja. Independent component analysis: algorithms and applications. Neural networks, ((4-5))411-430 2000.
[16] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-tim approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671-697, 2004.
[17] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational au- toencoders and nonlinear ica: unifying framework. International conference on artificial intelligence and statistics, pages 2207-2217. PMLR, 2020.
[18] Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Identifiability of deep generative models without auxiliary information. Advances Neural Information Processing Systems, 35: 15:17687 2022.

---

[19] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pages 1875-1884. PMLR, 2017.
[20] Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neural Information Processing Systems, 30, 2017.
[21] Gustavo Lacerda, Peter I. Spirtes, Joseph Ramsey, and Patrik O Hoyer. Discovering cyclic causal models by independent components analysis. In Conference on Uncertainty in Artificial Intelligence, pages 366-374, 2008
[22] Gustavo Lacerda, Peter L Spirtes, Joseph Ramsey, and Patrik O Hoyer. Discovering cyclic causal models by independent components analysis. arXiv preprint /rxiv: 2012.
[23] Ehsan Mokhtarian, Saber Salehkaleybar, AmirEmad Ghassami, and Negar Kiyavash. A unified experiment design approach for cyclic and acyclic causal models. Journal of Machine Learning Research, 24(354):1-31, 2023.
[24] Joris M Mooij and Tom Claassen. Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Conference on Uncertainty in Artificial Intelligence, pages 1668 PMLR, 2020.
[25] Judea Pearl. Causality, Cambridge university press, 2009,
[26] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: founda- tions and learning algorithms. The MIT Press, 2017.
[27] Patrik Reizinger, Yash Sharma, Matthias Bethge, Bernhard Schölkopf, Ferenc Huszár, and Wieland Brendel. lacobian-based causal discovery with nonlinear ica. Transactions on Machine Learning Research, 2023.
[28] Thomas S Richardson. discovery algorithm for directed cyclic graphs arXiv preprint arXiv: 1302.3599. 2013.
[29] Thomas S Richardson. A polynomial-tin algorithm for deciding markov equivalence of directed cyclic graphical models. arXiv preprint arXiv:1302.36000 2013.
[30] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
[31] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(10), 2006.
[32] Peter Spirtes, Clark N Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2000.
[33] Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500-21511, 2020.
[34] Panagiotis Tigas, Yashas Annadani, Andrew Jesson, Bernhard Schölkopf, Yarin Gal, and Stefan Bauer. Interventions, where and how? experimental design for causal models at scale. Advances in Neural Information Processing Systems, 1522130-221443 2022.
[35] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[36] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial time algorithms for counting and sampling markov equivalent dags. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 192-1, 2021.
[37] Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial-inn time algorithms for counting and sampling markov equivalent dags with applications. Journal of Machine Learning Research, 24(213):1 -45, 2023.
12

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main contribution of the paper is to introduce near-optimal experiment
design in linear non- Non-Gaussian cyclic model, as mentioned in the the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
13

---

Justification:
The assumptions of the work are clearly mentioned in Assumption 3.1-3.3.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present proofs of all theorems in the appendix, for improved readability and space limitations.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The codes are available as supplementary material and experimental setups are explained in the appendix.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The codes are available as supplementary material to faithfully reproduce the results.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
gablic//uides/Codeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.ccppulic//uuue http://icc/giiie////eeeuubiiibii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The detail of experiments are discussed in Section 8 and in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The confidence intervals are reported in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources reported in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::p//pprrrps.cc/o///////lclc
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field of machine learning. There are general potential societal consequences result of improvement in alignment techniques, none which we feel must be specifically highlighted.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
17

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All code-bases used in the experiments are cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
wewpuurrpssccoooofeeeeeeeeeeeeee /
19


Reviews:
[{"review_id": "Mc1WNcAZsN", "reviewer": "Reviewer_1ET8", "summary": "This work addresses interventional experiment design in cyclic causal models under linear non-Gaussian functional models. \nIt contributes a characterization of the (observational) Markov Equivalence class in this setting through a direct correspondence between graphs in the MEC and matchings \nin bipartite graphs. The authors give an analysis of how targeted interventions on the system constrain this class, and motivate a reward function for optimal experiment design \nfor which they establish near-optimality guarantees. A sampling-based estimator is also suggested and analyzed, and simulation experiments support both the exact and sampling-based strategies.", "questions": "The main questions are related to the concerns mentioned above, \n- How does the method perform against previous proposals for optimal experimental design? Even when these assume acyclicity, it would be nevertheless be interesting to see the empirical performance in a cyclic setting. Similarly, it would be interesting to see a comparison between the acyclic vs. cyclic setting to judge the effect of this. \n- Did you perform any experiments without access to an ideal ICA procedure to judge the effect of this, and if not do you expect the version without ICA-oracle to still outperform the baselines?", "limitations": "There a no limitations besides what is noted above and no negative impacts.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths** The problem setting is sufficiently novel compared to the existing work  (e.g. Mokhtarian, 2023)  making this work a valuable addition to the literature. \nIn particular, the theoretical insights are original, both regarding the graphical characterizations as well as the proposed adaptive greedy policy with guarantees and sampling-based estimator. \nTheoretical justifications of all of these aspects are given where I found no major issues. There are also no issues regarding clarity and presentation of the work. \n\n**Weaknesses**  Regarding the quality of the experiments, \nit would be interesting  to see a more comprehensive experimental comparison to adaptive methods assuming acyclicity, perhaps on both  cyclic and acyclic settings, to better judge the empirical benefits of considering this setting.\nExperiments are conducted assuming access to an optimal ICA strategy which, while  reasonable  to isolate the effect of the proposed strategy itself, leave it unclear whether the proposal allows to address real-world settings.\nThis affects the practical significance of this work, which may be somewhat limited by to the strong assumptions on the generating process, \nnamely the linear non-Gaussian model and perfect, single-node interventions without off-target effects  which may not always be realistic.  \n\nNevertheless, existing work addressing cyclic causal graphs is indeed limited and this work can provide an important basis for future work, in particular with the given characterization of the MEC which may be of independent interest.", "was_revised": true, "final_justification": "The detailed rebuttal answers adequately address all points raised by the reviewers. The main points that were raised and resolved in the rebuttal and discussion are \n\n- addressing the assumption of access to an ideal ICA procedure through an additional experiment;\n- resolving a concern related to sampling-based estimation using results of Golovin & Krause (2011); \n- providing a detailed argument showing uniformity of the posterior under the uniform-prior assumption; and\n- giving additional clarifications and justifications, such as justifying the assumptions on the data-generating process, discussing extensions for non-linear settings, and clarifying that the approach allows for multi-node interventions. \n\nAs long as the above points meaningfully integrated into the revised manuscript, I am willing to vote for acceptance.", "rebuttal": "* Topic 1: Robustness to Non-Ideal ICA - Finite Sample:\nWe have extended our experiments to a more realistic setting that does not rely on access to an oracle ICA procedure. Instead, we simulate the practical case where ICA is estimated from finite samples by applying *FastICA* to both the observational and interventional datasets. To ensure the robustness of the matching procedure under finite-sample noise, we made a few modifications to the algorithm:\n    * **Adaptive Thresholding:** After ICA recovery, the resulting rows may be noisy, requiring the elimination of small-magnitude elements. However, naive thresholding can lead to overly sparse graphs that no longer admit a perfect matching in the corresponding bipartite representation. To address this, we implemented an adaptive thresholding scheme: it begins with strict relative and absolute magnitude thresholds and progressively relaxes them until the resulting bipartite graph admits at least one perfect matching. \n    * **Safe Matching via Ranked Edge Removal:** To avoid incorrect row matches (which could result in not finding perfect matchings), we replaced the original best-match strategy with a conservative method. For each unmatched node, we rank candidate rows by similarity and attempt to remove each from the bipartite graph. A candidate is only accepted if the resulting bipartite graph still admits a perfect matching. \nWith these modifications, we observed that our method continues to outperform all baseline strategies (e.g., Max Degree and Random), as shown in the table below:\n\n**Table**: Average number of experiments required for full causal discovery in different methods (finite-sample ICA setting)\n\n| **Number of Variables** | **FVS** | **Our Method** | **Max Degree** | **Random** |\n|-------------------------|--------:|----------------:|----------------:|-----------:|\n| 4                       |   0.12  |           0.19  |           0.20  |      0.23  |\n| 5                       |   0.28  |           0.34  |           0.40  |      0.39  |\n| 6                       |   0.42  |           0.44  |           0.56  |      0.63  |\n| 7                       |   0.54  |           0.62  |           0.75  |      0.91  |\n| 8                       |   0.82  |           0.89  |           1.15  |      1.26  |\n| 9                       |   0.88  |           1.11  |           1.52  |      1.65  |\n| 10                      |   1.11  |           1.35  |           1.91  |      2.33  |\n\nWe also report the distribution of relative errors $\\varepsilon_{\\mathrm{rel}}  = \\frac{\\Vert \\widehat{W} - W^* \\Vert_{F}}{\\Vert W^* \\Vert_F}$ between the ground-truth $W^*$ and recovered matrix $\\widehat{W}$ across all runs.\nIn over 80\\% of cases, the error is less than 15\\%, which confirms that our conservative matching design ensures reliable recovery despite finite-sample noise:\n\n**Table**: Distribution of Relative Errors Across All Runs\n\n| **Relative Error Range** | **Number of Instances** |\n|--------------------------|-------------------------:|\n| < 0.05                   |                      501 |\n| 0.05 – 0.15              |                       58 |\n| 0.15 – 0.25              |                       17 |\n| > 0.25                   |                      124 |\n\n* Topic 2: Assumptions in the Data Generating Process:\n    * Justification of linear non-Gaussian model -\n    Linear models are prevalent in many applications, mainly because they can be learned with a moderate sample size and offer simple qualitative interpretations. On the theory side, understanding causal phenomena in a linear model is often a necessary step toward a complete understanding of the given phenomenon, see e.g., (Pearl, 2013). Moreover, in many physical and engineering systems, linear models provide accurate approximations around equilibrium points or typical operating regimes. This local linearity is a well-established principle in control theory and system identification (Åström and Murray, 2008; Ljung, 1999), and supports the use of linear assumptions as a starting point even when the underlying system may be globally nonlinear.\nThe non-Gaussianity assumption is a common assumption required in a wide range of literature on causal effect estimation and causal discovery (Shimizu 2014, Hoyer et al. 2008, Salehkaleybar et al. 2020, Kivva et al. 2023, Peters et al. 2017). More specifically, for Gaussian distributions, some causal relationships are indistinguishable from observational data. This issue is well-illustrated by the non-identifiability results for linear Gaussian models from observational data (Peters et al. 2017). \n    * Generalization to multi-node interventions - \n    Our method is not restricted to single-node interventions. We briefly outline the extension.\n    When an intervention is applied to a set $\\mathcal{I} = \\lbrace i_1, i_2, \\dots, i_t \\rbrace$, the post-intervention matrix differs from the observational one only in the $t$ rows corresponding to the intervened variables. By comparing these matrices after ICA, we can identify the unmatched rows and associate each with an element of $\\mathcal{I}$, as long as the variables in $\\mathcal{I}$ do not form cycles among themselves — that is, the subgraph induced by $\\mathcal{I}$ is acyclic.\nThis condition ensures that there is a unique assignment between unmatched rows and the indices in $\\mathcal{I}$ such that the resulting matrix has non-zero diagonal entries. Moreover, it can be verified directly from the observational weight matrix: one can check whether the corresponding submatrix admits a unique row permutation that yields non-zero diagonal entries. If so, we can safely intervene on the entire set $\\mathcal{I}$ at once and recover the true corresponding row for each variable, assigning it to its correct index. This enables safe parallelization of interventions by selecting such subsets, thereby leading to more efficient experimental design.\n    * Generalization to imperfect interventions - \n    Our approach also extends to imperfect interventions, provided they sufficiently perturb the variable such that its post-intervention row does not match any row from the observational data. This condition holds with high probability under many realistic intervention mechanisms, such as random modifications of parental relationships. Therefore, our method remains valid and informative even under imperfect or noisy interventions.\n* Topic 3: Comparison to Adaptive Methods for Acyclic Graphs\nA summary of existing work on adaptive experiment design in the acyclic setting is provided in Table 1 of (Elahi et al., 2024). Most of the existing methods conduct experiments in the infinite-sample regime—that is, assuming access to the exact observational/interventional Markov equivalence class (MEC). However, since the equivalence classes defined for acyclic graphs do not extend to the cyclic case, these algorithms cannot be directly applied in the infinite-sample regime for cyclic settings. To the best of our knowledge, Elahi et al. (2024) is the only recent work that has conducted experiments in the finite-sample regime. Unfortunately, their implementation is not publicly available, and due to the short rebuttal period, we were unable to reimplement their method. Nonetheless, we will implement their method and report the results in the final version. That said, we believe that adaptive algorithms designed specifically for the acyclic setting may perform poorly in cyclic settings, as they do not account for the presence of cycles and often rely on conditional independence tests, which may not be sample-efficient.\nPearl, Linear Models: A Useful Microscope for Causal Analysis, Journal of Causal Inference, 2013.\n\nShimizu, LiNGAM: Non-Gaussian Methods for Estimating Causal Structures.\" Behaviormetrika, 2014.\n\nHoyer et al., Estimation of Causal Effects using Linear non-Gaussian Causal Models with Hidden Variables. International Journal of Approximate Reasoning, 2008.\n\nSalehkaleybar et al., Learning Linear non-Gaussian Causal Models in the Presence of Latent Variables, JMLR 2020.\n\nKivva et al., A Cross-Moment Approach for Causal Effect Estimation, NeurIPS 2023.\n\nPeters et al., Elements of Causal Inference: Foundations and Learning Algorithms, 2017.\n\nÅström and Murray, Feedback Systems: An Introduction for Scientists and Engineers, 2008.\n\nLjung, System Identification: Theory for the User, 1999.\n\nElahi et al., Adaptive Online Experimental Design for Causal Discovery, arXiv preprint arXiv:2405.11548, 2024."}, {"review_id": "7LRZZx9X83", "reviewer": "Reviewer_k8AX", "summary": "This paper tackles causal structure learning in linear non-Gaussian models with cycles, where observational data alone only identifies graphs up to an equivalence class. The authors provide a novel combinatorial characterization showing that each equivalence class corresponds to a perfect matching in a bipartite graph, and prove that each intervention reveals one edge of the true matching while eliminating incompatible graphs. They formalize optimal experiment design as an adaptive stochastic optimization problem with a submodular reward function, enabling a greedy algorithm with near-optimal performance guarantees. To make this computationally tractable, they develop a sampling-based estimator that avoids explicitly enumerating all graphs in the equivalence class and provide theoretical analysis of its accuracy. Their experiments in synthetic linear non-Gaussian data demonstrate that, when provided with the oracle weight matrix up to row-permutation and scaling, this approach recovers true causal structures with few interventions, often performing close to the theoretical lower bound.", "questions": "Q1. How does your interventional design approach perform when the initial observational equivalence class is incorrectly estimated? To address this, please consider doing the following:\n   - Provide theoretical analysis showing consistency can still be achieved even with incorrect initial equivalence class estimation (acknowledging optimality may be lost) \n   - Develop a modified implementation that accounts for uncertainty in the equivalence class (e.g., by sampling from nearby equivalence classes)\n   - Present empirical results on synthetic data quantifying how sensitive your approach is to misspecification\n\nQ2. Which components of your approach could potentially extend to nonlinear causal models, and where does linearity play a fundamental role? To address this, please consider doing the following:\n   - Clearly identify which theoretical results (bipartite matching characterization, strongly connected components analysis, intervention selection) rely essentially on linearity vs. those that might generalize\n   - Discuss whether the strongly connected components framework could be useful for characterizing equivalence classes in nonlinear settings\n   - Provide informed speculation about what modifications would be needed for nonlinear extensions\n\nIf the authors address my concerns in the Strengths/Weaknesses and Questions sections, I am very happy to increase my score.", "limitations": "Limitations, outside of the additional empirical experiments I requested above, are adequately addressed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nClarity - This submission is very clearly written, and extremely well organized. Assumptions are clearly stated in assumption formatting in Section 3, all reocurring terminology is defined and explained, and the groundwork for upcoming sections. The major sections are sensibily split into mapping each observational equivalence class into a bipartite graph (4), characterizing how interventions pair down the equivalence class (5), developing an adaptive greedy interventional design that is provably near optimal (6), and suggesting a reasonable statistical estimator for the theoretical method in 6, with corresponding analysis of estimator error. In each section, the authors very seamlessly weave between definitions and mathematical results, and explaining the intuition behind each step.\n\nQuality - Although I did not check the proofs in the appendix closely, the intuition behind the major results (Theorem 4.4, Theorem 6.6, and Theorem 7.1) seems clear, and proof sketches throughout the work seem accurate. The authors claims seem generally reasonable, as they outline weaknesses (such as the computational intractability of the theoretical reward function in Section 6), and take steps to try and mitigate them (developing a statistical estimator via sampling in Section 7). The authors adress a wide range of parts of the discovery problem, providing a novel framing of equivalence classes as bipartite matchings, connecting interventional results to the matching, and finally prove near statistical optimality of their approach. Therefore, the claimed contributions in Section 1 are largely substantiated by the details of the work.\n\nOriginality - The key novelty in the work lies first in finding a bipartite matching representation of the equivalence class of potentially cyclic linear SEMs (Section 4), then showing how this bipartite matching can be combined with interventions to eliminate graphs from the class (Section 5). The most important idea is perhaps the move in Section 4.1 to reduce the typical $d$-dimensional graph to a lower level representation  (condensation graph) via strongly connected components, and then proving that condensation graphs are sufficient for acharacterizing all distribution-equivalent graphs. This analysis is quite neat, and potentially more broadly applicable beyond linear SEMs, as strongly connected components may be useful (but perhaps not sufficient) for characterizing other distributions.\n\nWeaknesses:\n\nSignificance\n\n- The main simplifying assumption int his work is linearity (and also causal sufficiency to some degree), which limit the scope of applicability. While this is fine for foundational results, and particularly as there are not many works addressing interventional experiment design in cyclic settings, authors should make clear where they leverage linearity heavily. Additional a discussion on what parts of this are potentially transferable to the nonlinear setting, and perhaps some speculation on what parts are more or less likely to generalize would also be valuable to other researchers in this area.\n- The other major drawback of the experimental approach here is that it seems to depends somewhat strongly on the accuracy of the original estimation of the equivalence class. After all, the way interventions are chosen depends on calculating the value of the  intervention subject to knowledge of the class. This motivates the need to characterize how their approach interacts with error in estimating the original observational class. This can be tackled theoretically in different ways; either you could show that consistency can still be achieved even if original test was wrong (optimality is probably no longer true though), or you could provide a way to loosen the current implementation to get consistency, perhaps by randomly sampling from graphs in nearby equivalence classes (just a thought). This could also be addressed empirically, by running tests in synthetic data to see how bad a problem misspecification of the original equivalence class is - this would help inform future work as to whether this is an subarea of this methodology that would benefit a lot from improvement.", "was_revised": true, "final_justification": "The paper develops a novel theoretical approach to an interventional structure learning in graphs with cycles, an important and often unaddressed problem in causal discovery. It also presents interesting causal sub-structures such as the SCC and other proof techniques that may be generalizable beyond the linear setting considered. The authors provided additional experimental results that confirm the robustness of their approach when the initial MEC estimated gleaned from observational data has errors. I recommend to accept.", "rebuttal": "* Topic 1: Errors in Estimating the Equivalence Classes\n    * Analysis of how our method behaves under misspecification - \nWhen the initial observational equivalence class is incorrectly estimated (e.g., due to ICA errors), the algorithm may still make progress by eliminating incorrect matchings that conflict with interventional data. However, theoretical guarantees such as consistency or optimality can no longer be ensured in the worst case, as the algorithm may converge to an incorrect row permutation of the ground-truth matrix according to our extended simulations (see the results in the following). Still, in most cases, the algorithm recovers the true structure.\n    * Algorithmic modifications to deal with uncertainty in the equivalence class -\n     We have extended our experiments to a more realistic setting that does not rely on access to an oracle ICA procedure. Instead, we simulate the practical case where ICA is estimated from finite samples by applying *FastICA* to both the observational and interventional datasets, which may lead to an uncertainty in the equivalence classes. To ensure robustness in the presence of ICA estimation noise and corresponding misspecifications in the equivalence class, we made two key algorithmic modifications:\n        * **Adaptive Thresholding:** After ICA recovery, the resulting rows may be noisy, requiring the elimination of small-magnitude elements. However, naive thresholding can lead to overly sparse graphs that no longer admit a perfect matching in the corresponding bipartite representation. To address this, we implemented an adaptive thresholding scheme: it begins with strict relative and absolute magnitude thresholds and progressively relaxes them until the resulting bipartite graph admits at least one perfect matching. \n        * **Safe Matching via Ranked Edge Removal:** To avoid incorrect row matches (which could result in not finding perfect matchings), we replaced the original best-match strategy with a conservative method. For each unmatched node, we rank candidate rows by similarity and attempt to remove each from the bipartite graph. A candidate is only accepted if the resulting bipartite graph still admits a perfect matching. \n    * Empirical evidence showing robustness against misspecifications - \n    With these modifications, we observe that our method continues to outperform all baseline strategies (e.g., Max Degree and Random) in terms of the number of experiments needed for full causal discovery, even under noisy ICA-based estimation:\n\n**Table**: Average number of experiments required for full causal discovery in different methods (finite-sample ICA setting)\n\n| **Number of Variables** | **FVS** | **Our Method** | **Max Degree** | **Random** |\n|-------------------------|--------:|----------------:|----------------:|-----------:|\n| 4                       |   0.12  |           0.19  |           0.20  |      0.23  |\n| 5                       |   0.28  |           0.34  |           0.40  |      0.39  |\n| 6                       |   0.42  |           0.44  |           0.56  |      0.63  |\n| 7                       |   0.54  |           0.62  |           0.75  |      0.91  |\n| 8                       |   0.82  |           0.89  |           1.15  |      1.26  |\n| 9                       |   0.88  |           1.11  |           1.52  |      1.65  |\n| 10                      |   1.11  |           1.35  |           1.91  |      2.33  |\n\nWe also report the distribution of relative errors \n$\\varepsilon_{\\mathrm{rel}}=\\frac{\\Vert \\widehat{W}-W^* \\Vert_{F}}{\\Vert W^* \\Vert_{F}}$ between the ground-truth $W^*$ and recovered matrix $\\widehat{W}$ across all runs. In over 80\\% of runs, the error is less than 15\\%, suggesting that—even under misspecification of the initial equivalence class—our approach retains strong empirical performance, although the guarantee of consistency may no longer hold:\n\n**Table**: Distribution of Relative Errors Across All Runs\n\n| **Relative Error Range** | **Number of Instances** |\n|--------------------------|-------------------------:|\n| < 0.05                   |                      501 |\n| 0.05 – 0.15              |                       58 |\n| 0.15 – 0.25              |                       17 |\n| > 0.25                   |                      124 |\n\n    \n    \n* Topic 2: Extentions to Nonlinear Settings\n    * Justification of linearity assumption\n        Linear models are prevalent in many applications, mainly because they can be learned with moderate sample size and offer simple qualitative interpretations. On the theory side, understanding causal phenomena in a linear model is often a necessary step toward a complete understanding of the given phenomenon, see e.g., (Pearl, 2013). Moreover, in many physical and engineering systems, linear models provide accurate approximations around equilibrium points or typical operating regimes. This local linearity is a well-established principle in control theory and system identification (Åström and Murray, 2008; Ljung, 1999), and supports the use of linear assumptions as a starting point even when the underlying system may be globally nonlinear. The non-Gaussianity assumption is a common assumption required in a wide range of literature on causal effect estimation and causal discovery (Shimizu 2014, Hoyer et al. 2008, Salehkaleybar et al. 2020, Kivva et al. 2023, Peters et al. 2017). More specifically, for Gaussian distributions, some causal relationships are indistinguishable from observational data. This issue is well-illustrated by the non-identifiability results for linear Gaussian models from observational data (Peters et al. 2017). \n    * Generalization of our results to nonlinear settings\n    In general SCMs, with the set of structural equations, $X_i:=f_i(Pa_i,N_i), 1\\leq i\\leq n$, let $\\mathbf{f}$ be a vector-valued function where the $i$-th coordinate is $f_i$. In (Reizinger et al., 2023), for DAGs, it is shown that the support of Jacobian of $\\mathbf{f}^{-1}$ is equal to $I-A$ where $A$ is the adjacency matrix of the causal graph. We believe that their proof can be extended to general directed graphs under the same conditions as in Assumption 1 in their work, excluding part (i), which is about acyclicity. Moreover, several algorithms in non-linear ICA have been proposed which can learn $\\mathbf{f}^{-1}$ up to some scaling, permutation, and monotonic element-wise transformations such as (Khemakhem et al. 2020) or (Kivva et al. 2022). Therefore, these results can be utilized to learn the $\\mathbf{f}^{-1}$ up to the mentioned indeterminacies and then used to learn the rows of $I-A$ up to some scaling and permutation. Let us denote the recovered matrix by $I - A_{\\text{ICA}}$. To recover SCCs, we can utilize the recovered matrix $I - A_{\\text{ICA}}$, which allows us to identify the equivalence class obtained from the observational data. \nFor the experiment design, which incorporates interventional data, we now rely on the matrix $I - A$ (as opposed to $I - W_{\\text{ICA}}$ in the linear case). This approach requires that the sparsity patterns of the rows be distinct to enable correct matching in the bipartite graph. Consequently, based on current results in nonlinear ICA, it is needed that each node has a unique parent set in order to carry out the experiment design step. We hope that this assumption can be relaxed with future advances in nonlinear ICA. \n\nPearl, Linear Models: A Useful Microscope for Causal Analysis, Journal of Causal Inference, 2013.\n\nShimizu, LiNGAM: Non-Gaussian Methods for Estimating Causal Structures.\" Behaviormetrika, 2014.\n\nHoyer et al., Estimation of Causal Effects using Linear non-Gaussian Causal Models with Hidden Variables. International Journal of Approximate Reasoning, 2008. \n\nSalehkaleybar et al., Learning Linear non-Gaussian Causal Models in the Presence of Latent Variables, JMLR 2020. \n\nKivva et al., A Cross-Moment Approach for Causal Effect Estimation, NeurIPS 2023. \n\nPeters et al., Elements of Causal Inference: Foundations and Learning Algorithms, 2017. \n\nÅström and Murray, Feedback Systems: An Introduction for Scientists and Engineers, 2008. \n\nLjung, System Identification: Theory for the User, 1999.\n\n Khemakhem et al., Variational Autoencoders and Nonlinear ICA: A Unifying Framework, AISTATS 2020.\n\nKivva et al., Identifiability of Deep Generative Models without Auxiliary Information, NeurIPS 2022.\n\nReizinger et al., Jacobian-based Causal Discovery with Nonlinear ICA, Transactions on Machine Learning Research, 2023."}, {"review_id": "jUIvw5wTxg", "reviewer": "Reviewer_kRFZ", "summary": "This paper tackles causal discovery in linear non-Gaussian cyclic models—systems where  cycles make structure learning tricky. Previous work shows that observational data alone can't fully identify the causal graph; instead, we're left with a set of permutation-equivalent candidates. Authors show that each atomic intervention cuts through the uncertainty by revealing one true edge, pruning incompatible graphs from the equivalence class. The authors frame experiment design as an adaptive stochastic optimization problem, proving their reward function is adaptive submodular and that a greedy policy achieves near-optimal efficiency. Simulations confirm that their method, aided by a sampling estimator, recovers the true causal structure with minimal interventions.", "questions": "Questions/Comments for the Authors:\n\nComparison with Mokhtarian et al. (2023):\nCould you compare your proposed approach against Mokhtarian et al. (2023) for the linear case? Demonstrating superior performance for this specific class of models would help readers better appreciate the work’s value.\n\nAssumption 3 (Non-Gaussian Noise):\nWhy is the restriction to at most one Gaussian noise component (Line 125) necessary? Does the model fail to admit a unique solution if multiple noise components are Gaussian? Could you justify this theoretically or with an example or a reference?\n\nSingle-Node Intervention Limitation:\nWhat prevents extending your method to multi-node interventions when such data is available? Could a similar approach be adapted for this case?\n\nSampling-Based Estimator Concerns:\nWhile you characterize the statistical accuracy of the sampling-based estimator, how does its use affect the optimality of solutions obtained via the greedy policy? Specifically, could estimation errors in the reward function lead to suboptimal intervention sequences?\n\nExperimental Details:\nHow many samples (M) were used for the sampling-based estimation in your experiments? This parameter’s choice seems critical for balancing accuracy and computational cost.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This work establishes that linear non-Gaussian cyclic models are identifiable only up to an equivalence class, characterized combinatorially via perfect matchings in bipartite graphs. Furthermore, the authors prove that each intervention reveals one true edge, enabling adaptive experiment design with submodular guarantees, and develop an efficient sampling estimator to overcome the computational challenge of graph enumeration. They also provide experimental validation of the proposed approach, demonstrating near-optimal recovery of causal structure with minimal interventions.\n\nWeaknesses: The problem setup is restricted to linear models and assumes non-Gaussian noise (with at most one Gaussian component). Additionally, the noise components must be independent, which limits practical applicability. The paper also lacks comparison with Ehsan Mokhtarian et al. (2023), which, while focusing on general SCMs, remains a valid baseline for the linear case. Furthermore, the framework limits each experiment to single-variable interventions, potentially restricting applications where multi-node intervention data is available.", "was_revised": true, "final_justification": "I thank the reviewer for the detailed response to my questions. Including some discussion from the response will improve the manuscript. I will keep score for the paper.", "rebuttal": "* Topic 1: Linearity, Non-Gaussianity, and Independent Noises Assumption - \nLinear models are prevalent in many applications, mainly because they can be learned with a moderate sample size and offer simple qualitative interpretations. On the theory side, understanding causal phenomena in a linear model is often a necessary step toward a complete understanding of the given phenomenon, see e.g., (Pearl, 2013). Moreover, in many physical and engineering systems, linear models provide accurate approximations around equilibrium points or typical operating regimes. This local linearity is a well-established principle in control theory and system identification (Åström and Murray, 2008; Ljung, 1999), and supports the use of linear assumptions as a starting point even when the underlying system may be globally nonlinear.\nThe non-Gaussianity assumption is a common assumption required in a wide range of literature on causal effect estimation and causal discovery (Shimizu 2014, Hoyer et al. 2008, Salehkaleybar et al. 2020, Kivva et al. 2023, Peters et al. 2017). More specifically, for Gaussian distributions, some causal relationships are indistinguishable from observational data. This issue is well-illustrated by the non-identifiability results for linear Gaussian models from observational data (Peters et al. 2017). \nAbout independent exogenous noises, this is the fundamental assumption in SCM, and it is often called \"principle of independent mechanism\". Please refer to Chapter 2 of the textbook (Peterts et al., 2017) for the justification of this assumption.\n\n* Topic 2: Why is the restriction to at most one Gaussian noise necessary?\nThis condition is required in linear ICA to identify the mixing matrix up to scaling and permutation (Eriksson & Koivunen, 2004). In our setting, it enables recovery of the rows of $ I-W$. For DAGs, it's also necessary to recover the full causal graph from observational data using ICA-LiNGAM (Shimizu et al., 2006).\n\n\n* Topic 3: Comparison with Prior Work (Mokhtarian et al. 2023) - \nIn the submitted paper (lines 93–108), we provided a detailed comparison with Mokhtarian et al. (2023). To summarize the key differences: their framework is non-adaptive—all interventions are selected in advance using only observational data. In contrast, our method is adaptive, choosing each intervention based on the outcomes of previous ones. Additionally, their approach involves multi-variable interventions. While they also consider a bounded setting, the required bound must exceed the size of the largest SCC in the graph minus one. Our method, by default, uses single-variable interventions—though it can be extended to the multi-variable case, discussed in the following—which is often more practical in scenarios with limited or fine-grained intervention capabilities. Finally, their method targets general SCMs and uses CI testing to recover the structure, while we focus on linear non-Gaussian models, allowing us to leverage ICA for causal discovery. A direct empirical comparison is not fair to them, given that our adaptive approach typically needs far fewer interventions than a non-adaptive one.\n\n* Topic 4: Multi-Node Interventions - \nIndeed, our method **can be extended to multi-node interventions** when such data is available. Suppose an experiment is conducted where interventions are simultaneously applied to a set of variables $\\mathcal{I}= \\lbrace i_1, i_2, \\dots, i_t \\rbrace$. In this case, applying ICA to both observational and interventional datasets yields matrices $P D (I - W)$ and $P' D' (I - W^{(i_1, i_2, \\dots, i_t)})$, where $P, P'$ are permutation matrices and $D, D'$ are diagonal scaling matrices. The matrix $W^{(i_1, \\dots, i_t)}$ is the post-intervention weight matrix, obtained by zeroing out the $i_1, \\dots, i_t$-th rows of $W$, corresponding to interventions on $\\lbrace i_1, i_2, \\dots, i_t \\rbrace$.\nThe difference between $P D (I - W)$ and $P' D' (I - W^{(i_1, \\dots, i_t)})$ lies precisely in the $t$ rows corresponding to the interventions. \nBy comparing the two matrices, we can identify the $t$ unmatched rows and each row belongs to one of the indices in $\\lbrace i_1, i_2, \\dots, i_t \\rbrace$. This turns the global row-permutation problem into a **local one** over the intervened set. More importantly, such an intervention effectively breaks the cycle reversion ambiguity between the intervened set $\\mathcal{I}$ and the rest of the graph, isolating the two. As a result, the permutation ambiguity is constrained separately within each set. \nIn the multi-node intervention case, it is needed that the set of intervened variables $\\mathcal{I}$ does not contain cycles among themselves — that is, the subgraph induced by $\\mathcal{I}$ must be acyclic. This condition ensures that there is a unique assignment between unmatched rows and the indices in $\\mathcal{I}$ such that the resulting matrix has non-zero diagonal entries. Moreover, it can be verified directly from the observational weight matrix: one can check whether the corresponding submatrix admits a unique row permutation that yields non-zero diagonal entries. If so, we can safely intervene on the entire set $\\mathcal{I}$ at once and recover the true corresponding row for each variable, assigning it to its correct index. \n\n* Topic 5: Sampling-Based Estimation and Optimality - \nThis question fits within the adaptive submodularity framework of Golovin & Krause (2011), which offers approximation guarantees for greedy policies even with approximate marginal gains. They showed that if each selection has an *absolute error* of at most $\\varepsilon$, the total reward remains near-optimal, with only an additive degradation.\nOur greedy rule selects the intervention $v$ maximizing the (estimated) marginal gain\n$\\Delta(v\\mid\\psi)=N\\,L(p_v)$ with $L(p_v)=\\sum_{i=1}^{k_v} p_{v,i}(1-p_{v,i})$, where $p_v$ is the categorical distribution over candidate rows adjacent to $v$ in the bipartite graph. We estimate $p_v$ from $M$ i.i.d. samples and use $ L(q_v) $ as our estimation for $L(p_v)$, where $ q_v $ is the empirical distribution formed from $ M $ i.i.d. samples used to estimate $p_v$. Theorem 7.1 in our paper shows that, for any fixed $v$,\n$$\\mathbb{P}\\left[\\bigl|L(q_v)-L(p_v)\\bigr|\\ge \\tfrac{1}{M}+\\sqrt{\\tfrac{2}{M}\\log\\left(\\tfrac{2}{\\delta}\\right)}\\right]\\le\\delta,\\tag{1} \\quad\\text{with prob. } \\ge 1-\\delta.$$\nhence\n$$\n\\bigl|\\widehat{\\Delta}(v\\mid\\psi)-\\Delta(v\\mid\\psi)\\bigr|\n\\le\nN\\left(\\tfrac{1}{M}+\\sqrt{\\tfrac{2}{M}\\log\\left(\\tfrac{2}{\\delta}\\right)}\\right)\n\\quad\\text{with prob. } \\ge 1-\\delta.$$\nwhere $\\widehat{\\Delta}(v\\mid\\psi) = NL(q_v)$. Now we want to have **uniform control across candidates.**\nLet $A_\\psi$ be the set of feasible interventions at state $\\psi$ (typically $|A_\\psi|\\le n$). Applying a union bound to eq. (1) with $\\delta'=\\delta/|A_\\psi|$ yields, with probability at least $1-\\delta$,\n$$\\sup_{v\\in A_\\psi}\\bigl|\\widehat{\\Delta}(v\\mid\\psi)-\\Delta(v\\mid\\psi)\\bigr|\n\\le\nR_M(\\delta,|A_\\psi|)\n:=\nN\\left(\\tfrac{1}{M}+\\sqrt{\\tfrac{2}{M}\\log\\Bigl(\\tfrac{2|A_\\psi|}{\\delta}\\Bigr)}\\right).\\tag{2}$$ \nLet $v^\\star\\in\\arg\\max_v \\Delta(v\\mid\\psi)$ and $v_{\\text{sel}}\\in\\arg\\max_v \\widehat{\\Delta}(v\\mid\\psi)$.\nBy optimality of $v_{\\text{sel}}$ for the estimates and the two–sided deviation bound in eq. (2), with probability at least $1-\\delta$, we have\n$$\\Delta(v_{\\text{sel}}\\mid\\psi)\n\\ge\n\\widehat{\\Delta}(v_{\\text{sel}}\\mid\\psi)-R_M\n\\ge\n\\widehat{\\Delta}(v^\\star\\mid\\psi)-R_M\n\\ge\n\\Delta(v^\\star\\mid\\psi)-2R_M .\\tag{3}$$\nThus each greedy step is computed with **absolute error** at most\n$\\varepsilon_M:=2R_M(\\delta,|A_\\psi|)$.\nSince our objective is adaptive monotone and adaptive submodular, we can invoke the **guarantees of Golovin and Krause (2011) for the greedy rules implemented with only a small absolute error**. Please refer to this paper for the definition of Policy Truncation (Definition 4), and Theorem 5. Hence, if at every step the selected item satisfies eq. (3), then for any integers $\\ell,k>0$,\n$$F\\left(\\pi_{[\\ell]}\\right) \\ge \\left(1-e^{-\\ell/k}\\right)F\\left(\\pi_{[k]}^{\\star}\\right) - \\ell\\varepsilon_M,$$\nwith high probability.\nTherefore, the cumulative degradation scales as\n$O\\left(\\ell N\\sqrt{\\tfrac{\\log(|A_\\psi|/\\delta)}{M}}\\right)$, vanishing at the standard Monte-Carlo rate.\n\n* Topic 6: Number of samples ($M$) used in the sampling-based estimation - \nWe experimented with $M \\in \\lbrace100, 500, 1000, 3000 \\rbrace$ and found that $M = 1000$ offered a good balance between accuracy and computational cost. Smaller values led to noisy estimates and worse interventions, while larger ones gave marginal gains with high runtime. Thus, we fixed $M = 1000$ in all experiments and will note this in the revision.\n\nPearl, Linear Models: A Useful Microscope for Causal Analysis, Journal of Causal Inference, 2013.\n\nShimizu, LiNGAM: Non-Gaussian Methods for Estimating Causal Structures.\" Behaviormetrika, 2014.\n\nHoyer et al., Estimation of Causal Effects using Linear non-Gaussian Causal Models with Hidden Variables. International Journal of Approximate Reasoning, 2008.\n\nSalehkaleybar et al., Learning Linear non-Gaussian Causal Models in the Presence of Latent Variables, JMLR 2020.\n\nKivva et al., A Cross-Moment Approach for Causal Effect Estimation, NeurIPS 2023.\n\nPeters et al., Elements of Causal Inference: Foundations and Learning Algorithms, 2017.\n\nÅström and Murray, Feedback Systems: An Introduction for Scientists and Engineers, 2008.\n\nLjung, System Identification: Theory for the User, 1999.\n\nEriksson and Koivunen, Identifiability, Separability, and Uniqueness of Linear ICA Models.\" IEEE Signal Processing Letters, 2004.\nShimizu et al., A Linear non-Gaussian Acyclic Model for Causal Discovery, JMLR, 2006.\n\nGolovin, Daniel, and Andreas Krause. \"Adaptive submodularity: Theory and applications in active learning and stochastic optimization.\" Journal of Artificial Intelligence Research 42 (2011)"}, {"review_id": "iT5tWbKjWY", "reviewer": "Reviewer_p51C", "summary": "The authors characterize graphically the equivalence class of graphs learnable from observational data as a bipartite graph where each node represents the ith row of the matrix (I-W) and an edge in the matching only exists if the jth entry of W is nonzero. Each valid permutation over rows defines a perfect matching. So distribution-equivalent graphs are row permutations consistent with matchings in the bipartite graph.", "questions": "Questions: \n\nIn appendix E the algorithm seems to do less favorably on dense graphs with a max of 60 nodes. Why is that? It seems the graphical structure might have something to do with it since all the methods appear to be doing nearly the same (qualitatively the algorithm is performing like max degree). Since erdos renyi graphs are so well-studied, is there some graphical statistic that could be used to explain when the adaptive algorithm will in particular do better than a max degree heuristic?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "strengths:\n\n- significance: the authors nicely set up the technical difficulty of learning with observational and interventional data with cycles. \n- quality: the paper contributes nice constructions and characterizations to this problem. The graphical characterization is nice, and the characterization of what is learned by intervening is nice. (I am not enough of an expert to know whether these characterizations are immediate or not). This reduces the combinatorial search problem quite a bit. The authors construct an adaptive search procedure with appealing properties, given access to a sampler over the space of perfect matchings, which is a relatively friendly object. The paper is a nice end-to-end procedure (given the output of ICA) that relates to fairly classical graphical ideas. \n\nweaknesses: \n\n- relevance: it's not so clear when causal discovery in cyclic graphs is relevant, what are the new potential real-world cases of causal discovery where you have both observational data and the capacity to run interventions that this can enable? the simulations are on random graphs and therefore not illuminating of the potential real-world relevance. \n\n\n- significance: \n\n-- The paper is a good characterization of the \"interventional\" part of causal discovery under observational+interventional data with cycles. It's not how the characterizations and approach of this paper are connected to the \"observational\" part of learning, ie from finite samples. The paper could be improved by exploring this front. \n-- The development of the adaptive algorithm enjoys a lot of relatively tractalbe structure. The objective is to find the set I that minimizes the size of the reduced equivalence class |Ω(I,ϕ)|. However, a lot of later characterizations seem to rely quite heavily on the uniform prior assumption. For example, I'm a little confused by this, \"Therefore, prior to an intervention, the probability that v is matched to row rzi is pi = ni/N.\", is this at the first step with the uniform prior, or at intermediate later timesteps as well? \n\nThe empirical analysis is a good proof of concept but not super thorough\n\n- clarity\n\nOverall good, but the paper could benefit from some explanations at certain places. I will put some questions here because they are more for expository purposes (and not really questions that I need answers to \"in order to improve my score\" as in the other box.)\n\nQuestions: \n- what is the SCC that is preserve in Fig 4b? \n- Why does intervening on variable xi, 218 identifies the row corresponding to xi. how should i interpret this / why is this different than interventions in the acyclic case? ]\n- What is the interpretation of (I-W) and its rows/permutations? \n- this is confusing: \nposterior distribution over realizations conditioned on consistency with all\n274 observations in ψ\n- \"Figures 2a and 2b show the average number of interventions under each strategy.\"\nTo do what? Recover the full graph? Exhaust the nodes? What feedback does the algorithm get to know that it's discovered the whole graph?", "was_revised": true, "final_justification": "I have read the reviews and rebuttal and maintain my score of accept. I am satisfied with the rebuttal response.", "rebuttal": "* Topic 1: Real-World Relevance of Cyclic Causal Discovery: In many real-world systems, feedback loops among variables play a crucial role in maintaining stability. These loops often induce cycles in the system's causal graph, particularly when temporal dynamics are sampled at a low rate or when modeling the system at equilibrium (Bongers et al., 2021). A prominent example is gene regulatory networks (GRNs), where sets of biological regulators interact to control the expression levels of proteins. A GRN can be represented by a directed graph, where nodes correspond to genes, and a directed edge from gene X to gene Y indicates that activation of gene X may directly promote or inhibit gene Y. An intervention on a gene typically involves \"knocking out\" that gene, which corresponds to removing all incoming edges to it. The objective is to recover the underlying causal structure of the GRN using both observational data and strategically designed interventions.\n* Topic 2: Uniform Prior Assumption: The uniformity assumption holds not only at the first step, but also throughout all intermediate steps of the adaptive process. At each round, the algorithm maintains the current interventional-equivalence class $\\Omega_t$, which consists of the set of graphs consistent with all observations and interventions so far. \nWe assume a uniform prior over the initial class $\\Omega_0$, and the posterior over the current class $\\Omega_t$ remains uniform as it is simply a filtered subset of $\\Omega_0$ consistent with the history. Note that we do not impose a new uniform prior at each step; rather, the uniform distribution over $\\Omega_t$ is inherited from the initial uniform prior and updated by eliminating graphs inconsistent with observed interventional outcomes. This induces a categorical distribution over matchings of any variable $v$, based on how often each row $r_i$ appears as a match to $v$ across the remaining graphs. Specifically, if $\\Omega_t = \\lbrace g_1,\\dots,g_{N_t} \\rbrace$, and $n_i$ of those graphs match $v$ to row $r_{z_i}$, then the probability that $v$ is matched to $r_{z_i}$ is $p_i = \\frac{n_i}{N_t}.$\nThis logic is valid at the first step (where $\\Omega_0$ is the full equivalence class) and at every later step, since the posterior is uniform over the consistent subset of graphs $\\Omega_t$. The structure of our bipartite matching formulation allows this uniformity to be efficiently updated after each intervention, preserving tractability throughout the algorithm.\n* Topic 3: Clarification of Technical Details\n    * What SCC is being preserved in Fig. 1b?\n    In Fig. 1b, we do not depict the full SCC; rather, we illustrate a subset of nodes from a single SCC to emphasize a key property: cycle reversion preserves the SCC structure. That is, even after applying cycle reversion, any two nodes that belonged to the same SCC remain mutually reachable, and therefore still lie in the same SCC.\nWe agree that the caption “SCCs are preserved after CR” and the limited scope of the illustration might be slightly misleading, as the figure shows only a portion of the SCC. A more accurate caption would clarify that the figure highlights two representative nodes from an SCC to demonstrate that their mutual reachability remains intact after reversion. We will revise the caption accordingly in the final version to avoid this ambiguity.\n    * Why does intervening on variable $x_i$ identify its row?\n    The key idea is that, in linear **cyclic models** with non-Gaussian noise, the observational distribution alone is not sufficient to uniquely identify the causal graph. Instead, it yields the matrix $W$ only up to an unknown row permutation, due to a cycle reversion (CR) ambiguity.\nAs stated in Proposition 5.1, intervening on a single variable $x_i$ allows us to recover the true $i$-th row of the causal matrix $W$. The intuition is that the intervention modifies the structural equation of $x_i$ (by cutting its incoming edges), so the corresponding row in $W$ is zeroed out under the intervention. Comparing the ICA results from observational and interventional data reveals exactly which row in the observational matrix has been \"removed,\" thus revealing the true position of row $i$ in $W$.\nIn the bipartite matching view, this means that the matching edge $(r_{\\pi^{-1}(i)}, i)$ becomes identifiable, and the row $r_{\\pi^{-1}(i)}$ is assigned definitively to column $i$ in the true permutation. This effectively fixes one row of the matrix and reduces the uncertainty for subsequent steps of the algorithm.\n      * Why this differs from the acyclic case: In linear **acyclic** models with non-Gaussian noise (i.e., LiNGAM), the causal matrix $W$ is uniquely identifiable from observational data alone due to its triangular structure. No permutation ambiguity arises, and thus interventions are not required to disambiguate the matching. In contrast, cyclic models allow multiple observationally equivalent graphs (related via cycle reversion), and resolving this ambiguity necessitates interventional data.\n    * Interpretation of $I-W$ and its row permutations:\n    The matrix $I - W$ corresponds to the reduced-form representation of a linear structural causal model (SCM). In a general SCM, each variable $x_i$ is defined as a function of its parents: $x_i = f_i(\\mathrm{PA}_{x_i}, e_i)$, and under linearity, the system can be written compactly as $x = Wx + e$. Solving for $x$, we obtain the reduced-form expression $x = (I - W)^{-1} e$, which expresses each variable as a linear combination of the exogenous noise terms. This reduced form is particularly useful because it captures the overall dependencies between variables and exogenous noise terms and allows for direct estimation from data using ICA.\nDue to ICA's identifiability only up to row permutations and scaling, the rows of the estimated $I - W$ may appear permuted. These row permutations correspond to different assignments of structural equations to variables. In particular, these permutations arise from **cycle reversion** ambiguities, where feedback loops in the causal graph can be flipped without changing the observational distribution. Our method resolves these ambiguities through targeted interventions.\n    * Confusion about posterior distributions.\n    We agree that the phrasing may be unclear without context. As formalized in our definitions, $\\Phi \\sim \\psi$ denotes the posterior distribution over the set of realizations (causal graphs) that are consistent with all observational and interventional outcomes recorded in the current partial realization $\\psi$. Each intervention in $\\psi$ provides constraints that eliminate inconsistent graphs from the original equivalence class $\\Omega$. The remaining feasible graphs—those that agree with all observations in $\\psi$—define a subset $\\Omega(\\psi) \\subseteq \\Omega$. \nWe assume a uniform prior over $\\Omega$, and thus maintain a **uniform posterior** over the remaining consistent graphs in $\\Omega(\\psi)$. All graphs that contradict any observation in $\\psi$ are assigned zero probability. In other words, the expression “posterior distribution conditioned on consistency with $\\psi$” simply refers to a uniform distribution over the surviving graphs after filtering out those incompatible with the outcomes observed so far. We will clarify this wording in the final version to improve readability.\n    * Stopping Criterion and Interpretation of Intervention Count in Figures 2a and 2b:\n    Figures 2a and 2b report the average number of interventions required to achieve full causal identification of the underlying graph—i.e., to uniquely recover the true matrix $W$.\nThe algorithm receives feedback in the form of structural constraints imposed by each intervention (i.e., fixing one row of $W$). As described in the first line of Algorithm 1, the stopping condition is triggered when the bipartite graph—whose edges represent remaining candidate matchings—is reduced to a **unique perfect matching**. This indicates that the row permutation ambiguity has been fully resolved and that all causal edges have been identified. Thus, the number reported in the figures reflects how many interventions are needed until this condition is met.\n    * Justification of performance on dense graphs:\n    In dense Erdős–Rényi graphs, most variables might have many parents, which leads to a large number of candidate matchings in the bipartite graph. As a result, the posterior distribution $\\mathbf{p}_v$ over possible rows for each node $v$ becomes nearly uniform, making the information gain $L(\\mathbf{p}_v)$ roughly the same for all nodes. This flattens the adaptive gain landscape and causes our method to behave similarly to simple heuristics like MAX-DEGREE, but still outperform those heuristics.\nIn contrast, for sparse graphs, the posteriors $\\mathbf{p}_v$ are more peaked (some values are close to 1), so the adaptive strategy can better prioritize \"high-information\" nodes and terminate faster.\n\nBongers et al., Foundations of Structural Causal Models with Cycles and Latent Variables, The Annals of Statistics, 2021"}]

Author rebuttal:

Meta-review: The paper focuses on intervention design in cyclic linear non-Gaussian models. It proposes a greedy policy for the interventions with near-optimal guarantees and a sampling-based estimator to efficiently estimate the reward function without enumerating all graphs in the (I)MEC. The reviewers acknowledge that the paper proposes a novel and well-founded theoretical analysis and method, mentioning also that the paper is very clearly written and rigorous. On the other hand, the reviewers raised a few minor issues regarding using more ablation and comparisons in the experimental evaluation, and regarding the significance, given its constraining parametric assumptions and single-node interventions. The authors provided several ablations and additional experimental results in the rebuttal, as well as a sketch of a generalization to imperfect and multi-node interventions, thus addressing in detail all of the reviewers' concerns. Overall, I agree with the reviewers that this is an interesting and theoretically sound contribution to the intervention design literature and hence recommend the paper's acceptance.
Decision: Accept (spotlight)