CS224W

前言 这节课主要介绍传统的图机器学习方法。传统方法主要分为两步，第一步人工设计特征，第二步使用各种机器学习方法进行预测。因此，特征工程在传统图机器学习方法中有很重要的地位。本节课主要介绍图上的特征工程方法，分别介绍针对节点（node-level）、边（link-level）和图（graph-level）的特征工程方法。 针对节点的特征工程方法 节点水平的特征主要有四类，下面分别介绍。 节点的度（node degree） 节点的中心性（node centrality） 节点的集聚系数（clustering coefficient） 非同构子图（graphlets） 节点的度 节点的度，这个最好理解了，即该节点的所连边的数目，或者说该节点的直接邻居数目。如果是有向图，还分为出度和入度。 节点的度的不足是，没有考虑到不同邻居的重要性不同，只要有一个邻居，度就加1，即认为所有邻居的重要性是相同的。 节点的中心性 节点的中心性这个特征考虑了节点的重要性，有多个中心性指标，如下： 特征向量中心性（Engienvector centrality） 中介中心性（Betweenness centrality） 接近中心性（Closeness centrality） 特征向量中心性的定义是：节点v的重要性=v的邻居的重要性的和，除以λ进行归一化。 根据定义可知，特征向量中心性是递归定义的，写成矩阵形式就是Ac=λc，特征向量c的每个维度就是每个顶点的特征向量中心性的值。 忘记了怎么求特征值和特征向量的同学可以复习一下：https://blog.csdn.net/Junerror/article/details/80222540。 算出最大特征值λ_max对应的特征向量c_max之后，节点v的特征向量中心性就是向量c_max的第v个分量。具体看维基百科：https://zh.wikipedia.org/zh-cn/%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F%E4%B8%AD%E5%BF%83%E6%80%A7。 如果说特征向量中心性有点难以理解和计算的话，接下来介绍的中介中心性和接近中心性就很好理解了。 中介中心性，顾名思义，就是节点作为中介（枢纽）的重要性。计算方法是，所有节点对(s,t)的最短路径穿过节点v的比例。(s,t)的最短路径可以认为是(s,t)之间的交通要道，如果这条路径穿过节点v的话，说明v在交通要道上，所以v是很重要的中介枢纽。具体计算方法见下图，即v在所有(s,t)的最短路径中出现的比例。 接近中心性也很好理解，就是节点v与图中其他节点的接近程度。计算方法是：v到其他节点的最短路径之和的倒数。如果一个节点越中心，则它到其他节点的最短路径越短，则接近中心性越大。比如下图的D就比A更中心，所以D的接近中心性更大。 节点的集聚系数 集聚系数是个很有意思的指标，它描述的不是节点本身，而是节点的邻居的集聚程度。其计算公式如下图所示，分子是v的邻居形成的边的数目，分母是v的邻居理论上能形成最多的边的数目，分母用来归一化的。 集聚系数=1表示v的邻居都两两认识，=0表示v的邻居两两都不认识。集聚系数越大，表示邻居聚集程度越高，越有可能是一个紧密的团体。 非同构子图 非同构子图的英文定义是：rooted connected non-isomorphic subgraphs，很准确啊，有根的连通的非同构子图。比如下图中3个节点的graphlets有3个，G1中目标节点（根节点）在1和2形成的子图是不一样的（不同构），而在G2中3个点的位置是等价的，所以G2只有1个graphlet，加起来就是3个graphelts。从2个节点到5个节点，能形成的graphlets总数是73个。 Graphlet Degree Vector（GDV）是基于graphlets的特征，它计算以目标节点v为根，能形成的不同graphlets的数目向量，相当于描述了v周围不同子结构的子图个数。如下子图3所示，红色节点v的2-3个节点的GDV向量是[2,1,0,2]。如果统计节点v周围的2~5个节点（包含v自己）形成的graphlets的数目，则会得到一个维度为73的GDV向量，相当于节点v的一个特征向量。这个73维度的特征向量是节点v周围四跳（4-hop）的结构信息。 小结一下节点的特征大概可以分成两类，一类是基于重要性的特征，例如节点的度、节点的中心性；另一类是基于结构的特征，例如节点的度、集聚系数、非同构子图个数向量。基于重要性的特征可用于预测网络中的重要节点，例如社交网络中的名人节点；基于结构的特征可用于预测网络中不同节点的不同功能，例如蛋白质相互作用网络中不同蛋白质的功能，因为不同的局部子结构往往蕴含了不同的功能。 针对边的特征工程方法 针对边<A,B>的特征工程方法，固然可以把节点A和B的节点特征concat起来作为边<A,B>的特征，但是丢失了很多边特有的信息，效果不一定好。专门针对边设计的特征工程方法有三个，下面分别介绍： 基于距离的特征（Distance-based feature） 局部邻居重叠比例（Local neighborhood overlap） 全局邻居重叠比例（Global neighborhood overlap） 基于距离的特征 两点之间的最短路径长度，这个最好理解了，可以用Dijkstra算法和Floyd算法求解。然而最短路径无法捕捉两个节点的共同邻居数目，比如下图中BH和BE的最短路径都是2，但BH有两个共同邻居CD，而BE只有一个共同邻居D，如果只用最短路径这个特征，则无法区分BH和BE这两对节点。 局部邻居重叠比例 局部邻居重叠比例衡量两个节点的邻居重叠程度，比如简单的Common neighbors直接计算两个节点的共同邻居数目；Jaccard’s coefficient用邻居交集数目除以并集数目做了归一化。 Adamic-Adar index的计算方法是所有共同邻居的度的对数分之一加和。它的直观含义是，如果共同邻居的度越小，则说明两个节点的关系越紧密。比如下图中，A和B的共同邻居是C，C的度是4，说明C除了连接了A和B，还连了另外2个节点。如果C的度越大，则说明A和B占C的邻居的重要性越低；反之，如果C只连了A和B，则说明A和B通过C这个枢纽连接的关系很重要。举个简单的例子，比如两个人都喜欢一个很小众的电影，则他们的兴趣可能会很接近，但如果都喜欢一个大众电影，则他们的关系可能没那么强烈。 局部邻居重叠比例的问题是：只考虑了一跳直接相连的邻居，没有考虑间接相连的邻居（潜在关系），后面介绍的全局邻居重叠比例可以解决这个问题。 全局邻居重叠比例 Katz index统计的是任意两个节点之间任意长度的路径的个数。在计算Katz index的时候，需要计算两个节点uv之间长度为l的路径个数。计算方法是邻接矩阵的l次方。 ...

