Paper Info
Title
Multi-Level Downsampling Of Graph Signals Via Improved Maximum Spanning Trees
Abstract
Graph signal processing (GSP) is an emerging field in the signal processing community. Novel GSP-based transforms, such as graph Fourier transform and graph wavelet filter banks, have been successfully utilized in image processing and pattern recognition. As a rapidly developing research area, graph signal processing aims to extend classical signal processing techniques to signals with irregular underlying structures. One of the hot topics in GSP is to develop multiscale transforms such that novel GSP-based techniques can be applied in image processing or other related areas. For designing graph signal multi-scale frameworks, downsampling operations that ensuring multi-level downsampling should be specifically constructed. Among the existing downsampling methods in graph signal processing, the state-of-the-art method was constructed based on the maximum spanning tree (MST). However, when using this method for multi-level downsampling of graph signals defined on unweighted densely connected graphs, such as social network data, the sampling rates are not close to 1/2. This phenomenon is summarized as a new problem and called downsampling unbalance problem in this paper. Due to the unbalance, MST-based downsampling method cannot be applied to construct graph signal multi-scale transforms. In this paper, we propose a novel and efficient method to detect and reduce the downsampling unbalance generated by the MST-based method. For any given graph signal, we apply the graph density to construct a measurement of the downsampling unbalance generated by the MST-based method. If a graph signal has large unbalance possibility, the multi-level downsampling is conducted after the MST is improved. The experimental results on synthetic and real-world social network data show that downsampling unbalance can be efficiently detected and then reduced by our method.
Year
DOI
Venue
2019
10.1142/S0218001419580059
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
Keywords
Field
DocType
Graph signals, maximum spanning tree, graph density, unbalance possibility, Imbalance reduction
Signal processing,Graph,Graph fourier transform,Pattern recognition,Graph signal processing,Spanning tree,Artificial intelligence,Wavelet filter,Upsampling,Mathematics,Dense graph
Journal
Volume
Issue
ISSN
33
3
0218-0014
Citations 
PageRank 
References 
0
0.34
15
Authors
7
Name
Order
Citations
PageRank
Xianwei Zheng101.35
Yuan Yan Tang22662209.20
Jiantao Zhou358078.87
Jianjia Pan4185.01
Shouzhi Yang5368.73
Youfa Li683.75
patrick s p wang730347.66