Boosting Causal Discovery via Adaptive Sample Reweighting
Authors: An Zhang
Fangfu Liu
Wenchang Ma
Zhibo Cai
Xiang Wang
Tat-Seng Chua
Venue: ICLR 2023 poster (2023)
Keywords: Causal Structure Learning
Score-based Causal Discovery
Adaptive Sample Reweighting

Abstract: Under stringent model type and variable distribution assumptions, score-based causal discovery methods learn the directed acyclic graph (DAG) from observational data by evaluating candidate graphs over an averaged score function. Despite the great success in low-dimensional linear systems, it has been observed that these approaches overly exploits easier-to-fit samples, thus inevitably learning spurious edges. Worse still, the common homogeneity assumption of most causal discovery methods can be easily violated due to the widespread existence of heterogeneous data in the real world, resulting in performance vulnerability when noise distributions vary. We propose a simple yet effective model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore for short, where the learned weights tailors quantitatively to the important degree of each samples. Intuitively, we leverage the bilevel optimization scheme to alternatively train a standard DAG learner first, then upweight the samples that the DAG learner fails to fit well and downweight the samples that the DAG learner easily extracts the causation information from. Extensive experiments on both synthetic and real-world datasets are carried out to validate the effectiveness of ReScore. We observe consistent and significant boosts in structure learning performance. We further visualize that ReScore concurrently mitigates the influence of spurious edges and generalizes to heterogeneous data. Finally, we perform theoretical analysis to guarantee the structure identifiability and the weight adaptive properties of ReScore. Our codes are available at https://github.com/anzhang314/ReScore.

Published as a conference paper at ICLR 2023
BOOSTING DIFFERENTIABLE CAUSAL DISCOVERY VIA ADAPTIVE SAMPLE REWEIGHTING
An Zhang Fangfu Liu', Wenchang Ma², Zhibo Cai', Xiang Wang" Tat-seng Chua Sea-NExT Joint Lab, "National University of Singapore, Tsinghua University RRemmin University of China, UUniversity of Science and Technology of China anzhangêu. nus edu, liuffl tetailemalle ts tsinghua. edu, en, e0724290uu mus.edu caizhiboß ruc. edu. cn, xiangwang122 gmail com, descts@nuse edu.
ABSTRACT
Under stringent model type and variable distribution assumptions, differentiable score-based causal discovery methods learn a directed acyclic graph (DAG) from observational data by evaluating candidate graphs Despite great success in low-dimensional linear systems, it has been observed that these approaches overly exploit easier-to-fi samples, thus inevitably learning spurious edges. Worse still, the common homogeneity assumption can be easily violated, due to the widespread existence of heterogeneous data in the real world, resulting in performance vulnerability when noise distributions vary. We propose simple yet effective model-agnostic framework boost causal discovery per- formance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore for short, where the weights tailor quantitatively portance degree of each sample. Intuitively, we leverage the bilevel optimization scheme to alternately train a standard DAG learner and reweight samples that upweight the samples the learner fails to fit and downweight the samples that the learner easily extracts the spurious information from. Extensive experiments on both synthetic and real-world datasets are carried out to validate the effective- ness of ReScore. We observe consistent and significant boosts structure learning performance. Furthermore, influence of spurious edges and generalizes to heterogeneous data. Finally, we perform the theoretical analysis guarantee the structure identifiability and the weight adaptive properties of ReScore in linear systems. Our codes are available https: /gttbbb...tuu//g//// com/ wnzhang314//anm 31//eecore.
average score function.
the im-
visualize that ReScore concurrently mitigates the
INTRODUCTION
Learning causal structure from purely observational data (i.e., causal discovery) is a fundamental but daunting task (Chickering et al., 2004; Shen et al., 2020). strives to identify causal relationships between variables and encode the conditional independence as a directed acyclic graph (DAG). Differentiable score-based optimization is crucial enabler of causal discovery (Vowels al., 2021). Specifically, it is formulated as continuous constraint optimization problem by minimizing the average score function and a smooth acyelicity constraint. To ensure the structure is fully or partially identifiable (see Section 2), researchers impose stringent restrictions on model parametric family (e.g., linear, additive) and common assumptions of variable distributions (e.g., data homogeneity) (Peters et al., 2014; Ng et al., 2019a). Following this scheme, recent follow-on studies (Kalainathan al., 2018; Ng et al., 2019 9b; Zhu et al., 2020; Khemakhem al., 2021; Yu et al., 2021) extend the formulation to general nonlinear problems by utilizing a variety of deep learning models.
However, upon careful inspections, we spot and justify two unsatisfactory behaviors of the current differentiable score-based methods:
Differentiable score-based causal discovery is error-prone learning spurious edges or reverse causal directions between variables, which derails the structure learning accuracy (He et al., 2021;
"Xiang Wang is the corresponding author, also with the Institute of Artificial Intelligence, Hefei Compre- hensive National Science Center.

---

Published as a conference paper at ICLR 2023
B
B
NOTEARS
A
E (222)
SHD
SHD
SHD =
(N,),),, P1 (0.0..1)
B
B
Es
NOTEARS
+ ReScore
A
C
A
A
= 2B + EC- N(O.1)
SHD=
SHD =
SHD = P1 = O,P2 =1
P1
L, 0
P1
0.2, Pz 0.8
Figure 1: A simple example of basic chain structure that NOTEARS would learn spurious edges while ReScore can help to mitigate the bad influence.
Ng et al., 2022). We substantiate our claim with an illustrative example as shown in Figure (see another example Appendix 1.3. We find that even the fundamental chain structure in linear system is easily misidentified by the state-of-the-an method, NOTEARS (Zheng et al., 2018).
Despite being appealing in synthetic data, differentiable score-based methods suffer from severe performance degradation when encountering heterogeneous data (Huang et al., 2020; 2019). Con- sidering Figure again, NOTEARS is susceptible to learning redundant causations when the dis- tributions of noise variables vary.
Taking a closer look at this dominant scheme (i.e., optimizing the DAG learner via an average score function under strict assumptions), we ascribe these undesirable behaviors to its inherent limitations:
The collected datasets naturally include an overwhelming number of easy samples and small number of informative samples that might contain crucial causation information (Shrivastava et al., 2016). Averagely scoring the samples deprives the discovery process of differentiating sample importance, thus easy samples dominate the learning of DAG. As a result, prevailing score-based techniques fail to learn true causal relationship but instead yield the easier-to-fit spurious edges.
Noise distribution shifts are inevitable and common in real-world training, as the observations are typically collected at different periods, environments, locations, and so forth (Arjovsky et al., 2019). As result, the strong assumption of noise homogeneity for differentiable DAG learner is easily violated in real-world data (Peters et al., 2016). A line of works (Ghassami et al., 2018; Wang et al., 2022) dedicated to heterogeneous data successfully address this issue. However, they often require explicit domain annotations (i.e., ideal partition according to heterogeneity un- derlying the data) for each sample, which prohibitively expensive and hard to obtain (Creager et al., 20 thus further limiting their applicability.
To reshape the optimization scheme and resolve these limitations, we propose to adaptively reweight the samples, which de facto concurrently mitigates the influence of spurious edges and generalizes to heterogeneous data. The core idea to discover and upweight set of less-fitted samples that offer additional insight into depicting the causal edges, compared to the samples easily fitted via spurious edges. Focusing more on less-fitted samples enables the DAG learner to effectively generalize to heterogeneous data, especially in real-world scenarios whose samples typically come from disad- vantaged domains. However, due to the difficulty of accessing domain annotations, distinguishing such disadvantaged but informative samples and adaptively assigning their weights are challenging.
Towards this end, we present a simple yet effective model-agnostic optimization framework, coined ReScore, which automatically learns reweight the samples and optimize the differentiable DAG learner, without any knowledge of domain annotations. Specifically, we frame the adaptive weights learning and the differentiable DAG learning a bilevel optimization problem, where the outer-level problem is solved subject to the optimal value of the inner-level problem:
In the inner loop, the DAG learner is first fixed and evaluated by the reweighted score function to quantify the reliance on easier-to-fir samples, and then the instance-wise weights are adaptively optimized to induce the DAG learner to the worst-case.
In the outer loop, upon the reweighted observation data where the weights are determined by the inner loop, any differential score-based causal discovery method can be applied to optimize the DAG learner and refine the causal structure.
2

---

Published as a conference paper at ICLR 2023
Benefiting from this optimization scheme, our ReScore has three desirable properties. First, it is model-agnostic technique that can empower any differentiable score-based causal discovery method. Moreover, theoretically reveal that the structure identifiability is inherited by ReScore from the original causal discovery method in linear systems (cf. Theorem 1). Second, ReScore jointly miti- gates the negative effect of spurious edge learning and performance drop in heterogeneous data via auto-learnable adaptive weights. Theoretical analysis in Section 3.3 (cf. Theorem 2) validates the oracle adaptive properties of weights. Third, ReScore boosts the causal discovery performance by large margin. Surprisingly, it performs competitively or even outperforms CD-NOD (Huang et al., 2020) and DICD (Wang al., 2022), which require domain annotation, on heterogeneous synthetic data and real-world data (ef. Section 4.2).
2 DIFFERENTIABLE CAUSAL DISCOVERY
We begin by introducing the task formulation of causal discovery and the identifiability issue. We then present the differentiable based scheme optimize the DAG learner.
Task Formulation. Causal discovery aims to infer the Structural Causal Model (SCM) (Pearl, 2000; Pearl et al., 2016) from the observational data, which best describes the data generating procedure. Formally. let X E Raxd be a matrix of observational data, which consists of n independent and identically distributed (i.i.d.) random vectors X = (Xi...., Xa) E Rdd Given X, we aim to learn a SCM (Px, 9). which encodes causal directed acyclic graph (DAG) with structural equation model (SEM) to reveal the data generation from the distribution of variables X. Specifically, we denote the DAG by G (V)),, where (G)) is the variable set and EG)) collects the causal directed edges between variables. We present the joint distribution over X as Px. which is Markov w.E.t. G. The probability distribution function of Px is factored as p(x) I P(æ:/ P(z:] (ea())) where pa(i) = {j E V(9)= X; + X; E E(G)} is the set of parents of variable X; in G and P(r; ((a(t) the conditional probability density function of variable X; given Xpa(t)- As result, the SEM can be formulated as collection of d structural equations:
X; fx ())) No), == .d
where fi : IR Xpacel + R can be any linear or nonlinear function, and N = (N Na) are jointly independent noise variables.
Identifiability Issue. In general, without further assumption on the SEM (cf. Equation 1), it is not possible to uniquely learn the DAG & by only using the observations of Px. This is the identifiability issue in causal discovery (Lachapelle et al., 2020). Nonetheless, with the assumption of the SEM, the DAG G is said to be identifiable over Px. no other SEM can encode the same distribution Px with different DAG under the same assumption. To guarantee the identifiability, most prior studies restrict the form of the structural equations to be additive w.r.t. to noises, i.e., additive noise models (ANM). Assuming ANM, as long the structural equations are linear with non-Gan Gaussian errors (Shimizu et al., 2006; Loh & Bühlmann, 2014), linear Gaussian model with equal noise variances (Peters & Bühlmann, 2014), nonlinear structural equation model with mild conditions (Hoyer et al., 2008; Zhang& & Hyvarinen, 2009; Peters et al., 4), then the DAG G is identifiable.
Solution to Causal Discovery. Prevailing causal discovery approaches roughly fall into two lines: constraint- and score-based methods (Spirtes & Zhang, 2016; Glymour et al., 2019). Specifically, bonstraint-based methods (Spirtes et al., 1995; Spirtes & Glymour, 1991; Colombo al., 2012) determine up to the Markov equivalence class of causal graphs, based on conditional independent tests under certain assumptions. Score-based methods (Vowels et al., 2021) evaluate the candidate graphs with a predefined score function and search the DAG space for the optimal graph. Here we focus on the cosse-based line.
Score-based Causal Discovery. With slight abuse of notation, G refers to a directed graph in the rest of the paper. Formally, the score-based scheme casts the task of DAG learning as a combinatorial optimization problem:
mjn S(9;)) = L(G;X) + RR (G) s.t. G DAG,
Here this problem consists of two ingredients: the combinatorial acyclicity constraint 9 E DAA and the score function S(G; X). The score function composes two terms: (1) the goodness-of-fit
3

