斯坦福CS224W

参考资料：

原课程：https://web.stanford.edu/class/cs224w/index.html 诸神佬的博客：https://blog.csdn.net/PolarisRisingWar/article/details/117287320 b站中文：https://www.bilibili.com/video/BV1RZ4y1c7Co?vd_source=1a36db16e3fec3ccbe040303ff015aab b站讲解：https://www.bilibili.com/video/BV1pR4y1S7GA?vd_source=1a36db16e3fec3ccbe040303ff015aab ## 1.图论基础见离散数学。 1. Heterogeneous Graph (异质图)的例子： - 社交网络图：一个人可以与多个人建立联系，每个人可能有不同的属性（如年龄、性别、职业等）。 - 生物信息学中的基因调控网络：一个基因可以调控多个其他基因的表达。

异质图和普通图的区别：
- 普通图的边表示节点之间的连接关系，而异质图中的边可以表示不同类型的关系，如合作、竞争等。
- 普通图中的节点通常具有相同类型的属性，而异质图中的节点可以具有不同类型的属性。
Bipartite Graph (二分图)的例子：
- 学生与课程的关系图：一个学生可以选择多个课程，一个课程可以被多个学生选择。
- 城市与道路的关系图：一个城市可以有多个道路，一个道路连接两个城市。
Directed Graph的例子：
- 交通流量图：每条边表示一条路，边的权重表示车辆的流量。
- 电子邮件传递过程：每个节点表示一个人或组织，边表示邮件从一个节点传递到另一个节点的过程。
设计本体图Ontology的方法：
- 确定领域范围和概念：首先明确本体涉及的领域和概念，例如生物学、计算机科学等。
- 定义实体和关系：根据领域知识，定义实体（如人、物、事件等）和关系（如“属于”、“发生在”等）。
- 设计本体结构和语义约束：确定实体之间的关系类型（一对一、一对多等），并添加适当的语义约束以确保一致性和完整性。
- 使用本体编辑器或工具进行建模：可以使用专业的本体编辑器（如OWL、RDF等）或在线工具来创建和维护本体图。
为什么要把图表示成矩阵？
- 矩阵是一种高效的数据结构，适用于表示稀疏图（即边的数量远小于顶点的数量的平方）。在稀疏图中，大部分元素为零，因此使用矩阵可以节省存储空间和计算资源。
从连通域的角度理解“六度空间”理论：
- “六度空间”理论指的是任何两个人之间最多只需要通过六个人就可以相互认识。这是因为在社交网络中，信息传播通常是通过朋友的朋友的朋友等间接途径进行的。当一个人想要认识另一个人时，他/她可以通过直接的朋友、朋友的朋友、朋友的朋友的朋友等途径将信息传递给目标对象。因此，最多需要经过六个中间人即可实现相互认识。
为什么很多真实场景的图都是稀疏的？
- 许多真实场景中的图形往往是由少量节点和边组成的，这就是所谓的稀疏图。这主要有以下原因：
  - 低度连接性：在许多情况下，节点之间的连接性较低，只有少数几条边存在。例如，社交媒体上的好友关系通常只涉及到一小部分用户。
  - 长路径限制：许多图形结构具有限制路径长度的要求，因为过长的路径可能导致信息传输效率低下或产生冗余信息。例如，生物信息学中的基因调控网络中，某些调控因子可能会抑制与其直接相连的其他调控因子的影响。 ## 2.传统图机器学习方法 ### a.前言传统的图机器学习即人工特征工程+机器学习。而后面的深度学习GNN可以端到端自动学习特征。

本章重点着眼于手工设计无向图三种数据层次上的结构特征，连接关系，做预测问题。 ### b.节点(node)层面的特征工程 #### 找到能够描述节点在网络中结构与位置的特征 · 节点度数 · 节点重要度 · 聚集系数 · 定义的子图的数量 #### 度数缺点在于将节点的所有邻居视为同等重要的 #### 节点重要度 node centrality考虑了节点的重要性 - 1eigenvector centrality：认为如果节点邻居重要，那么节点本身也重要因此节点 v的centrality是邻居centrality的加总。可用矩阵表示。 - 2betweenness centrality：认为如果一个节点处在很多节点对的最短路径上，那么这个节点是重要的。（衡量一个节点作为bridge或transit hub的能力。就对我而言直觉上感觉就像是新加坡的马六甲海峡啊，巴拿马运河啊，埃及的苏伊士运河啊，什么君士坦丁堡，上海，香港……之类的商业要冲的感觉）

