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-03-01
Source PublicationInternational Journal of Pattern Recognition and Artificial Intelligence
ISSN0218-0014
Volume33Issue:3
AbstractGraph 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 12. 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 density Graph signals maximum spanning tree unbalance possibility unbalance reduction
DOI10.1142/S0218001419580059
URLView the original
Language英语
Fulltext Access
Citation statistics
Cited Times [WOS]:1   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Corresponding AuthorYang,Shouzhi
Affiliation1.School of Mathematics and Big Data,Foshan University,Guangdong Foshan,528000,China
2.Department of Mathematics,Shantou University,Guangdong Shantou,515063,China
3.Department of Computer and Information Science,University of Macau,999078,Macao
4.College of Mathematics and Information Science,Guangxi University,Nanning,530000,China
5.Northeastern University,Boston,United States
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).
APA Zheng,Xianwei,Tang,Yuan Yan,Zhou,Jiantao,Pan,Jianjia,Yang,Shouzhi,Li,Youfa,&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).
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).
Files in This Item:
There are no files associated with this item.
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.