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

III：小型：协作研究：大规模网络的经济高效采样和估计

• 批准号: 1908375
• 负责人: Chul-Ho Lee
• 金额: $ 25万
• 依托单位: Florida Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908375&HistoricalAwards=false
• 关键词: III; Small; Collaborative; Research; Cost

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.

来自大规模网络或图形的采样和估算结构信息对于我们对网络动态及其丰富应用集集的理解至关重要。马尔可夫链蒙特卡洛（MCMC）一直是更广泛的图形采样背景的关键推动者，包括估计大图的属性，对搜索引擎索引的文档语料库进行采样，从隐藏的数据库背后的隐藏数据库中采样记录，识别某些特征的子分类，并识别某些特征和频繁的图形模式匹配。尽管MCMC方法的多功能应用及其定制算法用于分析各种形式的图形结构数据，但仍存在围绕MCMC方法的文献中的关键挑战和局限性。一个是与采样操作相关的“成本”消耗/约束，该操作限制了获得的总样品的大小，并基于获得的样品对任何估计器的准确性产生负面影响。另一个局限性是，MCMC的最新进展，尤其是建立在有利的非可逆马尔可夫链上的基础上，由于其所需的全球对基本状态空间的了解，缺乏分配的实施，不受约束的状态空间以及简化的成本假设，因此无法将各种大型抽样任务利用。这项研究的目的是通过使采样器自适应和可能在正确构造的图形域上进行自适应和可能交互式来充分利用一组爬行采样器的电势，以在广泛的图形采样任务中超越当前状态。具体而言，该项目的目的是：（i）建立一个理论框架，通过在挑战的访问环境中最佳平衡样品质量和数量之间的折衷与给定的成本预算，（ii）设计一类自适应随机步行，通过实现最小的信息，并实现最小的随机步行，并通过实现最小的时间，并通过实现较小的时间来控制，并通过实现较小的时间来控制样本质量和数量，从而构建了一系列具有成本效益的抽样策略，并实现了最小的随机步行。探索和（iii）将标准的MCMC工具包扩展到对可行的子图/配置以及图表上可行的子图/配置和计算/优化的更快，更具成本效益的探索，以及在现实中创建实用和可用的解决方案的广泛验证。这项研究对广泛的多学科应用具有很大的潜在影响，包括对统计推理和有效估计和有效估计和随机算法进行大规模图表，以在各种学科中进行组合优化，其中标准的MCMC方法在其中占主导地位，但也限制了我们的理解。更广泛的影响审查标准。

项目成果

An Efficient and Scalable Algorithm for Estimating Kemeny's Constant of a Markov Chain on Large Graphs

• DOI: 10.1145/3447548.3467431
• 发表时间: 2021-08
• 期刊: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining
• 作者: Shiju Li;Xin Huang;Chul-Ho Lee

Estimating Distributions of Large Graphs from Incomplete Sampled Data

• DOI: 10.23919/ifipnetworking52078.2021.9472848
• 发表时间: 2021-06
• 期刊: 2021 IFIP Networking Conference (IFIP Networking)
• 作者: Shiju Li;Xin Huang;Chul-Ho Lee

Trapping Malicious Crawlers in Social Networks

• DOI: 10.1145/3340531.3412004
• 发表时间: 2020-10
• 期刊: Proceedings of the 29th ACM International Conference on Information & Knowledge Management
• 作者: Shiju Li;Chul-Ho Lee;Do Young Eun