本期文章將為大家分享飛槳社區(qū)開發(fā)者肖淙曦、周景博發(fā)表于數(shù)據(jù)挖掘頂會(huì)KDD2023的論文《Spatial Heterophily Aware Graph Neural Networks》。

肖淙曦

肖淙曦，百度研究院商業(yè)智能實(shí)驗(yàn)室研究實(shí)習(xí)生，中國科學(xué)技術(shù)大學(xué)在讀博士生，主要從事時(shí)空數(shù)據(jù)挖掘和圖深度學(xué)習(xí)相關(guān)的研究工作。基于飛槳完成多篇論文，發(fā)表于KDD、AAAI等計(jì)算機(jī)頂級(jí)學(xué)術(shù)會(huì)議。

周景博

周景博，飛槳開發(fā)者高級(jí)技術(shù)專家（高級(jí)PPDE），現(xiàn)任百度研究院商業(yè)智能實(shí)驗(yàn)室資深研究員，主要從事數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)相關(guān)的研究和應(yīng)用工作，包括時(shí)空大數(shù)據(jù)、深度幾何學(xué)習(xí)、知識(shí)圖譜和AI輔助藥物設(shè)計(jì)等，PaddleSpatial技術(shù)負(fù)責(zé)人，基于飛槳完成論文多篇，發(fā)表于KDD、AAAI、TKDE等計(jì)算機(jī)頂級(jí)會(huì)議和期刊上。

背景介紹

近年來，圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks, GNNs）被廣泛應(yīng)用于智能城市計(jì)算。考慮到城市是一個(gè)復(fù)雜的系統(tǒng)，城市實(shí)體之間存在各種聯(lián)系，許多研究工作將城市建模為一個(gè)城市圖（Urban Graph），其中圖上的節(jié)點(diǎn)表示某種城市實(shí)體，邊表示實(shí)體間的某種關(guān)聯(lián)，并采用圖神經(jīng)網(wǎng)絡(luò)對(duì)城市圖進(jìn)行學(xué)習(xí)，以解決城市中各種下游任務(wù)。

然而，與一般的圖不同，城市圖經(jīng)常具有空間異配性（Spatial Heterophily），該特點(diǎn)限制了一般圖神經(jīng)網(wǎng)絡(luò)的性能。首先，圖的異配性（Heterophily）和同配性（Homophily）是兩個(gè)相對(duì)的概念。一般的GNN模型假設(shè)圖數(shù)據(jù)存在較好的同配性，相鄰節(jié)點(diǎn)具有相似的特點(diǎn)。而由于不同功能城市實(shí)體間的關(guān)聯(lián)復(fù)雜，城市圖往往具有異配性，即相連的節(jié)點(diǎn)可能不相似。比如，住宅區(qū)和工作場(chǎng)所之前經(jīng)常存在人口流動(dòng)關(guān)系，但顯然這兩種區(qū)域存在巨大差異。一般的同配圖神經(jīng)網(wǎng)絡(luò)（Homophilic GNNs）趨向于為相鄰節(jié)點(diǎn)產(chǎn)生相似的表示，可能會(huì)忽略重要的差異信息，限制了其在具有異配性的城市圖上的有效性。

在本文中，我們進(jìn)一步發(fā)現(xiàn)城市圖的鄰居異配通常還呈現(xiàn)出一定的空間多樣性，我們稱這種特點(diǎn)為空間異配性（Spatial Heterophily）。對(duì)一般的異配圖，鄰居與中心節(jié)點(diǎn)具有差異；而在城市圖上，位于不同地理位置的鄰居，對(duì)中心節(jié)點(diǎn)的差異分布是不同的，而不是均勻的，即差異存在空間多樣性（Spatial Diversity）。本文設(shè)計(jì)了一個(gè)空間多樣性評(píng)分指標(biāo)（Spatial Diversity Score）來描述城市圖的空間異配性。如圖1（a）所示，城市圖可能獲得較高的得分，說明圖上的鄰居差異分布存在空間多樣性，即空間異配性。

圖1 空間異配性分析

