Sparse graphs using exchangeable random measures

• 成果类型: Article
• 署名作者: Caron, Francois; Fox, Emily B.
• 署名单位: University of Oxford; University of Washington; University of Washington Seattle
• 刊物名称: JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY
• ISSN/ISSBN: 1369-7412
• DOI: 10.1111/rssb.12233
• 发表日期: 2017
• 页码: 1295-1366
• 关键词: convergent sequences; network; models; distributions; statistics; simulation; inference; arrays; priors; noise

摘要

Statistical network modelling has focused on representing the graph as a discrete structure, namely the adjacency matrix. When assuming exchangeability of this arraywhich can aid in modelling, computations and theoretical analysisthe Aldous-Hoover theorem informs us that the graph is necessarily either dense or empty. We instead consider representing the graph as an exchangeable random measure and appeal to the Kallenberg representation theorem for this object. We explore using completely random measures (CRMs) to define the exchangeable random measure, and we show how our CRM construction enables us to achieve sparse graphs while maintaining the attractive properties of exchangeability. We relate the sparsity of the graph to the Levy measure defining the CRM. For a specific choice of CRM, our graphs can be tuned from dense to sparse on the basis of a single parameter. We present a scalable Hamiltonian Monte Carlo algorithm for posterior inference, which we use to analyse network properties in a range of real data sets, including networks with hundreds of thousands of nodes and millions of edges.