意思就是如果一个链接图上，任意两个节点之间的通路，经过每个点的次数，次数最大的点其重要性最大。 - 3closeness centrality：认为如果一个节点距其他节点之间距离最短，那么认为这个节点是重要的 $ c_{v}= $ - 5clustering coefficient3：衡量节点邻居的连接程度描述节点的局部结构信息 #### graphlets有根连通异构子图就跟同分异构体一样。 #### 总结——节点特征 - 节点在图中的重要性：如度数，centrality - 节点附近的拓扑属性如度数，聚集系数，异构图 #### 讨论就我的理解，大致来说，传统节点特征只能识别出结构上的相似，不能识别出图上空间、距离上的相似 ### c.边(link)的特征工程 #### 通过已知连接，补全未知连接 #### 两种formulations - 1.静态客观图：蛋白质，分子 - 2.时间动态预测图：社交网络，论文引用 #### 基于相似性进行链接预测：计算两点间的相似性得分（如用共同邻居衡量相似性），然后将点对进行排序，得分最高的n组点对就是预测结果，与真实值作比 #### distance-based feature：两点间最短路径的长度这种方式的问题在于没有考虑两个点邻居的重合度the degree of neighborhood overlap，如B-H有2个共同邻居，B-E和A-B都只有1个共同邻居 #### local neighborhood overlap：捕获两节点的共同邻居数 cn为共同好友数目 jc为交并比 a-ai为共同好友是不是社牛(好友的好友多) common neighbors的问题在于度数高的点对就会有更高的结果，Jaccard’s coefficient是其归一化后的结果。 Adamic-Adar index在实践中表现得好。在社交网络上表现好的原因：有一堆度数低的共同好友比有一堆名人共同好友的得分更高。 #### 全图邻居 local neighborhood overlap的限制在于，如果两个点没有共同邻居，值就为0。但是这两个点未来仍有可能被连接起来。所以我们使用考虑全图的global neighborhood overlap来解决这一问题。 Katz index：计算点对之间所有长度路径的条数计算方式：邻接矩阵求幂。邻接矩阵的k次幂结果，每个元素就是对应点对之间长度为k的路径的条数（离散数学里学过） discount factor β 会给比较长的距离以比较小的权重。 ### d.全图的特征工程光用node不够的话，可以设置一个degree kernel，用bag-of-degrees来描述图特征 text - 1.Count the number of different graphlets in a graph 即数每种节点组合类型的异构图数目 graphlet count vector：每个元素是图中对应graphlet的数量 text alt text graphlet kernel就是直接点积两个图的graphlet count vector得到相似性。对于图尺寸相差较大的情况需进行归一化 graphlet kernel的限制：计算昂贵 - 2.Weisfeiler-Lehman Kernel：相比graphlet kernel代价较小，效率更高。用节点邻居结构迭代地来扩充节点信息实现算法：Weisfeiler-Lehman graph isomorphism test=color refinement text text text text 经过k次迭代 text 大佬补充：这个color refinement方法与GNN的相似性我认为有二，一在都聚集了节点邻居信息，GNN详情见我撰写的后续课程笔记（就后面好几节课都讲了GNN）；二在在Lecture 9中会讲的GIN。 ### e.Node Embeddings 随机游走的艺术-图嵌入表示学习 Node Embeddings即将节点映射为D纬向量 text #### 前提 - embedding的相似性可以反映原节点在网络中的相似性，比如定义有边连接的点对为相似的点，则这样的点的embedding应该离得更近即矩阵相乘结果更大 #### Node Embeddings: Encoder and Decoder - 节点嵌入：目标是将节点编码encode为embedding space中的向量embedding，使embedding的相似度（如点积2）近似于图中节点的相似度（需要被定义） - Encoder：将节点映射为embedding 定义一个衡量节点相似度的函数（如衡量在原网络中的节点相似度） Decoder DEC 将embedding对映射为相似度得分 d一般是64-1000维 text - Z每列是一个节点所对应的embedding向量。v是一个其他元素都为0，对应节点位置的元素为1的向量。通过矩阵乘法的方式得到结果。这种方式就是将每个节点直接映射为一个embedding向量，我们的学习任务就是直接优化这些embedding。缺点：参数多，很难scale up3到大型图上。优点：如果获得了Z，各节点就能很快得到embedding。有很多种方法：如DeepWalk，node2vec等 - Encoder + Decoder Framework Summary - 节点相似的不同定义本节课：随机游走random walk定义的节点相似度 #### Random Walk Approaches for Node Embeddings P(v∣z_u) 是从 u uu 开始随机游走能得到 v 的概率，衡量 u 和 v 的相似性，用节点embedding向量相似性算概率。用于计算预测概率的非线性函数：softmax会将一组数据归一化为和为1的形式，最大值的结果会几乎为1。sigmoid会将实数归一化到 (0,1) 上 - random walk embeddings - zu转至*zv ~= 点 u 和 v 在一次随机游走中同时出现（点 v 在以 u 为起点的随机游走中出现）的概率 - log-likulihood目标函数：对这个目标函数的理解是：对节点 u ，我们希望其表示向量对其random walk neighborhood N_R(u) 的节点是predictive的（可以预测到它们的出现） - 具体函数如下： text - 优化random walk embeddings就是找到embedding z z 使L最小化但是计算这个公式代价很大，因为需要内外加总2次所有节点，复杂度达O(|V|^2)： - 为了解决这个分母，我们使用negative sampling的方法：简单来说就是原本我们是用所有节点作为归一化的负样本，现在我们只抽出一部分节点作为负样本，通过公式近似减少计算 text

Embedding Entire Graphs

任务目标：嵌入子图或整个图G，得到表示向量z_G 可用于： - 分类有毒无毒分子也可以视为对节点的一个子集的嵌入 - 1：聚合（加总或求平均）节点的嵌入 - 2：创造一个假节点（virtual node），用这个节点嵌入来作为图嵌入 - anonymous walk embeddings 什么东西？？

3.PageRank

PageRank是一种衡量网络中节点重要性的指标，主要思想是如果一个节点被很多重要节点指向(in-link)，那么该节点也很重要。可以从flow model / 线性方程组、power iteration（矩阵视角）、web surfer随机游走三种角度来看PageRank。求解PageRank的方法：power iteration。在求解PageRank的过程中会遇到spider traps和dead ends的问题，可以通过random teleport解决。 M / G 是随机游走的概率转移矩阵。 ### intro pagerank的历史地位：搜索引擎、信息检索、图机器学习、图数据挖掘“必读论文；线性代数的优雅应用典范

理解PageRank的五个角度： - 迭代求解线性方程组 - 迭代左乘M矩阵 - 矩阵的特征向量 - 随机游走 - 马尔科夫链