1. 课程建议先修知识点

1. 机器学习1
2. 算法和图论
3. 概率论与数理统计

2. Why Graphs

1. 图机器学习中的常用工具：NetworkX, PyTorch Geometric, DeepSNAP, GraphGym, SNAP.PY

2. 选择图的原因：图是用于描述并分析有关联/互动的实体的一种普适语言。它不将实体视为一系列孤立的点，而认为其互相之间有关系。它是一种很好的描述领域知识的方式。

3. 网络与图的分类

• networks / natural graphs：自然表示为图

1.Social networks: Society is a collection of 7+ billion individuals

2.Communication and transactions: Electronic devices, phone calls, financial transactions

3.Biomedicine: Interactions between genes/proteins regulate life（大概是基因或蛋白质之间互动从而调节生理活动的过程）

4.Brain connections: Our thoughts are hidden in the connections between billions of neurons

• graphs：作为一种表示方法

1. Information/knowledge are organized and linked
2. Software can be represented as a graph
3. Similarity networks: Connect similar data points
4. Relational structures: Molecules, Scene graphs, 3D shapes, Particle-based physics simulations

• 有时network和graph之间的差别是模糊的

 4.复杂领域会有丰富的关系结构，可以被表示为关系图relational graph，通过显式地建模关系，可以获得更好的表现

 5.但是现代深度学习工具常用于建模简单的序列sequence（如文本、语音等具有线性结构的数据）和grid（图片具有平移不变性，可以被表示为fixed size grids或fixed size standards）

这些传统工具很难用于图的建模，其难点在于网络的复杂：

①Arbitrary size and complex topological structure (i.e., no spatial locality2 like grids)

②没有基准点，没有节点固定的顺序。没有那种上下左右的方向

③经常出现动态的图，而且会有多模态的特征

 6.本课程中就要讲述如何将神经网络模型适用范围拓展到图上。图深度学习也是当前的新前沿领域。

 7.有监督机器学习全流程图：

在传统机器学习流程中，我们需要对原始数据进行特征工程feature engineering（比如手动提取特征等），但是现在我们使用表示学习representation learning的方式来自动学习到数据的特征，直接应用于下流预测任务。

 8.图的表示学习：大致来说就是将原始的节点（或链接、或图）表示为向量（嵌入embedding），图中相似的节点会被embed得靠近（指同一实体，在节点空间上相似，在向量空间上就也应当相似）

 9.cs224w本课程将聚焦图的机器学习和表示学习多个领域，课程大纲如下：

1. Traditional methods: Graphlets, Graph Kernels
2. Methods for node embeddings: DeepWalk, Node2Vec
3. Graph Neural Networks: GCN, GraphSAGE, GAT, Theory of GNNs
4. Knowledge graphs and reasoning: TransE, BetaE
5. Deep generative models for graphs
6. Applications to Biomedicine, Science, Industry

3. Applications of Graph ML

1. 图机器学习任务分成四类

• 节点级别 node level
• 边级别 edge level
• 社区 / 子图级别 community(subgraph) level
• 图级别，包括预测任务 graph-level prediction 和 图生成任务 graph generation

2. 各类型的典型任务

• Node classification: Predict a property of a node

Example: Categorize online users / items

• Link prediction: Predict whether there are missing links between two nodes

Example: Knowledge graph completion

• Graph classification: Categorize different graphs

Example: Molecule property prediction

• Clustering: Detect if nodes form a community

Example: Social circle detection

• Other tasks:

1. Graph generation: Drug discovery
2. Graph evolution: Physical simulation

3. node-level的例子：解决蛋白质折叠问题——AlphaFold3

大致来说就是蛋白质由一系列氨基酸（氨基酸链chains of amino acids或amino acid residues）结合而成，这些氨基酸之间的交互使其形成不同的折叠方式，组成三维蛋白质结构（这个组合方式很复杂，但是一系列氨基酸交互之后形成的结构就是唯一的，所以理论上可以预测出最终结果）。学习任务就是输入一系列氨基酸，预测蛋白质的3D结构。

AlphaFold将一个被折叠的蛋白质视作spatial graph，residue视作节点，在相近的residue之间建立边，形成图结构，搭建深度学习模型，预测节点在空间中的位置（也就是蛋白质的三维结构）。

4. edge-level的例子

• 推荐系统——PinSage4

推荐系统的任务是向用户推荐物品

PinSage：基于图的推荐系统

在网站Pinterest上给用户推荐相关图片。

