This paper proposes an adaptive multiscale decomposition algorithm for graph signals. We develop two types of graph signal cost functions: α-Sparsity functional and graph signal entropies, to capture the energy compaction of the signal components. The adaptive decomposition can then be constructed by applying a minimum cost constraint during the full subband decomposition. The proposed adaptive decomposition is shown to outperform graph wavelet decomposition in compressing nonpiecewise constant graph signals.