III: Small: Parametric Statistical Models to Support Statistical Hypothesis Testing over Graphs

III：小型：支持图形统计假设检验的参数统计模型

• 批准号: 1219015
• 负责人: Vishwanathan Swaminathan
• 金额: $ 49.18万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219015&HistoricalAwards=false
• 关键词: III; Small; Parametric; Statistical; Models

Graphs provide a natural representation of real-world networks e.g. world-wide web, biological networks, social networks. There is a growing body of work on both models of network structure and algorithms to automatically discover patterns (e.g., communities) in the structure. However, statistical methods for assessing the significance of discovered patterns or distinguishing between alternative models have received less attention. Robust statistical models, which can accurately represent distributions over collections of graphs, are critical for principled quantitative investigation of networks and their properties. Specifically, since sampling distributions (either analytical or empirical) can be used to determine the likelihood of a given sample, statistical models facilitate hypothesis testing and anomaly detection (e.g., graphs with low likelihood can be flagged as anomalous). However, unlike metric spaces the space of graphs exhibits a combinatorial structure which poses significant theoretical and practical challenges which need to be overcome for accurate estimation and efficient inference. This project investigates the interplay between choice of model representation, parameter estimation, and sampling/inference to develop statistical models that can accurately estimate (parametric) probability distributions over the space of graphs (i.e., graph populations). Speicifically, the project focuses on a novel probabilistic graph model that generates graphs by quilting together a set of subgraphs sampled from simpler basis graph models and the application of the resulting model to (i) explore and define graph classes, (ii) detect anomalies and assess their significance, and (iii) investigate graph dynamics and formally characterize notions of temporal stationarity and dynamic evolution.The proposed work will advance the state of the art in probabilistic models, and rigorous statistical methods for analyis, of graph structured data. The proposed work also contributes to research-based training of graduate and undergraduate students at Purdue University. All of the software, publications, and data resulting from the project will be freely disseminated to the larger research and educational community.

图提供了真实世界网络的自然表示，例如万维网、生物网络、社交网络。 在网络结构模型和自动发现模式的算法（例如，社区）的结构。然而，用于评估发现的模式的重要性或区分替代模型的统计方法受到的关注较少。鲁棒的统计模型可以准确地表示图集合上的分布，对于网络及其属性的原则性定量研究至关重要。具体地，由于采样分布（分析的或经验的）可以用于确定给定样本的可能性，因此统计模型便于假设检验和异常检测（例如，具有低可能性的图可以被标记为异常）。然而，与度量空间不同的是，图的空间具有组合结构，这带来了重大的理论和实践挑战，需要克服准确的估计和有效的推理。该项目研究模型表示，参数估计和抽样/推断的选择之间的相互作用，以开发统计模型，可以准确地估计（参数）概率分布在图形空间（即，图种群）。具体来说，该项目侧重于一种新的概率图模型，该模型通过将从更简单的基础图模型中采样的一组子图缝合在一起来生成图形，并将所生成的模型应用于（i）探索和定义图形类，（ii）检测异常并评估其重要性，以及（iii）研究图动力学，并正式表征时间平稳性和动态演化的概念。拟议的工作将推进国家的概率模型和严格的统计分析方法。拟议的工作也有助于在普渡大学的研究生和本科生的研究为基础的培训。该项目产生的所有软件、出版物和数据将免费传播给更大的研究和教育界。