Distributed Batch Reconstruction of Time-varying Graph Signals via Sobolev Smoothness on Cartesian Product Graph
-
摘要: 针对大规模网络数据的重构问题，该文以图信号处理(GSP)理论为基础，提出一种基于笛卡尔乘积图上Sobolev平滑的分布式批量重构算法(DBR-SSC)。该算法首先按时间顺序将时变图信号划分为多个信号段，并利用笛卡尔积将每一段内各时刻的图建模为乘积图；然后利用笛卡尔乘积图上的Sobolev差分平滑，将每一段的信号重构问题归结为优化问题；最后设计具有高收敛速度的分布式算法求解该优化问题。采用两种现实世界的数据集进行仿真实验，实验结果表明所提算法重构误差低并具有高收敛速度。Abstract: For the reconstruction of large-scale network data, a Distributed Batch Reconstruction algorithm via Sobolev Smoothness on Cartesian product graph (DBR-SSC) is proposed, which is based on the Graph Signal Processing (GSP) theory. In the proposed algorithm, the time-varying graph signal is firstly divided into multiple signal segments in time dimension, and a product graph is constructed from graphs at each time instant via Cartesian product. Secondly, the reconstruction of the time-varying graph signal in each segment is formulated as an optimization problem by exploiting the Sobolev difference smoothness on the Cartesian product graph. Finally, a distributed algorithm with high convergence rate is devised to solve the optimization problem. Two real world data sets are used for experiments, and it is shown that the proposed algorithm has low reconstruction error and high convergence rate.
-
算法1 段内时变图信号$ \bar {\boldsymbol{x}} $的分布式批量重构算法 输入：矩阵$\bar {\boldsymbol{H}}$，观测信号$\bar {\boldsymbol{y}}$，迭代停止标准$ \varepsilon $，最大迭代次数$ K $, ${\bar {\boldsymbol{x}}^{(0)} }{\text{ = } }{{ {\textit{0}}}}$, $ t = 0 $。 步骤： 步骤1 根据式(12)计算$\bar {\boldsymbol{P}}$。 步骤2 每一个子图中心节点(m,i)计算 ${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t + 1)} } = {{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t)} } - {{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{P} }{{\boldsymbol{\chi}} _{(m,i)} }({{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{H} }{{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t)} } - {{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{y} })$ (14) 并向${\bar {\boldsymbol{v}}_{(m,i)} }$中的所有节点$ (k,l) $发送相应的信号值${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t{\text{ + } }1)} }{(h)_{h = N \times (k - 1) + l} }$。 步骤3 $ \bar V $中的各节点对接收到的信号值进行平均，然后将平均值分别发送给所在子图的中心节点。 步骤4 各子图中心节点(m,i)将收到的信号值以及自身的信号值组成新的子图信号${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t{\text{ + } }1)} }$，如果
$\left\| { {{\boldsymbol{\chi}} _{(m,i)} }{ {\bar {\boldsymbol{x} } }^{(t + 1)} } - {{\boldsymbol{\chi}} _{(m,i)} }{ {\bar {\boldsymbol{x} } }^{(t)} } } \right\|_2^2 < \varepsilon$成立或$ t > K $，则结束程序。否则，令$ t = t + 1 $，并返回步骤2。输出：${\bar {\boldsymbol{x}}^{(t + 1)} }$作为本段的重构信号。 
下载: 导出CSV
表 1 PM2.5数据集上各种算法的平均重构误差(RMSE)对比
算法 受损节点数量占比(%) 10 20 30 BR-DS 1.29 1.94 2.43 BR-SS 1.29 1.94 2.43 BR-TR 1.60 2.37 2.91 DBR-SSC 1.29 1.91 2.41
下载: 导出CSV
表 2 PM2.5数据集上各种算法的平均迭代次数对比
算法 受损节点数量占比(%) 10 20 30 BR-DS 1.56 2.72 3.52 BR-SS 1.53 2.54 3.28 BR-TR 0.43 0.60 0.66 DBR-SSC 0.15 0.16 0.20
下载: 导出CSV
表 3 PM2.5数据集上各种算法所用平均CPU时间对比 (10–3 s)
算法 受损节点数量占比(%) 10 20 30 BR-DS 1.18 1.95 2.45 BR-SS 1.17 1.89 2.32 BR-TR 0.39 0.45 0.49 DBR-SSC 2.01 2.01 2.03
下载: 导出CSV
表 4 COVID-19数据集上各种算法的平均重构误差(RMSE)对比
算法 受损节点数量占比(%) 10 20 30 BR-DS 204 341 463 BR-SS 204 341 462 BR-TR 581 996 1254 DBR-SSC 196 332 447
下载: 导出CSV
表 5 COVID-19数据集上各种算法的平均迭代次数对比
算法 受损节点数量占比(%) 10 20 30 BR-DS 6.64 6.67 6.67 BR-SS 4.27 6.64 6.67 BR-TR 0.56 0.70 0.85 DBR-SSC 0.33 0.54 0.75
下载: 导出CSV
表 6 COVID-19数据集上各种算法所用平均CPU时间对比 (10–3 s)
算法 受损节点数量占比(%) 10 20 30 BR-DS 12.56 12.56 12.67 BR-SS 8.44 12.63 12.59 BR-TR 1.20 1.41 1.73 DBR-SSC 7.97 8.12 8.19
下载: 导出CSV
-
[1] CHEN Min, MAO Shiwen, and LIU Yunhao. Big data: A survey[J]. Mobile Networks and Applications, 2014, 19(2): 171–209. doi: 10.1007/s11036-013-0489-0 [2] 李建中, 刘显敏. 大数据的一个重要方面: 数据可用性[J]. 计算机研究与发展, 2013, 50(6): 1147–1162. doi: 10.7544/issn1000-1239.2013.20130646LI Jianzhong and LIU Xianmin. An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147–1162. doi: 10.7544/issn1000-1239.2013.20130646 [3] SANDRYHAILA A and MOURA J M F. Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure[J]. IEEE Signal Processing Magazine, 2014, 31(5): 80–90. doi: 10.1109/MSP.2014.2329213 [4] SANDRYHAILA A and MOURA J M F. Discrete signal processing on graphs: Frequency analysis[J]. IEEE Transactions on Signal Processing, 2014, 62(12): 3042–3054. doi: 10.1109/TSP.2014.2321121 [5] DONG Xiaowen, THANOU D, TONI L, et al. Graph signal processing for machine learning: A review and new perspectives[J]. IEEE Signal Processing Magazine, 2020, 37(6): 117–127. doi: 10.1109/MSP.2020.3014591 [6] GIRALDO J H, JAVED S, and BOUWMANS T. Graph moving object segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44(5): 2485–2503. doi: 10.1109/TPAMI.2020.3042093 [7] ITANI S and THANOU D. A graph signal processing framework for the classification of temporal brain data[C]. 2020 28th European Signal Processing Conference (EUSIPCO), Amsterdam, Netherlands, 2021: 1180–1184. [8] FENG Jie, CHEN Fangjiong, and CHEN Hongbin. Data reconstruction coverage based on graph signal processing for wireless sensor networks[J]. IEEE Wireless Communications Letters, 2022, 11(1): 48–52. doi: 10.1109/LWC.2021.3120276 [9] LEWENFUS G, MARTINS W A, CHATZINOTAS S, et al. Joint forecasting and interpolation of time-varying graph signals using deep learning[J]. IEEE Transactions on Signal and Information Processing over Networks, 2020, 6: 761–773. doi: 10.1109/TSIPN.2020.3040042 [10] CHEN Siheng, LIU Baoan, FENG Chen, et al. 3D point cloud processing and learning for autonomous driving: Impacting map creation, localization, and perception[J]. IEEE Signal Processing Magazine, 2021, 38(1): 68–86. doi: 10.1109/MSP.2020.2984780 [11] PERRAUDIN N, LOUKAS A, GRASSI F, et al. Towards stationary time-vertex signal processing[C]. 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, USA, 2017: 3914–3918. [12] ROMERO D, IOANNIDIS V N, and GIANNAKIS G B. Kernel-based reconstruction of space-time functions on dynamic graphs[J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 11(6): 856–869. doi: 10.1109/JSTSP.2017.2726976 [13] QIU Kai, MAO Xianghui, SHEN Xinyue, et al. Time-varying graph signal reconstruction[J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 11(6): 870–883. doi: 10.1109/JSTSP.2017.2726969 [14] GIRALDO J H, MAHMOOD A, GARCIA-GARCIA B, et al. Reconstruction of time-varying graph signals via Sobolev smoothness[J]. IEEE Transactions on Signal and Information Processing over Networks, 2022, 8: 201–214. doi: 10.1109/TSIPN.2022.3156886 [15] MOTEE N and SUN Qiyu. Sparsity and spatial localization measures for spatially distributed systems[J]. SIAM Journal on Control and Optimization, 2017, 55(1): 200–235. doi: 10.1137/15M1049294 [16] CHENG Cheng, JIANG Yingchun, and SUN Qiyu. Spatially distributed sampling and reconstruction[J]. Applied and Computational Harmonic Analysis, 2019, 47(1): 109–148. doi: 10.1016/j.acha.2017.07.007 [17] BOUTIN D L. The determining number of a Cartesian product[J]. Journal of Graph Theory, 2009, 61(2): 77–87. doi: 10.1002/jgt.20368 [18] JIANG Junzheng, CHENG Cheng, and SUN Qiyu. Nonsubsampled graph filter banks: Theory and distributed algorithms[J]. IEEE Transactions on Signal Processing, 2019, 67(15): 3938–3953. doi: 10.1109/TSP.2019.2922160 [19] US Environmental Protection Agency. Air quality data[EB/OL].https://www.epa.gov/outdoor-airquality-data, 2016. [20] DONG Ensheng, DU Hongru, and GARDNER L M. An interactive web-based dashboard to track COVID-19 in real time[J]. The Lancet Infectious Diseases, 2020, 20(5): 533–534. doi: 10.1016/S1473-3099(20)30120-1 -
下载:
点击查看大图
图(2) / 表(7)
计量
- 文章访问数: 383
- HTML全文浏览量: 125
- PDF下载量: 74
- 被引次数: 0
