NeuroMatch 利用图神经网络将查询和目标图分解成小的子图,并在嵌入空间中直接实现子图匹配,实验证明其比现有的组合匹配方法快 100 倍,比现有的近似子图匹配方法精度高 18%。
Jul, 2020
本研究旨在探讨如何在当今大规模图形上开展可扩展性的图形处理,提出了一种新的图形坐标系统的设计空间,即通过将图嵌入到坐标空间的方式精确地近似节点距离,从而实现常数时间内的距离查询和最短路径查询,在 43 百万个节点的图中能提供更准确的结果,且可以很容易地扩展到定位节点对之间的最短路径,解决了大规模图形分析的难题。
Jul, 2011
在没有节点标签的情况下,我们提出了一种在不精确匹配的情况下识别子图与完整图之间节点对应关系的方法,该方法包括两个步骤:提取子图的最小唯一拓扑保持子集及在全图中查找可行匹配,实现基于边界可交换性的独特路径配对扩展匹配集,并通过共识算法。
Sep, 2022
本研究使用理论高效的并行图算法和优化技术,结合大规模图分析,能够使单机具有 1TB 内存的计算机在几分钟内处理超过 35 亿个节点和 1280 亿条边的实际网络图像。同时,研究组将开发的这些算法公开提供给社区,以用作图算法效果评价指标的基准。
May, 2018
本文提出了一种基于图遍历和压缩表征的方法,该方法编码可索引向量使用量化和利用图结构改进相似度估计。该方法在保证较小比较集的高精度及显著内存压缩的同时,在 64-128 字节每向量的操作点上,优于现有技术在二十亿规模公共基准测试中的表现。
Apr, 2018
本论文提出了一种快速的大型图匹配的近似算法,使用新的投影固定点方法和双向随机投影的方法实现算法,理论上保证收敛速度为线性,并在大型合成和真实图上进行了广泛的实验,与之前的算法相比,在速度和准确性方面都有更好的表现。
Jul, 2012
本文提出了针对流模型的新算法,用于发现图的局部密集组件,该算法在经过 O ((log n)/log (1+epsilon)) 次输入后,可以找到一个子图,其密度保证是最优解的 2 (1+epsilon) 倍。
Jan, 2012
本文提出了一种基于抽样的算法,有效地从大规模网络中准确估算子图统计量,并展示实验结果表明其能更加快速地完成与现行技术相同准确度的查询量(样本量)
Jun, 2013
本研究提出了一种名为二进制分布式图形算法的方法,该方法使用二进制编码与图形结构相结合以加速在线和离线程序,并通过回忆更多二进制候选项来实现与实值场景中的性能相当,废除了单个机器内存和磁盘存储的限制,对超过 30 亿张图像的阿里巴巴商品数据集进行的实验比较表明,该方法优于现有技术的在线 / 离线平衡。
Feb, 2021
本文提出了 D2Match,一种基于 Deep learning 和 Degeneracy 的子图匹配方法,通过证明子图匹配可以退化为子树匹配,并形象地表述成在二分图上的完美匹配问题,并利用图神经网络的内置树状聚合机制实现线性时间复杂度,实验结果证实了 D2Match 具有优秀的匹配效果。
Jun, 2023