Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new algorithm to solve the problem of recovering, as much as possible, the original graphical causal structure at the causal timescale from the derived graphical structure at a measurement timescale, where measurements are made every u number of time steps for an unknown u. The new algorithm is based on ASP and incorporates some new constraints that were not exploited in previous algorithms. Experiments show that the new algorithm scales much better than the previous methods.   
strength_and_weaknesses: Strengths:

1. The proposed algorithm addresses a commonly encountered challenge to causal discovery and achieves a very significant speedup in comparison to previous attempts. 
2. The experiments demonstrate some nice properties of the new algorithm.
3. This paper is well written and relatively easy to follow.  
 
Weaknesses:

1. There is no experiment with real or even simulated data. I am a little puzzled why no empirical demonstration is attempted on streamlining the proposed algorithm with a causal discovery algorithm applied to data at the measurement time scale.
2. For the optimization version of the algorithm, it is unclear how the weights should be determined. Are they supposed to be entirely user or expert specified? Or is there a data-driven procedure to assign the weights. Conceivably some causal discovery methods may yield interpretable weights on the inferred edges, but this prospect does not seem to be discussed in the paper.    
3. It is also unclear to me why no empirical comparison is made to the ASP-based algorithm in Hyttinen et al. (2017). 
clarity,_quality,_novelty_and_reproducibility: The main idea of the paper seems quite straightforward given the previous work on this problem, so the novelty is limited. However, the improvement achieved by the new proposal is significant. The paper is very clear and readable, and I expect the reproducibility of the empirical results to be very good, especially since they do not involve data.

A clarificatory question: does the soundness of the algorithm rely on the assumption that the condition on gcd(L_s) in Theorem 3 (and Theorem 2) holds?
summary_of_the_review: This is a well written paper presenting an improved method to tackle an interesting problem. The improvement demonstrated by experiments is significant, though more experiments on simulated or real data would probably better vindicate the utility of the method.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focused on the causal discovery problem on the dynamic systems. The proposed method focuses on the problem that the measurements timescale and the causal timescale do not match. To solve this problem, this paper proposes Rate-Agnostic Structure Learning, that uses undersamples graph H as input learned from data D, domain knowledge or other sources. The learned graph from first order markov shows effective undersampling rate, from the full space of G1. sRASL proposed in this paper does not suffer from assumptions or computational complexities.
strength_and_weaknesses: Strengths:
1. The study problem in this paper is quite interesting, it focuses on learning causal graph from dynamic systems. This problem is quite challenge when the data are undersampled. 
2. The proposed algorithm has faster performance without asking for specific undersampling rate.

Weaknesses:
1.  It might be better to compare with more other baselines.
2.  It might be more clear to show how the graph changes with the time changing.

Additional questions:
1.  What is the main difference between sRASL and RASL?
2.  How would the undersampling rate influences the causal discovery results?
clarity,_quality,_novelty_and_reproducibility: The study problem in this paper is quite interesting. The proposed method in this paper is novel and efficient.
summary_of_the_review: In summary, this paper proposes to solve an interesting and challenging problem. The proposed method is sound and valid across different settings of datasets.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work studies the problem of learning a causal network from temporal data in the presence of under sampling. In particular, the authors propose a solver based approach for learning a graph from under sampled data, which improves upon prior art significantly in terms of running time. The core of the approach is converting an existing algorithm (RASL) which is score based to a solver based approach.
strength_and_weaknesses: Strengths:
* Compelling task
* Practical and reasonably scalable approach for learning graphs under under sampling
* Compelling experimental evidence

