更精確地預估到達時間,滴滴新研究提出異質時空圖卷積網絡

2021-01-11 機器之心Pro

機器之心發布

機器之心編輯部

「師傅，還有多長時間能到啊？」在打的趕往目的地時，我們經常會問這樣一個問題。但如果我們打的是滴滴，這個問題就不用開口問了。因為，滴滴的研究者正不斷挑戰更加精確的到達時間預估結果，相關結果被 KDD 2020 接收為Oral論文。

第 26 屆 ACM SIGKDD 知識發現和數據挖掘會議（KDD 2020）正以線上形式召開。今年 KDD 應用數據科學方向 (Applied Data Science Track) 共收到 756 篇論文投稿，收錄 121 篇，接收率約為 16.0%，其中 Oral 論文 44 篇、Poster 論文 77 篇；KDD 研究方向 (Research Track) 有 1279 篇論文投稿，收錄 216 篇，接收率約為 16.9%。

在本屆大會中，滴滴的《HetETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival》被接收為 Oral 論文。在這篇論文中，滴滴 AI Labs 技術團隊針對預估到達時間任務構建了一個異質時空圖，並提出了 HetETA 框架來挖掘時空圖中的豐富語義信息，有效提升了預估到達時間任務的精確度。本文是對這篇論文的詳細解讀。

論文地址：https://dl.acm.org/doi/pdf/10.1145/3394486.3403294

代碼地址：https://github.com/didi/heteta

研究背景與挑戰

隨著人們與日俱增的出行需求，智慧交通系統已成為城市建設中不可或缺的角色。預估到達時間（Estimated Time of Arrival，ETA）是智慧交通系統中尤為關鍵的一項任務，根據給定的出發時間，精確地預估出從起點到終點所需時長，有助於節省用戶的出行時間，優化車輛調度和路徑規劃等。ETA 任務與道路交通速度預測密切相關，即當道路的交通速度（或道路擁堵程度）已知時，可通過道路長度將道路的交通速度轉化為通過該道路所需的時間。

當前大多數工作致力於建立豐富的特徵系統來提高 ETA 任務的準確性，然而這些特徵系統很少考慮到空間信息的構建與挖掘。如圖 1 所示，地圖中的道路網絡實際上是一種含有多個連結關係的異質圖，而這些道路之間的連結關係（即空間信息）對於道路交通速度預測至關重要。例如圖 1 中的路段 1 如果是擁堵的，那麼路段 1 的前方直行道路 2 大概率也會是擁堵的。

圖表 1：地圖數據到異質圖的轉換

又比如在高速上直行的車輛速度一般高於向右駛出閘道的車輛。然而地圖中的道路網絡是一個大規模的稀疏網絡，以包含了 7 萬多個主幹道的瀋陽市為例，其道路網絡的平均度數為 2.52，即一條道路路段一般只連結 2～3 條道路。這樣的大規模稀疏網絡難以直接使用需要充足鄰居信息的圖神經網絡（Graph Neural Network，GNN）進行網絡的表示學習（representation learning／network embedding）。

除了地圖數據中的道路網絡，車輛軌跡信息也是一種描述道路之間連結關係的空間信息。例如圖 2 中青年大街的車輛大部分流向了太原街（瀋陽市具有火車站和客運站的交通樞紐）和中街（瀋陽市著名購物街）。大量的車輛軌跡組成了車流信息，隱含了城市的交通模式以及駕駛經驗、偏好信息，這些信息很難直接從地圖數據中的道路網絡中得到，因此需要對道路網絡和車流信息進行聯合建模。

圖表 2：瀋陽車流示意圖

此外，ETA 任務也與道路交通速度的時序信息息息相關。直觀來說，若某路段在當前時刻為擁堵狀態，則下一時刻該路段大概率仍為擁堵狀態，即道路下一時刻的交通狀態與近期時刻的交通狀態（近期路況）相關。

圖 3 描述了瀋陽某道路路段交通狀況在 2 周內的變化趨勢，從中可觀察到周一到周五工作日有明顯近似的尖峰時段（早上 8 點左右以及晚上 6 點左右），而周六日的尖峰時段則從早 8 點持續到晚上 6 點左右，即交通路況呈一定程度的周期性與規律性。因此，道路下一時刻的交通狀態除了與其近期路況相關，還與其近幾日的相同時段路況相關，同時也與近幾周相同星期的相同時段路況相關。

圖表 3：瀋陽某道路在 2 周內的交通速度變化情況

由此，滴滴在這篇論文中主要針對以下問題提出解決方案：

如何挖掘空間信息中不同關係連結所蘊含的語義關係？

如何克服大規模道路網絡的稀疏性？

如何聯合道路網絡信息和車流信息對 ETA 任務進行預測？

