Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a new method for haplotype reconstruction in polyploid species and viral quasispecies. Their approach relies on graph message passing neural network.
strengths_and_weaknesses: The paper offers a clear and careful explanation of the problem, and an original solution. The performance gains over previous methods are substantial, suggesting the method could likely have significant impact on biological practice.

A weakness of the method is that the problem is not set up using an explicit generative model, with a clear description of the estimand and noise. This makes it difficult to understand the statistical properties of the estimation problem the authors are trying to solve. Instead, an objective is simply assumed (though I understand it is a standard objective in the field). Perhaps even more importantly, this also prevents connections to the broader ML/statistics literature, and in particular prevents application/comparison to well-studied methods for clustering vectors of discrete data, with entries missing at random (an alternative view of the haplotype reconstruction problem). 
questions: I see how Eqn. 3 is a relaxation of the constraints in Eqn. 2, but how exactly does the objective (the Hamming distance) come in? Could you provide a proof/derivation of Eqn. 3 from Eqn. 2?

Line 94 typo: ployploid -> polyploid
Line 287 typo: quasiqpecies -> quasispecies
Table 3: title says 3 viral quasispecies datasets, but 10 datasets are listed
Where are the colors from in Figure 3? (i.e. what’s the reference haplotype assignment?)
limitations: Although these are not problems unique to this method, I think the method’s inability to take into account statistical uncertainty, and inability to automatically discover the number of haplotypes (as may be necessary in studying viral quasispecies) are important limitations that should be discussed and addressed going forward.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper proposes a GNN-based approach for clustering reads (short biological sequences) that come from a stochastic process of sampling, with errors, subsequences from a few similar, but different, long sequences (e.g. genomes of several viral quasispecies); the ultimate goal of the method is to infer these long sequences from a set of short reads.
strengths_and_weaknesses: The presentation of the problem and the method is mostly clear, although some design choices are presented without much motivation, and seem somewhat problematic. Specifically:
- why use only SNP positions in determining that reads are overlapping (line 156 and 174)? Why not use positions in which nucleotides are the same (non-SNP positions?). E.g. if two 200bp reads overlap on 100 bases, but are from a region (e.g. a highly conserved, essential gene) that contains very few SNPs (below $p$ SNPs), why are they not considered overlapping?
- In lines 155, one reads “any two reads (…) must be (…) non-overlapping, consistent, conflict. But Consistent is defined as 0 differences in SNPs, Conflict as $\geq q$ differences in SNPs, then two overlapping reads with e.g. $q-1$ differing SNPs are neither Consistent nor Conflicting.
- the requirement that “any two conflicting reads have two different colors and any two consistent reads have the same color” (line 185) seems too strong. What about e.g. three quasispecies GGGGAA, AACCTT, AACCGG and a set of 3 reads AACC CCTT CCGG, p=2, q=2? All three reads are overlapping, and 1 is consistent with 2 & 3, but 2 & 3 are in conflict.

The paper involves a GNN message passing approach for solving the problem of assigning reads to quasispecies (colors), modeled as minimizing the loss (eq. 3) composed of two terms involving inner products of color assignments $p_i$ for vertices $i$: the “consistent” term that is the sum of $-\log( <p_i, p_j> )$ over all pairs $(i,j)$ linked by consistent edge, and the “conflict” term that is the sum of $-log ( 1 - <p_i, p_j> )$ over all pairs $(i,j)$ linked by conflict edge. This is a straightforward extension of cited prior work that only used one edge type and had a single term. Thus, the novelty of the approach on the GNN side is limited.

Finally, the toy example in Figure 2 seems too simple: judging from it, the problem can be solved by finding connected components in the graph with only blue (Consistent) edges taken into account.

questions: Please comment on the assumptions/design choices (see above), and on the novelty of the method.
limitations: Limitations are described adequately.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper explores the haplotype assembly/phasing problem through the lens of graph coloring and proposes a solution based on graph representation learning with a local search refinement. The problem admits a unique graph coloring formulation that differs from conventional graph coloring in that there can be consistent and conflict edges, whereas, traditionally, graph coloring would only handle conflict edges. Similarly, graph neural networks typically assume that similar nodes should have similar embeddings, but this assumption is challenged in the current setting. The authors formulate a loss function to account for both types of edges and their experiments demonstrate a significant improvement over competing approaches.
strengths_and_weaknesses: Strengths
* A nice reduction from the haplotype assembly/phasing problem to a modified graph coloring problem is proposed, thereby introducing opportunities to leverage work done in that field.
* A novel loss function is derived that accounts for similarity and dissimilarity of vertex relationships via consistent and conflict edges, respectively. This may even be generalized to graph neural networks more broadly.
* Experiments are performed on synthetic a real-world datasets, demonstrating an improvement over competing approaches.

Weaknesses
* Some details are missing on how the COMBINE, AGGREGRATE, and MESSAGE functions are defined
questions: 1. Can you provide more details on how the COMBINE, AGGREGATE, and MESSAGE functions are defined?
2. How do you see the notions of similar and dissimilar embeddings via consistent and conflict relationships being generalized to graph neural networks more broadly?
limitations: The authors claim that Section 5 covers limitations, though details are scarce.

