acceptodds
Under review as a conference paper at ICLR 2027

Binary Expansion Group Intersection Network

Abstract

Conditional independence is fundamental to modern statistics and machine learning, yet beyond special parametric families it rarely admits an exact covariance-based characterization. We introduce the binary expansion group intersection network (BEGIN), a distribution-free graphical framework for representing conditional independence in multivariate binary data and bit-encoded multinomial variables. We show that for arbitrary binary random vectors, conditional independence is equivalent to a zero cross block of a generalized Schur complement. Its entries are probability-weighted sums of conditional covariances, with signs determined by conditioning interactions. The representation encompasses Ising models, higher-order binary models, and categorical graphical models, including distributions with structural zeros. We characterize the rank of the interaction covariance and establish Markov properties and conditions for concatenating BEGIN graphs. We test conditional independence using the maximum absolute value of the estimated entries in the BEGIN cross block, and we show that this test attains the optimal sample order under sparse interaction alternatives. Simulations show the power gain under sparsity and the computational efficiency of the interaction scan. An analysis of categorical Mushroom records shows how the maximizing binary interactions explain detected conditional associations.

Primary area:
learning theory
Keywords:
conditional independence, graphical models, binary data, Schur complement, distribution-free methods, group theory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_M79dOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper introduces BEGIN, a framework that characterizes conditional independence in binary and bit-encoded categorical data through zero blocks of a generalized Schur complement, including distributions with structural zeros. It develops graphical interpretations, a continuous-variable extension through increasingly fine binary expansions, and a maximum-interaction test with matching sample-complexity bounds under specified sparse alternatives. Validation consists of simulations evaluating power and computation, and an analysis of categorical Mushroom data.

Critical strengths
  1. Exact and interpretable characterization. Theorem 3.2 and Proposition 3.3 connect conditional independence to a zero residual covariance block, whose entries have explicit interpretations as weighted conditional covariances. Accommodating structural zeros and singular encodings makes this characterization applicable to general finite categorical distributions.

  2. Matching sparse-testing bounds. Under the stated design and sparsity assumptions, Theorem 4.1 establishes matching sample-complexity upper and lower bounds. This provides a substantive theoretical justification for Max BEGIN’s effectiveness against sparse interaction alternatives.

Critical weaknesses
  1. Insufficiently established novelty. The characterization builds on complete binary interaction bases, existing residual-covariance criteria for conditional independence, and Schur complements. Moreover, under the simulation design, Max BEGIN’s coordinates coincide with fixed-weight WGCM residual numerators. The paper does not sufficiently distinguish its conceptual advances from these existing ingredients, making the significance of its methodological contribution difficult to assess.

  2. Limited coverage of the testing guarantees. The optimal-power result requires a known conditional assignment law, independent fair conditioning bits, and sparse alternatives in a prescribed dictionary. It does not cover the within-cell permutation procedure used when the assignment law is unknown. The continuous extension provides a population characterization and approximation bounds, but no depth-selection rule or calibration accounting for discretization bias. Given prior work on CI testing from discretized continuous observations [1], the paper should clarify how its extension differs in assumptions, inferential targets, and statistical guarantees.

[1] Sun et al. A Conditional Independence Test in the Presence of Discretization. ICLR, 2025.

Questions for authors
  1. Could you clarify which results constitute nontrivial advances over existing complete-function CI criteria, BELIEF, and WGCM?

  2. Could you also report the Quadratic BEGIN and Interaction OLS dCRT comparisons already implemented in the supplementary code and explain their omission from the manuscript?

2 comments

We thank the reviewer for the careful assessment, and for asking how BEGIN relates to existing criteria and to WGCM, what the guarantees cover, and how the omitted comparisons perform.

W1 and Q1. Novelty. How does BEGIN relate to complete-function criteria, BELIEF and WGCM?

