论文解读 | KDD2024 演化图上的森林矩阵快速计算

文章预览

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入！ 点击  阅读原文  观看作者直播讲解回放 ！ 作者简介 孙浩鑫 ，复旦大学博士生，主要研究方向为大规模图上快速算法设计。 概述 森林矩阵在网络科学、观点动力学和机器学习相关应用中扮演着至关重要的角色，深刻刻画了网络的结构信息与内在联系。在本文中，我们研究了在演化中的图（与静态图相比，更准确地代表了现实世界网络的动态特性）中查询森林矩阵元素的问题。为了应对演化图所带来的独特挑战，我们首先为静态图中森林矩阵元素查询提出了两种近似算法，SFQ和SFQPlus。SFQ采用了森林矩阵的概率解释，而SFQPlus则结合了一种新颖的方差减少技术，我们理论证明了SFQPlus拥有更小的方差，因而可以提供更高的精确度。基于这两种算法，我们进一步设计了两种动态算法，这些算法的 ………………………………