KDD 2019大奖新鲜出炉！华人博士勇夺最佳论文，“中国队”横扫KDD CUP

新智元报道

来源：KDD 2019

编辑：张佳，大明，小芹

【新智元导读】KDD 2019大奖出炉！来自康奈尔大学的华人博士Dong Kun拿下Research Track最佳论文，KDD CUP奖项也几乎被国人包揽。此外，本届大会组委会中也出现了不少中国学者的名字。来看详细报道。

又是一年KDD。

第25届ACM SIGKDD（数据挖掘及知识发现）于2019年8月4日-9日在美国阿拉斯加安克雷奇市举办。

在去年的KDD，中国军团大放异彩。中科大、苏州大学与微软合作的《小冰乐队》获得了Research Track最佳学生论文。清华大学的唐杰和UIC的刘兵教授分别获得杰出贡献奖和创新奖。

那么，今年的KDD情况又如何呢？

录取率仅15%，“结果可重现”才有机会参评最佳论文

本届KDD共有来自51个国家和地区的3150人参会，其中，有超过832位女性注册和443位学生注册，有162名学生志愿者。今年赞助费超过108万美元，学生奖金约15万美元，支持了170名学生。

KDD 2019规模

作为数据挖掘领域最顶级的学术会议，KDD 大会以论文接收严格闻名，每年的接收率不超过20%，因此颇受行业关注。今年也是KDD大会采用双盲评审的第一年。

与往年一样，KDD大会分为 Research track和 Applied track。

据了解，今年KDD Research track 共收到了 1179 篇投稿，其中约 111 篇被接收为 oral 论文，63 篇被接收为 poster 论文，接收率约 15%。

Applied track收到大约 700 篇论文，其中大约 45 篇被接收为 oral 论文，约 100 篇被接收为 poster 论文，接收率约 20.7%。

相比之下，2018年KDD大会共评审了 1440 篇论文，其中，Research Track 评审了 983 篇论文，接收 181 篇，接收率为 18.4%；Applied Track 评审了 497 篇论文，接收 112 篇，接收率为 22.5%。

KDD 大会涉及的议题大多跨学科且应用广泛，吸引了来自统计、机器学习、数据库、万维网、生物信息学、多媒体、自然语言处理、人机交互、社会网络计算、高性能计算以及大数据挖掘等众多领域的专家和学者。

KDD官网的投稿要求

值得关注的是，今年KDD投稿通知中将“可重现性”作为重点，鼓励作者们在论文中公开研究代码和数据，汇报他们的方法在公开数据集上的实验结果，并尽可能完整描述论文中使用的算法和资源，以保证可重现性。

为了鼓励呈现结果的可重现性，KDD 2019 规定只有在文章最后额外提交两页附录体现“可重现性”内容（包括实验方法、经验评估和结果）的论文，才有资格参评“最佳论文”奖项。

最佳论文：华人一作拿下Research Track 最佳论文

那么，话不多说，首先来看最佳论文。

Research Track 最佳论文

这篇最佳论文题为“Network Density of States”，作者团队来自康奈尔大学，第一作者Dong Kun是康奈尔大学应用数学专业博士生。其他作者还包括Austin R. Benson，通信作者为康奈尔大学应用数学系教授David Bindel。

光谱分析可以将图结构与相关矩阵的特征值和特征向量连接起来。许多光谱图理论直接来自光谱几何，通过相关微分算子的光谱来研究可微分流形。但是从光谱几何到光谱图的转换主要集中在仅涉及少数极端特征值及其相关特征值的结果上。与几何学不同，通过特征值的整体分布（即谱密度）来实现对图的研究，主要局限于简单的随机图模型。现实世界的实际图谱内部在很大程度上仍处于未探索的状态，难以计算和解释。

本文深入研究了真实世界图谱的谱密度。我们借用了凝聚态物理中开发的工具，并添加了新的适应性来处理常见图形图案的光谱特征，所得到的方法是高效的。除了提供视觉上引人注目的图形指纹之外，我们还展示了谱密度估计对许多常见中心度量的计算的推动，并使用谱密度来估计有关图形结构的有意义的信息，仅从极值本征对信息是无法推断出这些信息的。

本文利用研究凝聚态物理中状态密度的方法来研究网络中的谱密度。本文研究了基于这些方法得到的全局态密度，以及由特定特征向量分量加权的局部密度。我们采用这些方法，利用大多数物理系统中不存在的图特定结构，分析谱密度对扰动的稳定性，以及我们的算法的收敛性。