Weaknesses:
* Would be nice to see a more substantive analysis of the behavior of the algorithm when assumptions fail to hold and the algorithm is finding "close" solutions
* Still relatively modest in scale. While 100 nodes is substantially larger than prior art large scale temporal systems can contain substantially more variables. 
* As I mention below, it would be nice to have an algorithmic description of the method in a more common format. 
clarity,_quality,_novelty_and_reproducibility: Overall I thought this paper was very well written, easy to follow, and fairly complete. The novelty is somewhat limited since it is directly building off of prior art, but I don't find that a reason for penalization–the work provides a non-trivial improvement that is important for application. My largest complaint with respect to clarity is the description of the algorithms. The authors use Clingo code to describe the algorithm. While I commend them for including code that can be easily reproduced, pseudocode should be preferred so the algorithms can be more easily interpreted by a wider audience. 
summary_of_the_review: Overall, I think this paper provides a nice extension to the existing literature. The problem of learning from under sampled time series is nearly ubiquitous in practical applications. I found the proposed method to be well reasoned, clearly presented, and to have good justification via empirical evidence. While I would have preferred to see a more thorough analysis of the behavior of the algorithm under misspecification, I consider this to be a nice addition to the literature.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The work addresses the problem of learning a causal graph, or rather the set of compatible graphs in the equivalence class, from time-series data when facing the challenge of undersampling, that is, when the sampling rate does not match the rate of the data-generating process. It assumes the presence of a compressed graph which can, asymptotically, be learned from time-series data and the objective is to identify all the causal graphs that are compatible with the compressed graph at some sampling rate. Thus, the authors propose an algorithm, sRASL, which reformulates a search-based algorithm, RASL by (Plis et al., 2015), along with additional structural insights into a constraint satisfaction problem. Experimental evaluation shows a clear advantage of the proposed algorithm over the search-based approach.
strength_and_weaknesses: Strengths: The evaluation of the proposed algorithm shows a significant speedup compared to RASL and thus provides a clear advantage in terms of scalability.

Weaknesses & comments:
1- Source of undersampled graph H: The authors state the following:
> sRASL algorithm takes as input a (potentially) undersampled graph H, whether learned from data D, expert domain knowledge, a combination of the two, or some other source.

It is understandable to make such an assumption whenever there are theoretical guarantees that a compressed graph can be asymptotically learned from data. If such a result is known in the literature, it should be made clear in the text. However, it sounds unlikely that such a structure can be fully learnable as is the case with PAGs (Zhang, 2008).

2- Evaluation: There is no comparison of the performance of sRASL and the work of (Hyttinen et al., 2017). I understand that the latter assumes the undersampling rate is known but a comparison is possible by running "the method sequentially for all possible u".

3- Citation confusion: The citations on page 2 regarding the works of MAGs and PAGs are incorrect. The work of (Richardson & Spirtes, 2002) presents the theoretical formulation of ancestral graphs where MAGs are a special case. However, MAGs are not learnable from data. Zhang (2008) builds on this work by Spirtes and others to formulate a complete learning algorithm, the output of which is a PAG. The cited work by Zhang is for inference applied on top of PAGs; a more suitable citation is the one below.

Zhang, J. (2008). On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial Intelligence, 172(16-17), 1873-1896.

4- Typos:
+ p.4, "As a concreate example of the improvements": concreate  --> concrete
+ p.5, "In order to incorporate Equation 5 in Listing 1": do you mean Equation 1?
+ p.6, "In other words, Theorem 5 implies": Do you mean Thm. 4? Theorem 5 in the appendix is the exact replica of Theorem 4.
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well-written and the various ideas are explained thoroughly, except for a few issues discussed above. 

Novelty: The proposed work appears to be marginally novel as it is based on ideas from previous works (shown below).
 - Search-based algorithm for the same task by (Plis et al., 2015).
 - Structural insights about SCCs in a compressed graph by (Danks & Plis, 2013)
 - Using ASP to learn the causal graph when the rate is known by (Hyttinen et al., 2017)

I am open to revisiting this evaluation based on elaboration from the authors.
summary_of_the_review: The proposed algorithm provides a clear advantage over previous methods in terms of speed and scalability. This is evident from the experiment though some further expansion of the results would be helpful (comparison to Hyttenin et al. (2017)). However, the method assembles ideas from previous works making the novelty and contribution marginal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides an Answer Set Programming based algorithm for determining a true directed causal structure from an under-sampled version of it.  The original problem is NP-complete, and previous methods have not been successful with even moderate-sized graphs, but the new method (sRASL) can deal with up to 100 nodes.

strength_and_weaknesses: UPDATE: Since the authors have added the references and explained the reasoning behind other choices, I will revise my score upwards.

----

