第 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 架構來挖掘時空圖中的豐富語義資訊，有效提升了預估到達時間任務的精确度。本文是對這篇論文的詳細解讀。
研究背景與挑戰
随着人們與日俱增的出行需求，智慧交通系統已成為城市建設中不可或缺的角色。預估到達時間（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 模型的有效性。