摘 要：下一個興趣點推薦是推薦算法領(lǐng)域的熱點，旨在為用戶推薦適合的下一地點。較新的研究通過圖和序列方法模擬用戶與POI的交互以及POI之間轉(zhuǎn)換關(guān)系，性能得到顯著提升。然而，現(xiàn)有模型仍然存在需要解決的問題。針對現(xiàn)有的下一個興趣點推薦模型的局限性，特別是如何充分捕捉User-POI交互圖上全局和局部信息，以及緩解圖神經(jīng)網(wǎng)絡(luò)的過平滑特性導(dǎo)致圖上信息丟失的問題，提出了基于graph Transformer的多編碼模型 （multi-coding network based on GT model）對下一個興趣點進行推薦。首先，從位置和結(jié)構(gòu)的視角上聯(lián)合對user-POI交互圖上進行全局、局部以及相對信息進行編碼；然后，將編碼后生成的圖嵌入通過graph Transformer網(wǎng)絡(luò)層更新圖上節(jié)點與邊信息；最后通過MLP網(wǎng)絡(luò)層生成預(yù)測；最終，MCGT在Gowalla和TKY兩個公開數(shù)據(jù)集進行對比實驗。結(jié)果表明，在Gowalla 數(shù)據(jù)集上recall和NDCG指標至少有3.79%的提升，在TKY數(shù)據(jù)集上recall和NDCG指標至少有2.5%的提升，證明了MCGT設(shè)計的合理性與有效性。

關(guān)鍵詞：下一個興趣點推薦；多編碼；全局信息；局部信息；相對信息；圖Transformer

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695（2024）11-026-3382-07

doi：10.19734/j.issn.1001-3695.2024.03.0092

Multi-coding next point of interest recommendation model based on GT model

Wang Yonggui， Zhang Xiaorui^?

（College of Electronics amp; Information Engineering， Liaoning Technical University， Huludao Liaoning 125105， China）

Abstract：Next point of interest （POI） recommendation is a hot topic in the field of recommendation algorithms， which aims at recommending the suitable next locations for users. Recent research has significantly improved performance by simulating user interactions with POIs and the transitions between POIs using graph and sequence methods. However， existing models still have issues that need to be addressed. In response to the limitations of current next POI recommendation models， particularly in how to fully capture both global and local information on the user-POI interaction graph， and in alleviating the oversmoothing characteristics of graph neural networks that lead to information loss on the graph， this paper proposed a multi-coding network based on the graph Transformer model for recommending the next POI. Firstly， it jointly encoded global， local， and relative information on the user-POI interaction graph from the perspectives of position and structure. Then， the graph embeddings produced by this encoding were updated through graph Transformer network layers， which refreshed the information of nodes and edges on the graph. Finally， predictions were generated through MLP network layers. The MCGT model was empirically tested on two public datasets， Gowalla and TKY. The results show that at least a 3.79% improvement in recall and NDCG metrics on the Gowalla dataset and at least a 2.5% improvement on the TKY dataset， thus proving the reasonableness and effectiveness of MCGT.

Key words：next point of interest recommendation; multi-encoding; global information; local information; relative information; graph Transformer

0 引言

隨著信息和通信技術(shù)的進步，在現(xiàn)代社會中，人們傾向于在社交媒體上分享他們的日常生活。在此趨勢下，基于社交位置的服務(wù)受到越來越多的關(guān)注，引起了學(xué)者們對興趣點推薦^［1～3］的研究，即根據(jù)用戶的歷史簽到軌跡推斷用戶可能會訪問的地點。作為興趣點推薦的一個子類，下一個興趣點^{［4， 5］}推薦旨在預(yù)測用戶在未來短時間內(nèi)最有可能到達的地點，通常是通過用戶的歷史簽到以及對用戶的個人偏好建模來對用戶即將訪問的地點進行預(yù)測。

關(guān)于下一個興趣點推薦問題的現(xiàn)有解決方案可以分為基于序列的解決方案和基于圖的解決方案兩類?；谛蛄械慕鉀Q方案主要包括馬爾可夫鏈、基于RNN的模型和基于注意力的模型。早期的研究使用馬爾可夫鏈來模擬序列轉(zhuǎn)換模式^［6］；基于RNN的方法將經(jīng)典的RNN體系結(jié)構(gòu)（如長短期記憶（LSTM）），與時間和空間上下文結(jié)合起來，以提高模型捕獲序列規(guī)律性^{［7，8］}的能力。此外，由于Transformer^［9］在自然語言處理（NLP）領(lǐng)域中取得巨大成功，提出了基于注意力的推薦方式來構(gòu)建模型^［10］。最近，由于圖模型的廣泛應(yīng)用，基于圖嵌入^［11］結(jié)構(gòu)的推薦模型被提出，研究人員基于空間臨近性或不同用戶的歷史軌跡來構(gòu)建POI圖。在先進模型中，由于其出色的用戶偏好捕獲能力和測量相同類型對象之間相似度的能力，GNN被認為是下一個POI推薦模型中最為有效的支持技術(shù)之一。例如，文獻［12］采用圖循環(huán)網(wǎng)絡(luò)（GRN）分析時空POI-POI圖來學(xué)習(xí)POI之間的時空相關(guān)性。文獻［4］提出了一種全局轉(zhuǎn)換流圖，并運用圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）建模POI的相似度。由于圖嵌入能夠表達豐富的上下文信息，所以它們被廣泛用于表示POI。文獻［13］提出了一種基于圖的度量方法，用于生成POI嵌入；文獻［14］則構(gòu)建了POI簽到序列圖，并利用圖神經(jīng)網(wǎng)絡(luò)（GNN）生成POI的嵌入以表示用戶的簽到行為；而文獻［15］提出了一種新的自適應(yīng)圖表示增強注意網(wǎng)絡(luò)用于下一個POI推薦，利用圖嵌入學(xué)習(xí)來替代預(yù)定義的靜態(tài)圖嵌入學(xué)習(xí)以獲得更具表現(xiàn)力的POI表示。