Daudin (1980) and Fukumizu et al. (2008) characterize conditional independence through residual covariances over complete function classes. BEGIN makes that class explicit and finite for binary vectors. Theorem 3.2 gives the criterion S[L,R]=0S[L,R]=0 on the Schur cross block for two multivariate endpoints, valid for every joint pmf, including singular categorical encodings. Proposition 3.3 gives each entry in closed form, as a signed sum of cellwise conditional covariances weighted by the cell probabilities. The products label the entries to scan and identify the contrasts behind a rejection.

The conditional-mean expansion in our Theorem 3.2(b) comes from BELIEF (Brown, Zhang and Meng, 2025, Lemma 2.2). Its Theorem 2.1 also gives the endpoint-product criterion when applied within each supported conditioning cell. BEGIN identifies the conditioning group as the intersection of the groups generated by the bits on the two sides and gives the corresponding Schur cross block. In particular, with no conditioning variables, Theorem 3.2 reduces to BELIEF Theorem 2.1, and for a scalar response BELIEF Theorem 2.5 gives a related slope criterion under full predictor support. Its Theorem 2.6 gives a precision-matrix criterion under an additional interior conditional-mean condition.

For WGCM, take scalar signs A,CA,C and a fixed product weight BΓB_\Gamma. A BEGIN coordinate is

=\mathbb E\left[B_\Gamma\operatorname{Cov}(A,C\mid B)\right].$$ As you note, the displayed quantity is the population moment targeted by fixed-weight WGCM. More generally, with the same endpoint features and conditioning weights, fixed-weight WGCM recovers the Max BEGIN. In the simulations of Section 5, both endpoints are scalar signs with known conditional means of zero, so the empirical numerators also agree for each matched weight. The test statistics and $p$-values can still differ because WGCM studentizes each score and the two tests may use different calibration methods. For binary data, BEGIN makes three novel contributions. A complete characterization of conditional independence. The group structure explains why these particular features and weights suffice. The groups of bit products generated by $(A,B)$ and $(B,C)$ share precisely the products generated by the conditioning bits $B$. After adjustment for this shared group, each entry of the Schur cross block depends on its two conditioning products only through their product (Proposition 3.3). Thus, for each pair of endpoint products, at most $2^{r_B}$ distinct scores determine all $4^{r_B}$ entries, where $r_B$ is the number of conditioning bits. These scores recover the conditional covariance in each supported cell, weighted by its probability. Theorem 3.2 shows that $A$ and $C$ are conditionally independent given $B$ if and only if all scores vanish for every pair of endpoint products, even when some bit patterns have zero probability. Interpretation of the maximizing score. In the light-tunnel example (Section 6.1, Figure 3), 36 scores suffice for all 144 Schur entries. In 48 of the 100 subsets, the maximizing score paired the high-versus-low infrared bit $C_1$ with the angle product $A_1A_2B_1B_2$. In 40 subsets, it paired $C_1$ with $A_1B_1$. The first angle pattern approximates the sign of the cosine product in (6.2), and the second approximates the sign of the sine product. The maximizing score thus identifies which physical pattern is most strongly associated with high versus low infrared readings in a given subset. Computational speed. BEGIN evaluates the sign products by packing observations into machine words and counting bits. At $n=512$, the full Max BEGIN test scanned 37 conditioning products and completed 199 randomizations in a median of 2.40 ms. The forest-weighted CRT, which fits a weight on half the sample, took 119.53 ms (Appendix N, Table 2). We did not time fixed-weight WGCM with the same products.

(Continue from the previous comment) W2. Scope of the guarantees. Which conclusions require a known law, fair bits, sparsity or a choice of depth?

For i.i.d. observations of scalar binary endpoints and a known conditional law of AA given BB, the level guarantee holds for any distribution of BB. The matching sample order hlog⁡(M)/ρ2h\log(M)/\rho^2 assumes independent fair conditioning bits, at most hh nonzero coefficients in a prespecified dictionary of size MM, and signal energy at least ρ2\rho^2. The stated range is 1≤h≤M1/2−ϵ1\le h\le M^{1/2-\epsilon} and 0<ρh≤10<\rho\sqrt{h}\le1 for fixed ϵ∈(0,1/2)\epsilon\in(0,1/2).

