Community-based Dynamic Graph Learning for Popularity Prediction

阅读笔记作者：叶文惠

备注：

1、论文阅读笔记将同步更新到四川大学网络空间安全协会学术园地版块（类似：https://www.scucyber.cn/fawa-fast-adversarial-watermark-attack-on-optical-character-recognition-ocr-systems/）；

2、论文阅读笔记需要同时通过Synology Drive上传到资源共享平台和协会学术园地版块收稿邮箱1092477425@qq.com并抄送到whzh.nc@scu.edu.cn，邮件中注明该文档在网站发布时的作者为本人真实姓名还是昵称（昵称命名不得违规）。

1 原文作者

Shuo Ji∗(SKLSDE Lab, Beihang University)

Xiaodong Lu∗(SKLSDE Lab, Beihang University)

Mingzhe Liu(SKLSDE Lab, Beihang University)

Leilei Sun†( SKLSDE Lab, Beihang University)

Chuanren Liu(The University of Tennessee)

Bowen Du(SKLSDE Lab, Beihang University)

Hui Xiong‡( The Hong Kong Univ. of Sci. and Tech.)

2 论文来源

Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD 2023)(CCF A)

3 论文地址

https://dl.acm.org/doi/10.1145/3580305.3599281

4 论文简介

4.1研究背景

作者指出，网络上的内容或产品的流行度预测是一个重要的问题，可以帮助在线平台识别受欢迎的内容或产品。然而，这个问题存在多方面的挑战，如用户偏好和产品特征的多样性、社会影响的复杂性、网络上的新内容或产品的不断出现以及用户和产品的持续演化。作者认为，现有的方法主要基于特征提取、序列模型或图神经网络，但不能充分利用网络中的高阶结构信息和个体或群体因素的动态演化信息，因此提出了一个基于社区的动态图学习方法来解决这个问题。

4.2研究内容

作者明确提出了他们要解决的问题，即给定一个包含用户和产品之间的交互信息的动态图，如何预测一个目标产品在未来一段时间内的流行度。即如何在一个连续时间的信息图中，利用基于社区的动态图表示学习方法来预测目标项目或在线内容的流行度。作者解释了这个问题的难点和价值，并给出了他们的方法的主要思想和贡献。

4.3研究结论

提出了一种基于社区的动态图表示学习方法，用于预测在线内容或产品的未来受欢迎程度。

该方法维持每个节点和社区的动态表示，并根据新观察到的用户–项目交互来更新表示。

该方法设计了一个社区检测模块，能够捕捉不断变化的社区结构，并识别最具影响力的节点。

该方法利用社区级别的信息传播来平衡局部和全局的信息传播。

该方法在三个真实数据集上进行了实验，证明了其在流行度预测方面的优越性。该方法还能够观察到语义社区的演化过程，以及用户偏好的变化轨迹。

5 解决问题

给定一个包含用户和产品之间的交互信息的动态图，如何预测一个目标产品在未来一段时间内的流行度。即如何在一个连续时间的信息图中，利用基于社区的动态图表示学习方法来预测目标项目或在线内容的流行度。

网络上的内容或产品的流行度预测是一个重要的问题，可以帮助在线平台识别受欢迎的内容或产品。然而，这个问题存在多方面的挑战，如用户偏好和产品特征的多样性、社会影响的复杂性、网络上的新内容或产品的不断出现以及用户和产品的持续演化。现有的方法主要基于特征提取、序列模型或图神经网络，但不能充分利用网络中的高阶结构信息和个体或群体因素的动态演化信息。

作者认为，这个解决这个问题需要考虑以下三个方面：

1) 如何维护用户和项目的动态表示，以捕捉他们的演化趋势和偏好变化；

2) 如何发现动态的社区结构，并学习社区级别的表示，以反映群体偏好和层次信息；

3) 如何基于学习到的表示来预测目标项目或在线内容的流行度。

文中三个模块企图解决以下三个问题：

1)静态图学习方法通常只捕捉结构特征，忽略了演变趋势和动态的偏好；

2)将社区结构整合入深度学习存在高计算成本、社区和关联节点间关系演变复杂的问题，并且还没有方法实现在连续时间的动态图上检测社区；

3)先前研究多基于节点表征预测，想要兼顾高层次结构信息，整合社区和节点表征进行预测。

6 本文贡献

1) 提出了一个动态图神经网络，用于流行度预测问题。作者的方法考虑了用户和项目之间的交互作为一个时间信息图，并学习动态节点表示，以探索用户偏好和项目特征的连续演化；

