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)}$$
我们可以得到下面优化问题:
$$\underset{Z^{(l)}}{\min }\Vert H^{(l)}-(1-\gamma )Z^{(l)}{H}^{(l)}-\gamma H^{(0)}{\Vert }_F^2+{\beta }_1\Vert Z^{(l)}{\Vert }_F^2+{\beta }_2\Vert Z^{(l)}-\sum _{k=1}^K{\lambda }_k{\hat{A}}^k{\Vert }_F^2$$
第一项是优化问题,第二项是F范数,第三项是逼近Z与多跳邻居
可得Z:
$$\begin{array}{rl}{Z}^{(l)\ast }& =\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)}^2{H}^{(l)}(H^{(l)}{)}^T+({\beta }_1+{\beta }_2)I_n\right]}^{-1}\end{array}$$

计算加速

$$H^{(l+1)}=(1-\gamma )Z^{(l)\ast }{H}^{(l)}+\gamma H^{(0)}.$$
$$\begin{array}{c}{H}^{(l+1)}=(1-\gamma )H^{(l)}(H^{(l)}{)}^T{Q}^{(l+1)}+{\beta }_2\sum _{k=1}^K{\lambda }_k{\hat{A}}^k{Q}^{(l+1)}\\ -\gamma (1-\gamma )H^{(0)}(H^{(l)}{)}^T{Q}^{(l+1)}+\gamma H^{(0)}\end{array}$$
其中,$$\begin{array}{rl}{Q}^{(l+1)}=& \frac{1-\gamma }{{\beta }_1+{\beta }_2}{H}^{(l)}-\frac{1-\gamma }{({\beta }_1+{\beta }_2{)}^2}{H}^{(l)}.\\ & {\left[\frac{1}{(1-\gamma {)}^2}{I}_c+\frac{1}{{\beta }_1+{\beta }_2}(H^{(l)}{)}^T{H}^{(l)}\right]}^{-1}(H^{(l)}{)}^T{H}^{(l)}\end{array}$$

Group Effective

$\text{Definition 4. 1. }(\text{Grouping effect ( Li et al. , 2020) ) . Given}$,a set of nodes V = { v i } i = 1 n \mathcal{V}=\{v_i\}_{i=1}^n V={vi​}i=1n​, let $v_i\to v_j$ denote the condi-tion that $(1){\Vert x_i-x_j\Vert }_2\to 0$ and $(2){\Vert {\hat{a}}_i^k-{\hat{a}}_j^k\Vert }_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}|\to 0,\forall 1\le p\le 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.节点数。然而，我们的方法加速了聚合，并推导出了一个线性的时间复杂度