  Statistical inference on graphs often proceeds via spectral methods involving
low-dimensional embeddings of matrix-valued graph representations, such as the
graph Laplacian or adjacency matrix. In this paper, we analyze the asymptotic
information-theoretic relative performance of Laplacian spectral embedding and
adjacency spectral embedding for block assignment recovery in stochastic block
model graphs by way of Chernoff information. We investigate the relationship
between spectral embedding performance and underlying network structure
(e.g.~homogeneity, affinity, core-periphery, (un)balancedness) via a
comprehensive treatment of the two-block stochastic block model and the class
of $K$-block models exhibiting homogeneous balanced affinity structure. Our
findings support the claim that, for a particular notion of sparsity, loosely
speaking, "Laplacian spectral embedding favors relatively sparse graphs,
whereas adjacency spectral embedding favors not-too-sparse graphs." We also
provide evidence in support of the claim that "adjacency spectral embedding
favors core-periphery network structure."
