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.