  We study the graph signal denoising problem by estimating a piecewise
constant signal over an undirected graph. We propose a new Bayesian approach
that first converts a general graph to a chain graph via the depth-first search
algorithm, and then imposes a heavy-tailed $t$-shrinkage prior on the
differences between consecutive signals over the induced chain graph. We show
that the posterior computation can be conveniently conducted by fully exploring
the conjugacy structure in the model. We also derive the posterior contraction
rate for the proposed estimator, and show that this rate is optimal up to a
logarithmic factor, besides automatically adapting to the unknown edge sparsity
level of the graph. We demonstrate the excellent empirical performance of the
proposed method via extensive simulation studies and applications to stock
market data.
