🤖 machine learning

Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning

本文提出了 TRicci，一种受网络曲率启发的边稀疏化框架，该框架将 Forman-Ricci 曲率扩展到了有向加权时序图，在保持预测性能的同时，在各种数据集上实现了约 80% 的稀疏化以及 55.94% 的训练和推理时间缩减。

原作者： Poupak Azad, Cuneyt Gurcan Akcora, Kiarash Shamsi

发布于 2026-08-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Poupak Azad, Cuneyt Gurcan Akcora, Kiarash Shamsi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

现代世界运行在永不停歇的网络之上。金融市场、社交媒体信息流和通信系统并非静态的地图，而是互动的生命流，其中连接在每一秒都在形成、消逝和转变。为了理解这些系统，科学家们构建了被称为“时序图”（temporal graphs）的数字模型，这些模型不仅捕捉谁与谁相连，还记录了这些连接发生的精确时间。挑战在于，这些模型可能会变得极其庞大且密集，充斥着数以百万计的瞬时交互。处理如此大规模且快速变化的数据需要巨大的计算能力，这往往会导致分析速度变得极其缓慢，甚至使标准机器无法运行。研究人员的核心问题在于，如何在不丢失揭示系统实际运作方式的关键模式的前提下，剔除这些数据流中的噪声和冗余。

一个研究小组提出了一种通过观察这些连接的几何结构来解决该问题的新方法。他们并没有简单地统计节点互动的次数或随机删除连接，而是开发了一种衡量每次交互“曲率”的方法。想象一下这样一个景观：有些路径是宽阔、繁忙的高速公路，而另一些则是通往无处之地的狭窄、冗余的小径。在数学语言中，这个景观具有一种形状，研究人员借鉴了一个古老的几何概念——最初用于描述曲面的曲率——来衡量时序网络中每一条边的重要性。他们将这种方法称为 TRicci。它根据三个要素为每条连接分配一个分数：这两个端点的活跃程度、交互发生的时间近度，以及是否存在许多同时发生的类似交互从而使得该特定交互显得不再独特。

研究人员将这一评分系统应用于各种现实世界的数据，包括九个不同的区块链交易网络和三个涵盖从加密货币转账到在线产品评论的大型基准数据集。在这些网络中，单次交易可能是一个用户行为转变的关键信号，而数千次其他交易则可能是没有任何新信息的重复性噪声。通过计算这些海量数据集中每条边的曲率分数，团队可以将连接按重要性从高到低进行排序。随后，他们测试了一种简单的策略：仅保留前 20% 的连接（即那些具有最高曲率分数的连接），并丢弃剩余的 80%。

结果令人瞩目。当研究人员将这些精简后的稀疏图输入到标准预测模型中时，系统的表现几乎与使用完整的、未精简的数据时一样出色。事实上，在所有实验中，这些简化后的图保留了原始庞大网络 97.7% 的预测能力。这意味着，通过移除绝大部分的边，研究人员并未丧失预测未来网络活动、识别影响力用户或检测参与度变化的能力。该方法在识别网络中的“高速公路”（即那些承载独特结构和时间权重的交互）方面表现得尤为有效，同时过滤掉了那些干扰视角的冗余“小径”。

除了保持准确性外，该方法还带来了巨大的速度提升。由于模型需要处理的连接大幅减少，训练算法和进行预测所需的时间平均降低了 55.94%。在某些情况下，这种时间节省甚至更高，对于特定数据集达到了近 7 7%。这种效率的提升对于必须快速做出决策的实时应用至关重要，例如检测金融交易中的欺诈行为或监控社交平台上的信息传播。研究人员发现，交互的具体时机至关重要；在时间上接近发生的连接往往会相互竞争，而该方法成功识别了其中哪些竞争性交互更为显著。

研究还探讨了不同的边选择方式如何影响结果。他们测试了保留曲率最高的边是否比保留曲率最低的边或随机选择更有效。数据展示了一个清晰的模式：曲率最高的边始终持有最高的预测价值。这表明，在动态网络中，最重要的交互并不一定是频率最高的，而是那些能在局部活动背景中脱颖而出的交互。研究人员通过将该方法与几种旨在简化图的现有技术进行对比验证，证明了其方法在保持预测未来网络状态的能力方面始终优于其他方法。

这种方法的独特之处在于，它并不依赖于特定的机器学习模型来完成工作。相反，它作为一个通用的过滤器，可以在任何分析开始之前进行应用。研究人员证明，通过理解网络的局部几何结构——即一条边如何融入其时间与活动的即时邻域——就可以识别出系统的本质结构。这使得研究复杂系统成为一种更轻量、更快且更高效的方式，且不会牺牲从数据中获得的洞察力。研究结果表明，对于许多动态网络而言，理解全貌并不需要所有的连接，而通过对剩余边进行精细的、基于几何的选择，可以揭示系统演进的真实形态。

技术摘要：通过时序 Forman-Ricci 曲率进行边缘稀疏化以实现动态图学习

问题陈述

