  We extend 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. We prove concentration inequalities for the
spectrum of a line graph, as well as limiting distribution results for the
largest eigenvalue and the empirical spectral distribution in certain settings.
For the stochastic blockmodel, we establish that although naive spectral
decompositions can fail to extract 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, we can consistently
estimate edge latent positions in a random line graph, even though such graphs
are of a random size, typically have high rank, and possess no spectral gap.
Our results demonstrate that the line graph of a stochastic block model
exhibits underlying block structure, and in simulations, we synthesize and test
our methods against several commonly-used techniques, including tensor
decompositions, for cluster recovery and edge covariate inference. By naturally
incorporating information encoded in both vertices and edges, the random line
graph improves network inference.