---

Published as a conference paper at ICLR 2023
a Ei= (fx, f(x)), where 1(x, fxx)) represents the loss of fitting observation x;; (2) the sparsity regularization Rxpase (9) stipulating that the total number of edges g should be penalized; And À is a hyperparameter controlling the regularization strengths. Next, will elaborate on the previous implementations of these two major ingredients.
measure (():X)= -
To implement S X), various approaches have been proposed, such as penalized least-squares loss (Zheng et al., 2020; 2018; Ng et al., 2019b), Evidence Lower Bound (ELBO) (Yu et al., 2019), log- likelihood with complexity regularizers (Kalainathan et al., 2018; Van de Geer & Bühlmann, 2013; Ng et al., 2020), Maximum Mean Discrepancy (MMD) (Goudet et al., 2018), Bayesian Information Criterion (BIC) (Geiger Heckerman, 1994; Zhu et al., 2020), Bayesian Dirichlet equivalence uniform (BDeu) score (Heckerman et al., 1995), Bayesian Gaussian equivalent (BGe) score (Kuipers al., 2014), 4), and others (Huang et al., 2018; Bach & Jordan, 2002; Sokolova et al., 2014).
As G E DAG enforces G to be acyclic, it becomes the main obstacle to the score-based scheme. Prior studies propose various approaches to search in the acyclic space, such as greedy search (Chickering, 2002; Hauser & Bühlmann, 2012), hill-climbing (Gámez et al., 2011: I; Tsamardinos et al., 2006), dynamic programming (Silander & Myllymäki, 2006; Koivisto Sood, 2004), A (Yuan & Malone, 2013), integer linear programming (Jaakkola et al., 2010; Cussens, 2011).
Differentiable Score-based Optimization. Different from the aforementioned search approaches, NOTEARS (Zheng et al., 2018) reframes the combinatorial optimization problem continuous constrained optimization problem:
min X(G;X) s.L. H()) O,
where H()) 0 is a differentiable equality DAG constraint.
As for the DAG constraint H()) = O, the prior effort (Zheng et al., 2018) turns to depict the "DAGness" of G's adjacency matrix A(g) {0, 1] 1]axd Specifically, [A(g)]s
if the causal
edge X; + X; exists in E'G)), otherwise [A(9)k; = 0. Prevailing implementations of DAGness constraints are H())= = TBA) d (Zheng et al., 2018), H = Tr((1 + a @ AA d (Yu al., 2019), and others (Wei al., 2020; Kyono al., 2020; Bello al., 2022; Zhu et al., 2021). As a result, this optimization problem in Equation 3 can be further formulated via the augmented Lagrangian method as:
min X));X) + PDAG(G), 9
(4)
where PDAG(g) = (G + (9) is the penalty term enforcing the DAGness on G, and p is a penalty parameter and a is the Lagrange multiplier.
3 METHODOLOGY OF RESCORE
On the basis of differentiable score- based causal discovery methods, we first devise our ReScore and then present its desirable properties.
3.1 BILEVEL FORMULATION RESCORE
Aiming to learn the causal structure accurately in practical scenarios, we focus on the observational data that heterogeneous and contains a large proportion of easy samples. Standard differentiable score-based causal discovery methods apply the average score function on all samples eamleeseuully. which inherently rely on easy samples to obtain high average goodness-of is error-prone to constructing easier-to-fi fit spurious edges based on the easy samples, while ignoring the causal relationship information maintained in hard samples. Assuming the oracle importance of each sample is known at hand, we can assign distinct weights to different samples and formulate the reweighted score function S. (9: X). instead of the average score function:
As a result, the DAG learner
(): = L. (G: X) + XR sparse (g) = Σ w,l(xx, fxx)) + XR XRsparse
(5)
where w = (w.,..., wr, is a sample reweighting vector with length n, wherein w; indicates the importance of the i-th observed sample x,.
4

---

Published as a conference paper at ICLR 2023
However, the oracle sample importance is usually unavailable in real-world scenarios. The problem, hence, comes to how to automatically learn appropriate the sample reweighting vector w. Intuitively, samples easily fitted with spurious edges should contribute less to the DAG learning, while samples that do not hold spurious edges but contain critical information about causal edges should be more importance. We therefore use a simple heuristic of downweighting the easier-to-fit but less informa- tive samples, and upweighting the less-fitted but more informative samples. This inspires us to learn to allocate weights adaptively, with the aim of maximizing the influence of less well-fitted samples and failing the DAG learner. Formally, we cast the overall framework of reweighting samples to boost causal discovery as the following bilevel optimization problem:
min Sw- (G; X) + (9)
g
w E arg max (9; WEC(r)
(6)
1] for the cutoff threshold r E (0, 1). The deviation of the weight distribution from the uniform distribution is bound by the hyperparam- eter т. Clearly. Equation 6 consists of two objectives, where the inner-level objective (i.e., optimize w by maximizing the reweighted score function) is nested within the outer-level objective (i.e., op- timize G by minimizing the differentiable score-based loss). Solving the luter-level problem should be subject to the optimal value of the inner-level problem.
where C(T) = {w: 0 Wi,..., Wnn S -.
Now we introduce how to solve this bilevel optimization problem. In the inner loop, we first fix the DAG learner which evaluates the error of each observed sample x;, Vi E {1, ,.]. and then maximize the reweighted score function to learn the weight w correspondingly. In the outer loop, upon the reweighted observations whose weights are determined in the inner loop, we minimize the reweighted score function to optimize the DAG learner. By alternately training the inner and outer loops, the importance of each sample is adaptively estimated based on the DAG learner's error, and in turn gradually guides the DAG learner to perform better the informative samples. It is worth highlighting that this ReScore scheme can be applied to any differentiable score-based causal discovery method listed in Section 2. The procedure of training ReScore is outlined in Algorithm 1.
Furthermore, our ReScore has the following desirable advantages:
As shown in Section 3.2, under mild conditions, our ReScore inherits the identifiability property of the original differentiable score-based causal discovery method.
ReScore is able to generate adaptive weights to observations through the bilevel optimize, so as to distinguish more information samples and fulfill their potentials to guide the DAG learning, This is consistent with our theoretical analysis in Section 3.3 and empirical results in Section 4.2.
ReScore is widely applicable to various types of data and models. In other words, it is model- agnostic and can effectively handle heterogeneous data without knowing the domain annotations in advance. Detailed ReScore performance can be found in Section 4.
3.2 THEORETICAL ANALYSIS ON IDENTIFIABILITY
The graph identifiability issue is the primary challenge hindering the development of structure learn- ing. As an optimization framework, the most desired property of ReScore is the capacity to ensure graph identifiability and substantially boost the performance of the differentiable score-based DAG learner. We develop Theorem I that guarantees the DAG identifiability when using ReScore.
Rendering DAG theoretically identifiable requires three standard steps (Peters et al., 2014; Zheng al., 2020: Ng et al., 2022): (1) assuming the particular restricted family of functions and data distributions of SEM in Equation 1; (2) theoretically proving the identifiability of SEM; and (3) developing an optimization algorithm with a predefined score function and showing that learned DAG asymptotically converges to the ground-truth DAG. Clearly, ReScore naturally inherits the original identifiability of a specific SEM as stated in Section 2. Consequently, the key concern lies on the third step- whether the DAG learned by our new optimization framework with the reweighted score function (g; X) can asymptoticalll converge to the ground-trum -trut DAG. To address this, we present the following theorem. Specifically, it demonstrates that. by guaranteeing the equivalence of optimization problems (Equation and Equation 6) in linear systems, the bounded weights will not affect the consistency results in identifiability analysis. See detailed proof in Appendix C.I.
5

---

Published as a conference paper at ICLR 2023
Theorem 1. Suppose the SEM in Equation 1 is linear and the size of observational data X is As the data size increases, i.e,, n - oc,
arg min { (9; PDac(()) arg min (S(G:X) (
PDAG(9)) m.S.,
9
in the following cases:
a. Using the least-squares loss L(G;X)=
1 X f( 2n
b. Using the negative log-likelihodd loss with standard Gaussian noise.
Remark: The identifiability property of ReScore with two most common score functions, namely least-square loss and negative log- rigllikelihood loss, is proved in Theorem 1. Similar conclusions can be easily derived for other loss functions, which we will explore in future work.
3.3 ORACLE PROPERTY OF ADAPTIVE WEIGHTS
Our ReScore suggests assigning varying degrees of importance to different observational samples. At its core is the simple yet effective heuristic: the less-fitted samples are more important than the easier-to-fit samples, they do not hold spurious edges but contain critical information about the causal edges. Hence, mining hard-to-learn causation information promising to help DAG learners mitigate the negative influence of spurious edges. The following theorem shows the adaptiveness property of ReScore, ie., instead of equally treating all samples, ReScore tends to upweight the im- portance of hard but informative samples while downweighting the reliance on casier-to-fit samples.
Theorem 2. Suppose that in the oplimization phase, the i-th observation hus larger error than the j-th observation in the sense that (xx,, [xx))
) > 1xx;, J(xx( (x,)), where i E (I....,n). Then,
w 2w,
where wt, W. are the optimal weights in Equation The equality holds if and only if = wz or : = = Tm
See Appendix C.2 for the detailed proof. It is simple to infer that, following the inner loop that maximizes the reweighted score function (9; X). the observations are ranked by learned adaptive weights w That is, one observation equipped with higher weight will have a greater impact on the subsequent outer loop to dominate the DAG learning.
4 EXPERIMENTS
We aim to answer the following research questions:
As model-agnostic framework, can ReScore widely strengthen the differentiable score- based causal discovery baselines?
RQI:
RQ2: How does ReScore perform when noise distribution varies? Can ReScore effectively learn the adaptive weights that successfully identify the important samples?
Baselines. To answer the first question (RQ1), we implement various backbone models including NOTEARS (Zheng al., 2018) and GOLEM (Ng et al., 2020) linear systems, and NOTEARS- MLP (Zheng et al., 2020), and GraN-DAG (Lachapelle et al., 2020) in nonlinear settings. To answer compare GOLEM+ReScore. SOTEARS-MLP-RRSSONE MLP+ReScore to a SOTA
the second question (RQ2),
baseline CD-NOD (Huang et al., 2020) and recently proposed approach DICD (Wang et al., 2022), which both require the ground-truth domain annotation. For comprehensive comparison, extensive experiments are conducted both homogeneous and heterogeneous synthetic datasets well as real-world benchmark dataset, i.e., Sachs (Sachs et al., 2005). Sachs, GES (Chickering, 2002), a benchmark discrete score-based causal discovery method, is also considered. A detailed description of the employed baselines can be found Appendix D.I.
Evaluation Metrics. To evaluate the quality of structure learning, four metrics reported: True Positive Rate (TPR), False Discovery Rate (FDR), Structural Hamming Distance (SHD), and Struc- tural Intervention Distance (SID) (Peters & Bühlmann, 2015), averaged over ten random trails.

---

Published as a conference paper at ICLR 2023
Table I: Results for ER graphs of 10 nodes on linear and nonlinear synthetic datasets.
ER2
ER4
TPR
F
SHD
SID
TPR
FDR
SHID
SID
Ramdom
0.08
0.93:au
53,2215
95 62122
0.092a.
0.93
$2.3
8033
NOTEARS
0.85
0.07
5.8273
20,855
0.79g
D.09
10.0a50
25.8:99
ReScore
0.89 L.89
1.08.
125
4.6.25
12.8
0.85
0.05 1a55
GOLEM
0.222o0
6.5
13.0a67
0.63230
0.16
17.2213
ReSeore
0.88
0.21 2011
6.0
12.4
0.06
0.17
16.2
46.7 16.7
NOTEARS-MLP'
0. 0.76
7.0a15
17.9
0.83
0.21
10,9:19
28. 28.6e112
ReScore
0.73 4%
0.10 Rin
6.839
20-3
0.94 HARE
0.15 oe 4455
1200%
GraN-DAG
2.7
8,70
0.98.300
0.12:
5.411
7.70
ReScore
0,90
2.4
7.20
0.90
0.11
2,80
1.50
322
342
-00
(d) SID w.r. X Figure 2: Performance comparison between NOTEARS- and ReScore on ER4 graphs of 10
(a) TPR W.E.. X
(b) FDR W.L. À
SHD w.r.f
nodes nonlinear synthetic datasets. The hyperparameter À defined in Equation 2 refers to the graph sparsity. See more results in Appendix D.4
4.1 OVERALL PERFORMANCE COMPARISON ON SYNTHETIC DATA (RQ1)
Simulations. The generating data differs along three dimensions: number of nodes, the degree of edge sparsity, and the type of graph. Two well-known graph sampling models, namely Erdos-Renyi (ER) and scale-free free (SF) (Barabási & Albert, 1999) are considered with kd expected edges (denoted as ERK or SFk) and d {10, 210,20, 50) nodes. Specifically, in linear settings, similar (Zheng et al. 2018; Gao et al., 2021), the coefficients are assigned following U-2 - -0.5) U U 2) with additive standard Gaussian noise. In nonlinear settings, following (Zheng et al., 2020), the ground- truth SEM in Equation| 1 is generated under the Gaussian process (GP) with radial basis function kernel of bandwidth one, where fi(-) is additive noise models with N₁ as an i.i.d. random variable following standard normal distribution. Both of these settings are known to be fully identifiable (Peters & Bühlmann, 2014; Peters et al., 2014). For each graph, 10 data sets of 2,000 samples are generated and the mean and standard deviations of the metrics reported for fair comparison.
Results. Tables 1, 9 and Tables in Appendix D.4 report the empirical results on both linear and nonlinear synthetic data. The emror bars depict the standard deviation across datasets over trails. The red and blue percentages separately refer to the increase and decrease of ReScore relative to the original score-based methods in each metrie, The best performing methods are bold. We find that:
ReScore consistently and significantly strengthens the score-based methods for structure learning across all datasets. In particular, it achieves substantial gains over the state-of-the-an baselines by around 3% to 60% in terms of SHD, revealing a lower number of missing, falsely detected, and reversed edges. We attribute the improvements to the dynamically learnable adaptive weights, which boost the quality of score-based DAG learners. With a closer look at the TPR and FDR. ReScore typically lowers FDR by eliminating spurious edges and enhances TPR by actively identifying more correct edges. This clearly demonstrates that ReScore effectively filters and upweights the more informative samples to better extract the causal relationship. Figure? also illustrates the clear trend that ReScore is excelling over NOTEARS-MLP as the sparsity penalty climbs. Additionally, as Table indicates, ReScore only adds a negligible amount of computational complexity as compared to the backbone score-based DAG learners.
Score-based causal discovery baselines suffer from severe performance drop on high- dimensional dense graph data. Despite the advances, beyond linear, NOTEARS-MLP and GraN-DAG fail to scale to more than 50 nodes in SF4 and ER4 graphs, mainly due to difficulties in enforcing acyclicity in high- digh-dimensional dense graph data (Varando, 2020; Lippe et al., 2022). Specifically, the TPR of GraN-DAG and NOTEARS-MLP in SF4 of 50 nodes is lower than 0.2, which indicates that they are not even able to accurately detect 40 edges out of 200 ground-truth edges. ReScore, as an optimization framework, relies heavily on the performance of the score-
7

---

Published as a conference paper at ICLR 2023
(a) Weights on linear data at the 1st and last epochs (b) Weights on nonlinear data at the 1st and last epochs
Figure 3: Illustration of adaptive weights learned by ReScore w.r.t sample loss on both linear and
nonlinear synthetic data. For each dataset, the left and right plots refer to the distribution of adaptive weights at the first and last epochs in the outer loop, respectively (i.e., the value of w", when Lą 0 and L K outer in Algorithm respectively). The disadvantaged but more informative samples are represented by the red dots. The dominant and easy samples, in contrast, are in blue.
based backbone model. When the backbone model fails to infer DAG on its own as the number of nodes and edge density increase, adding ReScore will not be able enhance the performance.
4.2 PERFORMANCE ON HETEROGENEOUS DATA (RQ2)
4.2.1 EVALUATION ON SYNTHETIC HETEROGENEOUS DATA
Motivations. It is commonplace to encounter heterogeneous data in real-world applications, of which the underlying causal generating process remain stable but the noise distribution may vary. Specific DAG learners designed for heterogeneous data are prone to assume strict conditions and require the knowledge of group annotation for each sample. Group annotations, however, tremely costly and challenging to obtain. We conjecture that a robust DAG learner is able to suc- cessfully handle heterogeneous data without the information of group annotation.
Simulations. Synthetic heterogeneous data both linear and nonlinear settings (n = 1000, d = 20, ER2) containing two distinct groups are also considered. 10% of observations come from the disadvantaged group, where half of the noise variables N; defined in Equation I follow A 1) and the remaining half of noise variables follow (V 0.1). 90% of the observations, in contrast, are generated from the dominant group where the scales of noise variables are flipped.
Results. To evaluate whether ReScore can handle heterogeneous data without requiring the group annotation by automatically identifying and upweighting informative samples, we compare base- line+ReScore to CD-NOD and DICD, two SOTA causal discovery approaches that rely on group annotations and are developed for heterogeneous data. Additionally, non-adaptive reweighting method called baseline+IPS is taken into account, in which sample weights are inversely propor- tional to group sizes. Specifically, we divide the whole observations into two subgroups. Obviously, a single sample from the disadvantaged group is undoubtedly more informative than a sample from the dominant group, it offers additional insight to depict the causal edges.
As Figure shows, dots of different colours mixed and scattered the beginning of the training. After mul-
Table 2: Results heterogeneous data.
Linear
TPRi
FDR,
SHD.
Nonlinear
TPR:
FDR,
SHD]
GOLEM
0.79
0.33
18.7
NOTEARS-MLP
0.62
0.36
25.8
IPS
0.35
28.7
tiple iterations of training inner and outer loops, the red dots from the dis-
ReScore
0.81
0.24
16.4
ReScore
0.63
0.32
23.8
CD-NOD
0.51
0.17
24.1
CN-NOD
0.60
0.29
26.0
advantaged group are gradually iden- DICD
0.82
DICD
0.50
tified and assigned to relatively larger weights compared to those blue dots with the same measure- of-fitness. This illustrates the effectiveness of ReScore and further offers insight into the reason for its performance improvements when handling heterogeneous data. Overall, all figures show clear positive trends, i.e., the underrepresented samples tend to learn bigger weights. These results vali- date the property of adaptive weights in Theorem 2.
Table 2 indicates that ReScore drives impressive performance breakthroughs in heterogeneous data, achieving competitive or even lower SHD without group annotations compared to CD-NOD and DICD recognized as the lower bound. Specifically, both GOLEM and NOTEARS-MLP are strug- gling from notorious performance drop when homogeneity assumption is invalidated, and posing hurdle from being scaled up to real-world large-scale applications. We ascribe this hurdle to blindly scoring the observational samples evenly, rather than distilling the erucial group information from
8

---

Published as a conference paper at ICLR 2023
distribution shift of noise variables. To better highlight the significance of the adaptive property, we also take Baseline+IPS into account, which views the ratio of group size as the propensity score and exploits its inverse to re- re-weight each sample's loss. Baseline+IPS suffers from severe perfor- mance drops in terms of TPR, revealing the limitation of fixed weights. In stark contrast, benefiting from adaptive weights, ReScore accomplish more profound causation understanding, leading to higher DAG learning quality. This validates that ReScore endows the backbone score-based DAG learner with better robustness against the heterogeneous data and alleviates the negative influence of spurious edges.
even extract group information from heterogeneous data that
4.2.2 EVALUATIONS ON REAL HETEROGENEOUS DATA.
Sachs (Sachs et al., 2005) contains the measurement of multiple phos- phorylated protein and phospholipid components simultaneously in large number of individual primary human immune system cells. In Sachs, nine different perturbation conditions are applied to sets of individual cells, each of which administers certain reagents to the cells. With the anno- tations of perturbation conditions, consider the Sachs as real-world het-
Table 3: The performance comparison Sachs dataset.
1PR
FDR
SHD J SID
#Predieted Edges
Random
0.076
0.899
23
63
22
GOLEM
0.176
0.026
53
ReScore
0.294
0.063
14
49
NOTEARS-MLP
0.412
0.632
16
45
19
ReScore
0.412
0.500
43
GraN-DAG
0.294
0.643
16
60
14
+ ReScore
0.353
0.600
15
58
GES
0.294
0.853
ReScore
0,588
0.722
28
50
36
CD-NOD
0.588
0.444
erogeneous data (Mooij et al., 2020). We train baselines on 7,466 samples, where the ground-truth graph (11 nodes and 17 edges) is widely accepted by the biological community.
As Table illustrates, ReScore steadily and prominently boosts all baselines, including both differ- entiable and discrete score-based causal discovery approaches w.r.f. SHD and SID) metrics. This clearly shows the effectiveness of ReScore to better mitigate the reliance on casier-to-fit samples. With a closer look at the TPR and FDR, baseline+ReScore surpasses the state-of-the- correspond- ing baseline by a large margin in most cases, indicating that ReScore can help successfully predict more correct edges and fewer false edges. Remarkably, compared to CD-NOD, which is designed for heterogeneous data and utilizes the annotations as prior knowledge, GES+ReScore obtains com- petitive TPR without using ground-truth annotations. Moreover, GraN-DAG+ can reach the same SHD as CD-NOD when 15 and 18 edges are predicted, respectively. These findings vali- date the potential of ReScore promising research direction for enhancing the generalization and accuracy of DAG learning methods when dealing with real-world data.
CONCLUSION
Today's 's differentiable score-based causal discovery approaches are still far from being able curately detect the causal structures, despite their great success on synthetic linear data. In this paper, we proposed ReScore, a simple-yet-effective model-agnostic optimization framework that simultancously eliminates spurious edge learning and generalizes to heterogeneous data by utiliz- ing learnable adaptive weights. Grounded by theoretical proof and empirical visualization studies, ReScore successfully identifies the informative samples and yields a consistent and significant boost in DAG learning. Extensive experiments verify that the remarkable improvement of ReScore on a variety of synthetic and real-world datasets indeed comes from adaptive weights.
Two aspects of ReScore's limitations will be covered in subsequent works. First, the performance of ReScore is highly related to the causal discovery backbone models, which leads to minor im- provements when the backbone methods fail. Second, having empirically explored the sensitivity to pure noise samples in D.3.2, we will theoretically analyze and further enhance the robustness of ReScore against these noises. It is expected to substantially improve the DAG learning quality, as well as distinguish true informative samples from pure noise samples. We believe that ReScore provides a promising research direction to diagnose the performance degradation for nonlinear and heterogeneous data in the structure learning challenge and will inspire more works in the future.

---

Environment inference for invariant Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research supported by the Sea-NExT Joint Lab, the National Natural Science Foundation of China (9227010114) 14), and CCCD Key Lab of the Ministry of Culture and Tourism.
REFERENCES
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.0289) 2019.
Francis R. Bach and Michael I. Jordan. Learning graphical models with mercer kernels. In NIPS, 2002.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Kevin Bello, Bryon Aragam, and Pradeep Ravikumar. Dagma: Learning dags via m-matrices and log-determinant acyclicity characterization. arXiv preprint arXiv:2209.0803: 022209900077, 2022.
Ruichu Cai, Jincheng Ye, Jie Qiao, Huiyuan Fu, and Zhifeng Hao. Fom: Fourth-order moment based causal direction identification on the heteroscedastic data. Neural Networks, 124:193-201, 2020.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002.
David Maxwell Chickering, David Heckerman, and Christopher Meek, Large-sample learning of bayesian networks is np-hard. Journal of machine learning research, 5:1287-1330, 2004.
Diego Colombo, Marloes H Maathuis, Markus Kalisch, and Thomas S Richardson. Learning high- dimensional directed acyclic graphs with latent and selection variables. The Annals of Statistics, pp. 294-321, 2012.
Elliot Creager, Jörn-Henrik Jacobsen, and Richard Zemel. learning. In ICMI., 2021.
James Cussens. Bayesian network learning with cutting planes. UAI, 2011.
José A Gámez, Juan L Mateo, and José M Puerta. Learning bayesian networks by hill climbing: effi- cient methods based on progressive restriction of the neighborhood. Data Mining and Knowledge Discovery, 22(1):106 1481066618,,,, 2011.
Yinghua Gao, Li Shen, and Shu-Tao Xia. DAG-GAN: causal structure learning with generative adversarial nets. In /CASSP, 2021.
Dan Geiger and David Heckerman. Learning gaussian networks. In UAI, 1994.
AmirEmad Ghassami, Saber Salchkaleybar, Negar Kiyavash, and Kun Zhang. Learning causal structures using regression invariance. In NIPS, 2017.
AmirEmad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domain causal struc- ture learning in linear systems. In NeurlPS, 2018.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graph- ical models. Frontiers in genetics, 10:524, 2019.
Olivier Goudet, Diviyan Kalainathan, Philippe Caillou, Isabelle Guyon, David Lopez-Paz, and Michele Sebag. Learning functional causal models with generative neural networks. In Ex- plainable and interpretable models in computer vision and machine learning, pp. 39-80. 2018.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. Journal of machine learning research, 13:2409- 2464, 2012.
10

