地理位置和時間感知的表示學習框架

周俊，張志強，曹月恬，鄭小林

（1. 浙江大學 計算機科學與技術學院， 浙江 杭州 310007; 2. 螞蟻集團， 浙江 杭州 310013）

近年來，許多研究者致力于使用表示學習的手段來學習用戶表征，刻畫用戶的歷史行為，并將其用于各種各樣的在線服務中，比如商品推薦、優惠券投放、在線廣告等。但現有的方法大多聚焦于對用戶歷史的點擊/購買商品序列建模，無法直接應用于具有強時空語義的實際場景中(如美團、餓了么等本地生活平臺)。在這樣的場景中，要同時解決“When”、“Where”和“What”的問題，即在特定的時間、特定的地點為用戶推薦合適的商品。為此，需要學習一個好的用戶表征，它不僅僅能捕獲用戶在點擊/購買序列上表現的興趣偏好，更要刻畫這些興趣偏好隨著時間和位置的演化特征。本文的核心研究任務是如何在時間和空間的維度上學習用戶的統一表征，刻畫用戶行為的時空語義。

在時間建模上，考慮到行為稀疏性和用戶關聯性，本文主要在用戶?商品交互(如購買)的時序圖上進行用戶表示學習。國外針對時序比較成熟的表示學習方法主要有3類：1) 基于隨機游走的方法[1-2]直接將時序信息融合到隨機游走序列中，并通過經典的skip-gram方法學習動態表征。但這類方法忽略了節點和邊上的豐富信息，并無法進行歸納學習。2) 基于時間切片的方法[3-4]先在不同的時間切片上進行表示學習，然后通過神經網絡將不同切片上的表示融合為最終的節點表示。這類方法忽略了每個時間切片內的動態性，一定程度上損害了節點關系隨時間演化的特性；3) 基于連續時間的方法[5-6]嘗試在連續時間上進行時間序列或時序圖的表示學習。但是此類方法大多仍然無法進行歸納學習。更重要的是，它們在進行時間編碼的時候忽略了時序圖上節點間的交互和時間維度上的上下文信息及其影響。

在空間建模上，如何對地理位置進行編碼至關重要。當前的表征方法包括使用geohash網格信息、興趣點(point of interest,POI)或興趣面(area of interest,AOI)的one-hot編碼，以及使用經緯度信息等。但是這些方式都有自己的缺點：1) geohash網格信息或者POI信息雖然可以精確區分不同的地點，但是由于數量太大，做one-hot編碼特征會導致模型參數爆炸。另外geohash網格或POI忽視了地理位置的遠近關系信息，不利于模型使用。2) AOI/POI的數量在幾百萬左右，規模不算很大，但是很多AOI/POI覆蓋的面積很大，這樣就不能區分其中包含的不同位置實體，另外目前AOI/POI的覆蓋率也不是很高；3) 直接經緯度信息雖然避免了one-hot編碼特征維度過大的問題，也保持了地理位置的遠近關系，但是由于經度和緯度值的微小變化，實際位置就會偏離很遠，模型很難使用這類特征。

針對以上不足，本文的目標是開發一個統一的用戶表示框架?GTRL (geography and time aware representation learning)，可以同時在時間和空間維度上對用戶的歷史行為軌跡進行聯合建模。

在時間信息建模上，首先，GTRL通過Mercer理論[7]來實現函數式的時間編碼，將時間戳(時間差)映射到高維空間中，并保存節點的時序性。其次，設計了連續時間和上下文感知的圖注意力網絡(C2GAT)，一個既可以利用圖上高階結構信息也可以在連續時間上刻畫節點局部上下文的、全新的、歸納式的圖表示學習模型。

在空間信息建模上，為GTRL設計了一種新穎的地理位置編碼器?GeoEncoder，以更高效簡潔的方式將每個地理位置映射為固定長度的字符串。基于經典的n-gram技術，GTRL可以在更加細粒度的視角上對位置信息進行刻畫。最后，依賴新興的注意力機制對用戶的歷史位置軌跡進行了深度建模，最終生成了用戶的地理偏好表征。

在模型優化方面，GTRL致力于同時解決上述的“When”、“Where”和“What”3個問題，因此為GTRL設計了統一的聯合優化方案。值得注意的是，在優化時間上，該方案引入了用戶行為中的時間間隔信息，用以刻畫行為的周期性、偏好的衰減性等一系列細粒度特征。

最后，本文在公開數據集和工業數據集上設計了大量的實驗，一方面驗證了GTRL的性能可以超過當前學術界最優的基線模型，另一方面證明了GTRL在實際業務場景中的優勢。