实验表明，这些方法非常有效。我们使用这些方法来计算这些密度，创建引人注目的图形指纹。我们还展示了状态密度如何揭示仅从极值特征值和特征向量中不明显的图特性，并将其用作快速计算图连通性和节点中心性的标准度量的工具。这为使用完整光谱信息作为大规模网络分析工具打开了大门。

本文回顾了内核多项式方法（KPM），它涉及DOS / LDOS的多项式扩展，以及通过Lanczos迭代（GQL）的高斯求积法。然后我们为LDOS引入了一种新的直接嵌套解剖方法，以及新的图形特定修改，以求改善KPM和GQL方法的收敛性。

图1：CAIDA自治系统图的标准化邻接矩阵的频谱直方图，该系统是一个包括22965个节点和47193个边的互联网拓扑。蓝色代表真实光谱，红色点是近似高度。图1b是图1a在特征值0附近的高度放大图（高度取0到500）

图2：图形数据中导致光谱密度出现局部峰值的常见图案（诱导子图）。每个图案都会生成一个特定的特征值，具有局部支持的特征向量。尽管我们可以对邻接、拉普拉斯算子或归一化拉普拉斯算子执行相同的分析（只有特征值不同），但这里统一使用归一化邻接矩阵来表示。仅在标记的节点上支持特征向量。

图3：在扫描光谱滤除图案后，高能物理理论（HepTh）协作网络的归一化邻接矩阵的谱直方图近似精度的提升。该图具有8638个节点和24816个边。蓝色条是真实光谱，红色点是近似高度。（图3a-3e）使用100个矩和20个探针向量。图（3f）分别表示不使用滤波器，在λ= 0处使用滤波器、全部使用滤波器时，光谱直方图的相对L1误差。

表1：从SNAP存储库中计算每个Chebyshev时刻（共有20个探测器）的平均时间

论文链接：

https://arxiv.org/pdf/1905.09758.pdf

Research Track第二名论文

题目：Optimizing Impression Counts for Outdoor Advertising

作者：

Yipeng Zhang 皇家墨尔本理工大学计算机科学博士生

Yuchen Li 新加坡管理大学信息系统助理教授

Zhifeng Bao 皇家墨尔本理工大学高级讲师

Songsong Mo 武汉大学

Ping Zhang 华为公司

本文提出并研究了对室外广告影响力的优化问题，尤其是关于广告牌给用户留下好印象的次数的计算问题。对于给定的广告牌数据集U，每个广告牌都有自己的地理位置和不同的成本以及一个映射数据集T和预算B，目的是找到在预算B条件下达到最大影响力的广告牌。和广告消费者行为研究一样，我们利用逻辑函数来计算展示在不同广告牌上的广告给消费者留下好印象的次数，以此作为衡量广告影响力的量度。

不过，这种方法产生了两个问题。首先，这个问题属于NP困难问题（非确定性多项式困难问题），目标是对于任何多项式时间ε > 0，在复杂度O(|T |1−ε)下进行估计。第二，对影响力的量度属于非子模块，采用直接贪心算法是不可行的。

本文提出了基于切线的算法计算子模块函数，来估计影响力的上界。此后，我们使用一个带θ终止条件的分支边界框架，不过，这个框架在|μ|很大时，运行非常耗时，我们又利用渐进式剪枝上界估计方法对其进行了进一步优化，大大降低了运行时间。我们的实验中使用的是现实世界中的广告牌和映射数据集，结果表明，我们使用的方法在效率上比基线方法高出了95%。而且，经过优化的方法比原始框架的运行速度快了两个数量级。

论文链接：

https://dl.acm.org/citation.cfm?doid=3292500.3330829

Applied Track最佳论文

题目：Actions Speak Louder than Goals: Valuing Player Actions in Soccer

作者：

Tom Decroos，比利时鲁汶大学

Lotte Bransen，SciSports公司

Jan Van Haaren，SciSports公司

Jesse Davis，比利时鲁汶大学

评估足球运动员在比赛期间的个人表现的对比赛的影响，这是球员招募中需要考察的关键指标。遗憾的是，大多数传统指标在解决此任务时都不尽如人意，因为它们要么集中于单独的镜头画面和目标行为，要么不考虑球员做出动作时的背景。本文介绍了（1）用于描述球场上各个球员动作的新语言，以及（2）基于球员表现对比赛结果的影响来评估任何类型的球员动作的新框架，同时考虑了动作发生时的背景。通过足球运动员表现行动的价值进行汇总，可以对球员对球队的总体进攻和防守的贡献进行量化。

