逐鹿最佳论文！程学旗团队获ECML-PKDD最佳学生论文奖

作者 | 陈大鑫

进入2020年后，国内最优秀的人工智能研究团队，都在暗暗地调整自己的目标——顶会论文数量已不是最终目标，逐鹿Best Paper 成为关键。

在SIGDIAL 2020上，清华黄民烈教授所带领的COAI小组拿到了最佳论文奖。

在ICML 2020上，北理工的魏恺轩等人获得了杰出论文奖。

在SIGKDD 2020 上，清华大学唐杰团队发表于2008年的论文被评为时间检验奖。

……

2020年以来，国内人工智能领域的研究团队在各个顶会上基本呈现全面爆发的局面。

而近期，中科院计算所的程学旗团队也加入了“最佳论文奖”获得者的队列之中，在9月14-18日召开的欧洲机器学习和数据挖掘国际会议ECML-PKDD上，拿下了“数据挖掘最佳学生论文奖”。

1

ECML 最佳论文

ECML-PKDD 会议是欧洲最大的机器学习和数据挖掘国际会议，具有18年的历史，也是中国计算机学会CCF认定的著名国际学术会议。

一个比较著名的案例是，2016年曾轰动一时的AlphaGo，其主干蒙特卡洛树搜索的主要技术UCT (Upper Confidence Trees) ，便来自2006年发表在该会议上的一项研究工作，作者为匈牙利科学家 L. Kocsis and Cs. Szepesvári。

在 2020 年度的ECML-PKDD会议中，共收到687篇投稿，最终录取论文130篇，录用率在18%左右。

本届ECML-PKDD 2020共有六篇不同领域的最佳（学生）论文奖，其中中科院计算所网络数据重点实验室刘盛华、沈华伟和程学旗共同指导的博士生冯文杰，以及密西根大学合作者Danai Koutra的研究工作被评为本届唯一的Best Student Data Mining Paper Award（数据挖掘最佳学生论文奖）。

论文链接：https://bitbucket.org/ghentdatascience/ecmlpkdd20-papers/raw/master/RT/sub_406.pdf

2

方法

中科院计算所的网络数据重点实验室是国内数据挖掘领域最强的团队之一。近几年作者团队主要面向大规模图的模式进行探索和挖掘，结合多种实用场景，发明具有高准确率、可扩展性强的解决新方法。

1、在实际场景中，我们应该如何有效地识别在线服务平台中的虚假评论或关系，以及基于用户的交互行为检测欺诈用户呢？

2、如何在时序图或动态图中捕获随时间拓扑变化最大的群组或社区，比如在科研社区中突然出现的热门话题或者学术合作关系等？

3、在大规模图中我们该如何高效地找到其中的最小割集以用于图分割等任务呢？

上述这些看似差别很大的问题都与最密子图的检测任务紧密相关，它是图数据分析中一类重要的基本问题，在许多不同的领域有广泛应用，比如发现生物组织中的功能团，人类行为数据中的迁移模式、社交网络中的社区结构以及金融网络中的欺诈犯罪等。

稠密子图检测用于社区发现：

稠密子图检测用于欺诈检测：

稠密子图检测用于热门话题识别：

现有的研究中针对形式各异的问题进行了不同的形式化表示并发明了不同解决算法，但目前还没有相关工作探究前述不同实际问题的关系；现有的检测算法并没有考虑真实数据的分布特点，在应对现代科学应用中出现的大规模图数据时仍然面临计算代价过高的问题。

表 1 统一的最密子图检测问题GenDS的对应关系总结

针对上面的挑战，在这篇被评为“数据挖掘最佳学生论文奖”的工作中，研究者们分析和对比了一些知名的相关问题之间的区别与联系，包括检测具有稀疏割集的社区结构、可疑的最密子图、时序图中前后对比变化最大的社区（子图）结构等，并提出了一种统一的形式定义广义最密子图检测问题（GenDS）。

它可以囊括多种不同的应用问题，这种统一表示能够从形式上清晰、明确地突出不同问题的差异，同时有助于设计一致性的解决方法；利用图的谱理论优化分析、偏态特征分布性质以及贪心优化策略，提出了一种快速、高效的可扩展算法 SpecGreedy来求解GenDS这一统一性问题。

