基于图割和局部算子的图子集选取-《计算机技术与发展》

文章信息/Info

Author(s):: CHEN Dan-ran; WANG Jian; School of Data Science,Fudan University,Shanghai 200433,China

Keywords:: graph signal processing; graph signal sampling; graph subset selection; localization operator; graph cut

摘要:: 图子集选取问题旨在从图节点集中采样少部分代表性节点,利用观测的节点信号值去重构原始图信号。在资源有限的情况下,可以降低数据维度和计算复杂度,提高对复杂多变图结构的适应性,从而为网络数据的传输处理提供高效的技术支撑。现有的确定性算法大多采用贪心优化,后序采样点的选择依赖于前序已采样节点,对初始值敏感,且可能陷入局部最优;同时,大多数频域算法没有考虑顶点域内采样集节点的空间关系。该文提出基于局部算子的两步采样算法,通过构建节点局部算子的内积完全图来度量采样节点的距离,首先求解标准图割,将节点集按距离划分指定个数簇;其次,在各个簇内依据稀疏性度量选择最优点,从而生成最终的采样集。该算法同时结合了频域与节点域的信息,并使得采样可并行执行。在多种图场景下与多种代表性算法相比,该算法都可以取得最优或相近的重构效果。

Abstract:: Graph subset selection aims to select a small set of representative nodes to recover the original graph signal. In the case oflimited resources,the data dimension and computational complexity can be reduced,and the adaptability to complex and changeable graphstructures can be improved,so as to provide efficient technical support for the transmission and processing of network data. Existing deterministic methods mostly use a greedy serial selection framework,in which node selection depends on previous sampled nodes. It can besensitive to initialization and may be trapped into local optimum. Meanwhile, most spectrum methods do not consider the spatialrelationship of sampled nodes in the vertex domain. We propose a two-step algorithm based on localization operators,which measuresdistances of sampled nodes by constructing a complete inner graph of localization operators. The first step is to find the normalized graphcut so that the vertex set can be divided into a specified number of clusters based on node distances. Then,an optimal vertex is selectedaccording to a sparsity measure in each cluster,which makes up the final sampling set. This method takes into account both spectral andvertex domain information and realizes the parallel execution in sampling. The proposed algorithm achieves the best or competitive reconstruction performance compared to existing methods in various scenarios.