Heterophilous Distribution Propagation for Graph Neural Networks

推荐指数:2颗星
HDP不是聚集所有邻居信息,而是根据训练期间的伪标签自适应的将邻居分为同配和异配.并通过原型对比,垂直约束异配邻居分布

前人的问题

1.邻居划分的不足.已存在的方法要不不能区分同配和异配,要不简单的采用阈值去划分同配异配
2.以往的异配GNN仅仅是简单的邻居聚合
作者的贡献:
现有的异配gnn存在如上两个问题
我们提出了一种新的gnn来解决如上的问题

模型

必要的定义:

Y是nodelabel,$S^{tra},S^{tar},S^{struct}$分别代表训练集(train),结构编码的目标集合(target),和trust set对于可信对比原型向量损失

模型图:

疑问:

• $S^{target}$如何构建的
• ${\alpha }^l$为啥是${\mathbb{R}}^{N\times 1}$

方法

语义邻居划分

异配性评估

$$h^{\prime }=\frac{|\{(u,v)|(u,v)\in {\mathcal{E}}^{\prime }\wedge y_u=y_v\wedge u,v\in {\mathbf{S}}^{tra}\}|}{|\{(u,v)|(u,v)\in {\mathcal{E}}^{\prime }\wedge u,v\in {\mathbf{S}}^{tra}\}|},$$
$S^{tra}$表示训练集, E ′ ∈ { E , E 2 } \mathcal{E}^{\prime}\in\{\mathcal{E},\mathcal{E}^2\} E′∈{E,E2}表示一阶和二阶邻居.
由于同配比$h^{\prime }$不太准确,我们用超参去平衡他:$\lambda \in [0.8,1.2]$
$$\hat{h}=\lambda h^{\prime }$$

邻居划分:

