超大規模圖計算在阿里巴巴的應用都有哪些？四篇KDD oral論文搶先看

雷鋒網 AI 科技評論：本文為阿里巴巴提供的 KDD 2018 解讀稿件。這一事件在雷鋒網學術頻道 AI 科技評論旗下資料庫項目「AI 影響因子」中有相應加分。

過去 30 年，隨著高質量實驗技術和互聯網高速連接的出現，越來越大量的數據已經可以自動化的生產和傳輸。隨之而來是，工業界、學術界、甚至個人都必須面對大型數據處理的挑戰，如何從這些大量高維異構的數據中挖掘有價值的信息，一直是數據挖掘從業人員們在解決的問題。「數據挖掘」，通常也為「資料庫中的知識發現」，是一個充分利用各種統計、機器學習、人工智慧模型和與之相適應的計算平台，去試圖自動解釋大型數據集的一個跨領域交叉學科。KDD (ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING) 正是這個領域的頂級會議。從實際數據和與之相關的業務以及 KDD 被接收的文章，我們可以總結出數據挖掘的幾個比較重要的發展趨勢：

?多模態數據挖掘：隨著技術可以更加有效地從多種渠道收集數據，比如音頻、視頻、文字、圖像等，這也是現在越來越被重視的一個方向，而數據本身也更更加有效的以各種方式進行存儲。如何進行跨領域的有效建模，比如多任務學習 (multi-task learning)，遷移學習 (transfer learning)，強化學習（reinforcement learning）等，都是重點的發展模型。

?全域數據挖掘：該方法涉及從移動設備和 IoT 設備等挖掘數據以獲得關於個人的信息。儘管在這種類型中存在諸如複雜性、隱私性、成本等的若干挑戰，但是該方法在各種行業中具有很大的機會，特別是在研究人機交互方面。

?分散式數據挖掘：這種類型的數據挖掘越來越受歡迎，因為它涉及挖掘存儲在不同公司位置或不同組織的大量信息，並且任何的演算法也已經很難在單機版對全網數據進行訓練和推理。此外適應度更高的演算法也可以用於從不同位置提取數據，並根據它們提供適當的見解和報告。

?時空數據挖掘：這是一種新的趨勢類型的數據挖掘，其包括從有周期性和季節性趨勢的環境，天文和地理數據中提取信息，其中還包括從外太空獲取的圖像。這種類型的數據挖掘可以揭示諸如距離和拓撲的各個方面，其主要用於動態的地理信息系統和其他導航應用，這種做法也有助於分析在正常系列事件之外發生的隨機事件。與我們密切相關的問題也是越來越普及，比如新零售，如何有效結合動態的線上線下數據對訪問顧客的購買模式和行為進行建模，就是一個非常有挑戰的時空數據模型問題。

?圖計算模型在大數據公司，尤其是 IT 公司是非常流行的一大類模型，因為是很多實際問題的最直接的解決方法。圖計算大致可以分為同構圖（homogeneous graph）和異構圖（heterogeneous graph），後者是在節點或者邊的種類大於等於 2 的情況下。此外知識圖譜也是異構圖中的一種重要應用，即一種基於語義學的圖模型（a semantic graphical model）。除了了傳統的圖計算模型，如大家熟知的 LPA、 Random Walk 及各種變形、CC 等，隨著深度學習的大量成功落地，Graph Embedding 也變得越來越流行。簡單說來，Graph Embedding 也是通過深度學習模型對節點或者邊進行 feature engineering。近幾年，隨著數據的多樣化，數據量的大幅度提升和算力的突破性進展，圖計算的發展和應用有井噴之勢，各大公司也相應推出圖計算平台，例如 Google Pregel， Facebook Giraph，騰訊星圖，華為 GES 等。

其中超大規模圖數據挖掘也可以認為是前面幾個趨勢的一個匯總，也將是未來 3~5 年年數據挖掘的一個大的集中爆發點。比如 DeepMind、谷歌大腦、MIT 等 27 位作者最近推出重磅論文，表示單純的深度學習已經成熟，而基於圖計算的深度學習將端到端學習與歸納推理相結合，有望解決深度學習無法進行關係推理的問題。超大規模圖計算在大數據公司發揮著越來越重要的作用，尤其是以深度學習和圖計算結合的大規模圖表徵為代表的系列演算法。

