论文地址:Inductive Representation Learning on Large Graphs

一、核心思想

GraphSAGE认为卷积=采样+信息聚合(sample+aggregate)。
通过采样和信息聚合来完成卷积操作,并且和GNN观点不同的是,聚合函数与输入的顺序无关,即邻域的结点无序。

二、实现步骤

1.通过采样,获得固定数量的邻域节点;
2.使用聚合函数获得邻域节点的聚合信息,获得目标点的embedding或者features;
3.利用邻域节点的聚合信息进行聚合,预测目标节点的内容或者label。

采样方式:GraphSAGE使用均匀采样(Uniform Sampling)来采样固定数目的邻域节点。即在其一阶相连的节点上可重复的进行均匀采样,获得固定数量的节点作为邻域。

聚合方式
1.Mean Aggregator(均值聚合): h v k ← σ ( W ⋅ M E A N ( { h v k − 1 } ∪ { h u k − 1 , ∀ u ∈ N ( v ) } ) h^k_v ← σ(W · MEAN(\{h^{k−1}_v\} ∪ \{h^{k−1}_u , ∀u ∈ N(v)\}) hvkσ(WMEAN({ hvk1}{ huk1,uN(v)})
2.LSTM Aggregator(LSTM聚合):
相较于均值聚合,表达能力更强,但是使用LSTM时,需要将邻域节点随机排序,输入到LSTM中进行聚合。
3. Pooling aggregator(最大值聚合): A G G R E G A T E k p o o l = m a x ( { σ ( W p o o l h u i k + b ) , ∀ u i ∈ N ( v ) } ) AGGREGATE^{pool}_k = max(\{σ (W_{pool}h^k_{u_i} + b) , ∀u_i ∈ N(v)\}) AGGREGATEkpool=max({ σ(Wpoolhuik+b),uiN(v)})

实现伪代码

三、对比


相较于GNN以及传统的CNN中需要定义邻域节点的顺序,GraphSAGE的作者认为图卷积邻域节点无序

相较于GNN中的每个节点拥有不同的卷积核参数,GraphSAGE在每一层的邻域中的所有节点共享同样的卷积核参数

GNN选择随机游的概率分布进行邻域构建,GraphSAGE通过均匀采样构建邻域。

四、举例