You are right that Theorem 4.1 does not cover the within-cell permutation procedure. Under i.i.d. sampling with fixed encodings, that procedure controls the level of each fixed test in finite samples without knowledge of the assignment law. A matching power bound remains open. The data analysis in the revised Section 6 uses rank cutpoints estimated within each subset. Exact calibration then requires the codes of the permuted endpoint to be exchangeable within each cell conditional on the conditioning codes and the other endpoint codes. Appendix O.4 reports the estimated sample sizes needed for 80% pooled power on measurements from the light tunnel of Gamella, Peters and Bühlmann (2025).

The dyadic approximation theorem (submitted Theorem 3.7, revised Theorem 3.6) is a population result. At a fixed depth, the test targets independence of the encoded endpoints given the encoded conditioning variables. Choosing the depth from the data, and calibrating the original continuous null when the conditional law is unknown, remain open. For bivariate unconditional independence, BET suggests scanning depths up to dmax⁡=4d_{\max}=4 (Zhang, 2019, Section 4.5). In the revised Section 6.2 we report four, five and six bits side by side instead of selecting a depth.

Sun et al. (2025) study a different observation model. They observe discretized versions of latent continuous variables and test conditional independence of the latent variables under a nonparanormal model, with asymptotic calibration. BEGIN assumes no parametric family, targets the observed discrete or encoded variables, and has finite-sample calibration under the exchangeability condition above.

Q2. Omitted comparisons. Why did the submission omit Quadratic BEGIN and Interaction OLS dCRT?

We initially conducted the following experiment. Max BEGIN had higher empirical power in this setting, so we emphasized it in the main text. The table below shows the rejection rates of the three tests under a one-interaction alternative.

Method

Power

Max BEGIN

0.980

Quadratic BEGIN

0.080

OLS dCRT

0.080

Settings for the table: AA and twelve conditioning bits B1B_1 to B12B_{12} are independent fair signs, and CC is a sign with P(C=1∣A,B)=(1+0.4AB1B2)/2\mathbb P(C=1\mid A,B)=(1+0.4AB_1B_2)/2, with n=256n=256. Each test scans all 212=40962^{12}=4096 products BΓB_\Gamma, including the constant. Max BEGIN takes the largest absolute mean of ACBΓACB_\Gamma, Quadratic BEGIN sums the squares of these means, and OLS dCRT is the squared norm of the fitted values when CC is regressed jointly on all ABΓAB_\Gamma. Each test is calibrated by 199 redraws of AA from its known fair law, with BB and CC held fixed, and rejects at level 0.05. Each entry is a rejection rate over 200 datasets.

Space constraints also led us to focus on Max BEGIN, for which Theorem~4.1 gives a sparse-power guarantee. For the 37-product comparison in the originally submitted code at n=128n=128, the powers of Max BEGIN, Quadratic BEGIN and Interaction OLS dCRT were .880.880, .680.680 and .600.600 with one active interaction, and .180.180, .615.615 and .580.580 with sixteen. These results illustrate how relative power depends on the alternative. Under a sparse setting, Max BEGIN is more sensitive and powerful. For this paper we would like to focus on detecting sparse dependence signals. While Max BEGIN doesn't perform as well as the other tests in the other denser scenario, this illustrates a well-known point that no single test is uniformly most powerful against all alternatives in nonparametric dependence testing.

