Title: A nonparametric test of co-spectrality in networks
Authors: Srijan Sengupta - North Carolina State University (United States) [presenting]
Abstract: Living in an interconnected world where network-valued data arises in many domains, statistical network analysis has emerged as an active area. However, the topic of hypothesis testing in networks has received relatively less attention. We consider the problem where one is given two networks, and the goal is to test whether the given networks are cospectral, i.e., they have the same non-zero eigenvalues. Cospectral graphs have been well studied in graph theory and computer science. Cospectrality is relevant in real-world networks since it implies that the two networks share several important path-based properties, such as the same number of closed walks of any given length, the same epidemic threshold, etc. However, to the extent of our knowledge, there has not been any formal statistical inference work on this topic. We propose a non-parametric test of co-spectrality by leveraging some recent developments in random matrix theory. We develop two versions of the test --- one based on an asymptotic bound and one based on bootstrap resampling. We establish theoretical results for the proposed test and demonstrate its empirical accuracy using synthetic networks sampled from a wide variety of models as well as several well-known real-world network datasets.