即使部分研究者已經(jīng)開始研究圖的異配性問題，但是現(xiàn)有的異配圖神經(jīng)網(wǎng)絡(luò)（Heterophilic GNNs）主要研究鄰居差異有限的異配圖，比如假設(shè)異配圖上僅有兩種類型的節(jié)點(diǎn)，而不能考慮城市圖上鄰居差異分布的空間多樣性。如圖1（b）所示，我們通過實(shí)驗(yàn)比較了不同GNN模型在一系列人工合成圖上的性能。當(dāng)逐漸加圖空間異配性（得分逐漸升高），現(xiàn)有異配圖神經(jīng)網(wǎng)絡(luò)無法保持優(yōu)良的性能。所以，設(shè)計(jì)一個(gè)能夠解決空間異配性的圖神經(jīng)網(wǎng)絡(luò)，更好地在城市圖上進(jìn)行表示學(xué)習(xí)，是十分有意義的。

為解決這一問題，本文提出了一個(gè)空間異配性感知圖神經(jīng)網(wǎng)絡(luò)（Spatial Heterophily Aware Graph Neural Network，SHGNN），模型結(jié)構(gòu)如圖2所示。該模型的設(shè)計(jì)受到了地理學(xué)第一定律 “任何事物都相關(guān)，但相近的事物關(guān)聯(lián)更緊密” 的啟發(fā)，即在城市中，我們能觀察到空間位置相近的城市實(shí)體通常具有相似的特點(diǎn)?；谶@一特性，本方法的核心思想是根據(jù)空間位置進(jìn)行鄰域劃分，將空間相近的鄰居分到一組，使得組內(nèi)鄰居與中心節(jié)點(diǎn)之間具有相近的差異分布，以夠緩解組內(nèi)鄰居異配的多樣性。在此基礎(chǔ)上，我們?cè)O(shè)計(jì)能夠同時(shí)建模差異信息的圖學(xué)習(xí)算法，對(duì)每個(gè)分組單獨(dú)處理，分而治之地解決城市圖的空間異配性。

在該工作中，我們基于飛槳實(shí)現(xiàn)了模型的搭建與訓(xùn)練。在輸入數(shù)據(jù)方面，本文使用飛槳的圖學(xué)習(xí)框架Paddle Graph Learning (PGL) 對(duì)城市圖進(jìn)行高效的構(gòu)建與存儲(chǔ)，包括節(jié)點(diǎn)之間的連接關(guān)系、節(jié)點(diǎn)空間坐標(biāo)，以及節(jié)點(diǎn)間的空間距離等信息。在模型方面，本文首先結(jié)合PGL的子圖提取接口與消息傳遞機(jī)制，便捷地實(shí)現(xiàn)了對(duì)不同空間位置的鄰居分別進(jìn)行消息聚合的操作；接著，基于飛槳的張量矩陣運(yùn)算，實(shí)現(xiàn)了城市圖上共性信息和差異信息的交互，增強(qiáng)城市圖的表示學(xué)習(xí)。基于飛槳?jiǎng)討B(tài)圖框架對(duì)模型進(jìn)行端到端訓(xùn)練后，本方法在不同的下游任務(wù)中表現(xiàn)出良好的性能。

方法框架

圖2 空間異配感知的圖神經(jīng)網(wǎng)絡(luò)

本文提出的空間異配性感知圖神經(jīng)網(wǎng)絡(luò)主要由兩個(gè)模塊組成，分別為旋轉(zhuǎn)-伸縮空間感知鄰域聚合（Rotation-Scaling Spatial Aggregation），以及異配感知的空間交互（Heterophily-Sensitive Spatial Interaction）。

旋轉(zhuǎn)-伸縮空間感知鄰域聚合

旋轉(zhuǎn)-伸縮空間感知鄰域聚合的首先對(duì)鄰居節(jié)點(diǎn)進(jìn)行劃分，將位置相近的鄰居分配到同一個(gè)空間組（Spatial Group），使得組內(nèi)鄰居對(duì)中心節(jié)點(diǎn)具有相近的差異分布，以緩解差異分布的多樣性。接著，我們分別對(duì)每個(gè)空間組的鄰居節(jié)點(diǎn)進(jìn)行特征聚合。該鄰域劃分和分組聚合，是以分而治之的方式解決空間異配性的基礎(chǔ)。