Reviewer_VASdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies how to represent and test conditional independence in multivariate binary data and in categorical variables encoded by bits, without assuming a parametric family. To this end, it expands the variables into all products of their bits, i.e. their interactions, and introduces BEGIN, in which the conditioning information is a group of interactions and the dependence that remains is a generalised Schur complement S\mathbf{S} of the interaction covariance. The main contribution, as the paper presents it, is Theorem 3.2 where for any joint pmf: A⊥ ⁣ ⁣ ⁣⊥C∣B\mathbf{A}\perp\!\!\!\perp\mathbf{C}\mid\mathbf{B} if and only if the cross block S[L,R]\mathbf{S}[\mathcal{L},\mathcal{R}] is zero, which through the generalised inverse also covers the structural zeros of categorical encodings. The paper further gives Markov properties and conditions for concatenating BEGIN graphs (Section 3.4), and an extension to general variables through dyadic expansions (Theorem 3.7). From the cross block it then builds the Max BEGIN test, the largest absolute estimated entry over a prespecified set of products, and Theorem 4.1 states that this test attains the optimal sample order against sparse alternatives when the law of AA given B\mathbf{B} is known and the conditioning bits are independent and fair. Finally, the test is evaluated in simulations against G2G^2, KCI-CRT and a forest-weighted CRT (Section 5), and on the UCI Mushroom data, where seven pairs are rejected at familywise level .05 (Section 6).

Critical strengths

None

Critical weaknesses

The introduction motivates itself by stating in line 038 that "fully distribution-free conditional independence testing is fundamentally impossible without additional structure" citing Shah & Peters (2020) for this statement. However, Shah & Peters qualified their hardness statement for continuous conditioning variables (See Remark 4 of their paper). In contrast, most of this paper deals in discrete variables (other than covering it briefly in Theorem 3.7). Specifically in the abstract (lines 14-16), the paper states the restriction to multivariate binary data and bit-encoded multinomial variables. Also, both the paper's experiments only involve discrete variables as well. Therefore the existing motivation does not cover the setting that the paper's method and experiments address, and the paper's introduction does not motivate/explain why the paper's proposed method is needed for discrete data.

Furthermore, the main text is a bit difficult due to dense prose. For instance, the paragraph after Thm. 4.1 states what the constants depend on, the rate of the randomisation version, the number of scanned products, the cost of forming and scanning them, why sparsity helps, what the maximising product identifies, and how products are computed. These clauses are stated one after another without much linkage between them or text explaining how they relate to the one before. Moreover, Section 3.4 shows how there's a graphical representation of the zero cross block, which is technically nice and interesting, but nothing in this section seems to be referenced again later in the main text. Also, the graphical object in lines 244-247 seems only be defined in Appendix C and SI,J∣S\mathbf{S}_{I,J\mid S} is only defined in words, which makes it harder to understand the section as a whole.

Questions for authors
  • What parts of Section 3, in particular Theorem 3.2 and Proposition 3.3, are already shown in the BELIEF paper (e.g. its Theorems 2.5 and 2.6, which characterise conditional independence through zero slopes and zero entries of an interaction precision matrix), and what parts are the paper's own contributions?
  • Apart from allowing structural zeros, isn't Theorem 3.6 essentially the classical decomposition result for graphs with a complete separator (see Lauritzen 1996)?
  • Section 6 compare Max BEGIN with no other test. Would a G2G^2 test of the same 63 statements, with the same correction, reject the same seven pairs, and if so, what does Max BEGIN add beyond the explanation in Figure 3(b)? Section 6: What can Max BEGIN do here that something like G2G^2 can't?

Minor Comments

  • line 091: maybe state the dimension of the power vector
1 comment

We thank the reviewer for the detailed reading, for the corrections concerning the hardness result and the submitted Theorem 3.6, and for asking how Max BEGIN compares with G2G^2 in Section 6.

Motivation. How does the hardness result of Shah and Peters apply to discrete data?

