基于圖卷積神經網絡的位置語義推斷

吳睿智，朱大勇，王春雨，秦 科

(電子科技大學計算機科學與工程學院 成都 611731)

隨著基于位置的社交網絡(LBSNs)的發展，用戶能夠在簽到位置發布評論分享自己的感受。理解用戶活動的語義對分析用戶行為起著重要的作用[1-2]。如，一位用戶發布一條評論“愿你在天堂安好！”。如果這條評論附加一個醫院的位置語義，將有利于更好地理解用戶的悲傷體驗。同時，位置語義對城市生活中一些基于位置的服務如位置檢索和位置推薦有所幫助[3-4]。如，當用戶到達一個新城市時，用戶將搜索目的地附近的酒店或餐館等語義信息。智能手機中的應用程序，如城市旅行中的導航，都依賴于位置語義[5-6]。位置語義對于跨越網絡和現實環境之間的鴻溝起著重要的作用。然而，據統計，至少有30%的位置在LBSNs 中缺乏語義標簽[7]。另一方面，盡管地圖服務提供商的業務增長迅速，但位置語義標簽查詢服務的成本卻很高。谷歌提供語義搜索服務，每1000 個地點收費超過千元。

位置語義研究一直是軌跡數據挖掘研究中的熱點，位置語義推斷也得到了許多研究者的廣泛關注。一般的研究思路為通過手工提取用戶簽到活動中的時空模式，或通過手工定義位置的時空特征，利用分類器推斷位置語義。如文獻[7]提取特定位置的顯式模式(explicit patterns, EP)和相似位置之間的隱式關聯(implicit relatedness, IR)?；贓P 和IR 特征，訓練支持向量機分類器推斷位置語義。文獻[8]提出一種新的位置特征，稱為相似用戶模式(similar user pattern, SUP)，同時考慮個人用戶活動的規律性，以及不同用戶之間的相似性。提取SUP 后，利用SUP 度量位置間的相似性，訓練分類器學習每個未標注語義的位置的語義標簽。文獻[9]提出一種基于圖表征學習的位置語義推斷算法，稱為預測位置嵌入(predictive place embedded, PPE)。PPE 首先構造用戶?標簽二部圖，通過用戶?標簽二部圖獲得用戶向量表征。優化每個位置作為其簽到用戶向量的質心嵌入表征的方式，將用戶相似度轉換為位置相似度，獲取位置語義標簽。

現有位置語義推理算法目標是提取簽到活動中所隱含的位置時空特征或用戶簽到時空模式，并將語義推理轉化為分類問題。但度量位置間的相似度或提取長效穩定的用戶簽到模式是一項困難的任務。為了克服這種局限性，本文提出一種基于圖卷積神經網絡的位置語義推理框架(semantic inferences with graph convolutional networks, SI-GCN)。 SIGCN 通過無監督的方式提取位置的時空特征，利用圖卷積神經網絡(graph convolutional networks,GCN[10])推斷位置的語義類別標簽。具體來說，SIGCN 通過node2vec[11-12]和變分自編碼器(variational autoencoder, VAE[13])自動提取位置時空特征。然后，SI-GCN 利用圖卷積網絡來捕獲用戶?位置訪問二部圖中的高階訪問關系，同時利用自注意力機制來學習用戶?位置訪問二部圖中相鄰節點的不同貢獻。實驗結果表明，相較于傳統的位置語義推斷算法，SI-GCN 取得了更好的位置語義推斷結果。

1 基于GCN 的語義推斷模型

圖1 為SI-GCN 的整體框架，從左至右分別是時空特征提取、用戶?位置訪問二部圖構建、利用兩層GCN 進行語義推理。

圖1 SI-GCN 框架圖

1.1 時空特征提取

位置的時空特征是位置社交網絡中位置語義研究的關鍵問題。SI-GCN 利用無監督學習的方式提取位置的空間結構信息和時間信息，其基本思想為在城市規劃中，具有相同的功能位置(即相同的語義類別)在城市中具有近似的空間結構。因此，提取空間特征主要目標是保留位置在地理空間中的結構特征。由于用戶與地理位置不同，用戶沒有直接的經緯度，SI-GCN 首先計算出用戶訪問頻率最高的3 個地理位置的平均經緯度作為用戶的地理坐標，為了構建地理空間網絡 Nsp，SI-GCN 將用戶的坐標(ulon,ulat)映射到城市中，利用用戶坐標和位置坐標，建立城市地理空間網絡 Nsp。具體如下：計算城市中節點之間的距離，如果距離小于δ，則將兩個節點連接為邊，反之亦然。