1 整體框架

本文提出的GTRL整體算法框架如圖1所示，框架會利用用戶的歷史行為進行建模，包括歷史交互的商品(如用戶購買過的商品)，交互時間以及交互發生的地理位置(購買的商鋪所在的地理位置)。框架的兩個核心模塊共同支持時空表示學習：1) 時序信息表示模塊包含函數式的時間編碼及連續時間和上下文感知的圖注意力網絡，主要用于學習時序圖上的用戶表示；2) 空間信息表示模塊包含層次化的地理位置編碼和深度用戶軌跡建模子模塊，主要對用戶歷史位置偏好表征的生成。為了統一解決時空語義場景的通用問題(即“When”、“Where”和“What”3個問題)，設計了統一的且可解耦的目標函數來同時優化交互預測、時間間隔預測以及地理位置預測。

圖1 GTRL框架的整體結構Fig.1 Overall architecture of GTRL framework

2 時序信息建模

為了更好地克服行為稀疏性和捕獲用戶行為的高階關聯性，本文從圖的角度出發進行時序信息的建模，并設計了連續時間和上下文感知的時序圖學習方法，主要分為兩個部分：1) 為了避免離散時間建模帶來的信息損失，GTRL嘗試用函數式的時間編碼技術將時間戳映射到連續可微的向量空間上更好地保存時序圖上的動態性；2) 在最近新興的圖神經網絡結構上，融合時間編碼，設計了連續時間和上下文感知的注意力機制，可在圖上按時間順序選取重要的鄰居，并同時考慮不同鄰居在時間上的相互影響。

2.1 函數式的時間編碼

函數式時間編碼的目的是找到一個從時間域到d維向量空間的映射 Φ (·)。具體地，考慮任意兩個時間戳t1,t2∈T，需要關心的是如何學習這兩個時間間隔之間的關系模式，可以表示成它們對應的時間編碼的內積，即 〈 Φ(t1),Φ(t2)〉。由此，可以將上述的時序模式進一步形式化成具有平移不變性的核函數 K，且其映射函數為 Φ (·)。

為了學習上述的時序核函數及其映射函數，在Mercer理論的啟發下，可以將該映射函數定義為

經驗上來說，時序模式可以被一系列周期核函數刻畫，參照文獻[8]介紹的定理，以 ω 為頻率的映射函數 Φ (·) 可以進一步被形式化為

值得注意的是，這樣的時間編碼是節點無關的。換句話說，由于時間編碼和節點不相關，會導致相同時間間隔下的任意兩個節點的時間編碼都是一樣的。但在具體的應用場景中，如個性化推薦，用戶在過去同一時間上購買的兩個不同的商品，對當下用戶興趣的影響是不同的。如一天前喝過咖啡今天很可能會繼續喝，但一天前吃過火鍋今天再吃的可能性就比較低了。因此，這樣的節點無關的時間編碼不適合用于后續圖神經網絡來進行時序圖表示。給定一個特定的節點v，可以進一步將該節點的時間編碼定義為

式中ci(u):Rd→R,i=1,2,··· 是一系列節點相關的映射函數，用來計算傅里葉系數。由于多層感知機對復雜交互的優秀建模能力，在實驗中將其用于實現ci(u)，并強制感知機的最后一層輸出為正數，以此來滿足Mercer理論的內在特性。

2.2 連續時間和上下文感知的圖注意力網絡

循環聚合器在序列上下文上應用復雜的LSTM(long short-term memory)結構來賦予C2GAT強大的表達能力。

卷積聚合器使用了卷積操作來保證C2GAT可以擴展到大規模數據集上。

3 空間信息建模

空間信息建模，即建模用戶在空間上的軌跡信息，是對用戶時空行為刻畫的另外一個主要模塊。具體來說，空間軌跡一方面可以在空間上區別人與人之間關系，刻畫用戶的空間遷移性，從而實現更好的用戶表示；另一方面，它也可以描述人與物(服務、權益和店鋪等)的關系，增強模型的預測能力。為此，本文設計了層級化的地理編碼和深度的歷史軌跡建模來實現這一目標，如圖2所示。

圖2 空間信息建模示意Fig.2 Illustration of geography aware modelling

3.1 層級化的地理編碼