前言 最近的工作涉及到图神经网络，打算系统学习下这方面的内容。首先搜集了相关的教材，发现市面上的教材大多数是罗列论文的形式，不太适合初学者入门。后来找到了斯坦福CS224W这门公开课，打算入坑，一是之前学习过斯坦福CS224N，感觉不错；二是CS224W这门课的老师是GraphSAGE的作者Jure Leskovec，有大佬背书错不了。 CS224W主页：http://web.stanford.edu/class/cs224w/ Winter 2021版主页：http://snap.stanford.edu/class/cs224w-2020/ Winter 2021版视频：https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn，Jure Leskovec是斯洛文尼亚人，英语不是很标准，建议打开YouTube的字幕。 背景介绍 图（Graph）是描述实体（entity）和关系（relation）的一种通用语言形式，它由节点（vertex或node）和连接节点的边组成，很多数据类型都可以用图的形式来描述。 图1 图及其应用实例 目前常见的图有两类： 第一类是网络（network），也称为自然图，例如： 社交网络，全球70亿人形成一个大网络 通信网络，例如通过电话、邮件、交易等形成的网络 生物医药网络，例如基因、蛋白质之间形成的网络 大脑中的成千上万的神经元形成的网络 第二类是通过抽象表示形成的图，例如 人工组织形成的信息网络、知识网络 软件中的代码调用形成的网络 分子网络、场景图、基于粒子的物理模拟等 现有的机器学习工具箱主要针对图像、文本和语音，对图的机器学习处理工具相对较少，因为图是不规则的数据，难以处理。对图的处理主要有以下难点： 图不是欧几里得数据结构，没有固定的大小和拓扑结构 图上的节点没有固定的顺序，也没有参考点，是去中心化的 图会随着时间动态变化，并且图中常常会融合多模态信息 本课程的两个重点： Deep learning in graphs，即图上的深度学习算法 Representation learning，即图表示学习，将图中的节点嵌入到一个低维稠密向量中，使得网络中相似节点的embedding距离接近 本课程的主要内容包括： 传统方法：Graphlets，Graph Kernels 节点嵌入方法：DeepWalk，Node2Vec 图神经网络：GCN，GraphSAGE，GAT，Theory of GNNs 知识图谱：TransE，BetaE 图上的深度生成网络 图在生物医药，科学和工业上的应用 图机器学习应用 图可以有很多应用场景，这些应用可以分为节点水平的（nodel level）、边水平的（edge level）、子图水平的（subgraph level）和图水平的（graph level）。下面逐一举例： Node-level：节点分类（node classification），例如预测节点的属性。节点回归？例如AlphaFolde使用GNN预测每个氨基酸在三维空间中的位置坐标，从而预测蛋白质的结构。感觉和GNN关系不太大吧？具体得看论文了。 Edge-level：链接预测（link prediction），预测两个节点之间是否存在边。例如在推荐系统中，预测user是否会购买item等。另外还可以用于预测药物的副作用，例如任意两种药组合吃，是否会产生副作用，产生哪种副作用，都是针对边的任务。 Sub-graph level：地图导航，预测预期到达时间（ETA）。DeepMind和Google Maps合作的一个工作，很有意思：https://www.deepmind.com/blog/traffic-prediction-with-advanced-graph-neural-networks。简单来说，把每条路分段（supersegment），每段表示成一个点，一条路的相邻段（点）连边，交叉路口的段（点）连边。通过GNN的消息传递，一条路的拥堵信息，可以传递到相邻的路。很自然的想法，也符合实际情况，比如在这条路拥堵了，司机可能就会走相邻的路，进而会影响相邻的路的ETA。问题是，GNN对图很敏感，不同地区、地段的路网图差异很大，有的路网小，有的路网大，因此不同training run之间的方差很大。一开始想到用lr decay来缓解。后来使用MetaGradients让模型自动调整学习率。使用多个loss，多目标学习防止过拟合。 Graph-level：例如新药发现：节点是原子、边是各种键，生成一个graph，就是一种新的复合物。物理模拟：动态图，节点表示粒子，有属性比如速度、动量，然后下一个时刻有新的位置，不断进化变化，类似RNN，可以模拟出粒子的动态变化过程。 图2 图机器学习应用场景 图的表示方法 构成图的基本要素包括顶点集合N和边集合E，可以用\(G(N,E)\)来表示一张图。 根据边是否有方向，可以将图分为无向图和有向图，无向图即图中的边没有方向，有向图即图中的边有方向。 对于无向图G，每个顶点的度就是该顶点所连边的数目，由于一条边连接了两个顶点，贡献了2个度，所以所有顶点的平均度数=2E/N。 对于有向图，顶点的度可分为入度和出度，如图3所示，顶点C的入度为2，出度为1。所有顶点的平均入度=平均出度=E/N。如果某个顶点的入度为0，则称该顶点为源点，例如顶点G；如果某个顶点的出度为0，则称该顶点为槽点（sink），就像水槽一样，只进不出；如果某个顶点的入度和出度都为0，则称该顶点为孤立点。 图3 图的表示方法和顶点的度 ...