硬核!一文梳理经典图网络模型

article/2025/7/11 2:57:59

dce28075484d7814b9473e7fa4895724.png

作者 | Chilia       

哥伦比亚大学 nlp搜索推荐   

整理 | NewBeeNLP

图神经网络已经在NLP、CV、搜索推荐广告等领域广泛应用,今天我们就来整体梳理一些经典常用的图网络模型:DeepWalk、GCN、Graphsage、GAT!

1. DeepWalk [2014]

DeepWalk是来解决图里面节点embedding问题的。Graph Embedding技术将图中的节点以低维稠密向量的形式进行表达,要求在原始图中相似(不同的方法对相似的定义不同)的节点其在低维表达空间也接近。得到的表达向量可以用来进行下游任务,如节点分类(node classification),链接预测(link prediction)等。

1.1 DeepWalk 算法原理

虽然DeepWalk是KDD 2014的工作,但却是我们了解Graph Embedding无法绕过的一个方法。

我们都知道在NLP任务中,word2vec是一种常用的word embedding方法,word2vec通过语料库中的句子序列来描述词与词的共现关系,进而学习到词语的向量表示。

DeepWalk的思想类似word2vec,使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系,DeepWalk给出的方法是使用**随机游走(RandomWalk)**的方式在图中进行节点采样。

RandomWalk是一种可重复访问visited节点的深度优先遍历算法。给定当前访问起始节点,从其邻居中随机采样节点作为下一个访问节点,重复此过程,直到访问序列长度 = K。获取足够数量的节点访问序列后,使用skip-gram进行向量学习,这样能够把握节点的共现信息。这样就得到了每个节点的embedding。

2. GCN [2016]

GCN的概念首次提出于ICLR 2017:SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS。

为什么要用GCN呢?这是因为对于图结构的数据,CNN、RNN都无法解决。

对于图片来说,我们用卷积核来提取特征,这是因为图片有平移不变性:一个小窗口无论移动到图片的哪一个位置,其内部的结构都是一模一样的,因此CNN可以实现参数共享。RNN主要用在NLP这种序列信息上。图片,或者语言,都属于欧式空间的数据,因此才有维度的概念,欧式空间的数据的特点就是结构很规则。

但是图结构(拓扑结构)如社交网络、知识图谱、分子结构等等是十分不规则的,可以认为是无限维的一种数据,所以它没有平移不变性。每一个节点的周围结构可能都是独一无二的,这种结构的数据,就让传统的CNN、RNN瞬间失效。

GCN,图卷积神经网络,实际上跟CNN的作用一样,就是一个特征提取器,只不过它的对象是图。GCN精妙地设计了一种从图数据中提取特征的方法,从而让我们可以使用这些特征去对图数据进行:

  • 节点分类(node classification)

  • 图分类(graph classification)

  • 链接预测(link prediction)

2.1 GCN的核心公式

假设我们手头有一个图,其中有N个节点,每个节点都有自己的特征embedding,我们设这些节点的特征组成一个N×D维的矩阵 ,然后各个节点之间的关系也会形成一个N×N维的矩阵A(就是邻接矩阵)

GCN也是一个神经网络层,它的层与层之间的传播方式是:

这个公式中:

  • , 是单位矩阵。

  • 是度矩阵(degree matrix),D[i][i]就是节点i的度。

  • H是每一层的特征,对于第一层(输入层)的话,就是矩阵 。

  • σ是非线性激活函数

用这个公式就可以很好地提取图的特征。假设我们构造一个两层的GCN,激活函数分别采用ReLU和Softmax,则整体的正向传播的公式为:

其中, .

那么, 为什么这个公式能提取图的特征呢?

  • A+I 其实是保证对于每个节点,都能够关注到其所有邻居节点自己的embedding。

  • 左右乘上度矩阵D是为了对A做一个标准化处理,让A的每一行加起来都是1.

当然,原论文中用非常复杂的数学公式做了很多证明,由于笔者数学不好,只能如此不求甚解的来粗略理解,感兴趣的同学可以自行阅读原论文。

3. GraphSAGE

3.1. GCN的局限

