ICDE 2025 | PKU-DAIR實驗室論文被ICDE 2025

錄用兩篇

ICDE（International Conference on Data Engineering ）是數(shù)據(jù)庫領域影響力最高的國際學術會議之一，也是CCF推薦的A類國際學術會議之一。第41屆IEEE國際數(shù)據(jù)工程大會（ICDE）將于2025年5月19日-23日在中國香港舉行。

PKU-DAIR實驗室論文《 Towards Scalable and Efficient Graph Structure Learning 》和《Training-free Heterogeneous Graph Condensation via Data Selection》被數(shù)據(jù)庫領域頂級會議ICDE 2025錄用論文兩篇。

一、面向可擴展且高效的圖結構學習

作者：Siqi Shen, Wentao Zhang, Chengshuo Du ,  Chong Chen, Fangcheng  Fu, Yingxia  Shao,  Bin Cui

1. 引言

圖結構學習（Graph Structure Learning，GSL）是一類提升圖結構質(zhì)量和圖神經(jīng)網(wǎng)絡（GNN）下游任務表現(xiàn)的方法。然而，在實際應用中，GSL通常面臨以下兩大挑戰(zhàn)：

（1）可擴展性不足

GSL方法的擴展性受限于高計算復雜度和架構耦合。許多方法的運算復雜度高達O(N^2)（N為節(jié)點數(shù)），導致執(zhí)行時間長、內(nèi)存消耗大，尤其在大規(guī)模圖上表現(xiàn)明顯。此外，結構優(yōu)化模塊與特定GNN架構緊密耦合，難以與如SGC、SIGN等可擴展GNN兼容，進一步限制了其適用性。

（2）效率低下

現(xiàn)有的GSL方法效率偏低，實驗結果充分證明了這一點。我們選用三個常用數(shù)據(jù)集（Cora、Citeseer和Pubmed），并選取了NodeFormer、CoGSL和SLAPS三個代表性GSL基線模型，記錄了它們在上述數(shù)據(jù)集上的端到端訓練時間。實驗結果（下圖）顯示，即便在小規(guī)模圖數(shù)據(jù)上，這些GSL方法的處理時間也顯著高于普通GNN的訓練時間，并且隨著圖規(guī)模的增大，執(zhí)行時間呈現(xiàn)快速增長趨勢。同時，圖結構優(yōu)化與圖學習模塊的強耦合性要求每次更換GNN架構時都需重新訓練，進一步增加計算開銷，降低靈活性。

                                            圖1. 在三個數(shù)據(jù)集上的不同執(zhí)行時間

這些挑戰(zhàn)凸顯了在大規(guī)模圖學習任務中，提升GSL方法可擴展性和效率的緊迫性。

2. 方法

針對現(xiàn)有GSL方法在可擴展性和效率上的不足，我們提出了一種新方法，稱為基于隨機游走的圖結構學習（簡稱RWGSL）。

為了解決可擴展性問題，我們引入了鄰域采樣和隨機游走策略，避免了對圖中所有節(jié)點對進行大規(guī)模計算的需求，從根本上降低了計算復雜度，顯著緩解了高復雜度帶來的計算資源消耗。

為了解決效率問題，我們將圖結構優(yōu)化模塊與圖學習模塊解耦，并將優(yōu)化過程前置到數(shù)據(jù)預處理階段。此設計具有兩方面優(yōu)勢：一方面，可以利用多進程并行技術加速圖結構優(yōu)化過程；另一方面，優(yōu)化后的圖結構與具體的GNN架構無關，從而具備更高的通用性和靈活性。

在圖結構優(yōu)化模塊中，我們綜合考慮圖拓撲結構和監(jiān)督信號等多方面因素，計算節(jié)點間的多維度相似性，以進一步提升方法的有效性，確保優(yōu)化后的圖結構能夠更好地支持下游任務的性能表現(xiàn)。下圖是我們的方法框架。

圖2. RWGSL框架

3. 實驗結果

下表展示了RWGSL在三個中等規(guī)模數(shù)據(jù)集上的節(jié)點分類結果。為清晰起見，我們標注了每種基礎GNN模型在使用優(yōu)化后的圖結構作為輸入時所帶來的準確率提升。此外，我們將每個數(shù)據(jù)集上的最佳結果用加粗表示，次優(yōu)結果用下劃線標注。

表1. 中等規(guī)模數(shù)據(jù)集上的節(jié)點分類結果