超大規模圖計算在大數據公司發揮著越來越重要的作用，尤其是以深度學習和圖計算結合的大規模圖表徵為代表的系列演算法在阿里的諸多業務場景都取得了階段性成果。阿里巴巴生態體系的數據是極其豐富多樣的，涵蓋著從購物、出行到娛樂、支付等各個方面信息。比如個性化推薦系統作為一種信息過濾的重要手段，可以依據我們的習慣和愛好推薦合適的商品或者服務，但是傳統的推薦系統容易出現稀疏性、冷啟動和信息重複性的問題，而知識圖譜作為大規模圖表徵的一類重要模型正在成為一種新興類型的推薦輔助信息，可以將自然人的全域信息有效的結合起來，真正挖掘、理解每個人的需求，在每個業務域推出消費者真正感興趣的潛在商品。我們正在致力於研發新一代推薦系統，可以高效的對於超過幾十億節點，千億的邊進行推理分析。基於這個挑戰，我們正竭力力尋找能夠在信息檢索、分散式計算、大規模系統設計、機器學習、人工智慧、自然語言處理等相關領域帶來新鮮理念的工程師和科學家。對於這個課題感興趣的同學歡迎和筆者進行更深入討論 (yang.yhx@alibaba-inc.com)。

下面我們就會具體介紹一下我們最近取得的一些成果和 KDD 接收文章，包括：

fraud detection（SPARC: Self-Paced Network Representation for Few-Shot Rare Category Characterization）；recommendation（Interactive Paths Embedding for Semantic Proximity Search on Heterogeneous Graphs）；entity resolution(Mobile Access Record Resolution on Large-Scale Identifier-Linkage Graphs)with deep model interpretations(Adversarial Detection with Model Interpretation)。

1. 天才的 SPARC: 阿里巴巴在罕見的分類分析的進展

在網路平台上，稀有數據通常是最有價值的。罕見的類別分析對於防止計算機網路入侵，發現社交媒體上的熱門話題以及檢測欺詐性在線交易至關重要。但是，找到這些數據可能會很困難。就像大海撈針中的諺語一樣，它們通常隱藏在正常數據點之間並且與正常數據點不可分割，並且標記罕見的類別示例非常昂貴。為了有效地分析數據集中的罕見類別，演算法必須是快速學習者。阿里巴巴的技術團隊與亞利桑那州立大學和騰訊醫學人工智慧實驗室合作，創建了 SPARC，這是一個自定進度的框架，以互利的方式逐步學習罕見的面向類別的網路表示和表徵模型。

?按照自己的節奏學習

SPARC 的靈感來自課程學習。課程學習範式模仿人類的認知過程：基礎模型從任務的簡單方面訓練到基於預定課程的更難的方面。

雖然這個概念已經應用於許多不同的情況，但試錯設計很難在現實世界中應用。然而，一種新的學習範式通過使用自定進度的調節器最小化損失函數來自動學習課程。這被稱為自定進度學習。研究小組建立在這種自定進度學習的理念之上，將其應用於稀有類別分析的場景，缺少標記的例子，以便逐步並同時學習稀有類別嵌入表示和表徵模型。SPARC 同時學習圖形嵌入並以互利的方式預測稀有類別示例。該框架能夠在給定網路（例如不同網路大小）中對不平衡類成員資格進行建模。SPARC 能夠從少量標記的稀有類別示例中學習，從而最大限度地降低標籤成本。此外，使用 SPARC 的面向類別的表示能夠在嵌入空間中廣泛地分離多數類和少數類，這些類在網路拓撲和特徵方面是不可分割的。

SPARC 自己節奏的模型示意圖

?將 SPARC 置於行動中

為了測試 SPARC 在該領域的有效性，研究人員收集了來自書目協作網路，NLP 網路和社交網路的數據集。該演算法按照以下標準與兩個無監督網路嵌入演算法 DeepWalk 和 LINE 以及另一個半監督框架 PLANETOID 進行了比較：分類準確性，發現的稀有類別示例的百分比和正在檢索的真實罕見示例的比率。

在大多數情況下，SPARC 在所有數據集和評估指標上的表現優於競爭最先進的方法。雖然半監督嵌入網路在分離類別時表現優於無監督方法，但 SPARC 在聚類罕見示例方面表現優異，並且能夠僅使用一個標記為罕見類別的示例進行訓練。此外，SPARC 更強大，誤差小於比較方法。

由 SPARC 和三個競爭框架提取的網路布局可視化

2. 誰知道誰：用互動式路徑嵌入正確的人

Web 平台最吸引人的功能之一是用戶與他人聯繫的能力。例如，在社交媒體上，用戶甚至可能不必在平台推薦新連接之前主動搜索朋友。在這些網路平台的表面下面是用戶之間龐大的連接網路，並且該網路的大部分依賴於「語義鄰近搜索」：將網路中的對象作為查詢並根據語義關係對其他對象進行排名。語義鄰近搜索查看諸如位置，就業地點和學校等特徵，以確定通過這些連接隱含的語義關係。從那裡，搜索將用戶作為查詢並詢問哪些其他用戶可能是鄰居，同事或同學，相應地對他們進行排名。然後，這些排名用於支持諸如社交媒體上的推薦連接，參考書目網路上的顧問/建議者連接以及在電子商務平台上鏈接用戶身份等功能。

