图形移动距离:一种用于几何图形的高效可计算距离度量
本文提出了一种针对属性图的伪度量(TMD),并研究了它与泛化的关系,显示出 TMD 捕捉了与图分类相关的属性,且良好相关性对于泛化的 GNNs 来说性能下降。
Oct, 2022
通过引入图测地线距离(GGD)度量,本文提出了一种用于评估图神经网络(GNNs)泛化性和稳定性的光谱框架。通过引入光谱图匹配过程找到节点对应关系并计算其测地线距离,通过减小较大图的尺寸但保留原始光谱特性的阻抗型光谱图粗化方案降低了图的大小。实验证明,所提出的 GGD 度量能够有效量化两个图之间的差异,包括节点之间的有效电阻、切割、随机行走的混合时间等结构(光谱)属性,与最新的 Tree-Mover's Distance(TMD)度量相比,提出的 GGD 度量在仅有部分节点特征可用时,对 GNN 的稳定性评估表现出显著改进。
Jun, 2024
本研究提出了一种基于数据并行的 Earth Mover's Distance 近似算法,具有线性时间复杂度以及适用于高维空间和高重叠概率分布的优势,在文本和图像领域中取得了较高的近似精度。
Dec, 2018
本文提出了一种计算大规模相关高维数据集之间的距离的快速方法,称为扩散地球移位距离(Diffusion Earth Mover's Distance)。通过建模数据集为分布并计算相互作用矩阵来实现,该方法的时间复杂度为 O (n),并且比基于树的算法更加准确和可微分,适用于深度神经网络等梯度下降框架。实验通过 210 个 COVID-19 样本的单细胞数据表明该方法比同等精确度的方法至少快两个数量级,且可以嵌入更高层次的患者流形中揭示患者间的结构和异质性,并可适用于其他医学和生物模型中大规模数据集的距离计算。
Feb, 2021
利用学习到的广义测地距离函数, LGGD 方法在图像处理、计算机图形学和计算机视觉领域中应用广泛,其在节点分类任务中具有改进的性能,并在真实图数据集上达到与最先进方法相竞争的结果,同时还展示了参数在图中广义测地方程中的可学习性以及新标签的动态包含能力。
Jul, 2024
本文提出了一种基于地标距离基础上的简洁的表征,称为 Geodesic Distance Descriptor (GDD),该方法可以有效地和准确地在几乎不损失信息的情况下近似匹配度量空间问题,可以提高现有的形状匹配程序的准确性和效率。
Nov, 2016
本文介绍了一种基于图傅里叶变换最大均值差的图分布与信号之间距离的计算方法,并在基准数据集和单细胞 RNA 测序数据分析中展示了其在基因聚类和细胞状态空间表征中的应用。
Jun, 2023
本文提出了一个新的距离度量方法,可以比较两个连续概率密度函数。主要优点是能够为高阶高斯混合模型提供解析闭合形式表达式,从而满足所有度量特性,这种特性在现实信号处理应用中非常有用。为解决 Gaussian 混合模型压缩问题,本文提出了一种基于优化的贪心算法 OGGMR,该算法使用了作者提出的度量作为准则,可以用低阶高斯模型逼近高阶的高斯混合模型,同时保留了原始混合模型的几何形状。实验结果表明,OGGMR 算法比其他同类算法更快更有效。
Jun, 2023
本文介绍了 QUBO 形式的 Graph Edit Distance (GED) 问题,它允许我们在量子芯片上实现两种不同的方法,即量子退火和变分量子算法,为机器学习和模式识别提供一种新颖的解决方案。
Nov, 2021
使用最近邻搜索来逼近地球移动距离(EMD),以实现高准确性、低时间复杂度和高内存效率;通过 GPU 的向量化进一步加快速度,比现有的近似 EMD 方法在图像分类和检索任务中达到 44 倍至 135 倍的速度优势,同时实现了更好的准确性、加速比和内存效率。
Jan, 2024