GNN 和 Eigen-GNN
论文题目
Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs
GNN
介绍
GNN 的本质是为了针对图结构数据而产生的,它提供了一种框架,来同时处理数据的特征和数据的结构。在此,我们需要介绍一下两种task[1]。
第一种,叫feature-driven。它更像是普通的机器学习所处理的,给定一堆数据,挖掘出数据的特征,从而完成我们希望完成的任务,如分类、降维等。
第二种,叫Struture-driven。它更加关注数据的结构,将潜在的内部结构挖掘出来,再来完成我们的任务。
而普通的DL更加关注前者,但GNN自身特性使然,能做到两者兼具。
原理
GNN 可以得到上述的两种效果,它的目标其实就是学习到每一个节点
v
v
v的表示
h
v
∈
R
m
h_v \in R^m
hv∈Rm。而其学习过程可以用下列函数进行表示:
h
v
=
f
(
x
v
,
x
c
o
[
v
]
,
h
n
e
[
v
]
,
x
n
e
[
v
]
)
h_v = f(x_v, x_{co[v]},h_{ne[v]},x_{ne[v]})
hv=f(xv,xco[v],hne[v],xne[v])
其中, x v x_v xv表示每一个节点 v v v的数据特征(一说是标签属性,同下,笔者不太清楚这两者的表述具体区别,欢迎指正)。 x c o [ v ] x_{co[v]} xco[v]标志着对于每一个节点 v v v,和其相连的边的数据特征, h n e [ v ] h_{ne[v]} hne[v]代表着 v v v的邻居节点的隐藏表达(hidden representation), x n e [ v ] x_{ne[v]} xne[v]代表着 v v v的邻居节点的数据特征。
因此,通过神经网络所训练出来的,应该是这个函数 f f f。这个函数 f f f,便是将输入的数据特征投影至低维特征下的转移函数。
对于一个多层的GNN,对第
t
+
1
t+1
t+1,有
H
t
+
1
=
F
(
H
t
,
X
)
H^{t+1} = F(H^t,X)
Ht+1=F(Ht,X)
问题
现如今,很多的GNN变种层数非常少,大概3-4层。但是,有研究人员证明了浅的GNN变种不太关注结构信息,而大部分集中在了数据的特征信息。
因此,Ziwei Zhang 等人便提出了Eigen-GNN。这个是一个插入式(plug-in)的模块,用来提升GNN的性能。
Eigen-GNN
所谓的Eigen-GNN,是在GNN的基础上,将图进行压缩(这个词或许不准确)。它利用的是原图中的特征空间上的信息,在特征空间上,对其进行GNN的处理。
定义
我们定义, X X X是特征矩阵(feature matrix), Q Q Q是某一个矩阵的前 d d d个最大特征值所对应的特征向量所组成的矩阵。 f f f是一个简单的函数(原文: f ( ⋅ ) f(\cdot) f(⋅)is a simple function such as identity mapping or a normalization operator)。 G ( A ) \mathcal{G}(A) G(A)是一个图矩阵函数,令 G ( A ) = D ~ − 1 2 A ~ D ~ − 1 2 \mathcal{G}(\mathbf{A})=\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} G(A)=D~−21A~D~−21
性质
原文提出了一个置换等价性。这部分我不太能读懂,我猜测是对于图 G G G, G ′ G' G′, G ′ G' G′关于 G G G调换了两个或者两个以上节点顺序的图,这两个图 G G G, G ′ G' G′等价。
第二是计算的复杂度。
第三是退化性。在Eigen-GNN取特征空间维度 d = 1 d=1 d=1和没有隐藏层时,它会退化为SGC(Simple Graph Convolution)。
模型
本文的Eigen-GNN,感觉像是在原始的GNN上改动了一点。