盡管現(xiàn)有關(guān)于圖神經(jīng)網(wǎng)絡(luò)推薦模型在下一個興趣點推薦方向推薦效果良好，但仍然存在兩個需要解決的問題。首先，現(xiàn)有推薦模型僅通過圖神經(jīng)網(wǎng)絡(luò)生成POI圖上的局部信息的嵌入，忽略了全局信息對POI節(jié)點特征的影響；其次，傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)模型在處理圖嵌入結(jié)構(gòu)數(shù)據(jù)時，消息傳遞的過程中產(chǎn)生的過平滑與過擠壓的現(xiàn)象會使圖上節(jié)點的邊緣信息丟失，對推薦效果產(chǎn)生影響；而且，當數(shù)據(jù)集體量較大時，圖上的計算量增加會對所使用的設(shè)備產(chǎn)生負擔。

因此，本文提出了MCGT模型來解決上述問題。首先，通過將所有用戶的簽到軌跡映射到一個user-POI圖中，構(gòu)建一個圖結(jié)構(gòu)，其中每個節(jié)點表示一個用戶或一個POI。用戶節(jié)點與POI節(jié)點之間存在訪問與被訪問的關(guān)系，而POI與POI節(jié)點之間存在用戶移動關(guān)系，并具有方向性，權(quán)重根據(jù)訪問的頻率而定。為了專注于用戶個性化偏好以及提升計算效率，以不同用戶為中心，通過K-hop的方式劃分子圖，對每個子圖分別進行全局編碼、局部編碼和相對編碼。全局編碼通過對子圖進行拉普拉斯特征分解，將其特征向量和特征值分別作為全局位置編碼和全局結(jié)構(gòu)編碼。特征向量捕捉圖上節(jié)點的位置，特征值則反映子圖的整體連接性，提供交互模式的宏觀視圖。局部編碼利用隨機游走生成的對角線元素和非對角線元素之和，分別作為局部結(jié)構(gòu)編碼和局部位置編碼。對角線元素反映節(jié)點在其局部環(huán)境中的重要性，非對角線元素的和描述了節(jié)點間的局部連接細節(jié)，專注于捕捉鄰域信息。相對編碼則通過衡量節(jié)點之間的相對位置和結(jié)構(gòu)關(guān)系，增強模型在區(qū)分圖中節(jié)點微小位置差異方面的能力。通過融合全局編碼、局部編碼和相對編碼的信息，可以全面挖掘用戶的個性化偏好，提高下一個POI推薦的準確性和個性化程度。

將編碼后的子圖輸入到graph Transformer層中進行訓(xùn)練，通過Transformer中的自注意力機制，可以直接捕捉節(jié)點之間的全局關(guān)系，避免過度依賴節(jié)點的局部鄰居信息，關(guān)注遠距離節(jié)點，減少了層數(shù)過多時的過平滑問題，能更好地處理長距離依賴和全局結(jié)構(gòu)信息。最終輸出的向量即為推薦結(jié)果。這種綜合利用全局編碼、局部編碼、相對編碼和graph Transformer的方法使得下一個興趣點推薦模型能夠更精準地捕捉用戶個性化的興趣，并更有效地進行推薦。

本文主要做了以下貢獻：

a）提出信息多編碼方式，相應(yīng)地分為局部編碼、全局編碼和相對編碼三種類別，充分捕獲圖上上下文信息，挖掘用戶的整體偏好和局部興趣點的特定關(guān)聯(lián)。這有助于提高個性化推薦的準確性。

b）創(chuàng)新性結(jié)合GatedGCN^［16］與Bi-Transformer^［17］作為一個網(wǎng)絡(luò)層用于推薦，其中GatedGCN可以使上下文信息在圖上傳播，Bi-Transformer（BERT）模型可以在圖上線性地捕獲圖上的全局注意，獲得用戶訪問POI歷史軌跡中的個性化偏好，并緩解了現(xiàn)有模型過平滑特性導(dǎo)致的邊緣信息丟失現(xiàn)象，提升推薦效果。

c）在Gowalla和Foursquare-TKY兩個真實數(shù)據(jù)集上進行了實驗。實驗結(jié)果表明，本文方案在多種設(shè)置下優(yōu)于最先進的方案。

1 相關(guān)工作

1.1 下一個興趣點推薦

與一般的POI推薦方法相比，下一個POI推薦的目標是根據(jù)用戶歷史的簽到記錄來預(yù)測用戶可能會簽入的下一個POI。因此，順序的影響是理解用戶行為的一個重要因素。經(jīng)典的序列因子建模方法，如馬爾可夫鏈^［18］和遞歸神經(jīng)網(wǎng)絡(luò)^［19］，已經(jīng)被引入到下一個POI推薦任務(wù)中。

Wang等人^［20］利用圖嵌入技術(shù)顯式地模擬復(fù)雜的地理影響。Fang等人^［21］提出了URPI-GRU，它由一個短期模塊和一個長期模塊組成。在短期模塊中，利用GRU模型來學(xué)習(xí)用戶的周期性和當前偏好。在長期模塊中，通過考慮K-近鄰序列來提取用戶的長期偏好。Zheng等人^［22］提出了一種記憶增強層次注意網(wǎng)絡(luò)，該網(wǎng)絡(luò)集成了短期簽到序列和長期記憶，旨在利用這兩種信息來源的組合來捕捉用戶運動的復(fù)雜時空模式。Huang等人^［23］提出了DAN-信噪比，通過利用自我注意機制在一個統(tǒng)一的框架內(nèi)建模順序和社會影響，解決了這一差距。文獻［24］提出一種基于異質(zhì)圖嵌入的時空不敏感興趣點推薦模型，降低推薦過程對興趣點間距離的敏感程度，進而增強推薦結(jié)果的可解釋性。Lai等人^［25］提出了位置擴展算法和門控深度網(wǎng)絡(luò)的組合，利用一個門控的深度網(wǎng)絡(luò)，通過生成輔助的二進制門來捕獲長期的行為依賴關(guān)系。此外，還采用了位置擴展算法來增強遞歸神經(jīng)網(wǎng)絡(luò)中的上下文交互作用。

