图邻接谱嵌入的样本外扩展

Feb, 2018

Out-of-sample extension of graph adjacency spectral embedding

Keith Levin, Farbod Roosta-Khorasani, Michael W. Mahoney, Carey E. Priebe

TL;DR本研究提出了针对图中节点嵌入的 out-of-sample extension 问题的两种解决方案，并在随机点积图的情况下，证明了这两种方法的正确性，并给出了最小二乘估计的组合中心极限定理的证明。

Abstract

Many popular dimensionality reduction procedures have out-of-sample extensions, which allow a practitioner to apply a learned embedding to observations not seen in the initial training sample. In this work, we consider the problem of obtaining an out-of-sample extension for the adjacen

dimensionality reduction adjacency spectral embedding latent position model least-squares objective maximum-likelihood formulation

发现论文，激发创造

邻接矩阵和拉普拉斯矩阵谱嵌入的外样本扩展极限定理

研究了针对图嵌入方法的样本外推问题，通过最小二乘方法和极大似然方法得出的新数据点嵌入向量近似服从中心极限定理及浓度不等式，并提供了一个既简捷又精确的计算成本与估计精度权衡框架。

Sep, 2019

谱嵌入的统计解释：广义随机点积图

本文提出了一种新的混合成员随机块模型，使用频谱嵌入来生成节点向量表示，并通过使用高斯混合模型进行频谱聚类以及拟合保持最小体积的简单形体，可以在异 Philic 连接和消极的特定要求中提供更好的表现。

Sep, 2017

随机块模型图的一致邻接谱嵌入

本文介绍一种通过嵌入过程估算随机块模型中节点的块成员资格的方法，并证明了该方法的一致性和可靠性，可用于大规模图形和参与虚拟谱聚类等应用。

Aug, 2011

关于随机块模型图的谱嵌入性能和揭示网络结构

本文分析 Laplacian 和 adjacency 频谱嵌入在随机块模型图中块分配恢复方面的相对性能，并研究了嵌入性能与底层网络结构之间的关系，结果表明 Laplacian spectral embedding 更适用于相对稀疏的图，而 adjacency spectral embedding 更适用于核心 - 边缘网络结构。

Aug, 2018

分布式草图缩放图聚类

该研究使用基于矩阵草图的方法来解决在大规模图分析中传统方法遇到的挑战，尤其是无监督学习的社区结构划分问题，实验表明该方法在分配内存中可以获得出色的聚类效果，同时提高了聚类速度。

Jul, 2020

通过邻接谱嵌入理想地对随机块模型图进行聚类

本文证明了邻接谱嵌入可以用于完美聚类随机块模型和度校正随机块模型，以及更一般的随机点积图模型。

Oct, 2013

隐私保护的随机块模型邻接谱嵌入

该论文提出了一种差分隐私邻接谱嵌入算法，用于随机块模型，实现了邻接谱嵌入的近似一致性，并且在确定的隐私参数下，可以实现与邻接谱嵌入相当的准确性。

May, 2019

随机内积图的普适一致潜在位置估计及顶点分类

本文介绍了使用邻接矩阵的特征分解可以一致地估计从分布中独立同分布的潜在位置，并且如果类标签对于趋近于无穷的顶点观察，则剩余的顶点可以使用 K 最近邻分类规则收敛于贝叶斯最优。我们使用模拟数据和从维基百科衍生的图表评估了提出的方法。

Jul, 2012

利用光谱嵌入技术对随机游走特征值的锐利界限

本文介绍了利用图的随机行走矩阵的前 k 个非平凡特征向量对图进行谱嵌入的方法，并使用此框架限制了所有图的所有特征值，并提出了一种新的工具 —— 谱嵌入，在分析可逆马尔可夫链中使用。

Nov, 2012

随机图中归一化拉普拉斯算子的特征向量的极限定理

本研究证明：在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论，我们证明了对于随机块模型图，归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布，并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起，我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响，演示了嵌入方法都不占优势，因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。

Jul, 2016