We argue that the standard graph Laplacian is preferable for spectral
partitioning of signed graphs compared to the signed Laplacian. Simple examples
demonstrate that partitioning based on signs of components of the leading
eigenvectors of the signed Laplacian may be meaningless, in contrast to
partitioning based on the Fiedler vector of the standard graph Laplacian for
signed graphs. We observe that negative eigenvalues are beneficial for spectral
partitioning of signed graphs, making the Fiedler vector easier to compute.

本文通过简单例子证明，在有符号图中，基于有符号拉普拉斯矩阵的算法比基于符号化拉普拉斯矩阵的算法更好地执行图谱划分，而负特征值有助于计算 Fiedler 向量。

关于符号图的谱分割

On spectral partitioning of signed graphs

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.

研究随机图中将顶点划分为块的谱技术，通过修改邻接谱分区算法，只需估计通信概率矩阵的秩上限，从而在模型错配的情况下实现一致性，也适用于具有多种模态的邻接表以及有向或无向的图。

在未知模型参数时，针对随机块模型的一致的邻接谱划分

Consistent adjacency-spectral partitioning for the stochastic block  model when the model parameters are unknown

Spectral partitioning is a simple, nearly-linear time, algorithm to find
sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for
the quality of the approximation found by the algorithm. Local graph
partitioning algorithms [ST08,ACL06,AP09] run in time that is nearly linear in
the size of the output set, and their approximation guarantee is worse than the
guarantee provided by the Cheeger inequalities by a polylogarithmic
$\log^{\Omega(1)} n$ factor. It has been a long standing open problem to design
a local graph clustering algorithm with an approximation guarantee close to the
guarantee of the Cheeger inequalities and with a running time nearly linear in
the size of the output.
In this paper we solve this problem; we design an algorithm with the same
guarantee (up to a constant factor) as the Cheeger inequality, that runs in
time slightly super linear in the size of the output. This is the first
sublinear (in the size of the input) time algorithm with almost the same
guarantee as the Cheeger's inequality. As a byproduct of our results, we prove
a bicriteria approximation algorithm for the expansion profile of any graph.
Let $\phi(\gamma) = \min_{\mu(S) \leq \gamma}\phi(S)$. There is a polynomial
time algorithm that, for any $\gamma,\epsilon>0$, finds a set $S$ of measure
$\mu(S)\leq 2\gamma^{1+\epsilon}$, and expansion $\phi(S)\leq
\sqrt{2\phi(\gamma)/\epsilon}$. Our proof techniques also provide a simpler
proof of the structural result of Arora, Barak, Steurer [ABS10], that can be
applied to irregular graphs.
Our main technical tool is that for any set $S$ of vertices of a graph, a
lazy $t$-step random walk started from a randomly chosen vertex of $S$, will
remain entirely inside $S$ with probability at least $(1-\phi(S)/2)^t$. This
itself provides a new lower bound to the uniform mixing time of any finite
states reversible markov chain.

本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

近似扩张剖面和几乎最优局部图聚类

Approximating the Expansion Profile and Almost Optimal Local Graph  Clustering

We describe a new approximation algorithm for Max Cut. Our algorithm runs in
$\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an
approximation ratio of $.531$. On instances in which an optimal solution cuts a
$1-\epsilon$ fraction of edges, our algorithm finds a solution that cuts a
$1-4\sqrt{\epsilon} + 8\epsilon-o(1)$ fraction of edges.
Our main result is a variant of spectral partitioning, which can be
implemented in nearly linear time. Given a graph in which the Max Cut optimum
is a $1-\epsilon$ fraction of edges, our spectral partitioning algorithm finds
a set $S$ of vertices and a bipartition $L,R=S-L$ of $S$ such that at least a
$1-O(\sqrt \epsilon)$ fraction of the edges incident on $S$ have one endpoint
in $L$ and one endpoint in $R$. (This can be seen as an analog of Cheeger's
inequality for the smallest eigenvalue of the adjacency matrix of a graph.)
Iterating this procedure yields the approximation results stated above.
A different, more complicated, variant of spectral partitioning leads to an
$\tilde O(n^3)$ time algorithm that cuts $1/2 + e^{-\Omega(1/\eps)}$ fraction
of edges in graphs in which the optimum is $1/2 + \epsilon$.

本研究提出了一种基于谱分割的近似算法，可以在多项式时间内解决 max cut 问题，并取得了高质量的结果。