利用光谱嵌入技术对随机游走特征值的锐利界限
本研究针对典型的谱聚类算法,探讨在一些较弱条件下其性能为何,还研究了利用少于 k 个特征向量进行嵌入的谱聚类,实验表明在合成和真实数据上,使用少于 k 个特征向量时,谱聚类也能够产生相当或更好的结果。
Aug, 2022
本研究证明:在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论,我们证明了对于随机块模型图,归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布,并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起,我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响,演示了嵌入方法都不占优势,因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
Jul, 2016
使用谱嵌入来估计随机块模型图中的块概率矩阵 B,在平均度数以 n 的 Ω(√n) 的速率增长时,我们建立了渐进正常性结果;当 B 是全秩的时,从谱嵌入得到的 B 的估计是渐近有效的;当 B 是奇异的时,从谱嵌入得到的估计可以比在没有排名假设的情况下最大化对数似然获得的估计具有更小的均方误差,并且可以几乎像假定已知 rk (B) 的真实 MLE 一样有效。
Oct, 2017
本文提出了一种新的混合成员随机块模型,使用频谱嵌入来生成节点向量表示,并通过使用高斯混合模型进行频谱聚类以及拟合保持最小体积的简单形体,可以在异 Philic 连接和消极的特定要求中提供更好的表现。
Sep, 2017
该论文研究了高阶重复本征值与稀疏割的关系,探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中,并应用几何考虑进行嵌入的聚类算法的理论基础,并证明了在所有图形中,存在一组大小不超过 2n/k 的集合,其扩展至多为 O (sqrt (λklogk)),从理论上提供了这些算法的近乎最优权衡。
Nov, 2011
本研究提出了一种基于顶点嵌入的简单谱聚类算法,通过幂法计算的向量,在接近线性时间内计算顶点嵌入,并在输入图形的自然假设下,算法能够可靠地恢复出真实聚类结果。通过在多个合成和现实世界数据集上的评估发现,该算法与其他聚类算法相比,具有显著更快的速度,并且产生的聚类准确度基本相同。
Oct, 2023
本文引入了一种新的超图拉普拉斯算子,并研究了其光谱。通过该算子的第二小本征值,证明了超图的扩展性和混合时间,并进一步将这些结果推广到了图的节点扩展。
Aug, 2014
本研究提出了针对图中节点嵌入的 out-of-sample extension 问题的两种解决方案,并在随机点积图的情况下,证明了这两种方法的正确性,并给出了最小二乘估计的组合中心极限定理的证明。
Feb, 2018
该研究使用基于矩阵草图的方法来解决在大规模图分析中传统方法遇到的挑战,尤其是无监督学习的社区结构划分问题,实验表明该方法在分配内存中可以获得出色的聚类效果,同时提高了聚类速度。
Jul, 2020
通过引入不同的连通性矩阵(如邻接、拉普拉斯和标准化拉普拉斯矩阵),我们研究了非均匀超图的基础加权图的谱特性,并展示了这些矩阵的谱特性可以很好地研究超图的不同结构特性。通过这些操作符的特征值研究超图的连通性。通过对 Laplacian 矩阵和标准化 Laplacian 矩阵的最小非平凡特征值进行边界限制来定义超图上的 Cheeger 恒量。此外,我们还介绍了关于超图上的 Ricci 曲率的两种不同方法。
Nov, 2017