Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Summary

The paper develops several useful lower and upper bounds on the rank of DAGs — specifically minimum and maximum rank of all weighted matrices that induce the same DAG — in terms of various graphical properties like head-tail vertex cover, number of non-root and non-leaf vertices. The paper also bounds the rank of DAG in terms of the rank of its skeleton and moral graph. The paper proposes learning low-rank linear or non-linear structural equation models (SEMs) by adding simple norm constraints or matrix factorization to existing SEM learning methods. Through experiments on synthetic and real world data the authors demonstrate that when the underlying SEM is low-rank, exploiting this low-rank assumption in the learning process can lead to better performance. The authors also demonstrate that the rank can be estimated using the obtained bounds from a validation set.

# Strengths

1. The main contribution of the paper is a strong justification for learning SEMs under a low-rank assumption by showing that graphs with many hubs are low-rank. Existing theoretical results for learning SEMs show a polynomial dependence of the sample complexity on the maximum degree of the true SEM. Therefore, learning SEMs subject to rank constraints rather than sparsity constraints can be useful for graphs with hubs.
2. The bounds on the rank of DAGs are generally useful beyond learning SEMs.

# Weakness

1. The paper does not propose any novel algorithms for learning low-rank DAGs, other than merely augmenting existing methods with nuclear norm constraint or using matrix factorization.
2. The method for estimating the rank from the validation set is crude and computationally expensive.

# Questions to address in rebuttal

1. In Figure 2, is degree (x-axis) the maximum degree of a node graphs ?
2. Figure 2 shows that the rank increases with the degree and that the rank is always larger than the degree. Therefore, even for graphs with hubs learning SEMs subject to sparsity constraints might still give better results than learning SEMs subject to rank constraints?
3. More details are needed on how the rank is estimated from the validation set with a complete algorithm.

# Post-rebuttal comments
Hello everyone,

I have read the author's response and I am leaning towards rejection. The paper can be divided into two halves. The first half where the authors obtain bounds on ranks of DAGs is the main contribution of the paper and is clearly interesting. The second half of the paper tries to shoehorn these bounds into an algorithm for learning causal DAGs from observational data which is disappointing and is clearly below standard for the following reasons:

1. The bounds depend on the underlying DAG which is unknown and therefore cannot be estimated from samples. Therefore the authors propose using "structural priors" to obtain these bounds. The authors don't mention where they get these structural priors from. Furthermore the bounds are only useful to restrict the hyper-parameter search space in the matrix factorization approach which is applicable to linear SEMs. These bounds can only be used "qualitatively" to guide selection of regularization penalty in the nuclear norm approach which is necessary for non-linear SEM methods.

2. The theoretical results would still be useful if the authors could adequately demonstrate that for certain family of graphs the maximum degree can be high while the rank can be low therefore learning DAGs subject to sparsity constraints (whose sample complexity depend on the maximum degree) can perform worse than learning DAGs with rank constraints. However, this is not clear since in experiments the authors only show the SHD as a function of "average degree" and not "maximum degree". Figure 2 again compares rank against average degree and not maximum degree.

3. The experiments are only performed in the low-dimensional regime at a fixed sample size (3000 samples and 300 nodes).


review_title: Good justification for learning low-rank SEMs

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper attempts to exploit the low-rankness of the adjacency matrix of the DAG in Bayesian network structure learning. The overall framework is similar to NOTEARS, except that the adjacency matrix W is decomposed into low rank components W = UV'. To justify the approach, the paper also includes lower and upper bounds of the rank of DAGs, albeit mostly theoretical and not applicable to real experiments. 

The paper is very solid in presenting mathematical facts and detailed algorithms. However, my main concern is about the fact that the algorithm requires knowledge (or guess) about the rank. In fact, the experiments in Section 5 already uses the ground truth rank information in NOTEARS-low-rank. Algorithm 1 is a great resource to be shared in the community, however in principal it shouldn't be needed to perform the experiments in Section 5. If one can gain accuracy benefit even without knowing the true rank, paying extra runtime cost is acceptable (Table 1). 

There are also many works on combining low-rankness with sparsity, which I suggest the authors to consider as future steps.

Update:
The authors have explained the issue raised in the review. It's not ideal that the algorithm requires the knowledge of rank beforehand, but it's okay if this point is clearly communicated in the paper. I would keep my current score. 
review_title: review

