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

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

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.