在完成地理空間網絡Nsp的構建后，使用node2vec 算法以無監督的方式學習用戶和位置的空間特征 fsp?？臻g特征學習希望通過最大化一個節點與相鄰節點同時出現的概率的方式保留位置的空間結構信息，即最大化Pr(N(v)|fsp(v))。定義 V 是 Nsp中的節點集合， v是 V的一個節點v ∈V，N(v)是v的鄰居?？臻g特征提取的目標函數表示為：

提取時間特征的目標是學習用戶或位置簽到活動時間模式的特征向量。本研究中，時間模式定義為一個7×24 的時間矩陣來計算用戶或位置訪問頻次。如，如果用戶A 在周一上午9:00?10:00 訪問位置B，則用戶的時間矩陣的對應元素增加1。位置的訪問時間矩陣計算方法與用戶方法一致。

圖2 為利用變分自編碼器提取時間特征的過程，利用變分自編碼器無監督學習時間矩陣的特征向量。

圖2 變分自編碼器提取時間特征的圖示

具體如下：時間矩陣作為編碼器層的輸入向量進行編碼；重參數化層是獲取編碼網絡輸出向量的均值向量和方差向量；隱層向量是由重參數化層采樣恢復的時間矩陣的隱向量表征；最后，解碼器層通過隱向量重構時間矩陣。VAE 的損失函數表示為：

1.2 位置語義推斷

為了分析簽到活動和位置語義之間的關系，SI-GCN 構建一個用戶?位置訪問二部圖，記作Nc。如圖1 所示，二部圖的一側是用戶u，另一側是位置l。如果用戶ui訪問過位置li，則eij=1，反之亦然：

SI-GCN 采用文獻[14]中提出的具有LeakyRelu激活函數的前饋神經層a：

式中，||表示連接操作。完成鄰居節點注意力系數計算后，利用非線性激活函數 φ，每個節點的輸出為：

先前的研究表明疊加圖卷積層能夠探索圖中節點的高階信息。因此，SI-GCN 引入兩層GCN 來挖掘簽到活動中的高階信息。第一層探索節點的鄰居節點的影響，如在 Nc中兩個朋友共同訪問的位置或用戶訪問的兩個位置。第二層旨在獲取 Nc中的二階信息，例如多個好友共同訪問同一個位置。引入兩層GCN 能夠更好的捕獲用戶簽到活動中的高階信息。在用戶?位置訪問二部圖 Nc中，鄰接矩陣為A，根據GCN 的傳播公式，SI-GCN 第一層的輸出為：

式中， W2、 W3是網絡參數。由于用戶沒有語義標簽，對于用戶的語義標簽，將用戶訪問次數最多的位置的語義標簽視為用戶的語義標簽。最終，SIGCN 的損失函數為：

式中， C 是語義類別集合； Ym是訓練集中具有真實語義類別標簽的節點集合； Ymc是 Ym中有真實語義類別的節點集合； zmc是SI-GCN 預測的語義類別。SI-GCN 采用ADAM 算法學習網絡參數。最后，SI-GCN 的完整過程總結如下：

3)對簽到數據集中的每一個用戶，計算每個用戶和位置的時間矩陣，采用VAE 算法計算時間特征 fte；

4)由空間特征 fsp和時間特征 fte組成時空特征：fst=[fsp||fte]；

5)由式(3)構造用戶?地理位置訪問二部圖Nc。利用兩層GCN 模型推斷位置語義，利用ADAM 優化方法訓練網絡參數，推斷地理位置語義標簽結果。

2 實驗分析

為了全面評估SI-GCN 的性能，實驗利用來自Foursquare 的兩個真實的簽到數據集進行實驗，驗證SI-GCN 的語義推斷性能。同時，將SI-GCN 與3 種基準算法進行比較，分別是SAP[7]、SUP[8]和PPE[9]。SI-GCN 是在PyTorch 框架下實現的，所有的實驗都是在一臺4 核(3.5 GHz CPU) 32 GB 內存的服務器上進行的，使用雙NVIDIA GPU (8 GB顯存)。

2.1 實驗設置

