该研究探讨了一种可并行化的方法,通过对大型图的频谱进行扩展,以加速奇异值分解求解器和谱聚类,并利用多项式逼近来实现此目的。
Jul, 2022
本文研究了网络或图谱的光谱问题。在图太大无法明确计算光谱的情况下,提出了一种次线性时间算法,可以计算光谱的简洁表示,并证明了其实用性。同时探讨了该算法在有界度图模型下的属性测试的实际应用。
Dec, 2017
本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法,证明了任何图都有近乎线性大小的谱稀疏化,并给出了一个可在几乎线性时间内构建谱稀疏化的算法,该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。
Aug, 2008
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
提供了同时稀疏化和粗化图形的统一框架,其原理基于图拉普拉斯算子的物理解释,并使用一种无偏处理程序来减少图形并保留其大规模结构。
Feb, 2019
介绍了一个广义图拉普拉斯算子,旨在研究超图的特定组合属性,如多路扩展和直径,并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
本文提出了一种基于图信号处理的方法,采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤,该方法在控制误差的同时计算时间效率可达到数个数量级的提升,并在人工合成数据和真实网络数据集上进行测试。
Feb, 2016
该研究从不同的角度研究了图的加粗技术,并提出了一种保持图距离的方法,该方法使用 Gromov-Wasserstein(GW)距离,并采用加权核 K-means 方法最小化两个图的距离及其加粗版本之间的差异,以此来改进现有的谱保存方法。研究还包括一组实验,支持理论和方法,包括利用谱信息对图进行分类和回归。
Jun, 2023
提出了一种灵活的超图 1-Laplacian 定义框架,包括依赖于边的顶点权重,以反映超边内不同顶点的重要性,增强了超图模型的表现能力。利用超图 1-Laplacian 的第二个最小特征向量进行聚类,可以实现比传统 Laplacian 更高的聚类精度,而且该方法可以在现实数据集上得到验证。在特定情况下,超图 1-Laplacian 等效于相关图的 1-Laplacian,可以更有效地计算特征向量,方便应用于更大的数据集。
Apr, 2023
本文提出了一种基于图信号处理的快速谱聚类算法,通过使用图滤波器对随机信号进行谱聚类距离矩阵的估计,利用这些随机向量的随机性来估计聚类数目 k,相较于传统谱聚类方法,我们的方法在大规模数据集上表现相当且速度至少快二倍。
Sep, 2015