Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation
Authors: Yang Ni
Venue: NeurIPS 2022 Accept (2022)
Keywords: Causal Discovery
Categorical Data
Qualitative Data
Discrete Data
Bayesian Network

Abstract: Causal discovery for quantitative data has been extensively studied but less is known for categorical data. We propose a novel causal model for categorical data based on a new classification model, termed classification with optimal label permutation (COLP). By design, COLP is a parsimonious classifier, which gives rise to a provably identifiable causal model. A simple learning algorithm via comparing likelihood functions of causal and anti-causal models suffices to learn the causal direction. Through experiments with synthetic and real data, we demonstrate the favorable performance of the proposed COLP-based causal model compared to state-of-the-art methods. We also make available an accompanying R package COLP, which contains the proposed causal discovery algorithm and a benchmark dataset of categorical cause-effect pairs. 

Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation
Yang Ni Department of Statistics Texas A&M University College Station, TX 77843 yni@stat. tamu. edu
Abstract
Causal discovery for quantitative data has been extensively studied but less is known for categorical data. We propose a novel causal model for categorical data based on new classification model, termed classification with optimal label permutation (COLP). By design, COLP is a parsimonious classifier, which gives rise to a provably identifiable causal model. A simple learning algorithm via comparing likelihood functions of causal and anti-causal models suffices to learn the causal direction. Through experiments with synthetic and real data, we demonstrate the favorable performance of the proposed COLP-based causal model compared to state-of-ther methods. We also make available an accompanying R package COLP, which contains the proposed causal discovery algorithm and a benchmark dataset of categorical cause-effect pairs.
1 Introduction
Discovering causality from observational data has seen rapid development recent years partly because knowledge of causality is desired in many areas where controlled experimentation is very difficult, infeasible, or expensive to carry out. Particularly, for continuous and count data, numerous
methods and theories have been developed (Shimizu et al., 2006 Hoyer et al.) 2009 Zhang and Hyvärinen| 2009 Mooij et al. 2010 Janzing et al. 2012 Chen et al.] 2014 Sgouritsa et al. 2015 Hernandez- Lobato et al. 2016 Marx and Vreeken 2017 B Blöbaum et al. 2018 Park and Park 2019
Choi et al. 20200 Tagasovska et al. 2020J. All of these methods, in essence, exploit the quantitative nature of continuous and count data in discovering causality. Therefore, they not applicable to categorical data for which the values can only be interpreted qualitatively. For example, while Y (X) E may be reasonable causal model for continuous data, the interpretation of such model for categorical data, although possible (Peters et al., 2010 Suzuki et al.) (0044) under certain cireumstances, is much less natural because the order of magnitude of the values of categorical data is arbitrary and meaningless
(Cai et al., 2018).
In general, causal discovery for categorical data is much less studied. What is known to date is that the causal model X - can be identified if X and are ordinal [Ni and Mallick] 2022]. X admits hidden compact representation Y' f(X) such that Y'I < ( denotes the cardinality) and X - Y - CCa et al. 2018 Qiao et al. 2021). if the exogenous variable E of the structural causal model Y
JX, E') has entropy that does not scale with the number of categories [ompton
eet al. 2020 2022 if P(X) and P(Y[X) are independent random variables [Liu and Chan 2016). or
if the categorical variables X and Y binary and they do not share the same marginal distribution
(Wii et al.) 2018). Note that causal discovery methods that focus on identifying Markov equivalence
classes Spirtes et al. 2000 Lam et al. 2022] are not directly applicable to bivariate causal discovery
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

