Multiresolution Representations for Piecewise-Smooth Signals on Graphs

What is a mathematically rigorous way to describe the taxi-pickup distribution in Manhattan, or the profile information in online social networks? A deep understanding of representing those data not only provides insights to the data properties, but also benefits to many subsequent processing procedures, such as denoising, sampling, recovery and localization. In this paper, we model those complex and irregular data as piecewise-smooth graph signals and propose a graph dictionary to effectively represent those graph signals. We first propose the graph multiresolution analysis, which provides a principle to design good representations. We then propose a coarse-to-fine approach, which iteratively partitions a graph into two subgraphs until we reach individual nodes. This approach efficiently implements the graph multiresolution analysis and the induced graph dictionary promotes sparse representations piecewise-smooth graph signals. Finally, we validate the proposed graph dictionary on two tasks: approximation and localization. The empirical results show that the proposed graph dictionary outperforms eight other representation methods on six datasets, including traffic networks, social networks and point cloud meshes.