CS224W：图机器学习1

• 斯坦福大学公开课CS224W的学习笔记

图机器学习导论

图机器学习研究的问题

• 图结构和网络结构是非常常见的数据结构，常见的事件图、计算机网络、事务网、社交网络和人际关系网等等都是图状结构
  • 网络也叫做自然图Natural Graphs
  • 图是对于一些关系的表示，可以表示信息和知识的联系，软件也可以表示为一张图
  • 很多时候网络和图的区别是非常模糊的，通常可以将它们混为一谈，而该课程要研究的也就是如何利用图中的关系来进行更好的预测
• 相比于图像和文本，图结构的大小比较随意，没有固定的节点顺序，并且通常是动态的
• 图学习的任务可以有node level，edge level，community level和graph-level多个层次，常见的有
  • 节点分类：比如预测线上用户的类型
  • 链接预测：预测两个节点之间是否缺少了链接，比如知识图谱补全
  • 图分类：比如化学中的分子性质预测
  • 聚类：检测节点是否构成一个类别，比如社交圈检测
  • 其他的还有图生成，图进化等等

图的表示方式

• 常见的表示方式使用节点集合N和边集合E构成一个图结构#card=math&code=G%28N%2C%20E%29&id=sbIiz)
  • 图可以分为有向图和无向图，区别就在于边是否具有方向性，节点的degree表示包含这个节点的边的数量，而在有向图中又可以具体分为出度和入度
  • 二分图是一种特殊的图结构，可以将图中的节点分成两个不相交的集合U和V，使得图中的任意一条边的两个顶点分别属于U和V
• 图也可以用接邻矩阵来表示，其中无向图的邻接矩阵是一个对称矩阵，通常邻接矩阵都比较稀疏，网络结构通常都是比较稀疏的图
• 图可以用接邻表来表示，这种表示方式只保留了有边的节点的情况，而舍去了稀疏的大部分内容，节约了存储空间
• 一些图中的基本概念：
  • 强连通有向图：任意两个节点U和V之间存在U到V以及V到U的路径
  • 弱连通有向图：任意两个节点U和V之间存在U到V或者V到U的路径
  • 强连通分量：有向图中的强连通子图

传统的图机器学习方法

• 传统的机器学习通过手工提取特征来完成图机器学习中的node-level，link-level和graph-level的一些预测，目标是对于给定的图#card=math&code=G%3D%28V%2C%20E%29&id=TQGGN)学习出一个从V映射到R上面的函数

节点层面的机器学习任务

• 图机器学习在节点层面的主要任务是对节点进行分类和学习图的结构特征，主要有：
  • 节点的度数
  • 节点的中心(node centrality)
  • 聚类系数
  • graphlets

node centrality

节点中心node centrality是在在一个图中表示出不同节点的重要性，而不是简单的出入度数。一个节点v如果与一些很重要的节点相邻那么这个节点也很重要，一个节点的centrality可以这样计算：

%7Dcu%0A#card=math&code=c_v%3D%5Cfrac%7B1%7D%7B%5Clambda%7D%5Csum%7Bu%5Cin%20N%28v%29%7Dc_u%0A&id=bHIzO)

• 问题在于上面的这个表达式其实是一种循环定义，需要用另一种方法来表示
• 特征向量中心：我们可以用向量的相识来表示上面的centrality定义式：
  • 其中A是图G的邻接矩阵，如果两个点uv相邻，那么否则就是0
  • 我们发现这时候由每个点的centrality组成的向量C实际上就是矩阵A的特征向量，其中最大的特征向量总是为正并且唯一的，因此可以用A矩阵的最大特征值作为图G的centrality
• 中间性中心Betweenness Centrality
  • 该标准认为一个节点如果处于很多通往其他节点的最短路径上，那么这个节点就比较重要，因此定义：

• 该标准下重要程度的计算方式就是对于图中的任意两个和v不同的节点s，t，计算其最短路径中包含v的比例并进行求和
  • 邻近中心Closeness Centrality
• 该标准认为一个节点如果拥有比较小的到其他所有节点的最短路径长度，那么它就比较重要，用l表示图中两个节点的最短路径长，那么：

聚类系数

聚类系数可以衡量一个节点的邻居节点的连接情况，假设一个节点v有k个邻居，这些k个邻居之间有n条边，那么聚类系数可以写作：

%7D%0A#card=math&code=e_v%3D%5Cfrac%7Bn%7D%7BC_k%5E2%7D%3D%5Cfrac%7B2n%7D%7Bk%28k-1%29%7D%0A&id=u1uCo)

• 聚类系数某种意义上也可以理解为记录了每个节点与其邻近节点构成的三角形的个数，即对于一个节点v，如果它的两个邻居u和w之间有一条边，那么uvw就构成了一个三角形，而这个三角形被统计到了聚类系数中去