2) 提出了一个动态的基于社区的信息扩散机制，用于捕获群体偏好，该机制动态地将具有相似潜在偏好的节点分配到一个社区，并学习相应的社区级别的表示。据作者所知，这是第一个用于连续时间动态图的深度社区检测方法；

3) 在真实世界的数据集上进行了实验，证明了所提方法的有效性。作者的方法不仅能够模拟用户偏好的变化，还能够捕捉社区随时间的演化、语义社区演变、项目演变趋势。。

7 论文方法

本文的方法主要分为四个模块，动态节点表征模块、动态社区结构模块、基于社区的消息传播模块以及预测模块。

动态节点表征模块

为了解决先前工作使用静态图学习方法时忽略趋势的演变和偏好的动态性问题。

首先，为每个节点维持一个记忆 ，表示时间t之前的节点历史新信息。当新交互 出现时，使用对交互的编码消息 , 更新相关节点 的记忆。以 举例说明计算方式：

表示 之前的节点 的记忆， 是训练参数，||表示拼接 表示时序特征，基于时间戳 产生，时间戳蕴含丰富的时序特征，可以反应节点的演变模式，节点在不同时间出现的交互会反应出不同的行为特征，可以通过以下方法计算：

表示此次交互出现距离上一次出现的时间间隔，即

通过GRU方法混合节点信息，更新节点记忆。

动态社区结构

本模块为了解决在深度学习中整合社区结构会导致高计算成本和关系评估复杂的问题。而且，深度学习还没有被运用到具有动态模式的社区检测领域。本文想要实现一种在连续时间上检测社区的方法，可以同时整合动态的群组信息和层次信息。本文的方法可以防止社区漂移和大量数据的矩阵计算。

定义社区：区别于先前研究将共享密集链接的星状节点结构定义为社区，本文构建一个用户项目二元图网络，将具有相同组偏好的用户归为一个社区，用一个社区中心点来表示社区，社区信息表示为， 表示以 为中心的社区。具有相似兴趣的用户和具有相似主题的项目会被归为一个社区。

对每个新到的交互 ，将和 分别当作社区中心，将它们的邻居当作成员进行计算。以 为例， 表示 的邻居组成的社区成员。

为了表示每个成员对社区的归属感，通过注意力机制设计了成员强度变量 。

首先，通过潜在社区成员的记忆，为潜在社区 建立一个社区成员的查询向量表征。 表示中心节点的记忆， 表示成员节点的记忆：

然后，计算 ，和 是可训练参数

基于各个邻居的成员强度，计算社区的表征

基于计算出的可能的社区表征，参考能够适应性捕捉局部极值信息并从整个图中采样聚类表征的ASAP中的LEConv方法，将其运用到动态图中，进一步计算社区适应分数 ，表示在 时刻社区 的分数：

是可训练参数， 表示邻居节点的适应度分数，计算如下：

是可训练参数，基于这个分数，用 、 和先前排前k的社区进行比较排序，来保留新的k个社区。 表示之前的前k个社区。这个操作可以节省后续的计算成本。

接着进行社区成员的选择，想要构成一个完整的社区，需要找到完整的社区子图，直接链接的节点是一部分，本文还想要考虑l-hop的节点。以2-hop为例，基于最新更新完的图，第一层选择直接连接的节点，第二层选择在1-hop中成员强度较大的节点，然后选择和这些节点连接的节点中成员强度较大的节点。（我觉得这里的larger是一个非常模糊的概念，例子中 的0.3和的0.25都是，但0.2就不是了， 和的0.4是，理由是比 的0.2大，这种解释和没解释有什么区别？）文中没有说明，具体实现的方法采用的l等于多少。

基于社区的消息传播

区别于先前工作从节点表征直接预测，本文从中层观（介于宏观和微观之间）来学习，并抽象出了基于社区的消息传播模式。通过动态社区检测捕捉到的结构信息和群组偏好通过消息传播将交互产生的影响传播到整个社区。因为相同社区的用户具有相似偏好，更趋向于和相似的项目产生交互。对社区成员产生的消息如下：

然后通过如下公式，将消息融合进邻居节点的记忆并更新。因此达到基于社区信息的图学习。

最后，基于得到的社区表征和节点记忆，可以进行项目流行度的增量预测。通过下面公式，预测在接下来 时间内 的流行度。 是可训练参数。

这个流行度预测问题可以被归类到回归问题，采用均方对数函数（MSLE）作为损失函数，公式如下：

8 实验结果

数据集