在具有大型用戶基礎的網站（例如 Facebook）上，如上所述的異構圖形可能會很快變得複雜

然而，語義鄰近搜索並不完美。異構列表上的語義關係並不總是明確的，並且對象之間可能缺少鏈接。先前對語義接近度的研究已經嘗試測量與連接查詢對象和目標對象的路徑的語義接近度。但是，這些路徑在建模中是弱耦合的，每個路徑都是單獨處理的。它們的輸出僅在最後階段匯總，限制了模型形成對象之間相互依賴關係的完整畫面的能力。阿里巴巴的技術團隊與來自浙江大學和新加坡高級數字科學中心的研究人員合作，開發了互動式路徑嵌入（IPE），以更強地耦合語義鄰近搜索路徑，找到用戶之間的聯繫，這些聯繫可能會被當前基線忽視。

?IPE 模型的建立

阿里巴巴的研究團隊介紹了交互路徑的概念，同時處理多條路徑並在它們之間添加依賴關係。結果，這些路徑被認為是強耦合的。然後將這些互動式路徑嵌入到低維向量中，該向量可以捕獲用戶之間的語義關係的全部範圍。

IPE 框架的模型

從那裡開始，研究人員利用了一種無循環的改組機制。不希望圖形結構中的循環，因為它們使得兩個節點更難以彼此到達。這種機制改變了路徑的順序，以消除不同的循環並最大化路徑效率。然後，門控循環單元（GRU）架構嵌入交互路徑，並允許每個 GRU 模擬來自其他 GRU 的相互依賴性。最後，交互路徑結構嵌入輸出被聚合為單個向量，然後可以用於估計語義關係接近度。

?IPE 在實際中的使用

為了測試 IPE 在該領域的有效性，阿里巴巴的技術團隊尋找不同類型的異構網路，如 LinkedIn，Facebook，DBLP 和淘寶。在實驗中，IPE 和其他幾個語義用戶搜索基線的任務是根據每個網路特有的特徵集定義不同類型的關係。研究人員為每個測試查詢用戶和每個所需的語義關係構建了理想的排名。他們將這種理想排名與各種最先進的語義用戶搜索演算法生成的排名進行了比較。在所有這些測試中，IPE 不僅在競爭基線方面表現優異，而且在自身的降級版本方面也表現優異，通常顯著。這驗證了交互路徑結構，並為擴展 IPE 以處理異構網路中的屬性和動態以進行語義鄰近搜索打開了大門。

3. 通過你的手機可以對你做人物畫像嗎？

電子商務時代正在見證移動互聯網用戶的快速增長。主要的電子商務公司現在每天都會看到數十億的移動訪問實例，並且隱藏在這些記錄中的是有價值的用戶行為特徵，例如購物偏好和瀏覽模式。但是，為了從龐大的數據集中提取此信息，需要將記錄鏈接到相應的移動設備，這一過程稱為移動訪問記錄解析（MARR）。MARR 面臨兩大挑戰：

1.訪問記錄中的設備標識符和其他屬性可能缺失或不可靠。

2.數據集包含數百萬台設備的數十億訪問記錄。

目前，還沒有開發出現有方法來解決如此大規模使用移動設備標識符的問題。

?我們可能不知道你在用什麼設備

根據國際電信聯盟（ITU）的一份新報告，2017 年全球移動互聯網用戶（非用戶）數量達到 77.4 億。隨著行動電話取代台式電腦成為最廣泛使用的數字平台，移動用戶偏好的特徵他們的訪問記錄中的行為模式變得非常重要。與傳統的博客相比，移動訪問記錄主要依賴於 cookie 來跟蹤用戶行為，因此可以更清晰地了解訪問記錄中具有各種 ID 的互聯網用戶。這些 ID 包括：

1.國際移動設備身份（IMEI）- 用於識別設備的唯一標識符。

2.國際移動用戶識別碼（IMSI）- 用於識別存儲在 SIM 卡中的蜂窩網路中的用戶。

3.UserTrack 設備 IDentity（UTDID）。

IMEI 和 IMSI 分別是一個智能手機和手機號碼的標識符。另一方面，UTDID 與這兩個基於硬體的標識符完全不同，因為它由阿里巴巴（中國的跨國電子商務公司）生成和使用，用於設備識別。利用這些 ID，可以將訪問記錄映射到相應的行動電話或應用程序，從而生成更高質量的用戶配置文件。將訪問記錄映射到行動電話或應用程序似乎是一件簡單的事情，因為可以使用諸如 IMEI，IMSI 和 UTDID 之類的 ID 來唯一地識別設備和應用程序。但是，從實際應用中收集的數據遠非完美。將丟失屬性值，雜訊（有問題和誤導性）ID 和 ID 轉換問題。ID Shift 轉換的一種方式是當設備在安裝新 SIM 卡時獲得新的 IMSI。

