Oct, 2023

通用图随机特征

PDF
TL;DR我们提出了一种新的准蒙特卡洛机制，用于改进基于图的采样，称为斥力随机游走。通过在相互作用的集合中引入轨迹之间的相关性，使其边际转移概率不变，我们能够更高效地探索图，并提高统计估计量的集中度，同时保持其无偏性。该机制具有简单易用的实现方法。我们展示了斥力随机游走在估计图核、PageRank 向量和图图案集中度等各种环境中的有效性，并提供了详细的实验评估和稳健的理论保证。据我们所知，斥力随机游走是第一个对图上行走者的方向进行严格研究的准蒙特卡洛方案，在这个令人兴奋的初创领域中引发了新的研究。
quasi-monte carlorepelling random walksgraph-based samplinggraph kernelspagerank vector
发现论文，激发创造
  • 排斥随机游走

    我们提出了一种新颖的准蒙特卡罗机制 —— 排斥随机游走，该机制通过在一个交互集合的轨迹之间引入相关性，使它们的边际转移概率保持不变，从而能够更有效地探索图形，提高统计估计的集中度，同时保持其无偏性。我们展示了排斥随机游走在一系列设置中的有效性，包括图核的估计、PageRank 向量和图结构浓度。我们提供了详细的实验评估和稳健的理论保证。据我们所知，排斥随机游走是第一个对图中行者的方向进行严格研究的准蒙特卡罗方案，为这个令人兴奋的新领域带来了新的研究。

    Oct, 2023

  • 拟蒙特卡罗图随机特征

    本文提出一种新的机制，通过采用反向终止方法，在算法的随机游走长度之间产生负相关性，从而改善最近引入的图形随机特征（Graph random features，GRFs）类的准蒙特卡洛（quasi-Monte Carlo，q-GRFs ）在稍加限制下证明了它们在 2 - 正则拉普拉斯核的较低方差估计器效果，并在多种任务上展示了实证精度提高。

    May, 2023

  • 一般图上的自我排斥随机游走 - 通过非线性马尔可夫链实现最小采样方差

    通过自反随机游走（SRRW）设计的随机游走者，结合采样和邻域探索的马尔可夫链蒙特卡罗（MCMC）过程，近似目标分布，并在一定程度上提高采样方差

    May, 2023

  • 通过自排斥随机行走加速分布式随机优化

    使用一种非线性 Markov 链 - 即自排斥随机游走（SRRW）驱动分布式随机优化算法，证明了该算法的迭代误差趋于零，同时导出了迭代误差对应的渐近协方差矩阵的显式形式。

    Jan, 2024

  • 基于图的表示学习方法泛化框架

    本论文介绍了带标记的随机游走的概念，以此为基础对现有的一些利用随机游走的算法如 DeepWalk、node2vec 等进行了推广，可适用于传导学习、归纳学习以及具备属性的图形数据，并在多个领域的各种图形上验证了该算法的有效性。

    Sep, 2017

  • 多维随机游走估计和采样图

    本文提出一种新的 $m$- 维随机游走采样方法，称为前沿采样，该方法在大规模实际网络图中表现出更低的估计误差，并且比随机顶点采样更适合采样图的度数分布尾部。

    Feb, 2010

  • 用随机特征驯服图核函数

    本文介绍了图随机特征（GRFs）的机制，并对其进行了理论和实证分析。GRFs 可以用于构建基于图节点定义的多个重要核函数的无偏随机估计器。相比传统的图核函数算法，GRFs 具有显著的计算性能。此外，GRFs 还提供了一种简单的分布式算法以及其改进版本 q-GRFs 来优化 GRFs 的方差，尤其适用于解决具有正对称矩阵的线性方程组。

    Apr, 2023

  • 大规模图中奇异子结构的快速准确挖掘：摇摆随机游走

    本文提出了一种新的算法 Waddling Random Walk（WRW），用于估计任意大小的图相对浓度，并通过在可访问的节点路径上进行随机游走来采样子图以提高计算效率、精度与准确性。通过使用广泛使用的图形数据集，该算法在速度、精度和准确性方面都优于当前最先进的挖掘子图统计算法。

    May, 2016

  • 随机、大规模和高效行走

    本研究提出一组技术，允许在每台机器的空间强烈次线性的情况下，在 Massive Parallel Computation（MPC）模型中高效生成许多独立的随机游走，从而突破了 PageRank 等在有向和无向图的应用中遇到的局限性。

    Jul, 2019

  • 随机梯度 Repulsive 力量 MCMC

    本文提出 Bayesian inference 的两种不同算法的统一视图，即 Stochastic Gradient Markov Chain Monte Carlo （SG-MCMC）和 Stein Variational Gradient Descent（SVGD），提出一种新的改进和高效的采样方法，将 SVGD 与噪声结合，构成多链 SG-MCMC 方法，实现粒子之间斥力的作用，避免了崩溃并促进了更好的参数空间探索，并证明了这种添加噪声项是获得有效 SG-MCMC 采样器的必要条件。实验表明了所提出方案的益处。

    Nov, 2018