名称	描述	*Item、interaction*
Twitter	2012. 4.25-5.20的发文和转推	hashtags 带有hashtags的发文或转推
Aminer	2003-2010发表在计算机科学上的论文及相关元数据	研究领域在研究领域发文
APS	1990-2010发表在美国物理学会的论文及相关元数据	从论文标题提取的关键词带有相关关键词的发文

对比的基准模型

1）基于特征的方法，利用手工设计的特征和传统的机器学习方法（DT和SVR）；

2）基于RNN的方法，采用顺序模型来捕获每个项目自身序列内的时间信息（LSTM和DFTC）；

3）基于GNN的方法，采用图形神经网络来建模节点之间的复杂关系（其余方法）。

实验设置

*数据集*	*一个单位持续时间*
Twitter	3天
Aminer	6个月
APS	1年

*时间分区*	作用
倒数第一	测试
倒数第二	验证
剩下全部	训练

*评估指标*	描述
MSLE	均方对数误差
MALE	平均绝对对数误差
MAPE	平均绝对百分比误差
PCC	皮尔逊相关系数

动态特征150维，时序特征100维，社区数800，最大成员数200，使用Adam优化器，初始学习速率0.00005，早期暂停策略的耐心值8。

想要验证的问题

•问题1：与经典和最先进的方法相比，CDGP的表现如何？

•问题2：CDGP的不同组成部分如何促进其绩效？

•问题3：关键超参数（即社区数量和社区的最大成员数量）的选择如何影响动态社区结构的学习？

•问题4：CDGP如何从充满活力的社区代表中获益？

•问题5：从用户和项目表示的演变中可以反映出什么？

对比试验

首先，可以观察到依赖于手工设计的特征的基于特征的方法（即，DT和SVR）实现了不令人满意的性能。这表明有一些复杂的模式控制着商品流行度的增长，这些模式不容易被手工设计的特征所捕捉。

第二，在所有基于RNN和基于GNN的方法中，LightGCN的性能最差，这可能是因为它将项目的交互序列组合到一个静态图中，忽略了交互的实际顺序。这显示了捕获节点之间的时间依赖关系的重要性。此外，动态图学习方法（TGN和CDGP）在AMiner和APS上取得了所有方法中最好的性能，这进一步证明了捕捉项目和用户演变趋势的优势。在Twitter上，TGN的表现相对较差，这可能是因为Twitter的时间跨度较短（1个月左右），项目和用户的演变不明显。

第三，CDGP始终在所有数据集上产生最佳性能，验证了所提出方法的有效性。此外，CDGP与TGN相比实现了显著的改进，这与社区结构可以反映层次信息以及社区级消息传递可以促进节点级表示的学习的直觉是一致的。

总的来说，CDGP明显优于现有的方法，因为：1）维护动态节点表示以捕捉节点之间的共享进化模式。2）学习动态社区结构以考虑时态信息图中的高阶信息。

消融实验

•w/o CM消除了动态社区结构。

•w/o GCN使用GCN计算社区适合度分数。

•w/o TIME消除了时间特征 。

可以观察到：

1）CDGP优于w/o CM，这表明动态群落结构可以利用高阶信息进行更好的预测。

2）w/o GCN的性能下降表明适应度函数比GCN更能捕捉群落内的结构信息。

3）w/o时间性能不如CDGP，表明时间特征可以从时间戳中捕捉有价值的进化模式

超参数的影响

以四个数量级改变参数，得到了如下结果。

社区数量的影响。社区数量是一个主要的超参数，它在更新过程中限制了当选社区的数量。对于AMiner，将社区数量从5、50、500到5000不等，对于Twitter和APS数据集，将社区数量从8、80、800到8000不等。

从结果可以得出结论：1）随着社区数量的增加，500或800之前的绩效有明显的下降趋势。与少数社区（5或8个）相比，绩效显著提高，验证了社区结构的有效性。2）大量的社区导致绩效的提高，这可能是因为社区的规模受到社区数量的限制。

最大成员数的影响。当更新动态社区表示时，太多的社区成员可能会导致高计算成本。因此，最大成员数，即分配给社区的最大成员数，应设置为适当的值，这有助于只观察最近与社区中心互动过且成员实力较高的成员。最大会员人数从2、20、200到2000不等。结果显示，最大成员数越大，性能越好。然而，与200年至2000年间不断增加的计算成本相比，性能并没有显著提高，尤其是在Twitter和APS数据集上。

动态表示分析

了解CDGP如何从动态社区结构中受益。首先将CDGP与经典的聚类和社区检测方法进行比较。接下来，通过可视化探索动态社区结构，以更好地理解社区的演变。