节点是图片和用户，组成如左下角所示的bipartite图（这个概念将在本章后文讲解）。图中的d是嵌入向量之间的距离，即任务目标是使相似节点嵌入之间的距离比不相似节点嵌入之间的距离更小。

2. 在同时吃2种药的情况下预测药的副作用

背景：很多人需要同时吃多种药来治疗多种病症。

任务：输入一对药物，预测其有害副作用。

Biomedical Graph Link Prediction5

（预测概率最高的组合药物副作用。其中有一部分已经有论文证明存在）

5. subgraph-level的例子：Traffic Prediction6

Google Map预测一段路程的长度、耗时等：将路段建模成图，在每个子图上建立预测模型。

6. graph-level的例子

• 药物发现——用图神经网络的图分类任务来从一系列备选图（分子被表示为图，节点是原子，边是化学键）中预测最有可能是抗生素的分子7

2. Graph Generation —— Molecule Generation / Optimization8

3. Graph Evolution —— Physics Simulation（粒子间的相互作用）

将整个物质表示为图（proximity graph），用GNN来预测粒子的下一步活动（组成一个新位置、新图）

4. Choice of Graph Representation

1. 图的组成成分

• 节点（N或V）
• 链接 / 边（E）
• 网络 / 图（G）

2. 图是一种解决关系问题时的通用语言，各种情况下的统一数学表示。将问题抽象成图，可以用同一种机器学习算法解决所有问题。

3. 但为问题选择合适的表示方法是个很难的任务。

如图中举例，用论文间的引用作为关系就比用论文题目含有同一单词作为关系，表达能力会好很多。

4. 建图时需要考虑以什么作为节点，以什么作为边

对某一领域或问题选择合适的网络表示方法会决定我们能不能成功使用网络：

• 有些情况下只有唯一的明确做法
• 有些情况下可以选择很多种做法
• The way you assign links will determine the nature of the question you can study

5. 以下介绍一些design choice

• 有向图VS无向图

2. 度数degree：每个点连接了多少边

参考了一下评论，感觉有向图跟无向图要作区分的话，更方便的还是看B点：在无向图中其度数就是2，在有向图中其度数就是3，所以在平均度数的计算上会有所差别。

3. Bipartite Graph

类似地，还有multipartite的情况

4. Folded/Projected Bipartite Graphs

如图所示，就是将一个bipartite图的两个节点子集分别投影

projection图上两个节点之间有连接：这两个节点在folded/projected bipartite graphs上至少有一个共同邻居

5. Representing Graphs

• 邻接矩阵Adjacency Matrix：每一行/列代表一个节点，如果节点之间有边就是1，没有就是0

无向图的邻接矩阵天然对称

2. Edge list

这种方式常用于深度学习框架中，因为可以将图直接表示成一个二维矩阵。这种表示方法的问题在于很难进行图的操作和分析，就算只是计算图中点的度数都会很难

3. Adjacency list

对图的分析和操作更方便

6. 节点和边的属性，可选项：

• Weight (e.g., frequency of communication)
• Ranking (best friend, second best friend…)
• Type (friend, relative, co-worker)
• Sign: Friend vs. Foe, Trust vs. Distrust
• Properties depending on the structure of the rest of the graph: Number of common friends

7. Weighted / Unweighted

8. Self-edges (self-loops) / Multigraph

这个multigraph有时也可被视作是weighted graph，就是说将多边的地方视作一条边的权重（在邻接矩阵上可看出效果是一样的）。但有时也可能就是想要分别处理每一条边，这些边上可能有不同的property和attribute

9.Connectivity

• 无向图的Connectivity

1. connected：任意两个节点都有路径相通
2. disconnected：由2至多个connected components构成

最大的子连接图：giant component

isolated node

这种图的邻接矩阵可以写成block-diagonal的形式，数字只在connected components之中出现

• 有向图的Connectivity

1. strongly connected directed graph: has a path from each node to every other node and vice versa (e.g., A-B path and B-A path)
2. weakly connected directed graph: is connected if we disregard the edge directions

3. strongly connected components

5. 本章总结

• Machine learning with Graphs

Applications and use cases

• Different types of tasks:

Node level

Edge level

Graph level

• Choice of a graph representation:

Directed, undirected, bipartite, weighted, adjacency matrix

机器学习可以看李宏毅老师的课程入门。我之前看的是2017版的，2021年时看了李老师最新版深度学习课程并撰写了笔记，可以参考：李宏毅2021春季机器学习课程视频笔记集合 ↩︎

