Oversampled bipartite graphs with controlled redundancy

This paper extends our previous work on graph oversampling for graph signal processing. In the graph oversampling method, nodes are duplicated and edges are appended to construct oversampled graph Laplacian matrix. It can convert an arbitrary K-colorable graph into one bipartite graph which includes all edges of the original graph. Since it uses a coloring-based algorithm, performance of graph signal processing depends on the coloring results. In this paper, we present graph oversampling based on a few different graph bipartition methods which use maximum spanning tree and eigendecomposition. Furthermore, we consider the effective selection method of duplicated nodes. The performance of the oversampled graphs is compared through an experiment on graph signal denoising.

1. Introduction

Graph signal processing has been developed as a useful tool for analysis of high-dimensional data [1], such as sensor and brain networks, traffic, learning, and images. Whereas signals of regular signal processing have very simple structures, those of graph signal processing are allowed to have complex irregular structures. Graph wavelet transforms can be used for analyzing, processing or compressing graph signals.