III: Small: Collaborative Research: Cost-Efficient Sampling and Estimation from Large-Scale Networks

从大规模网络或图中采样和估计结构信息对于我们理解网络动力学及其丰富的应用集一直是核心。马尔可夫链蒙特卡罗(MCMC)已经成为更广泛的图采样环境的关键使能器，包括估计大型图的属性、对搜索引擎索引的文档语料库进行采样、从Web表单背后的隐藏数据库中采样记录、识别某些特征的子图以及频繁的图模式匹配。尽管MCMC方法及其用于分析各种形式的图形结构数据的定制算法得到了广泛的应用，但以MCMC方法为中心的文献中仍然存在严重的挑战和局限性。一个是与抽样操作相关的“成本”消耗/约束，它限制了获得的总样本的大小，并对基于获得的样本的任何估计器的准确性产生负面影响。另一个限制是MCMC的最新进展，特别是建立在有利的不可逆马尔可夫链上的进展，不能用于各种大图采样任务，因为它们需要基本状态空间的全局知识，缺乏分布实现，无约束的状态空间，以及简化的成本假设。本研究的目的是充分挖掘爬行采样器的潜力，使采样器在适当构造的图域上自适应并可能交互，从而在大范围的图采样任务中超越当前的现状。具体地说，该项目的目标是：(I)建立一个理论框架，通过在具有给定成本预算的挑战接入环境下最佳地平衡样本质量和数量之间的权衡，来构建一套成本效率高的采样策略；(Ii)通过充分利用过去的信息来设计一类自适应随机游动，以在获得的样本上实现最小的时间相关性，并通过集体控制随机游动来实现最大的空间探索；以及(Iii)扩展标准的MCMC工具包，以更快和更具成本效率地探索可行的子图/配置和图上的计算/优化，以及广泛的验证，以在现实中创建实用和可用的解决方案。这项研究对广泛的多学科应用具有很高的潜在影响，包括采样大规模图表以进行统计推理和有效估计，以及用于不同学科中组合优化的随机化算法，其中标准的MCMC方法一直占主导地位，但也限制了我们的理解。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Sampling and estimating structural information from large-scale networks or graphs has been central to our understanding of the network dynamics and its rich set of applications. Markov Chain Monte Carlo (MCMC) has been the key enabler for a broader context of graph sampling, including estimating the properties of large graphs, sampling the corpus of documents indexed by search engines, sampling records from hidden databases behind Web forms, identifying subgraphs of certain characteristics and frequent graph pattern matching. Despite versatile applications of the MCMC methods and their customized algorithms for analyzing graph-structured data in various forms, there still exist critical challenges and limitations in the literature centered around the MCMC methods. One is the 'cost' consumption/constraints associated with the sampling operation, which limits the size of total samples obtained and negatively affects the accuracy of any estimator based on the obtained samples. Another limitation is that the recent advances in MCMC, especially built up on favorable non-reversible Markov chains, cannot be leveraged to the various large-graph sampling tasks, due to their required global knowledge of the underlying state space, lack of distribution implementation, unconstrained state space, as well as the simplified cost assumption. The goal of this research is to fully exploit the potentials of a set of crawling samplers by making the samplers adaptive and possibly interactive on a properly constructed graph domain, to transcend the current status-quo in the wide range of graph sampling tasks. Specifically, the project aims to: (i) build a theoretical framework to construct a suite of cost-efficient sampling policies by optimally balancing the tradeoff between the sample quality and quantity under challenged access environments with a given cost budget, (ii) design a class of adaptive random walks by fully exploiting the past information to achieve minimal temporal correlations over the obtained samples and by controlling the random walks collectively to enable maximal space exploration, and (iii) extend the standard MCMC toolkits toward faster and more cost-efficient exploration of feasible subgraphs/configurations and computing/optimization on a graph, along with extensive validations to create practical and usable solutions in reality. This research has a high potential impact on a vast range of multi-disciplinary applications, including sampling large-scale graphs for statistical inference and efficient estimation and randomized algorithms for combinatorial optimizations in various disciplines, where the standard MCMC methods have been dominant but also constrained our understanding.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.