目录

1 什么是图？

2 图能做什么？

3 传统的图算法从应用角度可分为三类

3.1 路径查找算法——Dijkstra

3.2 中心度算法——PageRank

3.3 社区发现算法——LPA

4 图神经网络

5 网络表示学习和图嵌入

5.1 基于矩阵分解的图嵌入

5.2 基于随机游走的图嵌入

5.3 基于图神经网络的图嵌入

引用：

---

1 什么是图？

图是一种常见的数据结构，用于表示对象及其之间的关系。其中，对象又称节点（node）或顶点（vertex），关系用边（edge）来描述。在数学上一般用 G=(V,E,A,X) 来表示，其中 V={v1,v2……,vn} 是节点集合，E=e_ij 表示边的集合，A 是大小为|V|×|V|的邻接矩阵，用于表示节点之间的连接关系，如果 e_ij∈E，则 A_ij=1，X 是大小为|V|×d 的特征矩阵，X 的第 i 行 X_i:表示第 i 个节点的属性特征，其中 d 是属性的维度。

 

2 图能做什么？

上图中，右侧手机号171505****关联了393个人，16年-19年累计进件1665次，放款65笔，其中33笔当期状态是逾期！

 

3 传统的图算法从应用角度可分为三类

1. 路径查找算法

2. 中心度算法

3. 社区发现算法

 

3.1 路径查找算法——Dijkstra

Dijkstra是一个贪心算法，用于在加权的图中查找最短路径，比起无脑的遍历，Dijkstra优化的点是，为了避免不必要的

重复计算，保留上一步的计算信息。

对于带权有向或无向图 G=(V,E)，Dijkstra 算法的复杂度为O(V^2) 只有当权重为正值时有效，基于 Fibonacci heap 的最

小优先队列实现版本，其时间复杂度为O(E+VlogV)。当权重有负值，可使用贝尔曼-福特算法。

1. 指定一个节点，例如我们要计算 'A' 到其他节点的最短路径
2. 引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该
点的路径，注意 如上图所示，A->E由于没有直接相连 初始时为∞）
3. 初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0，U集合初始时为 A->B = 8, A->E = ∞, A->D = 1, 
A->C = 5
4. 从U集合中找出路径最短的点，加入S集合，例如 A->D = 1
5. 更新U集合路径，if ( 'D 到 C,E 的距离' + 'AD 距离' < 'A 到 C,E 的距离' ) 则更新U
循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

3.2 中心度算法——PageRank

定义问题： 一个网站的排名，如何确定；或一个人在社交网络中的影响力，如何确定；

被一个门户网站指向，被一个大V关注……

假设，4个网站之间的跳转入左图，抽象出来就是转移矩阵M，假设一个人最开始访问这四个网站的概率都是1/4，那经过第一轮跳转

终止点问题&陷阱问题

在计算PR时，增加空值随机跳出的阻尼系数β，可以理解成关掉无外链的网页，重新随机打开一个新的网页。

3.3 社区发现算法——LPA

LPA算法是一个极其简单的图传播算法，其经验假设是以节点为中心，进行投票制，十分高效。

1. 初始化，将图中的每个节点看成一个独立的社区；
2. While所有节点的社区标签不再变化；
    统计每个节点邻居的社区，将出现最多次的社区赋给该节点，如果出现最多次的社区有多个，随机选择一个社区赋给该节点。

算法本身很简单，分布式实现也很容易。但是这个算法也存在很大的问题：由于存在随机选择的情况，所以算法很容易

出现振荡。但这个算法的运行开销很低，拿来做baseline，作为参考也是可以的。另外，对于一个带权重的图，亦可以

考虑带权重的投票机制。

另：半监督学习版LPA

构建转移矩阵M，M中的转移概率计算方法为W_ij = exp(- d_ij/σ^2)
2. 对未标注的样本随机初始化，已标注样本为样本标签，构造状态矩阵R
3. 按转移概率，对矩阵R的状态进行更新，只更新未标注样本(同样可以加入阻尼系数β)
4. 对行进行归一化
5. 重复3,4步骤直到收敛

