A0906
Title: Beyond the adjacency matrix: Random line graphs and inference for networks with edge attributes
Authors: Zachary Lubberts - University of Virginia (United States) [presenting]
Avanti Athreya - Johns Hopkins University (United States)
Carey Priebe - Johns Hopkins University (United States)
Youngser Park - Johns Hopkins University (United States)
Abstract: Any modern network inference paradigm must incorporate multiple aspects of network structure, including information often encoded in vertices and edges. Methodology for handling vertex attributes has been developed for a number of network models, but comparable techniques for edge-related attributes remain largely unavailable. This gap is addressed in the literature by extending the latent position random graph model to the line graph of a random graph, which is formed by creating a vertex for each edge in the original random graph and connecting each pair of edges incident to a common vertex in the original graph. Concentration inequalities are proved for the spectrum of a line graph and then establish that although naive spectral decompositions can fail to extract the necessary signal for edge clustering, there exist signal-preserving singular subspaces of the line graph that can be recovered through a carefully-chosen projection. Moreover, edge latent positions can be consistently estimated in a random line graph, even though such graphs are of random size, typically have a high rank, and possess no spectral gap. The results also demonstrate that the line graph of a stochastic block model exhibits underlying block structure, and the methods are synthesized and tested in simulations for cluster recovery and edge covariate inference in stochastic block model graphs.