软分配$\mathbf{Z}\in {\mathbb{R}}^{N\times K}$表示HDP预测的结果.
$${\mathbf{P}}_{uv}=\{\begin{array}{ll}{\mathbf{z}}_u{\mathbf{z}}_v^T,& (u,v)\in {\mathcal{E}}^{\prime },\\ 0,& \text{otherwise.}\end{array}$$

$$ϵ=\mathrm{TopK}(\mathbf{P},\hat{h}|{\mathcal{E}}^{\prime }|)$$
$\mathbf{TopK}(\mathbf{x},\mathbf{y})$意味着x的第y大个元素.然后,我们可以得到同配邻接矩阵和异配邻接矩阵:
$$\begin{array}{rl}{\mathbf{A}}_{uv}^{hm}& =\{\begin{array}{ll}1,& {\mathbf{P}}_{uv}\ge ϵ\wedge (u,v)\in {\mathcal{E}}^{\prime },\\ 0,& \text{otherwise.}\end{array}\\ {\mathbf{A}}_{uv}^{ht}& =\{\begin{array}{ll}1,& {\mathbf{P}}_{uv}<ϵ\wedge (u,v)\in {\mathcal{E}}^{\prime },\\ 0,& \text{otherwise.}\end{array}\end{array}$$

异配邻居模型

我们分三步对异配模型
1.构建节点的自我表征
2.建模每个节点的异配邻居分布
3.通过语义认知消息传播机制传播

自我表征的构建

我们语义结构编码作为属性节点的补充
1.构建结构嵌入
$${\hat{\mathbf{X}}}^{str}=\{\begin{array}{l}[0,0,...,1,...,0],i\in S^{\ast }\\ [0,0,...,0,...,0],i\notin S^{\ast }\end{array}$$
其中,${\mathbf{S}}^{tar}\subset {\mathbf{S}}^{tra}$
最终的嵌入通过随机游走计算而得到
$${\mathbf{X}}^{str}=({\mathbf{D}}^{-1}\mathbf{A}{)}^{\kappa }{\hat{\mathbf{X}}}^{str},$$
节点的自我表征可以通过简单的MLP,建模节点特征和结构特征得到:
$${\mathbf{H}}^{ego}=\mathrm{MLP}([\mathbf{X}\Vert {\mathbf{X}}^{str}])$$
其中,$[\cdot ||\cdot ]$表示拼接操作

异配邻居分布

$${\mathbf{H}}^{nb}={\mathbf{D}}^{ht}{}^{-1}{\mathbf{A}}^{ht}{\mathbf{H}}^{ego}.$$
其中,$D^{ht}$:${\mathbf{D}}_{ii}^{ht}={\sum }_j{\mathbf{A}}_{ij}^{ht}$

语义消息传播机制:

我们引入了语义消息传播:SMP(Semantic-aware Message Passing)
$$\begin{array}{rl}& {\tilde{\mathbf{H}}}^l={\mathbf{D}}^{h{m}^{-1}}{\mathbf{A}}^{hm}{\mathbf{H}}^{(l-1)},\\ & {\alpha }^l=f_{{\phi }^l}([{\mathbf{H}}^0\Vert {\tilde{\mathbf{H}}}^l]),\\ & {\mathbf{H}}^l={\alpha }^l{\mathbf{H}}^0+(1-{\alpha }^l)){\tilde{\mathbf{H}}}^l\end{array}$$
其中,${\alpha }^l\in {\mathbb{R}}^{N\times 1}$被权重学习器学习得到. #question 为啥是N*1维度?
$${\mathbf{H}}^{ht}=\mathrm{SMP}({\mathbf{H}}^{nb},l^{ht})$$$${\mathbf{H}}^{hm}=\mathrm{SMP}({\mathbf{H}}^{ego},l^{hm})$$

我们可以得到最终特征:
$$\mathbf{H}=[{\mathbf{H}}^{hm}\Vert {\mathbf{H}}^{ht}].$$$$\mathbf{Z}=f_{\psi }(\mathbf{H}),\hat{\mathbf{Y}}=\arg \max (\mathbf{Z}).$$

模型训练

模型初始化:

$${\mathbf{X}}^{nb}=\hat{\mathbf{A}}\mathbf{X}$$$${\mathbf{X}}^{all}=[\mathbf{X}\Vert {\mathbf{X}}^{nb}\Vert {\mathbf{X}}^{str}]$$
$$\mathbf{Z}={\mathrm{MLP}}^{init}({\mathbf{X}}^{all})$$

模型优化

$${\mathcal{L}}^{ce}=\mathrm{CE}(\mathbf{Z},\mathbf{Y}),$$ S t r u = { v i ∣ Z i m a x ≥ δ } \mathbf{S}^{tru}=\{v_i|\mathbf{Z}_i^{max}\geq\delta\} Stru={vi​∣Zimax​≥δ}$$\delta =\mathrm{TopK}({\mathbf{Z}}^{max},\rho |\mathcal{V}|)$$
其中,$\delta =\mathrm{TopK}({\mathbf{Z}}^{max},\rho |\mathcal{V}|)$
我们可以得到原型向量:
c j = 1 ∣ S j t r u ∣ ∑ v i ∈ S j t r u h i e g o , S i t r u = { v i ∣ v i ∈ S t r u ∧ Y ^ i = j } . \begin{gathered} \mathbf{c}_{j} =\frac1{|\mathbf{S}_j^{tru}|}\sum_{v_i\in\mathbf{S}_j^{tru}}\mathbf{h}_i^{ego}, \\ \mathbf{S}_{i}^{tru} =\{v_i|v_i\in\mathbf{S}^{tru}\wedge\widehat{\mathbf{Y}}_i=j\}. \end{gathered} cj​=∣Sjtru​∣1​vi​∈Sjtru​∑​hiego​,Sitru​={vi​∣vi​∈Stru∧Y i​=j}.​
最终得到原型向量损失:
$${\mathcal{L}}^{tpc}=-\sum _{v_i\in {\mathbf{S}}^{tru}}\log \frac{\exp (s({\mathbf{h}}_i^{ego},{\mathbf{c}}_j)/\tau )}{{\sum }_{k=1}^K\exp ([s({\mathbf{h}}_i^{ego},{\mathbf{c}}_k){]}_{+}/\tau ))},$$
其中,$s({\mathbf{h}}_i^{ego},{\mathbf{c}}_j)=\frac{{\mathbf{h}}_i^{ego}\cdot {\mathbf{c}}_j}{|{\mathbf{h}}_i^{ego}||{\mathbf{c}}_j|}.$

整体损失函数:
$$\mathcal{L}={\mathcal{L}}^{ce}+\beta {\mathcal{L}}^{tpc}$$

结果还阔以

总结:

貌似提供了一种自适应阈值的方式,但是我仍然有如下的问题:
1.引入了超参$\lambda$去放大缩小阈值.其实仍没有解决阈值问题
2.有点没读懂target是如何划分的