4 图神经网络

图神经网络(Graph Neural Network)是直接在图数据结构上运行的神经网络。GNN的典型应用便是节点分类。图中的每

个节点都有一个标签，我们希望不需要标注数据，可以预测新的节点标签。在首次提出GNN的论文《The graph neural

network model》中来看GNN的定义。

在节点分类问题中，每个节点v的特征用xv表示，并且和标签tv相关联。给定部分标记的图G，目标是利用这些标

记的节点来预测未标记节点的标签。网络学会用d维向量（状态）hv表示每个节点，其中包含其邻域信息。

其中，xco[v]表示与v连接的边的特征，hne[v]表示v的相邻节点嵌入表示，xne[v]表示v的相邻节点的特征。函数f是将这

些输入投影到d维空间的传递函数。

通过将状态hv以及特征xv传递给输出函数g来计算GNN的输出：

f和这里的g都可以解释为前馈全连接神经网络。 L1损失可以直接表述如下：

关键问题就是x、h的向量表示 —— everything2vec。

5 网络表示学习和图嵌入

将图的拓扑结构、节点属性、节点标签特征经过神经网络非线性映射，在深层可以提取到更高层次的特征表示，然后变换

成一个向量通过全连接层进行分类，那提取这个向量的过程称为表示学习（Representation Learning）。图嵌入也类似，

通过神经网络学习从节点到向量的映射，尽可能的保留住节点的结构信息和属性信息。图嵌入方法可以分为基于矩阵分解

的图嵌入、基于随机游走的图嵌入、基于神经网络的图嵌入（即图神经网络）。

5.1 基于矩阵分解的图嵌入

邻接矩阵(adjacency matrix)

拉普拉斯矩阵

L=D-A

5.2 基于随机游走的图嵌入

DeepWalk 算法

