Variational perspective on local graph clustering
Variational perspective on local graph clustering
复制标题
DOI：
10.1007/s10107-017-1214-8
复制
发表时间：
2019-03-01
影响因子：
2.7
通讯作者：
Mahoney, Michael W.
中科院分区：
文献类型：
--
作者：
Fountoulakis, Kimon;Roosta-Khorasani, Farbod;Mahoney, Michael W.
现代图聚类应用程序需要分析大型图，这可能是计算昂贵的。在这方面，局部谱图聚类方法的目的是在不访问整个图的情况下识别给定的参考节点种子集周围的良好连接的聚类。Andersen等人的开创性论文（见：FOCS '06 proceedings of the 47 th annual IEEE symposium on foundations of computer science，pp 475-486，2006）中著名的近似个性化PageRank（APPR）算法就是这样一种方法。APPR的引入和动机纯粹是从算法的角度出发的。换句话说，没有目标函数/最优性条件的先验概念来表征APPR所采取的步骤。在这里，我们推导出一个新的变分制定明确的实际优化问题解决的APPR。在此过程中，我们绘制了Andersen等人（2006）的局部谱算法和迭代收缩阈值算法（ISTA）之间的联系。特别是，我们表明，适当初始化的ISTA应用到我们的变分公式可以恢复抢手的本地集群的时间，只取决于非零的最佳解决方案，而不是整个图形的数量。在这个过程中，我们表明，一个优化算法，显然需要访问整个图形，可以表现在一个完全本地的方式只访问少量的节点。这种观点建立了一个桥梁，跨越两个看似不相交的领域的图形处理和数值优化，它允许一个利用良好的研究，数值上强大的，高效的优化算法处理今天的大型图形。
Modern graph clustering applications require the analysis of large graphs and this can be computationally expensive. In this regard, local spectral graph clustering methods aim to identify well-connected clusters around a given seed set of reference nodes without accessing the entire graph. The celebrated Approximate Personalized PageRank (APPR) algorithm in the seminal paper by Andersen et al. (in: FOCS '06 proceedings of the 47th annual IEEE symposium on foundations of computer science, pp 475-486, 2006) is one such method. APPR was introduced and motivated purely from an algorithmic perspective. In other words, there is no a priori notion of objective function/optimality conditions that characterizes the steps taken by APPR. Here, we derive a novel variational formulation which makes explicit the actual optimization problem solved by APPR. In doing so, we draw connections between the local spectral algorithm of Andersen et al. (2006) and an iterative shrinkage-thresholding algorithm (ISTA). In particular, we show that, appropriately initialized ISTA applied to our variational formulation can recover the sought-after local cluster in a time that only depends on the number of non-zeros of the optimal solution instead of the entire graph. In the process, we show that an optimization algorithm which apparently requires accessing the entire graph, can be made to behave in a completely local manner by accessing only a small number of nodes. This viewpoint builds a bridge across two seemingly disjoint fields of graph processing and numerical optimization, and it allows one to leverage well-studied, numerically robust, and efficient optimization algorithms for processing today's large graphs.