然而，上述方法忽略了對POI圖上全局信息和局部信息的融合，限制了推薦的準確性。因此，本文使用多編碼的方式捕獲圖上的全局信息與局部信息，豐富了生成的圖嵌入表示，提升推薦效果。

1.2 graph Transformer

近年來，有關(guān)下一個興趣點推薦的模型試圖利用各種圖神經(jīng)網(wǎng)絡(luò)，通過嵌入方式建模user-item交互圖。例如，PinSage^［26］和NGCF^［27］建立在譜域的圖卷積網(wǎng)絡(luò)上，隨后LightGCN^［28］提出了一種簡化的模型，去除了冗余的非線性變換，采用基于求和的池化操作，在基于GCN的消息傳遞模式上，每個用戶和項目都被編碼到轉(zhuǎn)換后的嵌入中，并保存了多跳連接，充分利用節(jié)點上的信息，提升推薦效果。為了進一步提高用戶表示能力，最近的一些研究設(shè)計用于user-item交互建模的解糾纏圖神經(jīng)架構(gòu)，如DGCF^［29］和DisenHAN^［30］。同時，提出了幾種多關(guān)系GNN來增強具有多行為建模的推薦系統(tǒng)，包括KHGT^［31］和HM-GCR^［32］，為推薦方向提供了有力的建模。然而，由于GCN在訓(xùn)練過程中每一層只聚合直接相鄰節(jié)點的信息，對全局信息的捕捉能力相對較弱，對于更遠處的節(jié)點關(guān)系，GCN的表示學(xué)習(xí)效果欠佳；且由于單一的圖卷積網(wǎng)絡(luò)的過平滑^［33］和低表達性等問題的限制，這些層在早期階段無法保留圖上完整信息，存在信息丟失的現(xiàn)象。因此，本文利用Gated-GCN與Bi-Transformer（BERT）共同構(gòu)建的網(wǎng)絡(luò)層實現(xiàn)推薦，與單一的圖卷積模型不同的是，BERT可以在圖上捕獲更遠處的節(jié)點信息，與GatedGCN共同完成對圖上節(jié)點以及邊的更新。BERT與GatedGCN通過全連接使信息在全局圖上傳播，從而解決由過平滑和過擠壓造成的表達瓶頸，充分結(jié)合圖上的全局與局部信息，避免了圖中邊信息丟失，豐富目標節(jié)點的表征，提高推薦的效果。

2 MCGT模型

MCGT模型主要由編碼部分與graph Transformer網(wǎng)絡(luò)層兩部分組成，編碼部分由局部編碼、全局編碼以及相對編碼組成，其中局部編碼由隨機游走算法生成，對角線元素與非對角線元素行的和分別對應(yīng)位置編碼與結(jié)構(gòu)編碼；拉普拉斯矩陣分解的前K個最小特征向量與特征值分別表示全局位置編碼與結(jié)構(gòu)編碼；相對位置與相對結(jié)構(gòu)編碼分別由特征向量的梯度與兩個節(jié)點是否屬于同一子結(jié)構(gòu)的布爾值構(gòu)成。將編碼信息通過concat融合，編碼后的圖結(jié)構(gòu)使用graph Transformer網(wǎng)絡(luò)層進行訓(xùn)練，最后輸出最終的預(yù)測。

2.1 問題定義

設(shè)U={u₁，u₂，…，u_U}和P={p₁，p₂，…，p_P}分別表示用戶和POIs的集合，用戶的簽入由c=〈u，p，t〉表示，表明用戶u在t時刻訪問了位置p，用戶的簽到軌跡是由其一系列按時間順序記錄的簽到構(gòu)成的。使用T_ui={c^t₁₁，c^t₂₂，…，c^t_mm}來表示用戶u_i的歷史軌跡，其中c^t_mm表示u_i的最新簽到記錄。利用不同用戶的簽到記錄和共同訪問的興趣點（POI），構(gòu)建用戶全局軌跡圖。由G=〈V，E，R〉表示，其中v∈V表示全局圖上的實體，e∈E表示兩個不同實體之間連接的邊，r∈R表示興趣點之間是否存在用戶流動的關(guān)系。給定user-POI軌跡圖，下一個POI推薦旨在輸出用戶u_i短期內(nèi)最有可能訪問的top-k POI。

2.2 子圖劃分

在實現(xiàn)個性化推薦的過程中，為了有效緩解數(shù)據(jù)集規(guī)模過大對實驗設(shè)備帶來的壓力，本文采用劃分子圖的方式。具體而言，以圖上每一個用戶作為中心點，以該用戶為中心，通過k-hop鄰域擴展構(gòu)建子圖，由于隨著K值的增加，子圖包含更多的節(jié)點信息和邊信息，會引入大量無關(guān)的信息和噪聲，信息可能會被稀釋，導(dǎo)致模型難以區(qū)分重要特征和次要特征。因此，在本文模型中，K值設(shè)置為1。劃分方式如圖1所示。

2.3 多樣性編碼

位置編碼（position encoding）明確節(jié)點在圖中位置，結(jié)構(gòu)編碼（structure encoding）提供子圖結(jié)構(gòu)的嵌入。當子圖上的位置編碼相近時，圖中兩個節(jié)點距離相近，因此地點通常相似，通過對用戶訪問地點的相似性進行建模，為用戶推薦感興趣的地點；當兩個節(jié)點的結(jié)構(gòu)編碼相似時，說明兩個子圖的結(jié)構(gòu)相似，因此當用戶的交互數(shù)據(jù)稀疏時，通過相似的結(jié)構(gòu)編碼信息，為用戶推薦相似結(jié)構(gòu)上的地點，來緩解數(shù)據(jù)稀疏性，提高推薦效果。因此，本節(jié)使用的全局編碼、局部編碼與相對編碼對用戶與地點生成圖嵌入主要分為位置和結(jié)構(gòu)兩種類別，用圖嵌入代替現(xiàn)有模型使用的序列嵌入對數(shù)據(jù)進行訓(xùn)練，充分挖掘圖上信息的傳遞，提升推薦效果。整體架構(gòu)以及編碼方式如圖2所示。

