发表于:neurips21
推荐指数: #paper/⭐⭐
设定:在本文中,h是过滤器.
bernstein 多项式逼近(这个证明有点稀里糊涂的,反正我觉得一点点问题,可能因为我水平低)
p
K
(
t
)
:
=
∑
k
=
0
K
θ
k
⋅
b
k
K
(
t
)
=
∑
k
=
0
K
f
(
k
K
)
⋅
(
K
k
)
(
1
−
t
)
K
−
k
t
k
.
p_K(t):=\sum_{k=0}^K\theta_k\cdot b_k^K(t)=\sum_{k=0}^Kf\left(\frac kK\right)\cdot\binom Kk(1-t)^{K-k}t^k.
pK(t):=k=0∑Kθk⋅bkK(t)=k=0∑Kf(Kk)⋅(kK)(1−t)K−ktk.
(其实类似于二项分布.如上K,k即二项分布的前缀)
推论2.1:给定一个连续函数f(t)
t
∈
[
0
,
1
]
t \in[0,1]
t∈[0,1],我们有:当
K
→
∞
K\to\infty
K→∞时,
p
K
(
t
)
→
f
(
t
)
p_{K}(t)\to f(t)
pK(t)→f(t).
后者容易理解,当K趋近于无穷时,将f后面的即为二项分布,求和为0.而
f
(
k
K
)
f\left( \frac{k}{K} \right)
f(Kk)又和t相关,用t取代(感觉理解的有问题)
对于过滤函数
h
:
[
0
,
2
]
→
[
0
,
1
]
h:[0,2]\to[0,1]
h:[0,2]→[0,1],我们有
t
=
λ
2
t=\frac{\lambda}{2}
t=2λ,我们就有:
f
(
t
)
=
h
(
2
t
)
f(t)=h(2t)
f(t)=h(2t),
θ
k
=
f
(
k
/
K
)
=
h
(
2
k
/
K
)
\theta_k = f(k/K) = h(2k/K)
θk=f(k/K)=h(2k/K).
b
k
K
(
t
)
=
b
k
K
(
λ
2
)
=
(
K
k
)
(
1
−
λ
2
)
K
−
k
(
λ
2
)
k
b_{k}^K(t)=b_k^K(\frac\lambda2) = \binom Kk(1-\frac\lambda2)^{K-k}(\frac\lambda2)^k
bkK(t)=bkK(2λ)=(kK)(1−2λ)K−k(2λ)k.最终,我们可以得到如下近似:
p
K
(
λ
/
2
)
=
∑
k
=
0
K
θ
k
(
K
k
)
(
1
−
λ
2
)
K
−
k
(
λ
2
)
k
=
∑
k
=
0
K
θ
k
1
2
K
(
K
k
)
(
2
−
λ
)
K
−
k
λ
k
p_K(\lambda/2)~=~\sum_{k=0}^K\theta_k\binom Kk(1-\frac\lambda2)^{K-k}\left(\frac\lambda2\right)^k~=~\sum_{k=0}^K\theta_k\frac1{2^K}\binom Kk(2-\lambda)^{K-k}\lambda^k
pK(λ/2) = ∑k=0Kθk(kK)(1−2λ)K−k(2λ)k = ∑k=0Kθk2K1(kK)(2−λ)K−kλk.
z
=
U
d
i
a
g
[
p
K
(
λ
1
/
2
)
,
.
.
.
,
p
K
(
λ
n
/
2
)
]
U
T
⏟
R
e
m
N
e
t
x
=
∑
k
=
0
K
θ
k
1
2
K
(
K
k
)
(
2
I
−
L
)
K
−
k
L
k
x
\mathbf{z}=\underbrace{\mathbf{U}diag[p_K(\lambda_1/2),...,p_K(\lambda_n/2)]\mathbf{U}^T}_{\mathrm{RemNet}}\mathbf{x}=\sum_{k=0}^K\theta_k\frac1{2^K}\binom Kk(2\mathbf{I}-\mathbf{L})^{K-k}\mathbf{L}^k\mathbf{x}
z=RemNet
Udiag[pK(λ1/2),...,pK(λn/2)]UTx=k=0∑Kθk2K1(kK)(2I−L)K−kLkx
实现常见的过滤器通过BernNet
证明好麻烦啊,烦烦烦
附录:组合数性质
∙
C
n
k
=
C
n
n
−
k
∙
C
n
k
+
1
=
C
n
k
×
n
−
k
k
+
1
∙
C
n
k
=
C
n
−
1
k
−
1
×
n
k
∙
C
n
k
=
C
n
−
1
k
−
1
+
C
n
−
1
k
\begin{aligned}&\bullet C_n^k = C_n^{n-k}\\&\bullet C_n^{k+1} = C_n^k \times \frac{n-k}{k+1}\\&\bullet C_n^k = C_{n-1}^{k-1} \times \frac{n}{k}\\&\bullet C_n^k = C_{n-1}^{k-1} + C_{n-1}^k\end{aligned}
∙Cnk=Cnn−k∙Cnk+1=Cnk×k+1n−k∙Cnk=Cn−1k−1×kn∙Cnk=Cn−1k−1+Cn−1k
C
n
k
=
A
n
k
A
k
k
=
n
k
‾
k
!
=
n
!
k
!
(
n
−
k
)
!
C_n^k=\frac{A_n^k}{A_k^k}=\frac{n^{\underline{k}}}{k!}=\frac{n!}{k!(n-k)!}
Cnk=AkkAnk=k!nk=k!(n−k)!n!
图过滤
min
z
f
(
z
)
=
(
1
−
α
)
z
T
γ
(
L
)
z
+
α
∥
z
−
x
∥
2
2
\min_\mathbf{z}f(\mathbf{z})=(1-\alpha)\mathbf{z}^T\gamma(\mathbf{L})\mathbf{z}+\alpha\|\mathbf{z}-\mathbf{x}\|_2^2
zminf(z)=(1−α)zTγ(L)z+α∥z−x∥22
令其倒数为0,
α
=
0.5
\alpha=0.5
α=0.5,
γ
(
L
)
=
e
t
L
−
I
\gamma(\mathbf{L})=e^{t\mathbf{L}}-\mathbf{I}
γ(L)=etL−I.
∂
f
(
z
)
∂
z
=
(
e
t
L
−
I
)
z
+
z
−
x
=
0
,
\frac{\partial f(\mathbf{z})}{\partial\mathbf{z}}=\left(e^{t\mathbf{L}}-\mathbf{I}\right)\mathbf{z}+\mathbf{z}-\mathbf{x}=\mathbf{0},
∂z∂f(z)=(etL−I)z+z−x=0,
z
∗
=
e
−
t
L
x
=
e
−
t
(
I
−
P
)
x
=
∑
k
=
0
∞
e
−
t
t
k
k
!
P
k
x
.
\mathbf{z}^*=e^{-t\mathbf{L}}\mathbf{x}=e^{-t(\mathbf{I}-\mathbf{P})}\mathbf{x}=\sum_{k=0}^\infty e^{-t}\frac{t^k}{k!}\mathbf{P}^k\mathbf{x}.
z∗=e−tLx=e−t(I−P)x=∑k=0∞e−tk!tkPkx.
这就是基于图热核的GNN例如GDC和GraphHeat采用的核
过滤器的非负性(保证凸优化)
0
≤
g
(
λ
)
=
∑
k
=
0
K
w
k
λ
k
≤
1
,
∀
λ
∈
[
0
,
2
]
.
0\leq g(\lambda)=\sum_{k=0}^Kw_k\lambda^k\leq1, \forall \lambda\in[0,2].
0≤g(λ)=∑k=0Kwkλk≤1,∀λ∈[0,2].证明:
α
(
α
I
+
(
1
−
α
)
γ
(
L
)
)
−
1
x
=
U
d
i
a
g
[
α
α
+
(
1
−
α
)
γ
(
λ
1
)
,
.
.
.
,
α
α
+
(
1
−
α
)
γ
(
λ
n
)
]
U
T
x
.
\alpha\left(\alpha\mathbf{I}+(1-\alpha)\gamma(\mathbf{L})\right)^{-1}\mathbf{x}=\mathbf{U}diag\left[\frac\alpha{\alpha+(1-\alpha)\gamma(\lambda_1)},...,\frac\alpha{\alpha+(1-\alpha)\gamma(\lambda_n)}\right]\mathbf{U}^T\mathbf{x}.
α(αI+(1−α)γ(L))−1x=Udiag[α+(1−α)γ(λ1)α,...,α+(1−α)γ(λn)α]UTx.
λ
∈
[
0
,
2
]
,
we have
0
≤
h
(
λ
)
≤
α
α
+
(
1
−
α
)
⋅
0
=
1
for
λ
∈
[
0
,
2
]
.
\lambda\in[0,2],\text{ we have }0\leq h(\lambda)\leq\frac\alpha{\alpha+(1-\alpha)\cdot0}=1\text{ for }\lambda\in[0,2].
λ∈[0,2], we have 0≤h(λ)≤α+(1−α)⋅0α=1 for λ∈[0,2].
结果:貌似挺高的,但是别人跑的就没那么高.
结构:
Z
=
∑
k
=
0
K
θ
k
1
2
K
(
K
k
)
(
2
I
−
L
)
K
−
k
L
k
f
(
X
)
,
\mathbf{Z}=\sum_{k=0}^K\theta_k\frac1{2^K}\binom Kk(2\mathbf{I}-\mathbf{L})^{K-k}\mathbf{L}^kf\left(\mathbf{X}\right),
Z=∑k=0Kθk2K1(kK)(2I−L)K−kLkf(X),
其中:f(X)是二层的MLP
