GraphSAGE的基础理论

这篇具有很好参考价值的文章主要介绍了GraphSAGE的基础理论。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

GraphSAGE原理(理解用)

引入:

GCN的缺点:

  • 从大型网络中学习的困难:GCN在嵌入训练期间需要所有节点的存在。这不允许批量训练模型。
  • 推广到看不见的节点的困难:GCN假设单个固定图,要求在一个确定的图中去学习顶点的embedding。但是,在许多实际应用中,需要快速生成看不见的节点的嵌入。而GCN无法直接泛化到在训练过程没有出现过的顶点,即属于一种直推式(transductive)的学习。

GraphSAGE:其核心思想是通过学习一个对邻居顶点进行聚合表示的函数来产生目标顶点的embedding向量。

GraphSAGE工作流程

  1. 对图中每个顶点的邻居顶点进行采样。模型不使用给定节点的整个邻域,而是统一采样一组固定大小的邻居。
  2. 根据聚合函数聚合邻居顶点蕴含的信息。
  3. 得到图中各顶点的向量表示供下游任务使用。
  1. 对图中每个顶点的邻居顶点进行采样

    • 考虑计算效率的情况下:对每个顶点采样一定数量的邻居顶点作为待聚合信息的顶点。设采样数量为k,若顶点邻居数少于k,则采用有放回的抽样方法,直到采样出k个顶点。若顶点邻居数大于k,则采用无放回的抽样。
    • 不考虑计算效率的情况下:完全可以对每个顶点利用其所有的邻居顶点进行信息聚合,这样是信息无损的。

    具体来说:

    在第 k k k 层时,对每个顶点 v v v,首先使用顶点 v v v 的邻居顶点的 k − 1 k-1 k1 层的 embedding 表示来产生其邻居顶点的第 k k k 层聚合表示 h N ( v ) k h_{N(v)}^k hN(v)k,之后将 h N ( v ) k h_{N(v)}^k hN(v)k 和顶点 v v v 的第 k − 1 k-1 k1 层表示 h v k − 1 h_v^{k-1} hvk1进行拼接(concat),经过一个非线性变换产生顶点 v v v 的第 k k k 层 embedding 表示。一般而言,可用公式可表示为(只是为了说明流程,具体还要看聚合函数的选取): h N ( v ) k = a g g r e g a t e k ( { h u k − 1 , ∀ u ∈ N ( v ) } ) h_{N(v)}^k = aggregate_k(\{h_u^{k-1}, \forall u \in N(v)\}) hN(v)k=aggregatek({huk1,uN(v)}) h v k = σ ( W k ⋅ c o n c a t ( h v k − 1 , h N ( v ) k ) ) h_v^k = \sigma (W^k \cdot concat(h_v^{k-1},h_{N(v)}^k) ) hvk=σ(Wkconcat(hvk1,hN(v)k))

  2. 根据聚合函数聚合邻居顶点蕴含的信息

    聚合函数的选取:

    • MEAN aggregator:
      h v k = σ ( W ⋅ M E A N ( { h v k − 1 } ∪ { h u k − 1 , ∀ u ∈ N ( v ) } ) ) h_v^k = \sigma (W \cdot MEAN(\{h_v^{k-1}\}\cup\{h_u^{k-1},\forall u \in N(v)\})) hvk=σ(WMEAN({hvk1}{huk1,uN(v)}))
    • Pooling aggregator:
      h N ( v ) k = p o o l i n g _ m e t h o d ( { σ ( W h u k + b ) , ∀ u ∈ N ( v ) } ) h_{N(v)}^k = pooling\_method(\{\sigma(Wh_u^k+b), \forall u \in N(v)\}) hN(v)k=pooling_method({σ(Whuk+b),uN(v)}) 注意这里是 h N ( v ) k ,而不是 h v k ;其中 p o o l i n g _ m e t h o d ∈ { m a x , m e a n } 注意这里是h_{N(v)}^k,而不是h_v^k;其中pooling\_method \in \{max,mean\} 注意这里是hN(v)k,而不是hvk;其中pooling_method{max,mean}
    • LSTM aggregator:
      中心节点的邻居节点随机打乱作为输入序列,将 所得向量表示 h N ( v ) k h_{N(v)}^k hN(v)k中心节点的向量 h v k − 1 h_v^{k-1} hvk1 表示分别经过非线性变换后拼接,得到中心节点在该层的向量表示。LSTM 本身用于序列数据,而邻居节点没有明显的序列关系,因此输入到 LSTM 中的邻居节点需要随机打乱顺序
  3. 参数的学习

    • 无监督学习

      基于图的损失函数希望邻近的顶点具有相似的向量表示,同时让分离的顶点的表示尽可能不同。 目标函数如下: J G ( z u ) = − l o g ( σ ( z u T z v ) ) − Q ⋅ E v n ∼ P n ( v ) l o g ( σ ( − z u T z v n ) ) J_G(z_u) = -log(\sigma(z_u^Tz_v))-Q\cdot E_{v_n ∼ P_n(v) }log(\sigma(-z_u^Tz_{v_n})) JG(zu)=log(σ(zuTzv))QEvnPn(v)log(σ(zuTzvn))其中 v v v 是在定长随机游走中在 u u u 附近同时出现的节点, σ σ σ s i g m o i d 函数 sigmoid函数 sigmoid函数 P n P_n Pn是一个负抽样分布, Q Q Q定义了负抽样的数量。

      与DeepWalk不同的是,这里的顶点表示向量是通过聚合顶点的邻接点特征产生的,而不是简单的进行一个embedding lookup操作得到。

    • 监督学习

      监督学习形式根据任务的不同直接设置目标函数即可,如最常用的节点分类任务使用交叉熵损失函数。