Some minor comments:
"haploytypes" -> haplotypes
"Neural Networks on Graph." -> Neural Networks on Graphs.
"functionm" -> function
"} respectively" -> }, respectively
"Two overlapping read are called" -> reads
"naturally motives" -> naturally motivates
"constraints satisfying problem" -> constraint satisfaction problem
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Haplotype assembly is crucial for resolving the fine structure of structural variation, detecting copy number variation, SNP panel imputation (these tasks in diploids), and reconstruction of viral "quasispecies". Assembly is more difficult with shallower sequencing, increasing ploidy, increasing sequencing error, and increasing numbers of related strains.

The authors define the assembly problem for ploidy > 2, given a priori a number N of chromosomes or species, and a set of reads aligned to a reference, as assigning reads to N haplotypes ("colouring") are aligned to minimize the summed hamming distances between each of the reads and their respective consensus haplotype (the so-called MEC). This problem is unfortunately NP-hard.

The authors first relax the problem by allowing themselves to merely assign each read a probability of belonging to each haplotype, solving the original problem by simply assigning each read the most likely colour (this is taken from previous work). Next they write a heuristic loss for this relaxed problem. The loss penalizes overlapping and consistent (> p bases overlapping, all the same) reads being assigned to different haplotypes and overlapping and inconsistent (> p bases overlapping, > q different - p, q are hyperparameters) being assigned to the same haplotype.

Precomputing which reads overlap and are consistent or inconsistent, the authors propose minimizing the objective the following way:
assign each read an embedding that is put through a neural network
After obtaining a colouring by minimizing this heuristic objective, the authors "tune" the colouring to minimize the MEC as well. However, in figure 5 (compared to table 3), the authors demonstrate that most of the performance improvement of the model compared to previous methods comes from simply minimizing the heuristic loss.

The authors demonstrate their ability to minimize the MEC on a number of benchmarks
strengths_and_weaknesses: Strengths:
1) Data and code was easily accessible, making it easy to tell what the authors did. Although the particular parameters used to run the code are not available.
2) The authors seemingly pose what seems to be a new objective for the relaxed assembly problem whose minimization seems to also minimize the MEC.
3) The authors propose a method that, in attempting to minimize this new objective, succeeds in minimizing the MEC more than previous methods.
Weaknesses:
1) I am concerned the benchmarks do not justify the use of the GNN.
2) I am concerned benchmarking using only MEC on very small datasets may not display any possible pathology of the assembly and doesn't demonstrate the ability of the model to scale to relevant data sizes.
(See questions)
Because of these concerns, the validation provides enough guidance to practitioners on the strengths and efficacy of the model.
3) The main text leaves certain concepts ambiguous: i) the authors did not make it clear in the main text what parameters were being optimized in the methods, in particular the initial embeddings. ii) it was not stated unequivocally that the authors themselves had come up with the objective (3), or what they were inspired by.

questions: 1) My primary question: The loss in equation (3) must be minimized over a space of dimension #reads X (#haplotypes-1). The largest this dimension ends up being in the benchmarks is 500 x 14 = 7000. Is it not thus possible to perform gradient descent on the haplotype membership probabilities directly? It also seems that since the GNN method involves optimizing the initial embeddings of all reads, optimizing the GNN is a higher dimensional problem than optimizing the membership probabilities directly. (Other NN methods cited -CAECseq and GAEseq- avoid the problem of the dimensionality of the optimization problem scaling with number of reads by using the one-hot encoded sequence or the column of the SNP matrix to construct the initial embedding, in principle reducing the dimension of the optimization problem.)

2) Why do the benchmarks contain so few reads and only aim to reconstruct small parts of a chromosome? Methods exist for diploid haplotype assembly that are accurate for 100s of kb containing substantially more than 1000 reads. H-PoP looked to assemble over 60 thousand reads with 12 thousand SNPs in their publication. Is scaling to the size of an entire chromosome a difficulty for your method? Is this scaling not necessary for use of these algorithms?

3) Why only focus on MEC as a performance metric? It is known that the presence of reads with errors means that the correct phasing may not be the one with the lowest MEC. Many alternatives, including switch error rate are presented in the author's citation Saada OA et al, 2022. This seems to be an important consideration especially when introducing a new metric to minimize.
limitations: It seems that the primary limitation of this method is its inability to scale beyond small datasets assembling short reads from only a fraction of a chromosome at once. At least evidence was not shown of scaling to larger datasets.
The authors have not suggested a method to tune hyperparameters p and q for arbitrary datasets, which may be required for sequencing with different read length and quality.
review_title: null

Meta-review: metareview: This paper presents a method, NeurHap, that addresses the haplotype reconstruction problem using a combination of graph representation learning and combinatorial optimization. The reviewers engaged in a detailed discussion with the authors on the merits of the paper. Some reviews found weakness in the novelty, yet as a contribution to the problem domain, found it useful. The main concerns were around lack of clarity. One review found a lack of clarity about the estimand, noise and objective which limit connections to work in the broader machine learning community. There was also a lack of clarity in terminology around "consistent" and "ambiguous". Finally, there was a lack of clarity around the parameters used in the method for the data analysis. These concerns compounded to reduce enthusiasm for the paper. I most strongly encourage the authors to take the reviewers' comments into consideration and revise their paper to improve the clarity and consistency with existing literature in the field so that the contributions can be understood and appreciated by the wider machine learning community.

confidence: Less certain
Decision: Accept