T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs
Authors: Changwoo J. Lee
Zhao Tang Luo
Huiyan Sang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian
Clustering
Fused Lasso
High-dimensional regression
Markov chain Monte Carlo
Shrinkage prior
Sparsity
Tree-based methods

Abstract: Graphs have been commonly used to represent complex data structures. In models dealing with graph-structured data, multivariate parameters may not only exhibit sparse patterns but have structured sparsity and smoothness in the sense that both zero and non-zero parameters tend to cluster together. We propose a new prior for high-dimensional parameters with graphical relations, referred to as the Tree-based Low-rank Horseshoe (T-LoHo) model, that generalizes the popular univariate Bayesian horseshoe shrinkage prior to the multivariate setting to detect structured sparsity and smoothness simultaneously. The T-LoHo prior can be embedded in many high-dimensional hierarchical models. To illustrate its utility, we apply it to regularize a Bayesian high-dimensional regression problem where the regression coefficients are linked by a graph, so that the resulting clusters have flexible shapes and satisfy the cluster contiguity constraint with respect to the graph. We design an efficient Markov chain Monte Carlo algorithm that delivers full Bayesian inference with uncertainty measures for model parameters such as the number of clusters. We offer theoretical investigations of the clustering effects and posterior concentration results. Finally, we illustrate the performance of the model with simulation studies and a real data application for anomaly detection on a road network. The results indicate substantial improvements over other competing methods such as the sparse fused lasso.

