Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper describes a continuous-time Markov Chain method for modeling the time evolution of events. By including independent items the authors are able to increase the limit on the number of items modeled. This research is particularly relevant as larger single-cell sequencing data sets are being collected.
main_review:   The underlying biomedical problem is well-motivated and the authors briefly mention other possible applications. I think they could have provided more clarity on the specific problem --- the use of the term "item" is confusing in paragraph 2. The reader wonders if an "item" is a cell or a genetic locus, though this is clarified later in the paper.

  Going from cross-section data to longitudinal inferences requires assumptions about the distribution of the samples. It would be helpful to be more clear about the assumptions that enable the underlying inferential goal of this work.

  The "warm-up" example clearly illustrates an important point. But the title "warm-up" seems pedantic. Perhaps a more descriptive title such as "A counter-example for inferring time order" would help the reader to understand the motivation of the example. The discussion in section 3.3 is helpful in that it links back to the counterexample.

  There are some standards for genetic nomenclature and it does not seem the case that the authors have used that nomenclature here. This leads to some confusion as to what exactly is meant by "amplification" in figure 3. Is this an increase in copy number or increase in transcription or translation due to an epigenetic change or something else. It would be helpful to clearly state what the data can and can't inform about the mechanisms.

  The meaning of the error bars in figure 3 is not clearly stated.

  The development of the method is predicated on a set of "interesting items" $V$ and a set of "independent items" that are used to help inform the clock (lines 1-168). Then, in the paragraph on lines 169-174, the authors state, "we will make no distinction between 'items of interest' and independent items". It is not clear, theoretically, what motivates or justifies this shift in perspective. Prior to this change, I was left considering how one might select "interesting" and "independent" genetic loci, but it seems that has been rendered unnecessary. It would be helpful for the authors to clarify what motivates and theoretically justifies the elimination of the need to specify $V_+$ - the "independent" set of items.

  The description of the experiments makes it impossible to reproduce the results of the paper. On line 280, the authors state that they evaluate on a data set of tumor samples from glioblastoma from TCGA, but TCGA contains expression, mutation, and methylation data. It is not clear what data the authors used and the url to the entire project does not enable reproduction of the analysis. Perhaps a more detailed description with code can be provided in supplementary information.
limitations_and_societal_impact:   The authors only compared to Schill (2019). There are many tumor evolution method available in the bioinformatics literature and without a more comprehensive comparison, the utility of this approach may not be clear and adoption of the approach may be limited.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors model the time evolution of discrete states (e.g. genetic mutations) using a continuous-time Markov chains. They show that the resulting learning task is generally underspecified given cross-sectional data. The authors suggest including additional independent items that can help determine time order, and resolve this underspecification.  The authors implement an approximate likelihood maximization method for learning continuous-time Markov chains, which shows good performance on high-dimensional data, is faster than competing methods, and shows promising results on synthetic and real cancer data.
main_review: Originality: The work is a novel combination of well-known techniques. Related work needs to be adequetely cited

Quality: The submission is technically sound justified by theoretical analysis and experimental results. This is a complete piece of work and is built heavily using Schill 2019. 

Clarity: The submission is clearly written. 

Significance: The study and results are important in many fields. There is potential for others to use the ideas. The work provides a unique theoretical approach.

* Comments to authors

   * The problem setup section as well as Section 5.1 heavily lean on Schill 2019: https://academic.oup.com/bioinformatics/article/36/1/241/5524604
This fact is not clearly cited in the paper or Problem section.
It seems that the current paper builds on Schill 2019, while also uses the same cancer data for real-world experiments, with the value-add of theoretically proving the usage of additional data. 

   * Regarding the additional unimportant data, how much and how complete should this be? The Markov chain would require that these additional data are present at (t-1), so that the chain can learn at t. What if additional data is missing at (t-1) or is available only intermittently? Would the equations in Section 4.2 still hold?

  * Is the maximum dim of \Theta_{full}, sum of dim of V and V_{+}? (Section 3.2). So in cases, when the dim of \Theta_{full} is < sum of dim of V and V_{+}, shouldn’t the off-diagonal information be taken into account as well?
  
  * From Theorem 1, Appendices C and G, it seems that \Theta_{full} has to maintain a block-diagonal structure. By adding additional unimportant data, across time points, there is a higher likelihood to see dependency across time points (i.e important signals in the off-diagonal elements). This is generally the case when identifying trajectories of cell differentiation in single-cell data across multiple (pseudo) time points and adding incomplete information for certain time points when available. It is a non-standard and underspecified problem, in which case, the dependency of additional terms is what helps connect time points. Based on this, aren’t the authors losing important information by enforcing a block-diagonal structure? How easy is it to incorporate information from off-diagonal elements into the CTMC?
