逐鹿最佳论文！程学旗团队获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、在大规模图中我们该如何高效地找到其中的最小割集以用于图分割等任务呢？

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

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

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

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

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

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

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

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

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

SpecGreedy 检测算法具体过程：

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

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

检测速度：

结果质量：

算法可扩展性：

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

3

算法应用实例

癌症基因的交互网络

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

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

论文合作群体跟踪

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

出租车出行网络建模

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

疾病监测

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

金融交易网络异常监测

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

3

总结

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

本文的主要贡献如下:

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

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

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

作者介绍

冯文杰：

中国科学院计算技术研究所博士毕业，目前是新加坡国立大学数据科学研究所研究员，研究兴趣包括数据挖掘、大规模图挖掘、机器学习、社交网络分析和异常检测。

个人主页：https://wenchieh.github.io/

刘盛华：

中国科学院计算技术研究所的副研究员，CMU计算机科学系访问学者、清华大学计算机系博士、优博论文、UCLA电子工程系学术界校友代表等。亚太设计自动化会议（ASP-DAC）最佳论文候选提名、ECML-PKDD最佳学生论文奖、微软亚洲学者、国际期刊Complexity的特别专刊共同客座主编。

目前研究兴趣包括大图数据分析、时间序列挖掘、异常检测，图神经网络鲁棒性，以及为海量数据设计智能和可扩展算法。论文出版物发表在IEEE TKDE，ACM TKDD，ECML-PKDD，CIKM，ICDM，SDM，以及AAAI，IJCAI，TCAD，DAC等。

个人主页：https://shenghua-liu.github.io/

沈华伟：

中国科学院计算技术研究所研究员，中科院计算所博士、美国东北大学Barabasi CCNR研究中心访问学者。中国中文信息学会社会媒体处理专委会副主任，中国计算机学会学术工作委员会委员。主要研究领域为社交媒体计算、网络数据挖掘、图神经网络。在PNAS、IEEE TKDE、Phys. Rev. E等期刊和WWW、SIGIR、AAAI、IJCAI、ICLR等国际会议上发表论文100余篇。

获得中国科学院院长特别奖和钱伟长中文信息处理科学技术一等奖，入选中国科学院计算技术研究所“学术百星”计划、中国科学院王宽诚率先人才计划、首批中国科学院青年创新促进会优秀会员、北京智源人工智能研究院青年科学家。担任ACM CIKM 2019的本地主席、WWW 2021社交网络分析和图算法的Track Chair。

个人主页：http://www.bigdatalab.ac.cn/~shenhuawei/

程学旗：

中科院计算所研究员、博士生导师、副所长。主要研究方向网络数据科学、大数据分析技术、信息检索与挖掘、大数据系统以及信息安全应用等。CCF会士、IEEE高级会员，担任中国计算机学会大数据专家委员会秘书长、中国中文信息学会信息检索专委会主任、中国工业与应用数学学会大数据与人工智能专委会副主任。国家杰出青年科学基金、国务院特殊津获得者，中组部万人计划科技领军人才。

在本领域重要国际学术期刊和会议上发表论文200余篇，Google Scholar引用超过16000次，获得授权专利60余件。研制完成的大规模分布式机器学习系统（EasyML）、文本与自然语言处理工具集（MatchZoo）、图数据计算引擎（SQLGraph）等在国际开源社区影响广泛，在查询理解、信息检索和排序学习方面的研究成果五次获得本领域重要学术会议（ACM SIGIR、ACM CIKM、PKDD等）优秀论文奖。研究成果形成的大数据分析系统与关键技术得到了规模化应用，成果获得国家科技进步二等奖三次，省部级奖励六次。

个人主页：http://www.bigdatalab.ac.cn/~cxq/