本文中提出的方法考虑了被传统球员评估指标所忽略的相关背景信息，并在2016/2017和2017/2018赛季的欧洲顶级比赛中展示了与球员搜寻和比赛风格特征相关的大量实例。

论文链接：

https://arxiv.org/pdf/1802.07127.pdf

Applied Track第二名论文

题目：Developing Measures of Cognitive Impairment in the Real World from Consumer-Grade Multimodal Sensor Streams

作者：

Richard Chen, Filip Jankovic, Luca Foschini, Lampros Kourtis, Alessio Signorini, Nikki Marinsek, Melissa Pugh, Jie Shen, Roy Yaari, Vera Maljkovic, Marc Sunga, Han Hee Song, Hyun Joon Jung, Belle Tseng, Andrew Trister

当前，可穿戴消费设备和移动计算平台（智能手机，智能手表，平板电脑）已经无处不在，其性能和技术水平也越来越高，支持多种传感器模式，这使得我们能够持续监控患者的日常活动。我们可以针对认知障碍的生理和行为特征挖掘这类丰富的纵向信息，并且以及时高效的方式提供检测MCI的新途径。

在本研究中，我们提供了一个平台，使用几种消费级智能设备远程监测与认知障碍相关的症状。我们在Lilly探索性数字评估研究中展示了该平台如何收集了总共16TB的数据，这项为期12周的可行性研究监测了31名患有认知障碍的人和82名没有认知障碍、可以正常生活的人。

我们描述了使用谨慎的数据统一、时间对齐和插补技术来处理实际环境中固有的数据缺失，并最终表明，这些不同的数据能够在症状区分与健康控制上发挥的重要作用。

论文链接：

http://alessiosignorini.com/articles/developing-measures-cognitive-impairment-multimodal-sensor-streams/paper.pdf

经典论文奖：CELF算法

KDD 2019的经典论文奖(Test of Time Award)颁发给 KDD 2007的最佳学生论文：Cost-effective Outbreak Detection in Networks，作者来自CMU和Nielsen BuzzMetrics。

在这篇论文中，来自CMU的Jure Leskovec等人提出名为CELF的优化算法(Cost_Effective Lazy Forward selection)，用于改进贪心算法的效率，可以比原始贪心算法快 700倍。现在，CELF已成为一种经典的社会网络影响最大化发现算法。

CELF算法

该方法是基于影响力具有子模函数特征提出的，即所有节点的影响力随着种子节点集合中节点数目增加在减弱，具有单调递减性。

该方法分为两个步骤：第一个步骤用于选择第一个种子节点，在全部节点中搜索种子节点，选择影响力最大节点加入到种子节点集合中；第二个步骤用于选择余下种子节点，利用影响力具有单调递减性这一性质在部分影响力较大节点中搜索种子节点。由于在第二个步骤中此方法搜索种子节点空间的减少，该方法的效率有了较大提高。

CEFL算法的性能

该论文的第一作者Jure Leskovec现在是斯坦福大学计算机科学系副教授，研究重点是大型社会和信息网络的挖掘和建模。

Jure Leskovec

Leskovec在学生时代就是牛人，在KDD、WWW、INFOCOM等学术会议发表多篇论文，获得2 篇 KDD 最佳论文(2007最佳学生论文和2005最佳研究论文)，博士毕业即加入斯坦福任教。

其他奖项

人物奖

今年的KDD同样表彰了两位有杰出贡献的人，他们分别是：

创新奖（Innovation Award）得主：Charu Aggarwal

本届KDD创新奖(Innovation Award)获得者是IBM Watson研究院的Charu Aggarwal，他是IEEE和ACM fellow，知识发现和数据挖掘领域的著名学者。他于1993年从印度理工学院坎普尔分校获得学士学位，1996年在麻省理工学院获得博士学位。他在数据挖掘领域做了许多有影响力的工作，对数据流、隐私、不确定性数据和社交网络分析有着特殊的兴趣。发表著作19部(写作8部，编辑11部)，论文350余篇，申请或被授予专利80余项。他的h指数是96。

服务奖（Service Award）得主：Balaji Krishnapuram

本届KDD服务奖(Service Award)获得者是IBM Watson Health总监、杰出工程师Balaji Krishnapuram，奖励他是对数据挖掘的杰出贡献和对社区的杰出服务。

初创公司奖（ Startup Research Awards）

Qiang Liu, RealAI

Chao Liu, TianYanCha

Zhen Wei, Arkive

Kartik Yellepeddi, Deepair

Dissertation Awards

获奖者：Tim Althoff, Stanford, advised by Jure Leskovec

