graph neural network

学习笔记机器学习 GNN

字数统计: 1.9k阅读时长: 8 min

 2023/11/11 

图机器学习学习笔记

deep learning for graphs

图网络要复杂得多:

尺寸任意，拓扑结构复杂
没有固定的节点顺序或参考点
通常是动态的，具有多模态特征

将ajacency matrix和node feature结合送入网络存在以下问题

$O(\mid V \mid)$参数太大
不适用于不同大小的图
对节点排序敏感

如果套用CNN的话，没有固定的notion of locality或者sliding window在一个卷积核内，以及graph的同构性从不同角度看会不一样但图是permutation invariant的

permutation invariance / equivariance

置换不变性
- 对于图嵌入
- 节点的排序不会改变图的表示
排列不变性
- 对于节点嵌入
- 节点的排序将导致节点表示的相同排序

对于上面的两个图，embedding函数$f(Ai, Xi)$产生的结果应该是一样的，这样的函数就说其是permutation invariance

Graph neural networks consist of multiple permutation equivariant / invariant functions.

a general perspective on graph neural network

如果借用CNN的思维的话即从邻居那得到咨询然后做卷积，这种即GCN。我们需要定义邻居以及让模型学会如何得到邻居的信息（aggregate infomation）

receptive field在cnn里指的是卷积核的视野，在graph里是指拉neighbors的次数，一阶邻居、二阶邻居，receptive field越大能看到的范围越大。当邻居的info拿到后要做平均，然后使用一个nn做更新。

math of graph convolution

$h^{(k)}_u$ 是node-v邻居的embedding，加起来除以邻居的数量，即蓝色部分是在平均邻居的咨询。而这样缺少了自身的咨询，因为要加上红色部分node-v本身的咨询 $h^{(k)}_v$。注意加上前需要分别乘上weight进行transform，得到和后使用非线性函数激活。这样就是一次的convolution即1-layer（注意这里因为permutation invariance / equivalence所以拉邻居的顺序不会影响最后的结果）

但当graph的node很多的时候复杂度会很高，因此我们需要借助matrix operation

matrix formulation

拉邻居加起来的过程就可以看作是邻接矩阵乘上embedding matrix，在用度矩阵degree做一个平均。

gnn framework

gnn layer = message + aggregation，现在不同的gnn的区别是他们产生message的方法或者aggregate的方法不同；

借由叠加多层的layer，看到的视野更大，而不同的层数之间也可以像cnn一样使用dropout来更powerful；

有时候一个graph可能本身没有feature只有一个结构，又或者是graph的结构太复杂/稀疏，我们可以做feature augmentation / structure augmentation，即raw input graph ≠ computational graph.

learning objective: Supervised / Unsupervised objectives, Node/Edge/Graph level objectives;

inductive capability

a single layer of a gnn

theory

message function

message function是在对邻居的node embedding做一些转换，让它更好再传给当前node

$m^{(l)}_u = MSG^{(l)}(h^{(l-1)} _ {u})$

这里的$MSG$可以是任何形式的layer，可以是linear也可以是non-linear，甚至可以是multi-layers的

aggregation function

收集所有邻居的info，可以用sum、mean等。

$$h^{(l)}_v = AGG^{(l)}({m^{(l)}_u, u \in N(v)})$$

$$AGG: Sum(·)，Mean(·)，Max(·) $$ 优势从左到右以此递减

message agregatio issue

上述的单一message+aggregation方法缺失了node-v自己的值

$$h^{(l)} _v = CONCAT(AGG({ { m^{(l)} _u, u \in N(v} }), m^{(l)} _v)$$

写成带学习权重的形式就是：

$$m^{(l)} _u = W^{(l)}(h^{(l-1)} _ {u})$$

$$m^{(l)}_v = B^{(l)}(h^{(l-1)} _ {v})$$

整个过程就是：

$$h^{(l)} _v = CONCAT(AGG({ { W^{(l)}(h^{(l-1)} _ {u}), u \in N(v} }), B^{(l)}(h^{(l-1)} _ {v}))$$

examples

GCN

$$h^{(l)}_v = \sigma (W^{(l)} \sum\limits _ {u \in N(v)} \frac{h^{(l-1)}_u}{\mid N(v) \mid})$$

$$h^{(l)}_v = \sigma (\sum\limits _ {u \in N(v)} W^{(l)} \frac{h^{(l-1)}_u}{\mid N(v) \mid})$$

变换后就是

$$h^{(l)} _v = \sigma(Sum({ { m^{(l-1)} _ {u}, u \in N(v) } } ))$$

注意转换后的公式，把w移动进去后，把邻居的message即$h^{(l-1)}_u$乘上一个learning weight，再除以node的degree做一个平均normalize，这是message部分。然后在用一个$Sum(·)$做一个aggregation。最后包一层non-linear的layer。

GCN解决丢失自己node embedding的issue时，在图里添加了一个self-edges即loop，使得邻接矩阵添加了一个单位矩阵$I$。

如果写成矩阵计算的形式就是：

$$A’ = A + I$$

$$\hat{A} = D^{-\frac{1}{2}}A’D^{-\frac{1}{2}}$$

$$H^{(l)} _v = \sigma(\hat{A} H^{(l-1)} _v W^{(l)})$$