Graphlets

Graphlets是一种根连通的非同构子图，有如下几个衍生出的概念：

• Graphlet Degree Vector(GDV)：基于Graphlets的节点特征，记录了每个节点所能接触到的graphlets的个数，和度数以及聚类系数不同，度数衡量了一个节点能接触到的边的数量，而聚类系数衡量了一个节点能接触到的“三角形”的个数，而GDV记录了以一个节点v为root的所有的graphlet

• GDV提供了一个节点的局部网络拓扑结构的衡量方式

边层面

图机器学习在边层面的主要任务是基于已经存在的连接来预测新的连接，因此关键的问题在于如何设计和表示一对节点的特征，一般有两种边预测的场景：

• 随机缺失了若干条边，要求将图补全
• 随时间会变化的边关系：在时许数据的场景下节点和节点之间的边关系可能会随时间发生变化，这种情况叫做evaluation，一般来说可以用如下步骤来解决时序预测问题：
  • 对每一个节点对计算一个score C，即一个既定的标准
  • 根据这个标准来对节点对进行排序
  • 预测排序中的top-n作为新的边，并进行验证

基于距离的特征

• 用两个节点之间的最短路径距离来表示节点对的特征，但是这种方式没有考虑到邻近点的重合度

Local Neighborhood Overlap

用共同的邻近节点的个数作为一个节点对的特征，对于一个节点v，用#card=math&code=N%28v%29&id=D2CPl)表示所有邻近节点构成的集合，那么有这样几种标准：

• 共同邻居：

%5Ccap%20N(v)%7C%0A#card=math&code=%7CN%28u%29%5Ccap%20N%28v%29%7C%0A&id=a7Arq)

• Jaccard系数

%5Ccap%20N(v)%7C%7D%7B%7CN(u)%5Ccup%20N(v)%7C%7D%0A#card=math&code=%5Cfrac%7B%7CN%28u%29%5Ccap%20N%28v%29%7C%7D%7B%7CN%28u%29%5Ccup%20N%28v%29%7C%7D%0A&id=AD9Fn)

Global Neighborhood Overlap

局部的neighborhood overlap在两个节点没有共同邻居的时候始终为0，但这两个节点仍然有可能存在一定的关系，而Local Neighborhood Overlap这些关系的特征，因此就需要Global Neighborhood Overlap

• Katz index：记录两个节点之间所有的路径数，可以使用邻接矩阵来计算，假设临界矩阵为A，其中如果u和v相邻那么，这样一来就可以表示是否有连接uv的长度为K的路径，因此可以用下面的共识来计算这一特征量：

• 而Katz index矩阵可以用如下方式来计算：

%5E%7B-1%7D-I%0A#card=math&code=S%3D%5Csum_%7Bi%3D1%7D%5E%7B%5Cinfin%7D%5Cbeta%5EiA%5Ei%3D%28I-%5Cbeta%20A%29%5E%7B-1%7D-I%0A&id=xv2v9)

图层面的特征和图kernel

目标是提取整张图整体的特征，而传统机器学习中经常使用kernel来进行特征的提取，图也可以使用kernel来进行特征的提取，其核心是一个图特征向量#card=math&code=%5Cphi%28G%29&id=PmVgu)

BoW

图kerbel的关键想法是基于Bag-of-Word(BoW)BoW原本是指使用单词出现的次数来作为文档的特征，而将其扩展到图上就可以将节点作为“单词”，即可以计算图中各种不同度数的节点的数量，并将结果作为一个多维的向量输出，向量的每一个维度d的值代表了图中度数为d的节点总数

Graphlet特征

• 可以计算图中不同的graphlet的个数来表示图的特征，但是这里的graphlet和节点层面的不太一样，不需要完全连接，也没有根的概念

• 对于一个给定的图G，用一个graphlet表来定义graphlet计数向量 ，则：

_i%3D%5C%23(g_i%5Csubset%20G)%0A#card=math&code=%28f_G%29_i%3D%5C%23%28g_i%5Csubset%20G%29%0A&id=B1I21)

• graphlet kernel可以定义为：

%3DfG%5ETf%7BG’%7D%0A#card=math&code=K%28G%2CG%27%29%3DfG%5ETf%7BG%27%7D%0A&id=J3epG)

• 如果两张图的size不同会引起结果的失真，那么就可以进行正则化操作，令：

%3DhG%5ETh%7BG’%7D%0A#card=math&code=hG%3D%5Cfrac%7Bf_g%7D%7B%5Csum%20f_G%7D%5Crightarrow%20K%28G%2CG%27%29%3Dh_G%5ETh%7BG%27%7D%0A&id=aAZQj)

• 这种kernel的问题在于计算graphlet的个数的时间复杂度是非常高的，并且是NP-hard的