為了避免傳統地理位置編碼(geohash網格、POI或者AOI的one-hot編碼以及經緯度編碼等)的不足，設計的地理位置編碼器(GeoEncoder)參考了谷歌地圖和必應地圖中廣泛使用的Tile Map System，將全地圖等分為4塊，分別標為0、1、2、3。然后將標號為“0”的地塊(Tile)繼續等分為4小塊，分別標為00、01、02、03，這4小塊有共同的前綴：“0”，也就是它們上層那個地塊的編號。其他標號為“1”、“2”、“3”的地塊進行同樣的劃分操作。這樣遞歸地將地圖不斷劃分下去，直到最小地塊滿足要求的進度為止。采樣這種地理編碼方式，中國地圖，考慮最小地塊長度為10米，只需要長度為19的序列編碼就可以覆蓋全國所有位置。這樣產出的編碼具有很好的性質：給定任意兩個地塊，它們的共同前綴越短，它們距離越遠；反之則越近。圖3具體展示了對位置“杭州市?西湖區?天目里”的層級化地理編碼。

圖3 層次化地理位置編碼示意(以“杭州市?西湖區?天目里”為例)Fig.3 Illustration of hierarchical location encoding(take “Hangzhou–Xihu–Tianmuli” as an example)

但是并不能直接使用這個編碼作為ID特征。進一步地，參考2020 KDD的工作[8]，可以對這個編碼做n-gram處理(一般取n=6)轉換成序列的形式。具體來說，給定編碼“120 220 011 012 000 332”做6-gram處理之后會變為[‘120 220’, ‘202 200’,‘022001’, ‘220 011’, ‘200 110’, ‘001101’, ‘011012’,‘110 120’, ‘101 200’, ‘012000', ‘120 003’, ‘200 033’,‘000332’]的序列，其中單詞量為4 096(46)。

一個地理位置基于GeoEncoder +n-gram做序列編碼之后，該序列從左到右逐步刻畫了更細粒度的位置信息。可以類比于從國家粒度，逐步精細到地區、省、市、縣等。不同的是，GeoEncoder +n-gram的序列編碼方式還可以描述相對位置信息。考慮n=1的最簡單情況，當一個序列編碼的第k個位置為0、1、2和3時，表示它在當前區域的西北、東北、西南和東南區域。當n取值變大，序列編碼則可以表示更復雜的相對位置信息。為刻畫上述序列編碼層級遞進的性質，GTRL的地理編碼模塊使用LSTM模型來建模序列編碼得到每個地理位置的低維表征。

3.2 深度的歷史軌跡建模

4 模型學習

相比于傳統的時序點過程，GTRL使用了一種強度自由的形式來建模用戶的時間間隔，可以更好地適應復雜的真實應用場景。由于神經網絡強大的擬合能力，GTRL將其作為累積強度函數是實現基礎，整體的公式為

為了解決時間t、位置g、 商品v的聯合預測，GTRL通過如下的聯合分布來估計：

p(v,g,t|u)=p(v|u)·p(g|u)·p(t,|u,v)

式中：下一次交互預測p(v|u) 與下一次位置預測p(g|u) 分別由以hu(t) 為輸入的多層感知機器得到；而下一次交互間隔預測p(t,|u,v) 由時序點過程支持。由于商品和位置量級很大，GTRL使用了隨機負采樣的方式來進行近似計算。最后，根據極大似然估計的策略，最終的損失函數為

5 實驗分析

5.1 公開數據集上的有效性實驗

首先，本文分別在4個公開數據集(Reddit、Wikipedia、MOOC和LastFM)上進行(推導式/歸納式)鏈路預測和節點分類任務，來驗證GTRL中的時序信息建模模塊(即C2GAT)的有效性。4個數據集的詳細統計信息如表1所示。

表1 4個公開數據集的統計信息Table 1 Statistics of four public datasets

在實驗中，選取了9個經典的基準方法，大致可以分為3類：1) 基于深度遞歸網絡的方法：Time-LSTM[10]和Jodie[11]；2)靜態的圖神經網絡方法：GraphSAGE[12]和GAT[13]；3) 時序圖神經網絡方法：CTDNE[14]，M2DNE[15]、GCRN[16]、Graph-SAGE-T和GAT-T和TGAT[5]。

本文將C2GAT與上述的9個基準方法在(推導式/歸納式)鏈路預測和節點分類任務上的性能對比實驗結果分別展示在表2和表3中。從表2、3中可以得出如下兩點結論：

表2 公開數據集上(推導式/歸納式)鏈路預測任務的性能比較Table 2 Performance comparison (AUC) for (transductive / inductive) link prediction task on public datasets

表3 公開數據集上節點分類任務的性能比較(AUC)Table 3 Performance comparison (AUC) for node classification task on public datasets

