ICDE 2025 | PKU-DAIR實(shí)驗(yàn)室論文被ICDE 2025

錄用兩篇

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

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

一,、面向可擴(kuò)展且高效的圖結(jié)構(gòu)學(xué)習(xí)

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

1. 引言

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

（1）可擴(kuò)展性不足

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

（2）效率低下

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

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

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

2. 方法

針對(duì)現(xiàn)有GSL方法在可擴(kuò)展性和效率上的不足,，我們提出了一種新方法,，稱為基于隨機(jī)游走的圖結(jié)構(gòu)學(xué)習(xí)（簡(jiǎn)稱RWGSL）。

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

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

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

圖2. RWGSL框架

3. 實(shí)驗(yàn)結(jié)果

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

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

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

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

表2. 大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

4. 總結(jié)

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

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

我們?cè)诙鄠€(gè)數(shù)據(jù)集上進(jìn)行了廣泛實(shí)驗(yàn)，驗(yàn)證了RWGSL的有效性和可擴(kuò)展性,，為高效圖學(xué)習(xí)技術(shù)的進(jìn)一步探索與發(fā)展提供了新的方向和動(dòng)力,。

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

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

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

1. 引言

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

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

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

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

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

2. 方法

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

圖2. FreeHGC架構(gòu)

3. 實(shí)驗(yàn)結(jié)果

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

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

表2. 節(jié)點(diǎn)分類預(yù)測(cè)任務(wù)的實(shí)驗(yàn)結(jié)果

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

表3. 大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

4. 總結(jié)

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

實(shí)驗(yàn)室簡(jiǎn)介

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