Aug, 2013

图采样的调查与分类

PDF
TL;DR本文系统总结了图采样的目标和方法，并对其关系进行了形式化论证，提供了将理论分析与实际应用桥接的通用框架。通过研究哪些图属性在采样过程中得以保留，展现了一种构造高效估算器的方法，并可以加速一类图算法的实现。此外，文章还讨论了一些高级属性，同时指出了该领域中尚有许多未被探索的问题及未来的研究方向。
graph samplingvertex samplingedge samplingtraversal-based samplinggraph properties
发现论文，激发创造
  • 网络采样：从静态到流式图

    本文提出了一个网络抽样的框架，此框架能从静态到流式的完整的计算模型范围内，基于图诱导设计了一系列通用的采样方法，并证明此系列采样方法可以更准确地保留输入图的拓扑特性，研究了网络采样算法对关系分类算法参数估计和性能评估的影响。

    Nov, 2012

  • 使用采样理论进行图信号主动半监督学习

    提出了一种基于图信号采样理论的离线池式主动半监督学习框架，该框架使用节点选择来最大化从采样集重构信号的频率，以解决有限的已标记数据但有大量未标记数据的问题。

    May, 2014

  • 基于图的离散信号处理：采样理论

    本文提出了适用于有向图和无向图信号的抽样定理，可以实现在保证完美恢复的前提下降低样本量，且可以将采样后的信号系数形成新的图信号，该理论还被应用于半监督分类，以较少的标记样本就达到了与之前工作相似甚至更好的性能。

    Mar, 2015

  • 使用图采样计算模体数量

    本文从统计学角度研究了网络采样和子图统计中的几个问题，提出了一些估算方法，并给出了理论与实验结果。

    Feb, 2018

  • 大规模属性图假设检验的基于采样的框架

    这篇论文介绍了基于假设的图采样和假设测试框架，通过路径假设感知采样方法 PHASE 提高准确性和时间效率。实验证明，该框架能够有效利用常见的图采样方法进行假设测试，并且在准确性和时间效率方面具有优势。

    Mar, 2024

  • 使用连续本地聚合对图信号进行采样

    本文介绍了一种用于图信号采样的新方案，旨在更高效地实现信号稀疏表示和重建，基于图驻点合成算子和 VandeMonde 矩阵结构，可以针对有向环和非环图的信道进行采样和插值，同时进行了实验验证。

    Apr, 2015

  • 从海量图流中采样

    本文提出了 Graph Priority Sampling（GPS）来对规模庞大的图边流进行基于顺序的蓄水池采样，以计算图属性的估计目标，其与许多先前的图采样方案有所不同。通过应用 GPS 来计算 Twitter 网络中的三角形计数，证明了其能够高精度地对三角形计数进行估计，存储的仅仅是 40K 条边，并且具有低于 1％的误差。

    Mar, 2017

  • 智能抽样用于代理建模、超参数优化和数据分析

    在采样技术的研究领域，我们提出智能采样的概念，既可以创建新算法，也可以修改其他领域的适当算法以满足采样需求，经过定量和定性比较发现，简单的算法可以轻松地满足超参数优化、数据分析等方面的采样需求，并且优于当前使用的更复杂的算法，从而更好地利用时间和计算资源。

    Jun, 2023

  • 基于图的模型无关数据子采样算法在推荐系统中的应用

    通过研究用户 - 项目图的拓扑结构，利用图电导估计每个用户 - 项目交互的重要性并进行网路传播，避免了模型误设（misspecified）对模型基础数据子采样方法的恶化，该方法在 KuaiRec 和 MIND 数据集上的实验结果证明了其相对于基准方法具有更优的性能。

    May, 2023

  • 子图频率：映射大型图集的经验和极端地理

    本研究通过计算每个图中的小诱导子图的频率来制定和分析这种表示，发现子图频率空间不仅受其组合属性的制约，还受其实证属性以及社会图在空间中实际位置的影响，并提供了灵活的框架和分类算法，以研究这些方面。

    Apr, 2013