Attribute-Guided Network Sampling Mechanisms
Attribute-Guided Network Sampling Mechanisms
复制标题
属性引导的网络采样机制
DOI：
--
复制
发表时间：
2021
影响因子：
3.6
通讯作者：
H. Sundaram
中科院分区：
文献类型：
--
作者：
Suhansanu Kumar;H. Sundaram
本文介绍了一种新的任务无关的采样器属性网络。这个问题很重要，因为虽然网络内容的数据挖掘任务很常见，但在互联网规模的网络上进行采样的成本很高。链接跟踪采样器，如雪球采样，森林火灾，随机游走和大都市-黑斯廷斯随机游走广泛用于从网络中采样。这些属性不可知的采样器的设计集中在保持网络结构的显着属性，并没有优化节点内容的任务。本文有三个贡献。首先，我们提出了一个任务无关的，属性感知的链接跟踪采样器接地信息理论。我们的采样器会向样本中添加信息量最大的节点（即，令人惊讶的）邻居。采样器倾向于快速探索属性空间，最大限度地减少未知节点的惊喜。其次，我们证明了内容抽样是一个NP-难问题。一个著名的算法最好在1 − 1/e内近似优化解，但需要完全访问整个图。第三，我们通过实证反事实分析表明，在许多现实世界的数据集，网络结构并不妨碍基于惊喜的链接跟踪采样器的性能。在18个真实世界数据集上的实验结果表明：基于属性的采样器是样本高效的，并且在很大程度上优于最先进的属性不可知采样器（例如，集群任务性能提升45%）。
This article introduces a novel task-independent sampler for attributed networks. The problem is important because while data mining tasks on network content are common, sampling on internet-scale networks is costly. Link-trace samplers such as Snowball sampling, Forest Fire, Random Walk, and Metropolis–Hastings Random Walk are widely used for sampling from networks. The design of these attribute-agnostic samplers focuses on preserving salient properties of network structure, and are not optimized for tasks on node content. This article has three contributions. First, we propose a task-independent, attribute aware link-trace sampler grounded in Information Theory. Our sampler greedily adds to the sample the node with the most informative (i.e., surprising) neighborhood. The sampler tends to rapidly explore the attribute space, maximally reducing the surprise of unseen nodes. Second, we prove that content sampling is an NP-hard problem. A well-known algorithm best approximates the optimization solution within 1 − 1/e, but requires full access to the entire graph. Third, we show through empirical counterfactual analysis that in many real-world datasets, network structure does not hinder the performance of surprise based link-trace samplers. Experimental results over 18 real-world datasets reveal: surprise-based samplers are sample efficient and outperform the state-of-the-art attribute-agnostic samplers by a wide margin (e.g., 45% performance improvement in clustering tasks).