Rates of Convergence of Spectral Methods for Graphon Estimation
Rates of Convergence of Spectral Methods for Graphon Estimation
复制标题
DOI：
--
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Jiaming Xu
中科院分区：
文献类型：
--
作者：
Jiaming Xu
本文研究了网络的生成机制--grahpon模型的估计问题。图子估计在许多应用中出现，例如预测网络中的缺失链接和在推荐系统中学习用户偏好。图子模型处理一个随机图的$n$个顶点，使得每对两个顶点$i$和$j$以概率$\rho \times f（x_i，x_j）$独立连接，其中$x_i$是未知的$d$维顶点标签，$f$是未知的对称函数，$\rho$是表征图稀疏性的尺度参数。最近的研究已经确定了极小极大错误率估计的graphon从一个单一的实现的随机图。然而，存在着一个很大的差距之间的已知的错误率的计算有效的估计程序和极小极大最优错误率。在这里，我们分析了谱方法，即通用奇异值阈值（USVT）算法，在相对稀疏的制度与平均顶点度$n\rho=\Omega（\log n）$。当f$属于光滑指数为$\alpha$的保持器或Sobolev空间时，我们证明了USVT的错误率至多为$（n\rho）^{ -2 \alpha /（2\alpha+d）}$，随着$\alpha$的增加，逼近$d=1$时的极小极大最优错误率$\log（n\rho）/（n\rho）$.此外，当$f$是解析的时，我们证明了USVT的错误率至多为$\log^d（n\rho）/（n\rho）$。在具有$k$块的随机块模型的特殊情况下，USVT的错误率至多为$k/（n\rho）$，其比极小极大最优错误率至多大一个乘法因子$k/\log k$。这与观察到的社区检测的计算差距相吻合。我们分析的一个关键步骤是使用图子函数f$的分段多项式近似来导出边缘概率矩阵的特征值衰减率。
This paper studies the problem of estimating the grahpon model - the underlying generating mechanism of a network. Graphon estimation arises in many applications such as predicting missing links in networks and learning user preferences in recommender systems. The graphon model deals with a random graph of $n$ vertices such that each pair of two vertices $i$ and $j$ are connected independently with probability $\rho \times f(x_i,x_j)$, where $x_i$ is the unknown $d$-dimensional label of vertex $i$, $f$ is an unknown symmetric function, and $\rho$ is a scaling parameter characterizing the graph sparsity. Recent studies have identified the minimax error rate of estimating the graphon from a single realization of the random graph. However, there exists a wide gap between the known error rates of computationally efficient estimation procedures and the minimax optimal error rate. Here we analyze a spectral method, namely universal singular value thresholding (USVT) algorithm, in the relatively sparse regime with the average vertex degree $n\rho=\Omega(\log n)$. When $f$ belongs to Holder or Sobolev space with smoothness index $\alpha$, we show the error rate of USVT is at most $(n\rho)^{ -2 \alpha / (2\alpha+d)}$, approaching the minimax optimal error rate $\log (n\rho)/(n\rho)$ for $d=1$ as $\alpha$ increases. Furthermore, when $f$ is analytic, we show the error rate of USVT is at most $\log^d (n\rho)/(n\rho)$. In the special case of stochastic block model with $k$ blocks, the error rate of USVT is at most $k/(n\rho)$, which is larger than the minimax optimal error rate by at most a multiplicative factor $k/\log k$. This coincides with the computational gap observed for community detection. A key step of our analysis is to derive the eigenvalue decaying rate of the edge probability matrix using piecewise polynomial approximations of the graphon function $f$.