Fiedler Vector Approximation via Interacting RandomWalks
Fiedler Vector Approximation via Interacting RandomWalks
复制标题
通过交互随机游走进行费德勒矢量逼近
DOI：
10.1145/3410048.3410107
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Young Eun, Do
中科院分区：
文献类型：
--
作者：
Doshi, Vishwaraj;Young Eun, Do
图的Fiedler向量，即图拉普拉斯矩阵的第二小特征值所对应的特征向量，在谱图理论中起着重要的作用，在图的双划分和包络约简等问题中都有应用。设计用来估计这个数量的算法通常依赖于对整个图的先验知识，并采用图稀疏化和幂迭代等技术，这些技术在图未知或动态变化的情况下有明显的缺点。在本文中，我们开发了一个框架，在这个框架中，我们构建了一个基于图上一组相互作用的随机游走的随机过程，并证明了我们的随机过程的适当缩放版本收敛于足够大的游走数的费德勒向量。与其他基于探索性随机漫步和动态计算的技术（如马尔可夫链蒙特卡罗（MCMC））一样，我们的算法克服了基于幂迭代的方法通常面临的挑战。但是，不像任何现有的基于随机行走的方法，如mcmc，其重点是在主要特征向量上，我们的交互随机行走框架收敛到费德勒向量（第二个特征向量）。我们还提供了数值结果来证实我们在不同图上的理论发现，并表明我们的算法在广泛的参数范围和随机行走数量上表现良好。模拟结果随时间变化的动态图形也提供，以显示我们的随机漫步技术在这种设置的有效性。作为一个重要的贡献，我们扩展了我们的结果，表明我们的框架不仅适用于逼近图拉普拉斯算子的Fiedler向量，而且适用于通过相互作用随机游动逼近任意时间可逆马尔可夫链核的第二个特征向量。据我们所知，我们尝试使用随机行走来近似任意时间可逆马尔可夫链的第二个特征向量是同类中的第一个，这为在图上使用随机行走来实现更高级别特征向量的近似开辟了可能性。
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.