---

Published as a conference paper at ICLR 2023
Yue He, Peng Cui, Zheyan Shen, Renzhe Xu, Furui Liu, and Yong Jiang. DARING: differentiable causal discovery with residual independence. In KDD, 2021.
David Heckerman, Dan Geiger, and David M Chickering. Learning bayesian networks: The combi- nation of knowledge and statistical data. Machine learning, 20(3):197-24 -433 1995.
Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In NIPS, 2008
Biwei Huang, Kun Zhang. Yizhu Lin, Bernhard Schölkopf, and Clark Glymour. Generalized score functions for causal discovery. In KDD, 2018.
Biwei Huang, Kun Zhang, Mingming Gong, and Clark Glymour. Causal discovery and forecasting in nonstationary environments with state-space models. ICMI, 2019.
Biwei Huang, Kun Zhang. Jiji Zhang, Joseph D. Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from baterogeneou//nonsaaiionrr data. Journal of machine learning research, 19:893,- 2020.
Tommi S. Jaakkola, David A. Sontag, Amir Globerson, and Marina Meila. Learning bayesian net- work structure using LP relaxations. In AISTATS, 2010.
Diviyan Kalainathan, Olivier Goudet, Isabelle Guyon, David Lopez-Paz, and Michèle Sebag. Struc- tural agnostic modeling: Adversarial learning of causal graphs. arXiv preprint arXiv:1803.0492 2018.
Ilyes Khemakhem, Ricardo Pio Monti, Robert Leech, and Aapo Hyvärinen. Causal autoregressive flows. In AISTATS, 2021.
Mikko Koivisto and Kismat Sood. Exact bayesian structure discovery in bayesian networks, Journal of machine learning research, 5:549-573, 2004.
Jack Kuipers, Giusi Moffa, and David Heckerman. Addendum on the scoring of gaussian directed acyelic graphical models. The Annals of Statisties, 42(4):1689-169) 2014.
Trent Kyono, Yao Zhang, and Mihaela van der Schaar. CASTLE: regularization via auxiliary causal graph discovery. In NeurlPS, 2020.
Sébastien Lachapelle, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. Gradient-based neural DAG learning. In ICLR, 2020.
Phillip Lippe, Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclic- ity constraints. In ICLR, 2022.
Po-Ling Loh and Peter Bühlmann. High-dimensional learning of linear causal networks via inverse covariance estimation. Journal of machine learning research, 15(1):3065-3105 2014.
Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of machine learning research, 21:99:1-99:108, 2020.
Ignavier Ng, Zhuangyan Fang, Shengyu Zhu, and Zhitang Chen. Masked gradient-based causal structure learning. CoRR, abs/1910.08527, 2019a.
Ignavier Ng, Shengyu Zhu, Zhitang Chen, and Zhuangyan Fang. graph autoencoder approach to causal structure learning. CoRR, abs/1911 1t5//911..001 1.07220, 2019b.
Ignavier Ng, AmirEmad Ghassami, and Kun Zhang. On the role of sparsity and DAG constraints for learning linear dags. In NeurlPS, 2020.
Ignavier Ng, Sébastien Lachapelle, Nan Rosemary Kc, Simon Lacoste-Julien, and Kun Zhang, On the convergence of continuous constrained optimization for structure learning. In International Conference on Artificial Intelligence and Statistics, pp. 8176-81919 8198, 2022.
Judea Pearl. Causality: Models, Reasoning, and Inference. 2000.

