数据派THU原创

2020/08/04 09:59

林夕作者林亦霖校对黄继彦编辑

斯坦福Machine Learning with Graphs学习笔记（第一讲）

一、Why Networks

二、网络的应用

2.1 应用领域

三、图的结构

3.1 网络表示的选择

3.2 点的度（Degree）

3.3 图的表示方式

邻接矩阵（Adjacency Matrix）

边列表（Edge list）

邻接列表（Adjacency list）

3.4 图的连通性

参考资料

最近我们小组开始整理CS224W机器学习图网络的一些笔记，这是第一课对应的PPT。

课程相关PPT链接：

http://web.stanford.edu/class/cs224w/slides/01-intro.pdf

一、Why Networks

第一部分简单介绍下关于图网络的一些基本定义，应用和意义。

网络的定义：网络是描述一系列交互实体的复杂系统的一种通用语言。

网络（Network）和图（Graph）的一些区别：

网络通常指真实的系统，eg.互联网、社交网络、信息网络、代谢网络、常用的表达有网络、节点、关系等；
图是网络的数学表达方式，比如互联网图谱、社交图谱、知识图谱、场景图、分子图（分子预测模型）。常用表达有图、顶点、边等词；
网络的概念比图的概念总体来看会大一点，但是总的来说network和graph区别也是比较模糊的，在实际中，这点区别也不会刻意强调，大家大致理解一下也就可以。

常见的网络比如有社会网络，通信网络，基因/蛋白质的互动网络，人脑神经元的连接网络。

现在学习图网络有什么意义呢。首先网络是一种描述复杂数据的通用语言，可以应用在众多领域，比如计算机，社会科学，物理学，经济学，生物都会涉及到对网络数据分析。其次网络数据关系能反应非欧式空间的数据关系，更能反应数据潜在的联系。另一方面，研究图网络将会对这些领域产生很大的影响。

接下来看网络的一些实际应用。

二、网络的应用

从网络分析方法角度来看，网络的应用可以分为以下几类：

节点分类（Node classification）：预测一个给定节点的类型；
链路预测（Link prediction）：预测两个节点是否是关联；
社区发现（Community detection）：识别密集的节点簇；
网络相似度分析（Network similarity）：节点或者网络相似度的测量。

2.1 应用领域

社交网络：研究人员从Facebook的数据中发现，人之间的平均距离实际是3.74。提出了新的4度社交网络。除此之外可以利用图聚类算法，识别社交圈。

基础建设（Infrastructure）：通过网络分析可以识别基建网络中哪里出了问题。比如电力系统中，可以通过图网络分析哪些点受影响比较严重。

知识图谱：知识图谱是异构图很好的例子，图的每一个结点具有不同的含义。可以对给定领域的知识进行编码。

推荐系统：预测一个用户的偏好，可以抽象为在一个二部图中预测边是否存在。涉及到的算法有Embedding Node, Graph-based algorithm recommend system。

生物化学应用：最近几年，使用图卷积网络（GNN）来预测药物的作用，相比点云技术（point-cloud based）已经获得了巨大的进展。预测药物相互组合的作用可以通过异构图来进行建模。

三、图的结构

这部分主要介绍图的结构以及图的一些表示方式和性质，以及如何选择适当的网络表示方式。

了解图的结构是图的分析的前提，一个网络是由一系列用边连接的实体构成（objects）。网络中的基本元素包括实体、关系和系统。

实体（objects）：节点（nodes）或顶点（vertex）N；
关系（interaction）：连接（links）或边（edges）E；
系统（system）：网络（network）或者图（graph）G(N,E)。

定义一个网络第一步就是选择表示实体，这个会决定研究的结果是否有意义，所以选择一个适当的网络表示方式非常重要。

比如当研究和工作有关系的人，可以构建一个职业网络；
当研究和性别有关系的人，可以构建一个性别网络；
当研究论文和引用的关系时，可以构建一个论文引用网络。

然后我们来看下如何定义一个网络。首先要知道如何构建一个图，构建一个图的两个关键是弄明白点是什么，边是什么。对于一个给定问题能否选择一个合适的网络决定了能否成功使用网络。有时候表示是唯一的、明确的，有时候表示是不唯一的，连边的方式将会决定研究的问题的本质。

3.1 网络表示的选择

图网络存在多种表示方式，根据边的连接是否有方向，可以分为有向图和无向图，根据边是否有权重可以分为有权图和无权图。除此之外，还有有环图，多边图，完全图，二部图等多种形式。

有向图 Vs 无向图：

无向图：边没有方向，例如，社交网络的关系；
有向图：边有方向，例如，打电话，Twitter的Follow。

完全图（complete graph）：

无向图的最大边数：；
当一个无向图中每个节点都有最大的边数的图叫完全图；
平均度是 N-1；

二部图（Bipartite Graph）：

二部图是一种可以将节点分成两个子集U和V（U和V是互相独立的集合），如果对于U集合中每个节点都有V的节点与之对应或者U中每个节点都有U的节点与之对应。这种图描述了两类对象之间的交互关系。以下几种关系可以构造二部图。

作者和文章；
演员和电影；
用户和电影；
菜谱和菜品之间的关系等。

无权图（unweighted）：边没有权重，有边权重都是1，否则是0；

无权图（weighted）：边上有权重，赋权值；

有环图（self-loops）：某些点上有环；

多边图（Multi-graph）：有的两点之间存在多条边；

3.2 点的度（Degree）

点的度是网络的一个重要属性。无向图和有向图点的度有所不同，需要分开来考虑。

无向图：

点的度：和点相连的边数；
平均度：每个点的度取平均。

有向图：

3.3 图的表示方式

邻接列表（Adjacency list）：

当网络很大，并且很稀疏的时候，这样表示非常方便，通过这种方式能迅速获取到一个点邻接点。依然是上图，邻接列表可以表示为：

1:
2:3,4
3:2,4
4:5
5:1,2

3.4 图的连通性

无向图的连通性：如果一个无向图的任何两个顶点（vertices）之间都有路径相连，那么认为这个图是连通的。反之，如果由两个或者更多的连通图构成则是非连通图。桥边（Bridge edge）是指删除以后能使图变成非连通图的边。在邻接矩阵中，非连通图，非0的部分被限制在块对角矩阵内，其他元素是0。

有向图的连通性：如果一个有向图的任意两个点存在路径，包括反向的，则认为是强连通的。不考虑边的方向，任意两个点存在路径则认为是弱连通的。另外，我们定义强连通组件（Strongly connectedcomponents-SCCs），它是指图的子图，并且是强连通的。