GCN本身有一个局限,即没法快速表示新节点。GCN需要把所有节点都参与训练(整个图都丢进去训练)才能得到node embedding,如果新node来了,没法得到新node的embedding。所以说,GCN是transductive的。(Transductive任务是指:训练阶段与测试阶段都基于同样的图结构

而GraphSAGE是inductive的。inductive任务是指:训练阶段与测试阶段需要处理的graph不同。通常是训练阶段只是在子图(subgraph)上进行,测试阶段需要处理未知的顶点。

要想得到新节点的表示,需要让新的node或者subgraph去和已经优化好的node embedding去“对齐”。然而每个节点的表示都是受到其他节点的影响(牵一发而动全身),因此添加一个节点,意味着许许多多与之相关的节点的表示都应该调整

3.2 GraphSAGE

针对这种问题,GraphSAGE模型提出了一种算法框架,可以很方便地得到新node的表示。

3.2.1 Embedding generation(前向传播算法)

Embedding generation算法共聚合K次,总共有K个聚合函数(aggregator),可以认为是K层,来聚合邻居节点的信息。假如 用来表示第k层每个节点的embedding,那么如何 从 得到呢?

  • 就是初始的每个节点embedding。

  • 对于每个节点v,都把它随机采样的若干邻居k-1层的所有向量表示 、以及节点v自己的k-1层表示聚合成一个向量,这样就得到了第层的表示 。这个聚合方法具体是怎么做的后面再详细介绍。

文中描述如下:

301e2bfc1a60f5a0e57b9bfa425801d5.png

随着层数K的增加,可以聚合越来越远距离的信息。这是因为,虽然每次选择邻居的时候就是从周围的一阶邻居中均匀地采样固定个数个邻居,但是由于节点的邻居也聚合了其邻居的信息,这样,在下一次聚合时,该节点就会接收到其邻居的邻居的信息,也就是聚合到了二阶邻居的信息了。这就像社交图谱中“朋友的朋友”的概念。

3.2.2 聚合函数选择
  • Mean Pooling:

这个比较好理解,就是当前节点v本身和它所有的邻居在k-1层的embedding的mean,然后经过MLP+sigmoid

  • LSTM Aggregator:把当前节点v的邻居随机打乱,输入到LSTM中。作者的想法是说LSTM的模型capacity更强。但是节点周围的邻居明明是没有顺序的,这样做似乎有不妥。

  • Pooling Aggregator:

把节点v的所有邻居节点都单独经过一个MLP+sigmoid得到一个向量,最后把所有邻居的向量做一个element-wise的max-pooling。

3.2.3 GraphSAGE的参数学习

GraphSAGE的参数就是聚合函数的参数。为了学习这些参数,需要设计合适的损失函数。

对于无监督学习,设计的损失函数应该让临近的节点的拥有相似的表示,反之应该表示大不相同。所以损失函数是这样的:

其中,节点v是和节点u在一定长度的random walk上共现的节点,所以它们的点积要尽可能大;后面这项是采了Q个负样本,它们的点积要尽可能小。这个loss和skip-gram中的negative sampling如出一辙。

对于有监督学习,可以直接使用cross-entropy loss等常规损失函数。当然,上面的这个loss也可以作为一个辅助loss。

3.3 和GCN的关系

原始GCN的方法,其实和GraphSAGE的Mean Pooling聚合方法是类似的,即每一层都聚合自己和自己邻居的归一化embedding表示。而GraphSAGE使用了其他capacity更大的聚合函数而已。

此外,GCN是一口气把整个图都丢进去训练,但是来了一个新的节点就不免又要把整个图重新训一次。而GraphSAGE则是在增加了新的节点之后,来增量更新旧的节点,调整整张图的embedding表示。只是生成新节点embedding的过程,实施起来相比于GCN更加灵活方便了。

4. GAT (Graph Attention Network)

4.1 GAT的具体做法

对于每个节点,注意力其在邻居顶点上的注意力。对于顶点 ,逐个计算它的邻居们和它自己之间的相似系数

首先一个共享参数 的线性映射对于顶点的特征进行了增维,当然这是一种常见的特征增强(feature augment)方法;之后,对变换后的特征进行了拼接(concatenate);最后 a(·)把拼接后的高维特征映射到一个实数上,作者是通过单层的MLP来实现的。

然后,再对此相关系数用softmax做归一化:

最后,根据计算好的注意力系数,把特征加权求和一下。这也是一种aggregation,只是和GCN不同,这个aggregation是带注意力权重的。

就是输出的节点的embedding,融合了其邻居和自身带注意力的权重(这里的注意力是self-attention)。

为了增强特征提取能力,用multi-head attention来进化增强一下:

4.2 与GCN的联系

GCN与GAT都是将邻居顶点的特征聚合到中心顶点上(一种aggregate运算)。不同的是GCN利用了拉普拉斯矩阵,GAT利用attention系数。一定程度上而言,GAT会更强,因为 顶点特征之间的相关性被更好地融入到模型中。

GAT适用于有向图。这是因为GAT的运算方式是逐顶点的运算(node-wise),每一次运算都需要循环遍历图上的所有顶点来完成。逐顶点运算意味着,摆脱了拉普利矩阵的束缚,使得有向图问题迎刃而解。也正因如此,GAT适用于inductive任务。与此相反的是,GCN是一种全图的计算方式,一次计算就更新全图的节点特征。

一起交流

想和你一起学习进步!『NewBeeNLP』目前已经建立了多个不同方向交流群(机器学习 / 深度学习 / 自然语言处理 / 搜索推荐 / 图网络 / 面试交流 / 等),名额有限,赶紧添加下方微信加入一起讨论交流吧!(注意一定o要备注信息才能通过)

edc7e5ffd5520e5cb6c53d4162d9fe39.png

END -

8a51f14cb21506221fade7a6bb0a7bd5.png

4c38118156adbbe651943ccf39136145.png

Green Deep Learning:NLP在大模型之外的另一种思路!

2022-01-22

d8429d891a3e1a531157662670307a9b.png

工作没满一年,我跳槽了!【附面经】

2022-01-24

c02bf1b29d8f81ac7b72a0486a07dabc.png

主动学习(Active Learning)概述及最新研究

2022-01-20

b8dd6b18e57bee9acd7aa0cfc9653a2d.png

搜索推荐广告中的Position Bias:美团DPIN

2022-01-19

d9f27f640d5de4c4c0ceb12a37b064f9.png

2ebf1bef0a176b18688eebec69d8936c.gif


http://chatgpt.dhexx.cn/article/xoUwqsAK.shtml

相关文章

图网络入门

目录 图网络基础知识 Graph Embedding 基础图网络模型 GCN GraphSAGE GAT 其他图网络模型 图网络基础知识 图网络的应用场景有很多,目前在工业界的主要应用是在推荐和风控领域,其他包括社交网络、交通网络、化学分子、3D点云等也都有一些应用。 …

图网络(Graph Network, GN)

目录 什么是图网络? 图网络框架 图网络内容 图的定义 GN块的内部结构 图网络中的关系归纳偏置 什么是图网络? 图网络是2018年由DeepMind、谷歌大脑、MIT和爱丁堡大学等公司和机构的27位科学家共同发表的论文《Relational inductive biases, deep …

图网络分类以及一些通用框架

图网络大体分类 递归图神经网络(Recurrent Graph Neural Networks)图卷积神经网络(Graph Convolution Networks)图注意力网络(Graph Attention Networks)图自编码器(Graph Auto-encoder&#x…

泛型的使用和作用

概述 泛型的使用 多态与泛型 两者要一致,Animal 和cat要一致 泛型的作用 提高 Java 程序的类型安全 通过前面的学习我们知道, 在集合中可以添加 Object 类型的对象, 如果在不使用泛型的情况下定义了一个 ArrayList 对象, 那 么各…

java泛型(java泛型的作用)

java泛型的基本使用是什么? add("test1"); String test1 (String)strList。get(0); System。out。println("Test 1 : " test1); } public void testGeneric() { List strList new ArrayList(); strList。 Java泛型的规则和限制有哪些呢&…

java泛型的作用及实现原理

一、泛型的介绍 泛型是Java 1.5的新特性,泛型的本质是参数化类型,也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中,分别称为泛型类、泛型接口、泛型方法。 Java泛型被引入的好处是安全简单。在Java …

泛型(一)--泛型的作用和定义

一、泛型的作用 泛型是.net中十分常见的一种特性。它是在.net 2.0的时候加入。那为什么要在.net 2.0的时候加入泛型这个特性呢?我们首先来看一段代码。 using System;namespace 泛型{class Program{static void Main(string[] args){int iParameter 1;string sPar…

什么叫泛型?有什么作用?

作者:Java3y 链接:https://www.zhihu.com/question/272185241/answer/366129174 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 一、什么是泛型? Java泛型设计原则:…

Java泛型的作用及优点有哪些

Java泛型是J2 SE1.5中引入的一个新特性,其本质是参数化类型,也就是说所操作的数据类型被指定为一个参数这种参数类型可以用在类、接口和方法的创建中,分别称为泛型类、泛型接口、泛型方法。 作用 第一是泛化。可以用T代表任意类型Java语言中引入泛型是一个较大的功能增强不…

第十章 泛型

10.1 泛型的理解和好处 10.1.1使用传统方法的问题分析 1)不能加入到集合ArrayList中的数据类型进行约束(不安全) 2)遍历的时候,需要进行类型转换,如果集合中的数据量较大,对效率有影响 10.1.2泛型的好处 1)编译时…

简述泛型的基本使用和作用

前言 在上一篇文章中,给大家讲解了泛型的概念、作用、使用场景,以及泛型集合、泛型接口和泛型类的用法,但受限于篇幅,并没有把泛型的内容讲解完毕。所以今天我们会继续学习泛型方法、泛型擦除,以及通配符等的内容&…

军职在线大学计算机基础(自主模式),《军职在线》中国哲学经典著作导读(自主模式)...

《军职在线》中国哲学经典着作导读(自主模式) 1《周易》导读 测试题C A C B D C D B B D D A B C D C D B A B 2《道德经》导读 测试题D C D C C C D A D C D B C C C A B A A B 3《庄子》导读 测试题D C D A A C B A A C A A C A D C B 4《论语》导读 测试题B B C ED B A A A …

台湾国立大学(林轩田)《机器学习技法》(第7讲)blending and bagging

课程地址:https://class.coursera.org/ntumlone-001/class 课件讲义:http://download.csdn.net/download/malele4th/10212756 注明:文中图片来自《机器学习技法》课程和部分博客 建议:建议读者学习林轩田老师原课程&#xff0c…

大学有新民之道,则大学生者负新民工作之实际责任者也。

梅贻琦,(1889-1962),字月涵,为梅曾臣长子。自1914年由美国吴士脱大学学成归国,即到清华担任教学和教务长等多种职务。1931年,梅贻琦出任清华校长,自此后一直到他在台湾去世&#xff…

【转载】中庸与技术书

2019独角兽企业重金招聘Python工程师标准>>> 转自:图灵社区 原文作者:刘祺 原文地址:http://www.ituring.com.cn/article/213657 本次转载已经过原作者同意,二次转载请自行联系原作者 #中庸与技术书 在我写这篇文章之前…

《大学》《中庸》全文及翻译 (转载)

《大学》全文及翻译 原文: 大学之道,在明明德,在亲民,在止于至善。知止而后有定,定而后能静,静而后能安,安而后能虑,虑而后能得。物有本末,事有终始,知所先后…

[C语言]求一个数是否是2的n次方

设a8,a的二进制数为1000,若为16,则是 0001 0000,2的n次方转为二进制则只保留一个 1 , 其余位置全是0,因此只要判断这个数的二进制是否只有一个 1 ,则知道这个数是否是2的n次方。 //求一个数是…

C语言|s1-s0|<=10的-6次方

#include <stdio.h> #include <math.h> double fun(double x) { double s11.0,s00.0; double t1.0; int n1; do { s0s1;//此时s0为s1的上一项 tt*(0.5-n1)*x/n; s1s1t; n; } while(fabs(s1-s0)>1e…

c语言字母能乘10吗,c语言编程中表示a乘以10的n次幂怎么表示

可以参考下面的代码&#xff1a; #include int main() { float a,s,n; sa*mi(10,n); return 0; } float mi(float x,int y) { float a; int i; a1; if(y>0) { for(i1;i<y;i) { aa*x; } } else { for(i-1;i>y;i--) { aa/x; } } return a; } 扩展资料&#xff1a; C语言…

c语言学习-编写函数求x的n次方的值

编写函数求x的n次方的值 程序流程图&#xff1a; 代码&#xff1a; #include<stdio.h> long mul(int j ,int k) { int i; long mu1; for(i0;i<k;i) mumu*j; return mu; } void main() { int x,n; long m; printf("please enter x\tn\t"); scanf("%…