SLOG An Inductive Spectral Graph Neural Network Beyond Polynomial Filter

推荐指数: #paper/⭐⭐ (二到三颗星.等作者开源代码,泡一下,在确定具体推荐分)
发表于: ICML 24

主要思路:

$$\omega ({\mathbf{L}}_{\mathbf{sym}})=(\mathbf{I}-\frac{1}{2}{\mathbf{L}}_{\mathbf{sym}}{)}^p(\mathbf{I}+({\mathbf{L}}_{\mathbf{sym}}-\mathbf{I}{)}^2{)}^q$$
这个式子是正定的.令${\mathbf{S}}_1=\frac{1}{2}(\mathbf{I}+{\mathbf{D}}^{-\frac{1}{2}}\mathbf{A}{\mathbf{D}}^{-\frac{1}{2}}),{\mathbf{S}}_2=\mathbf{I}+({\mathbf{D}}^{-\frac{1}{2}}\mathbf{A}{\mathbf{D}}^{-\frac{1}{2}}{)}^2$,那么$\omega ({\mathbf{L}}_{\mathrm{sym}})={\mathbf{S}}_1^p\cdot {\mathbf{S}}_2^q$.
其中,p和q是可学习的参数.
而p和q则影响了其是高通/低通/中通等

但是,由于p和q可能是负数或者其他情况.当图变得很大的时候,计算量很大.因此,我们采用了采样系数,采样子图,让图变得小.这样,计算开销就会在可控的范围内.
主要公式:

Slog B

$${\mathbf{Z}}_{{\mathcal{G}}_v}=\omega ({\mathbf{L}}_{{\mathcal{G}}_v}){\mathbf{X}}_{{\mathcal{G}}_v}\mathbf{W},$$
其中,${\mathcal{G}}_v$是以v为中心,采样的子图.

Slog N

$${\mathbf{H}}_{{\mathcal{G}}_v}^{(l)}=\sigma ({\omega }^{(l)}({\mathbf{L}}_{{\mathcal{G}}_v}){\mathbf{H}}_{{\mathcal{G}}_v}^{(l-1)}{\mathbf{W}}_1^{(l)}+{\mathbf{H}}_{{\mathcal{G}}_v}^{(l-1)}{\mathbf{W}}_2^{(l)}),$$

由于子图有不同的频率,因此我们使用了自适应参数去让每个子图去适应自己的同配比

$${\omega }_i({\mathbf{L}}_{{\mathcal{G}}_v})=(\mathbf{I}-\frac{1}{2}{\mathbf{L}}_{{\mathcal{G}}_v}{)}^{p_i^{\prime }}(\mathbf{I}+({\mathbf{L}}_{{\mathcal{G}}_v}-\mathbf{I}{)}^2{)}^{q_i^{\prime }}$$
其中,$p_i^{\prime }=\beta p_{\mathbf{glo}}+(1-\beta )p_i$,$q_i^{\prime }=\beta q_{\mathbf{glo}}+(1-\beta )q_i$
$\beta$是超参.$p_{glo}和q_{glo}$代表全局uniform filter.$p_i$和$q_i$对应自适应i个子图

结果分析:
Slog(B)Citeseer的结果比较不错.Squirrel fit,chameleon fit两个数据集没听过.minesweeper的正确率异常把?有好几个方法应该是在89左右.ratting的数据也不错…总体而言,常见的五个数据集(除去两个fit),cite和rate的效果不错.toker处于顶尖水平.看起来,slogN的效果并没有好的多少.这说明,gcn更多情况下还是由一阶和二阶决定的(以及其负阶).
大数据集结果和我之前看的论文,benchmark方法的结果不一样.(等作者公开代码后我跑一下,感觉和想的有点不一样)