實驗結果表明，與原始圖相比，使用RWGSL處理后的圖能夠顯著提升分類準確率。具體而言，RWGSL將基礎GCN的分類準確率在Cora數(shù)據(jù)集上提升了3.0%，在Citeseer數(shù)據(jù)集上提升了2.6%，在Pubmed數(shù)據(jù)集上提升了2.1%。值得注意的是，當RWGSL與GCN結合時，其表現(xiàn)可與其他先進的圖結構學習方法相媲美。此外，這些結果進一步驗證了RWGSL的強泛化能力：優(yōu)化后的單一圖結構能夠在所有基線模型中一致提升性能。

我們還在一個大規(guī)模數(shù)據(jù)集Ogbn-Products上進行了實驗，其結果展示在下表的左兩列中。

表2. 大規(guī)模數(shù)據(jù)集上的實驗結果

該表清楚地表明，大多數(shù)圖結構學習方法在處理大規(guī)模圖時面臨顯著挑戰(zhàn)。雖然NodeFormer在一定程度上展現(xiàn)了處理大規(guī)模圖的能力，但其表現(xiàn)仍未達到最優(yōu)。相比之下，當與可擴展的GNN結合時，我們的方法RWGSL能夠有效優(yōu)化大規(guī)模圖的拓撲結構，展現(xiàn)出令人期待的結果。具體而言，RWGSL將SGC的分類準確率提升了4.0%，SIGN提升了1.7%，GraphSAGE提升了1.3%，GraphSAINT提升了1.6%。這些結果表明，RWGSL在處理大規(guī)模圖結構優(yōu)化方面具有顯著優(yōu)勢，能夠有效提升可擴展GNN的性能。

4. 總結

通過對圖結構學習方法的調(diào)研和實踐，我們發(fā)現(xiàn)現(xiàn)有工作普遍面臨兩個關鍵挑戰(zhàn)：可擴展性有限和效率低下。具體而言，這些方法在處理大規(guī)模圖數(shù)據(jù)集時常常遭遇運行時間過長和內(nèi)存消耗過大的問題。為了解決這些局限性，我們提出了一種無參數(shù)、非參數(shù)學習型的圖結構學習方法——RWGSL。

RWGSL通過在數(shù)據(jù)預處理階段優(yōu)化圖結構并利用采樣策略縮小搜索空間，顯著降低了計算復雜度。其優(yōu)化后的圖結構為圖學習模型提供了更高質(zhì)量的輸入，在多種圖類型上均實現(xiàn)了性能的持續(xù)提升。

我們在多個數(shù)據(jù)集上進行了廣泛實驗，驗證了RWGSL的有效性和可擴展性，為高效圖學習技術的進一步探索與發(fā)展提供了新的方向和動力。

二、通過數(shù)據(jù)選擇實現(xiàn)無需訓練的異構圖壓縮

作者：Yuxuan Liang, Wentao Zhang, Xinyi Gao, Ling Yang, Chong Chen, Hongzhi Yin, Yunhai Tong, Bin Cui

論文鏈接：https://arxiv.org/abs/2412.16250

1. 引言

最近，圖壓縮（GC）已被提出作為密集計算問題的一種有前途的解決方案。圖壓縮旨在通過學習合成圖結構和節(jié)點屬性來壓縮大型原始圖。作為關鍵設計，GC 利用中繼模型連接原始圖和合成圖，方便兩個圖的比較和壓縮優(yōu)化。遵循 GCond 的梯度匹配范式，HGCond是第一個提出的用于壓縮異構圖的工作。與 GC 不同，它使用聚類信息進行超節(jié)點初始化，并采用正交參數(shù)序列（OPS）策略來探索參數(shù)。雖然這種方法可以壓縮異構圖，但它仍然存在兩個局限性：

（1）低性能： 考慮到模型復雜性導致的過擬合問題，HGCond 被迫僅使用最簡單的異構圖模型作為圖壓縮的中繼模型，其壓縮精度與最先進的 (SOTA) HGNN之間存在很大差距。即使使用先進的 HGNN 作為中繼模型，性能也會變差。此外，復雜的優(yōu)化問題使得 HGCond 的性能隨著壓縮圖的大小增加而下降或變平。同時，HGCond還存在泛化性差的問題。

（2）效率低： 遵循同構圖壓縮方法 GCond 的范式，HGCond 需要雙層優(yōu)化和嵌套循環(huán)來壓縮異構圖。這種復雜的壓縮過程計算量大且耗時。舉例來說，在128 個 epoch下大約需要 1 小時（在單個 TITAN RTX GPU 上運行）才能將大規(guī)模數(shù)據(jù)集 AMiner壓縮到 1%。

為了解決上述兩個挑戰(zhàn)，本文提出了一種新的無需訓練的異構圖壓縮方法，稱為 FreeHGC，用于從原始圖結構中選擇和合成高質(zhì)量圖，而無需模型訓練過程。與傳統(tǒng)的異構圖壓縮不同，傳統(tǒng)的異構圖壓縮通過迭代訓練中繼模型來優(yōu)化合成圖和參數(shù)，如圖 1 所示，我們提出的 FreeHGC 與模型無關，僅在預處理階段壓縮圖。圖 1 還從四個關鍵標準突出了 FreeHGC 與 HGCond 相比的優(yōu)勢：有效性、效率、靈活的壓縮率和泛化。

圖1. 現(xiàn)有異構圖壓縮方法與FreeHGC 的對比

2. 方法

FreeHGC執(zhí)行流程。我們提出第一種無需訓練的異構圖壓縮方法——FreeHGC。如圖2所示，我們的方法分為兩個部分：壓縮目標類型節(jié)點和壓縮其他類型節(jié)點。第一個部分使用感受野最大化函數(shù)和元路徑相似度最小化函數(shù)，基于圖結構的直接影響和元路徑之間的間接影響來計算節(jié)點的重要性。然后，F(xiàn)reeHGC將這兩個函數(shù)結合起來作為統(tǒng)一的數(shù)據(jù)選擇標準來選擇高質(zhì)量數(shù)據(jù)，在確保每個節(jié)點沿著不同的元路徑捕獲更豐富的圖結構信息的同時，最大化節(jié)點的影響力。第二個部分使用鄰居重要性最大化函數(shù)來選擇重要的父類型節(jié)點，并使用信息損失最小化函數(shù)來合成葉類型節(jié)點。重復上述過程，直到獲得壓縮圖。

圖2. FreeHGC架構

3. 實驗結果

實驗主要包含以下五個方面：（1）有效性；(2) 可擴展性；(3) 泛化性；(4) 壓縮數(shù)據(jù)分析；(5)消融實驗。這里選取具有代表性的有效性實驗和可擴展性實驗，其余實驗可參考論文。

（1）與最先進的圖壓縮方法進行端到端比較：如表1所示，在大多數(shù)壓縮率設置下，F(xiàn)reeHGC 的表現(xiàn)均優(yōu)于所有基線方法。

表2. 節(jié)點分類預測任務的實驗結果

（2）可擴展性：如表2所示，F(xiàn)reeHGC在不同的壓縮率下表現(xiàn)最佳，且準確度逐漸提高。

表3. 大規(guī)模數(shù)據(jù)集上的實驗結果

4. 總結

本文提出了一種新的無需訓練的異構圖壓縮方法——FreeHGC。其目標是從原始大圖中選取并合成高質(zhì)量節(jié)點，然后將其壓縮為無需訓練的小圖。節(jié)點分類任務上的實驗結果表明，F(xiàn)reeHGC 可以在保持令人滿意的性能的同時顯著減小圖的大小，并且具有靈活壓縮率的優(yōu)勢。此外，實驗結果還表明我們的方法具有良好的泛化性和可擴展性。

實驗室簡介

北京大學數(shù)據(jù)與智能實驗室（Data And Intelligence Research Lab at Peking Univeristy，PKU-DAIR實驗室）由北京大學計算機學院崔斌教授領導，長期從事數(shù)據(jù)庫系統(tǒng)、大數(shù)據(jù)管理與分析、人工智能等領域的前沿研究，在理論和技術創(chuàng)新以及系統(tǒng)研發(fā)上取得多項成果，已在國際頂級學術會議和期刊發(fā)表學術論文100余篇，發(fā)布多個開源項目。課題組同學曾數(shù)十次獲得包括CCF優(yōu)博、ACM中國優(yōu)博、北大優(yōu)博、微軟學者、蘋果獎學金、谷歌獎學金等榮譽。PKU-DAIR實驗室持續(xù)與工業(yè)界展開卓有成效的合作，與騰訊、阿里巴巴、蘋果、微軟、百度、快手、中興通訊等多家知名企業(yè)開展項目合作和前沿探索，解決實際問題，進行科研成果的轉(zhuǎn)化落地。