A clear strength is the improvement in the speed of discovering these underlying structures, which is impressive.

There are several weaknesses, however.  First, a significant part of the literature on causal discovery in time series is entirely omitted.  A short list (I am sure it is not exhaustive) would include Granger (1969), Chu and Glymour (2008), Entner and Hoyer (2010), Malinsky and Spirtes (2018), Jabbari et al. (2017) and Gerhardus and Runge (2020).  I would also expect to see a comparison of the method to at least one other state-of-the-art discovery algorithm, rather than to a worse incarnation of the method in the paper.

Second, the graph is assumed to be first order Markov without instantaneous effects, and the under-sampling assumed to be at a fixed integer; there is no reason to believe that either of these assumptions will hold in a real problem.  

Third, there is no real data application.  This is not necessarily a problem, but given that the motivation focuses very strongly on fMRI data and the paper claims that this new algorithm ought to be able to handle such data, I was disappointed not to see it applied.

### References

Chu, T. and Glymour, C. (2008). Search for Additive Nonlinear Time Series Causal Models. _Journal of Machine Learning Research_, 9:967–991.

Entner, D. and Hoyer, P. (2010). On Causal Discovery from Time Series Data using FCI. In _Proceedings of the 5th
European Workshop on Probabilistic Graphical Models_, pages 121–128.

Gerhardus, A. and Runge, J. High-recall causal discovery for autocorrelated time series with latent confounders. In _Advances in Neural Information Processing Systems_ 33 (2020): 12615-12625.

Granger, C. W. J. (1969). Investigating causal relations by econometric models and
cross-spectral methods. _Econometrica_, 37:424–438.

Jabbari, F., Ramsey, J., Spirtes, P., and Cooper, G. (2017). Discovery of Causal
Models that Contain Latent Variables Through Bayesian Scoring of Independence Constraints. In
_Machine Learning and Knowledge Discovery in Databases_, pages 142–157.

Malinsky, D. and Spirtes, P. (2018). Causal Structure Learning from
Multivariate Time Series in Settings with Unmeasured Confounding. In _Proceedings of 2018 ACM SIGKDD Workshop
on Causal Disocvery_, volume 92, pages 23–47, PMLR.

clarity,_quality,_novelty_and_reproducibility: The quality seems good, and I do not doubt its originality at all.  It is also very clearly written.
summary_of_the_review: UPDATE: Raised score from 5 to 6.

----

I can't give a higher rating than this unless the authors can explain their omission of so much (seemingly) related literature from the paper, and their reasons for only comparing to one (almost a straw-man) method.  If these things can be explained to my satisfaction, then I would be happy to raise my score.

### Minor Comments

1. The comparison at the end of section 2 is slightly unfair, since you take the longest computation from RASL and then give its sRASL counterpart.  You could presumably give the longest computation from sRASL and then say what its RASL counterpart was!

2. Similarly, the comment on page 9 ('except for high undersamplings') sounds wrong, given that you only use a maximum undersampling of 4; this is far lower than the 20 you describe as being likely in fMRI data.

### Typos
 - throughout: many `\cite` (or `\citet`) commands should be replaced by `\citep`.
 - page 1: 'importantly incorrect' - this is a strange choice of phrase.
 - page 2: the references for PAGs and MAGs appear to be the wrong way around.
 - page 4: 'Section4.3' $\to$ 'Section 4.3'.
 - page 5: 'In order to incorporate Equation 5 in Listing 1': this comment comes out of the blue, and no mention of the equations in Appendix C has previously been made.
 - page 9: 'tool in the scientists’ policy-makers’ toolboxes' - is there a missing word here?
 - pages 10-11: please ensure that your references are consistent and that the capitalization is correct.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Interesting causal structure discovery paper taking in consideration the issue with under sampling. A key point is that measurements might not happen exactly when they are "wanted" (for causal inference). They propose an approach using ASP that improves on SOTA, in particular in terms of speed up, which is significant. The paper is clearly written and has enough original material.

justification_for_why_not_higher_score: Topic/scope of the paper might not be fully attractive to the general ICLR audience.
justification_for_why_not_lower_score: Clear consensus that this is relevant work and well executed.
Decision: Accept: notable-top-25%