final_score: rating: 5: Marginally below acceptance threshold
review_content: # Review
## Summary of the paper and the review
- Paper summary: The paper explores the possibility of exploiting the potential low-rank nature of the underlying causal graph when conducting causal structure learning. Building on the recent gradient-based methods in (causal) DAG selection, they describe ways of integrating this assumption into the algorithms for existing gradient-based methods that assume linear or non-linear structural equation models (SEMs). They also provide some upper and lower bounds to the graph rank given the knowledge of certain structural priors. They test their proposal by augmenting two existing gradient-based methods and comparing its performance to the originals and other methods in simulated data.

- Review summary: The authors examine an intriguing and timely phenomenon, and provide some engaging arguments and results. However the study has some problems in its argumentation and experimentation. I have listed the perceived strengths and weaknesses of the paper below, including my questions for further clarification. I am looking forward to authors' improvements and responses regarding these issues.

## Strengths of the study
- The field of causal discovery can be considered as much a discussion regarding the nature of causality and how it manifests itself in observed joint distributions as it is a discussion regarding specific methods. I believe that it is very important that this work investigates the properties arising from the nature of the underlying distributions and how this should relate to the models and algorithms.
- The authors discuss the structure of causal-DAGs in relation to widely observed complex network structures such as scale-free networks. Although the connections they put forth are not always very clear (see below), I believe that discussing the nature of causal structures in the real world is an important direction, since causal discovery inevitably requires certain structural priors (e.g. independent causal mechanisms).
- Gradient-based DAG discovery methods constitute a promising direction towards causal structure discovery, especially in the presence of a large number of variables. The authors propose a method that can potentially improve any such method with relative ease.
- The modification the authors suggest comes with acceptable computational cost. Considering an extensive potential hyperparameter search, this cost is not negligible, yet it can still be said that it only adds a scaling factor to the complexity.
- Their method can be applied to both linear and nonlinear SEM's. Although the conceptual interpretations in the two case do not always translate, this is more due to the differing nature of the optimization problem in the two cases.
- The authors provide lower and upper bounds for the rank estimations of the causal systems given the existence of certain structural priors.
- The authors conduct simulated experiments where they vary a number of experimental conditions.
- The paper is well-written.

## Weaknesses of the study
### The claimed ubiquity of low-rank structure in causal systems: 
- The authors methods aim to exploit underlying low-rankness in the (adjacency matrix of the) underlying causal graphs. When arguing when real life causal systems are likely to be low rank, the authors invoke the prevalence of scale-free networks in real life. This argument is confusing since the observation of scale-free networks are frequently made in relational contexts where a rich-get-richer phenomena are frequently assumed to drive the scale-free property (e.g. a popular social media personality becoming more and more connected as opposed to a typical user). 
    - I fail to see why we would also see this in a causal-DAG setting as well, why would we have a causal hub? The authors write that: "It is observed that many real-world networks are scale-free, and some of them may be viewed as causal networks" - the authors could at least present some examples from the literature (in addition to the Pathfinder and arth150 data they cite) as well as more reasoning to make a more persuasive case. 
- This might have been less of an issue if the authors showed that low-rank assumption would benefit performance even in the case of high rank causal networks, but their results do not provide strong arguments to that effect (Appendix D.1).
- However, though being a weak point in their argumentation, this does not rule out the potential benefits of their methods, since the fact that the low-rankness assumption does not hold can be established in the cross-validation phase of a study using their method. 

### Upper and lower bounds on the rank of the adjacency matrix
- The paper devotes a whole section to extracting lower and upper bounds from prior knowledge regarding the structure of the graph, however provide little as to how we would realistically have access to such information. Almost none of the structural information required by the theorems seem to be easily accessible enough. The authors mention that "we usually have access to some structural information" but do not go into detail.
- Even when we have some structural information, it is not always clear how this information can be used in constraining the search space when this information is anything less than the knowledge of the causal structure itself. For example, even if we knew that our causal network had a number of causal hubs and thus is likely to be scale-free (which we perhaps could in some cases), it still is not clear how this knowledge could be directly used to obtain upper bounds. The relation is even more unclear for the nonlinear case since there is no direct way of relating $\hat{r}$ and $\lambda$.
- This might not have been as big an issue if this was not a section supporting a central claim in an application oriented paper - indeed, the theorems are presented as guidelines to constrain the search space for the estimated rank of the adjacency matrix, so more discussion and demonstration of their practical use is naturally sought.
- I believe that the authors could do two things:
    - They could show how the prior information required in Section 4 can actually plausibly be known beforehand in realistic scenarios, and maybe show example(s) of this in one or more of their applications (unlike in Section 5.3 where the prior information is assumed to be known).
    - Or they could make it clear that these are, though potentially useful as is or after contribution by other research, mostly theoretical demonstrations, and as of yet, their method would likely require extensive hyperparameter search as to the rank of the decomposition or the nuclear norm coefficient. This could possibly require them reevaluate their emphasis on these theoretical findings when introducing their research.

