首页 > 其他分享 >Learning Graph Filters for Spectral GNNs via Newton Interpolation

Learning Graph Filters for Spectral GNNs via Newton Interpolation

时间:2023-11-26 11:34:57浏览次数:36  
标签:Spectral bar via mathbf le Learning mathcal mathbb lambda

目录

Xu J., Dai E., Luo D>, Zhang X. and Wang S. Learning graph filters for spectral gnns via newton interpolation. 2023.

令谱图网络的多项式系数按照牛顿插值的方式训练.

符号说明

  • \(\mathcal{V} = \{v_1, \ldots, v_N\}\), node set;
  • \(\mathcal{E}\), edge set;
  • \(\mathbf{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_N\} \in \mathbb{R}^{N \times F}\), node feature matrix;
  • \(\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathbf{X})\), undirected graph;
  • \(\mathbf{A}\), adjacency matrix;
  • \(\mathbf{D}\), diagonal matrix with \(\mathbf{D}_{ii} = \sum_{j} \mathbf{A}_{ij}\);
  • \(\mathbf{L} = \mathbf{D - \mathbf{A}}\), Laplacian matrix

Motivation

  • 假设 Laplacian matrix 的特征分解为:

    \[\mathbf{L} = \mathbf{U\Lambda U}^T, \]

    其中 \(0 \le \lambda_1 \le \lambda_2 \le \cdots \le \lambda_N\) 为 \(\Lambda\) 的对角线元素 (即 \(\mathbf{L}\) 的特征值).

  • 作者首先分析了不同频率的重要性差异: 对于同质图, 低频信息更有用, 而对于异质图, 高频信息更加有用.

  • 一般来说, 我们通常根据 Homophily Ratio

    \[ h(G) = \frac{|\{(s, t) \in \mathcal{E}: y_s = y_t\}|}{|\mathcal{E}|} \]

    来判断一个图的性质.

  • 由于随机加边的"平衡图" (这里平衡图指的是每个类的结点数目是相同的) 的 \(\mathbb{E}[h(G)] = 1/C\), 所以, 我们可以认为, 当 \(h > 1 / C\) 的时候, 这个图是更偏向同质图的, 反之是偏向异质图的.

  • 定义

    \[\bar{d}_{in} = \frac{1}{|\mathcal{P}_{in}|} \sum_{(s, t) \in \mathcal{P}_{in}} (x_s - x_t)^2, \\ \bar{d}_{out} = \frac{1}{|\mathcal{P}_{out}|} \sum_{(s, t) \in \mathcal{P}_{out}} (x_s - x_t)^2, \]

    其中 (注意, 允许 self-loop)

    \[\mathcal{P}_{in} := \{(s, t) | y_s = y_t\}, \\ \mathcal{P}_{out} := \{(s, t) | y_s \not= y_t\}. \]

    故 \(\bar{d}_{in}, \bar{d}_{out}\) 分别描述了类内平均距离和类间平均距离. 我们定义二者之差为:

    \[\Delta \bar{d} = \bar{d}_{out} - \bar{d}_{in}. \]

    现在假设有两个滤波 \(g_1, g_2\) 满足:

    \[g_i(\mathbf{L}) = \mathbf{U} g_i(\Lambda) \mathbf{U}^T, \quad i=1,2, \]

    \[g_1(\lambda_i) < g_2 (\lambda_i), \quad 1 \le i \le m, g_1(\lambda_i) > g_2 (\lambda_i), \quad m+1 \le i \le N, \\ \|g_1(\Lambda)\|_F = \|g_2(\Lambda)\|. \]

    显然, \(g_1, g_2\) 分别侧重高频和低频信号. 令

    \[\mathbf{x}^{(1)} = g_1(\mathbf{L})\mathbf{x}, \quad \mathbf{x}^{(2)} = g_2(\mathbf{L})\mathbf{x}, \]

    则有 \(\mathbf{x}^{(1)}\) 更侧重高频, \(\mathbf{x}^{(2)}\) 更侧重低频.

  • 则, 在一定条件下:

    1. 当 \(h > 1 / C\) (即偏同质图):

      \[ \mathbb{E}_{\mathbf{x}}[\Delta \bar{d}^{(1)}] < \mathbb{E}_{\mathbf{x}}[\Delta \bar{d}^{(2)}]. \]

    2. 当 \(h < 1 / C\) (即偏异质图):

      \[ \mathbb{E}_{\mathbf{x}}[\Delta \bar{d}^{(1)}] > \mathbb{E}_{\mathbf{x}}[\Delta \bar{d}^{(2)}]. \]

  • 其实是很直观的一个结论.

  • 不过, 需要声明一点的是, \(\mathbb{E}_{\mathbf{x}}\) 的操作使得这个结论有那么一点一般 (但也挺有意思的).

  • 其次, 作者在文中采用的是 normalzied Laplacian matrix 去证明 (但实际上是有问题的).