GraphSAGE的实用基础理论(编代码用)

1. GraphSAGE的底层实现(pytorch)

PyG中NeighorSampler实现节点维度的mini-batch + GraphSAGE样例

参考博客:https://blog.csdn.net/weixin_39925939/article/details/121458145

PyG中的SAGEConv实现

原论文中实现方法: x i ′ = W ⋅ c o n c a t ( A g g r e g a t e j ∈ N ( i ) x j , x i ) x_i' = W \cdot concat(Aggregate_{j\in N(i)}x_j,x_i) xi=Wconcat(AggregatejN(i)xj,xi)

PyG中实现方法: x i ′ = W 1 x i + W 2 ⋅ A g g r e g a t e j ∈ N ( i ) x j x_i' = W_1x_i + W_2 \cdot Aggregate_{j\in N(i)}x_j xi=W1xi+W2AggregatejN(i)xj

这两种方式是一样的,但是不同的是:

SAGEConv代码中的邻居就是你传入的邻居,不管是使用NeighborSampler等方式对邻居进行采样过的邻居还是未采样的所有邻居,它只管接收你传入的邻居,邻居采样不在这里实现。

  • init函数

    参数说明:

    • in_channels: Union[int, Tuple[int, int]]:输入原始特征或者隐含层embedding的维度。如果是-1,则根据传入的x来推断特征维度。注意in_channels可以是一个整数,也可以是两个整数组成的tuple,分别对应source节点和target节点的特征维度。
    • source节点: 中心节点的邻居节点。 { x j , ∀ j ∈ N ( i ) } \{x_j, \forall j\in N(i)\} {xj,jN(i)}
    • target节点:中心节点。 x i x_i xi
    • in_channels[0]:参数 W 2 W_2 W2的shape[0],点乘source节点聚合后的特征矩阵
    • in_channels[1]:参数 W 1 W_1 W1的shape[0],点乘对应target节点的特征矩阵
    • out_channels:输出embedding的维度
    • normalize:是否对输出进行 l 2 l_2 l2归一化,默认为False
    • bias:偏差,默认为True
    • root_weight:输出是否会加上节点自身特征转换维度后的值,默认是True
    • kwargs.setdefault('aggr', 'mean'):邻域聚合方式,默认aggr='mean',其余方式还有aggr='max'aggr='add'
    class SAGEConv(MessagePassing):    
        def __init__(self, in_channels: Union[int, Tuple[int, int]],
                 out_channels: int, normalize: bool = False,
                 root_weight: bool = True,
                 bias: bool = True, **kwargs):  # yapf: disable
        kwargs.setdefault('aggr', 'mean')
        super(SAGEConv, self).__init__(**kwargs)
    
        self.in_channels = in_channels
        self.out_channels = out_channels
        self.normalize = normalize
        self.root_weight = root_weight
    
        if isinstance(in_channels, int):
            in_channels = (in_channels, in_channels)
    
        self.lin_l = Linear(in_channels[0], out_channels, bias=bias)
        if self.root_weight:
            self.lin_r = Linear(in_channels[1], out_channels, bias=False)
    
        self.reset_parameters()
    
    
  • forward函数

    参数说明:

    • x:Union[Tensor, OptPairTensor]:可以是Tensor,也可以是OptPairTensor (pyg定义的tuple of Tensor)。

    当图是bipartite的时候,x是OptPairTensor,为了和init函数中定义的in_channel对应,要使得:

    • source节点(邻居节点)特征对应x[0] ,在代码中赋值给x_lin_channel[0] W 2 W_2 W2)定义为lin_l
    • target节点(中心节点)特征对应x[1],在代码中赋值给 x_rin_channel[1] W 1 W_1 W1)定义为lin_r
    • edge_index: Adj: Adj是pyg定义的邻接矩阵类型,可以是Tensor,也可以是SparseTensor。
    def forward(self, x: Union[Tensor, OptPairTensor], edge_index: Adj,
                   size: Size = None) -> Tensor:
           """"""
           if isinstance(x, Tensor):
               x: OptPairTensor = (x, x)
    
           # propagate_type: (x: OptPairTensor)
           out = self.propagate(edge_index, x=x, size=size)
           out = self.lin_l(out)
    
           x_r = x[1]
           if self.root_weight and x_r is not None:
               out += self.lin_r(x_r)
    
           if self.normalize:
               out = F.normalize(out, p=2., dim=-1)
    
           return out
    
    
  • 消息传递函数(message函数)

    forward函数中使用self.propagate时调用,传入的edge_index不算显式参数。

    参数说明:

    • edge_index为Tensor
      edge_index为Tensor的时候,propagate调用message和aggregate实现消息传递和更新。这里message函数对邻居特征没有任何处理,只是进行了传递,所以最终propagate函数只是对邻居特征进行了aggregate
    • edge_index为SparseTensor
      edge_index为SparseTensor的时候,propagate函数会在message_and_aggregate被定义的情况下被优先调用,代替message和aggregate。
      这里message_and_aggregate直接调用类似矩阵计算matmul(adj_t, x[0], reduce=self.aggr)。x[0]是source节点的特征。matmul来自于torch_sparse,除了类似常规的矩阵相乘外,还给出了可选的reduce,这里可以实现add,mean和max聚合。
    def message(self, x_j: Tensor) -> Tensor:
        return x_j
    
    def message_and_aggregate(self, adj_t: SparseTensor,
                              x: OptPairTensor) -> Tensor:
        adj_t = adj_t.set_value(None, layout=None)
        return matmul(adj_t, x[0], reduce=self.aggr)
    