如何處理不同時序（近期的、每日的、每周的）路況信息中的模式關係？

解決方案：HetETA

圖表 4：HetETA 框架示意圖

為了解決上述問題，該研究提出了 HetETA 框架，聯合卷積神經網絡（Convolution Neural Network，CNN）和圖神經網絡（Graph Neural Network, GNN）處理時序信息和空間信息。如圖 4 所示，HetETA 由三個相同結構的組件組成，每個組件分別用於處理不同時序路況（近期的、每日的、每周的）中的異質時空信息，其中，，

為當前查詢時刻，為輸入三個組件的時間片數量，為一天的時間片總數量。三個組件均通過雙拼三明治結構進行時空卷積得到對應的低維向量表示，然後將這三個低維向量表示拼接起來作為長向量，經過一個全連接層得到預估的路段速度：

雙拼三明治結構（Double-stuffed sandwich layer）由 3 個卷積神經網絡和 2 個 Het-ChebNet 組成，其中 2 個 Het-ChebNet 夾在兩個卷積神經網絡中間形成一層空間卷積層，通過對時間（CNN）和空間的（Het-ChebNet）的交替卷積使模型能夠充分地挖掘時空之間的關聯性。最後一層的卷積神經網絡用於將時間維度壓縮至一維，以便於後續全連接層的操作。為了使 CNN 達到類似 RNN 的時序處理效果，本文採用了帶有門控的因果卷積神經網絡（如圖 5），在輸入時，執行卷積操作：

圖表 5：帶有門控的因果卷積神經網絡層

進而得到當前層的隱含狀態向量 H。空間卷積層所包含的兩個 Het-ChebNet 分別用於對道路網絡和車流網絡所構建的異質圖進行空間信息的卷積與提取，分別由兩個 Het-ChebNet 得到的隱含狀態通過拼接操作輸入下一層卷積神經網絡（如圖 6）。

圖表 6：雙拼圖卷積網絡

車流網絡所構建的異質圖一定程度上緩解了道路網絡的稀疏問題，為了克服基於 GCN（Graph Convolutional Network）的圖卷積模型無法在稀疏的道路網絡上收集充足的鄰居信息的問題，該研究採用了基於譜圖理論的 ChebNet 網絡，通過切比雪夫多項式構成局域濾波器：

然而，傳統的 ChebNet 網絡無法處理異質圖中所包含的多關係信息，因此該研究基於 ChebNet 提出了一個能夠捕捉多關係連結信息的 Het-ChebNet：

即通過在濾波器上乘積一個關於鄰居邊的注意力評分矩陣，使得濾波器能夠對不同的連結關係進行區分過濾提取信息。注意力評分矩陣存儲了異質圖中 z 階鄰居邊的注意力評分，其計算公式為：

在異質圖中，相同的兩個頂點之間可能具有多種連結關係，因此注意力評分矩陣的值為這些連結關係連結的評分之和：

最後通過 softmax 函數進行評分矩陣的歸一化：

實驗效果

研究人員在滴滴平臺數據集上對 HetETA 模型的有效性進行了驗證，對比算法包括 GRU、DCRNN、STGCN、Graph WaveNet 以及 ASTGCN。

如圖 7 所示，相比其他模型，HetETA 在送駕數據集和接駕數據集上分別獲得了 3.40%～46.67% 和 0.69%～28.33% 的實質性收益。當μ更大時，HetETA 帶來的 BCR-μ 的改善變得更加明顯。

圖表 7：ETA 任務 BCR 效果對比

此外，該研究還將 HetETA 與 WDR 模型聯合起來，將 HetETA 最後一層的隱狀態向量作為 WDR 的額外特徵輸入。與原來的 WDR 模型相比，加入了 HetETA 的 WDR 模型 MAPE 下降了 1.19%～1.94%，MAE 下降了 1.57%～5.30%，RMSE 下降了 1.67%～6.42%，BCR 下降了 3.33%～18.50%。這對於具有不可預測性的 ETA 任務而言，無疑是非常顯著的提升，證明了 HetETA 模型的有效性。

