1093
2025-01-02 17:34:58（已編輯）
ICDE 2025 | PKU-DAIR實驗室論文被ICDE 2025
錄用兩篇
ICDE（International Conference on Data Engineering ）是數(shù)據(jù)庫領(lǐng)域影響力最高的國際學(xué)術(shù)會議之一,，也是CCF推薦的A類國際學(xué)術(shù)會議之一。第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ù)庫領(lǐng)域頂級會議ICDE 2025錄用論文兩篇,。
一、面向可擴展且高效的圖結(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)的方法,。然而，在實際應(yīng)用中,，GSL通常面臨以下兩大挑戰(zhàn)：
（1）可擴展性不足
GSL方法的擴展性受限于高計算復(fù)雜度和架構(gòu)耦合,。許多方法的運算復(fù)雜度高達(dá)O(N^2)（N為節(jié)點數(shù)），導(dǎo)致執(zhí)行時間長,、內(nèi)存消耗大,，尤其在大規(guī)模圖上表現(xiàn)明顯。此外,，結(jié)構(gòu)優(yōu)化模塊與特定GNN架構(gòu)緊密耦合,，難以與如SGC、SIGN等可擴展GNN兼容,，進一步限制了其適用性,。
（2）效率低下
現(xiàn)有的GSL方法效率偏低，實驗結(jié)果充分證明了這一點,。我們選用三個常用數(shù)據(jù)集（Cora,、Citeseer和Pubmed），并選取了NodeFormer,、CoGSL和SLAPS三個代表性GSL基線模型,，記錄了它們在上述數(shù)據(jù)集上的端到端訓(xùn)練時間。實驗結(jié)果（下圖）顯示,，即便在小規(guī)模圖數(shù)據(jù)上,，這些GSL方法的處理時間也顯著高于普通GNN的訓(xùn)練時間，并且隨著圖規(guī)模的增大,，執(zhí)行時間呈現(xiàn)快速增長趨勢,。同時，圖結(jié)構(gòu)優(yōu)化與圖學(xué)習(xí)模塊的強耦合性要求每次更換GNN架構(gòu)時都需重新訓(xùn)練,，進一步增加計算開銷,，降低靈活性。
圖1. 在三個數(shù)據(jù)集上的不同執(zhí)行時間
這些挑戰(zhàn)凸顯了在大規(guī)模圖學(xué)習(xí)任務(wù)中,，提升GSL方法可擴展性和效率的緊迫性,。
2. 方法
針對現(xiàn)有GSL方法在可擴展性和效率上的不足，我們提出了一種新方法,，稱為基于隨機游走的圖結(jié)構(gòu)學(xué)習(xí)（簡稱RWGSL）,。
為了解決可擴展性問題,，我們引入了鄰域采樣和隨機游走策略，避免了對圖中所有節(jié)點對進行大規(guī)模計算的需求,，從根本上降低了計算復(fù)雜度,，顯著緩解了高復(fù)雜度帶來的計算資源消耗。
為了解決效率問題,，我們將圖結(jié)構(gòu)優(yōu)化模塊與圖學(xué)習(xí)模塊解耦,，并將優(yōu)化過程前置到數(shù)據(jù)預(yù)處理階段。此設(shè)計具有兩方面優(yōu)勢：一方面,，可以利用多進程并行技術(shù)加速圖結(jié)構(gòu)優(yōu)化過程,；另一方面，優(yōu)化后的圖結(jié)構(gòu)與具體的GNN架構(gòu)無關(guān),，從而具備更高的通用性和靈活性,。
在圖結(jié)構(gòu)優(yōu)化模塊中，我們綜合考慮圖拓?fù)浣Y(jié)構(gòu)和監(jiān)督信號等多方面因素,，計算節(jié)點間的多維度相似性,，以進一步提升方法的有效性，確保優(yōu)化后的圖結(jié)構(gòu)能夠更好地支持下游任務(wù)的性能表現(xiàn),。下圖是我們的方法框架,。
圖2. RWGSL框架
3. 實驗結(jié)果
下表展示了RWGSL在三個中等規(guī)模數(shù)據(jù)集上的節(jié)點分類結(jié)果。為清晰起見,，我們標(biāo)注了每種基礎(chǔ)GNN模型在使用優(yōu)化后的圖結(jié)構(gòu)作為輸入時所帶來的準(zhǔn)確率提升,。此外，我們將每個數(shù)據(jù)集上的最佳結(jié)果用加粗表示,，次優(yōu)結(jié)果用下劃線標(biāo)注,。
表1. 中等規(guī)模數(shù)據(jù)集上的節(jié)點分類結(jié)果
實驗結(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é)合時，其表現(xiàn)可與其他先進的圖結(jié)構(gòu)學(xué)習(xí)方法相媲美,。此外,，這些結(jié)果進一步驗證了RWGSL的強泛化能力：優(yōu)化后的單一圖結(jié)構(gòu)能夠在所有基線模型中一致提升性能。
我們還在一個大規(guī)模數(shù)據(jù)集Ogbn-Products上進行了實驗,，其結(jié)果展示在下表的左兩列中,。
表2. 大規(guī)模數(shù)據(jù)集上的實驗結(jié)果
該表清楚地表明,，大多數(shù)圖結(jié)構(gòu)學(xué)習(xí)方法在處理大規(guī)模圖時面臨顯著挑戰(zhàn)。雖然NodeFormer在一定程度上展現(xiàn)了處理大規(guī)模圖的能力,，但其表現(xiàn)仍未達(dá)到最優(yōu),。相比之下，當(dāng)與可擴展的GNN結(jié)合時,，我們的方法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)勢,，能夠有效提升可擴展GNN的性能,。
4. 總結(jié)
通過對圖結(jié)構(gòu)學(xué)習(xí)方法的調(diào)研和實踐，我們發(fā)現(xiàn)現(xiàn)有工作普遍面臨兩個關(guān)鍵挑戰(zhàn)：可擴展性有限和效率低下,。具體而言,，這些方法在處理大規(guī)模圖數(shù)據(jù)集時常常遭遇運行時間過長和內(nèi)存消耗過大的問題。為了解決這些局限性,，我們提出了一種無參數(shù),、非參數(shù)學(xué)習(xí)型的圖結(jié)構(gòu)學(xué)習(xí)方法——RWGSL。
RWGSL通過在數(shù)據(jù)預(yù)處理階段優(yōu)化圖結(jié)構(gòu)并利用采樣策略縮小搜索空間,，顯著降低了計算復(fù)雜度,。其優(yōu)化后的圖結(jié)構(gòu)為圖學(xué)習(xí)模型提供了更高質(zhì)量的輸入，在多種圖類型上均實現(xiàn)了性能的持續(xù)提升,。
我們在多個數(shù)據(jù)集上進行了廣泛實驗,，驗證了RWGSL的有效性和可擴展性，為高效圖學(xué)習(xí)技術(shù)的進一步探索與發(fā)展提供了新的方向和動力,。
二,、通過數(shù)據(jù)選擇實現(xiàn)無需訓(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）已被提出作為密集計算問題的一種有前途的解決方案,。圖壓縮旨在通過學(xué)習(xí)合成圖結(jié)構(gòu)和節(jié)點屬性來壓縮大型原始圖,。作為關(guān)鍵設(shè)計，GC 利用中繼模型連接原始圖和合成圖,，方便兩個圖的比較和壓縮優(yōu)化,。遵循 GCond 的梯度匹配范式，HGCond是第一個提出的用于壓縮異構(gòu)圖的工作,。與 GC 不同,，它使用聚類信息進行超節(jié)點初始化,，并采用正交參數(shù)序列（OPS）策略來探索參數(shù)。雖然這種方法可以壓縮異構(gòu)圖,，但它仍然存在兩個局限性：
（1）低性能： 考慮到模型復(fù)雜性導(dǎo)致的過擬合問題,，HGCond 被迫僅使用最簡單的異構(gòu)圖模型作為圖壓縮的中繼模型，其壓縮精度與最先進的 (SOTA) HGNN之間存在很大差距,。即使使用先進的 HGNN 作為中繼模型,，性能也會變差。此外,，復(fù)雜的優(yōu)化問題使得 HGCond 的性能隨著壓縮圖的大小增加而下降或變平,。同時，HGCond還存在泛化性差的問題,。
（2）效率低： 遵循同構(gòu)圖壓縮方法 GCond 的范式,，HGCond 需要雙層優(yōu)化和嵌套循環(huán)來壓縮異構(gòu)圖。這種復(fù)雜的壓縮過程計算量大且耗時,。舉例來說,，在128 個 epoch下大約需要 1 小時（在單個 TITAN RTX GPU 上運行）才能將大規(guī)模數(shù)據(jù)集 AMiner壓縮到 1%。
為了解決上述兩個挑戰(zhàn),，本文提出了一種新的無需訓(xùn)練的異構(gòu)圖壓縮方法,，稱為 FreeHGC，用于從原始圖結(jié)構(gòu)中選擇和合成高質(zhì)量圖,，而無需模型訓(xùn)練過程,。與傳統(tǒng)的異構(gòu)圖壓縮不同，傳統(tǒng)的異構(gòu)圖壓縮通過迭代訓(xùn)練中繼模型來優(yōu)化合成圖和參數(shù),，如圖 1 所示,，我們提出的 FreeHGC 與模型無關(guān)，僅在預(yù)處理階段壓縮圖,。圖 1 還從四個關(guān)鍵標(biāo)準(zhǔn)突出了 FreeHGC 與 HGCond 相比的優(yōu)勢：有效性,、效率、靈活的壓縮率和泛化,。
圖1. 現(xiàn)有異構(gòu)圖壓縮方法與FreeHGC 的對比
2. 方法
FreeHGC執(zhí)行流程,。我們提出第一種無需訓(xùn)練的異構(gòu)圖壓縮方法——FreeHGC。如圖2所示,，我們的方法分為兩個部分：壓縮目標(biāo)類型節(jié)點和壓縮其他類型節(jié)點,。第一個部分使用感受野最大化函數(shù)和元路徑相似度最小化函數(shù),，基于圖結(jié)構(gòu)的直接影響和元路徑之間的間接影響來計算節(jié)點的重要性,。然后，F(xiàn)reeHGC將這兩個函數(shù)結(jié)合起來作為統(tǒng)一的數(shù)據(jù)選擇標(biāo)準(zhǔn)來選擇高質(zhì)量數(shù)據(jù),，在確保每個節(jié)點沿著不同的元路徑捕獲更豐富的圖結(jié)構(gòu)信息的同時,，最大化節(jié)點的影響力,。第二個部分使用鄰居重要性最大化函數(shù)來選擇重要的父類型節(jié)點，并使用信息損失最小化函數(shù)來合成葉類型節(jié)點,。重復(fù)上述過程,，直到獲得壓縮圖。
圖2. FreeHGC架構(gòu)
3. 實驗結(jié)果
實驗主要包含以下五個方面：（1）有效性,；(2) 可擴展性,；(3) 泛化性；(4) 壓縮數(shù)據(jù)分析,；(5)消融實驗,。這里選取具有代表性的有效性實驗和可擴展性實驗，其余實驗可參考論文,。
（1）與最先進的圖壓縮方法進行端到端比較：如表1所示,，在大多數(shù)壓縮率設(shè)置下，F(xiàn)reeHGC 的表現(xiàn)均優(yōu)于所有基線方法,。
表2. 節(jié)點分類預(yù)測任務(wù)的實驗結(jié)果
（2）可擴展性：如表2所示,，F(xiàn)reeHGC在不同的壓縮率下表現(xiàn)最佳，且準(zhǔn)確度逐漸提高,。
表3. 大規(guī)模數(shù)據(jù)集上的實驗結(jié)果
4. 總結(jié)
本文提出了一種新的無需訓(xùn)練的異構(gòu)圖壓縮方法——FreeHGC,。其目標(biāo)是從原始大圖中選取并合成高質(zhì)量節(jié)點，然后將其壓縮為無需訓(xùn)練的小圖,。節(jié)點分類任務(wù)上的實驗結(jié)果表明,，F(xiàn)reeHGC 可以在保持令人滿意的性能的同時顯著減小圖的大小，并且具有靈活壓縮率的優(yōu)勢,。此外,，實驗結(jié)果還表明我們的方法具有良好的泛化性和可擴展性。
北京大學(xué)數(shù)據(jù)與智能實驗室（Data And Intelligence Research Lab at Peking Univeristy,，PKU-DAIR實驗室）由北京大學(xué)計算機學(xué)院崔斌教授領(lǐng)導(dǎo),，長期從事數(shù)據(jù)庫系統(tǒng)、大數(shù)據(jù)管理與分析,、人工智能等領(lǐng)域的前沿研究,，在理論和技術(shù)創(chuàng)新以及系統(tǒng)研發(fā)上取得多項成果，已在國際頂級學(xué)術(shù)會議和期刊發(fā)表學(xué)術(shù)論文100余篇,，發(fā)布多個開源項目,。課題組同學(xué)曾數(shù)十次獲得包括CCF優(yōu)博、ACM中國優(yōu)博,、北大優(yōu)博,、微軟學(xué)者、蘋果獎學(xué)金、谷歌獎學(xué)金等榮譽,。PKU-DAIR實驗室持續(xù)與工業(yè)界展開卓有成效的合作,，與騰訊、阿里巴巴,、蘋果,、微軟、百度,、快手,、中興通訊等多家知名企業(yè)開展項目合作和前沿探索，解決實際問題,，進行科研成果的轉(zhuǎn)化落地,。
