球类网站如何做宣传,工程项目管理软件哪个好,怎样创建网站信息平台,怀化建设局网站本文发表于:ICML22 推荐指数: #paper/⭐⭐⭐
问题背景:
异配图的邻接矩阵难以确定,以及异配图的计算复杂度开销大 可行的解决办法:高通滤波多跳邻居,GPRGNN(pagerank一类#xff0c;各阶邻居的权重不同,ACM-GCN#xff08;高低通滤波,H2GCN#xff08;应该复杂度很大…本文发表于:ICML22 推荐指数: #paper/⭐⭐⭐
问题背景:
异配图的邻接矩阵难以确定,以及异配图的计算复杂度开销大 可行的解决办法:高通滤波多跳邻居,GPRGNN(pagerank一类各阶邻居的权重不同,ACM-GCN高低通滤波,H2GCN应该复杂度很大 WRGATGGCNsigned message LINKXMLPgraph
模型 方法:两个MLP学习X和A,拼接后卷积 H X ( 0 ) M L P 1 ( X ) , H A ( 0 ) M L P 2 ( A ) H_X^{(0)}M\mathrm{LP}_1(X),~H_A^{(0)}\mathrm{MLP}_2(A) HX(0)MLP1(X), HA(0)MLP2(A) 仿照APPNP,再加上初等残差: H ( 0 ) ( 1 − α ) H X ( 0 ) α H A ( 0 ) H^{(0)}(1-\alpha)H_X^{(0)}\alpha H_A^{(0)} H(0)(1−α)HX(0)αHA(0) H ( l ) ( 1 − γ ) Z ( l ) H ( l ) γ H ( 0 ) O ( l ) H^{(l)}(1-\gamma)Z^{(l)}H^{(l)}\gamma H^{(0)}O^{(l)} H(l)(1−γ)Z(l)H(l)γH(0)O(l) 我们可以得到下面优化问题: min Z ( l ) ∥ H ( l ) − ( 1 − γ ) Z ( l ) H ( l ) − γ H ( 0 ) ∥ F 2 β 1 ∥ Z ( l ) ∥ F 2 β 2 ∥ Z ( l ) − ∑ k 1 K λ k A ^ k ∥ F 2 \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_{k1}^{K}\lambda_{k}\hat{A}^{k}\|_{F}^{2} Z(l)min∥H(l)−(1−γ)Z(l)H(l)−γH(0)∥F2β1∥Z(l)∥F2β2∥Z(l)−k1∑KλkA^k∥F2 第一项是优化问题,第二项是F范数,第三项是逼近Z与多跳邻居 可得Z: Z ( l ) ∗ [ ( 1 − γ ) H ( l ) ( H ( l ) ) T β 2 ∑ k 1 K λ k A ^ k − γ ( 1 − γ ) H ( 0 ) ( H ( l ) ) T ] [ ( 1 − γ ) 2 H ( l ) ( H ( l ) ) T ( β 1 β 2 ) I n ] − 1 \begin{aligned} Z^{(l)*} \left[(1-\gamma)H^{(l)}(H^{(l)})^T\beta_2\sum_{k1}^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} Z(l)∗[(1−γ)H(l)(H(l))Tβ2k1∑KλkA^k−γ(1−γ)H(0)(H(l))T][(1−γ)2H(l)(H(l))T(β1β2)In]−1
计算加速 H ( l 1 ) ( 1 − γ ) Z ( l ) ∗ H ( l ) γ H ( 0 ) . H^{(l1)}(1-\gamma)Z^{(l)*}H^{(l)}\gamma H^{(0)}. H(l1)(1−γ)Z(l)∗H(l)γH(0). H ( l 1 ) ( 1 − γ ) H ( l ) ( H ( l ) ) T Q ( l 1 ) β 2 ∑ k 1 K λ k A ^ k Q ( l 1 ) − γ ( 1 − γ ) H ( 0 ) ( H ( l ) ) T Q ( l 1 ) γ H ( 0 ) \begin{gathered} H^{(l1)} (1-\gamma)H^{(l)}(H^{(l)})^TQ^{(l1)}\beta_2\sum_{k1}^K\lambda_k\hat{A}^kQ^{(l1)} \\ -\gamma(1-\gamma)H^{(0)}(H^{(l)})^TQ^{(l1)}\gamma H^{(0)} \end{gathered} H(l1)(1−γ)H(l)(H(l))TQ(l1)β2k1∑KλkA^kQ(l1)−γ(1−γ)H(0)(H(l))TQ(l1)γH(0) 其中, Q ( l 1 ) 1 − γ β 1 β 2 H ( l ) − 1 − γ ( β 1 β 2 ) 2 H ( l ) . [ 1 ( 1 − γ ) 2 I c 1 β 1 β 2 ( H ( l ) ) T H ( l ) ] − 1 ( H ( l ) ) T H ( l ) \begin{aligned} Q^{(l1)} \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} Q(l1)β1β21−γH(l)−(β1β2)21−γH(l).[(1−γ)21Icβ1β21(H(l))TH(l)]−1(H(l))TH(l)
Group Effective Definition 4. 1. ( Grouping effect ( Li et al. , 2020) ) . Given \textbf{Definition 4. 1. }( \textbf{Grouping effect ( Li et al. , 2020) ) . Given} Definition 4. 1. (Grouping effect ( Li et al. , 2020) ) . Given,a set of nodes V { v i } i 1 n \mathcal{V}\{v_i\}_{i1}^n V{vi}i1n, let v i → v j v_i\to v_j vi→vj denote the condi-tion that ( 1 ) ∥ x i − x j ∥ 2 → 0 (1)\left\|x_i-x_j\right\|_2\to0 (1)∥xi−xj∥2→0 and ( 2 ) ∥ a ^ i k − a ^ j k ∥ 2 → 0 ( 2) \left \| \hat{a} _i^k- \hat{a} _j^k\right \| _2\to 0 (2) a^ik−a^jk 2→0, ∀ k ∈ \forall k\in ∀k∈ [ 1 , K ] . [1,K]. [1,K]. A matrix Z Z Z is said to have grouping effect if v i → v j ⇒ ∣ Z i p − Z j p ∣ → 0 , ∀ 1 ≤ p ≤ n . v_i\to v_j\Rightarrow|Z_{ip}-Z_{jp}|\to0,\forall1\leq p\leq n. vi→vj⇒∣Zip−Zjp∣→0,∀1≤p≤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.节点数。然而我们的方法加速了聚合并推导出了一个线性的时间复杂度
