A0451
Title: Higher-order accurate two-sample network inference and network hashing
Authors: Dong Xia - Hong Kong University of Science and Technology (Hong Kong) [presenting]
Abstract: Two-sample hypothesis testing for comparing two networks is an important yet difficult problem. Major challenges include: potentially different sizes and sparsity levels; non-repeated observations of adjacency matrices; computational scalability; and theoretical investigations, especially on finite-sample accuracy and minimax optimality. The first provably higher-order accurate two-sample inference method is proposed by comparing network moments. The method extends the classical two-sample t-test to the network setting. We make weak modelling assumptions and can effectively handle networks of different sizes and sparsity levels. We establish strong finite-sample theoretical guarantees, including rate-optimality properties. Our method is easy to implement and computes fast. We also devise a novel nonparametric framework of offline hashing and fast querying, particularly effective for maintaining and querying very large network databases. The effectiveness of the method by comprehensive simulations. The method is applied to two real-world data sets and discovers interesting novel structures.
