Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a novel Bayesian model for nonparametric regression in complex spaces such as manifolds.  Let $S$ be the set of points $s$ at which the outcome $Y(s)$ is observed.  The basic idea is to take a known (or estimated) graph $G$ over $S$, and consider the class of piecewise constant functions over spanning trees of $G$.  The mean of the outcome $Y(s)$ at $s$ is then modeled as a finite sum of such functions $g_m$ for $m=1,\ldots,M$.  An MH-within-Gibbs MCMC algorithm is proposed, in which the parameters of each $g_m$ function are updated in turn by making a move that preserves the full conditional distribution.  A well-chosen prior on trees facilitates exact sampling from the full conditional on spanning trees, using a previously known result from the literature. On simulated and real data, the method performs very favorably compared to competitors, including BART, SFS, and inGP.
main_review: I found the proposed model and inference technique to be quite interesting and thought-provoking.  The model appears to be novel, and while the individual pieces of the MCMC algorithm are not novel, the paper does a nice job of integrating these previous ideas.  The paper is well-written and clear, both in terms of exposition and mathematical presentation.  In terms of significance, if the good empirical results presented here generalize to other data sets, the method could be quite useful in many practical applications.

MAIN COMMENTS
1. Identifiability is not discussed in the article. Depending on how the model is used, this could be problematic.  For instance, if inferences on the individual component functions is desired, then there is a label-switching problem.  Also, lack of identifiability could affect MCMC mixing performance.
2. Out-of-sample predictions (Sec 3.2): The rationale for the proposed method of making out-of-sample predictions was not clear to me.  It seems like a natural approach would be to consider a new model in which the new point $u$ is included in $S$, and look at the posterior predictive on $Y(u)$.  Does this coincide with the proposed approach?
3. In Section 4.1, over what domain are the MSPEs and MAPEs computed?  For instance, are you averaging the prediction error over the whole domain $M$?  Or is this the error on the training set?  Or something else?
4. It seems like the MCMC sampler might mix slowly since each component is updated individually, holding the others fixed.  This might make it difficult for the sampler to move around the parameter space.  I would recommend using standard diagnostic techniques to assess MCMC convergence.
5. Computation time: How long does the BAST sampler take to run, compared to BART and the other competitors?
6. On what types of problems does BAST not perform well?  I would imagine that high-dimensional spaces might be more difficult (for BAST compared to BART, for example), since the distances between points are less useful for defining local smoothness in a high-dimensional space.  Evaluating performance on a high-dimensional example would make the paper much more compelling.
7. What about combining BAST with other types of functions, e.g., regression trees with axis-aligned splits like in BART?  A hybrid BAST-BART model might be interesting.

MINOR COMMENTS
- The paper assumes the data live on a compact Riemannian manifold. Is the compactness assumption needed?
- Line 100: I think “cycle” is a more standard term than “circle”.
- $M$ is used to denote both the manifold and the number of components in the model.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new Bayesian additive regression spanning trees (BAST) model for nonparametric regressions on manifolds. The model uses a new random spanning tree manifold partition model as weak learners, which allows it to capture complicated local discontinuity patterns in the true function while respecting intrinsic geometries of the domain. Building on nice properties of spanning tree structures, an efficient Bayesian inference algorithm is developed. Experiments on simulation data and the real chlorophyll data in Aral Sea show that BAST significantly outperforms other competing methods.
main_review: The paper is very well written and a pleasure to read. The Bayesian model and inference procedure in Sections 2-3 are clearly explained and technically sound. I found it is a solid piece of work as a whole and the BAST model is interesting itself and could be used in many applications.
 
Comments:
Line 79: The word "constrains" should be spelled as "constraints".
Line 120: Is would be useful to explain a bit more about the binary treed partition models, e.g., does it also need to specify the number k of clusters. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a modification of Bayesian Additive Regression Trees tailored to complicated or constrained input space.
The basic idea, like BART, is to learn a collection of piecewise-constant weak learners to approximate an unknown regression function. Unlike BART, which parametrizes each weak learner using a binary regression trees with axis-aligned splits, the proposed BAST procedure parametrizes the weak learners using a spatially-contiguous partition of the input space that is index by a random spanning tree.
The proposed procedure works quite well on simulated and real world data. It represents a very interesting new direction in a growing literature around BART.
main_review: Originality: The individual components of BAST are not especially novel; there are very active communities studying both BART and its extensions and spatially contiguous partitions using spanning trees . The main novelty, then, of the paper is the effective combination of these two ideas.

