谷歌、阿里、腾讯等在大规模图神经网络上必用的GNN加速算法(二)

简介: 谷歌、阿里、腾讯等在大规模图神经网络上必用的GNN加速算法(二)

2.Layer-wise sampling


2.1 FastGCN



220cce32af70bd4fdc5792ab786e4687.png


论文标题:FastGCN: fast learning with graph convolutional networks via importance sampling


论文来源:ICLR2018


论文方向:图卷积网络


论文链接:https://arxiv.org/abs/1801.10247


我们已知,GCN的形式为:


bd6a734a1040bd188eb36492a22b4552.png


从积分的角度看待图卷积,假设图是无限大图的子集,所有结点为独立同分布的结点,满足


6e96041cb8a507871be32b1713ba13a1.png

34861fd0e9299f8c29f9af7f5b3ed9d5.png



则可以应用蒙特卡洛法,对每一层进行采样 个结点, 来近似积分,以前层的结点作为共享邻居集合:


e1e62940a33e79fb60b73eb9b939f146.png


此外为了减少估计方差(Variance Reduction),采用重要性采样(Importance samling),结点根据以下概率分布采样:



27e8dd3caf602914b05a7bffaee70c2d.pnge1e62940a33e79fb60b73eb9b939f146.png


2.2 ASGCN



777c6424ebb516400c28710aff57f04f.png


论文标题:Adaptive Sampling Towards Fast Graph Representation Learning


论文来源:NIPS2018


论文方向:图卷积网络


论文链接:https://arxiv.org/abs/1809.05343


c75393a181f27cc21858ae441c79a179.png


对FastGCN的最后一个公式,其最优的解(最小化从 抽样出的结点的方差, )为:


3f5c839b4e947af2cd8bf8ee4484c3f2.png


其中 ,而 则是上一层结点从邻居聚集而来的隐层表示。在FastGCN中,则有


为了防止递归困境,为importance sampling学习一个独立的决定其重要性的函数(Adaptive sampling),基于结点的特征 来计算:


1dd3c5a52cba28d0c31001f71776c9d0 (1).png


因此最终的抽样结点的分布为:


501ad53199ad6004ee38891e4b551be4.png

相关文章
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
33 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
4月前
|
机器学习/深度学习 数据采集 人工智能
算法金 | 致敬深度学习三巨头:不愧是腾讯,LeNet问的巨细。。。
**LeNet 摘要** - LeNet 是 Yann LeCun 在 1989 年提出的卷积神经网络,用于手写数字识别,是深度学习和计算机视觉的里程碑。 - 网络结构包括卷积层(C1, C3, C5)、池化层(S2, S4)和全连接层(F6),处理 32x32 灰度图像,最终分类为 10 类。 - 卷积层提取特征,池化层降低维度,全连接层负责分类。激活函数主要使用 Sigmoid。 - LeNet 在 MNIST 数据集上表现优秀,但现代网络常使用 ReLU 激活和更深结构。 - LeNet 的局限性包括网络较浅、Sigmoid 梯度消失问题和平均池化,但其创新为后续 CNN 发展铺平道路
56 1
算法金 | 致敬深度学习三巨头:不愧是腾讯,LeNet问的巨细。。。
|
5月前
|
机器学习/深度学习 人工智能 自然语言处理
算法金 | 不愧是腾讯,问基础巨细节 。。。
**摘要:** 本文介绍了Adaboost算法的基本概念、工作原理和数学基础,它是由 Freund 和 Schapire 在 1996 年提出的迭代机器学习算法,通过组合多个弱分类器形成强分类器。Adaboost 通过调整样本权重,重点关注被错误分类的样本,以提高分类性能。文章还提供了代码示例,展示了如何使用决策树作为弱分类器,并在鸢尾花数据集上应用 Adaboost 分类器。此外,还讨论了Adaboost的优缺点及适用场景,强调其在分类问题上的高效性和广泛应用。
47 1
算法金 | 不愧是腾讯,问基础巨细节 。。。
|
5月前
|
机器学习/深度学习 数据采集 TensorFlow
使用Python实现深度学习模型:图神经网络(GNN)
使用Python实现深度学习模型:图神经网络(GNN)
295 1
|
4月前
|
Linux 网络安全 数据安全/隐私保护
网络安全教程-------渗透工具Kali,官网链接,ARM的介绍,Mobil,华为小米,oppe手机,是无法刷入第三方的操作系统的,E+手机,谷歌的picksoul,或者三星手机,系统盘是WSL的
网络安全教程-------渗透工具Kali,官网链接,ARM的介绍,Mobil,华为小米,oppe手机,是无法刷入第三方的操作系统的,E+手机,谷歌的picksoul,或者三星手机,系统盘是WSL的
|
6月前
|
机器学习/深度学习 数据挖掘 算法框架/工具
想要了解图或图神经网络?没有比看论文更好的方式,面试阿里国际站运营一般会问什么
想要了解图或图神经网络?没有比看论文更好的方式,面试阿里国际站运营一般会问什么
|
6月前
|
算法 架构师 网络协议
对标腾讯T9架构师的 Android 面试题新鲜出炉,算法真的太重要了
对标腾讯T9架构师的 Android 面试题新鲜出炉,算法真的太重要了
|
6月前
|
机器学习/深度学习 安全 网络安全
谷歌推出新一代恶意文件检测工具Magika:网络安全的重大进步
【2月更文挑战第9天】谷歌推出新一代恶意文件检测工具Magika:网络安全的重大进步
123 4
谷歌推出新一代恶意文件检测工具Magika:网络安全的重大进步
|
6月前
|
存储 算法
【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解
【数据结构与算法】【腾讯阿里链表面试题】算法题--链表易懂版讲解
|
6月前
|
存储 人工智能 算法
大数乘法的几种算法分析及比较(2014腾讯南京笔试题)
大数乘法的几种算法分析及比较(2014腾讯南京笔试题)
下一篇
无影云桌面