2.3.1 局部編碼

為了提升節(jié)點對圖中信息的理解，利用隨機游走算法對圖上節(jié)點進行編碼。隨機游走側(cè)重于捕捉圖上的局部信息，通過考察節(jié)點間的隨機游走路徑，能有效捕捉節(jié)點的鄰域信息。通過隨機游走生成的對角線元素與非對角線元素的和能反映節(jié)點間的連接強度和訪問頻率，有助于揭示圖上節(jié)點的局部特征。首先，構(gòu)建子圖的鄰接矩陣A、子圖邊的權(quán)重矩陣W和度矩陣D，通過標準化鄰接矩陣A得到轉(zhuǎn)移概率矩陣P=D^－1A，它代表了一個節(jié)點在單步隨機游走中轉(zhuǎn)移到其他節(jié)點的概率。對于m步隨機游走，轉(zhuǎn)移概率矩陣P^m=（D^－1A）m表示了節(jié)點在m步到達其他節(jié)點的概率分布。對每個節(jié)點i，定義其局部位置編碼為E^lp_i=∑j≠i（P^m）_ij。E^lp_i由P^m中對應(yīng)行的非對角線元素之和計算得出。這個編碼反映了節(jié)點i通過m步隨機游走與其他節(jié)點的關(guān)聯(lián)程度，捕捉了其在局部鄰域內(nèi)的位置信息。同時，為了揭示每個節(jié)點在其直接鄰域內(nèi)的結(jié)構(gòu)特性，利用P^m的對角線元素作為節(jié)點的局部結(jié)構(gòu)編碼：E^ls_i=P^m_ii，對角線上元素反映了用戶對當前節(jié)點的偏好以及節(jié)點與其鄰居之間的連接強度，有助于捕捉每個節(jié)點的局部結(jié)構(gòu)特征。通過這種方法，精確地捕捉了節(jié)點在其鄰域內(nèi)的位置和結(jié)構(gòu)信息，增強了節(jié)點對圖上信息的理解能力，為基于圖的表示提供了豐富的局部信息，從而有助于提高模型對復(fù)雜圖嵌入結(jié)構(gòu)的處理能力和推薦的準確性。

2.3.2 全局編碼

為了捕捉全局連通性和圖布局以及增強節(jié)點的區(qū)分能力，本文采用拉普拉斯矩陣分解的方式分別對節(jié)點進行位置編碼與結(jié)構(gòu)編碼。首先，對矩陣進行標準化，如式（1）（2）所示。

L=D－W（1）

L_norm=D^－12LD^－12（2）

對標準化的拉普拉斯矩陣L_norm進行特征分解，得到特征值{λ₁，λ₂，…，λ_n}和對應(yīng)的特征向量{v₁，v₂，…，v_n}，其中n是子圖中用戶訪問興趣點的數(shù)量，從特征值和特征向量中選擇前k個最小的非零特征值以及與之對應(yīng)的相關(guān)的特征向量，分別記為λ_ik與v_ik，對于每個節(jié)點i，E^gp_i=［v_ki］定義為全局位置編碼，描述了節(jié)點在整個子圖中的位置。v_ki表示矩陣中相關(guān)的特征向量的第i個元素，代表了節(jié)點i在全局編碼中的位置。較小的特征值描述圖的低頻成分，即大范圍的連通結(jié)構(gòu)。反映了圖中節(jié)點之間的整體連接模式和全局拓撲結(jié)構(gòu)。故前k個最小非零特征值，有助于識別子圖結(jié)構(gòu)，更好地捕捉全局連通性和圖的布局，故將特征值λ_k定義為全局結(jié)構(gòu)編碼。

2.3.3 相對編碼

本文使用拉普拉斯矩陣分解的特征向量梯度E^rp_ij=Δ?_k作為相對位置編碼用來明確節(jié)點之間的方向性，獲得節(jié)點之間訪問的順序關(guān)系；而相對結(jié)構(gòu)編碼則通過識別圖中相似的子結(jié)構(gòu)，揭示了節(jié)點之間的相似程度，若布爾值編碼為1，表示它們具有較高的相關(guān)性，可以反映出用戶的潛在興趣模式，推薦出更符合用戶興趣的地點。以節(jié)點是否屬于同一子結(jié)構(gòu)進行相對結(jié)構(gòu)編碼，公式為

E^rs_ij=1

i～j0

otherwise （3）

2.4 特征融合

將位置編碼與結(jié)構(gòu)編碼的特征信息進行融合，為了不混淆編碼信息，本文選擇使用concat對兩類編碼信息進行融合，且為確保全局結(jié)構(gòu)編碼與局部結(jié)構(gòu)編碼在相同的范圍內(nèi)，使用歸一化對其進行規(guī)范化編碼，式（4）對節(jié)點的編碼特征信息進行融合：

E^lp_i=MLP（norm（E^lp_i）），

E^gs_i=DeepSet（norm（E^gs_i））

E^ls_i=DeepSet（norm（E^ls_i）），

E^gp_i=DeepSet（E^gp_i）

X^l=concat（X⁰，E^lp_i，E^gs_i，E^ls_i，E^gp_i）（4）

式（5）為對邊的特征信息進行融合：

E^rs_i=MLP（E^rs_i），

E^rp_i=MLP（E^rp_i）

E^l=concat（E⁰，E^rs_i，E^rp_i）（5）

2.5 graph Transformer網(wǎng)絡(luò)層

graph Transformer層對比于普通的圖神經(jīng)網(wǎng)絡(luò)具有捕獲長距離依賴，減輕出現(xiàn)的過平滑，過擠壓現(xiàn)象等優(yōu)點，結(jié)合全局與局部信息編碼使模型具有更好的表達能力。

