Graph Powering and Spectral Robustness
Graph Powering and Spectral Robustness
复制标题
DOI：
10.1137/19m1257135
复制
发表时间：
2020-01-01
影响因子：
3.6
通讯作者：
Sandon, Colin
中科院分区：
文献类型：
--
作者：
Abbe, Emmanuel;Boix-Adsera, Enric;Sandon, Colin
谱算法，如主成分分析和谱聚类，依赖于矩阵A的极值特征对。然而，如果不对A进行适当的变换，这些特征对可能是不能提供信息的。原因是A的频谱可能被数据中的尺度变化导致的顶部特征值所污染，例如高次节点。设计一个好的PSI并确定什么是好的通常是具有挑战性的，而且依赖于模型。给出了稀疏图psi(A)=1((i+A)(R)>；=1)的一个简单而通用的构造，其中A表示邻接矩阵，r是一个整数，指示符函数是按入口应用的。我们支持这种具有如下正则化性质的“图赋权”构造：(I)如果图是从没有谱间隙的稀疏Erdos-Renyi系综中得到的，则图赋权产生一个“最大”谱间隙，与给随机正则图赋权时得到的谱间隙相当；(Ii)如果图是从稀疏随机块模型中得到的，则图赋权达到弱恢复的基本极限(Kesten-Stigum阈值)，同时解决了Massoulie在2013年提出的一个相关猜想；(Iii)我们使用几何块模型作为基准，并为该模型引入了新的猜想，证明了图增强算法对纠缠和团的健壮性显著高于以前基于自回避或非回溯行走计数的谱算法。
Spectral algorithms, such as principal component analysis and spectral clustering, rely on the extremal eigenpairs of a matrix A. However, these may be uninformative without preprocessing A with a proper transformation. The reason is that the spectrum of A may be contaminated by top eigenvalues resulting from scale variations in the data, such as high-degree nodes. Designing a good psi and establishing what good means is often challenging and model dependent. This paper proposes a simple and generic construction for sparse graphs, psi(A) = 1((I + A)(r) >= 1), where A denotes the adjacency matrix, r is an integer, and the indicator function is applied entrywise. We support this "graph powering" construction with the following regularization properties: (i) if the graph is drawn from the sparse Erdos-Renyi ensemble, which has no spectral gap, then graph powering produces a "maximal" spectral gap, comparable to that obtained when powering a random regular graph; (ii) if the graph is drawn from the sparse stochastic block model, graph powering achieves the fundamental limit for weak recovery (the Kesten-Stigum threshold), settling at the same time a related conjecture by Massoulie in 2013; (iii) we also demonstrate that graph powering is significantly more robust to tangles and cliques than previous spectral algorithms based on self-avoiding or nonbacktracking walk counts, using a geometric block model as our benchmark and introducing new conjectures for this model.