Title: Spectral embedding of weighted graphs
Authors: Ian Gallagher - University of Bristol (United Kingdom) [presenting]
Patrick Rubin-delanchy - University of Bristol (United Kingdom)
Carey Priebe - Johns Hopkins University (United States)
Andrew Jones - University of Bristol (United Kingdom)
Anna Bertiger - Microsoft (United States)
Abstract: The statistical analysis of a weighted graph through spectral embedding is considered. Under a latent position model in which the expected adjacency matrix has a low rank, we prove uniform consistency and a central limit theorem for the embedded nodes, treated as latent position estimates. In the special case of a weighted stochastic block model, this result implies that the embedding follows a Gaussian mixture model with each component representing a community. We exploit this to formally evaluate different weight representations of the graph using Chernoff information. For example, in a network anomaly detection problem where we observe a p-value on each edge, we recommend against directly embedding the matrix of p-values, and instead, using threshold or log $p$-values, depending on network sparsity and signal strength.