spatial locality空间局部性：当程序访问某存储器地址后，很可能马上访问其邻近地址的特性。（空间局部性_百度百科）

这个概念我有点没搞懂放在这里是什么意思……

参考资料：局部性原理浅析——良好代码的基本素质 - Geek_Ling - 博客园 ↩︎

课程中提供的参考资料：

DeepMind博文：AlphaFold: Using AI for scientific discovery10

DeepMind博文：AlphaFold: a solution to a 50-year-old grand challenge in biology11

SingularityHub文章：DeepMind’s AlphaFold Is Close to Solving One of Biology’s Greatest Challenges12 ↩︎

Ying et al., Graph Convolutional Neural Networks for Web-Scale Recommender Systems, KDD 2018

论文地址

是一个全网级别的大型推荐系统，使用random walk和图卷积神经网络，结合图结构和节点特征来产生节点嵌入 ↩︎

Zitnik et al., Modeling Polypharmacy Side Effects with Graph Convolutional Networks, Bioinformatics 2018

论文地址

提出模型Decagon，建立了一个由蛋白质-蛋白质交互、蛋白质-药物交互、药物-药物交互（即对应成对药物的副作用，每一种副作用都是一种边的类型）组成的多模态图。文章提出了一种用于多模态网络多关系预测的图卷积神经网络模型 ↩︎

参考资料：

DeepMind文章：Traffic prediction with advanced Graph Neural Networks

Google Map用机器学习结合当前交通情况及历史交通情况来预测未来交通情况。

为了在全球范围解决这个任务，用GNN结合关系学习偏好来建模真实世界道路网络的连接结构，以实施时空推理。

模型没咋看懂。直接上图吧：

论文链接：A Deep Learning Approach to Antibiotic Discovery

由于抗药性细菌大量出现，所以产生了对抗生素发现的更多需求。本文建立了一种深度学习模型来找抗生素。 ↩︎

论文链接：You et al., Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation, NeurIPS 2018

任务：基于某些给定条件（满足物理定律，如化学价等），生成优化某些目标（某些需要的特性，如是药的概率、人造可得性）的图结构（分子）。

本文提出了一个Graph Convolutional Policy Network (GCPN)，一个通过强化学习完成上述任务的图卷积网络。训练过程遵守特定领域规则，以特定领域的reward来做优化。

论文链接：Sanchez-Gonzalez et al., Learning to simulate complex physics with graph networks, ICML 2020 ↩︎

这一文章讲的是AlphaFold的早期版本。

阅读笔记：DNA提供一系列氨基酸来生成蛋白质，但是不控制蛋白质的形状。试图暴力迭代所有结构的耗时会长到不可接受，但是蛋白质折叠的自发过程仅需几毫秒就能完成。预测这些氨基酸链会折叠成什么样的复杂蛋白质结构被称为“蛋白质折叠问题protein folding problem”。

蛋白质结构预测的意义在于，其形状可能会影响其功能。如果能知道蛋白质的形状，就能猜测它在细胞中的作用，从而设计对应的药物。

文中描述了一种我没看懂的结合DL的预测蛋白质折叠问题的算法。

参考资料：

论文地址：Improved protein structure prediction using potentials from deep learning

Whiley Online Library论文地址：Protein structure prediction using multiple deep neural networks in the 13th Critical Assessment of Protein Structure Prediction (CASP13)

这篇相当于是前一篇文章的进阶版，提出了课程中所讲述的最新版本、效果最好的AlphaFold。

阅读笔记：

Christian Anfinsen于1972年就提出，蛋白质的氨基酸链可以完全决定其结构。此后五十年研究者们就一直致力于解决这一问题。

CASP竞赛提供的评估指标是GDT（Global Distance Test），这一指标简单来讲可以被认为是amino acid residues (beads in the protein chain)预测值与真实值空间距离小于某一误差的百分比例。超过90%可以认为是解决了这一问题，AlphaFold2成功达到这一指标。

下图是比较成功的预测的示例图：

模型是一个端到端的attention-based neural network system，来理解这个图结构，在其建立的隐式图上进行推理。它使用了evolutionarily related sequences, multiple sequence alignment (MSA), and a representation of amino acid residue pairs来改进图。

原文图片配文：An overview of the main neural network model architecture. The model operates over evolutionarily related protein sequences as well as amino acid residue pairs, iteratively passing information between both representations to generate a structure. ↩︎

类似于新闻稿。

解释了蛋白质结构对药物发现领域的意义。原文：Nearly all of our drugs are designed to dock onto a protein, like keys to a lock. ↩︎