---

Published as a conference paper at ICLR 2023
Judea Pearl, Madelyn Glymour, and Nicholas P Jewell. Causal inference in statistics: A primer. John Wiley & Sons, 2016.
Jonas Peters and Peter Bühlmann. Identifiability of gaussian structural equation models with equal error variances. Biometrika, 101(():219-228, 2014.
Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs.
Neural computation, 27(3):771-799) 2015.
Jonas Peters, Joris M. Mooij. Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of machine learning research, 15(1):2009-255. 2014.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant pre-
diction: identification and confidence intervals. Journal of the Royal Statistical Society; Series B (Statistical Methodology), -845):947-1012, 2016.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science, 308(5721): 523-529, 2005.
Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunities with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10 (1):1-12, 2020.
Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti J. Kerminen. A linear non- -on-gaussian acyclic model for causal discovery. Journal of machine learning research, 7:2003-2034 2006.
Abhinav Shrivastava, Abhinav Gupta, and Ross B. Girshick. Training region-based object detectors with online hard example mining. In CVPR, pp. 761-769. IEEE Computer Society, 2016.
Tomi Silander and Petri Myllymäki. simple approach for finding the globally optimal bayesian network structure. UAI, 2006.
Elena Sokolova, Perry Groot, Tom Claassen, and Tom Heskes. Causal discovery from databases with discrete and continuous variables. In European Workshop Probabilistic Graphical Models, pp. 442-457, 2014.
Peter Spirtes and Clark Glymour. An algorithm for fast recovery of sparse causal graphs. Social science computer review, 9(1):62-72, 1991.
Peter Spirtes and Kun Zhang. Causal discovery and inference: concepts and recent methodological advances. In Applied informatics, volume 3, pp. 1-28, 2016.
Peter Spirtes, Christopher Meek, and Thomas S. Richardson. Causal inference in the presence of latent variables and selection bias. In UAI, 1995.
Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-ma min hill-climbing bayesian network structure learning algorithm. Machine learning, 65(1):31-78, 2006.
Sara Van de Geer and Peter Bühlmann. lo-penalized maximum likelihood for sparse directed acyelic graphs. The Annals of Statistics, 41(2):536-567, 2013.
Gherardo Varando. Learning dags without imposing acyclicity. CoRR, abs/2006. 2020.
Matthew J Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey on structure learning and causal discovery. ACM Computing Surveys (CSUR), 2021.
Yu Wang, Zhang, Xiang Wang, Xiangnan He, and Tat-Seng Chua. Differentiable invariant causal discovery. CoRR, 2tt./2205.15633 2022.
Yuhao Wang, Vlado Menkovski, Hao Wang, Xin Du, and Mykola Pechenizkiy. Causal discovery from incomplete data: A deep learning approach. CoRR, 0bs/2001.053443 2020.
Dennis Wei, Tian Gao, and Yue Yu. Dags with no fears: closer look at continuous optimization for learning bayesian networks. In NeurIPS, 2020.
12

