  Any modern network inference paradigm must incorporate multiple aspects of
network structure, including information that is often encoded both in vertices
and in 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. We address this gap 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. We prove concentration inequalities for the spectrum of a
line graph, and then 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
also demonstrate that the line graph of a stochastic block model exhibits
underlying block structure, and we synthesize and test our methods in
simulations for cluster recovery and edge covariate inference in stochastic
block model graphs.