不同社区检测方法的比较。为了评估CDGP在发现动态社区结构和学习社区表示方面的有效性，将其与三种经典算法进行了比较。其中，k-means的中心是成员的平均值，而k-mediods选择网络中的节点作为中心，然后将节点分配给中心。DBSCAN是一种基于密度的聚类算法。考虑到这些聚类算法是在静态网络中开发的，将它们与本文的动态框架集成在一起。具体来说，本文将时间信息图视为以规则间隔的时间戳采样的几个图快照，当新快照出现时，本文重新检测该快照上的社区，其中每个快照可以被视为静态网络。

如表所示，CDGP实现了最佳性能。导致这一结果的原因有两个：

1）与其他从快照中检测社区的方法相比，本文方法在交互事件到来时不断更新社区结构，而不会丢失时间信息。

2）本文依靠社区得分函数检测社区结构，并使用注意机制计算成员强度。这些基于深度学习方法的组件可以比经典的聚类和社区检测方法更好地学习非线性关系。

动态社区代表投影。图形动态会影响社区结构和节点表示。为了进一步观察时间和空间维度的变化，利用t-NSE[33]在Twitter数据集上投影三个社区中成员的动态表示，其中每个社区可以被视为一种热门话题，成员基于语义偏好进行聚合。

图显示了一系列快照，其中本文跟踪了语义社区的演变，包括出生、死亡和成长。在早期，人们没有表现出明显的偏好，节点在第0天分散分布。三天后，社区1（红色散射）和3（蓝色散射）的主题变得流行，许多人被吸引来参加这些主题。如第三天所示，对这两个主题感兴趣的人聚集在中心周围。然后在第6天，这些社区变得更大，这表明越来越多的注意力被放在主题上。三天后，社区2（红色散射）的规模缩小，这可能归因于主题2的受欢迎程度逐渐降低，参与者被吸引到其他社区。而且话题2的受欢迎程度不足以让它成为社区中心，所以社区2被替代。之后，社区3以与社区2相同的方式消失。另一个有趣的观察是，社区1在第21天再次聚集。可能是因为一条新发布的关于这个话题的推文引起了人们的兴趣。

总的来说，人们的偏好在2012-03-27和2012-04-17之间不断演变，本文的方法可以捕捉到这种演变。相应地，社区动态地形成、分裂、成长和消失，暗示了热门话题的动态和人们语义偏好的演变。

项目和用户跟踪可视化

为了探索动态表征的变化能反映什么，使用t-SNE将AMiner上不同时间的用户和项目的动态表征投影到二维空间中，以查看它们的演变轨迹。

项目跟踪可视化。在这一部分中，首先选择四个项目，并在每年年底收集它们的表示，然后将这些表示投影到二维空间的点上。从图6中可以观察到，具有不同进化模式的项目在潜在空间中具有不同的轨迹。具体来说，这四个项目可以分为两组：受欢迎程度逐年上升的热门项目（A和B）和受欢迎程度逐渐下降的冷门项目（C和D）。属于同一组的项目具有相似的轨迹，而不同组的轨迹差异很大。这表明动态表示能很好地捕捉项目的演变模式，从而有助于预测项目的流行程度

用户轨迹可视化。一旦用户与一个项目交互，就收集他的表现，然后将这些表现投射到二维空间。如图所示，CDGP有潜力揭示作者的研究主题路径（用户偏好）：表示随着用户研究领域的转移而逐渐改变。并且位于接近位置的点具有相似的研究主题。并且位于接近位置的点具有相似的研究主题。这表明动态表示可以在某种程度上捕获用户偏好。

9 本文不足

本文在解释实验结果时，部分分析略显牵强，难以理解，比如超参部分的实验。

文章中在动态表征部分的实验描述不是很明确，在我的理解下，它使用社区检测算法和聚类算法时对图进行采样检测，但是本文方法采用连续检测，借此提出了连续检测的优越性，有些不妥。而且，这个部分的实验结果比对比实验中的其它方法都要好，是不是可以得出社区结构的优越性。

CDGP假设每个社区都有一个中心节点，而实际上社区的结构可能更加复杂和多样化。

CDGP使用固定的社区数量和社区成员数量，而实际上这些参数可能随着时间和数据的变化而变化。

CDGP没有考虑用户和项目的额外特征，例如文本、图像、标签等，这些特征可能对流行度预测有帮助。

10 代码和数据集地址

论文代码：

https://github.com/AhaSokach/CDGP（还没发布）

数据集：

Twitter：https://pan.baidu.com/s/1tWcEefxoRHj002F0s9BCTQ，密码1msd

Aminer：https://www.aminer.cn/citation

APS：https://journals.aps.org/datasets

110