我們的移動訪問記錄中有大量數據

?讓我們的設備自己發聲

阿里巴巴技術團隊觀察到，訪問記錄中的一個或兩個 ID 的 ID 轉換可能會不時發生，但很少發生在所有三個 ID 中。受此觀察的啟發，他們使用三個 ID（IMEI，IMSI，UTDID）的組合（他們稱之為「IDSET」）來可靠地識別來自特定移動設備的訪問記錄。上面給出了 IDSET 的示例記錄由 IDSET 標識，即 IMEI，IMSI 和 UTDID 的組合。基於 IDSET 的概念，他們引入了移動訪問記錄解決（MARR）問題。MARR 問題的目的是識別每個訪問記錄的物理設備，因為每個訪問記錄由一個特定的移動設備生成。該團隊的目標是根據設備對訪問記錄進行分組，該設備可用於為設備用戶生成配置文件。考慮到數據集的龐大規模和較差的數據質量主要是由於 ID 轉移問題，MARR 是一個非常具有挑戰性的問題。因此，該團隊還提出了一個稀疏標識符鏈接圖（SPI-Graph），並附帶豐富的移動設備分析數據，以準確地將移動訪問記錄與設備進行匹配（當數據集中的某些預期值丟失時，數據被視為「稀疏」，這是一般大規模數據分析中的常見現象）。到目前為止，大規模實際數據集的廣泛實驗結果驗證了團隊演算法的有效性和效率。這些結果還意味著團隊現在希望調查他們如何進一步將特定設備的移動訪問記錄分組到訪問會話中，從而更好地表徵用戶配置文件。

4.了解你的對手：阿里巴巴如何培養更智能的在線欺詐探測器

隨著越來越多的實際應用程序，機器學習（ML）系統最近成為一種有前途的在線欺詐檢測工具。然而，在大多數 ML 任務處理固定數據集的情況下，欺詐檢測對能夠在暴露時能夠適應的智能人類行為者起作用，這意味著 ML 模型在移位數據集中易於變得靜止。以前建立更能抵抗變化對手的探測器的努力依賴於諸如分類和特徵識別增強，死記硬背對抗訓練和深度神經網路應用之類的方法。每一個都有其自身的局限性，但一個主要的反覆出現的問題是「黑匣子」難題。研究人員通常無法獲取有關這些方法的內部運作的詳細信息，否認他們可以幫助他們進一步發展這些方法的重要見解。現在，阿里巴巴的研究人員已經開發了一種對抗訓練方法，該方法基於對 ML 模型運作的研究，運用其機制的知識來產生更強大的對手，供他們訓練。除了提高探測器的批發穩健性之外，從最少的計算資源中產生具有挑戰性的新對手的努力有助於揭示真正的欺詐犯罪者在被發現後可能從給定位置適應的方式。建立在垃圾郵件發送者基本上是人類代理人的前提下，他們在適應時花費的資源有限，該方法展示了如何根據先前攻擊的定位來預測未來攻擊的「方向」。

?檢查黑箱

ML 欺詐檢測系統依靠分類器來過濾內容，將一些垃圾郵件發送者實例視為高可信度，將其他實例視為低可信度實例，具體取決於它們被正確標記的概率。當大量垃圾郵件發送者實體落入其低信任區域時，分類器變得容易受到攻擊，因為即使對垃圾郵件發送者這樣的易於逃避（EP）樣本的微小變化也可能導致其錯誤分類為合法內容。出於研究目的，阿里巴巴團隊將這些 EP 樣品作為「種子」處理，用於生成強大的對抗樣品，用於探測器培訓。然後，他們試圖確定種子最容易受到影響的方向，以逃避分類機制，從而以最小的努力繞過檢測。利用這些發現，他們生成的對手非常模模擬實的惡意行為，減少了有效訓練更強檢測機制所需的攻擊者總數。通過使用 ML 機制的知識來分析其對沿其邊界引入的每個對手的響應，該團隊派生出特定於每個實例的本地解釋器功能。通過這些信息，他們更新了整體機制，以更好地考慮試驗期間引入的個別垃圾郵件威脅的演變。

新系統識別易於逃避的樣本，分析潛在的逃避策略，並相應地更新檢測模型

基於對 Yelp Review 和 Twitter 帖子數據的實驗，仔細的對手選擇證明在產生更具挑戰性的攻擊模擬方面是有效的，在試驗期間提供了關於分類器中的弱點的大量信息。然後，這些研究結果被用於為各種攻擊制定有效的防禦策略，這些策略可用於加強未來檢測框架的有效性。展望未來，阿里巴巴正在尋求擴展其垃圾郵件檢測工作，以處理實例之間關係鏈接的高維原始數據和數據集。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！