UM  > 科技學院
Multi-level Downsampling of Graph Signals via Improved Maximum Spanning Trees
Zheng, Xianwei1,2,3; Tang, Yuan Yan3; Zhou, Jiantao3; Pan, Jianjia3; Yang, Shouzhi2; Li, Youfa4; Wang, Patrick S. P.5
2019-05
Source PublicationINTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
ISSN0218-0014
Volume33Issue:3Pages:1958005
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 multi-scale 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 1212. 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.

KeywordGraph Signals Maximum Spanning Tree Graph Density Unbalance Possibility Imbalance Reduction
DOIhttps://doi.org/10.1142/S0218001419580059
Indexed BySCI
Language英语
WOS Research AreaComputer Science
WOS SubjectComputer Science, Artificial Intelligenc
WOS IDWOS:000459294000008
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionFaculty of Science and Technology
DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Corresponding AuthorYang, Shouzhi
Affiliation1.Foshan Univ, Sch Math & Big Data, Foshan 528000, Guangdong, Peoples R China
2.Shantou Univ, Dept Math, Shantou 515063, Guangdong, Peoples R China
3.Univ Macau, Dept Comp & Informat Sci, Macau 999078, Peoples R China
4.Guangxi Univ, Coll Math & Informat Sci, Nanning 530000, Peoples R China
5.Northeastern Univ, Boston, MA 02115 USA
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Zheng, Xianwei,Tang, Yuan Yan,Zhou, Jiantao,et al. Multi-level Downsampling of Graph Signals via Improved Maximum Spanning Trees[J]. INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE,2019,33(3):1958005.
APA Zheng, Xianwei.,Tang, Yuan Yan.,Zhou, Jiantao.,Pan, Jianjia.,Yang, Shouzhi.,...&Wang, Patrick S. P..(2019).Multi-level Downsampling of Graph Signals via Improved Maximum Spanning Trees.INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE,33(3),1958005.
MLA Zheng, Xianwei,et al."Multi-level Downsampling of Graph Signals via Improved Maximum Spanning Trees".INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 33.3(2019):1958005.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zheng, Xianwei]'s Articles
[Tang, Yuan Yan]'s Articles
[Zhou, Jiantao]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zheng, Xianwei]'s Articles
[Tang, Yuan Yan]'s Articles
[Zhou, Jiantao]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zheng, Xianwei]'s Articles
[Tang, Yuan Yan]'s Articles
[Zhou, Jiantao]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.