时序图学习对于分析具有持续演化交互作用的现实世界系统（如金融交易网络、通信系统和社交平台）至关重要。然而，从大规模时序图中学习面临着显著的计算挑战。随着交互作用的累积，网络变得密集且变化迅速，导致下游学习流水线（涉及快照构建、特征提取和模型训练）产生高昂的内存和运行时间成本。此外，稠密图通常包含许多对预测任务贡献微乎其微的边缘，从而引入了噪声和冗余。

现有的图稀疏化方法主要针对静态图，依赖于基于度（degree）或仅基于拓扑结构的准则，这些准则无法考虑到边缘的时序角色（例如，时间戳、近期性和随时间变化的竞争关系）。虽然最近的一些工作解决了时空设置下的问题，但它们通常侧重于特定的任务（如节点分类或预测），缺乏一种能够根据结构支持和时序上下文对有向加权时序图中的边缘进行排名的模型无关机制。

方法论：TRicci

作者提出了一种受网络曲率启发的边缘稀译框架 TRicci，专门为有向加权时序图设计。该方法将经典的 Forman–Ricci 曲率扩展到时序领域，为每个边缘分配一个重要性得分，以反映其结构支持、时序相关性和局部交互竞争。

核心组件

时序 Forman–Ricci 曲率公式化：
该框架适配了经典的“支持减去惩罚”结构的 Forman–Ricci 曲率。对于一条时序边缘 $e = (u, v, w_e, t_e)$ ，其得分计算如下：
$\text{TRicci}(e) = S_e - D_e$
- 端点支持 ( $S_e$ )： 衡量边缘相对于其端点活跃度的独特性。作者使用对数平滑后的节点活跃度（ $s(x) = \log(1 + \text{strength}(x))$ ）来防止高活跃节点主导得分。支持项与源节点和目标节点的平滑活跃度成反比。
- 时序竞争惩罚 ( $D_e$ )： 量化边缘在其局部时序邻域内的冗余度。该组件考虑了来自源节点和目标节点的传出边。关键在于，它采用了时序衰减核 $K(e, e', \tau) = \exp(-|t_e - t_{e'}|/\tau)$ 来对相邻边进行加权。在时间上接近的边会对惩罚产生更强的贡献，这反映了在时间上接近的交互通常提供重叠的结构信息。
基于快照的计算：
为了避免混合不同时序上下文中的交互，时序边流被划分为不重叠的离散时间快照。曲率得分在每个快照内独立计算，确保边缘的重要性相对于其局部时序上下文是相对的，且不存在未来信息泄露。
任务引导的边缘选择：
TRicci 作为一个模型无关的评分机制。在计算完曲率得分后，由任务引导的策略决定保留哪些边缘。作者通过验证评估了不同的策略（保留高曲率、低曲率或中间带宽的边缘）。实验表明，保留高曲率边缘（排名靠前的边缘）能获得最佳的预测保留效果。

主要贡献

本文概述了三个主要贡献：

新颖的公式化： 引入了首个专门针对有向加权时序图的 Temporal Forman–Ricci 曲率公式，整合了端点活跃度、时序近期性和局部交互竞争。
稀疏化框架： 应用此曲率度量来构建紧凑、稀疏的时序图表示，通过保留与任务相关的、按曲率排序的边缘来实现。
全面的评估： 在 12 个数据集（9 个区块链交易网络和 3 个 TGBL 基准测试）以及三个图级预测任务上进行了广泛评估。研究将其与三种最先进的稀疏化方法（MoG, TEDDY, SEM）进行了对比。

实验结果

该框架在三个图级预测任务上进行了评估：

网络活动增长预测： 预测下一个快照中边缘数量是否增加。
网络参与扩张预测： 预测活跃节点数量是否增加。
影响力节点更替预测： 预测高度数节点集合的显著变化。

主要发现：

预测保留： 在 80% 的边缘移除率下（仅保留约 20% 的边缘），TRicci 平均保留了全图 ROC–AUC 的 97.7% ± 2.2%。这显著优于最强的竞争方法（TEDDY），后者保留了 89.4% ± 6.3%。
效率： 该框架在所有数据集上平均减少了 55.94% 的端到端训练和推理时间。
曲率分析： 敏感性分析显示，高曲率边缘（Bin 5）始终保留了最多的预测信息，这支持了帕累托式（Pareto-style）的集中现象，即一小部分边缘承载了大部分信号。
鲁棒性： 该方法对时序衰减参数 $\tau$ 表现出合理的鲁棒性，最优性能通常在 $\tau = 1$ 天左右观察到。

意义与主张

作者声称，TRicci 证明了时序曲率可以作为可扩展时序图学习的有原则的基础。通过在大幅稀疏化的情况下保留预测性的时序-结构信息，该方法解决了稠密动态网络带来的计算瓶颈，且无需针对稀疏化逻辑进行特定任务的重新训练。

论文强调，与其他优化合成表示或依赖静态拓扑的方法不同，TRicci 显式地建模了边缘的时序角色（时间戳和近期性）以及局部交互竞争。这使得构建的稀疏图不仅在计算上是高效的，而且能够保留对于演化网络中下游预测任务至关重要的特定结构动力学。作者将这项工作定位为在交互数据庞大、稠密且具有时间敏感性（如区块链分析和在线社交平台）的领域中实现可扩展学习的一步。