基于圖神經(jīng)網(wǎng)絡的用戶軌跡分類

吳勁，陳樹沛*，楊慶,2，周帆

(1.電子科技大學信息與軟件工程學院 成都 610054；2.中國電子科技集團公司第十研究所 成都 610036)

隨著物聯(lián)網(wǎng)和移動應用的發(fā)展，基于位置信息的應用服務越來越多。在各種移動應用中，大量的個人位置信息和活動信息被收集，如共享單車的軌跡信息、用戶的簽到信息。這些信息反映了用戶的移動模式和活動意圖，可以用于提供各種各樣的服務，如交通規(guī)劃、智能推薦和智能城市規(guī)劃等。這為研究人員提供了一個挖掘人類移動模式的新機會，衍生了很多新研究，如下一個興趣點(point of interest,POI)推薦[1]、基于位置的信息推送[2]及在線社交推薦[3]等。在眾多的研究中，軌跡用戶鏈接(trajectory-user linking,TUL)[4]問題旨在研究如何將軌跡鏈接到生成該軌跡的用戶，可以更好地掌握各種基于位置的移動應用中用戶的移動模式和規(guī)律?；谖恢玫纳缃痪W(wǎng)絡(location-based social networks,LBSNs)，如Foursquare 和Yelp 等網(wǎng)站收集了很多用戶的簽到位置信息，出于隱私考慮，第三方服務提供商會對用戶身份進行匿名處理，因此用戶軌跡數(shù)據(jù)或用戶簽到數(shù)據(jù)一般不包含對應的真實用戶。將這些軌跡與相應的用戶關聯(lián)起來，可以挖掘出用戶的訪問意圖和活動規(guī)律，用于POI 推薦和用戶旅行路線推薦等。此外，TUL還可以識別出可疑的訪問和移動模式，預防違法犯罪活動。

近些年來，與人類移動相關的數(shù)據(jù)呈爆炸式增長[5]。由于軌跡數(shù)據(jù)的稀疏性和帶標記軌跡的數(shù)量不足，解決TUL 問題存在一定的挑戰(zhàn)。傳統(tǒng)的工作通常是通過馬爾可夫鏈等序列學習模型來建模人類的移動規(guī)律，進而將軌跡和用戶相鏈接。這些模型捕獲的是用戶簽到點之間的短期依賴關系。受現(xiàn)有深度學習技術的啟發(fā)，一些研究人員采用循環(huán)神經(jīng)網(wǎng)絡(recurrent neural networks,RNN)建模用戶軌跡，其表現(xiàn)優(yōu)于淺層機器學習方法。文獻[4]正式定義了TUL 問題，并提出了基于POI 嵌入和循環(huán)神經(jīng)網(wǎng)絡的軌跡用戶鏈接模型TULER。TULVAE[6]通過軌跡分布的變分推斷擴展了TULER，利用半監(jiān)督學習方式學習人類移動規(guī)律。TGAN[7]和STULIG[8]是兩種深度生成模型，通過數(shù)據(jù)增強增加軌跡數(shù)據(jù)量，并分別使用對抗學習和分級自編碼器對用戶軌跡進行分類。而最近關于用戶簽到點預測的方法，如DeepMove[9]、CATHI[10]和VaNext[11]，也可以用于解決TUL 問題。它們利用RNN 的變體，如長短時記憶網(wǎng)絡(long short term memory network,LSTM)[12]和門控循環(huán)單元(gatedrecurrent unit,GRU)[13]學習軌跡中的序列變換規(guī)律，在捕獲用戶個性化移動模式方面表現(xiàn)良好。

盡管上述研究在用戶移動模式學習和分類方面取得了很好的成果，但它們仍存在一定的局限性。首先，簽到點之間的空間位置關系尚未得到充分挖掘。現(xiàn)有方法只依靠軌跡數(shù)據(jù)來獲取簽到點嵌入，忽略了簽到點之間的地理位置信息。因此，僅從軌跡序列數(shù)據(jù)中不足以學習到有代表性的簽到點嵌入。其次，大多數(shù)POI 被訪問的頻率非常低，導致基于位置的社交網(wǎng)絡中的簽到數(shù)據(jù)往往過于稀疏，使得模型忽略了數(shù)據(jù)中隱含的訪問偏好和移動模式。另外，以往的工作主要使用生成模型來豐富軌跡數(shù)據(jù)，這通常需要非常高的計算成本。如，TULVAE和TGAN 分別利用變分自編碼器(variational autoencoder,VAE)[14]和生成對抗網(wǎng)絡(generative adversarial networks,GAN)[15]來推斷潛在的軌跡分布，這對于訓練和計算效率而言是一個挑戰(zhàn)。這些生成模型的效率問題限制了它們在大規(guī)模移動數(shù)據(jù)上的應用。