---

Published as a conference paper at ICLR 2023
Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. Causalvae: Disentangled representation learning via neural structural causal models. In CVPR, 2021.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure learning with graph neural networks. In ICML, 2019.
Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: efficient DAG structure learning approach. In ICML, 2021.
Changhe Yuan and Brandon M. Malone. Learning optimal bayesian networks: A shortest path perspective. Journal of Artificial Intelligence Research, 48:23-65, 2013.
Kun Zhang and Aapo Hyvarinen. On the identifiability of the post-nonlinear causal model. UAI, 2009.
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Dags with NO TEARS: contin- uous optimization for structure learning. In NeurIPS, 2018.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric P. Xing. Learning sparse nonparametric dags. In AISTATS, 2020.
Rong Zhu, Andreas Pfadler, Ziniu Wu, Yuxing Han, Xiaoke Yang, Feng Ye, Zhenping Qian, Jingren Zhou, and Bin Cui. Efficient and scalable structure learning for bayesian networks: Algorithms and applications, In ICDE, 2021.
Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In ICLR, 2020.
13

---

Published as a conference paper at ICLR 2023
A RELATED WORK
Differentiable score-based causal discovery methods. Learning the directed acyelic graph (DAG) from purely observational data is challenging, owing mainly the intractable combinatorial nature of acyclic graph space. A recent breakthrough, NOTEARS (Zheng et al., 2018), formulates the dis- crete DAG constraint into a continuous equality constraint, resulting optimization problem. Recent subsequent works extends the formulation to deal with nonlinear problems by using a variety of deep learning models, such as neural networks (NOTEARS+ (Zheng et al., 2020), GraN-DAG (Lachapelle et al., 2020), CASTLE (Kyono et al., 2020), MCSL (Ng al., 2019a), DARING (He et al., 2021)), generative autoencoder (CGNN (Goudet et al., 2018), Causal- VAE (Yang et al., 2021), ICL (Wang et al., 2020), DAG-GAN (Gao et al., 2021)), graph neural network (DAG-GNN (Gao et al., 1021). GAE (Ng et al., 2019b)), generative adversarial network (SAM (Kalainathan al., 2018), ICL (Wang al., 2020)), and reinforcement learning (RL-BIC (Zhu et al., 2020)).
differentiable score-based
Multi-domain causal structure learning. Most multi-domain causal structure learning methods are constraint- and have diverse definition of domains. In our paper, the multi-domain or multi-group refers to heterogeneous data whose underlying causal generating process remain stable but the distributions of noise variables may vary. In literature, our definition of multi-domale is consistent with MC (Ghassami al., 2018), CD-NOD (Huang al., 2020), LRE (Ghassami al., 2017), DICD (Wang et al., 2022), and others (Peters et al., 2016). In addition to the strict restriction of knowing the domain annotation advance, the majority of structure learning models dedicated to heterogeneous data exhibit limited applicability, due to linear case assumption (Ghassami et al., 2018; 2017), causal direction identification only (Huang et al., 2019; Cai et al., 2020), and time- consuming (Huang et al., 2020).
B ALGORITHM OF RESCORE
Algorithm ReScore Algorithm for Differentiable Score-based Causal Discovery
Input: observational data D: {x; : = 2......, n), DAG learner parameters 0g. reweighting model parameters fw. cutoff threshold r, epoch to start reweighting Kreweight, maximum epoch in the inner loop Kinner, maximum epoch in the outer loop Kouter
Initialize: initialize 0n uniformly output n 11 0, k2 =0 for k & Kouter do
Fix reweighting model parameters 0.. Calculate w' by applying threshold Optimize 0g by minimizing Sw (G: X) + PDAG(G)
Outer optimization Equation
if ki 2 kreweight then for K2 S Kinner do Fix the DAG learner's parameters 0g Get w from 0., by applying threshold
[
Optimize 0r by maximizing (g: X) # Inner optimization in Equation 6
K2 + K2 +1
end for
k1 < k1
+1
2i 0
end if end for return predicted G from DAG learner
14

---

Published as a conference paper at ICLR 2023
C IN-DEPTH ANALYSIS OF RESCORE
C.I PROOF OF THEOREM
Theorem 1. Suppose the SEM in Equation 1 linear and the size of observational data nT. As the data size increases, i.c., + OC,
arg min mig (9; + PDaa(9)) - arg min (S(G;X) + (D) U.S. 0
G
the following cases:
Using the least-squares loss X(G:X)= | f(x)l
b. Using the negative log-likelihood loss with standard Gaussian noise.
Proof. Let B = (Bi...., Ba) E Rdddd be the weighted adjacent matrix of SEM, the linear SEM can be written in the matrix form:
X N
where XX d. Var(N|X) d ................................ , and By since X₁ cannot be the parent of itself. Let X Ixd d be the observational data and N Rnd be the corresponding errors, then
X +N.
The original and reweighted functions for optimization are X)::)) + PaaG ()) = L): + sperass (B)+P(BB)
(B: PAG (B) C. (B; X) + XR sparse (B) (B)
Comparing the above functions, only the first goodness-off term are different, we will only con- sider this term.
For the least-squares loss case, the optimization problem is
min (B;X) min wxl(xi, B)
s.t. Bū 0,
1= d.
Let W ding(w),.. w.) be the n-dimennsionl matrix, and rewrite the loss function as
C. (B:X)
Σ |// x,B1|
wx xx,B3xxxx X,B)T
W. (Xij x1,,)²
x
XB3) T TW X33),
1=1
where x² is the j-th column matrix X. Let Dj be the d-dimensional identify matrix by setting j-th element as 0, for 1,...,d d. The above optimization is able to be written without the restriction:
d
min L. (B; min B
x xD;8))TW(C - XD,
d
min B
((x)) Twx 2(x)) WXD,, " WXD,3))
==1
15

---