旋轉(zhuǎn)-伸縮雙視角空間劃分

圖3 旋轉(zhuǎn)-伸縮雙視角空間劃分示意圖

如圖3（a）和（b）所示，首先從方向維度（Direction View）和距離維度（Distance View）對(duì)每個(gè)中心節(jié)點(diǎn)周圍的地理空間進(jìn)行劃分，產(chǎn)生多個(gè)互不相交的子空間，并依據(jù)每個(gè)鄰居節(jié)點(diǎn)所處的子空間對(duì)其進(jìn)行分組。其中，我們?cè)诜较蚓S度下將地理空間劃分成若干個(gè)方向不同的扇區(qū)（Sector），在距離維度下將空間劃分成若干個(gè)距離不同的環(huán)（Ring）。我們基于飛槳實(shí)現(xiàn)了上述空間劃分函數(shù)：首先，利用飛槳PGL.Graph類的節(jié)點(diǎn)特征、邊特征訪問API獲取節(jié)點(diǎn)的空間坐標(biāo)和節(jié)點(diǎn)間的空間距離，并計(jì)算出每個(gè)鄰居節(jié)點(diǎn)所屬的扇區(qū)和環(huán)；接著，基于PGL.sampling的subgraph API可以便捷地將每個(gè)扇區(qū)、每個(gè)環(huán)定義為不同子圖，以此完成鄰居節(jié)點(diǎn)的劃分，代碼如下所示。

考慮到以下特殊情況：部分鄰居節(jié)點(diǎn)可能分布在兩個(gè)子空間的邊界上，無法確定屬于哪個(gè)分組；我們進(jìn)一步提出了旋轉(zhuǎn)-伸縮多重劃分的策略，在方向和距離維度上都進(jìn)行多重劃分，使得不同的劃分之間能夠發(fā)揮互補(bǔ)優(yōu)勢(shì)，如圖3（c）和（d）所示。在實(shí)現(xiàn)上，我們通過飛槳定義了多組扇區(qū)邊界的旋轉(zhuǎn)角度，以及多組環(huán)邊界的距離區(qū)間，多次調(diào)用空間劃分函數(shù)以實(shí)現(xiàn)多重空間劃分，代碼如下所示。

空間感知的鄰域聚合

完成空間劃分后，在鄰域內(nèi)進(jìn)行特征聚合與消息傳遞。一般的GNNs通常使用求和或求平均的方式進(jìn)行鄰域特征聚合，這將無法區(qū)分具有不同空間分布的鄰居，進(jìn)而導(dǎo)致具有空間多樣性的異配分布被混合到一起，難以處理。與此不同，本方法對(duì)每個(gè)空間分組內(nèi)的鄰居進(jìn)行分別聚合（group-wise aggregation），以實(shí)現(xiàn)對(duì)空間異配性的“分而治之”，該聚合過程如圖2（a）所示。基于劃分好的PGL子圖結(jié)構(gòu)，我們可以借助PGL的消息傳遞方法SEND-RECV簡(jiǎn)便地實(shí)現(xiàn)每個(gè)空間分組內(nèi)的消息傳遞與特征聚合。以方向維度下扇區(qū)內(nèi)的鄰居聚合為例，代碼如下所示。

異配感知的空間交互

在此基礎(chǔ)上，異配感知的空間交互模塊包含兩個(gè)可學(xué)習(xí)的核函數(shù)（Kernel Function），在城市圖上自適應(yīng)地提取和利用各個(gè)空間組到中心節(jié)點(diǎn)、以及空間組之間的共性信息（Commonality）和差異信息（Discrepancy）。

共性核函數(shù)

考慮到不同的空間分組都是中心節(jié)點(diǎn)的鄰居，利用鄰域共性知識(shí)（Common Knowledge）或相似特點(diǎn)已經(jīng)被廣泛驗(yàn)證有利于圖的表示學(xué)習(xí)。因此，我們首先設(shè)計(jì)了一個(gè)共性核函數(shù)（Commonality Kernel Function）來捕捉空間分組之間的共性信息，并利用共性信息增強(qiáng)各個(gè)分組的表示，如圖2（b）所示。以方向維度為例，我們基于飛槳張量計(jì)算，實(shí)現(xiàn)了對(duì)不同扇區(qū)之間的共性進(jìn)行度量，以及用共性信息對(duì)扇區(qū)表征進(jìn)行更新。