### Experiments
- Given the above concerns, the experiments take on more importance in demonstrating the utility of the methods proposed. Though the experiments have some important findings, a stronger experiments section would allow the authors to make a stronger claim and base their argument more empirically. At least _some_ additional experiments should be feasible given the running times of the algorithms provided in the Appendix.
- Given that it is not clear why causal networks would be both low rank and dense, and given that the prior information to constrain the search space for the rank are not always accessible, I believe that a comparison with sparsity-inducing regularizers such as $\ell_1$ or $\ell_2$-regularizers  would be beneficial, with a correspondingly extensive hyperparameter search so that empirical superiority of the authors' method over others could be empirically established (This has only been conducted in Section 5.5, see below regarding these findings). Given that both would require extensive parameter search, for a practitioner it might not matter whether their regularizer is sparsity or low-rank-decomposition inducing.
- The authors conducted experiments by applying their methods to modify NOTEARS and GraN-DAG. In the absence of application of their modification to other methods, justification for their method choice and why similar improvements should be expected for others as well would be helpful if provided. 
- Additional experiments when the true rank goes beyond $d/2$ (for both linear and nonlinear SEMs) would be beneficial in understanding the behavior of the given method in such cases. 
    - Also, this would demonstrate a potential contrast between the two methods: in the nonlinear case the cross-validation could produce a very small $\lambda$ to practically disregard the low-rank assumption. However in the linear case, e.g. setting $\hat{r} = r$ would lead to full rank assumption but would lead to $2d^2$ parameters, potentially leading to worse results than the original algorithm both in terms of performance and computation time. 
    - In the cases where $d/2 \ll r$, could score comparison e.g. with an unfactorized NOTEARS method lead to the correct choice (that is, full-rank NOTEARS)?
- Is there a specific reason for the absence of results with alternative $k$'s and with ICA-LiNGAM in Linear SEM experiments in scale-free networks in Section 5.2? If not, the inclusion of these would also be illustrative, especially given the latter's comptetive performance in previous experiments.
- Given the centrality of scale-free graphs in their argumentation, is there a specific reason for the lack of nonlinear-SEM experiments with scale-free graphs?
- Section 5.3: As noted before, it might be hard in many cases to provide realistic lower and upper bounds for the rank values. This might require an extensive search for $\hat{r}$ and $\lambda$. Given that the method requires a potentially large parameter search, its effect to general algorithm time complexity must also be mentioned, e.g. its runtime being at least 10x that of the base algorithm. However, I believe that this extra computation cost could be acceptable for increase in structure discovery accuracy.
- The results presented in Figure 7 seem to include very wide interquartile ranges: are the differences between different methods/hyperparameters significant? 
    - Also in the description of this experiment, the authors note that the results show the "utility of the low-rank assumption" when the rank is not as low as assumed, but the results show almost equal results, and given that the assumed rank is not much lower than the real rank, I cannot see how this result supports their conclusions, especially given that this is conclusion is presented in the abstract.

## Other comments
- In Figures 2, 3, and 6 the horizontal axis reads "Degree" and the corresponding text mentions "graph degree", in Sections 4.3 and 5.1 . The authors must have meant average (in + out) degree as they did in Section 5.2 or Appendix C.1. I believe the paper would benefit from this being explicit everywhere. In Appendix A the authors seem to equate "graph degree" with total edges in the graph, but they must mean the average number of edges per node in the graph, so that it is consistent with the rest of the paper.
- In Figure 2a, is average NOTEARS (w/o outliers) performance non-existent in the figure or follow exactly the same trajectory as NOTEARS? 
- At Pg. 6 in Experiments section the authors might have wanted to cite (Zheng et al. 2018) for the algorithm NOTEARS.
- Figure 5 would benefit from adding the NOTEARS result from the Figure 3.
- Is there a specific reason for authors preferring ICA-LiNGAM over the following DirectLiNGAM?
- Parameter search spaces: In this case $\hat{r}$ would have to be searched for in $[1, d/2]$ (vs. the original algorithm with no low-rank assumption, see above), however it is unclear what the search space for $\lambda$ should be.  Also the authors would benefit from suggesting a search strategy for such a case.
- As a future work, the research could benefit from comparing the inductive bias of the current method to the literature on structure priors [1] or parameter priors affecting model selection through marginal likelihood [2] in DAGs. 

## References
1. Eggeling, Ralf, Jussi Viinikka, Aleksis Vuoksenmaa, and Mikko Koivisto. 2019. “On Structure Priors for Learning Bayesian Networks.” In _The 22nd International Conference on Artificial Intelligence and Statistics_, 1687–95. [http://proceedings.mlr.press/v89/eggeling19a.html](http://proceedings.mlr.press/v89/eggeling19a.html).
2. Silander, Tomi, Petri Kontkanen, and Petri Myllymaki. 2007. “On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter.” in _Proceedings of the Twenty Third Conference on Uncertainty in Artificial Intelligence_.
review_title: An engaging paper in need of improvement

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:
 
The paper provides a new approch for learning a (possibly densely-connced) low-rank DAG models in the high dimensional settings. In particular, this paper provides how to exploit the property of the low-rank for recovering a underlying causal structure. Futher shown is that under what circumstance the low-rank assumption holds and heuristically confirms that thgrough simulation settings. Lastly, the proposed approach is compared against the state-of-the-art DAG learning algorithms that requirs the assumption of a sparse graph.

##########################################################################

Reasons for score: 

 
Overall, I vote for accepting. This paper is well-written and delivers its main contribution really well. Futhermore it well summarizes the prior works on learning a causal graph. In addition, the main idea of recovering a graph under low-rank is novel. 
However, my major concern is about the simulations of the paper although I acknolwedge that most of relevant papers exploit a similar settings. It would be better to emphasize that the proposed algorithm attempts to learn a complete partial DAG, not a DAG. Although some of related paper fasely asserts that their approches recovers a DAG using conditional independence relationships or score function, I hope this paper clarifies this point.  

 
##########################################################################Pros: 
Pros:
 
1. The paper solve a very important problem of causal inference. It seems to be practical and novel. 
 
2. The paper is really clear and convincing. 
 
##########################################################################

Cons: 
One important comment from my side is that the way in which you simulate your models is severely biased. What I always do when I simulate models (and I think others should do something similar), is rescale edge weights for each
node such that if all parents have values with a standard-normal distribution, then the value of the node itself will also have a standard-normal distribution (assuming Gaussian additive noise). In this way one avoids that the variance of the variables blows up (or converges to 0) as one adds more and more nodes to the graph. Therefore, assuming a standard-normal error distribution (or error variance is large) is impractical.  

Furthermore, in the densely-connected graph settings, it must be really careful to determine the range of edge weights; otherwise, the variance of the variables are again blowing up. Hence, in some points, the targeted graph is unrealistic in large-scale settings (d is large). Nevertheless, as an emerging field of learning DAG models in polynomial time with complete search, it should be accepted. However, for a better representation and fair comparison, it would be better to change simulation settings.  

Lastly, this paper does not explain a complete partial DAG that the proposed method is actually finds. In principle, there might be plenty of solutions for the considered optimization problem. Hence this paper would be clearer for new researcher in DAG model learning if it emphasizes CPDAG or PDAG. 

##### Update ######
Although it is responded that the simulation setting used in the paper does cause blowing up samples or marginal variance, it is in general impossible or the setting assumes too sparse case where considered graphs are almost empty. In addition, as you mentioned, I also ackowledge that it is a widely-used setting; however, there are a lot of papers that are rejected because of the unfair simulation setting. I like the main idea of the paper a lot, and hence, I hope the authors set the simulation setting more carefully. 

Furthermore, it is really frustaring answer that the authors consider the only case where graph is uniquely idenfiable from the pure observations. As you know that is really rare when the number of nodes is large (p > 50). 
review_title: On Low Rank Directed Acyclic Graphs and Causal Structure Learning

Meta-review: This paper studies the low-rank properties of DAG models, and illustrates through proof-of-concept how low-rank-ness can be exploited in structure learning of DAGs. After a lengthy discussion amongst the reviewers, it became clear that although there are some interesting ideas here, there is not enough enthusiasm for this work in its current form. The results in Section 4 connecting rank to structural properties are interesting, but the reviewers were concerned by the lack of precise statements connecting these results to known ensembles such as scale-free graphs (even though the authors discuss some heuristic connections). In the end, despite considerable enthusiasm regarding these ideas and the importance of the problem studied, there remained too many concerns that require a major revision before acceptance.
Decision: Reject