為了解決上述挑戰(zhàn)和當前模型存在的不足，本文提出了一種新的基于圖神經(jīng)網(wǎng)絡的軌跡用戶鏈接模型GTUL。GTUL 不再只依賴用戶的訪問序列，而是利用簽到點構建簽到圖，收集軌跡中的空間信息和時間信息，然后使用圖神經(jīng)網(wǎng)絡(graph neural network,GNN)[16]學習簽到圖中的簽到點的表示，再結合循環(huán)神經(jīng)網(wǎng)絡建模用戶的移動模式，最后使用全連接網(wǎng)絡對軌跡進行用戶分類，實現(xiàn)軌跡與用戶的正確鏈接。簽到圖可以綜合所有的歷史軌跡信息，提取出原始軌跡數(shù)據(jù)的訪問偏好和復雜移動規(guī)律。與現(xiàn)有的軌跡數(shù)據(jù)增強算法相比，該方法更具通用性、可擴展性和有效性。

1 問題定義

2 模型設計

2.1 模型整體框架

本文模型分為4 個模塊，模型總體框架如圖1所示。首先，對原始軌跡數(shù)據(jù)進行分割處理，并基于分割后的軌跡數(shù)據(jù)構建用戶簽到圖(如圖1a 所示)；其次，利用GNN 學習簽到圖中的節(jié)點嵌入(如圖1b 所示)；然后，利用RNN 構建軌跡序列的向量表示(如圖1c 所示)；最后使用全連接網(wǎng)絡得到最終的分類結果(如圖1d 所示)。

圖1 基于圖神經(jīng)網(wǎng)絡的用戶軌跡分類模型架構

2.2 用戶簽到圖構建

根據(jù)文獻[4,9]的研究，用戶軌跡包含的簽到數(shù)量因人而異，軌跡的時間跨度也極不規(guī)則。因此，需要對用戶軌跡進行分割，劃分成多個子軌跡。文獻[4,10]發(fā)現(xiàn)用戶的簽到點存在很強的周期性，因此本文將每個用戶的歷史軌跡按固定的時間間隔(如6h)劃分為若干個子軌跡。

構建方法如圖2 所示，首先分別構建兩個圖來表示簽到點的地理特征(圖2c)和用戶的訪問偏好(圖2d)，并將這兩個圖合并形成最終的簽到圖(圖2e)。

圖2 簽到圖構建方法

正如文獻[4,9]中所觀察到的，移動應用用戶通常更喜歡訪問距離自己更近的位置。因此，連接距離相近的簽到點構造無向圖GS=，稱為空間圖(spatial graph)，其中每個節(jié)點vi∈V表示一個真實的簽到點，ES表示邊的集合。如果簽到點之間的地理距離小于某一個閾值ε，那么它們之間將有邊相連。

除了地理特征，還構建了有向訪問圖(visiting graph)，即GV=來收集用戶的訪問意圖和序列移動模式，其中EV表示所有的訪問軌跡。一條邊eij∈EV表示從地點i到地點j的一{個用戶}訪問行為。如用戶ui的一個子軌跡為，則在EV中添加和。因此，GV保存了所有用戶的歷史訪問偏好信息。

為了整合地理特征和序列信息，將上述GS和GV合并形成最終的無向簽到圖 G。具體來說，G是通過將屬于GV的邊添加到GS中來形成的。為簡單起見，根據(jù)LBSN 軌跡中的地理可互換的屬性省略了GV中的方向，即如果存在從位置i到位置j的移動轉移，那么從j到i的訪問模式對于另一個用戶來說是合理的。因此，簽到圖保存了空間圖的地理信息，同時保存了訪問圖中的用戶訪問偏好和簽到模式信息。此外，簽到圖的節(jié)點特征由簽到點的地理信息和POI 分類信息組成。

2.3 GNN 表示學習模塊