2.5.1 GatedGCN

為了更準確地捕獲POI的特征，僅僅依賴于學(xué)習(xí)到的圖的特征嵌入表示是不夠的。因此，模型引入了門控圖卷積網(wǎng)絡(luò)來進一步細化表示。GatedGCN（圖3）被視為一種高效的消息傳遞網(wǎng)絡(luò)，通過利用殘差連接、批歸一化以及門控邊緣的方式設(shè)計了GCN的各向異性變體，它明確地更新節(jié)點特征和邊緣特征如式（6）所示。

h^l+1_ig=h^l_i+ReLU （BN（U^lh^l_i+∑j∈N_ie^l_ij⊙V^lh^l_j））（6）

其中：U^l，V^l∈^d×d；d是特征的維度；h⁰_i=x^l；⊙表示Hadamard積；BN（·）是批處理歸一化運算符。并將邊緣特征向量更新為

e^l_ij=σ（^l_ij）∑j′∈N_iσ（^l_ij）+ε（7）

^l_ij=^l-1_ij+ReLU（BN （A^lh^l-1_i+B^lh^l-1_j+C^ll-1_ij））（8）

其中：σ（·）是sigmoid函數(shù)；ε是為了分母不為0來穩(wěn)定計算的一個趨近于無窮小的常數(shù)；A^l，B^l，C^l∈^d×d。

2.5.2 Bi-Transformer

由于在訓(xùn)練過程中，Bi-Transformer能夠同時學(xué)習(xí)目標POI左右兩側(cè)的上下文信息，可以增強POI的表征，而且它在聚合軌跡中最相關(guān)的行為上下文相關(guān)性方面具有強大的能力，如圖4所示。

因此，利用Bi-Transformer對子圖上的POI節(jié)點進行訓(xùn)練更新，如式（9）～（12）所示。

2.6 預(yù)測

利用雙層MLP層對通過graph Transformer層輸出的節(jié)點進行聚合，輸出的向量即為預(yù)測的結(jié)果。

h_i+1=2MLP（h^l+1_ig+h^l+1_iT）（13）

同時，使用交叉熵損失作為小批量訓(xùn)練的損失函數(shù)，并將損失表示為

Loss=－ylog（）－（1－y）log（1－）（14）

3 實驗與實驗分析

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

本文模型在Gowalla^［34］和Foursquare-TKY^［35］兩個真實的公共LBSN數(shù)據(jù)集上進行了實驗。Gowalla包含2008年3月至2010年10月在加利福尼亞州和內(nèi)華達州的簽到數(shù)據(jù)；Foursquare-TKY （TKY）包含2012年4月至2014年1月在東京簽到記錄的數(shù)據(jù)集。每條簽入數(shù)據(jù)都包含user-ID、POI-ID和時間戳，兩個數(shù)據(jù)集中所有記錄的簽到時間戳都是UTC時間。忽略訪問少于10個簽到記錄的非活動用戶和訪問少于10個用戶的冷門POI來對這兩個數(shù)據(jù)集進行預(yù)處理。每個用戶的前80%的簽到記錄用于測試，10%的簽到記錄用于驗證，后10%的簽到記錄用于訓(xùn)練。本文數(shù)據(jù)集如表1所示。

3.2 評價指標

本文使用推薦方向上召回率（recall@K）和標準化貼現(xiàn)累積增益（NDCG@K）兩個廣泛使用的評估指標。具體來說，recall@K衡量了top-K推薦中的標簽的比率，而NDCG@K反映了排名列表的質(zhì)量。在本文中，每個度量上重復(fù)實驗10次，并使用常用的K∈{5，10}給出平均結(jié)果。

3.3 參數(shù)設(shè)置

本文實驗是在RTX3090服務(wù)器，PyTorch 1.13.1的環(huán)境下進行的，對于MCGT模型，使用Adam作為優(yōu)化器，隱藏層維度與嵌入層維度相同且均為128，學(xué)習(xí)率設(shè)置為0.001，隱藏層的激活函數(shù)使用GELU函數(shù)，隨機游走的尺度根據(jù)數(shù)據(jù)集的特點分別設(shè)置為64與128，為防止出現(xiàn)過擬合的現(xiàn)象，模型使用了dropout技術(shù)，并將dropout的值設(shè)置為0.2。

3.4 基線模型

為了評估模型的有效性，本文將MCGT模型與以下幾個基線模型進行比較。

a）DeepMove^［36］：一個序列推薦模型，應(yīng)用RNN模型，通過在其上使用注意機制分別捕獲歷史序列和當前序列的周期性。

b）STGN^［8］：一種引入時空門來模擬連續(xù)訪問之間的時間和距離關(guān)系LSTM 模型。

c）LSTPM^［37］：一個使用非局部網(wǎng)絡(luò)來建模長期偏好，并使用一個地理擴張的RNN來學(xué)習(xí)短期偏好的一個經(jīng)典的LSTM模型。

d）LightGCN^［28］：一個先進的簡化的基于GNN的協(xié)同過濾框架，它省略了傳播過程中的非線性激活和特征轉(zhuǎn)換。

e）GSTN^［20］：一個基于圖的空間依賴建模，引入圖增強的時空網(wǎng)絡(luò)，結(jié)合LSTM和GSD進行下一個POI推薦的方法。

f）TADSAM^［38］：其使用擴展的自注意力機制處理用戶復(fù)雜的簽到記錄，開發(fā)了一種根據(jù)用戶不同時間窗口的簽到記錄的個性化的權(quán)重計算方法來利用用戶行為的時間模式。

g）GIPR^［24］：提出一種基于異質(zhì)圖嵌入的時空不敏感時空興趣點推薦模型，降低推薦過程對興趣點間距離的敏感程度，進而增強推薦結(jié)果的可解釋性。