As you point out, the hardness result of Shah and Peters (2020) concerns continuous conditioning variables. We have removed that statement from the introduction. For discrete data the difficulty is different. Conditioning on several variables splits the sample into many cells with few observations each, even when one simple interaction carries most of the conditional association. BEGIN pools the cells through signed interaction contrasts, and Max BEGIN searches for the largest one. Our reply to Q3 and Q4 shows this effect on physical measurements. The second motivation is structural. A categorical encoding can leave bit patterns unused, and the generalized Schur complement keeps an exact covariance criterion on that restricted support.

Q1. Relationship to BELIEF.

BELIEF Lemma 2.2 (Brown et al., 2025) gives the conditional-mean expansion in our Theorem 3.2(b). Applying BELIEF Theorem 2.1 in each supported conditioning cell also gives the criterion in terms of endpoint-product covariances. In particular, with no conditioning variables, Theorem 3.2 reduces to BELIEF Theorem 2.1, and for a scalar response BELIEF Theorem 2.5 gives a related slope criterion under full predictor support. Its Theorem 2.6 gives a precision-matrix criterion under an additional interior conditional-mean condition.

Our Theorem 3.2(c) characterizes conditional independence of two binary vectors given a third by S[L,R]=0S[L,R]=0 for every joint pmf, including encodings with empty cells, where the interaction covariance is singular (Theorem 3.1). Proposition 3.3 gives each entry in closed form as a probability-weighted, signed sum of cellwise conditional covariances. Section 3.4 uses the generalized inverse of Appendix C to preserve graphical separation in the singular case. Section 3.5 gives the dyadic extension.

Q2. Submitted Theorem 3.6. Is this the classical decomposition along a complete separator?

Yes. We overlooked this literature when we presented the statement as a theorem. We have deleted the submitted Theorem 3.6 and its proof. Section 3.4 now cites the classical results of Lauritzen (1996, Chapter 3) and Dawid and Lauritzen (1993).

Q3 and Q4. Section 6. Does G2G^2 reject the same pairs, and what can Max BEGIN do that G2G^2 cannot?

On the 63 Mushroom statements, with the same records, conditioning sets and correction, G2G^2 rejected 50 and Max BEGIN rejected 40, all of which G2G^2 also rejected. Of the ten statements in the submitted Figure 3(a), G2G^2 with its chi-square reference rejected the same seven pairs and one more, class and cap shape. For this additional pair, exact enumeration with fixed margins gave an adjusted pp-value of 3.23×10−93.23\times 10^{-9}. On those data, Max BEGIN identifies the contrast behind each of its rejections. The Mushroom data have no known graph, so they cannot show which test is closer to the truth.

The revised Section 6 and Appendix O therefore replace the Mushroom analysis with measurements from the light tunnel of Gamella, Peters and Bühlmann (2025, Nature Machine Intelligence), a physical apparatus with a documented causal graph. Figure 3 in Section 6.1 shows how the two most frequent maximizing contrasts distinguish high from low infrared readings across angle patterns that approximate the signs of the cosine and sine products in (6.2). In Section 6.2, we ran the PC-stable search on 14 of its variables once with Max BEGIN and once with G2G^2, using the same rank coding, within-cell permutations and 100 overlapping subsets of 800 measurements. With four to six bits per variable, Max BEGIN kept the three edges from the colour settings to the source current in every subset, while G2G^2 kept at most 28 percent of them. Both tests kept the two edges from the polarizer commands to their measured positions and added few spurious edges. The complete reference skeleton was recovered in 64 to 71 percent of subsets with Max BEGIN and in at most 2 percent with G2G^2.

With dd bits per variable and kk conditioning variables, Max BEGIN scans M=(2d−1)22dkM=(2^d-1)^2 2^{dk} entries, which is also the nominal dimension of the G2G^2 comparison. When few entries carry the signal, the maximum can remain sensitive as finer coding adds entries, whereas G2G^2 collects variation from all of them. Single tests on the same recording (Appendix O.4) show this pattern. With one conditioning actuator, the two tests are close at one or two bits per variable, and G2G^2 falls behind at finer codings.