圖表示學習的目標是學習一種編碼映射函數(shù)，將圖節(jié)點映射為低維密集的向量，以保持圖的結構和屬性特征。GNN 是神經(jīng)網(wǎng)絡在圖結構數(shù)據(jù)上的一個延伸，現(xiàn)在已經(jīng)成為學習圖表示的強大模型。在本文任務中，基于深度圖互信息最大化(deep graph infomax,DGI)[17]算法實現(xiàn)GNN 模塊，來學習簽到圖中的節(jié)點嵌入表示。DGI 是一種無監(jiān)督的圖神經(jīng)網(wǎng)絡模型，通過最大化近鄰表示(patch representation)與對應的高階圖摘要(high-level summaries of graphs)之間的互信息(mutual information)來學習一個對比任務。DGI 能夠學習到包含圖全局結構信息的節(jié)點嵌入向量，用于分類、預測等下游任務。

在簽到圖G=(V,E,X,A)中，V代表簽到點的集合，E代表邊的集合，X代表簽到點特征的集合，A代表鄰接矩陣，由V和E得出。如圖3 所示，基于DGI 通過5 個步驟實現(xiàn)簽到圖的節(jié)點嵌入學習。

圖3 圖神經(jīng)網(wǎng)絡表示學習

1)利用簽到圖，通過擾動函數(shù)(corruption function)構建負例節(jié)點，即不改變鄰接矩陣，對特征矩陣進行行變換，改變節(jié)點的特征向量：，C表示擾動函數(shù)。

2)使用圖卷積網(wǎng)絡(graph convolutional nueral network,GCN)[18]學習正例節(jié)點的鄰近節(jié)點表示：H=ε(X,A)，ε表示由圖卷積網(wǎng)絡構成的編碼器。

4)利用正例節(jié)點的節(jié)點表示獲得包含圖全局信息的高階圖摘要，生成摘要向量s=R(H)，R表示獲得高階圖摘要的輸出函數(shù)。

5)最大化簽到點的鄰近節(jié)點表示(局部特征)與摘要向量(全局特征)之間的互信息，作為整個GNN 模塊的優(yōu)化目標。由于互信息計算困難，利用Infomax 準則[19]，將互信息計算等價轉化為關于聯(lián)合分布和邊緣分布乘積間的JS 散度計算(Jensen-Shannon divergence)，即最大化互信息等價于最大化JS 散度：

式中，N表示正例的數(shù)量；M表示負例的數(shù)量；D表示判別器，用于計算節(jié)點表示與摘要向量之間的互信息。如果該節(jié)點表示包含在摘要向量中，得到的分數(shù)更高。

利用GNN 模塊學習到簽到圖的所有節(jié)點嵌入表示H，按照分割后的軌跡序列組成軌跡簽到點嵌入表示向量z，就可以進行后續(xù)的分類任務。

2.4 軌跡用戶鏈接多分類器

該模塊中的分類器是一個基于RNN 的神經(jīng)網(wǎng)絡，包含一個雙向LSTM 和一個單層全連接網(wǎng)絡。LSTM 可以有效捕獲軌跡中高階復雜的序列信息，其結構包含一個存儲單元和3 個門結構：輸入門g(i)、輸出門g(o)和遺忘門g(f)。LSTM 在第t時刻的輸入為t時刻簽到點嵌入表示zt：

式中，W,U,V,b均為可學習的參數(shù)；σ表示sigmoid激活函數(shù)；ct表示當前單元的狀態(tài)，它通過以下方式獲得門的組合：

式中，“ ⊙”表示矩陣對應元素相乘，最終的候選狀態(tài)mt為：

為了增強RNN 的記憶能力，使用由前向LSTM與后向LSTM 組合而成的BiLSTM，以利用來自正反兩個方向的上下文信息。在第t步時，可以得到軌跡嵌入qt：

式中，mt和是BiLSTM 的兩個輸出。軌跡向量q用最后時刻的qt來表示。

分類器還包含了一層的全連接網(wǎng)絡，用于輸出軌跡對應用戶(標簽)的概率分布。將軌跡向量q輸入至全連接網(wǎng)絡中，最后利用softmax 函數(shù)映射成C維的向量，得到分類輸出。其中C表示用戶數(shù)量，softmax 函數(shù)為歸一化指數(shù)函數(shù)：

式中，y為該軌跡屬于每個用戶的概率。在模型訓練中，將模型輸出的概率分布和真實分布(onehot 向量)之間的交叉熵作為模型的損失函數(shù)并進行訓練。本文模型GTUL 的預測算法如下。

3 實驗結果與分析

3.1 數(shù)據(jù)集