h）MSTHN^［25］：一種聯(lián)合學(xué)習(xí)局部和全局視圖，通過局部的不對稱聚合時空相關(guān)性以及全局采用穩(wěn)定的超圖神經(jīng)網(wǎng)絡(luò)捕獲高階協(xié)同信號進行推薦的方法。

在實驗時，令K={5，10}，并且使用相同的指標和測試數(shù)據(jù)來評估所有方法的性能。得到評價指標recall@K和NDCG@K的結(jié)果如表2、3所示，其中最優(yōu)結(jié)果用加粗表示，次優(yōu)結(jié)果用下畫線表示。將模型的性能與基線模型進行比較，可以得出以下結(jié)論：

在Gowalla和TKY數(shù)據(jù)集上的結(jié)果顯示，本文MCGT在所有評估指標下顯著優(yōu)于所有其他先進的基線方法。具體來說，在Gowalla上，recall@5、recall@10和NDCG@5、NDCG@10相對于最優(yōu)的推薦模型分別提升了4.3%、3.79%、6.9%和5.16%。在TKY上，評價指標分別提升了2.5%、9.2%、4.51%和4.98%。簡言之，上述實驗數(shù)據(jù)清楚地顯示了MCGT的優(yōu)越性。

基于注意力機制的方法效果優(yōu)于傳統(tǒng)方法和基于RNN的方法，在LSTPM中，geo-dilated LSTM顯式建模具有一定的效果，但在長序列建模中會弱于帶mask的多頭注意力機制，這證明了多頭注意力機制在建模序列依賴上效果顯著。在基于注意力的方法中，TADSAM由于加入了時序的因素更具競爭力，這一觀察結(jié)果證明了利用POI之間的訪問先后順序來提高性能的必要性。然而，這些方法僅僅集中于序列內(nèi)的POI相關(guān)性，沒有充分獲取POI之間的上下文信息，因此推薦效果并不十分理想。

GIPR利用異質(zhì)圖整合用戶信息、興趣點信息與交互信息，利用圖嵌入的方式學(xué)習(xí)用戶與興趣點的表征，說明了圖嵌入相對于序列嵌入在捕獲上下文信息的優(yōu)越性；MSTHN利用GNN從POI關(guān)系圖中提取有用的信息來學(xué)習(xí)信息表示，比其他基線獲得了更好的性能。這驗證了基于圖網(wǎng)絡(luò)的表示學(xué)習(xí)與全局和局部視角在下一個POI推薦中的有效性。然而，雖然這種方法在圖形設(shè)計上相對完善，但單純依靠圖神經(jīng)網(wǎng)絡(luò)堆疊生成的嵌入會忽略圖上邊緣信息致使圖上的信息丟失，導(dǎo)致性能次優(yōu)。

3.5 消融實驗

為了驗證本文模型的可行性，分別在兩個數(shù)據(jù)集上進行了一系列消融實驗來說明各個模塊的有效性。在本文模型的基礎(chǔ)上，對模型的三種變體做了實驗并進行比較：a）A表示去掉相對編碼；b）B表示去掉全局與局部結(jié)構(gòu)編碼；c）C表示去掉Transformer；d）D表示本文模型。

D與A相比加入了相對編碼，布爾值作為相對結(jié)構(gòu)編碼捕捉節(jié)點之間的結(jié)構(gòu)相似性，同時拉普拉斯特征值的梯度作為相對編碼引入位置關(guān)系，使得節(jié)點之間的局部信息與全局信息共同影響，充分利用上下文信息，從圖5可以看出，相對編碼對最終的推薦結(jié)果具有很大的影響。

D與B相比，D中加入了全局與局部結(jié)構(gòu)編碼，其中m-step隨機游走的對角線作為局部結(jié)構(gòu)編碼可以捕獲圖上局部結(jié)構(gòu)信息，而拉普拉斯矩陣最低特征值可以捕獲全局圖上的結(jié)構(gòu)信息，兩者共同作為結(jié)構(gòu)編碼有助于模型更好地理解節(jié)點之間的關(guān)系，提高用戶與地點之間關(guān)系的建模效果。

本文模型使用graph Transformer與C僅使用圖神經(jīng)網(wǎng)絡(luò)對比之下具有一定的效果，這是因為GT層對圖上的每個節(jié)點進行注意力的作用，因此圖上節(jié)點的特征信息在經(jīng)過L層的傳播可以捕獲更多交互信息，避免信息丟失，加強用戶個性化偏好的建模，提升推薦的效果。

3.6 特征融合函數(shù)分析

本文選取了五種常見的不同特征融合方法來分析其對整體推薦性能的影響。

a）求和方法（SUM）：將編碼矩陣特征元素逐元素相加，生成新特征。

b）最大池化方法（MAX）：比較多個編碼特征的每個元素，返回對應(yīng)位置的最大值，形成新特征。

c）平均融合方法（AVG）：將編碼特征矩陣逐元素相加后取平均，得到融合后的特征矩陣。

d）哈達瑪乘積（Hadamard product）：對多個編碼矩陣逐元素進行元素乘積，得到融合后的特征矩陣。

e）拼接方法（concat）：按指定維度將多個編碼特征合并，生成新特征。

不同的融合方法對模型產(chǎn)生的影響如表4、5所示，其中最優(yōu)結(jié)果加粗表示，次優(yōu)結(jié)果用下畫線表示。

首先，對多個編碼進行求和的方法在兩個數(shù)據(jù)集上表現(xiàn)的效果是最差的，這是因為將不同的編碼簡單相加，既無法有效平衡不同特征的影響，又可能導(dǎo)致特征信息的丟失；最大池化保留了最大值，但它丟棄了其他信息，這會導(dǎo)致編碼信息表示不完整，尤其是在特征值接近的情況下，某些重要信息可能被忽略；平均融合方法綜合了所有編碼的特征信息，使得特征表示更加全面，能夠更好地反映位置編碼和結(jié)構(gòu)編碼的整體特征，但同時也可能會導(dǎo)致一些重要的信息被弱化，影響推薦效果；哈達瑪乘積可以捕捉位置編碼和結(jié)構(gòu)編碼之間的交互關(guān)系，對推薦會產(chǎn)生一定的正面影響，但是，如果位置編碼與結(jié)構(gòu)編碼存在某些位置都很小的情況下，會弱化節(jié)點的特征信息，對推薦效果產(chǎn)生一定的影響；與上述融合方式不同，concat方法通過增加特征維度，使得特征表示更加豐富，能夠捕捉到更細粒度的特征信息，拼接保留了位置編碼和結(jié)構(gòu)編碼的獨立性，使得模型可以分別處理和學(xué)習(xí)不同信息的重要程度。

