  For random graphs distributed according to a stochastic block model, we
consider the inferential task of partioning vertices into blocks using spectral
techniques. Spectral partioning using the normalized Laplacian and the
adjacency matrix have both been shown to be consistent as the number of
vertices tend to infinity. Importantly, both procedures require that the number
of blocks and the rank of the communication probability matrix are known, even
as the rest of the parameters may be unknown. In this article, we prove that
the (suitably modified) adjacency-spectral partitioning procedure, requiring
only an upper bound on the rank of the communication probability matrix, is
consistent. Indeed, this result demonstrates a robustness to model
mis-specification; an overestimate of the rank may impose a moderate
performance penalty, but the procedure is still consistent. Furthermore, we
extend this procedure to the setting where adjacencies may have multiple
modalities and we allow for either directed or undirected graphs.

Methodology;Spectral Theory