差異核函數(shù)

除了共性知識(shí)以外，對(duì)于具有異配性的城市圖，建模鄰居節(jié)點(diǎn)的差異信息更是至關(guān)重要的。因此，我們?cè)O(shè)計(jì)了另一個(gè)差異核函數(shù)（Discrepancy Kernel Function）來捕捉中心節(jié)點(diǎn)與空間組，以及各空間組之間的不相似之處，并類似地用差異信息來增強(qiáng)各空間分組表征。以方向維度為例，代碼實(shí)現(xiàn)如下。

注意力門控機(jī)制

在各種的應(yīng)用場(chǎng)景中，城市圖上的不同城市實(shí)體可能具有不同程度的空間異配性。所以，我們進(jìn)一步基于飛槳實(shí)現(xiàn)了一個(gè)注意力門控機(jī)制（Attentive Gate），通過端到端的方式自適應(yīng)地學(xué)習(xí)共性信息和差異信息對(duì)特定任務(wù)中節(jié)點(diǎn)表征學(xué)習(xí)的重要性，以對(duì)兩個(gè)分量進(jìn)行融合。

空間維度融合

最后，我們通過飛槳定義了一個(gè)可學(xué)習(xí)的比例參數(shù)，對(duì)方向維度和距離維度下獲得的鄰域表示進(jìn)行融合，并更新中心節(jié)點(diǎn)的表示。

在不同應(yīng)用中，可以采用不同的損失對(duì)網(wǎng)絡(luò)進(jìn)行優(yōu)化以得到節(jié)點(diǎn)的最終表示，并用于節(jié)點(diǎn)預(yù)測(cè)任務(wù)。

實(shí)驗(yàn)

我們?cè)谌齻€(gè)城市任務(wù)的三個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了在城市圖上考慮空間異配性的重要性，并證實(shí)了本方法的有效性。相比一般的同配圖神經(jīng)網(wǎng)絡(luò)、異配圖神經(jīng)網(wǎng)絡(luò)、空間圖神經(jīng)網(wǎng)絡(luò)，本方法能在不同的下游任務(wù)中獲得更好的性能。

表1 三個(gè)城市任務(wù)中的性能比較

此外，我們還通過豐富的消融實(shí)驗(yàn)驗(yàn)證了本方法各部分設(shè)計(jì)的作用，包括從兩個(gè)空間維度建模空間異配性、采用旋轉(zhuǎn)-伸縮多重劃分、以及同時(shí)捕捉圖上的共性與差異信息等。

圖4 消融實(shí)驗(yàn)

總結(jié)

本文研究了城市圖上獨(dú)特的空間異配性問題。一方面，我們?cè)O(shè)計(jì)了一個(gè)指標(biāo)來描述城市圖的空間異配性，并分析其對(duì)圖神經(jīng)網(wǎng)絡(luò)的影響；另一方面，我們基于飛槳圖學(xué)習(xí)框架實(shí)現(xiàn)了一種新的空間異配性感知的圖神經(jīng)網(wǎng)絡(luò)，能夠簡(jiǎn)便地按空間劃分對(duì)鄰居進(jìn)行分組處理，分而治之地解決城市圖的空間異配問題，并在多個(gè)城市任務(wù)中取得性能提升。

相關(guān)代碼已經(jīng)開源在PaddleSpatial時(shí)空計(jì)算平臺(tái)上。PaddleSpatial是基于百度飛槳深度學(xué)習(xí)框架開發(fā)的時(shí)空大數(shù)據(jù)計(jì)算工具和平臺(tái)，融合了百度領(lǐng)先的區(qū)域分割、時(shí)空遷移學(xué)習(xí)、時(shí)間序列預(yù)測(cè)等時(shí)空能力，可支持多種時(shí)空計(jì)算場(chǎng)景的應(yīng)用。

Paper

https://arxiv.org/abs/2306.12139

Code

https://github.com/PaddlePaddle/PaddleSpatial/tree/main/research/SHGNN