相關焦點

  • 混合時空圖卷積網絡:更精準的時空預測模型|KDD2020
    以往的研究中主要利用通行時間這類交通狀態特徵作為模型輸入，很難預測整體的交通狀況，本文提出的混合時空圖卷積網絡，利用導航數據大大提升了時空預測的效果。日常通勤中的規律往往相對容易挖掘，但交通狀況還會受很多其他因素影響，之前的研究主要利用通行時間這類交通狀態作為特徵，少量研究引入事件，不能很好地預測實際交通流量。
  • 圖神經網絡讓預估到達準確率提升50%,谷歌地圖實現新突破
    機器之心報導編輯：魔王、杜偉、小舟公交車、計程車等交通工具的到達時間是影響公眾出行的一大因素。所以，預估到達時間（ETA）準確率成為非常實際的研究課題。近日，DeepMind 與谷歌地圖展開合作，利用圖神經網絡等 ML 技術，極大了提升了柏林、東京、雪梨等大城市的實時 ETA 準確率。很多人使用谷歌地圖（Google Maps）獲取精確的交通預測和預估到達時間（Estimated Time of Arrival，ETA）。這是很重要的工具，尤其是當你將途經交通擁堵路段或者需要按時參加重要的會議。
  • KDD 2018:滴滴提出WDR模型顯著提升ETA預測精度
    事項：KDD 2018獨家約稿
  • 港中文AAAI錄用論文詳解:ST-GCN 時空圖卷積網絡模型 | AAAI 2018
    作為動作識別系統中的重要模態，基於骨架的動作識別已經展現出重要的實用價值與研究價值。本論文正是針對這個任務提出了一種全新的深度學習模型，我們稱之為「時空圖卷積網絡」（ST-GCN）。構建時空圖ST-GCN 的基礎是時空圖結構。
  • 如何讓圖卷積網絡變深?騰訊AI Lab聯合清華提出DropEdge
    機器之心發布機器之心編輯部近年來，圖神經網絡的研究異常火爆，被各大頂會錄取的文章數量爆炸式增長。然而，目前大部分圖卷積網絡，尤其是面向節點分類的網絡，都是淺層網絡。這些模型分類效果往往隨著深度加深而變差（即使使用殘差連接），這與用於圖片分類的卷積網絡動輒超過幾十層的現象很不一致。圖卷積神經網絡變深之後難以訓練的現象嚴重製約了其表達能力。所以，如何有效的訓練超深圖卷積網絡是圖學習研究的一個重大挑戰。這項工作由騰訊 AI Lab 與清華大學合作完成。
  • 德克薩斯A&M大學在讀博士遊宇寧:自監督學習在圖卷積網絡中的研究...
    自監督學習是一種介於無監督和有監督學習之間的新範式，可以有效減少對大量帶注釋數據的需求。在數據訓練的過程中，生成帶有無噪聲標籤的數據集的成本很高，而無標籤的數據又一直在不斷產生。當前自監督學習已經被廣泛用於訓練卷積神經網絡（CNNs），有效地提高了圖像表示學習可傳遞性、泛化能力和魯棒性，並且已在語義分割、目標檢測、圖像分類、人體動作識別等實戰場景中展現出卓越效果。現在更多無需人工標註的前置任務訓練也被提出，如前景對象分割、圖像修補、圖像著色等。然而，自監督如何應用於處理圖數據結構的圖卷積網絡（GCNs）的問題卻很少被探索。
  • 為什麼要進行圖學習?談一談逆勢而上的圖神經網絡
    | 圖池化Rethinking pooling in graph neural networksNeurIPS2020 | 圖分類SOTA：節點互信息最大化與多尺度特徵交互NeurIPS 2020 | 超越同質性假設: 解決當前GNN的局限與並提出有效性設計NeurIPS 2020 | 圖上學習新方式—迭代式圖學習: 結合下遊任務迭代地學習圖結構和圖表示
  • 人工智慧之卷積神經網絡(CNN)
    ^_^本文引用地址：http://www.eepw.com.cn/article/201806/381807.htm　　20世紀60年代，Hubel和Wiesel在研究貓腦皮層中用於局部敏感和方向選擇的神經元時發現其獨特的網絡結構可以有效地降低反饋神經網絡的複雜性，繼而提出了卷積神經網絡CNN(Convolutional Neural Networks)。
  • 滴滴科技開放日:如何利用出行交易中的大數據優化乘客體驗
    他表示，滴滴有超過 5 億 5 千萬乘客，有超過 3000 萬司機，在這樣一個龐大的出行交易平臺上，從用戶打開滴滴 App 的那一刻，滴滴的大數據技術就開始在背後幫助用戶打造美好的出行體驗。他詳細描述了滴滴如何為乘客推薦上車點，如何進行路徑規劃，如何預估到達時間等等。
  • 滴滴新算法讓你兩不誤
    後來小陳準時趕到女朋友之前赴約……小陳心想這軟體預估到達的時間真是準啊，多虧了它，農藥也打了，約會也沒遲到。相信以上類似場景大家多少都有遇到過，大家近些年逐漸習慣用網約車，而以滴滴為代表的網約車軟體背後必須要提供各方面精準的服務。
  • 深入理解卷積網絡的卷積
    卷積神經網絡是一種特殊的神經網絡結構，是自動駕駛汽車、人臉識別系統等計算機視覺應用的基礎，其中基本的矩陣乘法運算被卷積運算取代。它們專門處理具有網格狀拓撲結構的數據。例如，時間序列數據和圖像數據可以看作是一個二維像素網格。
  • 從圖(Graph)到圖卷積(Graph Convolution):漫談圖神經網絡 (二)
    在從圖(Graph)到圖卷積(Graph Convolution): 漫談圖神經網絡 (一)中，我們簡單介紹了基於循環圖神經網絡的兩種重要模型，在本篇中，我們將著大量筆墨介紹圖卷積神經網絡中的卷積操作。接下來，我們將首先介紹一下圖卷積神經網絡的大概框架，藉此說明它與基於循環的圖神經網絡的區別。
  • 深度學習技術和卷積神經網絡(CNN)讓機器視覺識別更智能
    隨著人工智慧技術的進步，深度學習技術（DL）和卷積神經網絡技術(CNN)領域的人工智慧（AI）被引入到機器視覺圖像處理系統的應用中來,從而幫助機器學習和機器檢測缺陷更加高效，使機器視覺識別的過程更加精確。也讓使用這些技術的企業可以從智能化中獲得更高的生產經營效益。
  • 視覺信息助力廣告點擊率預估-京東廣告團隊技術論文入圍KDD2020
    在用戶興趣多變、異質行為差異巨大電商場景下，KFAtt比傳統attention表現出更優的效果。 Realtime Graph Convolutional Network (RGCN)是用戶-商品實時關係圖建模的方法。對於長尾和冷起階段的商品，藉助關係圖可以得到更豐富的表示；對於活動、促銷，實時關係圖也可以更快捕獲商品的時變特性。
  • 視覺信息助力廣告點擊率預估——京東廣告團隊技術論文入圍KDD2020
    在用戶興趣多變、異質行為差異巨大電商場景下，KFAtt比傳統attention表現出更優的效果。l Realtime Graph Convolutional Network (RGCN)是用戶-商品實時關係圖建模的方法。對於長尾和冷起階段的商品，藉助關係圖可以得到更豐富的表示;對於活動、促銷，實時關係圖也可以更快捕獲商品的時變特性。
  • 卷積神經網絡:從基礎技術到研究前景
    ，對卷積網絡的技術基礎、組成模塊、現狀和研究前景進行了梳理，介紹了我們當前對 CNN 的理解。本文對該論文進行了摘要式的編譯，更詳細的信息請參閱原論文及其中索引的相關文獻。 1.3 報告提綱 本報告的結構如下：本章給出了回顧我們對卷積網絡的理解的動機。第 2 章將描述各種多層網絡並給出計算機視覺應用中使用的最成功的架構。第 3 章將更具體地關注典型卷積網絡的每種構造模塊，並將從生物學和理論兩個角度討論不同組件的設計。
  • 深度學習時代的圖模型,清華發文綜述圖網絡
    但是，將深度學習應用於普遍存在的圖數據仍然存在問題，這是由於圖數據的獨特特性。近期，該領域出現大量研究，極大地提升了圖分析技術。清華大學朱文武等人綜述了應用於圖的不同深度學習方法。他們將現有方法分為三個大類：半監督方法，包括圖神經網絡和圖卷積網絡；無監督方法，包括圖自編碼器；近期新的研究方法，包括圖循環神經網絡和圖強化學習。然後按照這些方法的發展史對它們進行系統概述。
  • 三維變二維,港中文提出用於點雲卷積的局域展平網絡模塊FPConv
    為了克服三維卷積帶來的計算資源消耗和解析度限制，來自香港中文大學深圳分校等機構的研究人員們提出了一種基於局域展平的二維平面卷積方法FPConv，將點雲非線性投影到特殊平面上，而後在利用2D卷積進行有效地特徵抽取。這種方法將點雲轉換到二維平面上的投影過程和插值過程簡化為一個權重矩陣的學習。
  • 依圖團隊提出新一代移動端網絡架構MobileNeXt
    最近，依圖團隊發表在ECCV的一篇論文，提出了新一代移動端神經網絡架構MobileNeXt，大大優於谷歌的MobileNet、何愷明團隊提出的ResNet等使用倒殘差結構的模型，為移動端算力帶來了新的突破。
  • 從全卷積網絡到大型卷積核:深度學習的語義分割全指南
    2014年，加州大學伯克利分校的Long等人提出全卷積網絡（FCN），這使得卷積神經網絡無需全連接層即可進行密集的像素預測，CNN從而得到普及。使用這種方法可生成任意大小的圖像分割圖，且該方法比圖像塊分類法要快上許多。之後，語義分割領域幾乎所有先進方法都採用了該模型。　　除了全連接層，使用卷積神經網絡進行語義分割存在的另一個大問題是池化層。