problems as X + Y and Y - X are Markov equivalent. However, when additional variables are available, they may be able identify direct or indirect causal relationship between X and Y.
In this paper, we propose a novel causal model for categorical data based on classification with optimal label permutation (COLP). COLP itself is a new classifier, which is more parsimonious than multino- mial regression. COLP is inspired by ordinal regression, which has considerably lower model com- plexity than multinomial regression. Unfortunately, by design, ordinal regression is only applicable to categorical responses that admit natural ordering, e.g., human satisfaction (low, medium, and high). However, many categorical variables (e.g., choice of sports from (gymnasties, boxing, volleyball)) do not appear to have natural orderings but we argue that for the purposes of prediction, the response Y may be ordered in a meaningful way depending on the predictor X. For instance, one wants to to predict a person's 's choice of sports Y E {gymnastics, boxing, volleyball| based on his/her height X, it would make sense to order gymnastics < boxing < volleyball because on average volleyball players are taller than boxers who in turn tend to be taller than gymnasts. On the other hand, if the prediction of Y is based on the person's is strength, another ordering, volleyball < gymmasties < boxer, may be more suitable. In either case, once the ordering has been figured out, ordinal regression can be applied to model and predict given X. Of course, determining the ordering of Y could be subjective and tedious. The proposed COLP model is precisely designed to automatically find the best category ordering in an objective way. As expected, its model complexity is between multinomial regression and ordinal regression.
The main objective of this paper is causal discovery for categorical data. It turns out that the parsimony of COLP is quite useful in that regard while causal models based on multinomial regression are non-identifiable, we prove that the proposed COLP-based causal models are identifiable under the causal Markov and causal sufficient assumptions. Our experiments with synthetic and real data show that the proposed method outperforms state-of-the-art alternative methods.
2 Proposed Method
We first introduce the classification model COLP in Section COLP may be interest by itself as a new classifier but the focus of this paper is to build causal model based on COLP, which is presented in Section 2.2
2.1 Classification with Optimal Label Permutation
Let Y E (1...., L} be categorical response variable with L levels and let X = -X1, Xz)T be a S-dimensional predictor vector. Note that if L = 2, ordinal logistic regression, nominal logistic regression, and the proposed COLP equivalent and hence hereafter always assume L > 2. Later, X will be dummy variables representing a categorical predictor with S levels but, for now, we present COLP for general set of predictors.
If is ordered, an ordinal regression is often used,
P(Y < f x = F(y - B) 6= L.
(1)
where F is some link function (e.g., standard normal or logistic CDF), 7 .... </ are set of thresholds. and E R are ordinal regression coefficients. Equation (I) implies the conditional probability distribution P(Y = f X = F(y: X" - F( XT3) for & E (1...., (i....,) L} where To = -c, ?i = 0 (for parameter identifiability). and 7v. = Do. Therefore, effectively, the model complexity (i.e., the number of parameters) of an ordinal regression is I, 2 + S.
If Y is nominal with no natural ordering, a multinomial (logistic) regression can be used instead,
e
xT Be
P(Y = {X) Etarexi
l 1-
where Br are category regression coefficients and, for parameter identifiability, Bg = 0. The effective model complexity is (L 1) x S, which is strictly greater than the model complexity of an ordinal regression, L 7 2+5 S for I > 2 and 5 > 1. Even though multinomial regression is obviously also applicable to ordinal data by simply ignoring the ordering, ordinal regression often preferred over multinomial regression in this case because of parsimony.

---

S} with Here, we propose new classification model, which is more parsimonious than multinomial regression and useful beyond ordinal categorical data. The general idea is introduce permutation (1...., 1.] - {I..... L.J. which orders the categories so that the ordinal regression is applicable. Specifically, we propose the following probability model,
P(Y S e x F(Ya(e) x² E=,....,
which is similar to ordinal regression (T) but with an important additional parameter a E where E is the collection of all permutations of size L. Because any ordering and its reverse ā (i.e., (i) < (i) if and only if (i) > ā(]) would lead to equivalent ordinal regression models, for parameter identifiability, we assume o (1) < (2). Therefore, the effective size of o is L - because once a (3)..... (L) are fixed, o(1) and (2) are fixed due to the contraint. Consequently, the overall complexity of the proposed COLP model is L - 2 S + L - - 2L + S - 4. which is less than the complexity of a multinomial regression, (L (--1) 1) x 5, for L,S > 2. Similarly to the ordinal regression, (3) implies the conditional probability mass function,
P(Y = x = F(7(()) x" 3) F(7(()) B), B), f= L.
(4)
As we mentioned in Section 1 although a categorical variable may not have natural ordering, for the purpose of modeling and prediction, they may ordered meaningful way depending on the predictors. The proposed COLP, by including ordering parameter, can automatically find the best ordering in an objective manner. In addition, even for categorical variables that have natural orderings, the proposed COLP may still be preferred over both ordinal regression and multinomial regression. For instance, in one of later real data examples, Y = shelf placement E {1,2,3 2.33 (counting from the floor) and X cereal manufacturer. To predict Y based on X, it makes more sense use less natural ordering 1 < 3 < 2 for Y as shoppers are more likely to buy products on the middle shelf than either the top or bottom. In fact, when we ran COLP this data, 1 < 3 < 2 was identified as the optimal ordering. Moreover, COLP and the multinomial regression had the same goodness of fit, which was better than that of the ordinal regression. COLP had the best out-of-sample prediction, followed by the ordinal regression, and the multinomial was the worst. For this example, COLP had the right model complexity to achieve the best model fit as well the best out-of-sample prediction.
2.2 COLP- Causal Discovery
Next, we build a causal model based on COLP. Let Y E (I,..., L) and X E {1,..., L, S > 2. The COLP- causal model considers two competing causal hypotheses.
Mo X +Y vs M1 YY + X
with (observational) probability mass functions,
Px-r(X s, = f) = xx =1X- = 8),
Xx = s, = =) Px = -)PY = s|Y = e),
where Px-,y (x=
= 5) and Px {) are multinomial with probabilities w (w1,- ... ws) and p == (PI..... ., PL), and Px-y f| s) and P s|Y E) take similar forms as (4)
Px-Y f|X =) F(1(()) x" F(%)(0-1-33 - -x
Pr-x = s/Y = = =F(m(()) Y ax) - F( - Y
where X E (0, 13. and E 1). are dummy variable representation of X and Y, and a E Σ
In summary, causal model Mo X - Y is parameterized by (w, B, o) with = (72. .6-11 and B E RR whereas M1 Y + X is parameterized by (p. a. m7, x) with 17 (122 ... ---1) and L.
and x E II are permutations of [1,... [.} and ( S).
Like regression, the proposed COLP-based casual model (complexity 2L + 2S 5) is more parsimonious than saturated bivariate multinomial model (complexity = S x L 1). In fact, multinomial causal model where PX- &|X s) is multinomial regression has the same complexity as the saturated model. Therefore, a multinomial causal model is essentially just reparameterization of joint multinomial distribution, which of course can factorized in both causal and anti-causal directions, and hence is not identifiable. Now, the question is: can the parsimonious COLP-based casual model break the symmetry? The answer is yes, which will be formally established in the next section.
3

---

P(X,Y)
X
X
X =
==1
0.040
0.210
0.080
P(JP)
Y= 1
==2
Y
=
0.125
0.005
0.250
X 1
0.12
0.33
0.29
Saturated
Y 3
0.085
0.035
0.170
Px-r (X,Y)
Multinomial
0.64
0.01
0.12
Model
X 3
0.24
0.66
0.59
Y
P(Y)
M,:Y - x
1
0.33
COLP-Based Causal Model
2
0.38
P(Y)))
==
X=
X =
Mg: X
3
0.29
==1
0.16
0.84
0.16
Y= 2
0.50
0.02
0.50
X
P(X)
=
0.34
0.14
0.34
1
0.25
2
0.25
3
0.50
Figure Illustration of causal identifiability of COLP-based causal model. The set of joint dis- tributions P(X, Y) that can be represented by the COLP-basee causal model is a subset of those represented by the saturated multinomial model (this relation is indicated by ellipses). A specific COLP-based causal model Mo X - is given by = (0.25, 0.25, 0.5), 1, = (1, 11,
((1) = (2) = 3, and (3) = 2. These parameter values determine the conditional probability X( and the marginal probability P(X). which in turn define the joint probability P(X, Y). Although it is easy to find P(X[Y) and P(Y) for anti-causal model M1 Y
from the joint probability P(X, Y), M₁ no longer in the class of COLP- based causal models. Hence, if causal models are constrained to be COLP-based, the correct causal direction - Y can be identified.
2.3 Identifiability
Before stating our main identifiability theorem, we first provide intuition as to why multinomial regression-basees based causal models non-identifiable whereas the proposed COLP-basee causal models are identifiable. As mentioned in Section multinomial regression- based causal models are simply reparameterization of saturated bivariate multinomial model whereas COLP-based causal models are more parsimonious. We represent such relation as Venn diagram in Figure [ For given COLP-based causal model (represented by the dot in the inner ellipse), say Mo X - Y with X,Y E [1,2, 3). its conditional probability P(Y and marginal probability P(X) (represented by the probability tables at the bottom left corner) are determined by its specific parameter values, say w = (0.25, 0.25, 0.5), = 1, = (1, 1, 1)a a (1) = 1, (2) = 3, and (r3 = 2. The conditional and marginal probability distributions define the joint distribution P(X, Y) represented by the dot and the probability table at the top left corner. Now consider causal model with reversed direction Mj + X. Since the joint distribution (XX, Y) can always factorize into P(Y) and P(X] Y) (represented by the probability tables at the top right corner), it is obvious that Mg = Mi under such factorization. But M, represented by the dot in the outer ellipse, does not belong to the class of COLP-basee causal models anymore. In summary, when constrained to COLP- causal models, this particular example of Mo does not have an equivalent model. The identifiability theorem below shows that this is true in general.
Theorem If there is no unmeasured confounder, the link function F(.) is fixed real analytic function!] and F'()) is nowhere zero, then for almost all (w, 3, () there does exist (p, oz, m. σ) such that Mo = M1. i.e., Px-y((X = Y = E) = Pr = s. = E) for all (s, E (I.....S) L}.
All proof' provided in the Supplementary Material. No unmeasured confounder is common assumption in prior causal discovery work for categorical data [Peters et al. 2010 Suzuki et al., 2014 Liu and Chan 2016 Cai al. 2018 [Compton et al.] 2020]. The requirements the link function F(.) are quite mild; well-known link functions such as probit and logistic satisfy them.
A real function is said to be analytic if it is infinitely differentiable and matches its Taylor series in neighborhood of every point.

---

Algorithm Greedy Search: MLE of COLP
Input: data V1), ./)........ (In Mn initial parameters w. 8,7,0 Compute (()) = max Ii= Px-r(X Fy = "il,,,,,71 7.
Set M, (()
repeat
Initialize Improvement false for all permutation reachable from a do Compute (o') if M(o') > M. then
Set o' and M, M(o')) Set Improvement = True
end if end for until Improcement is false
Output: maximized likelihood M.
Next, we show that asymptotically we can correctly identify the true causal model.
Theorem 2 If Mo X + Y is the true data generating model, the likelihood of Mo is asymptotically greater than that of the anti-causal model M1 X.
Theorems and suggest simple causal discovery algorithm based on maximum likelihood
estimation (MLE). For dataset with n observations, (I1, 91),.... (Iin Mn). we conclude Mo X Y if
II Px-Y(X = F4, Y 3,7,0) w.B.y.a
II Py-x(X= Ix Y = Yo y. az 7, m) 1=1
max
max p.a.
and conclude M1 Y - otherwise. The MLE can be carried out in two steps. In the first step, for every Σ, we maximize the likelihood over w. w, 3, 7 through the standard MLE of ordinal
regression by treating ((g)).... (B,) as ordered labels, ((o max ,.r IT Px (X = r; Y. y/ (w, G, y, r). Then in the second step, we pick the largest ((r) among all E. This exhaustive search over all permutations is feasible when the number of categories is small. For categorical data with moderately large number of categories, (Algorithm [ can be used instead. At each iteration, we compute the MLE of ordinal regression for all the permutations that can be reached from the current permutation by switching the order of two elements. We replace the current permutation by the permutation with the largest increase in likelihood and stop the algorithm when the likelihood can no longer be improved.
iterative greedy search algorithm
3 Experiments
3.1
Synthetic Data
We first assessed the performance of the proposed COLP-based causal discovery method with three sets of synthetic data. For comparison, we considered recent categorical discovery method based on hidden compact representation (HCR, Cai al. 2018)
3.1.1 Scenario 1: Small Number of Categories
We generated data with the number of categories L = = 5 and varying sample size n = 50, 100, 1000. The true parameters were set as (1/5, 1/5, 1/5, 1/,, (E) E, Ve, and chosen to have balanced class size for each variable. Both the exhaustive (COLP. Exhaustive) and greedy (COLP-Greedy) versions of the COLP-based causal discovery algorithm were applied. The results based on 500 repeat simulations are summarized in Figure 2a and COLP-Greedy had virtually the same accuracy in identifying the correct causal directions, both of which increased with the sample size, which empirically verified Theorems [ and 2 and uniformly outperformed HCR. We also computed the Kendall's Tau between the estimated category ordering and the true ordering. Kendall's Tau close to I indicates good estimation. The average Kendall's
~ N (0, Is).
5

---

1.0
1.0
0.8
Accumcy
Accuncy
0.6
0.
COI --xttuuteie COLP Grredd
0.
400
600
600
1000
200
600
800
1000
200
400
600
600
1000
Sample Size
Sample
Sample
(a) Scenario 1
(b) Scenario 2
Scenario
Figure 2: Synthetic Data. Average accuracy of causal identification for
COLP.
Greedy, and HCR across different sample sizes and scenarios based on 500 repeat simulations. Standard errors are represented by the error bars. The accuracy curves of COI.-Exhause in (a) and (c) are slightly shifted the right for visualization.
Kendall' Tau
Scenario Scenari Scenario
0.4
200
400
600
800
1000
S Sample Size
Figure 3: Synthetic Data. Average Kendall's Tau of ordering estimation for COLP-Greedy, across different sample sizes and scenarios based on 500 repeat simulations. Standard errors are represented by the error bars.
Tau of COLP-Greee P-Greedy is reported Figure 3 improved as expected.
As sample size increased, the ordering estimation
In the Supplementary Material, we present additional results under this scenario: (i) we performed an ablation study to demonstrate the importance of learning the category ordering, and (ii) we investigated how estimation causal direction and label permutation vary as the number of categories increases.
3.1.2 Scenario 2: Larger Number of Categories
We now increased the number of categories to L = S 10 while keeping all the other simulation parameters the same. We did not apply COLP-Exhaustin COLP-Greedy outperformed HCR across all sample sizes and the margins were wider than those in Scenario 1. The ordering estimation had the similar increasing trend in Kendall's Tau sample size increased as in Scenario (Figure 3)
in this scenario. As shown in Figure 2b
3.1.3 Scenario 3: Hidden Confounders
While our identifiability theory assumes no unmeasured confounders, we empirically tested the sensitivity of our method to the presence of confounders. We generated trivariate categorical data (X, Y, Z) from the following true causal graph with the simulation parameters kept the same as in Scenario 1,

---

Z
X
Y
We applied COLP and HCR to (X, Y) only (i.e., Z became a hidden confounder). As shown in Figures 2c and COLP had the best performance and the estimation of causal directions and category orderings approached perfect recovery as sample size increased even in the presence of confounders.
3.2 Real Data
We further evaluated the proposed COLP- causal discovery method with four sets of public real categorical data: (i) Pittsburgh Bridges dataset, (ii) Abalone dataset, (iii) Tübingen Cause-Effect Pairs, and (iv) newly-created Categorical Cause-Effect Pairs. For comparison, we considered HCR as before and an additional competing method, entropic causal inference (ECI, Compton et al. (0200). For variables with more than six categories, only the greedy search applied for COLP-basee causal discovery. For variables with fewer categories, both exhaustive and greedy algorithms were applied, which generally produced the same results; therefore, do not differentiate between the two implementations when reporting the results below for simplicity.
3.2.1 Pittsburgh Bridges Dataset
This dataset [Reich and Fenves 1989] is available from the UCI Machine Learning Repository and was used in previous causal discovery work [Cai et al. 2018). It has 108 observations and the following 4 true cause-effect pairs: Erected (Crafts, Emerging, Mature, Modern) - Span (Short, Medium, Long), Material (Steel, Iron, Wood) - Span (Short, Medium, Long), Material + Lanes (1, 2, 4, 6). and Purpose (Aqueduct. Highway, Rail, Walk) Type (Wood, Suspen, Simple-T, Arch, Cantilev, CONT-T). addition to HCR and ECI, we also applied Markov equivalence blass-based causal discovery algorithm, GRaSP [am et al. 2022]. to all the variables.
The results are presented Table | COLP was able to correctly identify all cause-effect pairs whereas HCR missed 1 pair, ECI missed 2 pairs, and GRaSP correctly identified two direct causal links and two indirect causal links (i.e., directed paths with the correct directions). The effect variables of the first three pairs, Span and Lanes, have natural orderings, namely, Short < Medium Long and 1 < 2 < 4 < 6. The optimal orderings identified by COLP perfectly matched them (note that COLP does not take the natural ordering as input). The effect variable, Type, of the last pair does not have an obvious natural ordering. The optimal ordering was estimated to Simple-T < Cantilev CONT-T < Arch Wood Suspen and the COLP regression coefficients under X - Y were estimated to be 3 AAqueduet 2.90, Highway 1.03,, &Rail 11.63, and @ 13.66. This ordering seems sensible considering that the predictor/cause was Purpose. For example, (Simple-T, Cantilev, CONT-T) bridges more likely to be used for rail roads whereas (Arch, Wood, Suspen) bridges are more likely to be used for walking. Therefore, their ordering is consistent with the signs of &Rail (negative) and @allk (positive).
1.03,
Table 1: Pittsburgh Bridges Dataset. Correctly (incorrectly) identified causal direction is marked by / (x). For GRaSP, O means directed path was identified.
Cause (X)
Effect (Y) COLP HCR
ECI
GRaSP
Frected
Span
/
d
x
Material
Span
/
/
Material
Lanes
/
/
x
0
Purpose
Type
/
x
3.2.2 Abalone Dataset
This dataset (Nash et al. 1994 is available from the UCI Machine Learning Repository and was used previous research Cai et al. 2018). It has 4177 observations and the following true cause-effect pairs: Sex (male, female, infant) + Length, Sex - Diameter, and Sex + Height. We discretized Length, Diameter, and Height into categories their 20% 106,44%%,6099 and 80% quantiles. As in Section 3.2.I we compared COLP with HCR, ECI, and GRaSP.
7

---

The results are reported in 2 COLP and ECI were able to correctly identify all 3 cause-effect pairs whereas HCR missed pair, and GRaSP correctly identified one direct causal relationship and one indirect causal relationship, and failed to determine the causal direction of one pair. Because all the effect variables were obtained by discretization at quantiles, they had natural orderings. Again, in all cases, the optimal orderings identified by COLP perfectly matched them.
Table Abalone Dataset. Correctly (incorrectly) identified causal direction marked by 7(X). For GRaSP, O
means a directed path was identified.
Cause (X)
Effect (Y)
COLP
HCR
ECI
GRaSP
Length
/
d
Sex
Diameter
/
Height
x
3.2.3 Tübingen Cause-Effect Pairs
This is a well-known causal benchmark dataset [Mooij et al. 2016 (version: 12/20/2017). We picked pair 52, 53, 54, 55, and 105 for testing, which rarely used in prior work because at least one of the variables in each pair is multivariate. We applied K-means to each multivariate variable with K == and used the cluster labels categorical variable, and discretized each univariate variable 5 evenly spaced quantiles.
The results are shown in Table 3
COLP was able correctly identify all 5 cause-effect pairs whereas HCR missed pair and ECI missed 2 pairs. The effect variables of Pairs and 105 have natural orderings, which matched the optimal orderings identified by COLP.
Table 3: Tübingen Cause-Effect Pairs. Correctly (incorrectly) identified causal direction is marked by / (X).
Pair
Cause (X)
Effect (Y)
COLP
HCR
ECT
air temperature
air temperature pressure at surface
pressure surface
52
at day 50
day 51
sea level pressure
sea level pressure relative humidity
relative humidity
wind speed global radiation
53
ozone concentration
d
x
temperature displacement
mpg acceleration
54
horsepower weight
55
temperature at locations
ozone concentration at 16 locations
X
105
grey values of 9 pixels
light intensity
3.2.4
Categorical Cause-Effect Pairs
The Tübingen Cause-Effect Pairs data are largely continuous and may not be the best benchmarks for categorical causal discovery. Hence, we created categorical causal discovery benchmark dataset using a similar approach as in Mooij et al. [2016) Specifically, we searched for appropriate datasets in R packages MASS and datasets for which the pairwise causal relationships should be obvious from the context (c.g., treatment assignment causes treatment effect), and at least one of the variables in each pair is categorical. For non-categorical variable, we discretized at evenly spaced quantiles. The resulting dataset contains 33 categorical cause-effect pairs and is available in the R package COLP.
The results are shown in Table Overall, COLP, HCR, and ECI were able to correctly identify 70%, 61 % and 52% causal-effect pairs, respectively. terms the ordering estimation, some results were interesting. For example, mentioned in Section 2.1 1 for the "MASS:: data, the ordering of shelf placement E (,,),3 was estimated to be < < 2, which matches the fact that middle shelf is the most popular, followed by the top shelf, and the bottom shelf is the

---

least popular. In fact, under the correct causal direction X - Y, COLP was better than ordinal and multinomial regressions in terms of both goodness of fit (via within-sample prediction) and out-of-sample prediction (via leave-one-out cross-validation).
Table 4: Categorical Cause-Effect Pairs. Correctly (incorrectly) identified causal direction is marked
by Vxx).
Source
Data
Cause (X)
Effect (Y)
COLP
HCR
ECI
MASS
anorexia
Treat
Prewt-Postwt
X
MASS
painters
School
Composition
X
MASS
painters
School
Drawing
x
7
MASS
painters
School
Colour
MASS
painters
School
Expression
7
/
MASS
birthwt
race
low
7
x
x
MASS
bacteria
trt
y
MASS
survey
Sex
Clap
7
x
7
MASS
survey
Sex
Fold
7
x
7
MASS
oats
B
MASS
oats
V
Y
MASS
oats
N
Y
X
MASS
crabs
sp*sex
FL
X
MASS
crabs
sp*sex
RW
7
x
MASS
crabs
spxsex
CL
X
MASS
crabs
spxsex
CW
MASS
crabs
sp
BD
/
/
MASS
fgl
type
RI
x
MASS
immer
Var
YI
MASS
immer
Var
Y2
x
MASS
immer
Loc
Y1
7
MASS
immer
Loc
Y2
X
MASS
minn38
sex
phs
X
x
MASS
minn38 fol
hs
7
MASS
minn38 fol
phs
X
MASS
UScereal
mfr
shelf
7
7
x
MASS
UScereal
mfr
vitamins
/
datasets
chickwts
feed
weight
x
datasets
InsectSprays
spray
count
7
/
/
datasets
npk
N*P*K
yield
1
datasets
PlantGrowth
group
weight
X
x
datasets
ToothGrowth
supp" dose
len
/
/
/
datasets
warpbreaks
wool*tension
breaks
x
4 Conclusion
There are a few limitations of the current work. First, our identifiability theory assumes no un- measured confounders. Although our empirical studies suggested that the proposed method was relatively robust to the presence of confounders, it would be interesting to theoretically investigate the identifiability under this scenario. Second, we have focused on bivariate causal discovery. Extending it to multivariate cases would broaden the applicability of the proposed method. Third, the categorical cause-effect pairs dataset can be expanded by surveying more publicly available data.

---

Acknowledgments and Disclosure of Funding
This research partially supported by NSF DMS-2112943,, NSF DMS-1918851, and NIH IR0IGM148974-01. We appreciate the constructive comments from anonymous reviewers as well as Spencer Compton and Murat Kocaoglu, which helped improve the paper.
References
Patrick Blöbaum, Dominik Janzing, Takashi Washio, Shohei Shimizu, and Bernhard Schölkopf. Cause-effect inference by comparing regression errors. In International Conference on Artificial Intelligence and Statistics, pages 900-909, 2018.
Ruichu Cai, Jie Qiao, Kun Zhang, Zhenjie Zhang. and Zhifeng Hao. Causal discovery from discrete data using hidden compact representation. Advances in Neural Information Processing Systems, 2018:2666, 2018.
Zhitang Chen, Kun Zhang, Laiwan Chan, and Bernhard Schölkopf. Causal discovery via reproducing kernel Hilbert space embeddings. Neural Compulation, 26(7): 148--1117, 2014.
Junsouk Choi, Robert Chapkin, and Yang Ni. Bayesian causal structural learning with zero-inflated
Poisson Bayesian networks. In Advances in Neural Information Processing Systems 33, 2020.
Spencer Compton, Murat Kocaoglu, Kristjan Greenewald, and Dmitriy Katz. Entropic causal inference: Identifiability and finite sample results. In Advances in Neural Information Processing Systems, volume 33, pages 14772-14782. Curran Associates, Inc., 2020.
Spencer Compton, Kristjan Greenewald, Dmitriy A Katz, and Murat Kocaoglu. Entropic causal inference: Graph identifiability. In International Conference on Machine Learning, pages 4311- 1- 4343. PMLR, 2022.
Daniel Bernandez-Lobate Pablo Morales-Mombiela, David Lopez-Paz, and Alberto Suarez. Non- linear causal inference using Gaussianity measures. The Journal of Machine Learning Research, 17(1):99-997,, 2016.
Patrik O Hoyer, Dominik Janzing, Joris M Mooij, Jonas Peters, and Berhhard Schölkopf. Nonlinear causal discovery with additive noise models. In Advances in Neural Information Processing Systems, pages 689-696, 2009.
Dominik Janzing, Joris Mooij. Kun Zhang, Jan Lemeire, Jakob Zscheischler, Povilas Daniušis, Bastian Steudel, and Bernhard Schölkopf. Information-geometiic approach to inferring causal directions. Artificial Intelligence, 182:1-31. 2012.
Wai-Yin Lam, Bryan Andrews, and Joseph Ramsey. Greedy relaxations of the sparsest permutation algorithm. The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Furui Liu and Laiwan Chan. Causal inference on discrete data via estimating distance correlations. Neural Computation, 28(5):801-81) 2016.
Alexander Marx and Jilles Vreeken. Telling cause from effect using MDL-based local and global regression. In 2017 IEEE International Conference on Data Mining (ICDM), pages 307-316. IEEE, 2017.
Joris M Mooij, Oliver Stegle, Dominik Janzing, Kun Zhang, and Bernhard Schölkopf. Probabilistic latent variable models for distinguishing between cause and effect. In Advances in Neural Information Processing Systems, pages 1687-1695, 2010.
Joris M Mooij, Jonas Peters, Dominik Janzing, Jakob Zscheischler, and Berhhard Schölkopf. Distin- guishing cause from effect using observational data: methods and benchmarks. The Journal of Machine Learning Research, 17(1):103311200 2016.
Warwick J Nash, Tracy L Sellers, Simon Talbot, Andrew J Cawthorn, and Wes B Ford, The population biology of abalone (haliotis species) in tasmania. i. blacklip abalone (h. rubra) from the north coast and the islands of bass strait. Technical report (Tasmania. Sea Fisheries Division); 48, 1994.
10

---

Yang Ni and Bani Mallick. Ordinal causal discovery. The Proceedings of Thirty-Eightt Conference on Uncertainty in Artificial Intelligence, 2022.
Gunwoong Park and Hyewon Park. Identifiability of generalized hypergeometric distribution (GHD) directed acyclic graphical models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 158-166, 2019.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Identifying cause and effect on discrete data using additive noise models. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pages 597-604, 2010.
Jie Qiao, Yiming Bai, Ruichu Cai, and Zhifeng Hao. Learning causal structures using hidden compact representation. Neurocomputing, 463:328-333, 2021.
Yoram Reich and Steven Fenves. Incremental learning for capturing design expertise. Technical Report: EDRC 12-34-89, Engineering Design Research Center, Carnegie Mellon University, Pittshurgh, PA, 1989.
Eleni Sgouritsa, Dominik Janzing, Philipp Hennig, and Bernhard Schölkopf. Inference of cause and effect with unsupervised inverse regression. In Artificial Intelligence and Statistics, pages 847-855, 2015.
Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-Gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7002:))2003320330 2006.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT press, 2000.
Joe Suzuki, Takanori Inazumi, Takashi Washio, and Shohei Shimizu. Identifiability of an integer mod- ular acyclic additive noise model and its causal structure discovery. arXiv preprint arXiv: 101.55540..5625. 2014.
Natasa Tagasovska, Valérie Chavez-Demoulin, and Thibault Vatter. Distinguishing cause from effect using quantiles: Bivariate quantile causal discovery. In International Conference Machine Learning, pages 9311-9322 PMLR, 2020.
Wenjuan Wei, Lu Feng, and Chunchen Liu. Mixed causal structure discovery with application to prescriptive pricing. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 5126-5134, 2018.
Kun Zhang and Aapo Hyvärinen. On the identifiability of the post-nonlinear causal model. In Proceedings of the Tienty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI '09, page 647-655, Arlington, Virginia, USA, 2009. AUAI Press. ISBN 9780974903958..

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section f
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] An R package is submitted as supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (c.g.. type of GPUs, internal cluster, cloud provider)? [No] The focus of this paper is identifiability and the computation is quite fast and straightforward.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "mK2PmzwT3Bw", "reviewer": "Reviewer_Q1zD", "summary": "The authors propose a method for cause-effect inference when the causal pair consists of two categorical variables. Essentially, the authors fit an ordinal regression model and see in which direction they can fit a more parsimonious model. The parsimony is motivated by the assumption that certain orderings of the input data fit better with the variables in the outcome data, even when there is no natural ordering in the data. That way, the authors can fit a so-called *COLP (classification with optimal label permutation)* model in which they search for the permutation of the inputs that leads to the best maximum likelihood fit.", "questions": "Which anti-causal model do you choose in Figure 1, if it is not a COLP-based causal model?\n\nIn Figure 2, have you considered adding some horizontal jitter so that COLP-Exhaustive is more visible (in Scenarios 1 and 3)? Since the accuracy is very similar, it is not easy to see that both are plotted together. \n\nIn Figure 3, why would error bars hinder clarity? It seems that the improvement in Kendall's Tau is significant enough to be visible. Why not make three figures, one for each scenario, since there is enough space available?\n\nIn Subsection 3.1.3, what is the strength of the confounder? I appreciate that the authors show robustness to violations of causal sufficiency, but I am rather surprised that the method performs very closely to how it performs in Scenario 1.\n\nIn Subsection 3.2.1, what does RR stand for? Rest and relaxation? Other variables could probably be explained in more detailed as well, but $\\hat{\\beta}_{RR}$ is mentioned to show that the ordering is consistent, so the acronym should be explained.", "limitations": "The authors do not discuss any potential negative societal impacts of their work, but it is difficult to foresee any for this particular task.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The method proposed is straightforward and appears sound. The experimental section is comprehensive and contains experiments on both simulated and real-world data. The results are convincing and suggest that the COLP-greedy approach performs sufficiently well for the chosen experiments relative to the computationally-prohibitive COLP-exhaustive method.\n\nIn terms of weaknesses, the COLP method relies on the assumption that some particular ordering in the categories makes more sense than other orderings. It is hard to gauge how frequently this assumption will hold in practice. Furthermore, one must assume no hidden confounders, which is an important limitation that the authors admit. The clarity of presentation could be improved (see below).\n\nDetailed comments:\n- p1 (page 1), l27 (line 27): \"the $Y$ admit\" $\\to$ '$Y$ admits' \n- p1, l31: I think you mean 'or' instead of \"and\".\n- p2, l39: \"... natural orderings. But ...\" $\\to$ '... natural orderings **, but** ...'\n- p2, l68: Why include $\\gamma_L$, unlike $\\gamma_0$, in the list of thresholds from line 65, if $\\gamma_L = \\infty$? Later on, it is no longer included (p3, l109).\n- p2, l75: At the end of the sentence there is a dangling left parenthesis.\n- p3, l85: \"contraint\" $\\to$ 'constraint'\n- p3, l108: Add 'the' before \"causal model\".\n- p3, l111 & l117: \"casual\" $\\to$ 'causal'\n- p3, l132: Add 'a' after \"such\".\n- p3, l138: \"does\" $\\to$ 'do'\n- p3, l141: \"confounder\" $\\to$ 'confounders'\n- p6, Figure 2 caption: \"COLP-Exhausitve\" $\\to$ 'COLP-Exhaustive'\n- p8, l233: \"pair\" $\\to$ 'pairs'", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jWO4U2_FYQs", "reviewer": "Reviewer_ettZ", "summary": "This paper proposed classification with the optimal label permutation (COLP) method for causal discovery from categorical data. The main idea is that the ordinal regression is identifiable given the correct permutation.", "questions": "See the weaknesses above.", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed COLP is able to discover the causal relationship from categorical data.\n- It shows that COLP is identifiable almost surely.\n\nWeaknesses:\n- This work can be seen as a direct increment of [1], and the novelty is somewhat limited.\n- This work heavy rely on the label permutation on ordinal regression, and thus it is necessary to conduct an ablation study that remove the label permutation to show the supremacy of COLP.\n- The proposed greedy algorithm for learning permutation seems inefficacy under the large categories, and it should show how the number of categories affects the performance and whether the learned permutation is correct. \n[1] Ni Y, Mallick B. Ordinal Causal Discovery[C]//The 38th Conference on Uncertainty in Artificial Intelligence. 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ob3uQK8sLz", "reviewer": "Reviewer_q4Dr", "summary": "This paper proposes a parametric way for causal discovery over categorical data, which is far less studied than continuous data. The proposed method is named \"classification with optimal label permutation (COLP)\". COLP is inspired by ordinal regression. While the latter only applies to variables with a natural ordering, COLP can extend to categorical variables without a natural ordering - in the sense of prediction response. The corresponding causal model finds an optimal permutation and COLP parameters to satisfy one causal direction, while the other anti-causal direction cannot be satisfied by any COLP model - as is illustrated in the identifiability proof. Technically, the paper uses simple MLE to estimate the optimal COLP model. Experiments with synthetic and real data demonstrate COLP's better performance than SOTAs.", "questions": "**1. What are the hidden assumptions?**\n\nIt's known that [1] for multinomial distribution or linear Gaussian SEMs, the causal graph can be identified up to its Markov equivalence class (intrinsically on data; no matter which method is used). Then, in this paper, for the causal direction between pairwise categorical data to be identified, there must be parametric assumptions on the data generating process. For example, in the person's choice of sports case, \nto predict $Y\\in$ {gymnastics, boxing, volleyball} based on one's strength or height $X$, actually here it relies on the fact that $X$ is ordinal categorical, or even continuous. Then,\n  - Could the authors please give a mathematical formulation of all the assumptions used in COLP?\n  - Are those assumptions stronger or weaker, compared to the existing work, e.g., ordinal regression and multinomial regression?\n  - Overall, are those assumptions testifiable from data (e.g., LiNGAM assumption is testifiable by checking scatter plots)? \n  - Specifically on the $X\\rightarrow Y$ case above with continuous $X$, can COLP be viewed as (or compared with) methods for mixed-type data (e.g., using degenerated/conditional Gaussian score).\n  - The meaningful order of $Y$ replies on $X$ (as a regressor), i.e., yields a dependence relationship. Then, if we go beyond the bivariate case to the multivariate case, will this also yield a dependence graph? How to find a root (i.e., with natural ordering) variable? How to ensure that there is no loop in the dependence graph?\n\n**2. The identifiability is poorly explained, and the results seem to be wrong (to me).**\n\nLet's start with the illustrative example in Figure 1. Authors indicate that a COLP-based causal model $M_0:X\\rightarrow Y$ is satisfied with specific parameters $\\omega = (0.25, 0.25, 0.5)$, $\\gamma = 1$, $\\beta=(1,-1,1)^\\intercal$, and $\\sigma([1,2,3])=[1,3,2]$. By the equation in line 106, we have the link function satisfying $F(-1)=0.16, F(0)=0.34, F(1)=0.84, F(2)=0.98$. Then,\n - Seems that the unpermuted $Y$ ($\\sigma([1,2,3])=[1,2,3]$) also satisfies a COLP model (with other parameters $\\omega, \\gamma, \\beta$ unchanged): just let $F$ satisfy $F(-1)=0.16, F(0)=0.66, F(1)=0.84, F(2)=0.86$.\n - In general, how does COLP deal with the non-unique permutations for COLP models as above?\n - The paper states that \"$M_1:Y\\rightarrow X$ is no longer in the class of COLP-based causal models\". But it seems that this is incorrect.\n   + Suppose we have $\\omega=(0.33,0.38,0.29)$, $\\gamma=1$, $\\beta=(-a,-b,-c)^\\intercal$.\n   + Yes there does not exist a COLP model for unpermuted $X$: just consider the first two columns ($Y=1,2$), we cannot have a CDF link function $F$ with $F(a)=0.12, F(a+1)=0.76, F(b)=0.33, F(b+1)=0.34$, since $F$ is monotonically increasing.\n   + But, e.g., for the permutation of $X$: $\\sigma([1,2,3])=[1,3,2]$, there exists $F$ s.t., $F(a)=0.12, F(a+1)=0.36, F(b)=0.33, F(b+1)=0.99, F(c)=0.29, F(c+1)=0.88$ -- i.e., there is a COLP model also for $M_1:Y\\rightarrow X$.\n - I tried some examples though. E.g, this is a joint table where $X\\rightarrow Y$ can follow a COLP model, but not $Y\\rightarrow X$ (verify in a similar way as above):\n| P(X,Y) |  X=1  |  X=2  |  X=3  |\n|:------:|:-----:|:-----:|:-----:|\n|   Y=1  | 0.147 | 0.081 | 0.110 |\n|   Y=2  | 0.144 | 0.097 | 0.096 |\n|   Y=3  | 0.080 | 0.092 | 0.152 |\n\n - And this is a joint table where neither $X\\rightarrow Y$ nor $Y\\rightarrow X$ can be represented by a COLP model:\n| P(X,Y) |  X=1  |  X=2  |  X=3  |\n|:------:|:-----:|:-----:|:-----:|\n|   Y=1  | 0.128 | 0.073 | 0.087 |\n|   Y=2  | 0.061 | 0.054 | 0.180 |\n|   Y=3  | 0.069 | 0.170 | 0.178 |\n\n - Overall I think, to check whether there exists a COLP model, it's to check for the conditional probability table, whether there exists a row permutation s.t., for the cumulated summed table along the row axis, the column-wise argsort indices are same for all rows (so that there exists a valid CDF monotonically increasing function to satisfy the same length (of threshold $\\gamma$ intervals)). See the code below:\n```python\ndef is_X_to_Y(XY_joint_table):\n    '''\n    :param XY_joint_table:\n        e.g. Figure 1 in the paper,\n        +--------+-------+-------+-------+\n        | P(X,Y) |  X=1  |  X=2  |  X=3  |\n        +--------+-------+-------+-------+\n        |   Y=1  | 0.040 | 0.210 | 0.080 |\n        +--------+-------+-------+-------+\n        |   Y=2  | 0.125 | 0.005 | 0.250 |\n        +--------+-------+-------+-------+\n        |   Y=3  | 0.085 | 0.035 | 0.170 |\n        +--------+-------+-------+-------+\n        where axis0 is Y and axis1 is X.\n    :return:\n        True if there exists a COLP model X->Y, otherwise False.\n    '''\n    P_Y_given_X = XY_joint_table / XY_joint_table.sum(axis=0)[None]\n    for row_perm in itertools.permutations(np.arange(P_Y_given_X.shape[0])):\n        permed_P_Y_given_X = P_Y_given_X[list(row_perm)]\n        permed_CDF_Y_given_X = np.cumsum(permed_P_Y_given_X, axis=0)\n        col_sorted_ids = np.argsort(permed_CDF_Y_given_X[:-1],axis=1)\n        if (col_sorted_ids == col_sorted_ids[0]).all():\n            return True\n    return False\n```\n\n - Then by the code above, I sampled 10000 random joint probability tables with both $X,Y$ of cardinality 3 (I just choose $\\alpha=1$ for the Dirichlet distribution without further considerations):\n```python\nboth_direction_cnt, one_direction_cnt, no_direction_cnt = 0, 0, 0\nfor _ in range(10000):\n       joint = np.random.dirichlet(np.ones(9), size=1).reshape((3, 3))\n       X_to_Y, Y_to_X = is_X_to_Y(joint), is_X_to_Y(joint.T)\n       if X_to_Y and Y_to_X: both_direction_cnt += 1\n       elif X_to_Y or Y_to_X: one_direction_cnt += 1\n       else: no_direction_cnt += 1\nprint(both_direction_cnt, one_direction_cnt, no_direction_cnt)\n```\nThe result is that: `7129` are unidentifiable (both directions can have a COLP model); `1059` are unidentifiable (both directions do not have a COLP model), and only `1812` are identifiable (one direction satisfies, and one does not).\n - And with the cardinalities going up, less can be satisfied by COLP model (as expected). E.g, for $5x5=25$ table, the counts are respectively `both_direction_cnt=16, one_direction_cnt=405, no_direction_cnt=9579`.\n- This definitely violates the proof of zero measurements (Theorem 1). So, did I understand correctly? Please correct me if anything is wrong.\n\n**3. Questions about experimental results on real data**\n - Instead of accuracy metric as of in simulation results, for experiments on real data, authors only listed several results on some specific edges (not all edges) and showed that COLP is correct on all of these edges. Then naturally I would doubt whether there is cherry-picking, only reporting edges where COLP is correct (and competitors incorrect). Could the authors please report how they choose the edges? And is there any other metric (over all edges/ whole graph, e.g., Table 4) for the real datasets?\n - What does it mean by \"out-of-sample prediction (via leave-one-out cross-validation)\"? COLP seems to be an unsupervised method. Could the authors please explain more on this?\n\n\n---\n[1] Christopher Meek. ‘Strong Completeness and Faithfulness in Bayesian Networks’. In: Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. UAI’95. Montréal, Qué, Canada: Morgan Kaufmann Publishers Inc., 1995, pp. 411–418", "limitations": "Overall, the authors have adequately addressed the limitations: 1) identifiability based on causal sufficiency, 2) extension to multivariate, and 3) more real data. I would expect more elaboration on the hidden assumptions over the data generating process.", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Pros\n  - **Intriguing intuition**: the illustrating example of predicting one's choice of sports based on their height/strength is intuitive: though generally categorical variables do not have natural orderings, they may be ordered in a meaningful way as responses in prediction.\n  - **Comprehensive experimental results**: authors assessed the performance of COLP with both synthetic and real-world datasets. On synthetic datasets, three scenarios are considered: small/big number of categories and pairs with hidden confounders. Four well-known real categorical data are evaluated, which shows COLP's better performance than HCR and CE.\n\n+ Cons\n  - The **assumption is not well clarified**. The proposed COLP can be viewed as a variation of ordinal-regression-based categorical causal discovery. Then what is exactly the parametric assumption on the data generation process behind COLP and ordinal regression, respectively? This paper does not give a mathematical formulation. See question 1 for details.\n  - The theoretical part on **identifiability is poorly explained**, and the basic **examples and results seem wrong (to me)**. See question 2 for details. Please correct me if I did not understand correctly and I'm willing to change my assessment.\n  - The **experimental results on real data is broad, but not deep enough**, and is thus not convincing. There is not a quantitive evaluation metric, but only cases studies on some specific edges. Also, there are some small issues about clarity. See question 3 for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CsCr_Q98Y1", "reviewer": "Reviewer_WFBs", "summary": "The authors propose a novel method to do pairwise orientation (and adjacency discovery?) for categorical variables with > 2 categories.", "questions": "* Could you include MEC methods in your analyses as well? This might require using more variables and selecting good methods, but it is possible.\n\n* Could the situation for identifiability with binary variables be made clear?\n\n* Could it be clarified whether COLP is able to detect the nonexistence of pairwise edges and is able to conclude \"undirected\" if in fact a direction should not be inferred?\n", "limitations": "I did not see societal impact addressed; nor do I see it as much of an issue for this method.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The idea is based on a sound principle.\n\n* The creation of a categorical pairwise causal dataset is a great idea. Hopefully others can try their hand at it.\n\n* The theory given for the COLP algorithm intuitively makes sense, as does the algorithm provided.\n\n* I wondered whether the \"natural orderings\" found by COLP corresponded to intuitively natural ordering, but there were comments int he experimental section to this effect, so thanks.\n\nWeaknesses:\n\n* A main weakness of this paper is that is simply discounts out of hand the Markov Equivalence Class (MEC) approach to causal discovery. In fact, it is not even mentioned in the paper so far as I can see, despite the fact that it has been a major methodology for many years now and is still actively studied. \n\nOut of curiosity, I loaded up one of the the Pittsburgh Bridges dataset studied here removed the first column, and ran the novel GRaSP algorithm (UAI 2022) on it with the BDeu score with _all 12 variables_, and two of the ground truth edges identified by the authors were correctly oriented, with paths existing for the other ground truth edges. (It seems the authors only studied 4 of the 12 variables, suggesting that a latent variable algorithm may have been necessary.) So that strategy should not be discounted. \n\nThere is in fact a strategy in literature of using an MEC strategy to find and orient as many edges as possible and then to use a pairwise strategy to orient the remaining edges. Again, this should not be discounted, and \"causal discovery\" should not be taken to mean just pairwise (or \"bivariate\"--author's term) causal discovery.\n\nThere may be a question as to how the various methods (MEC methods included) do at detecting the directionality of the various edges. This is a sensitivity question and can be directly addressed.\n\nI'm also very familiar with the Abalone dataset, which is mixed continuous/discrete. Again, loading it up and running the GRasP algorithm on it with the mixed Conditional Gaussian score renders SEX as exogenous with respect to all of the other variables, which it should be, as female abalone are larger in size systematically than male abalone. Again, this is an MEC approach.\n\n* It was gratifying to see COLP results for even some of the Tubingen pairwise examples as well, though #54 is of course an 8-variable mixed continuous/discrete example (\"auto-mpg\") from the UCI Repository that can be handled using MEC method; I tried GRaSP on it as well with the Conditional Gaussian score, and it gets it right.\n\n* In Section 3.1, two competing categorical discovery methods are mentioned, HCR and CE; why are these not mentioned in the introduction so help situate the COLP algorithm immediately in the literature?\n\n* The word \"identifiable\" needs to be clarified here, as the MEC approach would take X--Y to be identifiable under certain assumptions, as meaning that there is either an edge X->Y or and edge X<-Y. It should be particularly mentioned, I think, that identifiability in this context means correctly identifying which of X->Y or X<-Y is correct. \n\n* Also, it is not clear to me based on what is said what identifiability extends to the binary case; if not, this should be stated up front.\n\n* I do wonder if the COLP method will correctly infer that an edge cannot be oriented pairwise if in fact it cannot, or if it will tend to guess one direction or the other?\n\n* In Figure 2, I conclude that COLP should not be attempted with sample sizes less than 400, which is good to know. I find it interesting that 5 is considered a \"small\" number of categories--this is not the world I live in.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept