Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Authors study the problem of learning the causal ordering and union support of DAGs from K linear SEMs. Authors propose a regularized joint estimator and show that this joint estimation enjoys a better sample complexity than single separate estimations. Moreover, guarantees for causal order and union support recovery are provided. For experiments, authors propose a continuous optimization problem that outputs the same causal order and union support than the joint estimator.
main_review: Here I present my review along the axes from the NeurIPS reviewing guidelines:

**Originality**

- Are the tasks or methods new? 
  - Yes. Authors study the problem of multitask learning of causal ordering which has been previously unexplored to the best of my knowledge.

- Is the work a novel combination of well-known techniques?
  - It is motivated by existing methods for multitask learning in the context of Markov random fields.

- Is it clear how this work differs from previous contributions? 
  - Yes. The setting itself is different from existing ones.

- Is related work adequately cited?
  - Yes. I think the work can benefit from referencing additional works. See below.


**Quality** 

- Is the submission technically sound? 
  - Yes. Proofs seem sound although I have not checked in full detail.

- Are claims well supported (e.g., by theoretical analysis or experimental results)? 
  - Yes. Proos are provided in the appendix. Empirical validation is provided for synthetic and real-world data.

- Are the methods used appropriate? 
  - Yes. The theoretical analyses use tools from optimization, linear algebra and concentration inequalities.

- Is this a complete piece of work or work in progress? 
  - Complete work.

- Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?
  - Discussions on the limitations of the presented approach can be beneficial.


**Clarity** 

- Is the submission clearly written? 
  - Yes.  

- Is it well organized? 
  - Yes. I was able to follow the main contributions without issues.

- Does it adequately inform the reader? 
  - Yes. Experimental details are provided in the appendix. The work is reproducible.


**Significance** 

- Are the results important? 
  - Yes. I think the topic is of interest to the graphical models community.

- Are others (researchers or practitioners) likely to use the ideas or build on them? 
  - Probably yes. I think the method proposed is an interesting direction to the setting under study.

- Does the submission address a difficult task in a better way than previous work? 
  - The work can be considered as a first set of results for multitask DAG learning.

- Does it advance the state of the art in a demonstrable way? 
  - Yes.

# Questions / Comments

1. I believe the work might benefit from a discussion section on the limitations of the results. For instance, Condition 3.3 (Bounded spectrum) might be an assumption that will not work for the high-dimensional case. In such scenario, due to n << p, there will be zero eigenvalues and the condition will not hold. Can authors comment on this?

2. The statement of Theorem 3.2. has been updated in the appendix, where authors claim that the appendix version is better than the one in the main paper. I am not sure if one is allowed to update this much a relevant part of the contributions, which is a major concern for me.

3. I think the paper can benefit from referencing works that also have a "direct" or "joint" goal instead of separate estimations. For instance:

    * In undirected networks: "Learning Shared Subgraphs in Ising Model Pairs" by Varici et al.
    * In linear SEMs: "Direct Learning with Guarantees of the Difference DAG Between Structural Equation Models" by Ghoshal et al.

  In both works above, there is also evidence of the advantages of a joint objective instead of performing separate estimations.

Typos:
* L51: p was not introduced.
* L245: Appendix F not G.

---
I thank the authors for their response. After reading other reviews and responses, I feel more positive about the paper and will increase my score to 7. I think that the paper could benefit by adding discussions on some points brought by the reviewers.

limitations_and_societal_impact: I think the limitations can be stated more explicitly in a separate section or paragraph.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a multi-task DAG learning under equal variance and Gaussian assumptions. Consistency results are provided and new algorithm is proposed to solve the formulation. Empirically, results are shown to be consistent with the theoretical analysis. 
main_review: Strength:

Recovery main results are serious work and appreciated.

Formulation of objective is novel

Weakness:

Strong assumptions on equal variance and Gaussian, although I understand the necessity for the theoretical analysis. 
 
Empirical evaluation is very weak. 
 

Comments:
- L51: it is not clear on what cardinality p is. 
- The model and method only work with Gaussian data, so the current title and introduction is somewhat misleading. Authors should make it clear that the model under consideration is only Gaussian DAG. 
- Equal variance and Gaussian assumptions: they are pretty strong assumption in the context of DAG identification and learning. Such a restricted space may limit its practical values. 
- causal order recovery theoretical analysis is thorough (although I did not check the proof details)
- Typical Gaussian network structures are learned via precision matrices. It seems possible that these precision matrices can help learning the DAG, e.g., serve as an skeleton of the DAG learning. Have authors considered this aspect?
- "the optimal solution must be an element in the discrete space Tp": would be good to have a formal statement on this.
- Algorithm 1 uses a min-max formulation and solved slightly different from original NOTEAR. Can authors discuss the advantages of this method?
- There seem no baseline methods for comparison.  This is a major concern. Why are [27][28] not compared?
- Gene regulatory network: it seems K = 1, n = 1000 has a better TPR: 0.47 and better SHD.  The results are therefore not very convincing for the proposed approach. What about cases with K > 1 and n = 1k? 
limitations_and_societal_impact: Did not find such a section.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers structure discovery of multiple but related DAGs in the sense that they share a common causal order. Authors propose an l1/l2-regularized MLE for multiple linear Gaussian models and design a continuous optimization method to obtain the estimates. Sample complexity analysis are also provided regarding causal order and union support recovery, which is interesting and novel. Experiments also validate the theoretical finding and the effectiveness of joint estimation. The paper is generally well-written, though some details seem missing in the experiment part.
main_review: ### Pros:

- A quantitative theoretic analysis of sample complexity regarding causal order and union support recovery, which is interesting and novel.
- An efficient algorithm to estimate the graph.
- Paper is generally very well-written.

### Cons:

Perhaps the most major issue to me is the setting of the problem. 
-	Authors consider linear-Gaussian models where all the noise variances are identical, in particular, are set to be 1 among all datasets. The consideration for this choice is from identifiability. However, it is believed (at least I believe) that the condition of identical noise variances is quite restricted in practice, and it is not testable from observations. Consequently, the proposed theory and algorithm may have little use in practice.
-	Authors are encouraged to also consider non-identifiable case. In this case, it might be beneficial to reduce some indeterminacies of the edges in Markov equivalence class, since you have some different but related DAGs?
-	While it is claimed the analysis could easily extend to a more general case where the noise variances are different across datasets, it is not clear how they would affect the structure recovery result. In particular, if a dataset has a small very noise variance while another has a large one, then is the result affected?
-	What if the DAGs do not share the same causal order but can have a very few violations? Can the proposed algorithm return any guaranteed results?

Other issues in the experiment part:
-	The paper is well-written in other parts, but this section seem to omit some import details: 1) running time is not reported. 2) since you have multiple DAGs, it is not clear what DAGs are counted in calculating the metrics (FDR, SHD); are they the average? or simply the result regarding the causal order? 3) standard deviations are not provided.
-	Import baselines are missing: for linear Gaussian models with equal noise variances, a well known method is to check the marginal variances of the variables; the largest one would be the source node; for other variables, apply linear regression with the previous variable and obtain residuals; again check the marginal variances of these residuals and follow the same steps; one would then obtain a causal order. How does this procedure compare with the proposed method, when, e.g., in the second experiment that a single dataset can have a number of samples?
-	It would be also beneficial to consider some more settings: different graph structures and densities; different sample numbers across datasets.


**update after reading authors' response** 

I appreciate authors' response which clearly extends the practical use of this work. I have decided to increase my score to 6 (tentatively), and I am also waiting for other reviewers' opinions on the pratical usage to see if it is possible to further increase the evaluation.

Two followed questions: 
1. Even without identifiability of the unique graph, how about thinking about the MEC? i.e., how close the estimated graph could be to the MEC?
2. Please check the followed comment on the mentioned baseline. Sorry for any inconvience.


limitations_and_societal_impact: I did not find any limitations and negative societal impact of the submission.
review_title: null

Meta-review: This was a very borderline paper. After the author response and discussion, the one reviewer recommending rejection raised their score to a weak accept. Please make sure to read all of the reviewer feedback carefully and make suggested/promised changes for the camera ready. In particular, reviewer x4HL had some additional followup concerns that should be addressed.
Decision: Accept (Poster)