逐鹿最佳論文！程學旗團隊獲ECML-PKDD最佳學生論文獎

  • 2020 年 11 月 17 日
  • AI

作者 | 陳大鑫

進入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（數據挖掘最佳學生論文獎）。
論文鏈接：//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演算法的效率與圖的大小成線性關係，在實際應用中非常有效，比如在研究合作關係中發現突然爆發。有理論界保證的檢測演算法設計和流圖自適應也是這項工作的可能擴展方向。
更多細節內容請查閱原論文。

5

作者介紹

馮文傑：
中國科學院計算技術研究所博士畢業，目前是新加坡國立大學數據科學研究所研究員，研究興趣包括數據挖掘、大規模圖挖掘、機器學習、社交網路分析和異常檢測。
個人主頁：//wenchieh.github.io/

劉盛華：
 

中國科學院計算技術研究所的副研究員，CMU電腦科學系訪問學者、清華大學電腦系博士、優博論文、UCLA電子工程系學術界校友代表等。亞太設計自動化會議（ASP-DAC）最佳論文候選提名、ECML-PKDD最佳學生論文獎、微軟亞洲學者、國際期刊Complexity的特別專刊共同客座主編。

目前研究興趣包括大圖數據分析、時間序列挖掘、異常檢測，圖神經網路魯棒性，以及為海量數據設計智慧和可擴展演算法。論文出版物發表在IEEE TKDE，ACM TKDD，ECML-PKDD，CIKM，ICDM，SDM，以及AAAI，IJCAI，TCAD，DAC等。

個人主頁：//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。
個人主頁：//www.bigdatalab.ac.cn/~shenhuawei/ 
 
程學旗：
中科院計算所研究員、博士生導師、副所長。主要研究方向網路數據科學、大數據分析技術、資訊檢索與挖掘、大數據系統以及資訊安全應用等。CCF會士、IEEE高級會員，擔任中國電腦學會大數據專家委員會秘書長、中國中文資訊學會資訊檢索專委會主任、中國工業與應用數學學會大數據與人工智慧專委會副主任。國家傑出青年科學基金、國務院特殊津獲得者，中組部萬人計劃科技領軍人才。
在本領域重要國際學術期刊和會議上發表論文200餘篇，Google Scholar引用超過16000次，獲得授權專利60餘件。研製完成的大規模分散式機器學習系統（EasyML）、文本與自然語言處理工具集（MatchZoo）、圖數據計算引擎（SQLGraph）等在國際開源社區影響廣泛，在查詢理解、資訊檢索和排序學習方面的研究成果五次獲得本領域重要學術會議（ACM SIGIR、ACM CIKM、PKDD等）優秀論文獎。研究成果形成的大數據分析系統與關鍵技術得到了規模化應用，成果獲得國家科技進步二等獎三次，省部級獎勵六次。
個人主頁：//www.bigdatalab.ac.cn/~cxq/

點擊閱讀原文，直達NeurIPS小組~

VirMach 便宜 VPS

QNews

QNews