【新智元導讀】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 大會以論文接收嚴格聞名，每年的接收率不超過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 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已成爲一種經典的社會網絡影響最大化發現算法。
該方法是基于影響力具有子模函數特征提出的，即所有節點的影響力隨著種子節點集合中節點數目增加在減弱，具有單調遞減性。
該方法分爲兩個步驟：第一個步驟用于選擇第一個種子節點，在全部節點中搜索種子節點，選擇影響力最大節點加入到種子節點集合中；第二個步驟用于選擇余下種子節點，利用影響力具有單調遞減性這一性質在部分影響力較大節點中搜索種子節點。由于在第二個步驟中此方法搜索種子節點空間的減少，該方法的效率有了較大提高。
該論文的第一作者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