Gowalla[20]是一個基于LBSN 網(wǎng)站的數(shù)據(jù)集，該數(shù)據(jù)集收集了2009 年2 月?2010 年10 月期間1 萬多個用戶的軌跡，包括詳細的時間戳和每次簽到點的地理坐標。Foursquare[21]包括從Foursquare網(wǎng)站收集的2012 年4 月?2013 年2 月期間大約10個月的簽到數(shù)據(jù)。簽到數(shù)據(jù)包含了簽到點的地理位置坐標、簽到時間和簽到點的類別屬性，以及簽到用戶的個人應用ID。

3.2 實驗設置

本文的實驗模型都基于PyTorch 深度學習框架來實現(xiàn)，使用了一塊GTX1070GPU 來加速計算。實驗數(shù)據(jù)集設置遵循文獻[4,6]中的設置。實驗從Gowalla 中隨機選擇了201 個用戶及其生成的軌跡，從Foursquare 中隨機選擇了300 個用戶和相應軌跡進行評估。具體的數(shù)據(jù)集設置如表1 所示。

表1 實驗中使用的數(shù)據(jù)集統(tǒng)計

在實驗中，需要分開訓練GNN 模型和多分類器模型。其中，GNN 模塊的具體參數(shù)設置如表2所示，多分類器模塊在訓練中使用Adam 優(yōu)化器(adaptive moment estimation)，多分類器學習率設置為0.0016，批處理塊大小為16，全局迭代了50 次。

表2 GNN 模塊參數(shù)設置

3.3 評價指標

本文使用ACC@K、macro-P、macro-R和macro-F1 作為評價指標來評價TUL 任務的性能。ACC@K表示用戶軌跡分類的準確性，如果生成軌跡T的用戶u(T)位于預測的top-K用戶集UK(T)內，則認為是正確的。可表示為：

式中，ACC@K表示軌跡正確分類到生成該軌跡的用戶的比率。macro-F1 是所有類的macro-P和macro-R的調和平均值。三者的計算方式為：

式中，i表示在第i個用戶標簽上的評價指標；R為召回率(recall)；P為精準率(precision)；TP 為正類用戶標簽被模型預測為正類的樣本數(shù)量；FN 為正類用戶標簽被模型預測為負類的樣本數(shù)量；FP為負類用戶標簽被模型預測為正類的樣本數(shù)量。

3.4 相關模型對比

將GTUL 與TUL 相關模型進行比較：

1)TULER[4]是第一個TUL 解決方案，它使用各種RNN 模型對用戶移動規(guī)律進行建模。

2)HTULER[6]是一個分層的TUL 模型，由3 個變體組成，包括HTULER-LSTM、HTULER-Bi 和HTULER-GRU。

3)TULVAE[6]以半監(jiān)督學習方式學習軌跡分布和用戶移動規(guī)律，該算法利用VAE 來學習RNN 中隱藏狀態(tài)的隨機隱變量的層次語義信息。

4)TGAN[7]是一種軌跡增強方法，利用條件對抗網(wǎng)絡來學習基本軌跡分布并生成綜合軌跡。原始軌跡數(shù)據(jù)將與增廣數(shù)據(jù)一起進行訓練，以解決數(shù)據(jù)的稀疏性問題。

5)STULIG[8]是最新的TUL 模型，它使用分層隱因子擴展了TULVAE。利用合成軌跡豐富了訓練數(shù)據(jù)，同時通過聯(lián)合訓練提高了TUL 的性能。

3.5 實驗結果分析

表3 展示了GTUL 與其他基準算法在兩個真實數(shù)據(jù)集上的性能比較。結果表明，GTUL 模型在各種指標中均取得了最好的性能，并且在用戶軌跡辨別的直接指標上有了明顯的提升，說明GTUL 可以有效提取歷史軌跡信息，建模用戶的移動規(guī)律。

除了模型的優(yōu)越性之外，本文還有以下發(fā)現(xiàn)。首先，像TULER 和HTULER 這樣的確定性分類模型表現(xiàn)整體不佳。這些模型使用簡單的RNN 模型來建模用戶軌跡，極大地依賴歷史軌跡的數(shù)量和質量，所以它們不足以從稀疏的訓練數(shù)據(jù)中捕捉復雜的用戶移動模式。這一結果表明，在LBSNs 中，用戶軌跡分類并不是一項簡單的任務，因為對于大多數(shù)用戶來說，許多必要的用戶移動模式因為簽到行為過少而無法發(fā)掘。由此可見，提高解決TUL 問題的效果還需要借助更多的數(shù)據(jù)處理技術，發(fā)掘更多的時空信息，以解決稀疏訓練數(shù)據(jù)帶來的問題。

