Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

本文發表于:ICML22
推薦指數: #paper/???

問題背景:

異配圖的鄰接矩陣難以確定,以及異配圖的計算復雜度開銷大
可行的解決辦法:高通濾波+多跳鄰居,GPRGNN(pagerank一類，各階鄰居的權重不同,ACM-GCN（高低通濾波,H2GCN（應該復雜度很大） WRGAT，GGCN（signed message） LINKX（MLP+graph）

模型

請添加圖片描述

方法:兩個MLP學習X和A,拼接后卷積
$H_X^{(0)}=M\mathrm{LP}_1(X),~H_A^{(0)}=\mathrm{MLP}_2(A)$
仿照APPNP,再加上初等殘差:
$H^{(0)}=(1-\alpha)H_X^{(0)}+\alpha H_A^{(0)}$
$H^{(l)}=(1-\gamma)Z^{(l)}H^{(l)}+\gamma H^{(0)}+O^{(l)}$
我們可以得到下面優化問題:
$\min_{Z^{(l)}}\|H^{(l)}-(1-\gamma)Z^{(l)}H^{(l)}-\gamma H^{(0)}\|_{F}^{2}+\beta_{1}\|Z^{(l)}\|_{F}^{2}+\beta_{2}\|Z^{(l)}-\sum_{k=1}^{K}\lambda_{k}\hat{A}^{k}\|_{F}^{2}$
第一項是優化問題,第二項是F范數,第三項是逼近Z與多跳鄰居
可得Z:
$\begin{aligned} Z^{(l)*}& =\left[(1-\gamma)H^{(l)}(H^{(l)})^T+\beta_2\sum_{k=1}^K\lambda_k\hat{A}^k-\gamma(1-\gamma)H^{(0)}(H^{(l)})^T\right] \\ &\left[\left(1-\gamma\right)^2H^{(l)}(H^{(l)})^T+(\beta_1+\beta_2)I_n\right]^{-1} \end{aligned}$

計算加速

$H^{(l+1)}=(1-\gamma)Z^{(l)*}H^{(l)}+\gamma H^{(0)}.$
$\begin{gathered} H^{(l+1)}= (1-\gamma)H^{(l)}(H^{(l)})^TQ^{(l+1)}+\beta_2\sum_{k=1}^K\lambda_k\hat{A}^kQ^{(l+1)} \\ -\gamma(1-\gamma)H^{(0)}(H^{(l)})^TQ^{(l+1)}+\gamma H^{(0)} \end{gathered}$
其中, $\begin{aligned} Q^{(l+1)}=& \frac{1-\gamma}{\beta_1+\beta_2}H^{(l)}-\frac{1-\gamma}{(\beta_1+\beta_2)^2}H^{(l)}. \\ &\left[\frac1{(1-\gamma)^2}I_c+\frac1{\beta_1+\beta_2}(H^{(l)})^TH^{(l)}\right]^{-1}(H^{(l)})^TH^{(l)} \end{aligned}$

Group Effective

$\textbf{Definition 4. 1. }( \textbf{Grouping effect ( Li et al. , 2020) ) . Given}$ ,a set of nodes $\mathcal{V}=\{v_i\}_{i=1}^n$ , let $v_i\to v_j$ denote the condi-tion that $(1)\left\|x_i-x_j\right\|_2\to0$ and $\left \| \hat{a} _i^k- \hat{a} _j^k\right \| _2\to 0$ , $\forall k\in$ $[1, K] .$ A matrix $Z$ is said to have grouping effect if
$v_i\to v_j\Rightarrow|Z_{ip}-Z_{jp}|\to0,\forall1\leq p\leq n.$
對于任意兩個節點vi和vj，無論它們在圖中有多遠，如果它們共享相似的特征向量和局部結構，我們都可以得出結論:（1），它們將被給予相似的系數向量；（2），它們將在描述其他節點時扮演相似的角色；而（3），它們將得到相似的表示向量。另一方面，在具有異質性的圖中，相鄰的節點更有可能出現不同的情況，因此它們會得到不同的嵌入。此外，對于特征相似度較低的兩個節點，如果它們具有較高的結構相似性，則可以通過局部圖結構的正則化項來增強其表征

GloGNN++

之前的這個H矩陣是縱向的 attention，即節點和鄰居之間的。這里提出橫向的 attention，就是自身節點特征的重要性不同，采用常規的方法,增加一個對角矩陣作為每一維特征的attention

討論

1.GAT中的權重是自動學習的，缺乏可解釋性，但我們的模型中的Z(l)是來自一個精心設計良好的優化問題，并且有一個封閉的解
2.其次，GAT中的注意權值總是非負值，而我們的方法中的Z(l)允許有符號值。因此，GAT只使用低通卷積濾波器，而我們的方法同時結合了低通和高通濾波器。
3.對于每個節點，GAT對圖中所有節點執行的鄰域聚合計算代價昂貴，具有二次時間復雜度w.r.t.節點數。然而，我們的方法加速了聚合，并推導出了一個線性的時間復雜度

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/41449.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/41449.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/41449.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！