Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Authors: Yiqing Li
Yewei Xia
Xiaofei Wang
Zhengming Chen
Liuhua Peng
Mingming Gong
Kun Zhang
Venue: ICML 2025 poster (2025)
Keywords: Independence tests
Sample reweighting
Causal discovery
Primary area: general_machine_learning->causality

Abstract: Discovering dependence patterns between variables from observational data is a fundamental issue in data analysis. However, existing testing methods often fail to detect subtle yet critical patterns that occur within small regions of the data distribution--patterns we term rare dependence. These rare dependencies obscure the true underlying dependence structure in variables, particularly in causal discovery tasks. 
To address this issue, we propose a novel testing method that combines kernel-based (conditional) independence testing with adaptive sample importance reweighting. By learning and assigning higher importance weights to data points exhibiting significant dependence, our method amplifies the patterns and can detect them successfully. Theoretically, we analyze the asymptotic distributions of the statistics in this method and show the uniform bound of the learning scheme. Furthermore, we integrate our tests into the PC algorithm, a constraint-based approach for causal discovery, equipping it to uncover causal relationships even in the presence of rare dependence. Empirical evaluation of synthetic and real-world datasets comprehensively demonstrates the efficacy of our method.

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Yiqing Li Yewei Xia 12 Xiaofei Wang' 13 Zhengming Chen Liuhua Peng s
Mingming Gong" 15 Kun Zhang
Abstract
1. Introduction
Statistical independence testing, which aims asses whether two variables are independent according sam- ples, is fundamental problem in data analysis and scien- tific inference. Such tests have applications in variety of fields. For example, in brain analysis using fMRI data, identifying which brain areas are involved in specific activi- ties and determining statistical associations between these activities is crucial (Fan et al., 2017). Other applications include self-supervised learning (Li al., 2021), feature selection (Candes al., 2018), causal inference (Imbens & Rubin, 2015) and more.
Discovering dependence patterns between vari- ables from observational data is fundamental issue in data analysis. However, existing testing methods often fail to detect subtle yet critical pat- terns that occur within small regions of the data distribution-patternss we term rare dependence. These rare dependencies obscure the true underly- ing dependence structure in variables, particularly in causal discovery tasks. To address this issue, we propose a novel testing method that combines kernel-based (conditional) independence testing with adaptive sample importance reweighting. By learning and assigning higher importance weights to data points exhibiting significant dependence, our method amplifies the dependence patterns and detects them successfully. Theoretically, we ana- lyze the asymptotic distributions the statistics in this method and show the uniform bound of the learning scheme. Furthermore, we integrate our tests into the PC algorithm, constraint-baat based approach for causal discovery, equipping it to un- cover causal relationships even in the presence of rare dependence. Empirical evaluation of syn- thetic and real-world datasets comprehensively demonstrates the efficacy of our method.
Example 1.1. X ~ U(-20, 20). Y = s e.e t,, (O, 0.25), E {-1, 1, with equal probability.
-20
-15
-10
10
15
20
Figure 1. 1000 samples generated following Example 1.1. p-value of HSIC with default settings on the whole sample is 0.1359 while p-value the samples within the red rectangle is 6.8 10
Recently, methods have been proposed to test for non-linear dependence (Gretton et al., 2005a; Póczos et al., 2012; Lopez-Paz. & Oquab, 2016; Sen et al., 2017; Gao et al., 2018; Li et al., 2024b). Although existing independence tests have achieved significant success, they still fail to de- tect dependence patterns that are significant only within small range of the entire distribution's 's support, which we term rare dependence. For instance, in Example 1.1, the dependence pattern here "exists everywhere", but it is only significant in a small range of X near zero and the dependence is further contaminated by the noise. Many conventional independence tests, such as HSIC (Gretton et al., 2005a), struggle to reject the null hypothesis for the samples shown in Fig. 1.
'Equal contribution 'Department of Machine Learning, Mo- hamed Bin Zayed University Artificial Intellgence, Abu Dhabi, UAE SShanghai Key Lab of Intelligent Information Processing, and School of Computer Science, Fudan University, Shanghai, China KKLAS and School of Mathematics and Statisties, Northcast Normal University, Changehun, China *College of Mathematics and Computer, Shantou University, Shantou, China 'School of Mathematics and Statistics, The University of Melbourne, Mel- bourne, VIC, Australia 'Department of Philosophy. Carnegie Mellon University, Pittsburgh, U.A. Correspondence Ming- ming Gong <mingming gong @ unimelb.cdu.auz. Kun Zhang <kunzl @cmu
Such rare dependence patterns are also commonly ob- served in real-worid scenarios. In economics, income and consumption may appear weakly related in low-income groups but become strongly coupled at higher income lev- els. In psychology (Keles al., 2020), the impact of so-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Extracting Rare Dependence Patterns via Adaptive Sample Rewcighting
cial media on adolescent mental health becomes significant only with excessive usage. Similar rare dependencies cur in medicine (Angst & Clark, 2006), biomedical infer- ence (Tikka et al.. 2019), physics (Aryasetiawan et al., 2004; Hwang et al., 2023), autonomous driving (Hwang et al., 2024), online advertising (Oentaryo et al., 2014), and soci- ology (Huang, 2017), highlighting the practical relevance of detecting rare dependencies. Misclassifying these de- pendencies independent can sometimes lead severe consequences. For example, in causal discovery, such false negatives can propagate errors throughout the graph during the execution of the PC algorithm (Spirtes et al., 2000).
2. Background
Notations. We use uppercase letters X, Y, Z to denote ran- dom variables'. Their domains are denoted by X,Y, Z re- spectively. Consider a continuous feature mapping / X' + Fx with the corresponding measureable positive definite kernel lx == (w), 1²), where Fx is the corresponding Repro- ducing Kernel Hilbert Space (RKHS). We set dxx = (xx) for simplicity. We denote the probability distribution of X as Px = P(X), and the corresponding equare-integrable spaces as f We assume that Fx C f3x- The notations for Y, 2 are defined by analogy with and y as feature mappings.
In Example 1.1, dependence is weak and difficult to detect on the whole sample. However, by focusing more "atten- tion" on the red rectangle in Fig. the dependence pattern becomes more obvious and easier to detect. Motivated by this, we design framework that automatically identifies and amplifies the significantly dependent subsamples and then tests the independence accordingly through reweighted samples. Specifically, the framework assigns an importance weight to each data point, which is produced by a learnable reweighting function. This function is trained by maxi- mizing the reweighted kernel-based dependence measure, which quantifies the dependence between variables calcu- lated on the reweighted samples. The test results based on the data reweighted by the optimized function are then used to decide the null hypothesis. In summary, the proposed framework adaptively assigns more "attention" to the depen- dent sub sub-samples, successfully detecting rare dependence.
Assume the observed samples D = [(1; ki) are inde- pendent and identically distributed (i.i.d.) samples drawn from Pxy. Independence tests calculate the test statistics T : X' x y + R from observed data D to summarize the information about the hypothesis
Ho JLL
V.S.
Hi : X X Y.
The value of the statistics will be compared to specific threshold to determine whether to reject the null hypothesis Ho or not. The performance of an independence test can be evaluated from two aspects: the rate of rejecting Ho when it true (Type I error rate); and the rate of not rejecting Ho when it is false (Type II error rate). Good tests are expected to control the probability of type I errors by significance level a, and large power, i.e., 1- Type II error rate.
Our statistical independence test is based on a kernel-based independence test, Hilbert-Schmidt Independence Criterion.
Besides, extend the idea detect conditional rare de- pendence. Moreover, we design a constraint- method to discover causal relations in the presence of rare depen- dence, which incorporates the proposed reweighting tests. We summarize our contributions as follows.
Definition 2.1. (Gretton et al., 2007) The Hilbert-Schmidt Independence Criterion between X and Y, denoted as HSIC(X, Y), is the HS norm of the covariance operator
x 1l = || 1(1x - px) (øy - HY py]
We propose a novel testing method that combines kernel-based independence tests with adaptive sam- ple importance reweighting to detect dependence even when rare dependence exists. The data point exhibits more significant dependence pattern will be automati- cally assigned with larger weights.
where uxx A Epx (X),, by A [o, @ is the ten- sor product, and Il is the Schbbrt norm.
For characteristic kernels (Gretton, 2015), the independence relationship X TT Y can be judged by HSIC(X, Y) = 0.
We also extend the idea to detect conditional rare inde- pendence. In addition, we integrate tests into the PC algorithm for causal discovery in the presence of rare dependence.
3. Method
In this section, we develop principled framework for de- tecting dependence. We first describe our motivation with some examples ($ 3.1). We define the importance reweight- ing functions then derive and analyze the reweighted statis- tics with carefully defined importance reweighting functions ($ 3.2), and propose a novel framework, that is, an opti- mization problem to learn the reweighting function and an
Theoretically, we obtain the uniform bound of our learning scheme and derive the asymptotic properties of the importance reweighting statisties of the tests.
Empirically, we conduct extensive experiments on syn- thetic and woaldworld data that demonstrate the efficacy of our method.
In some cases, if there is no confusion, it also he used sets of random variables.
2

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
algorithm to test for independence ($ 3.3). Next, a theoreti- cal bound is given guarantee the generalizability of our method ($ 3 3.4). Finally, extension of our framework for conditional independence (CI) is proposed ($ 3.5).
HO
Type I Error (a)
Critical Value
H1
Type lI Error (B)
H1 Mean
Sample size = 0g
Sample size = ng (n,2
pensity
X
5.0
3.1. Motivation
2.
2.5
Recall the dependence mentioned and exemplified in the introduction. We summarize them as "rare dependence" in our paper: the dependence between two variables is signifi- cant only on a small portion of the data. Next, we present another example to show the challenges of the independence test when rare dependence occurs. For all tests in this paper, we choose significance level of 0.05.
0.0
0.0
0.5
0.0
1.0
HSIC statistic
HSIC statistic
Figure 3. Illustration of distributions of HSIC under Ho and Hi in the "rare events" setting. Here na and my denote the sample sizes used in the two settings of the estimated statistical components (asymptotic distribution, mean value of the HI distribution, and the critical value) with n., > R2. Note that under M4. as n - 0o, the ratio of dependent sub-population goes to 0, leading to the mean value of HSIC approaches 0. Therefore the probability of Type II ertor will increase, making the tests prone to not reject Ho.
Example 3.1. X U). X E U (0.25, 11,Y ~ (O, 1). e 0.,5. Y 0.9-X+00.1 where ~ (O, 1). is clear that X H Y according to the data generating process, while HSIC test on whole samples (see scatter plot in Fig. 2) fails to catch the dependence.
pendence pattern for (X, Y) directly. We aim to find the significantly dependent sub-population and change the orig- inal distribution by reweighting to enlarge the dependence. We use the weights produced by the reweighting functions B(-) defined below.
1.0.
005
0.0
Definition 3.2 (Reweighting function and reweighted distri- bution). Let B be the set of reweighting functions,
-4
X
Figure2 2. 1000 data points generated following Example 3.1. p- value of HSIC on whole sample is 0.0613, p-value of HSTC on samples within the red rectangle is 0.0027.
B - {B: R
Exx [
(1)
C is reference variable that can be either X or Y (or a subset of X or Y) and C is the domain of C' correspondingly. Then v/3 E B, the corresponding reweighted distribution IP, which is well defined with the same support of Ixx,, can be determined by the probability density function (p.d.f.)
Notice that, when rare dependence happens, even collecting more data may not be helpful if we equally consider all data points. Inspired by the definition of "rare events" in (Wang, 2020; Wang et al., 2021), suppose that we have the sample (Ii; Vi, G in ~ a kind of distribution that satisfies P(C = 1) - 0, PCC
P(X,Y) = ((C)P(X,Y).
(2)
1) + Do as n + 50, where when X L Y and C 0 when X IL Y. As shown in Fig. 3, in this case the probability of Type II error will become larger as n + cc.
C' (0, 13 with C
Since the case in which X and Y are sets of random vari- ables are easily generalized, we regard X and Y as random variables in the following discussions for simplicity. If X IL Y holds, it is imperative to avoid introducing spu- rious dependence after reweighting, as formalized in the following proposition:
Now we turn to the reason why HSIC tests with subsamples can detect the dependence. Notice that the significantly dependent subsamples both Example 1.1 and 3.1 can be tracked through the values of the variable X. And tests on these subsamples are able to reject independence. This observation leads to the proposed method, which reweights the data points using learned function that takes a reference variable as the input. Note that although this paper mainly focus on HSIC, this behavior also holds in many other popular independence tests, e.g., randomized dependence coefficient (Lopez-Paz et al., 2013) etc.
Proposition 3.3 (Maintain the independence after reweight- ing). If X and Y are independent and C is either X or Y but not both, then X and Y are still independent in the reweighted distribution of (X, Y) with weight ((C).
The proof can be found in Appendix C.I. Since it is symmet- ric with respect to X or Y, we set C = X in the following discussion, unless stated otherwise.
As mentioned in Section 3.1, even though a rare depen- dence exists, it is still possible to detect it by identifying subsamples with significant dependence and increasing their importance ratios in the dependence measure. Therefore,
3.2. Dependent Subsample Extraction by Reweighting
Let X and Y be two different random variables (or disjoint sets of variables), and suppose we fail to see a clear de-
3

---

Extracting Rare Dependence Patterns via Adaptive Sample Rewcighting
aim to find importance reweighting function (-)) to make the dependency pattern between variables as clear as possible. To compare different reweighting functions, we first propose a statistic that quantifies the dependence in the reweighted distribution IP induced by a given reweighting function. This statistic can be directly computed from the original samples, eliminating the need for resampling.
Theorem 3.4 (Null distribution), Under Ho. we have Ea 0. In this case, HSIC (D) converges in dis- tribution to a weighted sum of X2 variables, i.e.
20
nHSIC (D) S
X
(6)
where Xi are i...d chi-square variables with freedom one.
Reweighted Hilbert-Schmide Independence Criterion
Denote wi & (xx.. Vi), X2 are the solutions the eigenvalue problem integrating over the distribution of variables way Wap and w,:
With a fixed function B()), at the population level, the HSIC calculated on the reweighted distribution P is
X [1(w)))= = / Bigr K (ws)
(7)
Bp [(vx - [x(xxx] @ (øy [I]
(3)
where 1P- = ix = 3(X)Pxx- x Rewrite it including only the initial distribution (X, Y) ~ Px and B()), we obtain the reweighted HSIC (RHSIC), HSIC (x, Y) A
Next, we give theorem about the asymptotic distribution when HSTC* (X, Y) > O. i.e., X n Y. This distribution would be useful in analyzing consistency.
Theorem 3.5. When HSTC (x, Y) > O, HSIC (D) con- verges in distribution a Gaussian according to:
[[xx Bxx
Ep |3 )1l
Vn
HSIC
2 NN( 03). (8)
Consider the test statistic on the dataset D = {( v1)) Denote 9g A ((xx) as the weight for a data point (Itk, )k).
The variance 033 = 16 (Eg.g (ar HSIC (X, x))))).
and B is the weight vector for D. A biased estimator of HSIC (X using plug-in estimation method is
where Ejgg,r - Bu W.,
(D) = n
Tr Kr Hz),
(4)
3.3. Testing Procedure and Whole Algorithm
Recall that in Pro. 3.3 we require infinite samples. In prac- tice, we only have access to finite samples, introducing dependence between the samples and the function 3(-) thus breaking the factorizable condition. Empirically. it man- ifests as the estimated (3.) overfitting the given samples and always reporting dependence even for independent vari- ables. To avoid it, we split the data into two independent parts. Suppose we have i.i.d. samples D = {(Zi. }:)] We randomly split it into disjoint training (Der) and testing (Dte) data. We optimize the function B(-) on Drr, and then use it to perform a test on Dre. The split ratio is set to 0.5. Proposition 3.6. Suppose the sample data are i..dd and randomly split into Die = {Ize, yhe I and Der correspond- ingly. B(-) maximizes the dependence measure of Der. Then 3(-) is independent of Dre-
where Kxx and Ky are kernel matrices calculated on sam- by (ys. Vj)- H3 & D3 D3), is the identity matrix, 1 is the vector of all 1s, and D3 A diag(3)....,B.))) When 3x = 1, it becomes the original HSIC.
ples, i.c. [Kx xxii xx (I,, (
We learn the optimal reweighting function to reweight the samples and test independence by maximizing this reweighted statistic. Next we analyze its asymptotic be- haviors under Ho and Hi.
Asymptotic Distribution for Reweighted HSIC
We now describe the null distributions of the test statis- ties given a known reweighting function 3(.). Suppose D= [w = {(x,, y)) We first define a symmetric function that satisfies HSIC (D) = 3 Ensor hijor as
Therefore, if X Y, we have that ((xte) is also indepen- dent of Y. and thus no spurious dependence between X and Y would be introduced in the reweighted distribution using ((zx)).
1 ljgr
Σ
(B.
Final Objective Function
+ 133,3eaneeke
23 23,8.Bu
To ensure that our learned 3(-) satisfies Def. 3.2, we con- strain & 2 0 and 1 E B = 1. Besides, we add two regularization terms. First, we aim to select more data points to avoid trivial solutions (c.g., a few extreme 3, val- ues assigned to uninformative noise samples while all others
Here the sum represents all ordered quadruples (s, 1, u, v) drawn without replacement from (i. g, r) and B₁ 3(x.). Assume E(( ) < co. we have We first define a sym- metric function that satisfies

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
are set zero). This is achieved by minimizing the sam- ple variance of B,, expressed as A -i=i(( (8; 1)2, which encourages the value of 3 to approach 1. Second, we ensure the smoothness of the function 5()) by employing the smoothness functional, which could bring more stable generalization by avoiding abrupt changes for nearby in- puts. Here we assume that (()) belongs to an RKHS, while the approach can also be applied other function spaces, such as neural networks. In an RKHS, with the reproduc- ing property, we can represent (()) as ( where A vbf = Ei= (1:)) with a being the parameter vector. This formulation naturally results in the regulariza- tion term | = a Kxx a, which corresponds to the smoothness functional in an RKHS (Evgeniou et al., 2000).
3.4. Generalizability of the Learned Functions
By optimizing Problem (9), we can obtain an empirical op- timal reweighting function ((+) D. The key question remaining is whether ()-)) will generalize well to the pop- ulation level F(X,Y), Y). That is, given sufficiently large dataset, can the difference between HSIC (X, Y) and the optimal reweighted dependence measure HSTC (X, Y) di- minish and convergence to O. Through some analysis, we can see that HSIC (X, Y) - HSIC (X, is bounded by 2 supsess HSIC (X, establish convergence, it suffices to show that as the sample size n + 0o, HSIC, (D) converges to HSIC (XI for each 8 E B. If this condition holds, we can conclude the convergence property of HSTC (X,Y) to HSIC" (X,Y) as n2 + xc. In the following, we present this result.
HSIC (D)). Therefore, to
In summary, we learn the reweighting function B(-) by solv- ing the following constrained optimization problem:
Theorem 3.7 (Uniform Bound), Suppose X C IR is a closed and bounded space and the values of the kernels xxx and by are also bounded. Assume that the reweighting functions B E B are continuous and Lipschitz. Then with probability at least 1 8, we have
arg min - log J + A1 11/xx + A2
n (B= - 1)2
8
n
s.t. B 2 0,
3 n2
HSTC - HSTC H (X
sup BEB
where Jy A HSIC (Dtr). An and X2 are hyperparameters that control the regularization terms. In practice, using a normalized version of the statistics during optimization may
(10)
1
log nl 1
O
V n1
log
help avoid overfitting amplifying noise. Therefore, in the experiment, we use jul
n
n3
jg'
instead of ju! where 1n 1 Tr H3] and juz - 1
Jo
The details of the proof can be found in Appendix D.5. This bound guarantees that if our optimization process succeeds, the value of HSIC, (D) with empirically learned function can converge to the optimal value HSIC (X,Y) as n oc with a rate shown in Eq. (10).
n
The null distribution in (6) has complex form (weighted sum of x3s) and is hard to calculate the threshold. Instead, in implementation we use the permutation test to approximate the a quantile. It permutes the ordering of the Y samples for times while that of X is kept fixed, using the critical value of this statistic distribution to estimate the true one. The whole algorithm is included in Algorithm 1.
3.5. Conditional Independence Test Version
In this section, we extend our method to the Conditional Independence (CT) test. We first provide the conditional ver- sion of some previous results. The input of the reweighting function 3()) now also includes the conditioning set.
Algorithm 1 Reweighted HSIC (RHSIC)
1: Input: D: samples. C: reference variable. at signifi- cance level. B: the number of permutations.
Definition 3.8 (Conditional version of reweighting function and reweighted distribution). Let C' be either X or Y with domain C, the reweighting function set B satisfies
2: Output: p-value and test statistics value.
3: Split D into D.r- = (Itr, } and Die (Ites }.e
4: Optimize the constrained problem (9) on Drr, to obtain the reweighting function 3(-).
B = { C Z
+ R22
20 Exxriz Z)] = =1] (11)
5: Use 3 = B((r.)) to calculate Tan. = HSIC (Din).
Then VB B, the corresponding reweighted distribution P PxrІz, which is well defined with the same support of Pxyzz, can be determined by the conditional p.d.f.
6: for all & E {l...., B} do
7: Permute Vte to get Uf: and Dr. = Dee U she- 3 (D).).
8: Calculate k-th statistics Ta = HSICS
P(X,Y Y Z) B Z)P(X,Y Z).
(12)
9: end for
10: Compute value by p- 1 ΣE= 1[T 2 Tobel where
Proposition 3.9 (Maintain the conditional independence after reweighting). If X and Y are conditionally indepen- dent given Z and that is either X or Y but not both, then
I denotes the indicator function.
5

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
X and Y are still conditionally independent given Z after being reweighted by the weight B3C, Z).
residuals become Riz (x) and R2 (Y). An estimator
of the statistic J calculated on D = { Vis =)) is:
We then introduce the reweighted statistic to calculate the conditional dependence measure in the reweighted distri- bution without resampling data, Recall that HSIC is based on the idea that independence can be related to uncorre- latedness between functions in RKHS Fx and Fy. For the statistic (JO') of the kemel-based CI test (KCIT), un- correlatedness is assessed between functions in restricted function spaces, where the effect of Z is accounted for using methods such as regression (Zhang et al., 2012).
5 == Tr
1
3 12
(14)
n2
YIZ
K X == R
x R
DB.
yiz == R DB
Therefore, for the CI test, the final objective function is similar to the optimization problem (9) with J replaced by Je As in the unconditional case, in the experiment we use a normalized version of this conditional dependence measure with the denominators joJ = Tr(K zl and
Lemma 3.10 (Characterization based on conditional cross- covariance operators (Fukumizu et al., 2007)). Denote X A (X, Z), & likk,, and Fx the RKHS correspond- ing to kg. Assume Fx C. Fy C CG,, and Fz C Cz Further assume that k & a characteristic" kernel on (X x V) x Z, and that Fz + TR (the direct sum of the two RKHSs) is dense in L² (P2 Then
jel = T riz)-
Similar to independent tests, we also use permutation test to approximate the - quantile of the null distribution to test for CI. The difference is that the permutation should break the dependence between Y and X while maintaining the conditional distribution of Y given Z. Therefore, we use local permutation method on Y that utilizes the nearest- neighbor search for Z (Runge, 2018).
E Exyzz =0 -0
(13)
Exy1z can be replaced with E ExpIz where Y (Y,Z),
4. Application in Causal Discovery
Therefore the statistic is defined as jel A Exvzz HSS Actually, according to the discussion in Appendix E.4, we can interpret Σ Σxyız as the partial covariance and obtain it using the cross-covariance between residuals of feature z. where rx and ry represent the residual of X and Y regressed on Z.
In this section, we discuss how to discover causal relations when some rare dependence patterns exist. We propose a new constraint-based causal discovery method, named RD-PC (Rare Dependence PC), which leverages the PC algorithm (Spirtes et al., 2000) equipped with our proposed RKCIT to test for CL. Here assume that no latent con- founders exist. With the Markov and faithfulness assump- tion, the d-separation in the ground-truth causal graph G should theoretically exhibit an equivalent relation with the CI relations implied by the distribution. However, rare dependence hard to detect, which would result in the dele- tion of some true edges and may even lead to erroneous propagation.
maps regressed on Z. That is, E1 ry = X
Reweighted Conditional Dependence Measure
With fixed function B(-), at the population level, define 2
the reweighted KCIT (RKCIT), JU A
as:
HS'
Epp (W xiz
E x12)) @ (0r12=
2
HS
Here, we assume known reference variable C. Specifically, for two variables X and Y from the node set V that exhibit rare dependence, their dependence is significant only within a region of C's distribution. Here, C' could be third vari- able other than X and Y. providing additional information that enables RKCIT to recover dependence more effectively, thereby enhancing its flexibility.
where 6 A xt - ExIex [2] , 111 e or Eploy [Z] X1z
are the residuals of original feature maps regressing on
Z. Here PP 8(x, (0),(XXY, YY Denote the central- ized kernel matrices for X, Y, as K2 Ky and 2, respectively. Given importance weights B and the fea- ture map v-).. the unbiased estimator of the centraliza- tion now becomes dill (z) (xx) 1 Σm (x;) =
With some abuse of notation, here we use KCIT(X, Y|2) to represent the result of testing X 11 YIZ by KCTT. RKCIT((C) (X, Y|Z) is defined similarly.
(I) DD1117). Therefore we have the centralized kernel matrix K K2 x and K2 are defined similarly. We use kernel ridge re- gression to estimate conditional expectations and obtain the The estimated
n
8 x (In - -11" k2 D.11""
Assumption 4.1. VX,Y E V. Z V (X,Y), if KCTT(X, (CTT(X,Y|2))) rejects the null hypothesis, then X /l YJZ. Besides, if both KCIT Y|Z) and RKCIT (Z) fails to reject the null hypothesis, then X JL YIZ.
V
residual matrix R
K Dg +c
Many popular kemnlss are characteristic, e.g., Gaussian, Laplace, etc. See the formal definition Appendix F.I.
Assumption 4.1 ensures the reliability of the dependence detected by KCIT, In addition, also ensures the reliability
6

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
of the independence detected by RKCIT. Then we derive the following rule to check the adjacency between two variables.
Algorithm 2 Rare Dependence PC (RD-PC)
1: Input: D: dataset. V: node set. C: reference variable.
Rule 1. For any X,Y E V. if ZE S Vi(X,)) s.t. both (XIT YIZ) and RKCIT ()) fail to reject the null hypothesis, then X and Y are not adjacent in G.
2: Output: causal graph G.
3: Stage 1: Causal skeleton discovery.
4: Initialize a complete undirected graph G on V.
5: Remove the edge connected to C' in by Rule 1.
On the other hand, although RKCIT ((C) (x, Z) could discover more dependence, it introduces an extra variable C, which sometimes rejects the null hypothesis even when X TL ZIz. We summarize the scenarios in the following:
For X, E V {C), remove the edge (X, Y) in G by Rule 1. If both X and Y are not adjacent to C, using KCTT only is enough.
7: Stage 2: Eliminating extraneous edges.
For X, Y E VV (V(C), if both X and Y are adjacent to C, check whether (X, Y) are the extraneous edge. Shuffle data of C in 'D as Cperm, if Rule is satisfied, remove the edge (X, Y), and orient X - C' and + C.
Proposition 4.2. For pair of variables X, Y E V. suppose that 32 S V) s.t. (OIT(X,Y\2) fails to reject the null hypothesis. Besides, for all these 7,, we have that RKCIT (X, 1 rejects the null hypothesis. Then, under Assumption 4.1, i) X and Y are adjacent with a rare dependence, or ii) X and Y are not adjacent in G and C must be the direct common effect of X and Y.
Stage 3: Determining the orientation.
Orient edges in G with the same orientation procedure as the PC algorithm (Meek, 1995).
Proposition 4.2 tells us that if X + C Y forms a V- structure, Rule can not correctly remove the edge between X and Y when executing the PC algorithm to recover the causal skeleton. Consequently, the inferred graph tends to be a superset of the true one. To recover the true causal skeleton and eliminate extraneous edges, we introduce our correction methods.
1.1.1. 1. INDEPENDENCE TESTS
We use the following two generation process, which covers two common scenarios where rare dependency occurs.
Data Generation (DG I). We slightly modify Example 1.1 with different variance o² for ~ .N(0, o²) to evaluate power. To test Type error, we set Y e with fixed = 0.5.
For two variables X, Y E V that satisfy the con- dition in Proposition 4.2, if there exists Z S VXX,Y,, such that R (X, Y Z) fail to reject the null hypothesis, then X and Y are not adjacent in G. Here Cperr denotes the shuffled C in dataset D.
Rule 2.
Data Generation II (DG II). We use a variant of the exper- iment in (Strobl et al., 2019). To evaluate the Type error, we generate data that follows X = (1xs), Y f2(E,), where Egs Ey are independently drawn from (00 and fi and f2 are smooth functions chosen uniformly from a set (see Appendix G.I). To compare the power, we generate X = fi(ez) + Eb, and then we generate Y f2(ey) + e if X < 7 where 7 is threshold, and Y = f2(5,) otherwise.
Based on Rule and Rule 2, we summarize the procedure of RD-PC in Algorithm 2. Theorem 4.3 shows its soundness.
Theorem 4.3. With Assumption 4.1, the causal Markov assumption and faithfulness assumption, Algorithm 2 cor- rectly recovers the underlying causal graph structure up to its Markov equivalence class.
Baselines. All the baselines follow their default settings un- less stated otherwise. HSIC (Gretton et al., 2007): the orig- inal HSIC test using gamma approximation. RDC (Lopez- Paz et al., 2013): use canonical correlation between finite set of random Fourier features. FHSIC (Zhang et al., 2018): HSIC using mimee-dimensional random Fourier feature map- pings to approximate kernels. FisherScan (Ma & Mao, 2019): Generalized Fisher's ' exact test on contingency tables and continuous sample spaces. LFHSIC (Ren et al., 2024): HSIC test with adaptively learned bandwidth. For all the other methods in our paper, including ours, use Gaussian kernel with median heuristic bandwidth.
We provide the proof and more discussion in Appendix F.
5. Experiments
We apply the proposed testing method to both synthetic and real data to evaluate their performance. Due to space limita- tion, causal discovery experiments see Appendix G.I. Codes are available at
5.1. Simulation Experiments
Results. In Fig. 4, we demonstrate that our method consis- tently controls Type I errors and that its power outperforms other baselines in both Data Generation I and II. For DG I, our method performs well because we not only try to find the sub-samples but also reweight them with a weight possibly larger than 1, effectively enlarging the size of the
For testing independence, we conduct experiments with varying numbers of samples and different levels of rare dependence in two generating settings. For testing CI, we further provide a comparison between various dimensions of the conditioning set. More details see Appendix G.
7

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Type I Error
Data Generation
Data Generation II
n=1000, r= 0.1
n=1000 0.1
Type eerrr rate
0.15
lest power (f)
Test power (1)
0.6
0.3
Test power (t)
F..6
B
0.10
0
e
0.4
Type error
0.2
0.4
X
0.05
0
0.2
0.1
0.2
0.00
DG1 l
DG II
0.4
0.5
0.6
0.01
0.02
0.03
0.0
5
10
5
10
r
Dimension of Z
Dimension of 2
-e- HS C
HSIC RFF -A-
-V-
LFHSIC
-X-
RDC
-
fisherScan
-E- Ours
-0-
KCIT
-A-
RKCIT
-P-
LPCI
-X- NNLSCIT
-Ei Ours
Figure 4. Left: Type I error rate and power of independence tests on DG I and DG II with 1000 samples. The first graph shows the Type I error rate for 6 methods in both data generations, where the significance level 0.05 annotated as the black line. The second and third graphs show the test power for DG I and II with different parameters respectively. Right: Type error rate and power of CI tests with different sizes of conditional set Z. We fix the sample size n = 1000 and the ratio of the rare dependence 7 = 0.1.
dependent sub-sample. For DG II, the advantage of our method becomes more obvious when the data become more imbalanced, i.c., 7 - O. For visualization of the important sub- samples found in example data, see Appendix G.
KCIT (Zhang et al., 2012). RCIT (Strobl et al., 2019), CCIT (Sen et al., 2017), GCIT (Bellot & van der Schaar, 2019), FCIT (Chalupka et al., 2018), GCM (Shah & Peters, 2020), and NNLSCIT (Li et al., 2024b). Results of some baselines are shown in Appendix G for beauty.
On the left of Fig. 5 compares the Type I error and power of the methods with different sample sizes n, where n E (500, 1000, 1500, 2000, 2500, 3000}. We fix = 0.5 and 0.01 for DG I and DG II respectively. Most meth- ods including ours succeed in controlling Type I error rate around 0.05, while LFHSIC and HSIC have a relatively unstable Type I error rate. Our method again consistently performs better in testing power, which confirms the need for sample-level importance reweighting when facing rare dependence. We note that the performance of the baselines also improves as increases, which is expected since the range of the significant dependent region is fixed. Note that HSIC almost always overlaps with LFHSIC for DG II, manifesting that optimizing the bandwidth of kernels is not enough to detect rare dependence. RDC performs well in DG while it struggles in DG II, further showing the genericity of our method.
Results. In the right of Fig. 4, we fix = 0.03 and compare the performance of different methods with various dimen- sions of the conditional set Z. Most methods except KCTT maintain Type I error around 0.05. This behaviour may be attributed to the error caused by gamma distribution ap- proximating the null distribution. On average, our method significantly outperforms other methods in testing power and achieves a power 50% better than KCIT, All the base- lines here are unsensitive to the increasing of the dimension of the conditioning variable.
We also enumerate T E (0.01, 0.03) to generate samples with different ratios of the sub-samples that are significantly dependent, as shown in Fig. 5, We use this setting to model different levels of rare dependence. The dimension of the conditioning variable Z is fixed 10 and the number of samples 1000. Our method achieves better perfor- mance than the baselines, especially compared to KCTT.
5.1.2. CI TESTS
Data Generation. We follow the synthetic experiment proposed in (Scetbon et al., 2022) with a slight variation. To compare the Type I error, we generate simulated data by:
5.2. Real-world Experiments
Sachs Dataset. We apply our RHSIC to a flow cytometry dataset (Sachs et al., 2005), which gives n 853 obser- vational measurements of 11 proteins. Here we focus on the dependence relationship between (PKA, PJINK). This pair is dependent according to the ground truth causal graph in Fig. 11. However, as the results discussed in (Mooij & Heskes, 2013), many popular (conditional) independence tests cannot detect this dependence relation. We compared our RHSIC with HSIC since theoretically these two pairs are dependent conditioning on empty set. The p- p-value produced by HSIC with default settings is 0.601, while our method successfully detected the dependence with p-value = 0.004. See Appendix G.3 for more details.
X = x (()++e)), Y = f2(Z= + +Ey)
Above, ž is the average of Z = (Z,, ... Zz,), Ex and Ey are sampled independently from ./ (0, 1). and fi and f2 are smooth functions chosen from the same set as in DG II The following generating function is for evaluating power:
x = (z + &,, Y ff( + Ey) + Eb.
x T,
x = f1 (Z + Eb, Y = =f + Ey);
if 2T. T.
where Q ~ (' 1), S. ~ 1). T 10, 1] is threshold and we set T equals to the 7-th percentile of X.
Financial Dataset. We also apply our method to monthly
Baselines. We compare with the following CI methods:
8

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Type lerror rate (4)
DG 0.5)
DGI (o- 0.5)
lerrar rate (4)
DG (T, - 0.01)
DG I (T; - 0.01)
1- 250-10
0.20
0.8
0.20
KCT RCT Ur
0.15
Test power
0.5
0.15
Test power
0.4
0.4
0.05
0.2
0.05
Tout
0.00
1000
2000
3000
1000
2000
3000
0.00
1000
2000
3000
1000
2000
3000
9.13 00b 0.20
9925 0039
number of samples
number of samples
number of samp
number of samples
-9 HSRC
-A-
RFF
-V- UNSIC
-X-
RDC -ES Ours
Figure 5. Left: Type error and Power of DG (first and second figure) and DG II (third and fourth figure) with different sample sizes. The first row represents Type error rates and the second row shows test power. Right: Testing powers of CI tests with various ratios of significantly dependent sub-samples. We fix the number of samples 1000 and the size of conditional set 7 10.
JPY/USD exchange rates (E) and U.S. federal funds rates (F) from 1990 to 2010, sourced from Federal Reserve Economic Data (FRED). Each month records datapoint, resulting in 251 samples in total. While the original HSIC fails to reject independence with p-value equals to 0.2174, RHSIC de- tects dependence with p 0.0005 using F as the reference variable. The Icarned weights assign higher importance to the samples in 2001 and 2008. These correspond to the Dot- com recession and the global financial crisis, respectively - showing that our method not only detects rare dependence but also provides interpretable insights.
biomarkers for targeted interventions in precision medicine and supports the inference of group-specific causal effects. Additionally, fine-grained causal structures support context- aware fairness by mitigating biases arising from majority groups. As discussed earlier, our method is well-suited to handle context-specifer or local independence scenarios, due to the complementary nature of its objectives. For example, Example 3.1 and Data Generation II & III in our experi- ments involve local dependence, and our method performs well these cases, as the low (near-zero) weight samples often help to identify locally independent regions.
6. Discussion
7. Conclusion
Some previous works fall into the subset of our setting. A line of research focusing on "local dependence" (Ab- berger, 2002; Uçer& & Bayramoğlu, 2007; Sricharan et al., 2011; Tjosthemm et al., 2022; Gorsky & Ma, 2022) actually helps quantify and visualize fine-gre grained dependence rela- tionship while lacking a formal testing procedure being restricted to a hard "local region". Context-Specific Inde- pendence (CSI) (Pensar et al., 2016; Hwang et al., 2023; Poole & Zhang, 2003; Boutilier et al., 2013; Pensar et al., 2015; Hwang et al., 2024) aims to find a more fine-graine grained independence relation, which is conceptually related to our objective, though approached from the perspective of in- dependence rather than dependence. The complementarity actually enables cussed in the next paragraph. (Wang, 2020; Wang et al., 2021) defined a term "rare events" to describe extremely im- balanced data for parameter estimation. The data- generating process proposed is a specific instantiation of our setting similar to Example 3.1 and thus solvable by our tests.
We focus on the problem of testing conditional indepen- dence in the presence of rare dependence, where the de- pendence is significant only in small regions of the sample. We propose a reweighted (conditional) dependence mea- sure, which adaptively reweights samples enhance the ability detect subtle dependence structures. We provide asymptotic analysis of the reweighted statistics and a con- sistency analysis of our approach to ensure its theoretical soundness. The theoretical results are applied to the causal discovery task, demonstrating their applicability in structure learning the presence of rare dependence. Extensive ex- periments on synthetic and real-world datasets validated the efféctiivnness of our method, highlighting its potential for broad applications in data analysis. Future work can explore extending our reweighting methods to other tasks.
methods to handle such cases, dis-
A Acknowledgements
The authors would like to thank the anonymous reviewers for their helpful comments. We would also like to acknowl- edge the support from NSF Award No. 2229881, AI Insti- tute for Societal Decision Making (AI-SDM), the National Institutes of Health (NIH) under Contract R01HL159805. and grants from Quris AI, Florin Court Capital, and MBZUAI- WIS Joint Program. MG was supported by ARC DE210101624, ARC DP240102088 and WIS-MBZUAI 142571. XW acknowledges the support from National Nat- ural Science Foundation of China (Grants No. 12171076).
The importance weights learned by our method naturally highlight subgroups of data that contribute most captur- ing the underlying dependence signal. As demonstrated in our real-world dataset analysis, these weights enhance inter- pretability for downstream applications. Notably, the algo- rithm in Sec. is capable of uncovering fine-grained causal structures by highlighting context-dependent relationships. This, in turn, facilitates the identification of context-specific
9

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Impact Statement
Chickering, D. M. Optimal structure identification with greedy search. J. Mach. Learn. Res., 3:507-554, 2002.
This paper presents work whose goal is to advance the field of Machine Learning and Causality. There are many poten- tial societal consequences of our work, none which we feel must be specifically highlighted here.
Chickering, D. M. and Heckerman, D. Efficient approxi- mations for the marginal likelihood of bayesian networks with hidden variables. Mach. Learn., 1997.
Daudin, Partial association measures and an application qualitative regression. Biometrika, 67(3):581-59) 1980.
References
Abberger, K. Exploring local dependence. Technical report, CoFE Discussion Paper, 2002.
Doran, G., Muandet, K., Zhang, K., and Schölkopf, B. A permutation-based kernel conditional independence test. In UAI, pp. 132-141. Citeseer, 2014.
Angst, M. S. and Clark, J. D. Opioid-induced hyperalgesia: qualitative systematic review. Anesthesiology, 104(3): 570-587, 2006.
Erdos, P. and Renyi, A. On random graphs i. Publicationes Mathematicae, 6:290-297, 1959.
Aryasetiawan, F., Imada, M., Georges, A., Kotliar, G., Bier- mann, S., and Lichtenstein, A. Frequency-dependee lo- cal interactions and low-energy effective models from electronic structure calculations. Physical Review B 3--Coneensed Matter and Materials Physics, 70(19): 195104, 2004.
Evgeniou, T., Pontil, M., and Poggio, T. Regularization
networks and support vector machines. Advances in com- putational mathematics, 13:1-50, 2000.
Fan, Y., de Micheaux, L., Penev, S., and Salopek, D. Multivariate nonparametric test of independence. Journal of Multivariate Analysis, 153:189-22 220, 2017.
Bach, F. R. and Jordan, M. I. Kernel independent component analysis. Journal of machine learning research, 3(Jul): 1-48, 2002.
Fukumizu, K., Bach, F. R., and Jordan, M. I. Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces. Journal of Machine Learning Research, (Jan):73-99) 2004.
Bellot, A. and van der Schaar, M. Conditional independence testing using generative adversarial networks. Advances in neural information processing systems, 32, 2019.
Fukumizu, K., Gretton, A., Sun, X., and Schölkopf, B. Ker- nel measures of conditional dependence. Advances in neural information processing systems, 20, 2007.
Benesty, J., Chen, J., Huang, Y., and Cohen, Pearson correlation coefficient. In Noise reduction in speech pro- cessing, pp. 1-4. Springer, 2009.
Gao, W., Oh, S., and Viswanath, Demystifying fixed k-nearest neighbor information estimators. IEEE Trans- actions on Information Theory, 64(8):5629-5661. 2018.
Berlinet, A. and Thomas-Agnan C. Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
Geiger, D. and Heckerman, D. Learning gaussian networks. In Uncertainty Proceedings 1994, pp. 235-244--4 255-243, Elsevier, 1994.
Boutilier, C., Friedman, N., Goldszmidt, M., and Koller,
D. Context-specific independence in bayesian networks. arXiv preprint arXiv: 302..3562 2013.
Gorsky, and Ma, L. Multi-scale fisher's independence test for multivariate dependence. Biometrika, 109(3): 569-587, 2022.
Buntine, W. Theory refinement on bayesian networks. In Uncertainty proceedings 1991, pp. 52 60. Elsevier, 1991.
Greenwood, P. F. and Nikulin, M. S. A guide to chi-squared testing, volume 280. John Wiley & Sons, 1996.
Candes, E., Fan, Y., Janson, L., and Lv. J. Panning for gold:' model-x' knockoffs 'kookoo for high dimensional controlled variable selection. Journal of the Royal Statistical Society Series B: Statistical Methodology, 80(3):551-577,200
Gretton, A. A simpler condition for consistency of a ker- nel independence test. arXiv preprint arXiv: 10l.:1501.0603.. 2015.
Casella, G. and Berger, R. L. Statistical Inference. Duxbury, Pacific Grove, CA, 2nd edition, 2002.
Gretton, A., Herbrich, R., and Smola, A. J. The kemel mutual information. In 2003 IEEE International Confer- ence on Acoustics, Speech, and Signal Processing. 2003. Proceedings 03)., volume 4, pp. IV-880. IEEE, 2003.
Chalupka, K., Perona, P., and Eberhardt, Fast conditional independence test for vector variables with large sample sizes. arXiv preprint arXiv: /004:0000.00 004002747, 2018
10

---

Extracting Rare Dependence Patterns via Adaptive Sample Rewcighting
Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. Measuring statistical dependence with hilbert-schmidd norms. In International conference on algorithmic learn- ing theory, pp. 63-77. Springer, 2005a.
Li, L., Ng. I., Luo, G., Huang, B., Chen, G., Liu, T., Gu, B., and Zhang, K. Federated causal discovery from heteroge- neous data, arXiv preprint 2iiv:2402.13244 2024a.
Li, S., Zhang, Y., Zhu, H., Wang. C., Shu, H., Chen, Z., Sun, Z., and Yang. Y. K-nearest-neighbot local sampling based conditional independence testing. Advances in Neural Information Processing Systems, 36, 2024b.
Gretton, A., Smola, A., Bousquet, O., Herbrich, R., Belitski, A., Augath, M., Murayama, Y., Pauls, J.. Schölkopf, B., and Logothetis, N. Kernel constrained covariance for dependence measurement. In International Workshop on Artificial Intelligence and Statistics, pp. 112-119. PMLR, 2005b.
Li, Y., Pogodin, R., Sutherland, D. J., and Gretton, A. Self- supervised learning with kernel dependence maximiza- tion. Advances Neural Information Processing Systems, 34:15543-15556 2021.
Gretton, A., Fukumizu, K., Teo, C., Song. L., Schölkopf. B., and Smola, A. A kernel statistical test of independence. Advances in neural information processing systems, 20, 2007.
Lopez-Paz, D. and Oquab, M. Revisiting classifier two- sample tests. arXiv preprint wrxiv:1610.065000 2016.
Heckerman, D., Geiger, D., and Chickering, D. M. Learning bayesian networks: The combination of knowledge and statistical data. Mach. Learn., 1973):177-243, 1995.
Lopez-Paz, D., Hennig, P., and Schölkopf, B. The ran- domized dependence coefficient. Advances in neural information processing systems, 26, 2013.
Hoyer, P., Janzing, D., Mooij, J. M., Peters, J., and Schölkopf, B. Nonlinear causal discovery with additive noise models. Advances in neural information processing systems, 21, 2008.
Ma, L. and Mao, J. Fisher exact scanning for dependency. Journal of the American Statistical Association, 114(525): 245-258, 2019.
Meek, C. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh conference on Uncertainty in artificial intelligence, pp. (03-410, 1995.
Huang. C. Time spent on social network sites and psycho- logical well-being: A anla-as..ysis. Cyberpsychology, Behavior, and Social Networking, 20(6):346-354, 2017.
Hwang, I., Kwak, Y., Song, Y.-J., Zhang, B.-T., and Lee, S. On discovery of local independence over continuous variables via neural contextual decomposition. In Confer- ence on Causal Learning and Reasoning, pp. 148-472. PMLR, 2023.
Mooij. J. and Heskes, T. Cyclic causal discovery from con- tinuous equilibrium data. arXiv preprint arXiv: 2013.
Mukherjee, S., Asnani, H., and Kannan, S. Comi: Classifier based conditional mutual information estimation. In Un- certainty in artificial intelligence, pp. 1083-1093, PMLR, 2020.
Hwang, I., Kwak, Y., Choi, S., Zhang, B.-T., and Lee, S. Fine-grained causal dynamics learning with quantization for improving robustness in reinforcement learning. arXiv preprint ar arXiv:2406.00 03234,, 2024.
Ng, I., Ghassami, A., and Zhang, K. On the role of sparsity and DAG constraints for learning linear dags. In NeurlPS, 2020.
Imbens, G. W. and Rubin, D. B. Causal Inference in Statis- ties, Social, and Biomedical Sciences. Cambridge Uni- versity Press, 2015.
Oentaryo, R., Lim, E.PP., Finegold, M., Lo, D., Zhu, F,, Phua, C., Cheu, E.-Y., Yap, G.-E., Sim, K., Nguyen, M. N., et Detecting click fraud in online advertising: a data mining approach. The Journal of Machine Learning Research, 15(1):99-144 140, 2014.
Jitkrittum, W., Szabó, 7., Chwialkowski, P., and Gretton, A. Interpretable distribution features with maximum test- ing power. Advances in Neural Information Processing Systems, 29, 2016.
Jitkrittum, W., Szabó, Z., and Gretton, A. An adaptive test of independence with analytic kernel embeddings. In International Conference on Machine Learning, pp. 1742-1751. PMLR, 2017.
Pensar, J., Nyman, H., Koski, T., and Corander, J. La- beled directed acyclic graphs: a generalization of context- specific independence in directed graphical models. Data mining and knowledge discovery, 29:503-533, 2015.
Keles, B., McCrae, N., and Grealish, A. A systematic re- view: the influence of social media on depression, anxiety and psychological distress in adolescents. International journal of adolescence and youth, 25(1):79-99) 2020.
Pensar, J., Nyman, H., Lintusaari, J., and Corander, J. The role of local partial independence in learning of bayesian networks. International journal of approximate reason- ing, 69:91-105, 2016

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Póczos, B., Ghahramani, Z., and Schneider, J. Copula- based kernel dependency measures. arXiv preprint arXiv: 1216:4220.46666 2012.
Spirtes, P., Glymour, C., and Scheines, R. Causation, Predic- tion, and Search, Second Edition. Adaptive computation and machine learning. MIT Press, 2000.
Poole, D. and Zhang, N. L. Exploiting contextual inde- pendence in probabilistic inference. Journal of Artificial Intelligence Research, 18:263-313, 2003.
Sricharan, K., Hero, A. O., and Rajaratnam, B. A local dependence measure and its application screening for high correlations in large data sets. In 14th International Conference on Information Fusion, pp. 1-8. IEEE, 2011.
Poole, D. L. Context-specific approximation in probabilistic inference. arXiv preprint arXiv: 300.74088 2013.
Strobl, V., Zhang. K., and Visweswaran, S. Approximate kernel-based conditional independence tests for fast non- parametric causal discovery. Journal of Causal Inference, 7(1):20180017, 2019. 2019
Ren, Y., Xia, Y., Zhang, H., Guan, J., and Zhou, S. Learning adaptive kernels for statistical independence tests. In International Conference Artificial Intelligence and Statistics, pp. 1494-2502. PMLR, 2024.
Su, L. and White, H. A consistent characteristic function- based test for conditional independence. Journal of Econometrics, 141 2000000773,,077.... 2007.
Rényi, A. On measures of dependence. Acta mathematica lungarica, 10(3-4):441455) 1959.
Tikka, S., Hyttinen, A., and Karvanen, Identifying causal effects via context-specific independence relations. Ad- vances in neural information processing systems, 32, 2019.
Runge, J. Conditional independence testing based on nearest-neighbor estimator of conditional mutual infor- mation. In International Conference on Artificial Intelli- gence and Statistics, pp. 938 947. Pmlr, 2018.
Tiku, M. Tables of the power of the f-test. Journal of the American Statistical Association, 62(318):525-539, 1967.
Sachs, K., Perez, O., Pe'er, D., Lauffenburger, D. A., and protein-sinnlingg
Nolan, G. P. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 357(11))): 523-529, 2005.
Tjøstheim, D., Otneim, H., and Støve, B. Statistical depen- dence: Beyond pearson's p. Statistical science, 37(1): 90-109, 2022.
Scetbon, M., Meunier, L., and Romano, Y. An asymptotic test for conditional independence using analytic kernel embeddings. International Conference on Machine Learning, pp. 19328-19346. PMLR, 2022.
Üşer, B. H. and Bayramoğlu, i. A new epsilon- local depen- dence measure and dependence maps. 2007.
Wang. H. Logistic regression for massive data with rare events. In International Conference on Machine Learning, pp. 9829-9836. PMLR, 2020.
Sen, R., Suresh, A. T., Shanmugam, K., Dimakis, A. G., and Shakkottai, S. Model-powerss conditional independence test. Advances in neural information processing systems, 30, 2017.
Wang. H., Zhang, A., and Wang, C. Nonuniform negative sampling and log odds correction with rare events data. Advances in Neural Information Processing Systems, 34: 19847-19859, 2021.
Shah, R. D. and Peters, J. The hardness of conditional inde- pendence testing and the generalised covariance measure. The Annals of Statistics, 48(3):151411538 2020.
Wei, D., Gao, T., and Yu, Y. Dags with no fears: A closer look at continuous optimization for learning bayesian networks. In NeurlPS, 2020.
Shao, Mathematical statistics. Springer Science Busi- ness Media, 2008
Shi, C., Xu, T.. Bergsma, W., and Li, L. Double generative adversarial networks for conditional independence testing. Journal of Machine Learning Research, 22(285):1-32, 2021.
Xu, X. and Zheng, L. Neural feature learning in function space. Journal of Machine Learning Research, 25(142): 1-76, 2024.
Yu, Y., Chen, J., Gao, T., and Yu, M. DAG-GNN: DAG structure learning with graph neural networks. In ICML, volume 97, pp. 7154-7163, 2019.
Shimizu, S. Lingam: Non- Non-gaussian methods for estimating causal structures. Behaviormetrika, 41(1):65-96 2014.
Song. L., Smola, A., Gretton, A., Borgwardt, K. M., and Bedo, Supervised feature selection via dependence estimation. In Proceedings of the 24th international con- ference on Machine learning, pp. 820-830, 2007.
Zhang, A., Liu, F. Ma, W., Cai, Z., Wang, X., and Chua, T.S. Boosting causal discovery via adaptive sample reweighting. In The Eleventh International Conference on Learning Representations, 2023.
12

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Zhang, K. and Hyvarinen, A. On the identifiability of the post-nonlinear causal model. arXiv preprint arXiv: 1205.2599 2012.
Zhang, K., Peters, J., Janzing, D., and Schölkopf, Kernel- based conditional independence test and application in causal discovery. arXiv preprint arXiv: / 202.33775 2012.
Zhang, Q., Filippi, S., Gretton, A., and Sejdinovic, D. Large- scale kernel methods for independence testing. Statistics and Computing, 28: 13-130, 2018.
Zheng, X., Aragam, B., and Pradeep Ravikumar, e. a. Dags with NO TEARS: continuous optimization for structure learning. NeurlPS, pp. 9492-9503, 2018.
Zheng, X., Dan, C., Aragam, B., Ravikumar, P., and Xing, E. P. Learning sparse nonparametrie dags. In AISTATS, volume 108, pp. 3414-3425. PMLR, 2020.
Zheng. Y., Huang, B., Chen, W., Ramsey, J., Gong, M., Cai, R., Shimizu, S., Spirtes, P., and Zhang, K. Causal-leam: Causal discovery in python. Journal of Machine Learning Research, 15(60))1-8, 2024.
13

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Organization of Appendices
Section A: Table of Symbols and Notations.
Section B: Detailed Related Works.
Section C: Reweighting Functions and the Reweighted Distribution.
Section D: Details about the Unconditional Independence Statistic.
Section E:
Details about the Conditional Independence Statistic.
Section F: Details about Causal Discovery.
Section G: Supplementary Experimental Details and Results.
Section H: Discussions.
A. Notations
Table Notation Table
Symbol
Description
X, Y,
Random variables (or sets of variables)
X,Y.
Domains for random variables
Fy,
Reproducing kernel Hilbert spaces (RKHS)
Sample vectors (or matrices)
Di,
Specific values of sample vectors (or matrices)
kx(xxx'), ky,,,,yyyyyy v'), Az(2,
Kernel functions on the input spaces X, Feature maps for X, Z
((),
Kx, Ky, Kz
Kernel matrice on samples 1,
EXY
Cross-Covariance operator
- I|F
Norm RKHS
[[X]
Expectation of X
[ar[X]
Variance of X
Cov [X]
Covariance of X and Y
R20
The set of positive real numbers (including 0) Borel o-algebra on R
B(R)
Pxy
Joint distribution of X and Y
PXYIZ
Joint distribution of and conditioned on Z
Tr|
The trace matrix
Tensor product
O
Big O notion
Number of samples
Y
X is independent of Y
(F)
The set of all r-tuples drawn without replacement
(n)x
Number of permutations
1(12,,,11-11.
Covering number with radii for equipped with infinite norm
1(0,
Normal distribution with zero mean and standard deviation
100
Uniform distribution in (0,
14

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
B. Related Works
In this section, we provide a more comprehensive review of literature.
B.1. Independence Tests
Traditional independent tests for discrete/categorical data include F-test (Tiku, 1967) and Chi-squared test (Greenwood & Nikulin, 1996). Testing independence for continuous variables is more challenging. Pearson correlation coefficient (Benesty et al., 2009) is often used to measure the correlation between variables. However, it only reflects linear dependence. In order to measure broader dependence, a class of kerne--based independence testing (Bach & Jordan, 2002: Gretton et al., 2005b; 2003; 2005a) was proposed. These methods the nonlinear dependence of variables by sufficiently adequate mappings under function classes. Under the reproducing kernel Hilbert space (RKHS) (Berlinet & Thomas-Agnan 2011) space, the kernel function is defined as a distance metric induced by the inner product of the feature mapping. One widely-used kernel-based independence test is the Hilbert Schmidt Independence Criterion (HSIC) (Gretton et al., 2005a), which measures dependence by the squared Hilbertt-chhidd norm induced by the cross-covariance operators in the RKHS space. Besides, the random dependence coefficient (Lopez-Paz et al., 2013) (RDC) was proposed. Compared to the kernel-based method, RDC is computationally efficient and easily implemented. This method ensures the marginal invariance by using copula transformation, and measures the dependence between variables by maximizing the correlation under random projection of copula transformation.
mainly based on the framework proposed by Rényi (Rényi, 1959) to measure
B.2. CI Tests
Conditional independent tests are generally more difficult than independent tests due the hardness of estimating the conditional density distribution compared to the marginal distribution. A class of metric-based CI test (Su & White, 2007) employs number of kernel smoothers to estimate conditional characteristic functions. This type of kernel smoothing estimation has a large computational cost when the condition set is high-dimensional. Another widely used method is kernel-based conditional independence testing such as KCIT (Zhang et al., 2012). KCIT is based on the partial association framework proposed by Daudin (Daudin, 1980) and uses conditional cross-correlation operators to identify conditional independence. Later, the approximate kernel-based method RCIT (Strobl et al., 2019) was proposed. which uses random Fourier features to approximate the Gaussian kernel, resulting in improvement in the computational efficiency of KCIT. Another class of methods (Doran et al., 2014; Bellot & van der Schaar, 2019; Shi et al., 2021; Runge, 2018; Sen et al., 2017; Mukherjee et al., 2020) obtains the distribution of the statistic under the null hypothesis by estimating the conditional density function or conditional mutual information, followed by a hypothesis test to determine conditional independence. The permutation-based method (Doran et al., 2014) obtains resampled samples of factorized distribution by performing permutations on the samples that satisfy a specific structure. Some other methods (Bellot & van der Schaar, 2019; Shi et al., 2021), use generative models to estimate the conditional density. The method (Runge, 2018; Mukherjee et al., 2020) uses k-nearest-neighbor (KNN) to obtain factorized distribution or estimate Kullback-Leibler (KL) divergence by classification to estimate conditional mutual information for judging conditional independence.
B.3. Context-specific Independence or Local (In-)Dependence
The methods for measuring local (in>)dependence (Pensar et al., 2016; Tjøstheim et al., 2022; Hwang et al., 2023) help visualize the fine-grained dependence relationship while lack formal testing procedure. Context-Specifte Independence (CSI) (Poole & Zhang, 2003; Boutilier et al., 2013; Poole, 2013; Pensar et al., 2015; Hwang et al., 2024) aims to find more fine-grained independence relation, which is conceptually related to our objective, though approached from the perspective of independence rather than dependence. The methods are mainly to find the specific contexts (subspaces of the variable domain) that conditional independence relationships hold. It is a widely used local independence relationships. To encode CSI relationships in graphical models, (Pensar et al., 2015) introduced Labeled Directed Acyelic Graphs (LDAGGs). Later, (Pensar et al., 2016) introduced partial conditional independence (PCI), which is generalization of CSI. Several recent efforts have aimed to identify local causal structures for continuous variables. However, CSI aims to find independence while we focus on dependence. And CSI has hard threshold for independent and dependent samples, making it more restricted scenario compared to rare dependence in our paper (Pensar et al., 2015).
15

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
B.4. Causal Discovery
Traditional causal discovery methods include constraint-basee and score-based methods. Constraint-based methods such as PC (Spirtes et al., 2000) first CI tests to obtain the causal skeleton, then employ V-structures and consistent propagation to infer the directions. Score-based methods such GES (Chickering, 2002) search for the best-scored candidate graph with pre-defined score function (e.g., BIC/MDL score (Chickering & Heckerman, 1997), BGe score (Geiger & Heckerman, 1994) for linsar-Gaussian models, the BDeu/BDe (Buntine, 1991; Heckerman et al.. 1995) score for discrete data. When the number of variables is large, the score-based methods usually employ a heuristic strategy to speed up the search process. Recently, NOTEARS (Zheng et al., 2018) innovatively proposes differentiable characterization of acyclicity, which converts score-based causal discovery from combinatorial optimization problem continuous optimization problem. Following that, some variants (Yu et al., 2019; Ng al., 2020; Wei et al., 2020; Zheng et al., 2020) were proposed to extend NOTEARS into more scenarios. Without further assumptions, we can only recover the underlying causal graph up to is Markov equivalence class. To make it fully identifiable, a widely used class of methods (Shimizu, 2014; Hoyer et al., 2008; Zhang & Hyvarinen, 2012) assumes that the data generation process satisfies a specific functional model. These function causal model-based causal discovery methods can use asymmetries in statistical dependencies to determine the direction between variables.
C. Reweighting Functions and the Reweighted Distribution
C.1. Proof of Proposition 3.3
Proposition 3.3 (Maintain the independence after reweighting). If X and Y are independent and C' is either X or Y but not both, then X and Y are still independent in the reweighted distribution of (X,Y) with weight B(C).
Proof. First we consider the case = X. Define Pxx _ ((X) -Px.
Since X TL L.Y.Px Prlx = PxPy
P xx = 3(X) Px Pyjx = ((X))xXP = x PPPP
(15)
And in the other case, C = Y. Define this time Py _ B(Y) Py. Similarly we have
P Pxy = 3(Y) Px Py|x = 3(Y)PxPP PxPr,
(16)
That is, Pxy is factorable in terms of X and Y, meaning that X and Y are still independent according to Pxy-
C.2. Proof of Proposition 3.9
Proposition 3.9 (Maintain the conditional independence after reweighting). If X and Y are conditionally independent given Z and that C is either X or Y but not both, then and are still conditionally independent given Z after reweighted by the weight (CC, Z).
Proof. Similar the unconditional independence, we first set C X and define P x & -3XXX Z) Pxizz we have
Px = (),, Px12 PY|x2 3(X, IP Px Priz Px|zIyy12
(17)
Priz, we have since X Z gives us Px|z Pr1x2 = Px|z PYIz. Next, set C' Y and define Iyy1z & 3,Y 2)
PX = 3(Y Px PY|xz = 3(Y, Pxiz PYyz = P P
(18)
That is, Pxyjz is factorable in terms of (X, 2) and (Y,Z), meaning that X and Y are still conditionally independent given Z according PP Pxx1z2
C.3. When C is a Third Variable
We first state more general case of the definition of the reweighting function and reweighted distribution.
16

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Definition C.1 (Reweighting function and reweighted distribution). C' either subset of X or Y, it represents another variable tha is independent of (X,Y). Let C and 2 be the domain of C and Z. The reweighting function set B satisfies
(:: : 2 B Exxy (3(C, Z)] =1]
Then v/3 B, the corresponding reweighted distribution 1p Pxyaiz. which well defined with the same support of P PxYcIZ. can be determined by the conditional probability density function
P(X,Y.C 2) = 2XC, Z).
(19)
The reweighting function and the reweighted distribution in the unconditional case are a special case of this definition where the conditioning set Z is empty. In fact, the results of Proposition 3.3 can be generalized to the case when is neither X nor Y. which is useful in the causal discovery settings in our paper. In general, the following proposition imposes the constraint that C' cannot be common effect of X and Y.
Proposition C.2 (Extention of Proposition 3.3). X and Y are independent and that is a subset of X or , or C a variable that satisfies ((C) = ( (Y), where X and y are subsets of X and Y, then and are still independent in the importance reweighed distribution of (X, (X with weight B(C).
The results Proposition 3.9 can also be generalized to the case where C' a third variable that is neither X nor Y.
Proposition C.3 (Extention of Proposition 3.9). Consider that X and Y are independent given Z and Č = {C, Z} where is subset of X or or Ö is a variable that satisfies 3(Ō) = 3xz (X, Z) (Y, Z), where X and Y are subsets of X and Y. Then, X and Y are still independent given Z in the importance reweighed distribution of (X, Y, 2) with weight 3(Ö).
Note that when Z it reduces the original conditional distribution (3x 1).
C.4. Proof of Proposition 3.6
Proposition 3.6 Suppose the sample data are i.i.d. and randomly split into Dre = {Ste, Uhe} and Dir correspondingly. 3(.) maximizes the dependence measure of Dir- Then 3(-) is independent of Die.
Proof. Since the sample data are i.i.d. Vi # j. (2,, v1) IL (I,,8y). By randomly splitting the entire dataset, we have Die 1L Dtr- We can denote B(.) = f(D.r), where f is measurable function of Dir- By standard result in probability (Casella & Berger, 2002, Theorem 4.3.5 and 12), if X and Y are independent, then any measurable function of X also independent Y. Applying this fact here gives 3(-) 1L Dic.
D. Details about the Unconditional Independence Statistic
We first give some preliminaries for later proof and derivation. Definition D.1 (U-staaistics). The statistic U,, defined as follows called U-statistic with symmetric function of order m:
Un
Σ ,.,,
(20)
m
where E. denotes the summation over the (m) combinations of m distinct elements im from [1....,m}
n).
For every Utsttissiic Un as estimator of 0 E [A (X1,
Xm)), there is a closely related V-statistic defined by
Vn
Σ h X.m)
m
Proposition D.2. Let V₂ be defined by the above function and we have n i.i.d. samples { drawn from x-
17

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
(ii Assume that Eijh (X......, .... Xtn) I11 < 0o for all Sn .... Si m. Then the bias of Vn satisfies bv. (Px) = =0(nn) (n-
(ii) Assume that E h (X,,...... Xim) Pp for all S S ... S im I m. Then the variance of Va satisfies
Var(V,) Var(Un) + 0
We also define some more statistics for later derivation. For h: = 1, ,..., , m, let
hg(21,...... ..,
rx) E [ x ) X1 21,.... ,.....,Ke Nx = 2tl
E [h(2111-.... Tb: X k+ll..... Xmm))
Note that hm h. Further define ÇA Var (Na(XI...... Xx)). Theorem D.3 ((Shao, 2008), Theorem 3.16). Let Vn be V-statistics with E S mm S m.
)7 < 00 for all in
(i) If (X1() 0, then
Vn -) 0) S N(0, m²
(ii) 1/C; -0 bul <2 - Var(ha((X1,Xa) 0, then
n (V, - -)- L m(m - 1)
2 Σ Axxis
where Xīj 's are i.idd random variables having the chi-square distribution Xi and X3 's are some constants (which may depend on Px satisfying Ej= =2.
D.I. Characterization of Unconditional Independence
For (X,Y) Y) 2 x ) the cross-covariance operator Σxy :Fy - Fx is defined by (Fukumizu et al., 2004):
vʃ Fx,g ( (x,xx))) = Exy
(21)
and the covariance operator itself can be written
Σxy
Exy [(+(X) μx) @ (6(Y) (r)], μx & (xd(X), & Eyd(Y),
(22)
where the tensor product. This operator is generalization of the cross-covariance matrix between random vectors. HSIC is the squared Hilbert-Schmidt norm (the sum of the squared singular values) of this operator, mentioned in Def. 2.1
HSIC(X, Y) EEx [xx (X, X')ky (Y, Y')J Exx [kx (X, (xy
(23)
2E Ex Ikx (X, X') [ky (Y,Y
Assuming the expectations exist, where X' denotes an independent copy of X. An unbiased estimator HSIC in sample D {(I2, / drawn from distribution Pxy is the sum of three U-statisties: (Gretton et al., 2007)
HSIC (D) (n)2 (1.))11g
Σ
k
Σ
KYKT
Σ K
(24)
(n)4
(n)3
(K....)))
(KJ..)E
where kip2 kx (zx, ,,), ky by (ys, Mj), (n),. := (n-m)!* and the index set i, denotes the set all r-tuples drawn without replacement from the set nt]. A biased estimator is the one replacing U- Utstatistics with V-statistics, as in
M 1 7
HSIC&(D) = n 1
Σ
(25)
71 f.j.g
where the summation indices now denote all r-tuples drawn with replacement from {1,..., n) and 1
18

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
D.2. Derivation of the Importance Reweighted Statistics for UI Test
We first consider the statistic for the reweighted distribution on the population level. Given known reweighting function 3()), we use 3 to represent ((x), 2x x [ Ex [3 4x and fly =Ep, [øv] Ex [B Φv]- Then
HSIC (X,Y)
2 XX
= 1|pp [eex 1² @ (ør (4) ] HS =
||Bp
|(0xx - nxx @ (ōr - p HS
MS
Suppose now we have data samples D and obtain its estimator. Let (ar be the ith dimension of (x)x) and set Be - (xx)) Define H3 - D3 (I- 11 D3) and D3 - diag ($1..... Bn), that is, the diagonal matrix with 3; on its diagonal. We
know the estimator of -xx
is
8 -xy
| [00x - -ixx) 20 (dr - -ma)] l|
Then on the sample level:
HS
HS
HS
)
2
(D)
53 XY
3x (((a))
-1 1 Σ (n(((z))) n
@ (((x))
(1
MS
A=
T1
Σ Brbb(an)) ) (olca)
3k
(b(x)
-
Σ (
71
n2
n2
HS
1 D3
I - D
2
(a(aa)
--
o5(1)²
n
1 KK
Ir x Hoor by H
Hou
n
n
On the other hand, we can also obtain the estimators through U-statistics and V-statistics, which is helpful for the later analysis regarding the asymptotic distributions. On the population level.
HSTC HSTCO(X,Y) = EXY,, KB (x)) 6 (()) (XX) @ ({))Hs)) + (1 s mE e ml) H1
y Kul 18 (()) HS.
BB kx Y + Ex,x [B 12 (x, Ey, (r
E x
2Fx
Bx B (xx X, x)
By 13 by 1)]
Here (X, (), 8), and (X, 8) are independent copies of (X, with corresponding weights B, 3 and B. The HS norm of D exists when the various expectations over the kernels are bounded, which is true as long as the kernels & and I are bounded. Based on the last equation we can unbiasedly estimate the reweighted HSIC in terms of the sum of three U-statistics:
HSIC (D)
1
Σ
B.BKKKY+
1
Σ
3, -
1
Σ
(n)2
(n)a
(n)3
(.....)))
(KJ-9))
which can also be formulated as one U-statistics as follow (from a similar extension by (Song et al., 2007))
HSIC (n)
Σ
((....9.r),
(26)
(Gigg.))
1 (.....))
he (1.j.g,))
&
Σ
(B
B.B.B. 23.8
(27)
41
(s,A,u.))
The last sum represents all ordered quadruples (s, t, u, v) selected without replacement from (i,j.4.r). Note that 1o8 (i,j.gr)) is 1 in paper. We can substitute the U-statisties with V-statistics and get the biased estimator of HSIC:
a Σ n
B.B.B, 1 m 8,,
1 a n $.3.9.
HSIC (D)
M n²
B.B.K
Σ n 3.3
Σ h(.i.. (28)
ij
19

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
D.3. Proof of the Asymptotic distribution of Reweighted HSIC
Theorem 3.4 (Null distribution). Define D ((ri, v)) {wi)i=r Under Ho. the V-statistic HSIC (D) in Eq. (28) is degenerate, meaning E,, = 0. In this case, HSTC, (D) converges in distribution according to
m HSIC (D) (D)
D
Xxai
(29)
where x²t are Li.d. chi-squure variables, and x are the solutions to the eigenvalue problem
Apbi (w;) =
f Bigr he Vi (wx) of
(30)
where the integral is over the distribution of variables W4, Wy, and Wr-
Proof. First we discuss the value of Ci and C2 for (D). We calculate Ejor (1, [ first for C1 Var, (ng (1.)..)))) = Var; (Ejgr (1,j,g,)) I
(..g.))
E [1 = 4!
Σ
BlB.S + BaBohy - 2Ba
(a,2,u.))
(K..g.)
Σ
EIS (, Bik E[2
The seconod equation is due the independence between X and Y under Hy and in this case we set the input of B as X. We enumerate all the posibilities of the terms including is:
i = s: B,
+
2k
== BE [ [
R&g + k4" 22xg")
i i= a [
E
Ba
23
== E [3, B.
E [iigt + Bitus 2k
When conditioned on i, we have E k
B[A+]] = B[ = B[ and B[Kg] B[k4²) B.kgy), etc. Therefore, we have E [ j. q. = for arbitray i. which means Ci = 0. Besides, for C2 = Var, (NL)(t.i...))
Vari (Bur (1. r) j) we also have the following enumerations:
i i=sjj=:: B R + BY
2k
j= B [B
K + 3,K 23,
j j= BE |
E + Bykk - 2k(²"
ky
i= -=t =:
B,8,AY EE
ki k -2he4"
j= =u: [.[[B.4) E
ke BBK -
j=0:
BE [B,
E
2h:
i i=uj==::
8 [
E R2f + B,K 23,4
j=t: B,B
E 1 + 3.b 2/3.k [ak
j=0:
|3,
Aigt + 3yK4 - 2k(2
i i=
E |
E keff + B,Kqi - 2k(4
j = 8 B.
- [6g + B
-2
j j= E [B
E
kest + 3.8,ky - 23,h22
20

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Different from the previous discussion, this time it's unable eliminate the terms and Eyr (1,)))))))) [ be function of and j. i.e., (2 0. Then apply the results in Theorem D.3, and would have
turns out
oc
Vn [HSIC) (D) - HSIC (X
4
Σ j=1
(31)
where xi, are i...d. Chi-square variables, and Ais are the solutions to the eigenvalue problem
Xebr (wz) = h Mgg vi (ws) dF.. s.g.r Prgr th (w:) d.i...r
(32)
where the integral is over the distribution of variables wi, wy, and wy.
Theorem 3.5. Given known B()) function, where 3 ((z)). Given i.i.d samples D { 8t) ) with distribution Pxy. Using the symmetric kernel function h2 (i, (. defined above, and assume E (h (i, q, r) Under H1, an observation of HSTC (X,Y) denoted as HSTC, (D), converges in distribution as n + 0o to a Gaussian according to
Vn HSSC, (D) - HSTC (X.Y)) 2, N(0,
(33)
The variance is o = 16 E, [Rg.a.r Mbar) HSTC (XI)) (x)r where Ejgr = E
Proof. We know for the biased estimator HSTC (D) in Eq. (28), its associated U -statistic (D) in Eq. (26) has C = =are (n. (1.5. = Var, (Ejer (1,.)))) Ii])
Since under H1, Egg (t, j. gr | i)] would clearly change value for different index when n - oo, therefore Çi > Then we have HSIC, (D) converges in distribution as Eq. 8 with variance o according to theorem D.3. Since the difference between HSIC, (D) and (SIC((D) drops as 1/n as shown in Proposition D.2, HSIC, (D) converges asymptotically to the same distribution.
D.4. Derivation of Regularization and Objective Function
For unconditional independence test, we use the negative logarithm of the normalized reweighted HSIC as the dependence loss. The normalized HSIC on the population level is shown below, whose estimator is illustrated in paper
JU JuL J33
J4'
where JuH = -E [(bx(X) Epp (X)) (Ø,(Y) - 18 25 (v)))
J Σ Fex (1)(X)) Bg (x (x)))
- J = Σ R3, - (5))
This measure can be considered as generalization of the squared correlation coefficient. If we replace the operators with normal covariance matrices and HS norms with Frobenious norms (i.e., use an identity map of feature maps & and y, which will be specified later), then the above measure is the squared correlation coefficient between X and Y.
Proposition D.4. The normalized reweighted HSIC, as J defined above, ranges from 0 1, i.e., J E [0.
Proof. From Cauchy-Schwand inequality, we have for all i.j
Cov x 1v:
s /Varey IVarxxIvs(X)) (V)(()]Vaar lo,
E22 Pxx [(v:(X) Ey (x)) (Y) の5 (Y)) < EE ( Ex vxxx)) E5, (0, -Y)) (Y))
Summing over all the and j gives us J S JUL JUL
The equality achieved when X Y.
21

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
On the sample level, the normalized HSIC; ju
where the denominators can be calculated by,
22
Jer 35
27
- Σ E [b((z)] -((()))
=
Σ
BR
((((x)
1 Σ
k=1
1 Σ (a(
I -- - D
I - D 7
D3
(2(11)²
1 n - -
And the derivation of the estimator for J is similar and we have J = E, R. (1btw))s B(o(v))) Tr (r Hs)
For regularization terms, suppose the reweighting function 3(-) is selected from an RKHS, i.e., 3 BB Then we can denote 3 as 3(X) = vxxw a where w is the vector of coefficients that represent X's RKHS, i.e., w = vaa, and a is vector of parameters. In order to ensure the smoothness of function to avoid drastic changes for nearby inputs, want ||س| = a K a be as small possible. At the same time, want select as many data points possible, i.., (a;;) should preferably be close to 1. Notice that ((X) has mean of 1, this condition can be achieved by minimizing the sample variance of Br, i.e..
Kza 1 1 (a K - (K) - -1) -a K3a 21 za + 1. n
(B. 1)²
(34)
n
72
n
Note that overall these two regularization terms make the variance of the importance reweighted distribution larger. Adding all the regularization terms and simplifying the calculation by taking logarithm, the final expected minimization objective function subject to constraint Σ 3g n and 8 0, Vi is:
arg min log J An // + A
arg min
(B, 1)²
Hy H3] where JUJ
and
TT H.]
- log Tr
KxDs
11 D3
Ky
T T--11 1 D3)
n
11 T D3 ]
+ log Tr
Kx
+ log Tr
Ky I 11 D3
(35)
n
n
A2 a
X2
+
A1 K +
K2
Kză
2
n
That is, we actually find the optimized a and then calculate 3 K Kxa a instead of optimizing 3 directly. We can also translate into an unconstrained optimization problem, where 3 softmax(e) and arg min taken w.r.t e. Note that through this transformation, we restrict (3 satisfies the constraints for each optimization step. while in constrained optimization we allow slight violation (c.g, trust-region Newton-CG (trust-ncg) and Sequential Least Squares Quadratic Programming (SLSQP)). We see the constrianed method significantly outperforms the unconstrained method, which demonstrates that looser constraint space help find the better solution. For conditional independence test, we substitute j J jCC and jCI with jol , jei and jCl and get the final objective function accordingly.
D.5. Proof of the Uniform Convergence Bound
To measure whether our estimated reweighting function (3) obtained in D generalizes well on the whole population, we are interested in bounding the difference of HSIC (X, Y) and the optimal reweighted measure HSIC (X, YY, using a decomposition described below.
22

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Overall Learning Framework
HSIC (X (X,)
HSIC (X,Y) - HSIC, (D)
+ HSIC (D) - HSIC, (D)
+ (D) HSTC H (X,))
- sup BEB
HSIC (x, Y) - HSIC/ (D)
+ +0+
HSTC & (D) - HSTC (x,))
HSIC (X - HSIC
S 2 sup
BEB
A
Therefore, if we can prove A" + 0 as the sample size n + co, which requires HSIC (X, Y) convergences to HSIC, (D) for each 3 E B, we can actually obtain the convergence property of HSIC* (x, to HSIC (X,Y) as n - co. In the following, we will represent this uniform convergence result. First, we list some required assumptions in the proof. Assumptions
ii) X' C Idd is a closed and bounded space.
iii) The functions 3(-) E B are continuous and Lipschitz.
(iii) The kernels xxx and ky are uniformly bounded by the lower bound and the upper bound:
sup xx (x, S vi,
sup ky v) S V2.
vey
For the kernels we use for experiments in paper (e.g., Gaussian kernels), v1 = =リ=
Remark D.5. Based assumption (i), let x [-M Mi], Vz E X. In practice this condition is easily satisfied since usually normalize the input data into [0, 1] or with mean 0 and standard deviation 1. For assumption (ii), we set the Lipschitz parameter as M2, i.e., for all x, x' E X' and x, x' E [-1,, MI). [3(x) ((x') < M2|æ x'). Furthermore, with these assumptions, the value of B(x) is also bounded. We denote the bound as R, i... B(x) E [0, R). Vz E M-,, Mi). Therefore v3 E B, [[x S R, Vz E X. Note that the assumptions (i) and (ii) do not restrict the specific form of the kernels, and common kernels (Gaussian, Laplacian, etc.) and the kernels used in our paper satisfy these properties.
Lemma D.6 (MeDiarmid's s Inequality). Consider n independent random variables XI...., Xns and a real-valued function Xx,...,X,p)) that satisfies the following inequality
sup If (211...,, 3 P2
rn)l sa
for all 1 i S Then for all 0:
-2c
P[S ( 1/ x,) +0 exp
1 c
Similarly:
-2c
PIf (X......... ...X,.,,,,))..... 5 Xn) - S exp
Σn
ca
Lemma D.7 (Covering Number Lipschitz Function Class). Let be the set of functions defined on the interval MM,, Mi] with the following properties:
F ( 1- M1 - R), [f()) - f(y) S Malx vl. Vx, E [- MM, Mi).
23

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
where M1, R, M2 O. Then, the e-covering number N(F, e, ll (lso) of F under the alee norm satisfies:
N(F, 1.111116)) s (4R/c)8M)ME))
for any E (0, min 2M)
Proof. Partition in the domain: Divide the domain
[-M1, _M] into uniform grid of points:
X = {I1, T2 ...,,
(2.,,, IND,
24 M, (i 1)o,
ô =
M2
The number of grid points is:
N 2M = M2/e] s M2/e,
since M2/ 2 1.
Discretization of Function Values: At each sampling point 2; E X, the function value ((z) is restricted to [0, RJ. To ensure precision of e, discretize (0, R into steps of size
y' = 2,, R}.
The number of discrete values is:
[R/e] S 2R/e,
since R/E 2 1.
Function Set Construction: Using the discretized values at the grid points, the set of possible functions is:
Fower =
The total number of such functions is:
|oover| (2R/E)aM, M2/c
Covering Property: By Lipschitz continuity, any function f E F can be approximated by function F with a maximum error of in the || 11 norm. Thus all the close balls whose centers are in Foover can cover F. Notice that those centers may lie outside F. Consider close balls (B) where g Foover but y & F. Choose a h Blg, +) N Thus close balls (h,,, 2 cover J. Furthermore, the || |l coverrng number for F satisfies:
F if any.
N(F e, 11x)) S (4R/c) MM,Ma//.
Without loss of generality, for the case of notation, we define M = M2 in our proof.
Theorem D.8. Let na denote HSIC (x, Y) on the importance reweighted distribution Pxy. f)3 (a)) denote the corresponding
(unbiased) estimator of na. (0 (B) == (w) ÿ7 represents a random error function. n and A (3) are their biased
counterparts. Under assumptions (i) to (iii), then we have that with probability at least
2
2 log +
16M log
4 (1 (1+3R 11+3R+RR)RR4
sup A (B) (1 3R 22
(36)
8
3R
3
n3
Proof. We use McDiarmid's inequality in Lemma D.6 obtain the bound.
First, for fixed B = B(x), we show that (3) fits the bounded differences property. Since we fix the weights in this part, for simplicity we omit the subscript from the statistics, e.g., shorten vi(") to fj Then we replace (#1, v1) with (æf vf) and
keep the remaining samples the same. The newly obtained samples are named as D', and its corresponding weights are 3' [(x') (}(x)) ) Tw. Define Biy B,B,, Biju 3,33B Biggr B The difference between
7: = 1
Σ (JJE
Σ
B x p.
Σ
n2)
(n)4
(n)s
(37)
(KJ.))E1
24

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
and the new substitution o/ == -HSIC (D') can be given by (also define Bi - =B Pijg - =B,B3,0. and plygr - 31838083)
() 5/| - (n)2 (4.))E (E()J)
B By B/
Bigg k - B Ri
1 Ky ++
2
Σ
(n)a
(n)3
(Ki---))) (E(IJia)))
(1.1.))
(E(():))
(n 11-1)1 1)1 R²v² +
(n- (n- Rt 2 +3 2(n ann-1p 1)2 RB02 2(1 3R 21(² R
-B 1 S 2-
(n)2
(n)s
(n)s
n
Since for all j,j. the term kg Ky k2 are all in the range [0, v] by assumption D.5.i and PG E [0, R) by assump- tion D. Also note that all the terms that none of j, q, are one is zero. Now using McDiarmid's inequality, we finish
the first part of the proof, that is, for fixed B. with probability at least 1 1- 5,
2 ( & (1+ 3R + RR V
log 8'
(38)
Next, we consider the case where 3 changes. Take the function space B as an example. Firstly since the function space is compact, the covering number (B, r). defined as the smallest number of closed balls with centers in B and radii whose union covers B, is finite. According to Lemma D.7, for many smooth kernels, c.g., Gaussian kernel, we have
NBB, r, ll (1x)) s (4R/r)8M// = (B, || 1100) S r
SM log
R r
(39)
Also, combining with the assumption D.5.ii, we have for any two 3, 3 E B,
|/8 - 1/3 (() S (n)2 (3,DEi5
Σ
(B.g - Bos) 1 kg |
1 (m)a
E
(Bijor - -Bgorr R
(K.-...))
+ 2
Σ
(Bisa -
x K و 2(1 + 3R + 2R²) ) |8(0)) -B(0)
(n)3
(4.i-4)Eiz
We derive the last inequality term by term. For the first term, since [18(z)]1> S R and | - | = v², we have
Σ (B.- - B.y) x k (m)2
Σ
(9. - B.) B, + B, (B, - B,) | 2R ||0) |
(n)2 (6.))E
(IJ))
Similarly, for the second and third term we have
Σ (Buyor - Biser) kg = (n)2 (1.))
Σ (B.- - Bzgr + +B, (B, - -3,) Brr
(n)4
(
+ Bag (3g - Br) 3r + Rig (B, - 3.) || - 4123,3 ||8(a) - -B(x) |.
2
Σ (Bess - Besa) kg/
2 Σ
(a. - B.) Bjg + Br (B, -,,) B
(n)3
(n)a
(i.-))eig
(1.j.4)Eiz
+Bi (Bg- - Bx) 1 < 6R [(x)) B(x) |.
and using the property of unbiased estimate, then
m - nø
Enjg" (a)
Enj.
B 10
1/3
S 2(1 + 3R + )R²) [(x) |
- B(a)
(40)
As result, for any function 3 E B, we can find a function 3 in the cover set such that
[| - (w))l Sr, r,
(41)
25

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
and define (1 +1+33 3R + 2(-) R A A which gives
A ( (3) =
| th) (35) + 3R 2 / +4
(42)
Combining with the result in the first part, we show that with probability at least - 6,
sup
(B) s max A (0)) (1*)(B))) +4Au2
g
(43)
2B r,
1100) 4Au2r.
< 2² log
We finish the proof of this part by combining inequality (39) and setting the radis Rn Rn-
Therefore, omit the constants and we have the following uniform bound:
Theorem 3.7 (Uniform Bound). Suppose X is a closed and bounded space and the values of the kernels x and ky are also bounded. Assume the reweighting functions are continuous and Lipschitz. Then with probability at least
HSIC (D) HSII ~0 (
log
1
sup
6 +
(44)
BEB
n3
713
D.6. Relation with (Xu & Zheng, 2024).
(Xu & Zheng, 2024) focuses on representation learning and proposes feature learning framework maximizing dependence with the target by using extension of Rényi maximal correlation (RMC) in L space, with functions parameterized via neural networks. While the goals are different our paper focuses on hypothesis testing, both works leverage dependence- maximization criteria to learn meaningful functions. Theoretically, RMC provides general measure of nonlinear dependence via optimal function pairs in L Modal decomposition captures the full spectrum of the cross-covariance operator, with the leading mode corresponding to RMC. Restricting to RKHS and aggregating all squared singular values yields HSIC. While RMC more general, its estimation and statistical inference in L neural networks is challenging. In contrast, our methods inherit the kernel-based formulation of HSTC, allowing efficient estimation by kernel trick and asymptotic distribution analysis with statistical guarantees.
E. Details about the Conditional Independence Statistic
E.1. Characterization of Conditional Independence
We first define characteristic kernel:
Lemma E.1 (Characteristic Kernel (Fukumizu et al., 2007)). A kernel Kx is characteristic, if E Fx the condition Ex-ex [f()] = Ex~Qx [X)] implies Px = Qx. where Px and Qx are two probability distributions of X.
Characteristic kernels have several interesting and useful properties. Most common kernels we used are characteristic, like the Gaussian kernel and Laplacian kernel. As shown in Lemma 3010, we use characteristic kernel and define X' & (X, Z), the characterization CI could be related to the partial cross-covariance operator as Σ Σxvız - X Y Z, where
ExTız = Exy Ex Ezy
We then explain more about the partial cross-covariance operator. For (X,Y) X' V, the cross-covariance operator Σxy Fy + Fx is defined by (Fukumizu al., 2004)
Exxxyy) = - F
(45)
The partial cross-covariance operator is defined as
Σxyız = Exy Σxz>i
(46)
IIf Ezz is not invertible, use the right inverse instead the inverse. See (Fukumizu et al., 2007).
26

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
which can be understood by analogy to the partial cross-covariance between X and Y given Z when they are jointly Gaussian variables. Generally speaking, it can be seen a partial cross-covariance between functions: (f(X), E Fx) and (Y), Vg E F given (g(Z), Vg E Fz} (Li et al., 2024a). From this point of view, another characterization of CI would be more intuitive, which enforces the uncorrelatedness of functions in suitable spaces. We introduce it as follows.
Lemma E.2 (Characterization of CI based on Partial Association (Daudin, 1980)). Let the probability distribution of X be denoted by Px. and similarly for the joint probability distribution of X as Pxz or P Define the spaces of square integrable functions of X and X as L'x and x respectively, which satisfy L = {f(X) < oo} and - { |E[9²] 3=). Notations are similar for Y. Then the conditional independence relation benween X and Y given Z, i.e., X 1 LY is
B(fg) = 0, Vf S and Vg E Sÿ, B(ʃğ) = 0,
(47)
V and Vg E L2y
(48)
E (Jg') O,
Aʃ E SR and and Sy
(49)
= (JØ') O,
Yʃ E Sx and Vg' lly.
(50)
Where the subspaces of L2 are defined as follows:
Sx - 1 [[S[Z) - 0},
Sy - (ge 1 [[(gl)) =0},
S/ - (g' g = -(Y) - _ LŽ.
Note the subspaces Sy. and S/ can be constructed from the corresponding 1,2 spaces via nonlinear regression. For instance, Vʃ 2. its projection in subspace f E Exx is given by
f(x) = f(x) R(f(Z)
(51)
where (Z) E L2 the regression function of f(X) on Z.
We can clearly see the connection between the lemma E.2 and CI characterization for Gaussian variables using un- correlatedness between variables. Particularly,
regard Eq. (47) as the uncorrelatedness between any residual function of X given Z and Y given Z. If we consider spaces Fx and Fy instead of L and Lţ2 lemma E.2 is then reduced to lemma 10. (Zhang et al., 2012) provided a way to derive the KCIT statistic according to Lemma E.2, i.e. joI = |CCov (vix - [ [Z), Øx - TE |
E.2. Derivation of the Importance Reweighted Statistics for CI Test
By the meaning of importance reweighting, with a fixed function 3(-), at the population level, we can define the statistic of the reweighted KCIT (RKCIT) as:
g
A
D XYIZ
Es (w X1Z
Ep x|zl) @ (0 Ess HS
HS
where xiz
A Vx
Ep & [Z]
091 4 Φr - EslØr| Z] are the residuals of feature maps regressing on Z. Here
PP- 3(X, (XX, Y, 2). Suppose that x A (sI,..., It.... In) are the i.i.d. samples for X, and y, are the i.i.d. samples for Y Z. Denote the centralized kernel matrices for X. Y. 7 as Kg. Ky and Kz, respectively. Given importance weights 33 and the feature map (-), the unbiased estimator 3.fl (1:) of the centralization (x)) = v/ (x) - E Ex))(x)) now becomes Ji ( = (xx) - - (z,, = (I, - DD,11"") Therefore we have the reweighted centralized kernel matrix
K = (d (7))) = (In 111
- K and K are defined similarly.
n
We use kernel ridge regression to estimate conditional expectations. The estimator of the covariance operator is
1 "
(Ba (((x)) D3 T
(52)
-XY
k=
27

---

Extracting Rare Dependence Patterns via Adaptive Sample Rewcighting
where D3 A diag($1, 82...., Bx). The estimators of other covariance operators, i.e., E 2xz Zyz and Zz are sim- ilar. Now we calculate the estimators of the residuals and get the residual matrix R under reweighted distributions.
Notice that Egg & 1 [2] = (=)²² 2 S
X dim((p))]
E zx using kernel ridge regression. We used the identity
PBT (BPB* + R) = = + B² R. BB B² R-- in the derivation.
0 812
BTT = (x) - -Bey W / = (x)) =x(()² [22 + (laim(pps)
I 22x
$3
(53)
(0)) + n
+ Xaiim(pz))
(54)
"(())) 20(=) ( + camieez)
(55)
= -((()) +(()) ! (2) (((())= In + +D ((()))
(56)
- -X)" " (2()) # |_ (()
(57)
= =eD K + +eD
(²))
(58)
= c Dg -In
(59)
Therefore the residual matrix R² =
K + cI
The estimated residuals become R² (B)) and R (1)).
Since the covariance operator of the residuals is Cov(ub x = EE
b 3
of then the statistic of RKCIT is
X
X12
J
1
D
8 T Pgy Y
Tr
28 1
TBT D
Y12
01
D
n
H1S
n²
Tr
R
(3)
(T)
R
D3 Ro (. R D3
n2
1
Tr
R
R
D3
R K R T D3
n²
1 Tr
n²
x 2
y Y
where
K 8 x
=
R
K
R D3, K B Y/2
T
K
T D3. K R2
Therefore, for the CI test, the final objective function is similar to the optimization problem (9) with ju replaced by J8 As in the unconditional case, in the experiment we use normalized version of this conditional dependence measure with the denominators jel Tr ( x and 53 Tr K
a r12b which can be obtained in similar manner:
2
D
D T
-T
K
1
X
n
HS
n
JCl
78 n Y1
D
3 212
Tr
K Y12
11
n
E.3. Discussion about the Asymptotic distribution of Reweighted KCI
(Zhang al., 2012) gave the asymptotic distribution of jer under Ho. which follows the distribution of weighted sum of chi-square variables that is slightly more complex than that of HSIC. However, the author did not provide the distribution under H4. For the purpose of conditional independence testing, we compute the distribution under Ho of j using the permutation test. We argue that the ground ground-truth asymptotic distribution has a similar form to the original jer since we analyze the asymptotic characteristics of a reweighted distribution.
28

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
E.4. Discussion of Uniform bound for Reweighted CI test
Actually, after giving the convergence rate of the estimated kernel ridge regression, the derivation of the uniform bound for Jg is similar to that of HSIC, with the minor difference that J is calculated for residual variables. We leave this the future extension of this work.
F. Details about Causal Discovery
F.. Proof of Rare Dependence PC.
In this section, to ensure the asymptotic correctness of the PC algorithm, all theoretical results are based on the assumptions of causal Markov, faithfulness, and causal sufficieney. These explicit definitions can refer standard literature (Spirtes al., 2000). If there is no further statement, we assume that these assumptions hold.
Assumption 4.1. VX,Y V CVV (X,Y), if KCIT(X, Y|Z) rejects the null hypothesis, then X 14 Y Besides, if both KCIT(X, Z) and RKCITT(C) (X, Y|z) fails reject the null hypothesis, then X TT Y Z.
Rule X,Y V, 3Z S (XXY)) s.t. both KCIT(X, Y|Z) and RKCIT (X, Y|Z) fail to reject the null hypothesis, then X and Y are not adjacent in G.
Proof. We prove this by contradiction. Suppose X and Y are adjacent in G. Without loss of generality, let X + Y in G. There are two cases we need to consider: (i) there does not exist rare dependence in P(X, Y), and (ii) there exists rare dependence in Y).
Case I: If there does not exist rare dependence in P(X, Y) and X + Y, then AZ C VM Y) such that TT Y Z holds, according the faithfulness assumption. This violates the condition that 32 S (XX s.t. KCIT(X, Y| accept the null hypothesis. Furthermore, by Proposition C.2, RKCIT((C) (X, Y Z) also fails to reject the null hypothesis. Thus, X and Y are not adjacent in G.
Case II: According to Assumption 4.1, if both KCIT(X, Y|Z)) and RKCIT* 2)) fail to reject the null hy- pothesis, then X IL ZIz. This violates the condition that X > Y in G (If there exists rare dependence in TPX, Y), (XC YIZ) reject the null hypothesis under the large sample).
In summary, X and Y are not adjacent in G.
Proposition 4.2. For pair of variables X,Y E V, if VZ C VMX,Y) s.t. KCIT(X, YIZ) fails reject the null hypothesis, and (b) for all these Z, we have that (C) (X, Z)) rejects the null hypothesis. Then, under Assumption 4.1, X and Y are adjacent with a rare dependence, or ii) X and are not adjacent in G and must be the direct common effect of X and Y.
Proof. I C CVXXXYY, KCIT(X, Y ()) fails to reject the null hypothesis, and if there is no rare dependence between P(X,Y) then X and Y are not adjacent in G according to the faithfulness assumption. Furthermore, we consider C' as a conditional set, i.c., C' C Z, and KCIT(X, Y Z) rejects the null hypothesis, then must be the common effect X and Y, as the V-structure is activated. Additionally, if RKCIT (X,Y Σ) rejects the null hypothesis for all Z, this implies that there exists rare dependence in P(X, Y). and thus X and Y must be adjacent in G (otherwise, 3Z such that (CC (X,) Y Z) fails to reject the null hypothesis by Proposition C.2).
Remark F.1. Proposition 4.2 tells that if X + - Y forms V-structure, Rule can not correctly remove the edge between X and Y when executing the PC algorithm recover the causal skeleton. Consequently, the inferred graph tends to be superset of the true one.
C
To further distinguish the rare dependence pattern or when X and are not adjacent in G in Proposition 4.2, we present the following Rule 2.
29

---

Extracting Rare Dependence Patterns via Adaptive Sample Rewcighting
Rule 2. For two variables X, x,Y E V that satisfy the condition in Proposition 4.2, if there exists Z S V VVXX, YJ, such that R (X,Y (| fail to reject the null hypothesis, then X and Y are not adjacent in G. Here Cperm denotes the shuffted C in dataset D.
Proof. If two variables X, Y E V satisfy the condition in Proposition 4.2, it means that either i) they are adjacent with rare dependence, or ii) they are the direct causes of C' (i.e. C' is the direct common effect of X and Y).
In case i). suppose Crerm is the randomly shuffled version of C, and Cx(i) is the i-th sample of Cperm, Firstly, suppose C' is continuous, then C. + Cj. i f a.s. Let/ be the original reweighting function and / be the reweighting function learned for Cperm, If ((c+()) = B(c),, vi, then RKCITT (C (Z) can still enlarge the dependence measure and reject the null hypothesis, which is the same as RKCITT(C) (x, (X,Y) Y|z). Since 3 is a simple composition of 3 and the permutation n, 3 B and thus learnable. When C' is discrete, we can add some small noise, e.g. Gaussian noise, to C' for each sample and treat it as a continuous variable.
In case ii), we note that Cperm, the randomly shuffled version of C, satisfies Cperm II X,Y, Z because the data points in the dataset D are i..dd, which means (zi, M/, 2i, c.) IL Cz(i); Vi & (i). Due to the randomness, as + Do, (i) = i) - 0. This climinates the spurious dependence between X and Y caused by selection bias. Therefore, RKCIT (X,
fails to reject the null hypothesis, since X and Y are indeed independent when conditioned on Z in this case.
Based on Rule and 2, we summarize the procedure of RD-PC in Algorithm 2. Theorem 4.3 proves its soundness. Theorem 4.3. With Assumption 4.1, suppose the causal Markov condition, faithfulness assumption, and causal sufficiency assumption hold. Then, Algorithm 2 correctly recovers the underlying causal graph structure up its Markov equivalence class.
Proof. Under Assumption 4, the conditional independence relations can be correctly identified using Rule 1 (Line 5 in Algorithm 2). In Line 6, Rule 1 is applied to remove the edges between X and for X, Y E V. As shown in the proof of Proposition 4.2, there are two cases that need be distinguished, since the equivalence class between the rare dependence pattern and C' may correspond to a collider structure. In Line 7, Rule is used to differentiate these structures and ensure that extraneous edges are removed. By the causal Markov assumption, faithfulness assumption, and causal sufficiency assumption, the causal skeleton can be correctly identified (Spirtes et al., 2000). Moreover, in Line 8, Meek's rule is used to orient the directions, the correctness of which is guaranteed by (Meek, 1995). In summary, in line with the PC algorithm (Spirtes et al., 2000), the causal structure can be identified up to a Markov equivalence class.
F.2. Relation with ReScore (Zhang et al., 2023).
ReScore (Zhang et al., 2023) aims to optimize the structure recovery of score-based causal discovery methods with fewer spurious edges and more robustness to heterogeneous data. They propose an effective model-agnostic framework of reweighting samples to boost differentiable score-based causal discovery methods. The core idea of ReScore is to identify and upweight less-fitted samples, as these samples provide additional insight into uncovering the true causal edges- to those easily fitted through spurious associations. Although RD-PC, which employs method for causal discovery, its objective is
proposed
RHSIC and RKCIT with correction rules, is also a sample reweighting- fundamentally different from that of ReScore. ReScore is designed to mitigate the influence of spurious edges by focusing on less-fitted samples, whereas RD-PC aims to recover true causal edges that are easily overlooked or erroneously removed due to rare dependence. Exploring the connection between rare dependence and less-fitted samples may offer an interesting direction for future research.
G. Supplementary Experimental Details and Results
Implementation Details. Here we provide the implementation details of the methods. In all experiments, we use Gaussian kernels in all kernel-based methods. The significance level is set to 0.05. The results are obtained after averaging the values in the 100 tests.
In our method, we use the constrained optimization library provided by scipy to minimize our objective function, and set the
30

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
maximum number of iterations 50. We set the number of permutations to 2000 approximate the null distribution. The hyperparameters in objective functions (9) are set to A X2 =le-3 for RHSIC and Å =le-6, 22 =le-1 for RKCIT. And the e for kernel ridge regression is set to le-3, For the conditional independence test, we use calibration for our RKCIT when we change the dimension of Z (the empirical threshold is set to 0.0375). We observe that some baseline methods naturally maintain a Type error rate close to 0.05. Other baseline methods have higher Type errors and lower power, which means that, however calibrated, their performance is worse than ours. Therefore, for these baseline methods, we report their original results.
G.1. Synthetic Data
More details about the synthetic datasets are explained in this section, including the implementation details, more experiments under different settings and more baseline models, and the results analysis of Fl and SHD for causal discovery.
G.I.I. SYNTHETIC EXPERIMENTS FOR UI
Data Generation I: we slightly modify Example 1.1 with different variance 0² for (00 o²) to evaluate the power. To test the Type error, we set Y = with fixed = 0.5.
Data Generation II: we use a variant of the synthetic experiment in (Strobl et al., 2019). To evaluate the Type I error, we generate the data that follows X = fE = f2(Ey), where Ex, Ey are drawn independently from NV 1) and fi and f2 are smooth functions chosen uniformly from a set {a3, cos(z), 1 + sin (3x)², 20 sin (Ax²"), Gsign(z)}, where Gsign(z) = |e| sgn( X.). where is the dimension of variable X and (O, 1). To compare the power, we generate X fi (ea) + Eh. and then we generate Y [2(5y) + Eb if X where is a threshold, and Y (2 otherwise.
Data Generation III: The data generation III is similar to the procedure of DG II except that we use third variable Q ~ (0, 1) to compare with the threshold r and decide the generation process accordingly.
Results: See Fig. 6 for the experiment results for Data Generation III. Other experiment results are in the main paper.
Type Error
DG III Gaussian
DG III Laplacian
Type errrr rate (
0.15
1.00
BGB
Test power (f)
0.75
0.75
0.10
Test power
0.50
0.05
0.25
0.25
0.00
Gaussian
Laplacian
0.10
0.15
0.20
0.10
0.15
0.20
t
HSIC
-A-
HSIC-RFF
LFHSIC -X-
RDC
FisherScan
Ours
Figure 6. Type I error rate and Power of Data Generation III with Gaussian and Laplacian noise.
Baselines for UT. All the baselines follow their default settings unless stated otherwise. HSIC (Gretton et al., 2007): the original HSIC test using gamma approximation for p-value. Code from python library causal-learn (Zheng et al., 2024); LFHSIC (Ren et al.. 2024): HSIC test with adaptively learned bandwidth. Code from https//ggiuubb.oo//eniiiinneeee LK; RDC (Lopez-Paz et al., 2013): use canonical correlation between a finite set of random Fourier features. We permute the samples 500 times to compute the empirical p-value. Code from http://github.comggrrrorrro (Zhang al., 2018): HSIC using finite-dimensional random Fourier feature mappings approximate kernels. Code from
FHSIC
1.2. SYNTHETIC EXPERIMENTS FOR CI
Data Generation I (DG I): We follow the synthetic experiment proposed in (Scetbon et al., 2022) with a slight variation.
To compare the Type I error, we generate simulated data by:
f -222222 (22 +
(60)
31

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Above, Z is the average of Z (Z,, Za.). 8x and By are sampled independently from (0, 1), and f1 and /2 are smooth functions chosen from the same set in DG II. The following generating function is for evaluating power:
x f1 +e) te, Y f2(Z Ev) + Eb. if < T
X = fi(Z +Ex Y= fz(Z + +ty),
if 2 T.
where Q~ ~ (), 6b ~ (00 1), r E [0.1] is threshold.
Data Generation (DG I): The data generation similar to the procedure of DG I except that we use the 7 percentile of the count of X as the threshold.
Baselines for CL We compare with the following CI methods. KCIT (Zhang al., 2012): the original KCI test based on the partial association framework. Code from python library causal-learn (Zheng et al., 2024); CCIT (Sen et al., 2017); a blassifier-based test leveraging nearest neighbor sampling to approximate conditional distribution; RCTT (Strobl et al., 2019): KCI using random Fourier features to approximate the kernel function. Code from python library causal-learn (Zheng et al., 2024); GCIT (Bellot & van der Schaar, 2019): a test employing generative adversarial network to approximate null distribution; GCM (Shah Peters, 2020): test based on the generalized covariance measure; NNLSCIT (I.i et al., 2024b); a baase conditional mutual information estimator.
Results. See the Fig. 7, Fig. 8 and Fig. 9, compare our methods with the CI testing.
n=1000, 0.1
n=1000 T- 0.1
0.35
Test power (t)
eree rate
0.25
0.6
0.20
0.4
0.15
0.10
0.00
10
Dimension of
Dimension of Z
-
KIT
-
RGT
4
UPCI
-X
NNLSCIT
Durs
Figure 7. Type error rates and Test powers for CI tests with Data Generation I while Changing the dimension of Z. Here the number of samples fixed 1000 and the level of rare dependence is r 0.1.
n=1000, r= 0.1
n=1000,
Type error rate (1)
0.6
Test power
0.2
0.0
2.5
7.5
10.0
5.0
7.5
10.0
Dimension of Z
Dimension of Z
KCIT
-A-
RKCIT
-V-
GCM
-X-
GCIT
-B- Ours
Figure 8. Type error rates and Test powers with Data Generation I for more CI baselines. Again here change the Z dimensions.
G.2. Causal Discovery
Data Generation: We first randomly generate DAGs with 6 nodes and 10 directed edges from the graphical model Erdös- Rényi (ER) (Erdos & Renyi, 1959). We generate 30 graphs, and for each DAG, we randomly select one node from the graph as the reference variable C. We construct the rare dependence between C and its children by adding dependence only when C' is in its lower 3% percentile. The synthetic data is generated according to the following nonlinear structural equation:
X, fa (pa (X.) + +x),2 = 1,...,
where the causal mechanism f. is randomly selected from functions such as linear, sin, cos, tanh, sigmoid, and their combinations and (X;) the parents set of variable X,. The noise term 6; is sampled from Gaussian distribution.
32

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Type Error
zdim=1
zdim=10
0.30
Test power (t)
DaGE
0.20
0.6
power
0.6
0.15
0.10
0.4
0.4
0.05
0.3
0.3
2dim=1
zdim=10 10
0.100
0.125
0.150
0.175 0.200
0.
0.100
0.125
0.150
a.175
0.200
KCIT
ACIT
LPCI
*
GCM
Ours
Figure 9. Type I error rates and Powers of Data Generation I (DG I) with different sizes of the conditional variable..
Fl Score (t)
SHD (L)
0.6
0.5
400
600
400
600
number of samples
number of samples
Figure SHD and F1 Score of the causal discover experiment. We follow the data generation and change the number of samples E [300, 400, 500, 600, 700].
Result. We use PC algorithm with KCIT our baseline. The result can be found in Fig. 10. Our RD-PC consistently performs well here.
G.3. Real-world Data
The the flow-cytometry data published by (Sachs et al., 2005) is popular real-world data for causal discovery methods, which gives expression levels of 11 proteins under various experimental conditions. We take the popular learned causal structures as the ground-truth causal graph for this dataset, as shown in Fig. 11.
PIPS
PLOE
PIP
PIPS
PIPS
SAVI
Mak
Ert
Eift
A11
ABA
PEAA
PIA
PSA
PRO
FBC
PSC
Figure 11. Figure 5 in (Mooij & Heskes, 2013). Left: Consensus network, according (Sachs al., 2005): Middle: Reconstruction of the signaling network by (Sachs et al., 2005), in comparison with the consensus network; Right: The best acyclic reconstruction found by (Mooij & Heskes, 2013). Black edges: expected. Blue edges: unexpected, novel findings. Red dashed edges: missing.
H. Discussions
H.1. Why not Use Mutual Information?
In principle, we can also detect rare dependence by maximizing the mutual information between X and Y on the reweighted sample. However, maximizing the mutual information with the importance reweighted data involves estimation of the data densities, which is difficult problem. Instead, we maximize a specific kernel-based dependence measure on the data w.r.t.
33

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
the importance reweighting ratio B(C).
H.2. Kernel Choice
The performance of RHSIC/RKCIT depends on the choice of the kernel. Our theoretical claims require characteristic kernel. our experiments (including Examples 1.1 and 3.1), use the Gaussian kernel with median heuristic bandwidth.
We conducted additional experiments comparing kernels and found Gaussian consistently performs best. The poor performance of the polynomial kernel is expected, as it is not characteristic. Laplace is characteristie but has heavier tails than Gaussian; its performance drop suggests lighter-tailed kernels may be preferable.
Type Error
RHSIC
HSIC
Type I e rate (
0.15
Test power (t)
0.8
0.10
Test power
0.6
0.05
0.6
0.4
G
0.2
0.00
0.4
RHSIC
HSIC
0.10
0.15
0.20
0.10
0.15
0.20
Gaussian Kernel
Laplace Kernel
-
Polynomial Kemel
Figure 12. Type I error and test power comparisons of RHSIC and HSIC with different choices of kernels. Used the DG III in Appendix with r 0.1.
H.3. Selection of Reference Variable C
When do UI/CI tests where only X and Y are observed, consider C X or C = Y. Once more information is available, e.g. more observed variables in causal discovery, C can be third variable to leverage such information.
Take the DG III T 0.1 as an example, in the causal graph X e - + + Q, we observe X,Y, Q and want to test X Y. Proposition C.2 shows that C'= - xx Y, or Q are all valid here (i.e., do not introduce spurious dependence). RHSIC with = Q performs the best since Q directly controls the dependence between X and Y. while C Y, a child of Q, brings some power loss though still acceptable. RHSIC with C X is ineffective since 1 Q.
Method
Type Error
Test Power 1
RHSIC(C =
0.05
0.8
RHSIC(C = Y)
0.1
0.57
RHSTC(C- = X)
0.01
0.06
HSIC
0.04
0.17
Table Comparison of Type error and Power different choices of the reference variable C' for RHSIC.
In practice, only X,Y Y are available, we recommend testing with both C X and C' = Y and selecting the lower p-value.
H.4. Train-Test Splitting Ratio
Different train-test splitting may lead to different performance. However, RHSIC significantly outperforms baselines when rare dependence exists, suggesting the splitting loss is limited and outweighed by the gain in detecting rare dependencies. To examine the effect of splitting on performance, we list different split ratios on DG III T = 0.1. 0.5 ratio generally performs well, consistent with prior work (Jitkrittum et al., 2016; 2017).
34

---

Extracting Rare Dependence Patterns via Adaptive Sample Reweighting
Table 3. On performance under different ratios of test- best-train splitting
DG III (T 0.1)
I = 0.4)
Train
Test
Type Error
Test Power t
Type Error
Test Power 1
90%: : 10%
0.05
0.41
0.05
0.28
80% 20%
0.07
0.61
0.08
0.47
70% 30%
0.07
0.68
0.04
0.59
60%: : 40%
0.05
0.76
0.05
0.63
50% 50%
0.05
0.80
0.05
0.69
40% 60%
0.04
0.78
0.05
0..9
30%: 70%
0.01
0.74
0.06
0.71
20% 80%
0.01
0.70
0.03
0.57
10%: 90%
0.04
0.68
0.05
0.47
35


Reviews:
[{"review_id": "4uTngUqXSb", "reviewer": "Reviewer_YWTp", "summary": "This paper proposes the use of adaptive sample weighting to detect rate dependencies in data. The key idea is to incorporate weights for data points by formulating an objective problem that maximizes the reweighted HSIC along with regularization terms. Asymptotic hypothesis test guarantees for the resulting reweighted HSIC test are provided through direct applications of the classical theory of V-estimators and U-estimators.\n\nThe estimation of sample weights is analyzed as a statistical learning problem (empirical risk minimization) using simple arguments from empirical process theory, leading to non-asymptotic uniform convergence guarantees.\n\nFinally, this idea is extended to conditional HSIC, and, building on this, a new version of the PC algorithm is designed that utilizes the reweighted conditional HSIC to infer conditional independence. In the experiments, the strong performance of the new PC algorithm is demonstrated on both synthetic data and a real-world dataset from flow cytometry (Sachs et al., 2005).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate the reviewer's constructive comments and helpful feedback. Please see below for our response. All figures and tables are available at https://tinyurl.com/mwafx6kh.\n\n- **(Weakness & Reference)** \nThank you for your comments and for pointing out the work by Zhang et al. (2023), which we will cite in our revised version. **Our work and Zhang et al. (2023) originate from different motivations and aim to address distinct problems.** Our research is motivated by the specific challenge of detecting rare dependence, a topic that remains unexplored to the best of our knowledge. Rare dependence is widespread across many real-world domains and confirmed by lots of literature, such as psychology[1], medicine[2], physics[3], sociology[4], etc. Our focus is on **detecting rare dependencies** that are otherwise missed by existing independent tests. The proposed RHSIC and RKCIT are statistical tools for independence and conditional independence testing designed to recover rare dependencies. We emphasize that discovering causal relations in the presence of rare dependence is one important application of our methods, not the ultimate goal. Our method is not restricted to causal discovery. \n\n  On the other hand, ReScore (Zhang et al., 2023) aims to optimize the structure recovery of score-based causal discovery methods with fewer spurious edges and more robustness to heterogeneous data. They propose an effective model-agnostic framework of reweighting samples to boost differentiable score-based causal discovery methods. The core idea of ReScore is to identify and upweight less-fitted samples, as these samples provide additional insight into uncovering the true causal edges—compared to those easily fitted through spurious associations. Although RD-PC, which employs our proposed RHSIC and RKCIT with correction rules, is also a sample reweighting-based method for causal discovery, its objective is fundamentally different from that of ReScore. ReScore is designed to mitigate the influence of spurious edges by focusing on less-fitted samples, whereas RD-PC aims to recover true causal edges that are easily overlooked or erroneously removed due to rare dependence. Exploring the connection between rare dependence and less-fitted samples may offer an interesting direction for future research.\n\n  We appreciate the opportunity to clarify this and will update the manuscript accordingly.\n\n- **(Theoretical claims)**  \nThank you for your insightful comments. We agree that the uniform bound in Theorem 3.7 applies to the empirical risk without regularization terms, rather than to the optimization problem (9). We acknowledge that this discrepancy exists and appreciate the opportunity to address it. We should have discussed this in detail in the paper. A gap remains between the theoretical aspect and the current algorithmic implementation. We have included a discussion in our updated manuscript. In practice, however, when analyzing data, we have to introduce a trade-off by employing the normalized RHSIC with two penalties in (9): the first term to control the smoothness of the $\\hat{\\beta}$ function, and the second to constrain the deviation of $\\hat{\\beta}$ from one to select as many samples as possible. These two penalties allow us to balance theoretical rigor with practical performance in practice.\n\n  We appreciate the reviewer for raising this issue. To address this concern more thoroughly, we will revise the manuscript by adding an ablation study in the Experiment Section to quantify the regularization’s effect and discuss this theoretical-practical tradeoff explicitly. \n\nWe are encouraged that the reviewer recognizes our work as \"well-written\" and our theoretical analysis as \"in depth.\" We also appreciate the reviewer’s acknowledgment of our comprehensive synthetic and real-world experiments.\n\nBesides, we would like to add that our contribution goes beyond the classical results that the reviewer mentioned; we identify a new problem setting, rare dependence in statistical testing, and establish a general framework to solve this problem. In real-world scenarios, such rare dependencies often arise due to noise or imbalanced data distribution, making them difficult to detect using standard tests. To this end, we hope this work provides a foundation for various potential practical extensions, such as interpretable subgroup discovery, robust causal inference, and scientific analysis in domains like medicine, economics, and social science.\n\nWe sincerely appreciate your thoughtful feedback and recognition of our work. Thank you for your time and efforts.\n\n[1] A Systematic Review: The Influence of Social Media on Depression, Anxiety and Psychological Distress in Adolescents.\n\n[2] Opioid-induced Hyperalgesia: A Qualitative Systematic Review.\n\n[3] Frequency-Dependent Local Interactions and Low-Energy Effective Models from Electronic Structure Calculations.\n\n[4] Time Spent on Social Network Sites and Psychological Well-Being.", "claims_and_evidence": "Yes, the theoretical claims are indeed classical, and the proofs are provided. The experiments are also discussed in detail.", "methods_and_evaluation_criteria": "Yes, test power and Type I error are reported for the experiments, which is common in the causality literature.", "theoretical_claims": "Yes, I skimmed briefly, and they seem to be correct.\n\nHowever, one important note should be mentioned in the paper: the uniform bound in Theorem 3.7 is not designed for the optimization problem (9) but rather for the version of the empirical risk that does not include any regularization terms. With regularization, the term $B$ in line 1080 is not negative, and as a result, the entire conversion of the problem into uniform convergence bounds breaks down.", "experimental_designs_or_analyses": "Yes, they seem to be valid.", "relation_to_broader_scientific_literature": "The authors design a new independence test, leading to a new class of constraint-based causal discovery algorithms, which may have broader impacts in applications such as biology or the human sciences.", "essential_references_not_discussed": "Yes, indeed, the idea of adaptive sample reweighting for causality is not novel and has been proposed before (and is not cited in this manuscript), particularly in:\n\nZhang, A., Liu, F., Ma, W., Cai, Z., Wang, X., & Chua, T. S. Boosting Causal Discovery via Adaptive Sample Reweighting. In The Eleventh International Conference on Learning Representations.\n\nIn that work, adaptive sample reweighting was formulated as an optimization problem in combination with score-based causal learning algorithms. In contrast, this paper considers a constraint-based approach (PC). However, in general, this prior work significantly undermines the novelty of this submission.", "other_strengths_and_weaknesses": "Strengths:\n- Paper is well-written and all aspects of theory are analyzed (despite following classical results and not necessarily very novel) in depth, especially on asymptotics of hypothesis testing, causal discovery of the resulting PC algorithm up to markov blanket and uniform convergence results for estimation of the sample weights.\n- A comprehensive set of synthetic and real-world experiments are provided.\n\nWeakness:\n- The idea is not novel and similar idea have been proposed before (Zhang, An, et al. 2023). \n\nBecause the paper is complete (in terms of theory and experiments), I am leaning toward acceptance.", "other_comments_or_suggestions": "Besides the missing reference, I don't have any other suggestions.", "questions_for_authors": "The paper is well-written, and I don’t have any questions.", "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": "", "extra_scores": {}}, {"review_id": "PBvad1JlZM", "reviewer": "Reviewer_MSVk", "summary": "Existing conditional independence testing methods suffer to detect dependencies that occur in a small regions of the data which is referred to as rare dependence. This work aims to resolve this issue by proposing  a kernel-based independence testing with an importance reweighting, which assigns higher weight to data point that involves such rare dependencies. Theoretical analysis and experimental results demonstrate the validity and effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the insightful and constructive feedback. Please see below for our response. All figures and tables are available at https://tinyurl.com/mwafx6kh.\n\n- **On Motivation** (Reference & W1)\n  We thank the reviewer for this valuable suggestion. We agree that the motivation can be strengthened, especially regarding real-world relevance. We reviewed the literature on local and context-specific independence [1–5], which supports the practical significance of rare dependence. For instance, [3] applies CSI to physical dynamics such as friction; [5] demonstrates local dependence in reinforcement learning, e.g., autonomous driving; [6] discusses CSI in biomedical inference, e.g., dose-response effects in antibiotic treatment. These works are insightful and we will cite and integrate these as examples.\n\n  Rare dependence is common across domains. In economics, income and consumption may appear weakly related in low-income groups but become strongly coupled at higher income levels. In psychology[7], the impact of social media on adolescent mental health becomes significant only with excessive usage. Similar rare dependencies occur in medicine[8], physics[9], and sociology[10], highlighting the practical relevance of detecting rare dependencies.\n\n  We will revise the motivation accordingly and include references [1–5] and these real-world examples to better contextualize the relevance of rare dependence in practice.\n\n- **On real-world datasets** (Experimental & W3)\n\n  We agree that additional real-world evaluation would further strengthen the work. In response, we have added an experiment **(see link above)** using monthly JPY/USD exchange rates (E) and U.S. federal funds rates (F) from 1990 to 2010, sourced from FRED. While the original HSIC fails to reject independence (p = 0.2174), RHSIC detects dependence (p = 0.0005) using F as the reference variable. The learned weights assign higher importance to the samples in 2001 and 2008. These correspond to the Dot-com recession and the global financial crisis, respectively — showing that our method not only detects rare dependence but also provides interpretable insights. \n\n- **On local (in-)dependencies** (W2 & Q1)\n\n  We thank the reviewer for this thoughtful question. We apologize for the misleading wording \"opposite\" and will revise it accordingly. We intended to highlight a difference in focus — which we now realize is not necessarily exclusive: prior works aim to model precise conditional independence structures, while our goal is to detect rare dependence overlooked by existing tests. \n\n  We agree that our methods can deal with context-specific or local (in-)dependence problems. For example, Example 3.1 and Data Generation II & III in our experiments involve local dependence, and our method performs well in these cases. Moreover, the learned sample weights can help identify independent regions — low-weight samples often correspond to locally independent areas. We will clarify this point in the revision.\n\n- (Q2) Indeed, one advantage of our method is that the learned importance weights provide a natural way to identify subgroups of data that contribute most to the rare dependence signal. As shown in our real-world dataset analysis and local-independence discussion above, these weights help uncover meaningful patterns and guide downstream interpretation, enhancing interpretability.\n\n  We agree that explicitly extracting high-weight subgroups could further extend the utility of our method. In particular, the learned weights can support fine-grained causal structure discovery by highlighting context-dependent relationships. Moreover, the structures recovered by our approach (e.g., the algorithm in Sec. 4) can provide valuable inputs for downstream tasks. Both aspects are relevant to applications discussed in [4,5,6], as suggested by the reviewer. We view this as a promising direction for future work.\n\n- (Q3) Yes. Since kernel matrices can be constructed for discrete variables using Kronecker kernels [11], our method — which operates on these matrices — directly applies to the discrete case. \n\nWe sincerely thank you for your constructive feedback, the time you have dedicated, and your recognition of our work. We especially appreciate the valuable suggestions regarding future directions, which we find highly inspiring and will consider in our subsequent research. Thank you.\n\n[7] A Systematic Review: The Influence of Social Media on Depression, Anxiety and Psychological Distress in Adolescents.\n\n[8] Opioid-induced Hyperalgesia: A Qualitative Systematic Review.\n\n[9] Frequency-Dependent Local Interactions and Low-Energy Effective Models from Electronic Structure Calculations.\n\n[10] Time Spent on Social Network Sites and Psychological Well-Being.", "claims_and_evidence": "The paper proposes a (conditional) independence tests for detecting rare dependencies and provides a theoretical guarantee regarding bound and asymptotic property. The effectiveness of the method is evaluated with two synthetic data generating process and one real-world dataset.", "methods_and_evaluation_criteria": "- The method and evaluation criteria are appropriate for the task.", "theoretical_claims": "- The paper provides an asymptotic analysis on the importance reweighting statistics of the test. Theoretical claims seem to be convincing, though I did not check the proof in detail.", "experimental_designs_or_analyses": "- Experimental setup looks reasonable. That being said, evaluation on only a single real-world dataset seems a bit narrow.", "relation_to_broader_scientific_literature": "The dependency pattern within the data is heterogenous and imbalanced in many practical scenarios (e.g., economics, biology, social science). I believe the paper has potential impact to broader scientific literature.", "essential_references_not_discussed": "I think the motivation should be better presented since in it’s current form, it might be unclear whether such rare dependencies are prevalent in real-world applications which is related to the significance of the problem. Accordingly, I suggest the authors to include the literature on local independences [1-5] to discuss and better motivate the relevance of “rare dependencies” in practical applications.", "other_strengths_and_weaknesses": "**[Strengths]**\n\n- The paper is well-written and easy to follow.\n- The paper tackles an important problem and theoretical analysis looks solid. Another strength is the application to causal discovery and corresponding evaluation.\n\n**[Weaknesses]**\n\n- The motivation is somewhat weak in the current manuscript, since some readers might question the importance and relevance of “rare dependencies” in real-world datasets and scenarios.\n- The authors mention that discovering local (in-)dependencies (e.g., context-specific independence [1, 2] or local independence [3]) are “opposite to our objective”. Can you elaborate on what this means? Intuitively, such local (in-)dependencies can be regarded as a special case of “rare dependence”, i.e., soft vs. hard, and I don’t see any reason why it is opposite to the scope of this work. It would be interesting to see how the proposed method performs in such settings.\n- The evaluation considers only a single real-world dataset and the proposed method is limited to continuous variables.", "other_comments_or_suggestions": "See above and below.", "questions_for_authors": "- Could the proposed method be evaluated on discovering local (in-)dependencies?\n- One desirable property is to find a particular region of the data where the “rare dependence” exhibits (e.g., [-2, 2] in Fig. 1 and [0,0.25] in Fig. 2) as it provides an interpretability and could be further leveraged, e.g., for efficient [4], robust inference [5], and causal effect identification [6]. I assume the proposed method could be further extended to capture such specific subgroup of the data, e.g., by collecting datapoints with large importance weights; I would like to hear the thoughts from the authors.\n- Could the proposed method be extended to discrete variables?\n\n***References***\n\n[1] Context-specific independence in Bayesian networks\n\n[2] The role of local partial independence in learning of Bayesian networks\n\n[3] On discovery of local independence over continuous variables via neural contextual decomposition\n\n[4] Exploiting contextual independence in probabilistic inference\n\n[5] Fine-grained causal dynamics learning with quantization for improving robustness in reinforcement learning\n\n[6] Identifying causal effects via context-specific independence relations", "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": "", "extra_scores": {}}, {"review_id": "JErO1sKjmN", "reviewer": "Reviewer_L7CG", "summary": "This paper considers the discovery of the dependence pattern in a specific small region, coined \"rare dependence\". The authors proposed a reweighting (importance sampling) -based approach and presented several statistical properties. They also demonstrated several applications, e.g., causal discovery, on synthetic and real-world datasets.\n\n## update after rebuttal\nI appreciate the author addressing some of my concerns, and I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We appreciate the reviewer's constructive comments and helpful feedback. Please see below for our response. All figures and tables are available at https://tinyurl.com/mwafx6kh.\n\n- **On kernel choice** (Comments & Q1)\n  Indeed, RHSIC/RKCIT performance depends on kernel choice. Our theoretical claims require a characteristic kernel. In practice (e.g., Examples 1.1 and 3.1), we use the Gaussian kernel with median heuristic width, as in standard HSIC.\n  \n    We conducted additional experiments comparing kernels and found that Gaussian consistently performs best. The poor performance of the polynomial kernel is expected, as it is not characteristic. Laplace is characteristic but has heavier tails than Gaussian; its performance drop suggests that lighter-tailed kernels may be preferable.\n  |Method (Kernel)|Type I ↓|Power ↑|\n  |-|-|-|\n  |RHSIC (Gaussian)|0.05|0.8|\n  |RHSIC (Laplace)|0.08|0.6|\n  |RHSIC (Polynomial)|0.04|0.42|\n\n- **On related work** (References)\n  We thank the reviewer for pointing out this related work. While our goals differ — ours focus on hypothesis testing, theirs on representation learning — both leverage dependence-maximization criteria to learn meaningful functions. We will cite and discuss [XZ2024] in the manuscript.\n\n  [XZ2024] proposes a feature learning framework maximizing dependence with the target using an extension of Rényi maximal correlation (RMC) in $L^2$ space, with functions parameterized via neural networks. In contrast, we focus on detecting rare dependence using HSIC/KCI, widely adopted in independence testing, and learn a reweighting function to assign sample-wise importance. Theoretically, RMC provides a general measure of nonlinear dependence via optimal function pairs in $L^2$. Modal decomposition captures the full spectrum of the cross-covariance operator, with the leading mode corresponding to RMC. Restricting to RKHS and aggregating all squared singular values yields HSIC. While RMC is more general, its estimation and statistical inference in $L^2$ with neural networks might be more challenging. In contrast, our methods inherit the kernel-based formulation of HSIC, allowing efficient estimation by kernel trick and asymptotic distribution analysis with statistical guarantees.\n\n- (Q2) Examples 1.1 and 3.1 illustrate two types of rare dependence and show a shared solution. Example 3.1 is *local*, with $X \\perp Y$ holding in a subregion. Example 1.1 shows *global but weak* dependence, where the signal exists throughout but is largely buried by noise. Both of them motivate our method, which adaptively reweights samples to better reveal underlying dependence patterns.\n\n- (Q3) We thank the reviewer for pointing this out. We acknowledge the inconsistency in notation: X, Y are introduced as random variables in Sec. 2 but later referred to as variable sets. We will unify the notation to \"random variables or sets of variables\". Most examples in our paper treat X and Y as variables for simplicity and illustration purpose. The phrase “C is a subset of X or Y” assumes that X and Y are sets of variables; when they are individual random variables, C is either X or Y. We agree this was ambiguous and will rephrase accordingly.\n\n- (Q4)  We thank the reviewer for this question. Our reweighting framework is general and does not assume rare dependence lies in a rectangular region. In nonlinear Example 1.1, axis-aligned boxes are purely for visualization; they are not a limitation of the method. The nonlinearity is captured by the reweighting function $\\beta(C)$, which is flexible and nonlinear. It assigns higher weights to samples more likely to exhibit dependence, based on their values of C. This allows the method to adapt to complex dependence structures - as long as some signal is present along the reference variable C. Hence, our method naturally handles nonlinear rare dependence.\n\n  We say that C can be either X or Y, but not both. As mentioned in Proposition 3.3, C being either X or Y preserves the independence between them and avoids introducing spurious dependence. However, using $C=(X,Y)$ in Eq. (15) makes the reweighted distribution $\\tilde{\\mathbb{P}}_{XY}=\\beta(X,Y)\\mathbb{P}_X\\mathbb{P}_Y$ no longer factorizable in X and Y. This means the reweighed distribution changes the original independence relation. We will revise the manuscript to clarify these points.\n\n- **On notation and presentation** (Comments)\n\n  We appreciate the reviewer's comments. We will define \"characteristic kernel\" upon its first mention (end of Sec. 2), and revise ambiguous notation — in particular, replacing $\\mathcal{H}$ with $\\mathcal{F}$, denoting RKHSs of X, Y, Z as $\\mathcal{F}_X, \\mathcal{F}_Y, \\mathcal{F}_Z$. We will also provide intuitive explanations and examples for each theorem or proposition when it appears, and streamline the notation for clarity.\n\nWe sincerely thank the reviewer for your recognition and your valuable feedback that helps improve the presentation of our submission.", "claims_and_evidence": "The theoretical claims are clear in general. However, it is unclear how the kernel choice might affect these claims. In particular, the value of HSIC is subject to the kernel choice, which should significantly impact the results, e.g., the independence test.", "methods_and_evaluation_criteria": "The proposed methods and evaluations are reasonable.", "theoretical_claims": "The results are mostly intuitive despite the heavy mathematical notations. The proofs seem reasonable, though I did not check them line by line.", "experimental_designs_or_analyses": "The experiment designs are reasonable.", "relation_to_broader_scientific_literature": "The proposed approach could potentially help improve the performance of causal discovery, which has broader applications in scientific domains.", "essential_references_not_discussed": "Recent works on dependence and conditional dependence learning have extended Rényi's maximal correlation to general analyses of dependence and conditional dependence, e.g., \n\n[XZ2024] Xu, Xiangxiang, and Lizhong Zheng. \"Neural feature learning in function space.\" Journal of Machine Learning Research 25.142 (2024): 1-76.\n\nFor example, the covariance ($\\Sigma$) -based criterion also appeared in analyzing maximal correlation [XZ2024]. The construction of $\\ddot Y$ (cf. Lemma 3.10 of the manuscript) also appeared in [XZ2024] without the kernel assumptions. It could be interesting to compare these analyses and approaches.", "other_strengths_and_weaknesses": "Strength: The theoretical claims are sound.\n\nWeaknesses: see questions.", "other_comments_or_suggestions": "The presentation can be improved. In general, the notations can be so heavy that key ideas are deeply buried in the equations. \n\nExamples:\n1. The characteristic kernel was not defined in its first appearance (end of Sec. 2);\n2. The notation $\\mathcal{H}$ was used to indicate both hypothesis and the RKHS.", "questions_for_authors": "Q1: How do kernel choices affect the results? In practice, how should we select the kernel (e.g., to compute the HSIC claimed by Examples 1.1 and 3.1)?\n\nQ2: Why use two different examples (1.1 and 3.1)?\n\nQ3: Section 3.2, first line: \"two disjoint sets of variables\": is X a set of random variables or a single random variable? Similarly, the definition of C as a \"subset of X or Y\" is problematic. Note that this definition of sets does not apply to examples 1.1. and 3.1, and from later contexts, X and Y seem to be random variables instead of sets.\n\nQ4: Can the designed reweighting be extended to a more general case? Note that in the manuscript, it was assumed that the rare dependence happens in a rectangular region. (equivalently, in Eq. (1), C can only be a \"subset\" of X or Y, not arbitrary shapes.) This might not necessarily be the case when considering nonlinear dependence.", "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": "", "extra_scores": {}}, {"review_id": "bGKLqm25Q6", "reviewer": "Reviewer_6TwN", "summary": "This paper tackles independence testing, when there is rare dependence. Rare dependence is defined as the case when most of the data points exhibit independent behaviour between two variables, but a subset exhibits dependence. The authors propose to solve this problem by augmenting the dataset with weights that are a function of some reference variable, that reweight the samples by maximising the HSIC test statistic for dependence (maximising a measure of dependence). The authors derive the null distribution, show that it is too complex and calculate the required quantile using a permutation test. A conditional independence test version is also introduced. Experiments show that the tests perform better than baselines.\n\n## update after rebuttal\nOn reading the response and the other reviews, I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for the detailed and constructive feedback. Below we address all raised points grouped by topic. All figures and tables are available at https://tinyurl.com/mwafx6kh.\n\n-  **Rare dependence in reality** (Claims & Methods & W1) \nWe clarify that we have evaluated our method on a real-world dataset (Sachs et al., 2005) in Sec. 5.2. We agree that real-world support is important and include additional real-world experiments (see first & second responses to Reviewer MSVk).\n\n- **Consensus datasets** (Claims & Methods)\nWe tested our method on three standard dependence benchmarks: Data Generation III (DG III) in Appendix with $\\tau=1$, i.e. totally dependent; Sinusoid in (Ren et al., 2024) and ISA in (Gretton et al., 2007). As shown in the table, RHSIC slightly underperforms full HSIC due to data splitting to learn reweighting function (split ratio=0.5), but outperforms HSIC using half of the data. \n  In practice, when we are unsure whether rare dependence exists, it is preferable to use HSIC first, and then apply RHSIC if HSIC fails.\n\n  |Method|RHSIC||HSIC||HSIC(n/2)||\n  |-|-|-|-|-|-|-|\n  |Data Generation|Type I ↓|Power ↑|Type I ↓|Power ↑|Type I ↓|Power ↑|\n  |DG III|0.03|0.99|0.04|1|0.04|0.67|\n  |Sinusoid|0.04|1|0.05|1|0.02|1|\n  |ISA|0.09|0.16|0.1|0.26|0.1|0.15|\n\n- **Test-train splitting** (W2)\nWe agree that splitting for reweighting may cause a performance drop compared to full-data baselines, as shown above. However, RHSIC significantly outperforms them when rare dependence exists, suggesting the splitting loss is limited and outweighed by the gain in detecting rare dependencies.\n  To examine the effect, we list different split ratios on DG III $\\tau=0.1$. A 0.5/0.5 ratio generally performs well, consistent with prior work [1,2,3].\n|Tr:Te|Type I ↓|Power ↑|\n|-|-|-|\n|7:3|0.07|0.68|\n|5:5|0.05|0.8|\n|3:7|0.01|0.74|\n|HSIC|0.04|0.17|\n- **Reference variable C selection** (Comments)\nWhen do UI/CI tests where only X and Y are observed, we consider C=X or Y. Once more information is available, e.g. more observed variables as in causal discovery, C can be a third variable to leverage such information.\n  Take the DG III $\\tau=0.1$ as an example, in the causal graph X<--$\\epsilon_b$-->Y<--Q, we observe X, Y, Q and want to test X $\\perp$ Y. Proposition C.2 shows that C=X, Y, or Q are all valid here (i.e., do not introduce spurious dependence). RHSIC with C=Q performs the best since Q directly controls the dependence between X and Y, while C=Y, a child of Q, brings some power loss though still acceptable. C=X is ineffective since X $\\perp$ Q.\n|Method|Type I ↓|Power ↑|\n|-|-|-|\n|RHSIC (C=Q)|0.05|0.8|\n|RHSIC (C=Y)|0.1|0.57|\n|RHSIC (C=X)|0.01|0.06|\n|HSIC|0.04|0.17|\n\n  In practice, if only X, Y are available, we recommend testing with both C=X and C=Y and selecting the lower p-value.\n\n- **Proof for Prop. 3.6** (Theoretical)\n We are sorry for omitting the proof for Proposition 3.6 in the submission, and we include it below. The proof uses the independence preservation under measurable transformations.\n\n  *Proof.*  Since the data are i.i.d., $D_{tr} \\perp D_{te}$.  As $\\hat{\\beta} = f(D_{tr})$ is a measurable function of $D_{tr}$, it follows that $\\hat{\\beta} \\perp D_{te}$  (Thm 4.3.5 in [4]). $\\square$\n  \n   We also agree that the appendix numbering could be improved, and we will revise it to clearly indicate where each proposition is proven.\n\n- (Q1) We have updated Fig. 3 (see the link above) and will revise the surrounding text for clarity. We use it to visualize that the original HSIC may fail to detect dependence in rare dependence settings, even if we have infinite samples. \n\n- (Q2) We should make sure the reweighted p.d.f., $\\tilde{\\mathbb{P}}(X,Y)=\\beta(C)\\mathbb{P}(X,Y)$, is still a well-defined one, i.e. $\\int_{\\mathcal{X\\times Y}}\\tilde{\\mathbb{P}}(X,Y)dXdY=1$, which gives us $\\mathbb{E}[\\beta(C)]=1$. We will clarify this in our manuscript.\n\n- (Q3&4) Thank you for your careful reading. We will correct the terminology in L169 and formally define KCIT and RKCIT in Section 4.\n\n- (Q5) Thanks for your question. In our rules, we employ KCIT to detect non-rare dependencies and RKCIT to detect rare ones. While RKCIT is capable of identifying non-rare dependencies as well, its reliance on data splitting may introduce unnecessary statistical inefficiency. Therefore, we prefer KCIT in such cases. Assumption 4.1 guarantees the reliability of KCIT when it rejects the null hypothesis. However, if KCIT fails to reject, this could be due to the presence of a rare dependence, in which case RKCIT serves as a complementary test.\n\nWe sincerely appreciate your thoughtful feedback and recognition of our work. Thank you for your time.\n\n[1] Interpretable distribution features with maximum testing power. NeurIPS 2016.\n\n[2] An adaptive test of independence with analytic kernel embeddings. ICML 2017.\n\n[3] Learning adaptive kernels for statistical independence tests. AISTATS 2024.\n\n[4] Casella & Berger, Statistical Inference.", "claims_and_evidence": "The only claim that is not thoroughly tested is the fact that rare dependence is actually an issue in reality. The authors also test their causal discovery method in the appendix, however, I would also like to see application of their method on a consensus benchmark (one that is not constructed to exhibit rare dependence), to see what is lost in this case.", "methods_and_evaluation_criteria": "The authors test only on examples where rare dependence is synthetically created. Some real world example of this would be beneficial. Furthermore, it would be interesting to see what is lost compared to baselines if the data does not actually exhibit rare dependence.", "theoretical_claims": "I can't seem to find the proof for proposition 3.6. The proofs in the Appendix are also numbered differently than the main paper, this makes finding the exact proof for a claim a little difficult. Furthermore, it might make sense to write (at the start of the section or where the proof is written), exactly where this is proven.\n\nThe rest of the proofs seem correct.", "experimental_designs_or_analyses": "The experiments seem sound (see above for some issues).", "relation_to_broader_scientific_literature": "I have not seen the issue of rare dependence tackled in this way.", "essential_references_not_discussed": "Up to my knowledge the required references are discussed in Appendix B.", "other_strengths_and_weaknesses": "Strengths:\n- The paper is tacking an issue that has not been tackled before.\n- The solution is sound with experiments showing improvement over the baselines.\n\nWeaknesses:\n- The paper does not convincingly argue that rare dependence is a problem in practice.\n- The splitting into test and train may lead to a loss of performance compared to other baselines. This has not been explored properly.", "other_comments_or_suggestions": "It is not quite clear to me how to select the reference variable C. From the motivating examples, it seemed to me that it has to be either X or Y, but the experiments seem to suggest that it can be a third variable as well. How is this variable chosen in practice? What are the effects of choosing one variable over another given a certain causal graph?", "questions_for_authors": "- Figure 3 is not clear at all, n1 and n2 are not defined, the text around the figure is also confusing. I can see what point is being made, but unsure how the figure is helping here.\n- Eq 1, why do you want the expected $\\beta(C)$ to be equal to 1? This should be explained in the text.\n- L169 LHS, it might make sense to say that the test statistic is being maximised (instead of optimised).\n- KCIT and RKCIT are not formally defined in Section 4.\n- I'm unsure why your rules are defined in terms of KCIT and RKCIT both? The relation and the compromises between KCIT and RKCIT should be explained properly here.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel kernel-based conditional independence test method. The method captures rare dependence patterns through adaptive sample importance reweighting. The authors incorporate this conditional independence test into the PC algorithm and demonstrate its effectiveness using both synthetic and real-world datasets. The paper addresses an important problem in causal discovery. The method comes with theoretical guarantees, including bounds and asymptotic properties.
Decision: Accept (poster)