在第t大奇异值分解（SVD）向量上的SpecGreedy检测示意：

SpecGreedy算法根据SVD分解逐步搜索最优解的过程：

SpecGreedy 检测算法具体过程：

作者通过在来自不同领域的 40 个真实网络数据 (最大网络的边数达到 14.7 亿条) 上进行了大量实验，分析和验证的结果表明：在最密子图检测中，对比与其他基线方法，SpecGreedy算法可将检测速度提高 58.6倍且得到子图密度更大或者具有近似相同的结果；SpecGreedy 的算法复杂度是与图的大小线性可扩展的。

以下是SpecGreedy 算法在真实数据上的检测性能（检测速度、结果质量）以及算法可扩展性的验证结果。

检测速度：

结果质量：

算法可扩展性：

此外，针对算法的有效性，作者也在实际应用中进行了验证——用于有趣群体异常模式的检测，例如，在大规模的随时间变化的学术共同作者网络中发现了突现的合作模式 ，算法检测到形成较大规模的团 (Clique) 结构，分别对应于在“脑网络与疾病”、“神经科学与医药”及“物理学”领域的研究成果。

图注：SpecGreedy算法检测的罕见学术合作模式

3

算法应用实例

癌症基因的交互网络

针对癌症病人的基因交互网络，在癌症不同的发展阶段（期）：如1A、1B、2B、3A等，某些子图网络会发生显著变化（如由连边稠密变得稀疏，或反之）。

传统生物医学诊断是针对不同病变的基因，并结合专家知识和经验、单基因特征分析和人工选择等方法来发现由病变引起的基因交互的变化，用于指导发现和判断疾病的发展阶段；而最密子图检测问题可以检测最显著变化的子图结构，为生物学家提供后续生化实验验证的候选依据。

论文合作群体跟踪

对于人的群体行为，如论文合作团体的变化，作者发现过一个学术社区，研究者们早年间紧密合作，之后随着一些研究者的毕业或转到工业界等，合作团体发生了显著的变化，多年之后留下最核心的学者形成紧密的合作关系网络。

出租车出行网络建模

在出租车出行轨迹数据中，有学者利用分析匿名用户上下车地点、时间这样带时域属性的关系，可以判断出车辆早晚高峰出行密集的起点和终点社区、以及周末和节假日里从车站、机场来往观光名胜的社区，甚至通过建模动态交通网络可以帮助人们发现突发事件：比如临时的交通管制、大型的活动等。

疾病监测

根据用户在搜索引擎中对疾病的搜索、浏览历史记录：记录查询地域、查询疾病的词、查询时间等，可以判断发现流行病，比如每年春天哪些地域易发生流感，某地域在某个季节最容易发生什么流行病、甚至可能提早检测到疾病的突然爆发，如今年的新冠病毒的爆发早期信号。这都与大图中的最密子图检测和建模问题密切相关。

金融交易网络异常监测

金融交易网络的稠密子图结构检测也是一个非常有意思的问题，其中包含五花八门的稠密结构或者特别的模式，对应与各种不同的用途，如骗贷、诈骗、洗钱、虚开发票、不合规资金借贷的用途等等。作者在某类反洗钱案例中发现了这样的结构：稠密流的多部子图。

3

总结

在本文中，作者提出了广义最稠密子图检测GenDS，并结合了相关研究问题的几个著名实例，利用图的谱理论优化分析、偏态特征分布性质以及贪心优化策略，提出了一种快速、高效的可扩展算法 SpecGreedy来求解GenDS这一统一性问题。

本文的主要贡献如下:

理论：本文对不同应用中最密子图的检测提出了统一的公式，并利用谱理论分析了文中提出的优化问题。

算法：本文设计了一个快速算法:SpecGreedy，来解决GenDS问题。

实验：SpecGreedy的效率在40个真实世界的图上得到了验证。SpecGreedy算法的效率与图的大小成线性关系，在实际应用中非常有效，比如在研究合作关系中发现突然爆发。有理论界保证的检测算法设计和流图自适应也是这项工作的可能扩展方向。