3.7 超參數(shù)實驗

本文進一步分析了MCGT中g(shù)raph Transformer層數(shù)和head數(shù)的影響。

a）層數(shù)的影響。為了研究堆疊graph Transformer層的影響，在{1、2、3、4}中進行了層數(shù)的實驗。如圖6所示， MCGT通過在TKY上使用2層，在Gowalla上疊加3層，獲得了最好的性能。在達到閾值后，隨著層數(shù)的增加，模型效果開始下降。

b）head數(shù)量的影響。為了探討在graph Transformer層中選擇頭數(shù)的影響，從集合{1、2、4、8}中選擇頭數(shù)進行實驗。從圖7可以看出，兩個數(shù)據(jù)集均在頭數(shù)為4時獲得最佳性能，頭數(shù)從4增加到8，recall@10和NDCG@10開始下降。

4 結(jié)束語

本文提出了一種基于GT模型的多編碼下一個興趣點推薦模型，用于提升下一個興趣點推薦系統(tǒng)的準確性。通過引入隨機游走算法和拉普拉斯矩陣分解，分別從局部和全局視角對節(jié)點進行位置和結(jié)構(gòu)編碼，充分捕捉了節(jié)點在子圖中的信息。局部編碼側(cè)重于捕捉節(jié)點的鄰域信息，而全局編碼則揭示了圖的整體連通性和拓撲結(jié)構(gòu)。相對編碼進一步明確了節(jié)點之間的方向性和相似性，為模型提供了豐富的特征信息，隨后通過GatedGCN和Bi-Transformer組成的網(wǎng)絡(luò)層進一步捕獲用戶的個性化偏好。其中，GatedGCN通過門控機制和批歸一化，有效地更新了節(jié)點和邊緣特征，提升了模型的表達能力；Bi-Transformer則通過雙向注意力機制，增強了節(jié)點之間的上下文關(guān)聯(lián)。在Gowalla和TKY的數(shù)據(jù)集的評價指標上提升了至少2.5%的推薦效果。在未來的工作中，可以引入自適應(yīng)的推薦算法，結(jié)合局部和全局編碼，根據(jù)用戶行為的變化自動調(diào)整策略，提高推薦的時效性和精準度；同時，也可以結(jié)合用戶在社交網(wǎng)絡(luò)上的行為數(shù)據(jù)，利用局部和全局編碼捕捉用戶的興趣和社交影響力進行跨域推薦，提升推薦的個性化和社交性。

參考文獻：

［1］Ji Weiyu， Meng Xiangwu， Zhang Yujie. STARec： adaptive learning with spatiotemporal and activity influence for POI recommendation［J］. ACM Trans on Information Systems， 2021， 40（4）： article No. 65.

［2］Ji Weiyu， Meng Xiangwu， Zhang Yujie. SPATM： a social period-aware topic model for personalized venue recommendation［J］. IEEE Trans on Knowledge and Data Engineering， 2020， 34（8）： 3997-4010.

［3］Shi Lei， Song Guangjia， Cheng Gang， et al. A user-based aggregation topic model for understanding user’s preference and intention in social network［J］. Neurocomputing， 2020， 413： 1-13.

［4］Yang Song， Liu Jiamou， Zhao Kaiqi. GETNext： trajectory flow map enhanced transformer for next POI recommendation［C］// Proc of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2022： 1144-1153.

［5］Wu Yuxia， Li Ke， Zhao Guoshuai， et al. Personalized long-and short-term preference learning for next POI recommendation［J］. IEEE Trans on Knowledge and Data Engineering， 2020， 34（4）： 1944-1957.

［6］Cheng Chen， Yang Haiqin， Lyu M R， et al. Where you like to go next： successive point-of-interest recommendation［C］// Proc of the 23rd International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2013： 2605-2611.

［7］Liu Qiang， Wu Shu， Wang Liang， et al. Predicting the next location： a recurrent model with spatial and temporal contexts［C］// Proc of the 30th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2016： 194-200.

［8］Zhao Pengpeng， Luo Anjing， Liu Yanchi， et al. Where to go next： a spatio-temporal gated network for next POI recommendation［J］. IEEE Trans on Knowledge and Data Engineering， 2020， 34（5）： 2512-2524.

［9］Gillioz A， Casas J， Mugellini E， et al. Overview of the Transformer-based models for NLP tasks［C］// Proc of the 15th Conference on Computer Science and Information Systems. Piscataway， NJ： IEEE Press， 2020： 179-183.

［10］Guo Qing， Sun Zhu， Zhang Jie， et al. An attentional recurrent neural network for personalized next location recommendation［C］// Proc of the 34th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2020： 83-90.

［11］吳永慶， 孫鵬， 金堯， 等. 融合一致性社交關(guān)系的協(xié)同相似嵌入推薦模型［J］. 計算機應(yīng)用研究， 2023， 40（10）： 2951-2956， 2966. （Wu Yongqing， Sun Peng， Jin Yao， et al. Collaborative similarity embedding recommendation model integrating consistent social relationships［J］. Application Research of Computers， 2023， 40（10）： 2951-2956， 2966.）

［12］Lim N， Hooi B， Ng S K， et al. Hierarchical multi-task graph recurrent network for next POI recommendation［C］// Proc of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2022： 1133-1143.