第二名：Chao Zhang, University of Illinois at Urbana-Champaign, advised by Jiawei Han

荣誉奖：

Michael Yeh, University of California - Riverside, advised by Eamonn Keogh

Ioannis (John) Paparrizos, Columbia University, advised by Luis Gravano

KDD CUP 2019

KDD CUP素有“大数据世界杯”之美誉，吸引全球各地的工程师、开发者和学生参与。

今年的KDD CUP共3个Track：

• 常规机器学习竞赛Track（常规ML Track）
• 自动机器学习竞赛Track（自动ML Track）
• “Humanity研究”强化学习竞赛轨道（Humanity RL Track）

常规ML Track

常规ML Track由百度赞助，总奖金45,000美元。

任务1获奖者：

第一名(奖金10,000美元):

Shiwen Cui, Changhua Meng, Can Yi, Weiqiang Wang, Xing Zhao, Long Guo, 蚂蚁金服

第二名 (奖金5,000美元):

Hengda Bao, 上海微盟企业发展有限公司

Jie Zhang, 趋势科技

Wenchao Xu, 滴滴出行

Qiang Wang, 北京邮电大学

Jiayuan Xie, 华南理工大学

He Wang, Ceyuan Liang, 京东

第三名 (奖金3,000美元):

Hua Zhixiang, Sangyu, 来自JIANGLI

任务2获奖者：

第一名(奖金5,000美元):

“Simulating the Effects of Eco-Friendly Transportation Selections for Air Pollution Reduction”

Keiichi Ochiai, Tsukasa Demizu, Shin Ishiguro, Shohei Maruyama, Akihiro Kawana, 来自NTT DOCOMO, INC

第二名(奖金3,000美元):

“Interdisciplinary Knowledge and Experience Fusion In Multi-Modal Transportation Recommendation System”

Yang Liu, Cheng Lyu, Zhiyuan Liu, 东南大学

第三名(奖金2,000美元):

“How to Build ‘Age-friendly’ Cities: Based on Big Data from Baidu Map”

Xin Wei, Nanlin Liu, Yuan Chen, Xiaopei Liu, Tao Wang, Shijun Mu, Hongke Zhao, Xi Zhang, 天津大学和阿尔伯塔大学

PaddlePaddle特别奖(奖金4,000美元):

“Long-term Joint Scheduling for Urban Traffic”

Xianfeng Liang, Likang Wu, Joya Chen, Yang Liu, Runlong Yu, Min Hou, Han Wu, Yuyang Ye, Qi Liu, Enhong Chen, 中国科学技术大学

Auto-ML Track

Auto-ML Track由第四范式赞助，总奖金33,500美元。

第一名（奖金15,000美元）：

Zhipeng Luo，DeepBlueAI

Jianqiang Huang，北京大学

Mingjian Chen，Bohang Zheng，DeepBlueAI

第二名（奖金10,000美元）

Chengxi Xue, Shu Yao, Zeyi Wen, Bingsheng He 新加坡国立大学

第三名（奖金5,000美元）

Suiyuan Zhang，Jinnian Zhang 阿里巴巴集团

Zhanhao Liu 佐治亚理工学院

Zhiqiang Tao, Yaliang Li, Bolin Ding, Shaojian He 阿里巴巴集团

Xu Chu 佐治亚理工学院

Xin Li，Jingren Zhou 阿里巴巴集团

Humanity RL Track

Humanity RL Track由IBM Africa 和Hexagon-ML.com赞助，总奖金25,000美元。

第一名(奖金5,000美元)

Zi-Kuan Huang, Jing-Jing Xiao, Hung-Yu Kao, 国立成功大学

第二名（奖金4,000美元）

Lixin Zou, 清华大学

Long Xia, 京东

Zhuo Zhang, 北京航空航天大学

Dawei Yin, 京东

第三名 (奖金3,000美元)

Suiqian Luo, 瓜子网

会议管理层：57人里华人有14人

至于最关键的KDD 2019组织委员会，在所有57人中，华人/中国人有14人，占比约25%。

他们分别是：

Hui Xiong, Baidu / Rutgers University

Yuxiao Dong, Microsoft Research

Shenghua Bao, Amazon

Wenjun Zhou, UTK

Xiang Ren, USC

Ping Zhang, The Ohio State University

Yong Ge, University of Arizona

Lei Li, Bytedance AI Lab

Shipeng Yu, LinkedIn

Xing Xie, Microsoft Research Asia

Juhua Hu, University of Washington, Tacoma

Bing Liu, UIC

Jing Gao, University at Buffalo, SUNY