limitations_and_societal_impact: Limitations were not mentioned in the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors tackle the problem of time evolution of discrete sets through the view of continuous-time markov chains. The authors provide a theoretical justification of why these problems in general underspecified in the setting of cross-sectional data. They go on to demonstrate that the underspecification can be overcome by use of additional items / features that can help determine time order by deriving a bound on the mean and variance of the observed time for these additional items. An approximate formulation for likelihood maximization is then presented without any assumptions of prior knowledge of the additional items or the structure of the additional items. The theoretical framework is then tested using simulation studies and demonstrate that accuracy of state sequence recovery can be significantly improved with use of the additional items. The framework is also evaluated using a real world cancer dataset from TCGA by ordering of pairs of mutation and copy number aberration events. 
main_review: This is a very interesting submission that demonstrates how underspecification in continuous-time markov chains can be resolved by use of additional independent features/ which might not directly relevant to the problem under consideration. The paper is well written and the use of a consistent example throughout the manuscript conveys the concepts clearly. My comments are largely related in practical applications:
1. The simulation results presented by the authors are convincing and a clear demonstration of the concept. However it is not clear to me how well the formulation would hold up under noisy data - perhaps larger markov chains where some observations might be missing subset of states would provide a practical view of the limitations 
2. Any individual cancer type has been demonstrated to contain distinct sub types each with associated mutations and/or copy number alterations. For eg, the IDH mutation in GBM highlighted by the authors is observed in only a subset of individuals and is associated with better survival. Therefore a broad span of patient data will most likely include mutation /copy number aberration drivers that are distinct and mutually exclusive to each other. How is the learning process influenced in the presence of such confounding factors and how does it affect the interpretation of the results. 
	

limitations_and_societal_impact: The authors address the limitations of the behavior of the algorithm when assumption of independence of additional features is violated.

The work does not appear to lead to any potential negative societal impacts in my opinion.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper deals with learning a particular class of multi-component continuous time Markov chains (CTMC) when time stamps are unobserved in the data. In this class binary components change their state irreversibly, rates follow a pairwise interaction model and one component changes at a time. The authors show that modeling independent elements provides information about the posterior distribution of observation time and provide an efficient stochastic approximation to the likelihood’s gradient.
main_review: **Originality**: 
Inferring temporal relations between sequences using independent mutations and a CTMC model is already a fundamental technique in phylogenetics. Therefore, I suggest mentioning the relation of the proposed approach to this field. Yet, as far as I know, the explicit quantification of the added value of independent components (Theorem 1) is novel.
The approximation technique is a novel combination of formulas for inferring the likelihood of partial sequences, stochastic gradient approximation and MCMC sampling.

**Quality**: 
The added value of additional independent components is supported by a sound derivation in Equation 2. This added value is quantified in Theorem 1 which is proved in the appendix.
The approximation algorithm contains a series of well-established steps.
The experimental section gives a good illustration of actual gain of leveraging additional independent components and illustrate a very nice application of modeling cancer tumor progression.
While the title describes the method as a general CTMC, the actual model is a specific type that assume irreversible changes of components with pairwise influences on the rates. This subclass has an interesting important application and therefore it does not diminish the significance of this work. However, this specificity should be more clearly stated, at least in the abstract.

**Clarity**: 
The paper is clearly written. Here are some suggestions to improve readability:
1.	‘Underspecified’ is a broad term and makes the abstract a bit vague. It may be good to state the sentence from the introduction -- ‘consist of unordered sets of item observed at unknown time point’ -- already in the abstract.
2.	The cancer example is very illustrative and provides a strong motivation. Furthermore, the paragraph in line 162 motivates the usage of independent mutations. It may be good to move it to the introduction, to make the motivation clearer at this stage.
Minor questions:
3.	Theorem 1: should V be replaced by V_{+}?
4.	Figure 1: do the different curves represent posteriors given different values of S_{+}? 
5.	Where the N tumor samples taken from N distinct patients, or were multiple samples taken from some patients? This may influence the choice of modeling approach.

**Significance**: 
This work may be an important step in enabling modelling of cancer tumor progression, and may have also applications in other domains in which systems accumulate irreversible changes over time with dependencies among some of the components.


limitations_and_societal_impact: I do not see a potential negative social impact that is specific to this work.

The paper lacks a discussion of limitations of the method. For example, the experimental section used a fixed value of lambda. This seems to have a major effect on the sparsity of the inferred interaction matrix. Is there a reasonable way to tune this hyperparameter as done in prediction tasks?
review_title: null

Meta-review: This paper describes a method for modeling the time-series changes in a discrete set of items. The particular application the authors have in mind is phylogenetic inference where the items are genetic mutations. The method involves reframing and using continuous-time Markov chains. While moving to the continuous domain helps address the combinatorial nature of the problem, it introduces another problem - underspecification - which results in poor generalization, sensitivity, and false positive correlations. The authors propose a solution based on prior work (Schill et. al 2019) that employs so-called "unimportant items" to help recover the time order.

The reviewers noted two specific aspects of significance of the work. First, the paper provides bounds on the expected amount of information gain from including these "unimportant items". Second, the paper addresses an important problem in bioinformatics. Inferring the tumor evolution process is a well-studies problem in genomics and has been studied extensively. In clinical applications, the tumor evolution may be of limited concern because the physician is primarily interested in treating the whole tumor as it presents (including any heterogeneity). But, in fundamental research, understanding the tumor evolution can inform our basic understanding of the processes that lead to tumor growth and metastatic processes and therefore phylogenetic inference is a significant problem to address. It should be noted that for this method to be used in practice, a distinction must be made between "interesting" and "uninteresting" items. This may be done by the model or with prior knowledge. The authors have constructed their algorithm to allow the model to make this distinction which may improve the generality for problems outside of phylogenetic inference.

I'm in agreement with the reviewers after considering the author response and discussion that this paper should be recommended for acceptance. The theoretical contributions may prove useful for a broad range of similar problems and the practical utility on a data set relevant for practical phylogenetic inference is demonstrated.

Decision: Accept (Poster)