Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been successfully used for graph partitioning, hidden clique recovery and graph coloring. In this paper, we study the power of spectral algorithms using two matrices in a graph partitioning problem. We use two different matrices resulting from two different encodings of the same graph and then combine the spectral information coming from these two matrices. We analyze a two-matrix spectral algorithm for the problem of identifying latent community structure in large random graphs. In particular, we consider the problem of recovering community assignments exactly in the censored stochastic block model, where each edge status is revealed independently with some probability. We show that spectral algorithms based on two matrices are optimal and succeed in recovering communities up to the information theoretic threshold. On the other hand, we show that for most choices of the parameters, any spectral algorithm based on one matrix is suboptimal. This is in contrast to our prior works (2022a, 2022b) which showed that for the symmetric Stochastic Block Model and the Planted Dense Subgraph problem, a spectral algorithm based on one matrix achieves the information theoretic threshold. We additionally provide more general geometric conditions for the (sub)-optimality of spectral algorithms.

翻译：光谱运算法是图形优化和推断问题的主要工具之一。 通常, 图形被编码成矩阵和表层图和表层图值, 然后用来解决给定的图形问题。 光谱算算法被成功地用于图形分割、 隐藏的球状恢复和图形颜色。 在本文中, 我们用两个矩阵来研究光谱算法在图形分区问题中的力量。 我们使用来自同一图两个不同编码的两个不同的矩阵的不同矩阵, 然后将来自这两个矩阵的光谱信息合并起来。 我们分析用于在大随机图表中识别潜在社区结构问题的双矩阵光谱谱谱谱谱谱算法和等值值。 特别是, 我们考虑的是完全在受检查的区划区划区划模型模型中恢复社区任务的问题, 每个边缘状态都以某种概率独立显示。 我们显示基于两个矩阵的光谱算算算法是最佳的, 成功地将社区恢复到信息温度阈值。 在另一手, 我们显示大多数参数的选择, 任何基于一个矩阵的光谱矩阵的光谱运算算算法, 在一个矩阵上, 20个基底图的底图的底图显示一个基图的底图, 这个基图是20号的基图的基图的基图, 。 这个基图的基图的底图的基图的基图的基图的基图的基图的基图的比比。</s>