论文标题
从图形信号中盲目提取公平分区
Blind Extraction of Equitable Partitions from Graph Signals
论文作者
论文摘要
查找公平分区与图对称性的提取和在各种应用程序上下文中的提取密切相关，例如节点角色检测，群集同步，共识动力学和网络控制问题。在这项工作中，我们研究了一个盲目的识别问题，我们旨在在不了解网络边缘的情况下恢复网络的公平分区，而仅基于对未知图滤波器的输出的观察。具体来说，我们考虑两个设置。首先，我们考虑一个场景，在该场景中，我们可以控制图形过滤器的输入，并提出一种方法，以提取受众所周知的Weisfeiler-Lehman（颜色改进）算法启发的分区。其次，我们将这个想法概括为仅观察到图形滤波器的随机，低级别激发的设置，并提出一种简单的光谱算法以提取相关的公平分区。最后，我们建立了理论界限，即该频谱检测方案会产生并执行数值实验以说明我们的理论结果并比较这两个算法的错误。
Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications context such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions. Finally, we establish theoretical bounds on the error that this spectral detection scheme incurs and perform numerical experiments that illustrate our theoretical results and compare both algorithms.
