CS224W笔记-第一课

时间:2024-10-26 08:47:50

第一课:课程介绍和基本概念

CS224的课程题目在2019学年改成了《图的机器学习》,老师还是Jure Leskovec。第一节课对整个课程进行了介绍。主要内容包括3个部分:

  1. 什么是图(Graph)及研究的内容。
  2. 课程的安排和后勤。
  3. 核心概念和名词属于

一、什么是图及研究的内容

2019年的课程内容做了比较大的修改,从原来的主要是做图分析,改成偏重于进行基于图的预测,所以课程名称也改为《图机器学习》。

课程主要的内容是研究: 以图形式表征的数据

图是什么

General language for describing complex system of interacting entities.

图的两种常见的说法:

  • 网络(network):偏向于自然存在的图结构,比如互联网、社交网络等。
  • 信息图(information graph):偏向于人为概念出来的图,比如知识图谱、相似网络等。
图研究的主要问题:
  1. 图系统是如何组织的,
  2. 它们有什么特征?
  3. 我们如何利用图的结构特性进行更好的预测。
图研究的主要驱动原因:

除非我们能够理解和了解这些图结构的系统,否则我们无法对它们进行建模及预测。

下面是为什么个学生要学习图研究。虽然Jure说了半天,其实趋势已经这样了,大家也要跟上潮流啊。不然怎么找工作。呵呵。。。。

机器学习图研究的具体应用的问题

  1. 节点预测:分类、回归。
  2. 边预测:两个节点间是否应该有边连接。
  3. 社区检测:发现密集连接的节点群。
  4. 网络相似度测量:测量多节点/网络的相似度

下面给出了一系列的网络研究和应用的例子,比如FB的social circle发现、基础设施故障的影响、多态知识图谱(KG)、推荐里面应用的边预测、知识图谱在推荐里的应用(Pinterest)、图向量Embedding、社交媒体里的观点分类、Wiki假/欺骗文档的识别、信息传播模式的识别、生物医疗里面的药物副作用预测。最后一个是Jure自己的研究,所以讲了很多。

二、课程的安排和后勤

大部分内容都是给斯坦福学生的。要了解的是这个课程很长,一共19次课,每次视频都一个多小时,覆盖了很多内容。同时课程的作业使用的是他们自己开发的这个工具包。如果想要更好的GNN的Python包,这里推荐DGL(Deep Graph Library)这个框架,对于想直接使用GNN的用户很方便了。

三、基本名词概念

图的基本结构概念

网络是一些对象的集合,其中部分对象之间通过链接互相作用在一起。

图的组成部分:

  • 对象:node、vertices —— N
  • 交互作用:link、edge —— E
  • 系统:network、graph —— G(N, E)

课程里对network和graph这两个名词进行了区分。Network更多的指向现实世界里的系统;而graph是对network的数学表示。

对同一个network的不同表示,可以产生不同的graph

图的定义方法

对于node和edge的不同选择,会对同一个network实体产生不同的graph,比如都是科学文献,可是产生co-author network,也可以产生citation-network。

随后Jure介绍了一些不同的node和edge的特征,形成了图的基本名词概念

有向和无向边:undirected/directed edge

无向边的图会有对称关系,而有向边则缺乏这个性质。

节点的度

:和nodei 相连的边的数量。K
对于有向图,还区分入度出度。分别是指向node的边的数量和发出的边的数量。总度是入度和出度的和。

平均度:图内所有节点的度的和,除以节点的数量。
对于无向图,等于边的数量*2,再除以节点的数量,2E/N
对于有向图,就是边的数量,除以节点的数量,E/N

完全图(complete graph)

对于无向图,最大的边数是 Emax=(N,2)=N(N-1)/2
如果一个图的边的数量等于_Emax_,那么这个图就叫完全图。完全图的平均度=N-1

二分图(bipartite graph)

这里借用Wiki里的定义二分图

在圖論中,二分图是一類特殊的圖,又稱為雙分圖、二部图、偶图。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖,使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。

二分图里的折叠图(folded graph)
U或者V中的两个node,如果它们共享一个端节点,则它们之间可以建立起一个link,由此对于U或者V则可以分别构建出一个图,就是折叠图。比如作者->文章的二分图,作者可以沟通co-auther的折叠图,文章可以构成同作者的折叠图。

图的表示方法

一、邻接矩阵(Adjacency Matrix)

一个N by N的矩阵,其中N是图的节点数量。矩阵里如果两个节点间有变,则相应的位置的值为1,否则为0。

无向图的邻接矩阵是对称的,而有向图则不一定。

计算一个节点的就可以统计它对应的行或者列的和。

二、 边列表(Edge List)

只记录边的起点和终点的列表,比如:
(1,2)
(1,3)

(10,50)

三、邻接列表(Adjacency List)

只记录邻接矩阵里的行里有值的对应节点,比如:
1:
2: 3,4
3: 2,3
4: 5

图表征的性质

大部分现实世界的网络都是稀疏的。即,E << Emax,或者图的平均度都远远小于节点的数量。因此邻接矩阵通常都是充满了0,二矩阵密度都是非常小的值,如10-8矩阵密度=E/N2

边的类型

除了节点,边也可以被赋予很多属性:权重、排序、符号、类别等待。在邻接矩阵里,可以使用数字来代替1,0的值,记录这些边的类型。

图的类型

自环图:节点自己可以有边连接到自己。
多图:节点和节点间有超过一条的变。

无向图的连接性

完全连接的图:无向图里任何两个节点都可以通过一系列的变连起来。
非完全连接的图:由两个或两个以上的完全连接图构成的图。
图中连接在一起的部分,叫component,最大的component叫giant component。
强连接:两两节点见都可以连接起来。双向
弱连接:不一定两两见都可以连起来。可能只有单向