近日，南方科技大学计算机系唐博老师带领的数据库课题组在数据挖掘和知识发现领域取得一系列科研进展。该研究团队三项成果被数据挖掘和知识发现领域的顶会之首KDD 2023长文（2篇Research Track，1篇Applied Data Science Track）接收。研究内容涉及社交网络中的容量受限影响力最大化、跨越中心性的高效近似算法和高效易用的图神经网络模型推理框架等。

成果一

（Research Track）

Capacity Constrained Influence Maximization in Social Networks

影响力最大化是病毒式营销、网络监控等领域的重要问题，其旨在选择在网络中具备影响力的少数传播用户，以便最大程度地传播目标信息（例如推广活动）。然而，以往的研究忽视了用户参与活动的能力限制。以在线游戏社交网络为例，玩家的能力限制表示每个玩家只能与有限数量的朋友互动。对该场景的观察还指出，推广的最初接受者往往是选定用户的朋友而非用户本身，并且现有解决方案在计算量和解质量方面表现不佳。基于这些发现，我们提出了一个新的问题，即容量受限的影响力最大化（Capacity Constrained Influence Maximization），其旨在为每个初始接受者选择有限数量的具有影响力的朋友，从而将推广传递给更多用户。为了解决该问题，我们提出了MG-Greedy和RR-Greedy两种算法，并且进一步设计了具有良好近似比和近线性复杂度的可扩展实现RR-OPIM+。大量实验表明，RR-OPIM+ 在解质量和运行时间方面显著优于其他8种先进的解决方案。此外，我们还将RR-OPIM+部署到网络游戏场景中，显著地改善了基线算法的性能。

图1.实验组 (Treatment)和对照组 (Control)分别对应RR-OPIM+和基线算法

该工作的第一、第二作者分别是2019级南方科技大学-新加坡国立大学联培博士张诗奇和2020级南方科技大学本科生黄弋骞，唐博老师为通讯作者。该工作由南科大数据库课题组与腾讯公司孙嘉辰博士和林文清博士，新加坡国立大学萧小奎教授合作完成。

张诗奇 (第一作者)

黄弋骞 （第二作者）

成果二

（Research Track）

Efficient Approximation Algorithms for Spanning Centrality

针对给定的图G，边e的跨度中心性（SC）衡量了e对于使G连接的重要性。在实践中，SC在计算生物学、电气网络和组合优化等领域得到了广泛应用。然而，在大型图上计算所有边缘的SC（AESC）是一项极具挑战性的任务。现有的技术无法处理这样的图，因为它们要么需要昂贵的矩阵操作，要么需要采样大量的长随机游走。为了解决这些问题，本文提出了TGT和其增强版TGT+，这是两种用于AESC计算的算法，具有严格的理论近似保证。特别是，TGT通过进行精心设计的截断长度的确定性图遍历来解决先前解决方案的缺陷。TGT+在TGT的基础上进一步提高了实证效率和渐近性能，同时保持结果的质量，基于TGT与随机游走和几个附加的启发式优化方法的结合。我们使用各种真实数据集对TGT+与最近的竞争对手进行了实验评估，如下图所示，在有亿级边的数据集下，TGT+仍可在速度上快于最优的现有技术。

图2. TGT+与最优现有技术运行时间的对比

该工作的第一作者是南方科技大学与新加坡国立大学联培博士张诗奇，唐博老师为通讯作者。该工作由南科大数据库课题组与香港浸会大学杨任驰教授，香港科技大学唐靖教授和新加坡国立大学萧小奎教授合作完成。

张诗奇 (第一作者)

成果三

（Applied Data Science Track）

DGI: An Easy and Efficient Framework for GNN Model Evaluation

现存的工作都致力于优化图神经网络（GNN）的训练，但高效的模型推理方案（即根据给定的模型计算图节点的嵌入）仍然有待解决。使用广泛采用的Node-wise方法，由于邻居爆炸问题，模型推理仍可能占端到端训练过程中90％以上的时间。Layer-wise方法通过在GNN模型中逐层进行计算从而避免邻居爆炸问题。然而，Layer-wise模型推理需要相当大的实现工作，因为用户需要手动将GNN模型分解为层，并且对于具有不同结构的GNN模型需要不同的实现。

 图3. DGI的工作流程

本文推出了DGI，一个易于使用且高效的GNN模型评估框架，它可以自动将GNN模型的训练代码翻译成Layer-wise推理的代码，以最小化用户的工作量。DGI适用于不同的GNN模型和推理请求（例如，计算所有或部分节点的嵌入），并支持在无法适应CPU内存的大型图上进行外部执行。在底层，DGI跟踪GNN模型的计算图，根据定制规则将计算图分成适合逐层推理的层，并通过Node Reorder和Dynamic Batch Size Control来高效地执行每个层的计算。实验结果表明，DGI在效率上与手写的layer-wise 推理实现相当，并在不同的数据集和硬件设置下一致优于Node-wise推理，速度最大可以提升三个数量级。

该工作由南科大数据库课题组与AWS Shanghai AI Lab，香港中文大学James Cheng团队合作完成。第一作者尹沛骐是南科大数据库课题组2018级毕业生，该工作是其本科毕业设计内容，在晏潇老师（通讯作者）和唐博老师指导下完成。

尹沛骐 (第一作者)

南方科技大学计算机科学与工程系

图文丨数据库课题组