Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

In 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).

Detailed comments:
- p1 (page 1), l27 (line 27): "the $Y$ admit" $\to$ '$Y$ admits' 
- p1, l31: I think you mean 'or' instead of "and".
- p2, l39: "... natural orderings. But ..." $\to$ '... natural orderings **, but** ...'
- 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).
- p2, l75: At the end of the sentence there is a dangling left parenthesis.
- p3, l85: "contraint" $\to$ 'constraint'
- p3, l108: Add 'the' before "causal model".
- p3, l111 & l117: "casual" $\to$ 'causal'
- p3, l132: Add 'a' after "such".
- p3, l138: "does" $\to$ 'do'
- p3, l141: "confounder" $\to$ 'confounders'
- p6, Figure 2 caption: "COLP-Exhausitve" $\to$ 'COLP-Exhaustive'
- p8, l233: "pair" $\to$ 'pairs'
questions: Which anti-causal model do you choose in Figure 1, if it is not a COLP-based causal model?

In 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. 

In 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?

In 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.

In 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The proposed COLP is able to discover the causal relationship from categorical data.
- It shows that COLP is identifiable almost surely.

Weaknesses:
- This work can be seen as a direct increment of [1], and the novelty is somewhat limited.
- 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.
- 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. 
[1] Ni Y, Mallick B. Ordinal Causal Discovery[C]//The 38th Conference on Uncertainty in Artificial Intelligence. 2022.
questions: See the weaknesses above.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors propose a novel method to do pairwise orientation (and adjacency discovery?) for categorical variables with > 2 categories.
strengths_and_weaknesses: Strengths:

* The idea is based on a sound principle.

* The creation of a categorical pairwise causal dataset is a great idea. Hopefully others can try their hand at it.

* The theory given for the COLP algorithm intuitively makes sense, as does the algorithm provided.

* 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.

Weaknesses:

* 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. 

Out 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. 

There 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.

There 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.

I'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.

* 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.

* 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?

* 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. 

* 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.

* 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?

* 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.

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.

* Could the situation for identifiability with binary variables be made clear?

* 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?

limitations: I did not see societal impact addressed; nor do I see it as much of an issue for this method.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: + Pros
  - **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.
  - **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.

+ Cons
  - 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.
  - 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.
  - 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.
questions: **1. What are the hidden assumptions?**

It'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, 
to 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,
  - Could the authors please give a mathematical formulation of all the assumptions used in COLP?
  - Are those assumptions stronger or weaker, compared to the existing work, e.g., ordinal regression and multinomial regression?
  - Overall, are those assumptions testifiable from data (e.g., LiNGAM assumption is testifiable by checking scatter plots)? 
  - 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).
  - 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?

**2. The identifiability is poorly explained, and the results seem to be wrong (to me).**

Let'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,
 - 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$.
 - In general, how does COLP deal with the non-unique permutations for COLP models as above?
 - 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.
   + Suppose we have $\omega=(0.33,0.38,0.29)$, $\gamma=1$, $\beta=(-a,-b,-c)^\intercal$.
   + 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.
   + 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$.
 - 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):
| P(X,Y) |  X=1  |  X=2  |  X=3  |
|:------:|:-----:|:-----:|:-----:|
|   Y=1  | 0.147 | 0.081 | 0.110 |
|   Y=2  | 0.144 | 0.097 | 0.096 |
|   Y=3  | 0.080 | 0.092 | 0.152 |

 - And this is a joint table where neither $X\rightarrow Y$ nor $Y\rightarrow X$ can be represented by a COLP model:
| P(X,Y) |  X=1  |  X=2  |  X=3  |
|:------:|:-----:|:-----:|:-----:|
|   Y=1  | 0.128 | 0.073 | 0.087 |
|   Y=2  | 0.061 | 0.054 | 0.180 |
|   Y=3  | 0.069 | 0.170 | 0.178 |

 - 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:
```python
def is_X_to_Y(XY_joint_table):
    '''
    :param XY_joint_table:
        e.g. Figure 1 in the paper,
        +--------+-------+-------+-------+
        | P(X,Y) |  X=1  |  X=2  |  X=3  |
        +--------+-------+-------+-------+
        |   Y=1  | 0.040 | 0.210 | 0.080 |
        +--------+-------+-------+-------+
        |   Y=2  | 0.125 | 0.005 | 0.250 |
        +--------+-------+-------+-------+
        |   Y=3  | 0.085 | 0.035 | 0.170 |
        +--------+-------+-------+-------+
        where axis0 is Y and axis1 is X.
    :return:
        True if there exists a COLP model X->Y, otherwise False.
    '''
    P_Y_given_X = XY_joint_table / XY_joint_table.sum(axis=0)[None]
    for row_perm in itertools.permutations(np.arange(P_Y_given_X.shape[0])):
        permed_P_Y_given_X = P_Y_given_X[list(row_perm)]
        permed_CDF_Y_given_X = np.cumsum(permed_P_Y_given_X, axis=0)
        col_sorted_ids = np.argsort(permed_CDF_Y_given_X[:-1],axis=1)
        if (col_sorted_ids == col_sorted_ids[0]).all():
            return True
    return False
```

 - 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):
```python
both_direction_cnt, one_direction_cnt, no_direction_cnt = 0, 0, 0
for _ in range(10000):
       joint = np.random.dirichlet(np.ones(9), size=1).reshape((3, 3))
       X_to_Y, Y_to_X = is_X_to_Y(joint), is_X_to_Y(joint.T)
       if X_to_Y and Y_to_X: both_direction_cnt += 1
       elif X_to_Y or Y_to_X: one_direction_cnt += 1
       else: no_direction_cnt += 1
print(both_direction_cnt, one_direction_cnt, no_direction_cnt)
```
The 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).
 - 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`.
- This definitely violates the proof of zero measurements (Theorem 1). So, did I understand correctly? Please correct me if anything is wrong.

**3. Questions about experimental results on real data**
 - 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?
 - 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?


---
[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.
review_title: null

Meta-review: metareview: All reviewers are convinced by the scientific soundness and evaluation results about this paper. 
The reviewers had some concerns regarding clarity and evaluation but in general liked 
various aspects of the paper. The authors did a good job of addressing the reviewers' concerns 
so acceptance is recommended.

confidence: Certain
Decision: Accept