［13］Xie Min， Yin Hongzhi， Xu Fanjiang， et al. Graph-based metric embedding for next POI recommendation［C］// Proc of the 17th International Conference on Web Information Systems Engineering. Berlin： Springer， 2016： 207-222.

［14］Wang Dongjing， Wang Xingliang， Xiang Zhengzhe， et al. Attentive sequential model based on graph neural network for next POI recommendation［J］. World Wide Web， 2021， 24（6）： 2161-2184.

［15］Wang Zhaobo， Zhu Yanmin， Wang Chunyan， et al. Adaptive graph representation learning for next POI recommendation［C］// Proc of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2023： 393-402.

［16］Bresson X， Laurent T. Residual gated graph convnets［EB/OL］. （2018-04-24）. https：//arxiv.org/abs/1711.07553.

［17］Devlin J， Chang Mingwei， Lee K， et al. BERT： pre-training of deep bidirectional transformers for language understanding［C］// Proc of Conference of the North American Chapter of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， PA： Association for Computational Linguistics， 2019： 4171-4186.

［18］He Jing， Li Xin， Liao Lejian. Next point-of-interest recommendation via a category-aware Listwise Bayesian personalized ranking［J］. Journal of Computational Science， 2018， 28： 206-216.

［19］Zhao Kangzhi， Zhang Yong， Yin Hongzhi， et al. Discovering subsequence patterns for next POI recommendation［C］// Proc of the 29th International Conference on International Joint Conferences on Artificial Intelligence. 2020： 3216-3222.

［20］Wang Zhaobo， Zhu Yanmin， Zhang Qiaomei， et al. Graph-enhanced spatial-temporal network for next POI recommendation［J］. ACM Trans on Knowledge Discovery from Data， 2022， 16（6）： article No. 104.

［21］Fang Jinfeng， Meng Xiangfu. URPI-GRU： an approach of next POI recommendation based on user relationship and preference information［J］. Knowledge-Based Systems， 2022， 256（C）： 109848.

［22］Zheng Chenwang， Tao Dan， Wang Jiangtao， et al. Memory augmented hierarchical attention network for next point-of-interest recommendation［J］. IEEE Trans on Computational Social Systems， 2020， 8（2）： 489-499.

［23］Huang Liwei， Ma Yutao， Liu Yanbo， et al. DAN-SNR： a deep attentive network for social-aware next point-of-interest recommendation［J］. ACM Trans on Internet Technology， 2020， 21（1）： article No. 2.

［24］李曼文， 張月琴， 張晨威， 等. 異質(zhì)圖嵌入的地理不敏感時空興趣點推薦方法［J］. 計算機科學(xué)與探索， 2024， 18（3）： 755-767. （Li Manwen， Zhang Yueqin， Zhang Chenwei， et al. Geographically insensitive spatiotemporal interest point recommendation method with heterogeneous graph embedding［J］. Computer Science and Discovery， 2024， 18（3）： 755-767.）

［25］Lai Yantong， Su Yijun， Wei Linwei， et al. Multi-view spatial-temporal enhanced hypergraph network for next POI recommendation［C］// Proc of the 28th International Conference on Database Systems for Advanced Applications. Cham： Springer， 2023： 237-252.

［26］Ying R， He Ruining， Chen Kaifeng， et al. Graph convolutional neural networks for Web-scale recommender systems［C］// Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining. New York： ACM Press， 2018： 974-983.

［27］Wang Xiang， He Xiangnan， Wang Meng， et al. Neural graph colla-borative filtering［C］// Proc of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2019： 165-174.

［28］He Xiangnan， Deng Kuan， Wang Xiang， et al. LightGCN： simplif-ying and powering graph convolution network for recommendation［C］// Proc of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2020： 639-648.

［29］Wang Xiang， Jin Hongye， Zhang An， et al. Disentangled graph collaborative filtering［C］// Proc of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press， 2020： 1001-1010.

［30］Wang Yifan， Tang Suyao， Lei Yuntong， et al. DisenHAN： disentangled heterogeneous graph attention network for recommendation［C］// Proc of the 29th ACM International Conference on Information amp; Knowledge Management. New York： ACM Press， 2020： 1605-1614.

［31］Xia Lianghao， Huang Chao， Xu Yong， et al. Knowledge-enhanced hierarchical graph transformer network for multi-behavior recommendation［C］// Proc of the 21st AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2021： 4486-4493.

［32］Yang Haoran， Chen Hongxu， Li Lin， et al. Hyper meta-path contrastive learning for multi-behavior recommendation［C］// Proc of the 21st IEEE International Conference on Data Mining. Piscataway， NJ： IEEE Press， 2021： 787-796.

［33］Topping J， Di Giovanni F， Chamberlain B P， et al. Understanding over-squashing and bottlenecks on graphs via curvature［EB/OL］. （2022-11-12）. https：//arxiv.org/abs/2111.14522.

［34］Cho E， Myers S A， Leskovec J. Friendship and mobility： user movement in location-based social networks［C］// Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2011： 1082-1090.

［35］Yang Dingqi， Zhang Daqing， Zheng V W， et al. Modeling user acti-vity preference by leveraging user spatial temporal characteristics in LBSNs［J］. IEEE Trans on Systems， Man， and Cybernetics： Systems， 2014， 45（1）： 129-142.

［36］Feng Jie， Li Yong， Zhang Chao， et al. DeepMove： predicting human mobility with attentional recurrent networks［C］// Proc of the 9th World Wide Web Conference. New York： ACM Press， 2018： 1459-1468.

［37］Sun Ke， Qian Tieyun， Chen Tong， et al. Where to go next： modeling long-and short-term user preferences for point-of-interest recommendation［C］// Proc of the 34th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2020： 214-221.

［38］Liu Peng， Guo Yange， Liang Yuan， et al. TADSAM： a time-aware dynamic self-attention model for next point-of-interest recommendation［C］// Proc of the 1st International Workshop on Practical Deep Learning in the Wild. Palo Alto， CA： AAAI Press， 2022.