光谱保留图稀疏化和粗化的统一框架
本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法,证明了任何图都有近乎线性大小的谱稀疏化,并给出了一个可在几乎线性时间内构建谱稀疏化的算法,该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。
Aug, 2008
该研究从不同的角度研究了图的加粗技术,并提出了一种保持图距离的方法,该方法使用 Gromov-Wasserstein(GW)距离,并采用加权核 K-means 方法最小化两个图的距离及其加粗版本之间的差异,以此来改进现有的谱保存方法。研究还包括一组实验,支持理论和方法,包括利用谱信息对图进行分类和回归。
Jun, 2023
本文探讨了粗化对一般图的光谱特性的影响,发现主本征值和本征空间在新旧图拉普拉斯矩阵之间成立。研究结果可以应用于利用粗化的学习算法,尤其是在谱聚类中,该现象缺乏正式的验证。
Feb, 2018
图简化技术是一种应对大型图数据集复杂性和规模的有效方法,本调查研究对图稀疏化、图粗化和图凝聚等简化方法进行了全面概述,并阐述了它们在不同场景中的实际应用,为该领域的发展提供了技术综述和重要研究方向。
Jan, 2024
本文提出了一种相似性感知的谱图稀疏化框架,利用有效的谱偏树边嵌入和过滤方案构建谱稀疏化,实现了保证谱相似度(相对条件数)水平的过滤,同时介绍了迭代图密度增加方案以促进高度病态问题的有效过滤。该方法已验证了各种公共领域稀疏矩阵收集到的图表,包括与 VLSI CAD、有限元分析、社会和数据网络频繁研究的许多机器学习和数据挖掘应用相关的图表。
Nov, 2019
本文考虑保留原图的一个子图、寻找 k - 边加权图来加强原图的谱稀疏化问题,给出可行条件及多项式时间算法,并在超稀疏化问题和谱优化问题方面得出了应用结果。
Dec, 2009
这篇论文证明了每个图形都有一个谱稀疏器,其边数与其顶点数成线性关系。特别地,通过 Laplacian matrices 构造的谱稀疏器提供了对图形的光谱映射,令其成为扩展图的推广。此外,该论文提供了一个简单的确定性多项式时间算法来构造这种稀疏器。
Aug, 2008
本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图,该算法基于三种新技术,并使用新的潜力函数,通过半定规划求解构造单侧频谱稀疏子图。
Feb, 2017
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
本文提出了一种基于相似度感知的谱图度规化框架,利用有效的谱离线嵌入和过滤方案构建保证谱相似度(相对条件数)水平的谱度规化器,并引入迭代图稠密化方案以促进高度病态问题的有效过滤。
Nov, 2017