Reviewer_dc4iOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

By developing a distribution-free graphical framework to represent conditional independence for binary variables, the paper improves power gain and computational efficiency.

Critical strengths
  • The idea of using a distribution-free graphical framework to examine conditional independence was interesting.
  • The results seem to be rigorous.
Critical weaknesses

-The technical parts are difficult to follow, such as 3.1 and especially 3.2. Examples are provided after, but those are to illustrate the results; illustrating the concepts can also help. I know that some of the concepts are basics in linear algebra or probability theory, but it helps to illustrate the less fundamental ones by providing some intuition and inline running examples. 3.5 was very difficult to follow. The paper perhaps better fits a statistics journal.

  • The framework is limited to the binary case
Questions for authors

If the goal is to publish the results in a machine learning venue like ICLR, it may help to demonstrate the benefit of BEGIN when integrated with machine learning models. Can the authors demonstrate that? (Although even doing this may not make the paper a great fit for ICLR)

1 comment

We thank the reviewer for reading the paper carefully and for suggesting a running example and a demonstration of BEGIN inside a learning method. We address both below.

Presentation. It helps to illustrate the less fundamental ones by providing some intuition and inline running examples.

Section 3.3 illustrates the definitions with three signs. For single signs A,B,CA,B,C, the groups ⟨A,B⟩={1,A,B,AB}\langle A,B\rangle=\lbrace 1,A,B,AB\rbrace and ⟨B,C⟩={1,B,C,BC}\langle B,C\rangle=\lbrace 1,B,C,BC\rbrace share {1,B}\lbrace 1,B\rbrace, which carries the conditioning information. Removing the shared group leaves L={A,AB}L=\lbrace A,AB\rbrace and R={C,BC}R=\lbrace C,BC\rbrace. Write w+w_+ and w−w_- for the values of wb=P(B=b)Cov⁡(A,C∣B=b)w_b=P(B=b)\operatorname{Cov}(A,C\mid B=b) at b=+1b=+1 and b=−1b=-1, with wb=0w_b=0 on an empty cell. The Schur cross block S[L,R]S[L,R] is a 2×22\times 2 matrix with w++w−w_+ + w_- in both diagonal entries and w+−w−w_+ - w_- in both off-diagonal entries.

If the two cells carry opposite associations, the sum can vanish while the difference reveals the signal. The sum and difference together recover both weighted cell contributions. At each supported value of BB, division by the cell probability recovers the corresponding covariance, so a zero block is equivalent to conditional independence on the support. Theorem 3.2 extends this argument to vector endpoints.

Beyond binary encoding. Is the framework limited to the binary case?

Section 3.1 handles encodings with unused bit patterns. Six categories with positive probability need three bits but occupy only six of the eight patterns. The covariance of the seven nonconstant interactions then has rank five, and the generalized Schur complement still gives the independence criterion.

The binary formulation also covers categorical and continuous numerical data. A categorical variable enters through its bit encoding, and a numeric variable through its leading binary digits. The first digit records which half of the range contains the observation, the second which quarter, and so on. Coarsening a conditioning variable can leave dependence within a cell. The theorem in Section 3.5 bounds this remaining dependence under conditional independence given the original conditioning variable and the stated continuity conditions, and the bound goes to zero as the cells become finer. The light-tunnel study described under the next point applies BEGIN to such multi-bit codings.

Learning models. Can BEGIN be integrated into a learning procedure? How does the contribution relate to machine learning?

In the revised Section 6.2, we use Max BEGIN as the conditional-independence test inside the PC-stable structure-learning algorithm (Colombo and Maathuis, 2014) on measurements from the light tunnel of Gamella, Peters and Bühlmann (2025), a physical testbed for AI methodology with a documented causal graph. With the same search, Max BEGIN recovered the undirected reference graph in 64 of 100 subsets at four bits per variable, compared with 2 of 100 for G2G^2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.