WWWMar, 2020

大规模网络图精确谱距离的近似计算方法 SLaQ

PDF
TL;DR本文提出了一种有效的图谱比较方法 SLaQ，该方法使用谱分析技术计算大规模图结构的相似度，可在线性时间内获取误差较小的结果。实验结果表明 SLaQ 的精度比现有方法提高了数个数量级，且在单机上能够在几分钟内比较百万级别的图。
spectral analysisgraph comparisonslaqapproximation techniquemulti-scale structure
发现论文，激发创造
  • NetLSD: 倾听图形的形状

    本文提出了 Network Laplacian Spectral Descriptor（NetLSD）方法，可以实现对大型图的快速比较，该方法是目前为止唯一一种既具有置换和尺寸等变性，同时又可扩展和高效计算的图形表示方法，并且具有比以往方法更好的表达性和效率。

    May, 2018

  • 图的频谱对齐

    本文提出了一种改进的广义图对齐方法，该方法结合了匹配和不匹配两种条件，在不同的图案例中，通过矩阵的谱分解达到了较好的性能表现，尤其在对齐正则图结构方面显著优于现有方法。

    Feb, 2016

  • 压缩谱聚类

    本文提出了一种基于图信号处理的方法，采用图滤波和随机采样技术加速生成 Laplacian 矩阵特征向量和 k-means 聚类算法步骤，该方法在控制误差的同时计算时间效率可达到数个数量级的提升，并在人工合成数据和真实网络数据集上进行测试。

    Feb, 2016

  • 优化 k 最近邻图以实现计算上有效的谱聚类

    本文提出了一种在精简边界的 $k$-nearest neighbor graph 中基于局部统计的数据代表子集的近似谱聚类算法的方法，以提高其计算效率，且在人工合成的测试数据集和真实数据集中实验表明与常规方法相比较，该方法具有性能一致性和较少边界数量的特点。

    Feb, 2023

  • 图的频谱稀疏化

    本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法，证明了任何图都有近乎线性大小的谱稀疏化，并给出了一个可在几乎线性时间内构建谱稀疏化的算法，该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。

    Aug, 2008

  • 小批量谱聚类

    采用自适应随机梯度优化的实用方法可以学习拉普拉斯矩阵的完整光谱，且每个迭代的成本与样本数量成线性关系，实验证明其具备比近似方法更好的计算可扩展性。

    Jul, 2016

  • GRASS：基于可扩展的谱扰动分析的图谱稀疏化算法

    本文提出了一种相似性感知的谱图稀疏化框架，利用有效的谱偏树边嵌入和过滤方案构建谱稀疏化，实现了保证谱相似度（相对条件数）水平的过滤，同时介绍了迭代图密度增加方案以促进高度病态问题的有效过滤。该方法已验证了各种公共领域稀疏矩阵收集到的图表，包括与 VLSI CAD、有限元分析、社会和数据网络频繁研究的许多机器学习和数据挖掘应用相关的图表。

    Nov, 2019

  • 可解释的图谱谱聚类文本文档

    通过提出基于组合 Laplacian 的图谱聚类结果的解释方法，实现了将聚类结果与文本内容之间的桥梁构建， 找到了与文档内容相关的谱聚类的解释方法。

    Aug, 2023

  • 谱聚类的平均灵敏度

    通过对拉普拉斯特征值极小值的研究，以平均灵敏度为指标，探究了谱聚类方法对于边缘扰动的稳健性，研究结果表明，当输入图像存在簇结构时，谱聚类方法对于边缘扰动是稳定的。

    Jun, 2020

  • 带最优图的统一谱聚类

    本文提出了一种改进的光谱聚类算法，旨在解决预定义的相似性图可能不是合适的聚类结果，并且传统离散化解决方法与光谱解决方案可能不一致的问题，并引入多核学习来解决如何选择最适合特定数据集的核的应用挑战。实验结果表明，该方法相比于现有的聚类方法具有更好的性能。

    Nov, 2017