1) GTRL中集成的C2GAT模型同時在鏈路預測和節點分類任務上都一致且明顯優于其余基準模型，驗證了C2GAT的有效性。這得益于C2GAT使用了一種更加有效的方式來捕獲圖上的動態性，并同時利用高階結構信息和局部序列式的上下信息。

2) 在這些對比方法中，多數情況下，時序圖模型的性能優于靜態圖模型優于深度序列模型。這證明了動態性、高階結構以及節點/邊特征對于時序圖表示學習的重要性。

5.2 工業數據集上的實驗

首先在支付寶首頁的本地生活場景進行了一系列關于時間維度的實驗，選取了外賣(“餓了么”服務)、旅游(“飛豬”服務)和欄目排序這3個具有強時間語義的數據集，具體的數據集統計信息見表4。

表4 3個工業數據集的統計信息Table 4 Statistics of four industrial datasets

考慮到數據規模的量級，本文針對性地選取了一系列代表性的基準方法，如基于特征的DeepFM[17]模型、基于序列的GRU4Rec[18]、DIN[11]、SASRec[20]，以及基于興趣演化的DIEN[21]和Time-LSTM[10]模型。詳細的性能比較如表5所示。可以發現：在3個實際的場景數據集上，本文提出的方法對比最優的基準方法可以帶來0.12%～1.71%的提升，驗證了該方法在實際場景中捕獲時間語義的有效性。

表5 工業數據集的性能比較Table 5 Performance comparison on industrial datasets %

進一步，將更加顯式地展示GTRL在時間間隔預測上的有效性。因此，本文在支付寶/本地生活的券核銷預估中應用了GTRL。首先對比線上最優的基準方法(MMoE[22])，GTRL在核銷率上可以帶來4.23%的提升。其次，展示了這個任務中三類券的真實核銷量?時間分布(藍色柱狀圖)以及GTRL對券核銷時間分布的估計(紅色實線)，如圖4所示。可以發現，GTRL的預測與真實的核銷分布基本吻合，也反映出了不同類型券核銷的時間周期性：1) 餐飲券：領券后一般都是盡快核銷，核銷量隨時間呈明顯衰減趨勢；2) 電影券：領券后盡快核銷(現領現買)，領券第2天核銷(1天后看電影)；3) 出行券：時間衰減不明顯，根據實際出行需求進行核銷，呈現天周期。

圖4 時間間隔預測的案例學習Fig.4 Case study for time interval prediction

除了預測時間任務外，GTRL也可以進行空間地理信息的建模[23-25]。將GTRL應用于建模用戶歷史線下交易的空間軌跡。首先，本文將學習到的用戶空間表征進行可視化，如圖5所示。

圖5 GTRL-G學習到的用戶表示示意Fig.5 Illustration of user embeddings learned by GTRL-G

從圖5中，可以發現：1) 每個城市聚簇明顯，北京?天津、佛山?廣州、蘇州?上海、成都?重慶4組城市對也呈現聚簇狀態，其中成都?重慶呈現較為明顯的分離(可能是成都?重慶距離較遠)。2) 圖(b)中：上海與蘇州昆山的聚簇overlap較大(住昆山，在上海工作)，蘇州主城區和張家港則明顯呈現獨立聚簇。進一步地，在雙十二的券抽獎場景上線了GTRL-G模型以幫助預測用戶未來支付的位置，對比線上基線模型(MMoE)，GTRL-G在整體核銷率上可以帶來3.31%的提升，在非消費券核銷率上可以帶來13.94%的提升。

6 結束語

本文提出了一個統一的用戶表示學習框架?GTRL，可以有效地捕獲用戶行為在時空維度的語義。具體地，GTRL在時間建模上使用了函數式的時間編碼和連續時間和上下文感知的圖注意力網絡用于在圖上靈活地捕獲高階的結構化時序信息。與此同時，GTRL在空間建模上引入了層級化的地理編碼和深度歷史軌跡建模模塊高效地刻畫了用戶的地理位置偏好。最后GTRL給出了一個統一且可解耦的優化方案來聯合預測下一次交互，及相應的時間和地理位置。大量的公開數據集和工業數據集上的實驗分別驗證了GTRL相較學術界基線模型的優勢，以及在實際業務場景中的有效性。在未來的工作中，將進一步致力于研究用戶行為的稀疏性問題，將更加復雜的結構信息(如用戶側的社交網絡信息和商品側的知識圖譜信息)集成到GTRL框架中。