T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs
Changwoo J. Lee Department of Statistics Texas A&M University c. c.lee@stat.. tamu. edu
Zhao Tang Luo Department of Statistics Texas A&M University ztluo@stat. tamu.
Huiyan Sang Department of Statistics Texas A&M University huiyan@stat. tamu. edu
Abstract
Graphs have been commonly used to represent complex data structures. In models dealing with graph-structured data, multivariate parameters may not only exhibit sparse patterns but have structured sparsity and smoothness in the sense that both zero and non-zero parameters tend to cluster together. We propose a new prior for high sith-immensioal parameters with graphical relations, referred to the Tree- based Low-rank Horseshoe (T-LoHo) model, that generalizes the popular univariate Bayesian horseshoe shrinkage prior to the multivariate setting detect structured sparsity and smoothness simultaneously. The T-LoHo prior can be embedded many high-dimensional hierarchical models. To illustrate its utility, we apply it regularize Bayesian high-dimensional regression problem where the regression coefficients linked by graph, so that the resulting clusters have flexible shapes and satisfy the cluster contiguity constraint with respect to the graph. We design an efficient Markov chain Monte Carlo algorithm that delivers full Bayesian inference with uncertainty measures for model parameters such as the number of clusters. We offer theoretical investigations of the clustering effects and posterior concentration results. Finally, we illustrate the performance of the model with simulation studies and real data application for anomaly detection on road network. The results indicate substantial improvements over other competing methods such as the sparse fused lasso. Code is available at https: / / thub. com/ changsoo- -LOOLOO...
Introduction
In high-ddmeensionl models such linear regressions where the number of parameters p may exceed the sample size n. it is often assumed that the parameter vector 3 E Re has many zero components, namely the sparsity assumption. This sparsity assumption allows the unknown parameter /3 to lie on low-dimensional subspace of IR", which addresses overfitting and leads to improved predictions and easier interpretations (Hastie et al., 2015). In many real-life applications, however, the parameter of interest B should be understood in a certain context where specific data structures exist, such as in many such cases, is desirable consider
time series, spatial, image, and network data analysis. another type of low-dimensional structure, where 3 is assumed to have clustered patterns and many possibly clustered zeros, which we shall call sparse homogeneity assumption.
One of the most popular models which assumes sparse homogeneity is the sparse fused lasso (Tib- shirani al., 2005) in linear regression settings. 1-D sparse fused lasso imposes é penalty on the differences of time-net same-neighboring coefficients as well as individual coefficients. The notion of "time-neighbee neieeneigg can be further generalized by considering a graph G G= with V = p so that G represents the general context or structure in which 33 should be interpreted. It leads to the generalized lasso (Tibshirani al., 201 where the penalty term now involves of pairwise differences of neighboring vertices with respect to G which facilitates B, = 93, where
[E] number
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(i.5) E E. In other words, the generalized lasso now allows neighboring coefficients with respect to the graph G to be clustered together. Other similar graph- based regularization approaches include graph OSCAR (Yang et al., 2012), grouping pursuit (Zhu et al., 2013) and graph trend filtering (Wang et al., 2016). However, when the number of edges, m, is large relative to p. regularization over the whole graph structure often faces severe computational burden. Ke et al. (2015) and Tang and Song (2016) addressed this problem by constructing a preliminary ranking of coefficients and performing a segmentation using 1-D fused lasso. Padilla et al. (2017) used depth-first search (DFS) algorithm to establish a chain graph order for constructing generalized lasso. In a spatial setting, Li and Sang (2019) used Euclidean minimum spanning tree to form the fused lasso penalty which also enjoys computational benefits. Nevertheless, these fixed chain or tree orders may not be compatible with the true cluster with respect to its context G' and hence may lead to over-clustering Besides, these aptimization-basse penalized estimators do not usually come with uncertainty measures.
Bayesian regularization methods have gained great popularity in nigh-dimensional models due to its flexibility and convenience in quantifying estimation and prediction uncertainties. There is rich literature in Bayesian high-dimensional regression models under the sparsity assumption, which can be roughly summarized into two categories: (i) spike-and-slab priors (George and McCulloch, 1993, 1997) and (ii) global-local shrinkage priors (see Bhadra et al., 2019, and references therein). A particular shrinkage prior, called the horseshoe prior (Carvalho et al., 2010), has gained a lot well as substantial computational
of attraction due to its tail-robustness and super-efficiency benefits of the global-local shrinkage prior family (Polson and Scott, 2010). However, relatively few works have been done in the of Bayesian high- -ighenimenii regression models under the sparse homogeneity assumption. Most approaches put sparsity-inducing priors directly on the pairwise differences of neighboring vertices of a graph achieve the graph-structured homogeneity of ( (Kyung et al., 2010; Shimamura et al., 2019; Song and Cheng, 2020; Kim and Gao, 2020; Banerjee, 2021). But similar to the generalized lasso, unless resorting to approximate methods such as EM algorithm, these approaches become computationally expensive to get posterior samples for general graphs with large number of edges. Another more subtle limitation of these methods is that they fail to incorporate structural assumptions among local shrinkage parameters.
In this paper, we propose Bayesian Tree-based Low-rank Horseshoe (T-LoHo) model to identify structured sparsity and smoothness of parameters whose prior structure is represented by a graph. Unlike other existing Bayesian methods which put independent priors on pairwise differences, T- LoHo extends the univariate horseshoe shrinkage prior to a multivariate setting where ,3 and its local shrinkage parameters
assumed to be piecewise constants on a graph. This low-rank structured model for local shrinkage parameters allows both clustering and sparsity effects to have strong local adaptivities. A random spanning forest (RSF) based graph clustering prior is introduced adaptively learn a compatible neighboring order to model graph partitions, which extends the recently developed random spanning tree partition models (Teixeira et al., 2019; Luo et al., 2021) to allow for possibly unconnected graphs. We show that this based prior retains model richness as its support is flexible enough to accommodate all possible contiguous partitions. We introduce T-LoHo prior to model high- -ige-dimensional linear regression coefficients, although it can be flcxibly embedded in other high-dimensional models. The resulting cluster estimates not only provide uncertainty measures but also have strong flexibility to accommodate sharp discontinuities. With state of the art computational strategies, we provide a highly efficient MCMC algorithm for posterior inference utilizing tree structures. We also study theoretical aspects of our model including posterior consistency results and its effect on clustering. We demonstrate the efficacy of T-LoHo model by using synthetic data and a real data analysis for anomaly detection on the Manhattan road network.
2 T-LoHo: Tree-based Low-rank Horseshoe Model
Consider graph G = (V, E) with |V p and |ز m which represents the pre-known structure of our parameter of interest 3 E R", For example, when 33 has a certain order (e.g. time), then we set G as a linear chain graph. When (vectorized) ,3 lies on 2-D image, we let G be 2-D lattice. A contiguous graph partition II = (CI,...,Ckk) is a disjoint partition of V such that each C2 induces a connected subgraph of G (the term graph partition will always refer to a contiguous graph partition hereafter). Under the sparse homogeneity assumption on B, the goal is to find a graph partition II with unknown size and corresponding estimate of (3 which contains many zeros. We introduce the model for B conditional on a partition II in Section 2.1 and describe the model for II in Section 2.2.

---

2.1 Low-Rank Multivariate Horseshoe Prior
First we review the horseshoe prior (Carvalho al., 2010), which provides sparse estimate of by shrinking small effects towards zero while maintaining robustness to large signals:
B {>)})=1 ~ o" di..(A........
X (0,1), T~ (0, p(o²) x 1/0²,
where (m,, V) denotes a p-dimensional multivariate normal distribution with mean m and covari-
ance V. and C+ (0, ?) denotes a half-Cauchl distribution with density p(A) = 2/ (/[ + >²/>²)) for À > 0. Here 7 is a global shrinkage parameter with hyperparameter To to enforce global shrinkage towards zero, {fy} are local shrinkage parameters with heavy tails which allow some of the Bj 's to escape the shrinkage, and x² is scaling factor which often assumed to be the noise variance.
0
0
(b)
1/v2
1/v2
U
1/
0
1/v2
3x6
TA
X
25/2
Graph G and partition + A4 1 [Cp Cg]
X
X2/2
X2/2
22/2
11
example F and cut-odgo((ashhed and cut=edge(dashed)
Another example of J
22/2
AR/2]
axs
Figure 1: Illustrative example of (a) graph partition and corresponding parameters when B R forms K = clusters, C1 = {1).C2 = {2, C) = (3,5); (b) compatible forest F and cut-edge(s).
Given graph partition II of G, seek new joint prior distribution of 3 E R2 to impose sparse homogeneity assumption while incorporating the clustering structure of II For example when y 5 and II = ((1), (2, 4), {3,5}) 5}} as shown in Figure 1(a), we seek a distribution which lies 3-dimensional subspace {B E R$ 32 = B1. B3 = }. In general, given graph partition with construct a K matrix & from I1:
size K,
kg = I/ if j C2 and 0 otherwise, k K, j I.
(1)
This K matrix d represents a projection from p-dimensional space to a reduced K -ddimensional space. Note that rows of are mutually orthonormal so that $ Ix. Using & obtained from II, we introduce the low-rank horseshoe (LoHo) prior to impose sparse homogeneity assumption on 3
B 0² A, IT ~ (0, 2,,
TT AT), A =
(2)
Ak ~ C (0,1), T~ C* ro); p(o²) x 1/0².
(3)
See fig. 1(a) for example of & and covariance matrix $ AΦ. Note LoHo introduces covariance matrix capturing clustering dependence among 3 and its marginal local shrinkage for simultaneous sparsity and fusion, key distinction from most existing methods (Carvalho et al., 2010; Kyung et al., 2010; Shimamura et al., 2019) that assume independence or only dependence among B but not local shrinkage parameters. Since K is assumed be small relative p. the covariance matrix & AΦ has low rank (i.e., rank (Φ A
K << p), and thus LoHo does not have a density with respect Lebesgue measure on R.. Instead, its distribution lies on the row space of & with dim(rowsp(()) (b) K, and we can consider the transformation = 4 so that f has N (0, x2,² density with respect to Lebesgue measure rowsp (). Observe that T is the Moore-Penrose pseudoinverse of Φ which implies & & is projection onto rowsp () that
recover B T B
By assigning a half-Cauchy prior, global shrinkage parameter 7 creates a strong pull towards zero while clusterwise local shrinkage parameters { allow some of the clusterwise 3x 's to escape the shrinkage. Assuming & having orthonormal rows is important in the sense that the effect of local shrinkage parameters (Ax k= remains same across the clusters with varying size. Thus using the projection onto the low-dimensional subspace, LoHo gives more parsimonious estimate of (3 by forming clusters of zero and non-zero parameters.
LoHo can be naturally incorporated into a linear model. With response vector y E T and column- standardized design matrix X E Raxp so that each column has unit & norm, we can write
y XB+
~~ (o,
3

---

Under this formulation, LoHo has close connection with Bayesian compressed regression (Guhaniyogi and Dunson, 2015). It randomly projects predictors X; H ΦX, with a certain family of matrix & and performs model averaging, at the cost of losing interpretability of B. But LoHo directly introduces a prior on (3 using the projection matrix & defined as (1) so that induces clustered coefficient while maintaining interpretabilityy of B3. Also, functional horseshoe (Shin et al., 2020) shrinks XB3 towards the subspace of (X) while LoHo shrinks 3 towards 0 along the (wws
We remark that, although it appears (T, A) and & handle sparsity and homogeneity separately, shrinkage component in LoHo also affects clustering by facilitating cluster fusion when signal is low and improving cluster identification when signal is high. More details are discussed in Section 3.2.
2.2 Tree-based Graph Partition Prior
Now describe how model the unknown partition II. A graph partition can be defined collection of disjoint connected subgraphs such that the union of vertices is V. To bypass the need to handle complex combinatorial graph partition problem, we consider an equivalent formulation of graph partition through edge cuts of spanning forests of G. Prop. guarantees that for any choice of partition II, there exist spanning forest F and a corresponding set of cut-edges E that induce II, ie., some edges in F can be removed so that vertices connected to each other form a cluster.
..... Ck} be a graph partition of G. Then there exists a spanning forest F (V, E with -='1= [V| The and a set of cul-edges EC C E with |E K The such that F and E induce II.
Proposition 1. Let G= (V, E) be graph with ne connected components and 11 [C1,
Proof is deferred Appendix A2. We will say spanning forest F is compatible with IT if we can construct 1I by cutting some of its edges, See Figure 1(b) for two examples of compatible F and cut-edge(s). Prop.1 suggests that to induce graph partition prior with full support, it amounts to first assigning a prior model on all possible spanning forests of G, and then assigning a prior model on all possible cut-edges sets conditional on spanning forest. When is connected spatial or spatial temporal graph, Teixeira et al. (2019) considered discrete uniform prior over all possible spanning trees. But in this case, approximate method is required sample spanning tree from its full conditional distribution due to serious inefficiency of the rejection sampler. In contrast, Luo et al. (2021) considered a random minimum spanning tree approach by assigning iid uniform random weights to the edges, so it can generate any arbitrarily given spanning tree of G and enable an exact and efficient posterior conditional sampling algorithm. Thus we follow a similar approach as in Luo et al. (2021) which leads to the following random minimum spanning forest prior on JF with full support,
F MSF(G, W), Wy Unif(O, 1). (i,5) E E, where MSF(G, W) denotes the minimum spanning forest of the graph G with edge weights W.
After F is given, selecting K --vv n. cut-edges forms a partition IT with size K. Following approaches of Knorr- Held and RaBer (2000), Feng et al. (2) and Luo et al. (2021), we introduce geometrically decaying prior distribution on K, and then select cut-edges uniformly at random given (F, K). The following prior specification completes the T-LoHo model:
Pr(K k) (1 c)*;
ne: n. + +,.....2 .P. (0
(5)
p[1 JF K) x 1(F is compatible with II and [m]=]]
(6)
T-LoHo involves two hyperparameters related to model complexity penalization. One is i (5) which, if selected to be closer to 1, strongly penalizes models with larger numbers of clusters. Another is To in (3) controlling the strength of global shrinkage. As To reduces to O, the posterior distribution of B tends to concentrate more at zero. More detailed hyperparameter sensitivity analysis and selection criteria are deferred to Appendix A5.
3 Posterior Inference and Theoretical Properties
3.1 Posterior Sampler and Computational Strategies
Here we briefly describe a reversible-jump Markov chain Monte Carlo algorithm (RJMCMC) (Green, 1995) and discuss computational strategies therein. Denote e == 03,0², A, T, II, K)F) be the set of parameters, and also denote X := x so that XB X T $33 X33 since B3 E rowsp(().

---

The posterior p(O y) is
p(Olu) (, (3 1/02 x (1+72) (1 + x
-1 (K=w.) x (1 (1-c)k x
(8)
where line (8) is the product of priors p(r) I p ( F) (W)) We draw posterior samples of fly using a collapsed RJMCMC posterior sampler as described in Algorithm 1.
Algorithm 1: One full iteration of the RJMCMC posterior sampler
Step Update II, K, F using collapsed conditional [II, K, F FIA,, T, y) where B, o² are integrated out. With probabilities (Pa: Pb, Pe: Pa) summing up to 1, perform one of the following substeps:
1-a. (splir) Propose (II*, ; === K- +) compatible with F. and accept with probability min(1, Pa Lo). where A. is prior ratio, Pa is proposal ratio, La is likelihood ratio.
1-b. (merge) Propose (II*, =
K - 1) compatible with F, and accept w.p. min [1, Ab.Pp, Pa Lo.. 1-c. (change) Propose (II*, - K) compatible with F, and accept w.p. min (1, As Pe Le).
1-d. (hyper) Update F compatible with current IT.
Step 2. Jointly update (r, (r,a2.3)) from (r,0?, ,1 A. K, by performing:
2-1. Update from [T A, 11, K, F, y] using
sampler, 2-2. Update o² from [o T, A, II, K, F, with inverse gamma distribution,
2-3. Update 33 from 0 A, II, K, F, y) with a multivariate normal distribution.
Step 3. Update A from |A Tr 3, IT, K,F, Fy) using a slice sampler.
When X I, (i.e., normal means model), it is possible integrate out instead of a²; see Appendix A1.
current partition and F
(1-+] splis, remowing
(1 b) merge, acding b
(1 <) hyper, changing."
Figure 2: Illustration of step in Alg.1. 1. Step (1-c) corresponds to performing (1-a), (1-b) sequentially.
Step updates cluster assignment by proposing one of the four moves (fig. 2): see Appendix A1 for details acceptance probabilities. Here instead of using the full conditional distribution, use the collapsed conditional distribution [II, K,J, T, y] where (3,a²) are integrated out to calculate the likelihood ratio L which significantly improves mixing. Specifically, the collapsed conditional [II, FIA, r, y] is proportional to (
(y T y/2) n2/2 where Σ I, + XXXX so that
Σ 1/2 (y Σ 1y2)))
Likelihood ratio
Σ 1/2(1)) Σ g 22)
Here superscript indicates the proposed parameters. Step 2 jointly updates [T, 0² -1 [o-]r,- x [ 2², -I following the approach of Johndrow et al. (2020). Finally, step updates local shrinkage parameters A using the slice sampler (Neal, 2003; Polson et al., 2014).
One demanding computational bottleneck is the likelihood ratio calculation that involves Σ-1 and [Σ]. notable advantage of T-LoHo is that it projects X to a low-dimensional space under the sparse homogeneity assumption, leading to an n by transformed design matrix X x where formula,
typically K << Applying Sherman- Woodbury-Moritn
easily calculate
-ー (I, + - XAX
L, X(7 2 + X
by reducing the rank of the inverting matrix from to K. Furthermore, utilize Cholesky decomposition R A- + X X to efficiently calculate E-1 and |Σ]. Once we have right triangular R. calculation of - only involves backward substitution, and also we can calculate [ no extra cost using the matrix determinant lemma. A naive implementation of the above likelihood
5

---

XTXXX X and its Cholesky factor R for each calculation would require to repeatedly - + --
MCMC step, except in steps (2-2) and (2-3) where we use E-1 and R calculated from step (2-1) respectively via Rue (2001)'s algorithm. For instance, step has a new X'=X =X and steps (2-1) and 3 have a new T" or A Alternatively, we propose to directly update R from its previous value. For step 1 where X X changes, we use Cholesky rank-1 update/downdate (Golub and Van Loan, 2013, Sec. 6.5.4) which reduces computational cost from ( (nK2, k*)) to O(K2). For steps (2-1) and 3 where the diagonal part changes, we present direct algorithm (see Alg. 2 in Appendix A)) for updating the corresponding Cholesky factor. These Cholesky updating schemes prove to be simple yet powerful computational strategies MCMC typically requires many iterations.
Excluding step (I-d), the total computational cost of Alg. 1 is O( max(nK, K))). compared the direct computation of Σ and |Σ] which leads to ((n)), Step (1-d) takes (m log p) construct MSF where m is the number of edges in G. Note that step 1-d (hyper) is selected with probability Pa at each iteration. We suggest a small value of pa such as 0.05, so that it would save computation time and give RJMCMC enough iterations to explore the partition compatible with the current MSF F.
3.2 Clustering Effect of T-LoHo
In this section, we investigate how T-LoHo prior differs from the Gaussian prior in terms of the effect on clustering. We focus on the sparsity of edge differences because of its important role in clustering. Examples include l (Tibshirani et al., 2011) and Eo penalties (Fan and Guan, 2018) on 13,-3, (i, E E}. Existing Bayesian methods seek sparsity of 3, - 3, by putting suitable prior catll--pponnntllggaanna
distributions on edge differences, such as Laplace (Kyung et al., 2010), (Shimamura et al., 2019), student's t (Song and Cheng, 2020; Banerjee and Shen, 2020), spike- and-slab (Kim and Gao, 2020), and horseshoe (Banerjee, 2021). But the aforementioned Bayesian methods have several limitations: (i) an additional post-processing step is often required due to the lack of explicit cluster estimates; (ii) sparsity assumption cannot be easily incorporated into their methods; and (iii) posterior inference method is either inefficient or inflexible (e.g., relying on a single F) when the underlying graph G has many edges. In contrast, although T-LoHo does not put sparsity-inducing priors directly on edge differences, it overcomes all these limitations and effectively finds clusters by its flexible low-rank structure. Below, we show that the use of horseshoe prior not only introduces shrinkage of /3 but also has a less obvious but profound clustering effect to facilitate homogeneity pursuit.
To analyze the effect of T-LoHo prior on clustering, we focus on the simple case when X = I, so that observations Y/i are independent and normally distributed, i.e., y,, o² ~ (B, o²), i 1, 1,...y Without loss of generality, consider the merge step (1-b) where the comparison between the proposed merged model M, := (II*, K 1) by combining two existing clusters Ci2 C2 and the current model M2 := (II, K) is made:
M1 mean of {y: = un #2 mean of (iitee, v.S. .M M1 + #2
We analyze the acceptance probability min A AA p. L} in step (1-b) of Alg. 1 because it is crucial in the clustering mechanism. The term A P is nothing but 1/(1 - c) which reflects the model size penalty imposed by p(K). The key part is the likelihood ratio L. where the different choice of prior on B (equivalently cluster mean μ4) leads to the different L under the same data. This likelihood ratio corresponds to the Bayes factor (Kass and Raftery, 1995) of the Bayesian two-sample test (Gönen et al., 2005). Thus, here we compare the Bayes factor BF12 = p(data) MM1) M1)/ (ddtta),2)) under the normal and T-LoHo prior respectively to analyze their effects on clustering.
Following the formulation of Bayesian two-sample t test, priors are reparametrized as (5, pz o²) := ((m - ((n-#2))oo (i + p2)/2,, o²) where the standardized difference 8 5= (11 //2)/a is the parameter of interest. Here we assume a noninformative prior on nuisance parameters p( xx 1/o², since
otherwise Bayes factor is no longer function of two-sample statistics ( and (n1, m22)::
1= (リ) (tpp /nx), og = ((m) 1)s² + (n2 - 1)x²) /v,
7i (nj + +mz 1
where nu+ = [Cx,, v = nu + - 2, and Uk. st are the sample mean and variance of group k, k = 1.
is obvious that independent normal priors on le (with variance scaled with σ²2) leads to a normal
prior on â as well. When 5 ~~n~NN7 (00 1), the Bayes factor BF
12 (Gönen et al., 2005) is
(1 + 2/v) - (1+1)//
pddata 5 = 0. p. o )p(() 0² d(p,.
BF =
J pdataa 8, n. ((, F, o² )d(o 02) (1 + 12) 1/2 /2 [M[1 + +nn))] (v+1)//2
-
6

---

Now if we change the priors on μr and 22 from independent normal to independent horseshoe distributions, induces the heavy-tailed prior Ta on ó which is convolution of two horseshoe priors: Proposition 2. Let detsH,( = Snx o2= (AJo, 1)d be a horseshoe prior. If μr ~u THS(a,T) Ti) and μ22 ~ THs(a,Ta) T2) independently, then it induces a distribution of the standardized difference 6 == (m1 p22 given TI, 72, denoted T ( T2), which can be wrilten as a scale mixture of normal with mixing distribution Jw(w) where w > 0:
(0( / N(00 w) (w(w)dwww fw(w)
1 π
TI
2 +
12
+ 72
+ + 7 + 73)
1
Proof is deferred to Appendix A3, See left panel of fig. 3 for the graphical illustration of T (6(())) (6 1).
Its tail behaves similarly with the Strawderman- Berger prior (Strawderman, 1971; Berger et al., 1980). By Proposition 2, the Bayes factor BF under the prior induced by horseshoe ó ~ ( TI 72) is
(1+ (u+1)/2
BF
(1+
1/2 (1 + 11 + nsw)]} (u+1)/2 sw (w))w
Horseshoe
70 m5
nu 10
nu 20
Prior
Bayes
Horseshce
0.
24
Normal
absolute value of ttattiscc
Figure 3: (Left) Joint density fxx y) = (H)(T)) overlaid with marginal density T - y) shown as red, when 71 72 = 1. (Right) Comparison of 1F as a function of [t] under different (11,22) settings. Higher Bayes factor implies favoring one-group Mi 141 f12-
Under the normal and Ta priors on 6, we compare 1F as function of [4] when the group sizes are (i) balanced, n1 n2g; (ii) unbalanced, n1 : n2 = 9 with v E (5, 10, 20), and display results at the right panel of fig. 3. Since arbitrary choice of scale leads to the different BF, set ~ N(O, 1) which corresponds to the unit information prior (Kass and Wasserman, 1995) and choose the scale of 8 ~ Ta such that median of scale mixture distribution fw(w) becomes 1. See Appendix A3 for details of specific choices of (71, 72) under different settings of (n1, n2). Although this is not the only possible scale matching criterion, it is reasonable choice for fair BF comparison so that we can focus on different origin/tail behavior of TA compared to the normal distribution.
When |t] is small to moderate, we can see that BF generally greater than BFT except for the case when n& is large (balanced, large v/) and |t] is small (in which case large BF12 in both models leads to accepting merge proposals anyways). This implies the prior ó FA more strongly favors the one-group Mi over the two- wwo-rrupp M2 compared to the normal prior 5 ~ NO. 1). This can be explained by the fact that, under M2, the heavy-tailed prior TA anticipates large effect size priori compared to the normal prior. Thus T-LoHo facilitates cluster fusion when [t] is small to moderate.
Now when |4] is large, we can that TA more strongly favors M2 compared to the normal prior, and the difference becomes more noticeable when group sizes are small and unbalanced. In fact, when (ni, n2) are fixed, BF12 converges to 0 as |t| oc whenever v 2 but BFT, never converges to O and is lower bounded by (1 + n2) -w/2 > O, which is also known as the information paradox (Liang et al., 2008). This finite sample consistency is important since it allows the model to identify the (small, unbalanced) cluster with a high signal difference, which might not be possible under the usual normal prior because the penalty term K) (1 c) may overwhelm it.
In summary, compared to the normal prior, T-LoHo tends to reduce redundant cluster representations (when |t| is small) while better capturing the highly significant cluster differences (when |t] is large).
7

---

3.3 Posterior Consistency Results
Notations. Let ((",, f oo)) denote the true B. 3 and respectively. Let [j E V 88 00}
denote the true active set of indices. Let I'I denote an arbitrary partition of = {1, ... PD) whose corresponding partition of 5" is determined by removing those edges with 3 33 > 0 from the
subgraph of any F compatible with Iî at vertex set 5" We define 9 maxn [i((")) among all possible IT. Let Pn denote all unique partitions that have at most 9 (1 + cs) clusters and their corresponding partitions of 5" are nested in the true partition of g" for some constant cs > 0.
Below, we consider the case when p can be much larger than n and establish posterior concentration results for the T-LoHo model as n goes to infinity, Our results rely on the following assumptions:
(A-1) The graph satisfies 9. < logp. p. n. = o(g,),, and log Pr.l = Olgn logg
(A-2) All the covariates are uniformly bounded. There exists some fixed constant λ > 0, such that Amin (X 2 nλo for any partition in Pr..
(A-3) max; 1331/0" < L, where log L) = O(log)).
(A-4) logT O(logp), T < p (2+err) V In log
2 p p and
mi
o (12(1 TT for some positive constants Cr, Co. and Co.
Assumption (A-1) is a regularity condition on G such that the resulting space of spanning forests is not too large. Assumption (A-2) is a commonly adopted condition on design matrix in high- dimensional linear regressions. Assumption (A-3) bounds the growth rate of the standardized true coefficients. Assumption (A-4) is a condition on the prior distributions of T and o² as well as choice of hyperparameter c. The proof of Theorem is given in the Appendix A4.
Theorem 1. (Posterior contraction) Under Assumptions (A-I) to (A-4), there exists large enough constant M1 > 0 and En x /9t. log p/n n such that the posterior distribution satisfies Ta (I| f ||2 Mi I S exp(-cine2) with probability - exp(- for some con-
stants C1 > 0 and C2 > O.
4 Numerical Examples
4.1 Simulation Studies
We conduct a simulation study to demonstrate the utility of our model. Motivated by the scalar- on-image regression problem, we consider a similar setting as Kang al. (2018). We construct 30 x 30 lattice graph which represents structure of 2-D image. Column-standardize predictors X; E 900 i I..... 100 are generated from mean zero Gaussian process with kernel exp(-ddp /d)/ where dz is the distance between pixels j and I, 0 is the range parameter
image
K [(r,, =1) with 1 = 0 indicating no dependence. True coefficient / E 12 is sparse (84% are zero) and has irregular cluster shapes with sharp discontinuities as shown in fig. 4(a). We let SNR E {2, to set error variance 2² = Var(X /NR and generate scalar responses y E IR 100 by y ~ ((X3,o
We compared our model with the soft-thresholded Gaussian process (STGP, Kang et al., 2018), sparse fused lasso on graph (FL,, Tibshirani et al., 201 I; Wang et al., 2016), graph OSCAR (GOSCAR, Yang al., 2012), and Bayesian graph Laplacian (BGL, Chakraborty and Lozano, 2019). We used mean squared prediction error (MSPE) with test set size 1000 to measure the predictive power and Rand index (RI) (Rand, 1971) measure the clustering accuracy. For T-LoHo and STGP, we collected 4,000 posterior samples after 10,000 burn-in with 10 thin-in rate. For T-LoHo, we calculated the posterior median estimate of (3 and the cluster point estimate of using Dahl (2006)'s method. For STGP, posterior mean estimate of /3 is used, and Rand index is calculated based on the binary classification tzero/non-zero using posterior thresholding probabilities. For FL, the two tuning parameters are selected among the fixed candidate set of tuning parameter ratio YFL E {0.2, 5] using the Bayesian information criterion. The T-LoHo and FL results presented here are when (ro,c) c) (1, 0.5) and yFF,. = 0.2 respectively; the hyperparameter sensitivity analysis of T-LoHo and the detailed settings of other models are available in Appendix A5. All computations were performed on Intel ES-2690 v3 CPU with 128GB of memory.
8

---

True 8
(b) T-LoHo
STOP
15
Fused Lasso
GOSCAR
(1) BGL
0.0
45
15
= (0, 4). (a) True coefficient image Bü (b) T-LoHo estimate with (To, c) = (1, 0.5); (c) STGP estimate after thresholding: (d) FL. estimate with tuning parameter ratio "FL 0.2; (e) GOSCAR estimate; (f) BGL estimate.
Figure 4: True and fitted results when (0R)
Table Performance comparison based on average MSPE and Rand index (RI) over 100 replicated simulations. Standard error is given in parentheses and time is in seconds. RI = indicates exact recovery of the true cluster.
D
SNR
T-LoHo
STGP
FL
GOSCAR
BGL
2
68.5(3.0)
93.4(1.7)
85.0(2.0)
(38.2(0.6)
(36.2(0.6)
O
4
24.4(2.0)
86.3(1.6)
55.8(1.4)
133.6(0.6)
132.3(0.6)
MSPE
3
2
251.0(11.2)
278.0(5.3)
341.0(13.0)
532.3(8.4)
483.2(6.0)
3
4
59.7(2.3)
163.9(2.2)
115.8(3.6)
335.0(4.8)
213.4(2.7)
0
2
0.88(0.006)
0.72(0.009)
0.47(0.012)
0.28(0.000)
0.29(0.000)
0.95(0.005)
0.72(0.010)
0.46(0.007)
0.28(0.000)
0.29(0.000)
RI
3
2
0.87().004)
0.79(0.004)
0.58(0.012)
0.28(0.000)
0.29(0.000)
3
0.95(0.002)
0,80(0.003)
0.57(0.010)
0,28(0.000)
0.29(0.000)
Time 0
4
107.9(0.4)
339.9(1.7)
110.4(0.6)
0.11(0.003)
956.2(2.3)
From fig. 4, we can see that T-LoHo successfully captures the irregular shape of cluster boundaries and sharp discontinuities. STGP gives much more smoothed estimate (which is expected because it does not assume homogeneity), and FL estimate contains many falsely identified non-zero clusters. The superior performance of T-LoHo over FL partly attributed to (i) the of horseshoe that reduces bias in FL, and (ii) the use of RSF-based prior which more efficiently searches non-zero edge differences from spanning forest instead of full graph G used in FL. Table shows that in all (0,SNR) settings, T-LoHo indeed outperforms other models in terms of both predictive and clustering accuracy. GOSCAR and BGL give very similar results as their penalty functions have similar octagonal shapes, and both perform poorly in prediction and result in partitions with (nearly) all singletons. It is partly because GOSCAR and BGL allow the coefficients within the same cluster having similar magnitudes but with different signs. Additional simulation studies with more non-zero clusters are available in Appendix A5.
4.2 Anomaly Detection in Road Networks
We applied T-LoHo the problem of detecting anomalies in road graphs. NYC Pride March is an annual event held in every June in Manhattan, New York. As the march causes traffic congestion along the route, Wang et al. (2016) considered the problem of detecting clusters on the Manhattan road network which have different taxi pickup/dropoff patterns from usual. We constructed the road network graph using GRASS GIS (GRASS Development Team, 2020) and got 3748 nodes (junctions) and 8474 edges (sections of roads). Following Wang et al. (2016), considered the event held in

---

2011 (12:00-2:00 pm, June 26th) and processed the number of taxi pickup/dropofi counts data to the nearest nodes with log transformation. A log baseline seasonal average was calculated from the same time block 12:00-2:00 pm the same day of the week across the nearest 8 weeks. Then it is plausible to assume that the difference between log counts on event day and log baseline seasonal average has many zeros and clustered patterns over the graph.
We fit T-LoHo and FL and compare the results. For T-LoHo, (To, = (1, 0.8) were used collect 5000 posterior samples after 1.5 x 10 burn-in with 10 thin-in rate. For the FL estimate, we followed Wang et al. (2016)'s ss specification where the regularizaton parameter in the fused term was chosen such that the model has 200 degrees of freedom and the one in the sparsity term is set as 0.2.
Eventlocatoon
Unfitered Signal
T-LoHo post median estimate
Fused Lasso estimate
46.85-
logd
150bu0c
43.00
5it Aue &
6.700
-24000
-12.25
-34.00
-722223
-14.223
-34.00
lnnghuee
longituse
longitude
IongRude
Figure 5: (Left two panels) 2011 NYC pride event route and unfiltered signal. Log- dof-difference value below 0 indicates lower pickup/dropoff frequency than usual; (Right two panels) T-LoHo and FL estimates; (Bottom right subplots) Fitted value comparison zoomed along the parade route, 5th Ave. & 9th St. to 5th Ave. & 36th St. Here mark x indicates unfiltered signal value, red dot indicates estimated value, and red line indicates 90% credible interval for T-LoHo estimate.
Figure shows the fitted results of two models. Both successfully capture the decreased taxi activity along the parade route and slightly increased taxi activity around the starting/ending point of the parade. From the subplots, can that FL biased because of soft-thresholding (Rinaldo et al., 2009) while T-LoHo appears to be less biased and capable of producing reasonable uncertainty measures. notable difference is T-LoHo can capture the decreased taxi activity around the lower Manhattan area while FL cannot due to the bias. In summary, T-LoHo gives better insight on how taxi activity changes when such event occurs.
Concluding Remarks
We propose a Tree-based Low-rank Horseshoe (T-LoHo) model to carry out Bayesian inference for graph-structured parameter which is assumed be sparse and smooth. Accompanied with theoretical grounds and computational strategies, our simulation studies and real data example demonstrate that T-LoHo outperforms other competing methods such as fused lasso high-dimensional linear regression context. Extensions to other types of high-dimensional models are possible. In addition, following similar model construction spirit T-LoHo, can build general class of tree-based low-rank sparse homogeneity model extending other global-local shrinkage priors (Polson and Scott, 2010). Another scenario not addressed this paper is when we have a weighted graph G (V, E. Wo) as parameter structure. In this case, incorporating priori edge weight Wo T-LoHo is a nontrivial but interesting future research question which might be useful for many possible real data applications. This work does not present any foreseeable societal consequence, users must fully aware of the context represented graph G when giving interpretation on clustered parameters to avoid any misleading conclusions.
PPublicly available from NYC Taxi & Limousine Commission website, CCO.
10

---

Acknowledgments and Disclosure of Funding
The research was partially supported by NSF DMS-1854655, NSF CCF- 193494 and NIH R01AG064010. The authors thank the referees and the area chair for valuable comments.
References
Banerjee, (2021). arXiv:2102.0737.
Horseshoe shrinkage methods for Bayesian fusion estimation.
arXiv preprint
Banerjee, and Shen, (2020). Graph signal denoising using t-shrinkage priors. arXiv preprint arX6v:2012.1366.
Berger, al. (1980). robust generalized bayes estimator and confidence region for a multivariate normal mean. Annals of Statistics, 8(4):716-761.
Bhadra, A., Datta, J., Polson, N. G., Willard, B., et al. (2019). Lasso meets horseshoe: A survey. Statistical Science, 34(3):405-427.
Carvalho, C. M., Polson, N. G., and Scott, J. G. (2010). The horseshoe estimator for sparse signals. Biometrika, 97(2):465-480.
Chakraborty, S. and Lozano, A. C. (2019). A graph laplacian prior for bayesian variable selection and grouping. Computational Statistics & Data Analysis, 136:72 91.
Dahl, D. B. (2006). Model-based clustcring for expression data via dirichlet process mixture model. Bayesian inference for gene expression and proteomics, 4:201-218.
Fan, Z. and Guan, L.. (2018). Approximate to fo-penalized estimation piecewise-constant signals on graphs. The Annals of Statistics, 1611733337733245
Feng W., Lim, C. Y.. Maiti, T., and Zhang. Z. (2016). Spatial regression and estimation disease risks: clustering-basee based approach. Statistical Analysis and Data Mining: The ASA Data Science Journal, 4617 434.
George, F. I. and McCulloch, R. E. (1993). Variable selection via gibbs sampling. Journal of the American Statistical Association, 88(423):881-88)
George, E. L. and McCulloch, R. (1997). Approaches for Bayesian variable selection. Statistica sinica, pages 339-373.
Golub, H. and Loan, C. F. (2013). Matrix computations, volume JHU press.
Gönen, M., Johnson, W. O., Lu, Y., and Westfall, P. H. (2005). The Bayesian two-sample test. The American Statistician, 59(3):252-257.
GRASS Development Team (2020). Geographic Resources Analysis Support System (GRASS GIS) Software Open Source Geospatial Foundation, USA.
Green, P. (1995). Reversible jump markov chain monte carlo computation and Bayesian model determination. Biometrika, 22(4):111-732
Guhaniyogi. R. and Dunson, D. B. (2015). Bayesian compressed regression. Journal of the American Statistical Association, 1100512):150011555 1514.
Hastie, T., Tibshirani, R., and Wainwright, M. (2015). Statistical learning with sparsity: the lasso and generalizations. CRC press.
Johndrow, J. E., Orenstein, P., and Bhattacharya, (2020). Scalable approximate meme algorithms for the horseshoe prior. Journal of Machine Learning Research, 21(73);1-61.
Kang, Reich, B. J., Staicu, A.M. (2018). Scalar-on-imen image regression soft-thresholded Gaussian process. Biometrika, 105(1):165-184. code available at https://www4... nesu, wcw..edu/uee.......oo bddu"/jreich/// software.
Kass, R. E. and Raftery, A. E. (1995). Bayes factors. Journal of the american statistical association, 90(430).773 795.

---

Kass, R. E. and Wasserman, L. (1995). A reference bayesian test for nested hypotheses and its relationship to the schwarz criterion. Journal the american statistical association, 90(431):928-934,
Ke, T., Fan, and Wu, (2015). Homogeneity Pursuit. Journal of the American Statistical Association, 110(509):155-194,
Kim, Y. and Gao. C. (2020). Bayesian model selection with graph structured sparsity. Journal of Machine Learning Research, 21(109):1-61.
Knorr-Held, L. and Raßer, G. (2000). Bayesian detection of clusters and discontinuities in discasc maps. Biometrics, 56(1):13-21.
Kyung, M., Gill, J., Ghosh, M., Casella, G., et al. (2010). Penalized regression, standard errors, and Bayesian lassos. Bayesian Analysis. 5(2):369-411.
Li, F. and Sang, H. (2019). Spatial homogeneity pursuit of regression coefficients for large datasets. Journal of the American Statistical Association, (14(52)):1000- 1062.
Liang, F., Paulo, R., Molina, G., Clyde. M. A.. and Berger. J. O. (2008). Mixtures of g priors for Bayesian variable selection. Journal of the American Statistical Association, 103(481):410-22)
Luo, Z. T., Sang, H., and Mallick, B. (2021). A Bayesian contiguous partitioning method for learning clustered latent variables. Journal of Machine Learning Research, 22(37):1-52.
Neal, R. M. (2003). Slice sampling. Annals of statistics, pages 705-741.
Padilla, O. H. M. Sharpnack, J., Scott. J. G.. and Tibshirani. R. J. (2017). The DFS fused lasso: Linear-time denoising over general graphs. J. Mach. Learn. Res., 18:176-1.
Polson, N. G. Scott, G. (2010). Shrink globally, act locally: Sparse Bayesian regularization and prediction. Bayesian statistics, 95501-538):00.
Polson, N. G., Scott, J. G., and Windle, J. (2014). The Bayesian bridge. Journal of the Royal Statistical Society:
Series B: Statistical Methodology, pages 713-733.
Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336):846
Rinaldo, A. et al. (2009). Properties and refinements of the fused lasso. Annals of Statistics, 37(5B):2922-299
Ruc, H. (2001). Fast sampling of Gaussian markov random fields. Journal of the Royal Statistical Society:
Series B (Statistical Methodology), 63(2)3325-338.
Shimamura, K., Ueki, M., Kawano, S., and Konishi, S. (2019). Bayesian generalized fused lasso modeling via neg distribution. Communications in Statistics- Theory and Methods, 48(16):4132 41533
Shin, M., Bhattacharya, A., and Johnson, V. F. (2020). Functional horseshoe priors for subspace shrinkage. Journal of the American Statistical Association, 115(53))17844-1999)
Song, Q. and Cheng, G. (2020). Bayesian fusion estimation via t shrinkage. Sankhya A, 82(2),353-385
Strawderman, W. F. (1971). Proper bayes minimax estimators of the multivariate normal mean. The Annals of Mathematical Statistics, 4281)3885-388
Tang, L. and Song. P. X. (2016). Fused lasso approach in regression coefficients clustering: learning parameter heterogeneity in data integration. The Journal of Machine Learning Research, 17(1):3915-3 -93377
Teixeira, I. V., Assunção, R. M., and Loschi, R. H. (2019). Bayesian space-time partitioning by sampling and pruning spanning trees. Journal of Machine Learning Research, 20(85):1-35.
Tibshirani, R., Saunders. M., Rosset, S., Zhu, J., and Knight, K. (2005). Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(1):91-100
Tibshirani, R. J., Taylor, J., et al. (2011). The solution path of the generalized lasso. The Annals of Statistics, (0(3):333--1377
Wang. Y.X.., Sharpnack, J.. Smola, A. J., and Tibshirani, R. J. (2016). Trend filtering on graphs. Journal of Machine Learning Research, 17(105):1-41.
Yang, S., Yuan, I.,, Lai, Y.-C., Shen, X., Wonka, and Ye, J. (2012). Feature grouping and selection over an undirected graph. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 922-930.
Zhu, Y., Shen, X., and Pan. W. (2013). Simultaneous grouping pursuit and feature selection over an undirected graph. Journal of the American Statistical Association, 108(502):713-755
12


Reviews:
[{"review_id": "zr-zLrkBics", "reviewer": "Reviewer_M78Z", "summary": "This paper propose a new prior referred to as Tree-based Low-rank Horseshoe (T-Loho), which can incorporate relationship among variables as a graph.\nTheoretical characteristics of the clustering effects and posterior concentrations are investigated.\nIn computational experiments based on both synthetic and real-world data, T-Loho turned out to be superior to fused lasso and soft-thresholded Gaussian process in terms of both regression performance and support recovery.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is presented with in-depth technical details, and therefore not easy to read from time to time.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In computational experiments, comparison to Bayesian fused lasso is missing. \nMore experiments demonstrating the power of tree-based graph partition prior are expected.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "xr0SiGzimBy", "reviewer": "Reviewer_ESxP", "summary": "The authors propose a multi-dimensional horseshoe prior for Bayesian inference that enforces clustering of the (non)zero parameters. The main contribution of the paper is to make this approach more flexible, feasible and computationally efficient.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\nImposing structured sparsity can have many practical applications and making this computationally feasible may have a great impact on the community. The inclusion of the scheme in a Bayesian inference setup has many advantages from the theoretical perspective. The paper is technically sound and the proposed method comes with posterior consistency guarantees.\n\nweaknesses:\nThe possibly unconvincing side of the paper is the value of its net contribution compared with the state-of-the-art. It is not clear if similar graph-structured priors have never been used in Bayesian learning and if their use to enforce parameter structured smoothness is new. A technical novelty of the paper is to go beyond the piecewise constant assumption of existing shrinkage approaches. The authors could have explained more explicitly what is the technical challenge of this extension. From what the authors write in Section 2, it looks like the key contribution relies on the inclusion of a new covariance matrix in the horseshoe prior (as the partition approximation scheme seems to be taken from previous work). The authors should explain better how this leads to the claimed computational advantages.\n\nquestions:\n- One of the main motivations of this work is the fact that \"fixed chain or tree orders may not be compatible with the true order with respect to its context G\". How is the order-within-a-context defined?\n- Are there examples of feasible or quasi-feasible regularization schemes that take into account the whole graph structure? \n- How are the theoretical results listed at the end of Section 1, e.g. posterior consistency, different from standard guarantees that can be obtained with other Bayesian methods? \n- What is a practical situation where a multi-dimensional parameter needs to show some sort of graph-neighbour continuity?\n- The proposed covariance matrix is claimed to capture at the same time fusion and sparsity. Is this obtained by including a tunable diagonal factor?\n- The goal of the new graph-clustering prior is to allow non-connected components in the graph. How does this come from the proposed form of the covariance matrix? And why is this important from an applications point of view?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the paper, I could not find any comment about the potential negative societal impact of the results. On the other hand, I can hardly think about social issues related to this work, except for possible unfair effects on the obtained models coming from a naive graph-based selection process of the model parameters.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "74hKVwhoUUD", "reviewer": "Reviewer_M8yM", "summary": "The paper proposes a new prior for high dimensional parameters with graphical relations. It can be regarded as an extension of univariate horseshoe shrinkage prior to multivariate setting by borrowing ideas from studies on homogenous sparse priors and tree-based graph partition prior. The paper describes posterior sampling strategy with efficient implementation details and theoretical guarantees. In the end, the paper demonstrates its methods via both simulated and real data experiments.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper extends the widely used univariate horseshoe prior to multivariate case. The task itself is not new and some of the ideas have their roots in previous literatures, however, the paper combines them in a non-trivial way. By introducing the low-rank structure for prior distribution, the paper naturally incorporates cluster information into prior. Then the paper uses the random minimum spanning tree approach introduced by [1] to model the partition prior. The remaining computation and theoretical proof techniques are borrowed from previous literatures. But the way they are combined are novel.\n\nThe paper is technically sound. The methods are clearly stated, and details of efficient implementation are included. The theoretical results are rigorously proved. In addition, the author uses simulation studies to demonstrate the benefits of their proposed methods compared with other widely used approaches. The simulation results are adequately interpreted. Besides, the author(s) also demonstrate(s) the method via real data application.\n\nThe paper is clearly written and well-written. Many informative figures are much appreciated. The details of method and experiments are described clearly. With that being said, the section 3.2 is a bit hard to follow. I think it will be better if the author(s) can give more high-level intuitive explanation.\n\nGiven the task of the paper is widely attractive, the Bayesian approach offered by the paper will be interesting to many researchers and practitioners. The method given by the paper is new and the benefit of it is shown by well-designed experiments. With that being said, most of results and techniques seem to be borrowed from somewhere else, and thus may not be surprising.\n\n[1] Zhao Tang Luo, Huiyan Sang, and Bani Mallick. A Bayesian contiguous partitioning method for learning clustered latent variables. Journal ofMachine Learning Research, 22(37):1–52, 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "46x89_yXA0b", "reviewer": "Reviewer_A5dn", "summary": "The authors generalize the univariate Bayesian horseshoe shrinkage prior to the multivariate setting and propose a new prior that detects sparsity and encourages smoothness within clusters of variables. The paper illustrates the application of the prior in Bayesian regression and present an MCMC algorithm. Numerical experiments with synthetic data and results with one real dataset illustrate the potential advantages over alternative methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written. The proposed prior is novel and the authors develop an efficient reversible jump MCMC sampler. The discussion on clustering effects provides valuable insights into the nature of the proposed prior and the authors provide a posterior contraction result.\nThe weaker parts of the paper are the discussion of related work and the simulation experiments. \n\n(1) The proposed method is compared against only two baselines, with one dating from 2005. Although fused lasso should definitely be included as a classical baseline, I think there are many alternatives for problems of this kind. Are the authors suggesting that there has been little interest in the analyzed problem and that there has only been one suitable competitive method proposed in the past decade? I would think that network lasso [R1] and its derivatives, the graph-based regularization of [R2], OWL and OSCAR regularization, and Bayesian graph Laplacian regularization [R3] would be candidate alternative methods. \n\n(2) The synthetic experiments only explore a scenario of two clusters. The problem would seem to be much more complex when there are multiple clusters in the data. The algorithm appears to perform well for the real data-set (where it appears to identify more clusters). Results for synthetic experiments with more clusters would provide insight into the behaviour – it’s not clear if many more iterations are required for a satisfactory exploration.\n\n[R1] Hallac, David, Jure Leskovec, and Stephen Boyd. \"Network lasso: Clustering and optimization in large graphs.\" Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 2015.\n\n[R2] Li, Yuan, et al. \"Graph-Based Regularization for Regression Problems with Alignment and Highly Correlated Designs.\" SIAM J. Mathematics of Data Science 2.2 (2020): 480-504.\n\n[R3] Liu, Fei, et al. \"Bayesian regularization via graph Laplacian.\" Bayesian Analysis 9.2 (2014): 449-474.\n\n** AFTER AUTHOR RESPONSE\n\nMy main concern with the paper was the inadequate comparison to other methods for addressing the same problem. In their response, the authors have indicated that they will include comparisons to several more recent baseline methods, and they have included results for preliminary experiments, which indicate that the proposed method provides a meaningful improvement. If the paper is revised to include more extensive experimental comparisons (which constitutes a relatively minor change), then I would consider it a valuable technical contribution. I have modified my recommendation to \"good paper, accept\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agree that the paper makes novel and valuable contributions. One the main concerns of the reviewers was that the paper was missing a sufficiently compelling discussion of how the method proposed in the paper compares with the state of the art, and an experimental comparison with more alternative methods. The responses to the different reviewers addresses well these concerns. The authors are strongly encouraged to include the new experimental results and the elements of discussion provided in the final version of the paper. 
Decision: Accept (Poster)