實驗采用FourSquare 收集的紐約市(NYC)和東京市(Tokyo)的簽到數據，時間從2012 年4 月12 日?2013 年2 月16 日[6]。每個簽到記錄包括用戶ID、位置ID、位置類別ID、位置語義類別、緯度、經度、與UTC 標準時間的偏差和UTC 標準時間。

由于部分位置簽到記錄過少，無法有效提取位置的時間特征。因此，在數據預處理中，刪除簽到記錄少于10 條的位置。表1 列出紐約市和東京市的簽到數據集的統計信息。實驗采取兩種語義標簽策略評估SI-GCN 的語義推斷性能：1)將FourSquare數據集的語義標簽分為9 大類，包括餐館、酒店、景點、交通樞紐、商店、教育、娛樂、宗教、公司等類別；2)從原有的FourSquare 數據集中選出兩個新的子數據集，其中僅包含按簽到次數排名前20 位的位置語義類別。為了評估SI-GCN 的綜合性能，實驗從準確性(Acc)、微觀F1 值(microF1)和宏觀F1 值(macroF1)3 個評價指標對SI-GCN 的性能進行評價。為了評價SI-GCN 的性能，實驗中設置不同比例的測試數據：20%、30%、40%、50%。SI-GCN 的語義性能如表2 所示。

表1 實驗所用數據集統計信息

表2 SI-GCN 在NYC 和Tokyo 兩個數據集的實驗結果

2.2 實驗結果

表2 為SI-GCN 在紐約市和東京市兩個簽到數據集的實驗結果。從表2 中得到以下觀察結果：1)更多的數據有利于SI-GCN 取得更好的實驗結果，能夠從更多的訓練數據中更好地捕捉到用戶簽到活動的時空特征與用戶?位置訪問二部圖的拓撲結構之間的關系，從而獲得更好的性能；2)數據分布不均衡對模型性能有負面影響。如紐約和東京的餐館標簽分別為30.8%和27.1%，SI-GCN 準確率較高，但microF1 和macroF1 值較低；3) 10 個大類別的語義推斷的性能優于前20 個類別的性能，原因是更多的語義標簽導致模型性能的下降；4)SI-GCN 在紐約集的結果優于東京數據集。分析數據集發現：紐約市的每個用戶有4.74 個訪問過的位置，而東京的每個用戶只有3.43 個訪問位置。盡管東京的用戶有更高的訪問頻率(紐約市每名用戶有136.6 條簽到記錄，東京每名用戶有195.2 條簽到記錄)，但SI-GCN 仍能夠從更多訪問位置中捕獲用戶的偏好。

實驗對比僅采用空間特征的SI-GCN-S 和僅采用時間特征SI-GCN-T 驗證空間、時間特征對模型性能的影響。表3 為兩種模型變體在東京市數據集的實驗結果。從準確率評價指標分析，空間特征或時間特征對模型的影響基本相同。從microF1 和macroF1 結果分析，尤其是當訓練數據較少時，SIGCN-T 在兩個數據集上的結果均顯著低于SIGCN-S，說明缺失空間特征對模型性能影響比時間特征大。

表3 SI-GCN 模型變體在Tokyo 簽到數據集的結果

圖3 為SI-GCN 與3 種基準模型SUP、PPE、SAP 在紐約市簽到數據集的對比實驗結果。從中能夠得出以下觀察結果：1) SI-GCN 優于其他3 種基準算法；2) PPE 的性能優于SUP 和SAP，SUP 的性能接近SAP。具體分析如下：首先，SI-GCN 利用node2vec 和VAE 學習空間結構特征和時間特征，而不是手工提取時空模式。其次，SI-GCN 采用圖卷積神經網絡和自注意力機制，在簽到活動中能夠有效區分來自用戶?位置訪問二部圖中鄰居節點的不同貢獻和高階信息。因此，本文所提出的SI-GCN 比基準算法具有更好的位置語義推理性能。

圖3 SI-GCN 與3 種基準算法在NYC 數據集對比結果

3 結 束 語

本文提出一種基于圖卷積神經網絡的位置語義推斷模型。與現有的方法不同，SI-GCN 避免手工提取簽到活動中時空特征的局限。同時，SI-GCN引入圖卷積神經網絡獲取簽到活動中的高階信息。此外，為了區分用戶?位置訪問二部圖中不同鄰居節點的影響，引入自注意力機制計算鄰居節點的影響力大小。SI-GCN 在兩個簽到數據集上的實驗結果表明，SI-GCN 優于現有方法。