【新智元导读】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 个探测器）的平均时间
论文链接：
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%。而且，经过优化的方法比原始框架的运行速度快了两个数量级。
论文链接：
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 赛季的欧洲顶级比赛中展示了与球员搜寻和比赛风格特征相关的大量实例。
论文链接：
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 名没有认知障碍、可以正常生活的人。
我们描述了使用谨慎的数据统一、时间对齐和插补技术来处理实际环境中固有的数据缺失，并最终表明，这些不同的数据能够在症状区分与健康控制上发挥的重要作用。
论文链接：
alessiosignorini.com/articles/de…
经典论文奖：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，DeepBlueAIJianqiang 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 UniversityYuxiao Dong, Microsoft Research
Shenghua Bao, Amazon
Wenjun Zhou, UTKXiang Ren, USCPing 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, UICJing Gao, University at Buffalo, SUNY
