基于图割和局部算子的图子集选取

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