Graph embeddings have emerged as a powerful tool for representing complex
network structures in a low-dimensional space, enabling the use of efficient
methods that employ the metric structure in the embedding space as a proxy for
the topological structure of the data. In this paper, we explore several
aspects that affect the quality of a vertex embedding of graph-structured data.
To this effect, we first present a family of flexible distance functions that
faithfully capture the topological distance between different vertices.
Secondly, we analyze vertex embeddings as resulting from a fitted
transformation of the distance matrix rather than as a direct result of
optimization. Finally, we evaluate the effectiveness of our proposed embedding
constructions by performing community detection on a host of benchmark
datasets. The reported results are competitive with classical algorithms that
operate on the entire graph while benefitting from a substantially reduced
computational complexity due to the reduced dimensionality of the
representations.

本文研究图嵌入的质量以及其在社区检测方面的有效性，通过使用灵活的距离函数捕捉不同顶点之间的拓扑距离，将顶点嵌入作为距离矩阵的变换结果进行分析，并在多个基准数据集上进行评估。结果表明，该方法操作于降维表示，使得计算复杂度大为减少，且性能与传统算法相媲美。

图顶点嵌入：距离、正则化和社区检测

Graph Vertex Embeddings: Distance, Regularization and Community  Detection

Spectral clustering is a popular and effective algorithm designed to find $k$
clusters in a graph $G$. In the classical spectral clustering algorithm, the
vertices of $G$ are embedded into $\mathbb{R}^k$ using $k$ eigenvectors of the
graph Laplacian matrix. However, computing this embedding is computationally
expensive and dominates the running time of the algorithm. In this paper, we
present a simple spectral clustering algorithm based on a vertex embedding with
$O(\log(k))$ vectors computed by the power method. The vertex embedding is
computed in nearly-linear time with respect to the size of the graph, and the
algorithm provably recovers the ground truth clusters under natural assumptions
on the input graph. We evaluate the new algorithm on several synthetic and
real-world datasets, finding that it is significantly faster than alternative
clustering algorithms, while producing results with approximately the same
clustering accuracy.

本研究提出了一种基于顶点嵌入的简单谱聚类算法，通过幂法计算的向量，在接近线性时间内计算顶点嵌入，并在输入图形的自然假设下，算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现，该算法与其他聚类算法相比，具有显著更快的速度，并且产生的聚类准确度基本相同。