另一方面，與傳統(tǒng)的基于RNN 的模型相比，TULVAE、TGAN 和STULIG 有效提高了TUL 的性能。這些方法依靠深度生成模型，利用合成軌跡來增強訓練數(shù)據(jù)。TULVAE 使用具有隨機隱變量的生成架構來學習用戶的移動規(guī)律。TGAN 使用從分布中采樣生成的軌跡來增強訓練數(shù)據(jù)，并且通過對抗學習的方式對模型進行訓練。STULIG 則利用合成軌跡增強訓練數(shù)據(jù)，并使用分層隱因子擴展生成架構。這些模型均取得了一定的效果，但它們都依賴于深層生成技術來推斷潛在的移動分布和估計潛在因素，通常計算效率低。更重要的是，由于數(shù)據(jù)稀疏性問題，生成模型可能引入關于數(shù)據(jù)分布的額外偏差。相比上述方法，本文提出的解決方案更簡潔，并省去了后驗分布推理的開銷。GTUL 算法基于用戶歷史軌跡構建簽到圖，使用圖神經(jīng)網(wǎng)絡學習簽到點的向量表示，使簽到點的表示包含更多的位置信息和時間信息，成功提高了軌跡用戶辨別的準確度。

3.6 訓練效率比較

GTUL 的另一主要優(yōu)點是訓練效率高。為了證明這一點，本文對比了所有方法的訓練時間，并將結果展示在表4 中。在所有方法中，TULVAE，TGAN 和STULIG 等生成模型為了生成新的合成軌跡需要花費大量計算開銷進行數(shù)據(jù)基礎分布的估算，無法迅速收斂。在這些生成模型中，基于VAE的模型更為昂貴。它們在推理期間計算每個時期每個軌跡的發(fā)生概率，其時間復雜度隨著用戶數(shù)量的增加而顯著增加。用戶越多，每個時期的迭代就越多，會產(chǎn)生巨大的計算成本。與這些方法相比，本文提出的GTUL 模型結構簡單清晰，不需要進行潛在因素推斷。GTUL 構建了信息豐富的簽到圖，利用GNN 模塊進行自監(jiān)督對比學習，可以高效無監(jiān)督地學習到包含地理位置信息和用戶訪問偏好信息的簽到點嵌入表示。因此GTUL 省去了生成模型的軌跡合成過程，在提取有用信息的同時極大地減少了計算成本，訓練時間大大縮短。

表4 訓練時間對比h

3.7 模塊性能分析

為了探究簽到圖包含的時空信息的有效性，增強本文方法的可解釋性，本文設計了一個模塊對比實驗。具體而言，分別只利用空間圖和訪問圖學習簽到點的嵌入表示，替換GTUL 中原有的簽到圖節(jié)點嵌入，得到兩個新的方法分別表示為GTULSGE和GTULVGE。將GTUL、GTULSGE 和GTULVGE一起對比，得到的結果如圖4 所示，其中value 表示各項評價指標的具體數(shù)值。

圖4 空間圖和訪問圖對TUL 性能的影響

根據(jù)圖4 可知，GTUL 的性能優(yōu)于GTULSGE和GTULVGE，說明空間信息和訪問意圖都對解決TUL 問題有重要作用，基于GNN 的簽到點嵌入表示成功獲取了這些關鍵信息。此外，GTULSGE的性能明顯低于GTUL 和GTULVGE，說明只利用地理位置信息，不考慮用戶訪問習慣，不足以學習到有代表性的簽到點嵌入表示。

4 結束語

本文提出了一種新的基于圖神經(jīng)網(wǎng)絡的用戶軌跡分類模型。該模型實現(xiàn)一種通過軌跡數(shù)據(jù)生成簽到圖的通用構造方法，對與用戶簽到位置和時間移動意圖相關的時空特征進行建模；利用圖神經(jīng)網(wǎng)絡獲取高階時空信息，發(fā)掘所構造的簽到圖中隱含的簽到之間的轉換模式。在真實移動應用的用戶軌跡數(shù)據(jù)上的實驗結果表明，本文模型能夠有效解決軌跡數(shù)據(jù)的稀疏問題和提高用戶移動模式的學習效率，高效區(qū)分不同用戶的軌跡，提高了TUL 任務的性能。未來的研究工作將考慮利用軌跡上下文POI屬性來提高模型的效率。另一種可能的擴展是引入額外的信息，如考慮用戶的交通方式、天氣或節(jié)假日等信息以提高模型的綜合預測能力。