2. GraphSAGE的实例

import torch
import torch.nn.functional as F
from torch_geometric.nn.conv import SAGEConv

class SAGE(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.):
        super(SAGE, self).__init__()
        
        self.convs = torch.nn.ModuleList()
        self.convs.append(SAGEConv(in_channels, hidden_channels))
        self.convs.append(SAGEConv(hidden_channels, out_channels))
        
        self.dropout = dropout
        
    def reset_parameters():
        for conv in self.convs:
            conv.reset_parameters()
            
    def forward(self, x, edge_index):
        x = self.convs[0](x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=self.dropout, training=self.training)
        x = self.convs[1](x, edge_index)
        
        return x.log_softmax(dim=-1)

#读取数据
from torch_geometric.datasets import Planetoid
import torch_geometric.transforms as T

transform = T.ToSparseTensor()
# 这里加上了ToSparseTensor(),所以边信息是以adj_t形式存储的,如果没有这个变换,则是edge_index
dataset = Planetoid(name='Cora', root=r'./dataset/Cora', transform=transform)
data = dataset[0]
data.adj_t = data.adj_t.to_symmetric()

model = SAGE(in_channels=dataset.num_features, hidden_channels=128, out_channels=dataset.num_classes)
optimizer = torch.optim.Adam(model.parameters(), lr=0.001)

