Fiedler Vector Approximation via Interacting Random Walks
Fiedler Vector Approximation via Interacting Random Walks
复制标题
DOI：
10.1145/3379502
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Vishwaraj Doshi;Do Young Eun
中科院分区：
文献类型：
--
作者：
Vishwaraj Doshi;Do Young Eun
图的Fiedler向量，即对应于图的Laplacian矩阵的第二小特征值的特征向量，在谱图理论中起着重要的作用，在图的二分划和包络约简等问题中有应用。设计用于估计该量的算法通常依赖于整个图的先验知识，并采用诸如图稀疏化和幂迭代等技术，这些技术在图未知或动态变化的情况下具有明显的缺点。在本文中，我们开发了一个框架，在这个框架中，我们构建了一个随机过程的基础上一组相互作用的随机游走图，并表明，我们的随机过程的适当缩放的版本收敛到费德勒向量足够大的行走。像其他技术的基础上探索随机游走和飞行计算，如马尔可夫链蒙特卡罗（MCMC），我们的算法克服了通常面临的挑战，基于幂迭代的方法。但是，与任何现有的基于随机游走的方法（如MCMCMC，其重点是领先的特征向量）不同，我们的框架与相互作用的随机游走收敛到费德勒向量（第二特征向量）。我们还提供了数值结果，以确认我们的理论研究结果在不同的图，并表明，我们的算法表现良好，在很宽的参数范围和随机游走的数量。随时间变化的动态图的模拟结果也提供了我们的随机游走为基础的技术在这样的设置显示的功效。作为一个重要的贡献，我们扩展了我们的结果，并表明，我们的框架是适用于逼近不仅是费德勒向量的图拉普拉斯算子，但也通过相互作用的随机游动的任何时间可逆的马尔可夫链核的第二特征向量。据我们所知，我们试图近似的第二个特征向量的任何时间可逆的马尔可夫链使用随机游动是第一种，开辟了可能性，以实现近似的更高层次的特征向量使用随机游动图。
The Fiedler vector of a graph, namely the eigenvector corresponding to the second smallest eigenvalue of a graph Laplacian matrix, plays an important role in spectral graph theory with applications in problems such as graph bi-partitioning and envelope reduction. Algorithms designed to estimate this quantity usually rely on a priori knowledge of the entire graph, and employ techniques such as graph sparsification and power iterations, which have obvious shortcomings in cases where the graph is unknown, or changing dynamically. In this paper, we develop a framework in which we construct a stochastic process based on a set of interacting random walks on a graph and show that a suitably scaled version of our stochastic process converges to the Fiedler vector for a sufficiently large number of walks. Like other techniques based on exploratory random walks and on-the-fly computations, such as Markov Chain Monte Carlo (MCMC), our algorithm overcomes challenges typically faced by power iteration based approaches. But, unlike any existing random walk based method such as MCMCs where the focus is on the leading eigenvector, our framework with interacting random walks converges to the Fiedler vector (second eigenvector). We also provide numerical results to confirm our theoretical findings on different graphs, and show that our algorithm performs well over a wide range of parameters and the number of random walks. Simulations results over time varying dynamic graphs are also provided to show the efficacy of our random walk based technique in such settings. As an important contribution, we extend our results and show that our framework is applicable for approximating not just the Fiedler vector of graph Laplacians, but also the second eigenvector of any time reversible Markov Chain kernel via interacting random walks. To the best of our knowledge, our attempt to approximate the second eigenvector of any time reversible Markov Chain using random walks is the first of its kind, opening up possibilities to achieving approximations of higher level eigenvectors using random walks on graphs.