NewtonNet

  • 说实话, 后面的设计和前面的 motivation 并没有太强的联系, 后面就是利用牛顿插值来限制多项式基的系数的学习:

    \[\mathbf{Z} = \sum_{k=0}^K \bigg \{ \hat{g}_t [q_0, \cdots, q_k] \prod_{i=0}^{k-1} (\mathbf{L} - q_i \mathbf{I}) \bigg\} f_{\theta}(\mathbf{X}). \]

  • 其中 \(\hat{g}_t[q_0, \cdots, q_k]\) 是根据牛顿插值的迭代公式得到的:

代码

[official]

标签:Spectral,bar,via,mathbf,le,Learning,mathcal,mathbb,lambda
From: https://www.cnblogs.com/MTandHJ/p/17856659.html

相关文章

  • [Deeplearning] 钻石矿工
    首先画图假设有两个点,那么去钻石的方案就如上图那么我们就需要比较蓝线的长度与红线的长度先看一下两点之间距离公式\(\sqrt{(x-u)^2+(y-v)^2}\)这个公式就是运用了勾股定理,一直两条边,求第三条接着,我们比较蓝线与红线的长短我们把它分为两个三角形(如图即可)随后,根据三角形......
  • [Deeplearning] 过河问题
    先模拟一下样例125101和2去,耗时21回,耗时35和10去,耗时132回,耗时151和2去,耗时17现在我们把题目化为两种策略策略1:共2人,一起过河,用时较小的将手电筒放回策略2:共4人,耗时较小的两人先过,接着将手电筒送回,用时较大的两人过,最后右侧用时最小的人将手电筒送回,左侧两人一起过......
  • [Deeplearning] 活动选择F604
    那个F604是干啥的我似乎也不知道思路依旧很简单,右端点排序,这个活动结束得越早留给后面的时间就越多代码:#include<bits/stdc++.h>usingnamespacestd;structnode{ intstart,end;}a[1010];intn,back,ans;boolcmp(nodex,nodey){ returnx.end<y.end;}intmain()......
  • [Deeplearning] 采购奖品
    思路:非常简单,按物品的单价排序,商品的单价小,我们就尽量多的选它代码:#include<bits/stdc++.h>usingnamespacestd;structnode{ intcost,num;}a[110];intn,m,ans,money;boolcmp(nodex,nodey){ returnx.cost<y.cost;}intmain(){ cin>>m>>n; for(inti=0;i<......
  • [Deeplearning] 吃蛋糕
    放张图自己体会(doge类似于爬楼梯的递推题动态转移方程,或者说递推式:dp[i]=dp[i-1]+dp[i-k]其中\(i≥k\)代码:#include<bits/stdc++.h>usingnamespacestd;constintmod=1000000007;longlongt,k,a,b;longlongdp[100010],sum[100010];intmain(){cin>>t>>k;......
  • [Deeplearning] 2017篮球队
    一道动态规划题\(f_{i, j, k}\)表示前i个人里取j个,身高大于等于k的方法数得到状态转移方程为\(f_{i, j, k} = f_{i − 1, j − 1, k − a_i}\)由于这样空间不够,我们需要降维代码:#include<bits/stdc++.h>usingnamespacestd;constintMAXN=2e5+5;intn,m,h......
  • [Deeplearning] 20210919小学组 取数游戏
    首先明确一下贪心策略:两人必然会从大往小取当自己无法得分时,最优策略就是不让对方得分当自己可以得分时,得分所以,最后只需要便利数组,当A或B能得分时便得分,不能得分就不得分,但是不管能否得分都需要将最大的数取出代码:#include<bits/stdc++.h>usingnamespacestd;intn,a[......
  • Java Learning Day1 关键字、标识符、注释、变量
    其实之前也学习过两个月的JAVA,跟着淘宝上买的王道Java课,每天看了1day,整个过程下来感觉什么都没有掌握,所以现在就打算重新学一次,从最开始的关键字开始,也就开通了博客,希望这次学习可以多多掌握一些吧。  关键字:小写、含有特殊含义的单词 标识符:方法名、类名、参数名、变量名......
  • Graph Neural Networks with Diverse Spectral Filtering
    目录概符号说明DSF代码GuoJ.,HuangK,YiX.andZhangR.Graphneuralnetworkswithdiversespectralfiltering.WWW,2023.概为每个结点赋予不同的多项式系数.符号说明\(\mathcal{V}\),nodeset,\(|\mathcal{V}|=N\);\(\mathcal{E}\),edgeset;\(\mathcal{......
  • Bean instantiation via constructor failed; nested exception is org.springframewo
    一、从公司的的GitLab下载项目到本地二、nacos-2.0.1启动不了我以为是我中文路径问题,然后放到全是英文的一样报错,百度一圈没找到解决方法。三、大佬路过,瞟了我一眼的电脑解决了。删除D:\nacos-2.0.0\data 下面的所有文件即可 原因就是有人把自己的数据上传到git了,导致......