def train():
    model.train()
    
    optimizer.zero_grad()
    out = model(data.x, data.adj_t)[data.train_mask] #前面我们提到了,SAGE是实现了edge_index和adj_t两种形式的
    loss = F.nll_loss(out, data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    
    return loss.item()

@torch.no_grad()
def test():
    model.eval()
    
    out = model(data.x, data.adj_t)
    y_pred = out.argmax(axis=-1)
    
    correct = y_pred == data.y
    train_acc = correct[data.train_mask].sum().float()/data.train_mask.sum()
    valid_acc = correct[data.val_mask].sum().float()/data.val_mask.sum()
    test_acc = correct[data.test_mask].sum().float()/data.test_mask.sum()
    
    return train_acc, valid_acc, test_acc 

#跑10个epoch看一下模型效果
for epoch in range(20):
    loss = train()
    train_acc, valid_acc, test_acc = test()
    print(f'Epoch: {epoch:02d}, '
                              f'Loss: {loss:.4f}, '
                              f'Train_acc: {100 * train_acc:.3f}%, '
                              f'Valid_acc: {100 * valid_acc:.3f}% '
                              f'Test_acc: {100 * test_acc:.3f}%')

引用

文章参考了:文章来源地址https://www.toymoban.com/news/detail-414586.html

  1. https://blog.csdn.net/weixin_39925939/article/details/121343538
  2. https://zhuanlan.zhihu.com/p/79637787
  3. https://zhuanlan.zhihu.com/p/336195862

到了这里,关于GraphSAGE的基础理论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【《机器学习和深度学习:原理、算法、实战(使用Python和TensorFlow)》——以机器学习理论为基础并包含其在工业界的实践的一本书】

    机器学习和深度学习已经成为从业人员在人工智能时代必备的技术,被广泛应用于图像识别、自然语言理解、推荐系统、语音识别等多个领域,并取得了丰硕的成果。目前,很多高校的人工智能、软件工程、计算机应用等专业均已开设了机器学习和深度学习的课程,此外,为

    2024年02月16日
    浏览(51)
  • 分布式理论基础:BASE理论

    BASE 是指基本可用(Basically Available)、软状态( Soft State)、最终一致性( Eventual Consistency),核心思想是即使无法做到强一致性(CAP 的一致性就是强一致性),但应用可以采用适合的方式达到最终一致性。 分布式系统在出现故障时,允许损失部分可用性,即保证核心可用。

    2024年02月04日
    浏览(43)
  • SQLserver基础入门理论(超基础)

    ♥️ 作者:小刘在C站 ♥️ 个人主页:  小刘主页  ♥️ 努力不一定有回报,但一定会有收获加油!一起努力,共赴美好人生! ♥️ 学习两年总结出的运维经验,以及思科模拟器全套网络实验教程。专栏: 云计算技术 ♥️小刘私信可以随便问,只要会绝不吝啬,感谢CSD

    2024年02月10日
    浏览(50)
  • API安全基础理论

    API(Application Programming Interface,应用程序编程接口)是一些预先定义的函数,目的是提供应用程序与开发人员基于某软件或硬件的以访问一组例程的能力,而又无需访问源码,或理解内部工作机制的细节。通过淘宝API,就算不知道如何操作,也能将产品或服务与其他产品或服务进

    2024年02月13日
    浏览(47)
  • 数据库基础理论

    数据:描述事务的符号记录,包含但不限于数字、 文字、图形、图像、声音、语言等。数据有多重形式,它们都可以经过数字化后存入计算机。 数据库:数据仓库。是长期存放在计算机内、有组织、可共享的大量数据的集合。数据库中的数据按照一定数据模型组织、描述和

    2024年01月21日
    浏览(43)
  • 微服务基础理论

    2014,微服务:架构风格(服务微化) 一个应用应该是一组小型服务;可以通过HTTP的方式进行互通; 对应的是过去的单体应用:ALL IN ONE 微服务:每一个功能元素最终都是一个可独立替换和独立升级的软件单元;(和ABB包想法有点儿像,进一步粒化。软件工程在原子化的方向上

    2024年02月15日
    浏览(39)
  • SaaS 架构基础理论(一)

    《互联网时代的软件革命 SaaS架构设计》学习笔记 云计算提供的强大软硬件环境和基础服务,将逐渐成为支撑SaaS应用的基础设施。各个云计算平台所包含的大量具有自身特色的公共服务,将为SaaS应用的开发提供了丰富的资源。而统一整合各个云计算平台的公共服务,也成为

    2024年02月02日
    浏览(44)
  • 图论算法|深度优先搜索理论基础|797.所有可能的路径|广度优先搜索BFS理论基础|200. 岛屿数量

    dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 递归和回溯是相辅相成的 https://leetcode.cn/problems/all-paths-from-source-to-target/ 有向无环图(DAG): 有环无向图是指在图中存在至少一个环(Cycle)的无向图。环是

    2024年02月15日
    浏览(55)
  • k8s基础理论

    1.核心对象 NameSpaces Pod ServiceAccount ReplicaSet Deployment service和ingress persistenvolume和persistenvolumeclaim 2.控制器 etcd apiserver controller manager scheduler kubelet kube-proxy 3.相关插件 容器运行时 网络插件 flannel calico 4.关于pod生命周期 pod创建过程 pod删除过程 pod的质量保证 pod的节点亲和性 pod的节

    2024年02月04日
    浏览(44)
  • 音视频入门基础理论知识

    本节介绍了音视频的基本原理知识以及编码相关概念。 视频(Video) 泛指将一系列静态影像以电信号的方式加以捕捉、 纪录、 处理、 储存、 传送与重现的各种技术。 连续的图像变化 每秒超过 24 帧(frame,fps) 画面以上时, 根据 视觉暂留原理 , 人眼无法辨别单幅的静态画

    2024年02月09日
    浏览(83)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包