Quality: On the whole, the ideas underlying BAST are sound and I commend the authors for a well-executed paper. A few minor questions about the method:

- Sensitivity to $\overline{k}$ & its interplay with $M$: Table S2 in the Supplementary Materials suggests that, at least for the two synthetic data experiments, BAST is not especially sensitive to the choice of the upper limit on number of clusters per partition. It would be helpful, however, to probe the sensitivity a bit more. E.g. how does the performance change as one increases or decreases $\overline{k}$? I suspect that if one were to increase $M$, one could get away with a smaller choice of $\overline{k}$ (and vice versa). A more comprehensive sensitivity analysis would be greatly appreciated. 

- Timing comparisons: I suspect that both BART and BAST are faster than the two other competing methods (SFS and inGP). Is this the case? 

- Complexity: What is the per-iteration time complexity? Will the worst-case complexity be O(M * n^2) as you may have to re-run Prim's Algorithm every time you propose a "hyper" move? How does this compare to the competing methods (BART, e.g., will have per-iteration time complexity O(M * n))

Clarity: The paper is well-written.

Significance: I think this paper represents a good step in pushing the boundaries of BART and moving away from strict axis-aligned splits. I anticipate it will be quite useful in spatial modeling. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Authors develop a novel Bayesian nonparametric regression model specially on known manifolds and complex constrained domains using additive RST partitions, which take advantage of flexibly shaped partitions. If the manifold is unknown, one should estimate it before applying the purposed method.
main_review: - The main contribution of this paper is replacing the binary decision tree in BART model with random spanning tree, a flexibly shaped partitions. In this sense, the novelty is somehow limited per the standard of NeurIPS.

- The experiments in the paper are not especially well-designed. For example, standard error of BAST goes up dramatically as $\\sigma$ increases, while BART told a different story. Authors should look into this or at least give some explanations.

- The paper is well written with a clear mind. Readers outside this narrow area should find it readable.

- Since the authors do not compare their method against some BART variants adapting to graph problem, it is hard for me to evaluate the significance of their work. In general, methods taking advantage of extra information (structure) should outperform those does not.
limitations_and_societal_impact: There are a lot improvements can be made, a few are as followed:
- Authors should find a way to fix the issues mentioned in the main review.
- The number of tree should be larger, since it is essentially a truncation. Per the original paper, a recommended number is at least 50. However, the larger the better. Another way is to implement the Reversible-Jump MCMC.
- Authors should examine whether BAST and BART converge or not after the purposed 20,000 iterations.
review_title: null

Meta-review: This article introduces a novel Bayesian method for nonparametric regression on manifolds, referred to as Bayesian Additive Regression Spanning Trees (BAST). The basic idea is to build a sparse graph $\mathcal{G}$ on the observed covariate data points, and use a BART-like ensemble of tree-based models on $\mathcal{G}$.  The graph $\mathcal{G}$ captures the lower-dimensional geometry of the manifold on which the covariates live, and the tree-based models yield piecewise-constant functions on partitions of the data. A Gibbs sampler algorithm is provided for posterior inference. In particular, a well-chosen prior on spanning trees facilitates exact sampling from the full conditional on trees for each tree-based model component in the ensemble, using a previously known result from the literature. Experiments are performed on simulated and real data.

Generally speaking, the reviewers and I found the paper to be interesting and novel.  The paper is well-written and the method appears to provide a valuable contribution to this area of research.  The method provides a compelling improvement in performance relative to competing methods.

In my view, the main limitations are:

1) The computation time is quite costly compared to competitors.  For instance, on the U-shape example, BAST takes 651.49 seconds while BART takes only 15.83 seconds (see authors' reply to Reviewer Tbpc).  The authors mention that a more computationally efficient implementation of BAST is under investigation.

2) Performance is likely to degrade significantly as the dimensionality of the data grows; see point 5 by Reviewer Tbpc and the authors' reply.

3) The method for out-of-sample predictions seems *ad hoc* and could potentially be improved.  The method does not provide a coherent (i.e., projective) model for all points in the space, since it is defined only on the observed points due to reliance on the graph $\mathcal{G}$.  Thus, the model does not lead to a natural technique for making out-of-sample predictions, which is presumably why an *ad hoc* method was used.

The only score below the acceptance threshold was from Reviewer R75X, with a score of 5.  Although R75X has not responded further, I found the authors' reply to satisfactorily address the main criticisms and questions.
Decision: Accept (Poster)