Published as a conference paper at ICLR 2023
The partial derivative of the loss function with respect to 3y is
Σラ= ((x) 2(x ((x))_XXXxs + DJ x
(L,(B:
08y
03,
0((x)) WWx -((x)) ( WXD 33 D
0,3
2D] x Wx + 2D x WXD,3,,
Setting the partial derivative to produces the optimal parameter:
8 - D- (x ( ( Wxx
D,D = Dy3, + D2 W X
(X (X) "D,, X X W, +
(8)
where N E R. is the j-th column in matrix N. In the above equation, the second equality holds because x = XD,8, + N Similarly, one can easily obtain that the optimum parameter for
ordinary mean-squared loss is
= D Xx -
is obvious that the difference between Equation and Equation is the second term. Compute the mean and variance matrix of the second term in Equation 8, we can get
E [(XTWX) WX)-XX WN'
E
E E
E
[x (X)
-X
0.
and
Var
[X
[X
WX)
'x WNN]
m8
X
WX)
(N') W X(XTXXXX)))
XXXXXXX |X
E
X
WX)
WX)
WXXX WX)
(X (X
WXX VXXXTXXX WX)
E WX) X WX) (X -.
The last equality holds because E(NNT X) = Var(N]X) + ((NIX) diag(o?......
Since w E C(T), it is easy to know that the variance matrix is finite. By the Kolmogorov's strong law of large numbers, the second term converges zero, thus
8 0.e. DyS
16

---

Published as a conference paper at ICLR 2023
which is same the ordinary case. Since noise N (Ni,..., .N) are are jointly independent, the pre- vious process can be apply to the other j E {L,...,d)) .d.. Let B (31...., 3.) and B ......., Ba), then
B 0.. 0.
Therefore, the convergence has been shown for 'case a."
Since the noise follows a Gaussian distribution, i.c.
X XB N (Ni,..., Na) NOO diaglo di..(o)).....0))
the loss function (negative log-likelihood function) is
d
(Xij x;13)2
L (B:X)
log
Jgy JgV 2T
203
1
n
wi log (a.v2T) 2n
Wi
(Xij x;3,)²
20²
j=1
j=1
log (oyV2m) 2m
(x) (x'- X33) -x,))
W(x TWx)'
X,,))
(10)
203
To minimize the loss function above w.r.t B, it is equivalent to minimize the second term in Equa- tion 10:
min -- T X.3)).
min (B;
It can be that the RHS above is similar to the loss function in 'case a.' except the coefficients 20 = 1, ... Therefore, one can use same approaches to get the equivalence result for 'case b.
Consequently, the proofs of the two special cases have been done.
C.2 PROOF OF THEOREM 2
Theorem 2. Suppose that in the optimization phase, the i-th observation has larger error than the j-th observation in the sense that [(x (xx)) > 1(xx, f(x)). where i.j E {1.....,1] n... Then,
i u
where wt, w. are the optimal weights in Equation 6. The equality holds if and only if =wz or w = = 7
Proof. We will show the theorem by contradiction. Without loss of generality, let =1, 2, and suppose w <wS. Since w" E C(T), one can find a small constant E E (0. minfu" - I such that
n rm wi}).
-** = [w" + e, w - e, wg...,,,i w.,) E C(T).
(11)
Therefore,
(g; (G:
[w] 1(xx,,((x))) (xx)) + wi 1(x2, (x2)) - [(w] + +e) f(x)) + (wz -) -)(x)(()))))))))))))) -)x((x)) [Xx))]
= E- [1(x,, fxx2) - [ < 0,
which contradicts w arg max Sw, (G: X). Thus, by contradiction, we can get wi 2 w stated in the theorem.
When wi w mn can also find small (0. min (wi I 1 wz)) such
n rn
that Equation 11 holds. Similarly, can get Sw. (G:X) S (G; X), and w wi I or
wf w 7m
by contradiction.
17

---

Published as a conference paper at ICLR 2023
D SUPPLEMENTARY EXPERIMENTS
D.1 BASELINES
We select seven state-of-the-art causal discovery methods as baselines for comparison:
NOTEARS (Zheng et al., 2018) is breakthrough work that firstly recasts the combinatorial graph search problem as a continuous optimization problem in linear settings. NOTEARS estimates the true causal graph by minimizing the reconstruction loss with the continuous acyclicity constraint.
NOTEARS-MLP (Zheng al., 2020) is extension of NOTEARS for nonlinear settings. ap- proximating the generative SEM model by MLP while only applying the continuous acyclicity constraint to the first layer of the MIP.
GraN-DAG (Lachapelle et al., 2020) adapts the continuous constrained optimization formulation to allow for nonlinear relationships between variables using neural networks and makes use of final pruning step to remove spurious edges, thus achieving good results in nonlinear settings.
GOLEM (Ng et al., 2020) improves on the least squares score function (Zheng et al., 2018) by proposing score function that directly maximizes the data likelihood. They show the likelihood- based score function with soft sparsity regularization is sufficient to asymptotically learn a DAG equivalent the ground-truth DAG.
DICD (Wang et al., 2022) aims discover the pevironmeen-invvaria causation while removing the environment-dependenn correlation based on ground truth domain annotation.
CD-NOD (Huang al., 2020) is constrained-baase causal discovery method that is designed for heterogeneous data, i.e., datasets from different environments. CD-NOD utilizes the independent changes across environments to predict the causal orientations and proposes constrained- based and sernel-based methods to find the causal structure.
GES (Chickering, 2002) is a score-based search algorithm that searches over the space of equiva- lence classes of Bayesian network structures.
D.2 EXPERIMENTAL SETTINGS
For NOTEARS, we follow the original linear implementation. For GOLEM, adopt the GOLEM- NV setting from the original repo. For NOTEARS-MES -MP,,, we follow the original non-linear imple- mentation which consist Multilayer Perceptron (MLP) comprising of two hidden layers with ten neurons each and ReLU activation functions (except for the Sachs dataset, which uses only one hidden layer, inherent the settings from Zheng et al. (2020)). For GraN-DAG, we employ the pns, training. and cam- cam-pruning stages from the original code and tune three pipeline stages together for best performance. The ReScore adaptive weights learning model for all nonlinear baselines consists of two hidden layer and ReLU activation, and for linear baselines the layer size is reduced to one. All Experiments are conducted on a single Tesla V100 GPU. Detailed hyperparameter search space for different methods is shown in Table 4.
D.3 STUDY ON RESCORE
D.3.1 ILLUSTRATIVE EXAMPLES OF RESCORE
Motivations. To fully comprehend the benefits of reweighting, two research hypotheses need to be verified. First, we have to determine the validity of the fundamental understanding ReScore, which states that real-world datasets inevitably include samples of varying importance. In other words, there are many informative samples that come from disadvantaged groups in real-world scenarios. Additionally, faithful reflection of sample importance, i.e., less-fitted samples typically come from disadvantaged groups, which are more important than those well-fitted samples.
must confirm that the adaptive weights learned by ReScore the
Simulations. Real-world Sachs (Sachs et al., 2005) dataset naturally contains nine groups, where each group corresponds with different experimental condition. We first rank the importance of
18

---

Published as a conference paper at ICLR 2023
Table Hyperparameter search spaces for each algorithm.
Hyperparameter space
X (0.002, 0.005, 0.01, 0.015, 0.02, 0.03, 0.09, 0.1, 0.25)
Gumbel softmax temperature ~ (0.1, 1, 10, 20, 30, 40, 50, 100)
NOTEARS/ / NOTEARS+ReScore
Cut-off threshold r ~ {0.01, 0.3, 0.5, 0.9, 0.999 Constraint convergence tolerance {10-9, 1000, 1010,,00-00 Log(learning rate of
À ~~ {0.002, 0.005, 0.01, 0.015, 0.02, 0.03, 0.1.00..... 0.25)
GOLEM/
Gumbel softmax temperature ~ (0.1, 10, 30, 40, 50, 100) Cut-off threshold 7 ~
GOLEM+ReScore
0.7 Log(learning rate of ReScore)
A ~ {0.002, 0.005, 0.015,, 0.02, 0.03, 0.09, 0.25) Gumbel softmax temperature (0.1, 10, 20,20,30, 30, 40, 50, 100)
# hidden units of ReScore ~ (1, 20,0,00.11 (0,,80000)
# hidden layers of ReScore ~ 21, 3, 4]
NOTEARS-MLP/ NOTEARR-MMP+RRecooee
# hidden units of NOTEARS-MLP--. 21,10,20,50, 80,
# hidden layers of ReScore ~ [1,2,3]
Cut-off threshold T ~ {0.01, 0.1, 0.3, 0.5, 0.9, 0..,0..... Constraint convergence tolerance ~ {10-6, 10 100 8,10-10 Log(carning rate of R
A~ {0.002, 0.005, 0.015, 0.00,,,,,000,000 0.03, 0.09, 0.1, 0.25}
Gumbel softmax temperature ~ (0.1, 10, 30, 40, 50, 100)
# hidden units of ReScore [1, 20, 50, 80, 100)
GraN-DAG/ GraN-DAG+Rescore
# hidden layers of ReScore ~ (1,2,3.4)
Log(larning rate of ReScore) ~ U[
PNS threshold ~ (0.5, 0.75, 1,
Log(Pruning cutoff) ~ (0.001,000066, 0.01, 0.03, 0.1, 0.1,0,, 0.3)
A~ (0.002, 0.005, 000,5.0.10001,,,,,,,, 0.015, 0.02, 0.03, 0.09, 0.1, 0.25)
Gumbel softmax temperature (0.1, 1, 10, 20, 20,30, 40, 50, 100)
GES/ /
# hidden units of ReScore ~ [0, 80, 100)
GeSrReScore
# hidden layers of ReScore [1,2,3,4]
Cut-off threshold 7 ~
Table 5: Performance comparison for removing samples in different groups
Group Index
3
S
2
4
8
Avg. ranking
578.4
2856.7
3368.1
3877.0
3949.4
4549.4
4573.2
4590.6
4910.1
SHD w/o group
16
16
17
16
16
17
17
19
19
TPR w/o group
0.529
0.412
0.412
0.412
0.412
0.412
0.412
0.353
0.294
each group in Sachs by using the average weights for each group learned by ReScore as the criterion. Then we eliminate 500 randomly selected samples in one specific group, perform NOTEARS-MLE. and show its DAG accuracy inferred from the remaining samples. Note that the sample size in each group, which ranges from 700 900, is fairly balanced.
Results. Table 5 clearly shows a declining trend w.e.. SHD and TPR metrics the significance of deleting groups grows. Specifically, removing samples from disadvantaged groups such as Groups and 0, which have the highest average weights, will significantly influence the DAG learning quality. In contrast, the SHD and TPR of NOTEARS-MLE can even be maintained or slightly decreased by excluding the samples from groups with relatively low average weights. This illustrates that samples of different importance are naturally present real-world datasets, and ReScore is capable of successfully extracting this importance.
19

---

Published as a conference paper at ICLR 2023
Table SHD for Peorrupt percentage noise samples.
0.01
0.02
0.05
0.08
0.1
0.2
0.3
0.5
NOTEARS-MLP
14.9
15.2
15.3
18.9
19.8
21.3
23.9
23.8
28.3
ReScore (7 0)
13.8
14.2
15.0
18.3
19.5
20.7
24.0
24.4
29.3
+ ReScore (Optimal r)
13.7
14.1
15.0
18.1
19.2
19.9
21.9
24.0
28.9
Imp. %
+8%
+7%
+2%
+4%
+3%
+7%
+8%
-1%
-2%
D.3.2 SENSITIVITY TO PURE NOISE SAMPLES
Motivations. A basic assumption of ReScore is that pure noise outliers involved in the training process. Otherwise, the DAG learner might get overwhelmed by arbitrarily up- up-weighting less well-fitted samples, in this case, pure noise data. The good news is that the constraint of the cutoff threshold + & ((7) = {w < S wi...., Wn S >i= Wi = 1} prevents over- exploitation of pure noise samples, which further strengthens ReScore's ability to withstand outliers. To evaluate the robustness of ReScore against pure noise samples, the following experiments are conducted.
Simulations. We produce Peorrupt percentage pure noise samples in nonlinear settings (n = 2000, d 20, ER2), where those noise samples are generated from different structural causal model. We try out broad range of Poorrupt = {0, 0.01, 0.02, 0.05, 0.08, 0.1, 0.2, 0.3, 0.5}.
Table 6 reports the comparison performance NOTEARS-MLE and two ReScore meth- ods (no cut-off threshold and optimal r) when encountering pure noise data. The best- pest-performing methods are bold; Imp. % measures the relative improvements of ReScore (Optimal 7) over the backbone NOTEARS-MLP. We observe that ReScore (Optimal 7) consistently yields remarkable improvements compared with NOTEARS-MLP in the case that less than 20% of samples are cor- rupted. These results demonstrate the robustness of ReScore when handling data that contains small proportion of pure noise data. Surprisingly, when the cutoff threshold 7 is set to be close to the ReScore still achieve relative gains over the baseline when less than 10% of the samples are pure noise. Although is more sensitive to noise samples than the optimum cutoff threshold These surprising findings support the effectiveness of adaptive weights and show the potential of ReScore.
Results.
D.3.3 EFFECT OF HYPERPARAMETER
We investigate the effect of cut-off threshold т on the performance of ReScore. Intuitively, ReScore relies on the hyperparameter to control the balance between hard sample mining and robustness towards extremely noisy samples. On one hand, setting the threshold closer to 0 results in no weight- clipping and leaves the model susceptible to noises, which results in sub-optimal performance. On the other hand, setting the threshold closer to disables the reweighting scheme and eventually reduces ReScore performance to its backbone model.
We conduct experiments under different settings of T using n = 2000 samples generated from GP model on ER4 graphs with d = 20 nodes. The weight distribution under best performing threshold tau = 0.9 and the trend of SHD w.r.f to T is shown in Figure 4. One can observe that ReScore obtains its best performance at performance. Furthermore, we find that in different settings, the optimal threshold usually falls in the range of [0.7, 0.99). This indicates that ReScore performs best when adaptive reweighting is conducted within restricted range.
0.9, while smaller or bigger threshold results in sub-optimal
D.3.4 SENSITIVITY TO NEURAL NETWORK COMPLEXITY.
We also investigated the effect number hidden units in our adaptive weights learning model for ReScore. We plot the TPR, FDR, SHD, SID with varing number of hidden units ranging from 10 to 100 units in nonlinear settings, using n = 600 and n = 2, 000 samples generated from GP model on ER4 graph with d 10 nodes. Detailed results could be found in Figure 5. One first observe our model is stable when increasing the neurons, illustrating the insensitivity of ReScore w.t.. the number of neurons in adaptive weights learning model. On the other hand, more observational
20

---

Published as a conference paper at ICLR 2023
54.
00316
504
00315
0.7
(a) weight distribution with 0.9
(b) SHD w.E. threshold т
Figure 4: Study of varying in ReScore model.
(a) TPR w.E.t neurons
(b) FDR WEEL neurons
(c) SHD WEE. neurons
(d) SID w.C. neurons
Figure 5: Performance with varying neurons in ReScore model.
samples to estimate the parameters could help the ReScore achieve higher performance, indicating rich samples bring benefit.
D.3.5 TRAINING COSTS.
In terms of time complexity, as shown in Table 7, we report the time for each baseline and ReScore on Sachs. Compared with backbone methods, ReScore adds very little computing cost training.
D.4 MORE EXPERIMENTAL. RESULTS FOR RQ1
Discussions. More experimental results on both the linear and nonlinear synthetic data are reported in Figures 6 and Tables ten trails. The red and blue percentages separately refer to the increase and decrease of ReScore relative to original score-based causal discovery methods in each metric. The best performing methods per task are bold.
The error bars depict the standard deviation across datasets over
21

---

Published as a conference paper at ICLR 2023
Table 7: Training cost on Sachs (seconds per iteration/in total).
NOTEARS
0.74 2.97
ReScore
3.8 15.3
NOTEARS-MLP
0.87 3.48
ReScore
4.3/17.0
GOLEM
13.4 53.5
ReScore
14.6/
GraN-DAG
4.9 / 197.3
ReScore
5.5 221.6
CETIA
208
150
654
500
G81
120
25a
120
6.0
630
630
100
700
(a)
TPR W.E..
(b) FDR W.X. X
(c) SHD W.E. À
(d) SID WEE.
Figure 6: Performance comparison between NOTEARS-MIE MLP and ReScore ER2 graphs of 10 nodes on nonlinear synthetic datasets. The hyperparameter À defined in Equation refers to the graph sparsity.
600
(a) TPR W.E.
(b) FDR w.l. X
(c) SHD W.E. X
(d) SID w.r.f.
Figure 7: Performance comparison between NOTEARS-ME MLP and ReScore ER2 graphs of 20 nodes on nonlinear synthetic datasets. The hyperparameter defined Equation refers to the graph sparsity.
200
650 A01 Bil
500
(a) TPR W.Y.
(b) FDR W.R. À
(c) SHD W.E. À
(d) SID W.E.
Figure 8: Performance comparison between NOTEARS-MLP and ReScore on ER4 graphs of 20 nodes on nonlinear synthetic datasets. The hyperparameter defined Equation refers to the graph sparsity.
Table 8: Results for ER graphs of 20 nodes on linear and nonlinear synthetic datasets.
ER2
ER4
TPR
FDR
SHD
SID
TPR
FDR
SHD
SID
Dane
292.35457
NOTEARS
0.85
0.09
9.2eas
55,4eau
0.74
0.23
39.4
185.8456.1
ReScore
0.77 2%%
0. 0.
50.6
0,79 -7%
36.8219
180.8
0.75ex27
78.2-126
0.46axas
ReScore
0. 76eass
20 se
15. Mess
77.0ea1s*
D. d8ear
70.2583
NOTEARS-MLP
0.70ax:2
a3
14.9
98.4um22
0.44axce
0.26
55.0as2
176.3
ReScore
0.73
1.an 77
13.7.51
$8.8
0.41
51.61
179.9)
GraN-DAG
9.3154
1.18
57.4s4A
ReScore
0.05
$1.00216.55
0.21g300
0.17
125.4.965
22

---

Published as a conference paper at ICLR 2023
Table 9; Results for ER graphs of 50 nodes on linear and nonlinear synthetic datasets.
ER4
TPR 1
FDR
SHD
SID 4
IPR
FDR
SHID
SID
Random
0.902z00
597. 3a
1082 Dg1603
g.09
0.92
998 2a44
1999, 2
NOTEARS
0.79
0,092000
27 6:23
427 Dasiee
0,51
0.27:mn0
133-44213
1643.8an122
ReSeore
0.88
0.15amw
2622
266.0 1611
0.52
0.29a
1330. 195
1453.6
1200
GOLEM
D D.80gno
0.35
68
0.31g
0.68ance
150.62251
+ ReSeore
D.82
0.33
G3.4g21
4.30 24 i55.5
0.39
0.00
146,3
1643.6-1148
NOTEARS-MLP
6.32
0.15e
69.5
0.06
167.0
1607.6
+ ReScore
0.51 cours"
a.10
53.5aa77
628.
1 1au
0.26:2244
0.11awe
154.4164
7
GraN-DAG
0:52gn0w
0.15
51 6627
652 Rigiond
0.32
0.08
141 16:3
1879.04913
ReScure
0,53c
0.11 11aeee-10
46.0:xp-128
581.0:0
0.31anes
0.06 -2%
138.8
-2%
1351,02s
Table 10: Results for SF graphs of 10 nodes on linear and nonlinear synthetic datasets.
SF2
SF4
TPR
FDR
SHD
SID +.
TPR
FDR
SHD
SID
0.05
52.2
15.1
0.18
D:95
57.2
79.1
NOTEARS
0.9W:.om
2.02.am
0.Maes
1,0a20
0,95g00
0.03g
12.2
6,2253
ReSeore
0.99 11
0.04
4555
0.
1.0 1000
0.97 199
0.03_amm
10.2
3.0_19 1079
GOLEM
0.96:200
0.07=a12
1.823
1,2424
0.85
0.12
7.0k22
12.8
ReScore
0.97
0.07 188
1.4
0.87
0.10..04
NOTEARS-MLP
0.84
0.25
6.7
8. 1.73
0.73
0 03
12,0s19
19-4
ReScore
0.82200 23%
0.17 4-485
6.
o 2002
0.27: 1955
11.0axe
12.8 192%
GraN-DAG
0.69:rc2
0.05=mme
5,9e30
12.0ak2
0.82ea.11
0.11
8.7
8:144
ReScore
0. 07
0.04
5.351x+AM
10.5 10.5a87
14%
0.86000
0.12:
8.1220
7.0
Table 11: Results for SF graphs of 20 nodes on linear and nonlinear synthetic datasets.
SF2
SF4
TPR
FDR
SHD
SID
TPR
FDR
SHD
SID
0.89
43.2a54
96.8
0.09
0,58
108.2s120
155.6em2
NOTEARS
0.90
0.02:tmm
4.0a1s
19.8
0.90
0.12:006
45.2a70
28.61.322
ReScore
0.95eaze
8.06ssue
3.611a
9
0.93 43R
0.02 4200%
45. 15.0ssa -0%
25.6:121
GOLEM
0.9650a
10.4
0.83+400
0.35
11.4
ReScore
0.96
0. 1
8.0
10.4e7a
f1.5
0.34
39.8
37 37.6=122"
NOTEARS-MLP
0.42eu11
0,23
25.5
0,20ssuu
0.22
58, 98511
115.6e250
ReScore
0.41aa13" 2%
0.10 n.10 1219
23.5
47.6194 +a3
0.24 8S%
2.09 --.0%
56.4122
109.0
GraN-DAG
0.03aa11
0.24
27.1e441
77.0
0.20sicus
0.18
56.8443
133.4=21a
ReScore
0.08eaus
0.15
25.7
72. Staaa
0.21
0.17
56.4545
125 122.4
Table 12: Results for SF graphs of 50 nodes on linear and nonlinear synthetic datasets.
SF2
SF4 SHDD
TPR 1
FDR
SHD
SID 1
TPR
FDR J
SID 4
Random
0. 0.10amme
0.89
334, 2aree
1003.3 3:145
0.12anm
0.80gmm
1023 Sases
1903 92
NOTEARS
0.82aom
23.6
135.4
0.71an
0.25aom
97.62449
276.2g
ReScore
0.94 159
1.15 50%
21.6 10%5
61.2azza 4221
0.73 -3
0.10
67.6
275.2
GOLEM
0.77amm
19
0.62an
0.31a
114 22315
384 02
+ ReScore
0. 0,70amaa
0.2
32. 2e11a
0.88
0.21 soun
113. 113.7a312
386. Lame
NOTEARS-MIPP
0.22
1001
25.8
266.8_460
0.11g000
1003
168.5 883.
ReScore
0.23
0.077 sour
75.6
207. 2ua
0.13
0.07 anoe
167.7a70
483.4
GraN-DAG
0.19mmm
0.28
90.2
380.8
0.11aom
0.25.6m
171 41r.
$49 fisss
ReScore
0.20amu 45%
0.24 -179
7
349.2s +056
0.11
0.2
170.8a4u+44%
568.02mm
23


Reviews:
[{"review_id": "wDXqg58LPgm", "reviewer": "Reviewer_m1MC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a method for improving the robustness of score-based DAG learning methods to heterogeneous noise.  It works by iteratively up-reweighting the poorly fitted observations and then rerunning the base method.\n", "summary_of_the_review": "This seems like a nice contribution to the literature, allowing for more accurate learning of DAG structure with score-based algorithms.  Please do ensure you take into account my comments below in your revision.  \n\n### Comments \n\n1. What happens if the observations are just statistical outliers, and don't really contain any useful information?  I could easily imagine just a few observations totally disrupting your algorithm in this context, because they would presumably be massively up-weighted and might overwhelm your fitting algorithm.\n\n2. You say that you can fit your method to 'any score-based causal discovery method'.  This is not correct - first, and most obviously, you need the individual data; second the data must be assumed to be independent; and third it is not clear to me whether the method would work for other classes of graphs.\n\n3. \"However, it is no doubt that integrating a strong backbone DAG learner with ReScore is the only way to truly advance in this field.\"  This statement is much too strong; it's not at all clear that another approach might work just as well as yours, or even better!\n\n4. In the proof of Theorem 1, you write down the conditional variance formula at the bottom of page 15 but you implicitly assume that $\\mathbb{E} [(X^TWX)^{-1} X^TW N^j \\mid X] = 0$.  This is fine (since it's used on the previous line), but you need to state that this is what you're doing, or the proof is hard to follow.  I would suggest giving the conditional variance formula before you start and then noting that this second term is zero.\n\n### Typos/Minor Points\n\n - page 4: \"combinatorial optimizaiton\" $\\to$ \"combinatorial optimization\";\n - page 5: \"hard less-fitted samples\" $\\to$ \"less well-fitted samples\";\n - page 6: \"negative llog-likelihood\"\n - page 9: \"In sheer contrast\" $\\to$ \"In stark contrast\"\n - page 15: \"one is easy to obtain that\" $\\to$ \"one can easily obtain that\"\n - below (9) \"of that term\" - which term? The one from (8), presumably!\n - page 16: \" 'case a.'. \" should be just \" 'case a.' \" and the open quote should be inverted.\n - just below \"standard Gaussian distribution\": not really, since the variances are not all 1.\n - below (10) \"equivalent to minimize the first term\": I think you mean the second term.\n\n", "strength_and_weaknesses": "The method seems useful and clearly improves performance in simulations, as well as on the well-known Sachs data.  \n\nThe weaknesses are: \n1. It is computationally more expensive - this is presumably inevitable given that it involves running the main method several times.\n2. No mention is made of the possibility of spurious outliers.  These are generally dealt with in statistics by _down_-weighting, not up-weighting. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S-cnc1zrfJ0", "reviewer": "Reviewer_ueyq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work addresses the problem of errors in structure learning algorithms.  The authors propose to reweight poorly fit samples in order to improve the efficacy of the underlying algorithm. A proof is shown under linear models for specific scoring rules in the asymptotic regime. Empirical results show the proposed method improving state of the art structure learning algorithms. ", "summary_of_the_review": "As I mentioned above, I think this is a well motivated and simple solution to a very compelling problem. I think the idea that the procedure can be applied a wide variety of algorithms is quite compelling. My reservations are listed above in the weaknesses, and is largely in the theoretical underpinnings and some of the details of the proposed approach. ", "strength_and_weaknesses": "Strengths: \n* The relative frailty of structure learning algorithms is a major roadblock to practical usage, so this task is very well motivated. \n* The authors present an algorithm which is simple and intuitive\n* Empirical results are very compelling\n\nWeaknesses:\n* The authors reweight samples with the intuition that these correspond to spurious edges, however it is not entirely clear to me why this should be limited to one reweighting step. Can the authors give some sort of intuition on why only one boosting step is used? What would happen if multiple reweighting steps were employed?\n* Theorem one is incredibly limited in scope. I don't think this necessarily a problem but the authors should reconcile their claim that the approach is applicable to any score base learner with the assumptions that restrict the space of models and algorithms substantially. \n* The approach deals with recovering directed graphs, but the authors frame in terms of causal discovery. In the case of causal discovery, only an equivalence class is recovered, not a fully directed graph. Do the authors have suggestions or intuition regarding the modifications necessary to have the algorithm work when an algorithm (e.g., GES) returns an equivalence class after every step?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Pj6nm4cl9q", "reviewer": "Reviewer_Q3NX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a model-agnostic framework that improves pre-existing score-based models for causal discovery. This is done by adapting the score weights for each sample while training the backbone model, thus alternating between training the backbone model and updating the weights.\nThe weights are updated in such a way as to give a larger impact to the less-fitted samples, which might be more informative to the backbone model. This framework is claimed to have a particularly large impact when dealing with heterogeneous data (even in cases when we do not know what samples come from which cohort).", "summary_of_the_review": "The proposed method is novel as far as I know, and the experimental results suggest it often yields impressive performance improvements. Because of some issues with the current manuscript, I am currently recommending rejection, but if these issues can be addressed, I expect to recommend acceptance.", "strength_and_weaknesses": "Strengths:\n\n* The exposition of the method is quite clear.\n\n* The proposed framework is very flexible, as it can be used on top of many other score-based methods.\n\nWeaknesses / questions about things that are unclear:\n\n* A main concern is that *the paper claims improvements for any score-based method, while this claim is only supported for the case of differentiable score-based methods*. In the experiments, the proposed framework is applied only with differentiable methods. Also, the framework is motivated from observed shortcomings of differentiable methods (bullets page 1&2). It is possible that the proposed framework also gives improvement with discrete score-based methods, but such a claim is not supported by the paper. The scope of the claim needs to be made clear, starting in the abstract.\n\n* Can you explain an example of how single datapoints may provide \"crucial causal information\", or how without reweighting there is  \"overfitting\" (both page 2)? I think figure 1 starts to demonstrate such issues, but does not explain these two points.\n\n* In Theorem 1, what does it mean to say \"asymptotically\", when the vector of weights is held fixed (and so its length can't increase to accommodate more datapoints)?\n\n* The argmax in (6) will often equal the empty set, because the set $\\mathbb{C}(\\tau)$ is open (so there is a supremum, but no maximum). Replace the inequalities between the $w$'s and the $\\tau$-terms by $\\leq$ to make the set closed.\n\n* The statement and proof of Theorem 2 are incorrect. The proof can only show that $w_i^* \\geq w_j^*$. Because in the proof, when supposing the contradiction, if $w_i^* = w_j^*$, there is no such $\\epsilon$. (BTW, the $\\mathbb{C}$ should be $\\mathbb{C}(\\tau)$. Also, you don't need this set to be open.) But this substantially weakens the statement of the theorem: it now leaves open the possibility that all weights are set equal.\n\n* Theorem 2 seems to suggest that the weights are increasing as a function of the losses (over the different datapoints). Can you explain why this is not what we see in Figure 3? (A possible reason might be related to the text \"in the optimization phase\" in Theorem 2. It is not  clear exactly what point of the bilevel optimization algorithm this refers to.)\n\n* Synthetic data experiment, bottom page 8: what does it mean that the \"noise scale is flipped\"?\n\n* Sachs data: This dataset contains (I think) 14 different interventional regimes, which are pooled together in this experiment. Pooling is not the most effective way to deal with these data (see eg Mooij, Magliacane and Claassen, 2020). As such, I disagree with the conclusions that this experiment \"highlight[s] the ineffectiveness of score-based causal discovery methods when dealing with real-world data\" and that \"integrating a strong backbone DAG learner with ReScore is the only way to truly advance in this field\". Further, due to these regimes, this experiment should be listed under \"heterogenous data\".\n\nMinor comments (not necessarily part of decision assessment):\n\n* I am not familiar with the terminology \"disadvantaged\" domain/data point; I think you mean \"underrepresented\"?\n\n* (page 5) \"Initially, ... are assumed\": This sentence is unclear. I think you want to say that a *family* of functions and a *family* of noise distributions need to be chosen. The use of the word \"specific\" confuses me though.\n\n* For the experiments with heterogenous data, you could consider comparing to a method that uses non-adaptive weights, set inversely proportional to the group sizes.\n\n* The manuscript contains many grammatical mistakes, as well as places where the wrong word was chosen (eg \"alternative(ly)\" when \"alternating(ly)\" is meant; \"phrases\" when \"phases\" is meant; ...). Please thoroughly proofread the manuscript and correct these errors.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "C1fvH2GjOr", "reviewer": "Reviewer_x5dL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a simple model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the score function. In particular, the proposed method leverages the bilevel optimization scheme to alternatively train a standard DAG learner first and then reweight the samples that the DAG learner fails to fit well.", "summary_of_the_review": "The paper is well organized and presented. The sample reweighting trick to improve causal discovery performance is novel, as far as I know. It is also simple and flexible to adapt to other continuous optimization methods.", "strength_and_weaknesses": "Strength:\n\n1. The paper is well presented. \n2. The proposed sample reweighting method can help causal discovery in heterogeneous data by auto-learnable adaptive weights.\n3. The proposed sample reweighting trick is simple and is flexible to combine with any score-based continuous optimization method in causal discovery.\n\nWeakness:\n\n1. It seems after adding the sample reweighting step, the reported empirical performance, especially FDR, instead gets worse in some cases. Is it because bilevel optimization is harder?\n\n2. With the sample reweighting step, the algorithm is computationally much more expensive.\n\n3. It would be more intuitive to understand the benefit of reweighting if the authors could provide illustrative examples.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster