論文標題：It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
論文發表：剛發表到Arixv，2025年5月
論文領域：圖神經網絡，圖重連技術
論文代碼：https://github.com/harel147/REFine
論文背景：
圖神經網絡（GNNs）擅長分析圖結構數據，但在異親圖上存在困難，其中連接的節點往往屬於不同的類。雖然這一挑戰通常是通過專門的GNN架構來解決的，但在這種情況下，圖形重新佈線仍然是一種未充分探索的策略。我們提供了連接邊緣同態性、GNN嵌入平滑度和節點分類性能的理論基礎，激發了增強同態性的需求。在此基礎上，我們引入了一個重佈線框架，該框架使用參考圖增加了圖的同態性，並從理論上保證了重佈線圖的同態性。為了擴大適用性，我們提出了一種標籤驅動的擴散方法，用於從節點特徵和訓練標籤構造同態參考圖。通過大量的仿真，分析了原始圖和參考圖的同態性對重佈線圖同態性和下游GNN性能的影響。我們在11個實際數據集上對我們的方法進行了評估，結果表明，該方法優於現有的重佈線技術和異親圖專用GNN，在保持高效性和可擴展性的同時提高了節點分類精度。
本文建立了邊緣同質性、圖上學習的 GNN 嵌入的平滑度和 GNN 性能之間的理論和經驗聯繫。
理論分析表明，在低同質關係的圖中，允許準確分類的學習節點嵌入在圖上無法平滑。這會與 GNN 的消息傳遞機制產生衝突，在許多情況下，GNN 傾向於沿圖結構平滑嵌入。
為了系統地控制圖的同質率，採用來源於流形學習領域的擴散過程。通過利用未充分利用的信息（節點特徵和節點標籤）來構建同質圖作為參考。
本文提出了幾種類型的圖同質度量來衡量圖中標籤相關性的不同方面，包括：邊同質性，節點同質性，類同質性，鄰居節點同質性。特別關注邊同質率，是最簡單和最常見的度量，量化了連接具有相同標籤的節點的邊的比比例。
目前研究領域處理異質圖結構的GNN架構：MixHop通過聚合多跳鄰居的信息來擴展GNN，GPRGNN引入了廣義PageRank權重的自適應學習機制，H2GCN通過引入高階連接模式來進一步完善消息傳遞，CAGNN使用共享混合器自適應地整合鄰居信息。
整個圖的邊同質率可以定義為
實驗研究顯示出，GNN在同質圖上的表現優於異質圖，這是標準GNN架構導致的。
迪利克雷能量，該度量捕獲了嵌入在整個圖結構中變化的平滑程度，其中小值表示連接節點之間的小變化（平滑度），大值表示連接節點之間的大變化（波動度）。
GNN 中的信息傳遞機制傾向於產生平滑的節點嵌入。GNN 本質上會降低平滑度項$tr(Z^T, LZ)$，這並不總是有益的，並且可能導致過度平滑。
定理1：
上面的公式的不等式的右側為線性可分離嵌入的平滑度的下限。較高的同質性導致較小的下限，使 GNN 更容易產生平滑和線性可分離的嵌入。相反，在異性圖中，增加的下界增加了消息傳遞引起的平滑可能損害線性可分離性的風險。
圖的同質性越大，GNN學習線性可分離、因而更有效的節點嵌入的潛力就越大。
定義參考圖為Gr=（v，Er），通過基於Er的邊來添加或刪除k條邊來修改邊集，定義了E(k)
其中Sk是k條邊的隨機子集，k>0表示添加邊，k<0表示刪除邊。
定義命題
所以有，
當滿足條件時，基於參考圖的邊加法在期望中提高了同質性。
當k<0的時，圖重連g(k)是通過刪除從 ℰ∩ℰ_r^c 隨機選擇的|k|邊獲得。
當滿足條件時，基於參考圖的邊刪除，提高了期望同質性。
使用邊添加進行重新連線對康奈爾數據集的影響，其中每列表示使用不同的 $g_{r,p}$ 具有不同同質性（由不同 p 值控制）的重新佈線。
邊刪除對Cora數據集的影響
當滿足條件時，去除邊會增加同質性（紅線下方的綠線），否則會降低。然而，較高的同質性並不總是能提高 GCN 性能，因為可能會發生過度擠壓。
假設特徵空間提供了與標籤一致的有意義的相似性度量，則基於特徵親和力的參考圖應該是同性的。我們的關鍵思想是將節點特徵與訓練標籤相結合，以構建一個參考圖，該參考圖不僅是同性的，而且可以推廣到未標記的節點。
本文引入擴散方法，通過由完全可用的節點特徵 𝐗 構建的圖，將標籤信息傳播到未標記的節點，從而“完成”缺失的標籤。該方法捕獲特徵和標籤之間的共享結構，從而產生比大多數情況下僅由其構 𝐗 造的參考圖具有更高的同質性。
本圖重連算法的步驟：
構建參考圖Gr的第一步是基於節點特徵向量構建親和矩陣WD，對於i，j ∈ {1,2,..n}，d(,)是距離度量，ϵ是控制親和率尺度的超參數。
其次，使用標準的內核歸一化手段，對親和率矩陣進行歸一化操作，得到數據核D。所以可以計算對角線矩陣D1，其對角線元素由WD的總和組成，使用它來獲得中間矩陣D’，計算另一個由於D' 和D2組成的對角矩陣，使用歸一化步驟
對於基於節點標籤的親和性矩陣，定義一個二進制矩陣
同樣，$W_p$可以基於具有標籤親和力的圖迴歸的連續標籤來構造，使用應用於$W_D$的相同歸一化對矩陣$W_p$進行歸一化。產生標籤核P。
對於上述的P和D的乘積，$\tau = PDP$，是一個以標籤為驅動的擴散過程，包含三個步驟：使用可用標籤在類內傳播；通過所有節點的節點特徵相似性傳播；最終通過標籤傳播。
所以可以根據 $\tau$ 來定義參考圖的邊集合，因為$\tau$的元素是連續的，所以可以將其裁剪來獲得與未加權圖的鄰接矩陣相對應的二進制矩陣。首先計算$\tau$的每一行的平局值。給出公式得到
$$\mu_i = \frac{1}{n}\sum_{j=1}^n\tau(i,j) $$
依據該平均值$\mu$可以得到裁剪的內核
可擴展性
因為本算法依賴於核操作，其計算成本巨大而不適應大型圖。為了確保可擴展性，使用METIS算法來將圖g聚類為N個子類。$N=\frac{|V|}{c}$，C是聚類大小，為超參數。每個集群$g_l$根據其參考圖獨立重新連接，最終通過合併所有的連接聚類來重建整個圖，同時保留原始圖的聚類間的邊。
REFine算法偽代碼為
對比算法：SDRF，FoSR，BORF算法，
節點分類任務的實驗數據為
因為算法是基於同質性的，所以對於異質圖來說也有很大的幫助，算法在異質圖神經網絡框架的上的意義，採用框架 MixHop，H2GCN，GPRGNN，OrderedGNN，和本算法基於標準的GNN（GCN，GATv2，APPNP三個）的圖重連算法。實驗數據如下
1，同質性和算法的提升
發現同質率越低的數據，本算法加入後對GNN的測試準確度提升越大。
2，只使用訓練標籤來做親和性矩陣
即是意味著$\tau = P$使用來替代$\tau = PDP$，測試準確率隨著 |k| 增加而下降，從實驗發現僅使用訓練標籤而不考慮數據時對未標記節點的泛化能力有限。
數據為
3，聚類大小超參數
較大的聚類大小會導致性能有所提高，運行時間增加。
主要是針對異質圖的圖重連算法，使用三個技術的組合，METIS聚類降低整個圖的計算量為一個個的小圖；使用親和矩陣來構建參考圖；聚類之間的圖重連算法。
圖重連算法開始向異質圖來做，通用領域的baseline已經夠高了，找圖神經網路的子方向來挖掘。
此內容由慣性聚合(RSS閱讀器)自動聚合整理，僅供閱讀參考。 原文來自 — 版權歸原作者所有。