基于word2vec提出来的，将节点当做词，随机游走得到的节点序列当做句子，用word2vec的框架(skip-gram+

Hierarchical Softmax）来进行词嵌入。

node2vec 算法

node2vec通过改变随机游走序列生成的方式进一步扩展了DeepWalk算法。DeepWalk选取随机游走序列中下一个节点

的方式是均匀随机分布的，而node2vec通过引入两个参数p和q，将宽度优先搜索和深度优先搜索引入随机游走序列的

生成过程。广度优先搜索注重刻画网络中的局部特征，而深度优先搜索能更好地遍历整个网络，反映了节点间的同质性。

t为游走初始节点（顶点），v为当前节点，dtx为顶点t和顶点x之间的最短路径距离

 

5.3 基于图神经网络的图嵌入

图嵌入框架

Hamilton 提出的一种图嵌入 encoder-decoder 框架，可以将大多数的图嵌入方法用这个框架来表示。在这个框架中，

我们围绕两个关键的映射函数组织了各种方法：一个 encoder(它将每个节点映射到一个低维向量) 和一个 decoder(它

从已知的嵌入中解码关于图的结构信息)。encoder-decoder 背后的直觉想法是这样的:如果我们能从低位嵌入表示中学

会解码高维图信息，如节点在图中的全局位置或节点的局部邻域结构，那么原则上，这些嵌入应包含下游机器学习任务

所需的所有信息。

 

decoder 是接受一组节点嵌入并从这些嵌入中解码用户指定的图统计数据的函数。例如，decoder 可能根据节点的嵌入

预测节点之间是否存在边，或者可能预测图中节点所属的社区。

 

GraphASGE算法

对于一个图G，先从一度节点中随机采样，再从一度采样节点的二度节点随机采样，得到如图一度3个二度5个节点。根

节点从采样的一度节点中使用aggregator1提取信息，一度节点从二度节点中使用aggregator2提取信息，一层层向内

聚，最终得到根节点的表征向量。

算法伪代码如下：

其中，第一层循环k表示第k层或k度（比如开始的例子中k属于[0,1,2]），hk表示在这一层中一个节点的表征，xv是v节点

的特征向量（如果节点没有特征表示可以进行随机初始化？那这个过程学习到的只是网络的拓扑结构）N表示相邻节点采

样函数。

过程是这样的：

k=1时：①每个节点v从相邻节点通过N采样得到ui，通过AGGREGATEk得到根据邻居节点对v节点的表征hN(v)；②将v节点

的k=0原始特征向量hv与hN(v)合并(concat)后经过W矩阵映射及σ非线性映射（非线性激活函数的全连接层），得到k=1层

节点v的表征hv；③遍历完全部节点后，对hv归一化；

k=2时：……

通常k不需要取3度以上，2度关系的表征对大部分场景已经足够。

损失函数

可以通过无监督方式或有监督方式进行，优化方向是，希望节点u与相邻节点相似度高，但与没有交集(n度以上)的节点相

似度低；

有监督的方式可以根据给定label的类型选择损失函数，比如：二分类可以采用交叉熵损失函数。

聚合函数

伪代码第5行可以使用不同聚合函数，本小节介绍五种满足排序不变量的聚合函数：平均、GCN归纳式、LSTM、pooling

聚合器。（因为邻居没有顺序，聚合函数需要满足排序不变量的特性，即输入顺序不会影响函数结果）

• a.平均聚合：直接对目标节点和所有邻居emebdding中每个维度取平均（替换伪代码中第5、6行），后再非线性转换；

• b. 归纳式聚合：先对邻居embedding中每个维度取平均，然后与目标节点embedding拼接后进行非线性转换；

• c. LSTM聚合：LSTM函数不符合“排序不变量”的性质Å，需要先对邻居随机排序，然后将随机的邻居序列embedding作为

LSTM输入；

• d. Pooling聚合：将相邻的相邻都扔进一个全连接神经网络中，

 

引用：

1. 简单的图神经网络介绍 https://www.jiqizhixin.com/articles/2019-02-15-14

2. 从数据结构到算法：图网络方法初探https://www.jiqizhixin.com/articles/2019-08-12-9

3. 《Graph_Algorithms_Neo4j》Mark Needham & Amy E. Hodler

4. 《图数据库》第二版 Ian Robinson著

5. Inductive Representation Learning on Large Graphs, William L. Hamilton, 2017

6. 图的邻接矩阵的实现 https://blog.csdn.net/canot/article/details/78703184

7. lpa标签传播算法讲解及代码实现 https://blog.csdn.net/nwpuwyk/article/details/47426909#commentBox

Java集合是用于存储数量不等的对象的容器，还可以保存具有映射关系的关联数组， Collection是集合接口，它提供了对集合对象进行基本操作的通用接口方法。

Java集合大致分为下面四种类型：List，Set,Queue,Map。

List代表有序，可重复集合，Set代表无序，不可重复集合，Queue代表队列集合，Map代表具有映射关系的集合。

Java集合主要有Collection和Map接口派生，他们是集合的根接口。
List,Set,Queue继承Collection接口，如下继承图：

Map接口的继承树：

Java集合类图如下：本身想自己画个，但是画出的效果不太好，从网上找个例图。

知识图谱（ Knowledge Graph）以结构化的形式描述客观世界中概念、实体及其关系，将互联网的信息表达成更接近人类认知世界的形式，提供了一种更好地组织、管理和理解互联网海量信息的能力。上述一大段是我从2018知识图谱发展报告中copy下来的一段话，用普通人能听懂的人话来描述:知识图谱就是把去发现世间万物的之间的联系。 在技术上就是将数据以一个一个的的三元组形式存储起来。

不知道大家有没有这样一种感受，如果你在某一领域的学习了解到很多的知识碎片，却无法将他们关联起来，这些知识碎片并不会加深你对这一领域的认知。而如果你能将他们联系起来，串联成一张知识网，那很有可能你就是这个领域决定的专家。因为你的脑中有这个领域的知识网，你就能知道这个领域的边界在哪。知识图谱就是要将知识串联起来，形成一张知识网。

知识图谱的应用场景：

知识图谱主要分为两类：

通用知识图谱和领域知识图谱。通用知识图谱主要需要知识的广度，而领域知识图谱需要知识具有深度。

通用知识图谱最普遍的应用场景就是：搜索引擎，

领域知识图谱的应用场景则比较丰富多样：司法，医疗，金融，电商等各行各业都可以构建属于自己行业的知识图谱，而这些知识图谱可以用于智能问答，辅助决策，风险规避等。

当然以上只是知识图谱被应用最多的场景，还有一些很有潜力的应用场景，比如将知识图谱和深度学习结合等。知识图谱这个新的，年轻的概念还等着大家去探索更多的应用可能性。

知识图谱的构建简介

这里笔者就不没有考虑业务逻辑，也不考虑构建过程中一下细节技术，直接讲一个简单粗暴版的构建流程。

实体抽取，实体链接（两个实体同一个含义需要规整），目前最主流的算法就是CNN+LSTM+CRF进行实体识别。

实体之间，关系抽取，拿到知识图谱最小单元三元组，比较经典算法的就是Piece-Wise-CNN,和 LSTM+ Attention 。

知识存储，一般采用图数据库（neo4j等）。

但是要注意的是，知识图谱一定要最先定义好构建它是用来干什么，目标业务导向，定义好符合业务逻辑schema层才是最最重要的。有了schema之后接下来的任务就是实体抽取和关系抽取啰，其中关系抽取是把知识点串联成一张知识网的重要过程，所以这里笔者着重介绍一下最近在知识图谱领域很火的有监督的关系抽取任务的一个模型PCNN。

关系抽取之PCNN（Piece-Wise-CNN）

这里笔者仔细解释一下有监督的关系抽取的任务的数据样式，任务形式，以及PCNN（Piece-Wise-CNN）的思想和tensorflow实现。

关系抽取数据：

data.png

input : 句子 Steve Jobs was the co-founder of Apple Inc和两个entities Steve Jobs 和 Apple Inc。

out： 实体之间关系 ： /business/company/founder

所以我们可以将其抽象成一个分类问题，输入句子和实体信息，然后让模型分出这两个实体之间的关系属于哪一类。

PCNN

下图清晰了显示了PCNN的整个网络架构，原文链接在这里，下面我对着下图介绍一下PCNN的实现过程：

数据预处理：首先对数据进行位置编码，按句子中各个词离entity的距离进行编码。

例如：“As we known，Steve Jobs was the co-founder of Apple Inc which is a great company in America.”

由于句子中有两个entity，所以这条句子就会产生两个和句子长度相同的编码。

pos_1:[-4,-3,-2,-1,0,1,2,3……] ,其中0就是Steve Jobs的位置。

pos_2:[-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3……] 其中0就是Apple Inc的位置。

切分句子：其中最主要的就是将一条文本数据在两个entity处各切一刀将文本且成了3段。

比如 As we known，Steve Jobs was the co-founder of Apple Inc which is a great company in America，将被切成：

As we known，Steve Jobs

Steve Jobs was the co-founder of Apple Inc

Apple Inc which is a great company in America.

注意，位置向量也同样进行了切分操作。

特征提取：将位置特征和文本特征拼接之后，然后将上面三个数据分别通过CNN 提取特征，

关系分类：提取出来的特征通过maxpooling层之后进行拼接后送入softmax层，最终得到relation的分类。

pcnn.png

从上面PCNN的流程我们可以发现，这个网络结构很注重entitiy之间的距离信息，位置信息，以及entitiy之间或者左右的信息。其实这些都是是关系抽取中最重要的特征。

一般来说两个entitiy之间距离越近，则他们有关系的可能性越大。

而透露出entities之间有关系的词一般会出现在两个entity之间，左侧，或者右侧。

例如：Steve Jobs was the co-founder of Apple Inc ， 关系词 co-founder就在两个entity之间

tensorflow 代码实现

由于之前对PCNN的整个流程有了比较详细的解释，这里笔者只是简单的介绍一下代码构成。

下方这一步是已经将文本向量和位置向量进行了切分，由于文本被两个entity分成了左，中，右三段，再这三段加上各自的两个位置向量。所以网络一共有9个输入，加上关系label输出，一共需要定义10个placeholder。

import tensorflow as tf

import os

os.environ['CUDA_VISIBLE_DEVICES'] = '1'

tf.reset_default_graph()

word_ids_left = tf.placeholder(tf.float32, shape=[None, maxlen, word_emb_size])

word_ids_mid = tf.placeholder(tf.float32, shape=[None, maxlen, word_emb_size])

word_ids_right = tf.placeholder(tf.float32, shape=[None, maxlen, word_emb_size])

pos_l_1 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_l_2 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_m_1 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_m_2 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_r_1 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_r_2 = tf.placeholder(tf.int32, shape=[None, maxlen])

pos_r_2 = tf.placeholder(tf.int32, shape=[None, maxlen])

label = tf.placeholder(dtype=tf.int32,shape=[None,n_class])

下方代码这是PCNN的实现，其中Piece_Wise_CNN函数是对PCNN的实现。

def get_sentence_emb(word_ids,pos_1,pos_2):

pos_emb_l1 = tf.keras.layers.Embedding(input_dim=498,output_dim=10,input_length=100)(pos_l_1)

pos_emb_l2 = tf.keras.layers.Embedding(input_dim=498,output_dim=10,input_length=100)(pos_l_2)

return tf.concat([word_ids,pos_emb_l1,pos_emb_l2],2)#[batch_size,maxlen,word_emb_size+2*pos_emb_size(10)]

def Piece_Wise_CNN(left_emb,mid_emb,right_emb,feature_map,n_class):

left = tf.keras.layers.Conv1D(filters=feature_map,kernel_size=3)(left_emb)#[batch_size,maxlen,word_emb_size+2*pos_emb_size(10)]

left = tf.keras.layers.GlobalMaxPool1D()(left)#[batch_size,feature_map]

mid = tf.keras.layers.Conv1D(filters=feature_map,kernel_size=3)(mid_emb)#[batch_size,maxlen,word_emb_size+2*pos_emb_size(10)]

mid = tf.keras.layers.GlobalMaxPool1D()(mid)#[batch_size,feature_map]

right = tf.keras.layers.Conv1D(filters=feature_map,kernel_size=3)(right_emb)#[batch_size,maxlen,word_emb_size+2*pos_emb_size(10)]

right = tf.keras.layers.GlobalMaxPool1D()(right)#[batch_size,feature_map]

final_feature = tf.concat([left,mid,right],1)#[batch_size,3*feature_map]

out = tf.keras.layers.Dense(n_class,activation="softmax")(final_feature) #[batch_size,n_class]

return out

def train_op(out,label,lr):

losses = tf.nn.softmax_cross_entropy_with_logits_v2(

logits=out, labels=label)

loss = tf.reduce_mean(losses)

train_op = tf.train.GradientDescentOptimizer(learning_rate=lr).minimize(loss)

return train_op,loss

这里是定义train_op部分。

left_emb = get_sentence_emb(word_ids_left,pos_l_1,pos_l_2)

mid_emb = get_sentence_emb(word_ids_mid,pos_m_1,pos_m_2)

right_emb = get_sentence_emb(word_ids_right,pos_r_1,pos_r_2)

out = Piece_Wise_CNN(left_emb,mid_emb,right_emb,20,n_class)

train_op,loss = train_op(out,label,lr = 0.01)

结语

这里笔者主要是想通过PCNN这个经典的关系抽取网络说明：其实有监督的关系抽取任务的关键是需要神经网络理解两个entity之间的语义连结，所以，而如何利用好句子中entity周围的词语的语义信息和entity之间的位置信息，可能是解决这类任务的关键。笔者在之前的文章中多次强调过自然语言处理最终目标还是希望算法能够理解语义。像PCNN这个网络则提出了切分句子，集中注意力关注句子提供关键信息的部分(自己的理解)，也许是一个好的方向。