1. 章节前言

1. 传统机器学习pipeline：设计并获取所有训练数据上节点/边/图的特征→训练机器学习模型→应用模型

图数据本身就会有特征，但是我们还想获得说明其在网络中的位置、其局部网络结构local network structure之类的特征（这些额外的特征描述了网络的拓扑结构，能使预测更加准确）

所以最终一共有两种特征：数据的structural feature，以及其本身的attributes and properities1

2. 本章重点着眼于手工设计无向图三种数据层次上的特征（其relational structure of the network），做预测问题
3. 图机器学习的目标：对一系列object做预测
4. design choice

• Features: d-dimensional vectors
• Objects: Nodes, edges, sets of nodes, entire graphs
• Objective function: What task are we aiming to solve?

2. Traditional Feature-based Methods: Node

1. 半监督学习任务如图所示案例，任务是预测灰点属于红点还是绿点。区分特征是度数（红点度数是1，绿点度数是2）

2. 特征抽取目标：找到能够描述节点在网络中结构与位置的特征

3. 度数node degree：缺点在于将节点的所有邻居视为同等重要的

5. clustering coefficient3：衡量节点邻居的连接程度

描述节点的局部结构信息

ego-network of a given node is simply a network that is induced by the node itself and its neighbors5. So it’s basically degree 1 neighborhood network around a given node.

这种三角形：How manys triples are connected

在社交网络之中会有很多这种三角形，因为可以想象你的朋友可能会经由你的介绍而认识，从而构建出一个这样的三角形/三元组。

这种三角形可以拓展到某些预定义的子图pre-specified subgraph6上，例如如下所示的

graphlet：

6. graphlets有根连通异构子图

1. Graphlet Degree Vector (GDV): Graphlet-base features for nodes
2. GDV与其他两种描述节点结构的特征的区别：
3. Degree counts #(edges) that a node touches
4. Clustering coefficient counts #(triangles) that a node touches.
5. GDV counts #(graphlets) that a node touches

Graphlet Degree Vector (GDV): A count vector of graphslets rooted at a given node.如图所示，对四种graphlet，v vv 的每一种graphlet的数量作为向量的一个元素。

注意：graphlet c的情况不存在，是因为像graphlet b那样中间那条线连上了。这是因为graphlet是induced subgraph5，所以那个边也存在，所以c情况不存在。

6. 考虑2-5个节点的graphlets，我们得到一个长度为73个坐标coordinate（就前图所示一共73种graphlet）的向量GDV，描述该点的局部拓扑结构topology of node’s neighborhood，可以捕获距离为4 hops的互联性interconnectivities。

相比节点度数或clustering coefficient，GDV能够描述两个节点之间更详细的节点局部拓扑结构相似性local topological similarity。

7. Node Level Feature: Summary

这些特征可以分为两类：

• Importance-based features: 捕获节点在图中的重要性

• Structure-based features: 捕获节点附近的拓扑属性

8. Discussion就我的理解，大致来说，传统节点特征只能识别出结构上的相似，不能识别出图上空间、距离上的相似

3. Traditional Feature-based Methods: Link

1. 预测任务是基于已知的边，预测新链接的出现。测试模型时，将每一对无链接的点对进行排序，取存在链接概率最高的K个点对，作为预测结果。

2. 特征在点对上
3. 有时你也可以直接将两个点的特征合并concatenate起来作为点对的特征，来训练模型。但这样做的缺点就在于失去了点之间关系的信息。
4. 链接预测任务的两种类型：随机缺失边；随时间演化边

图中的 ’ 念prime

第一种假设可以以蛋白质之间的交互作用举例，缺失的是研究者还没有发现的交互作用。（但这个假设其实有问题，因为研究者不是随机发现新链接的，新链接的发现会受到已发现链接的影响。在网络中有些部分被研究得更彻底，有些部分就几乎没有什么了解，不同部分的发现难度不同）

第二种假设可以以社交网络举例，随着时间流转，人们认识更多朋友。

5. 基于相似性进行链接预测：计算两点间的相似性得分（如用共同邻居衡量相似性），然后将点对进行排序，得分最高的n组点对就是预测结果，与真实值作比

6. distance-based feature：两点间最短路径的长度

这种方式的问题在于没有考虑两个点邻居的重合度the degree of neighborhood overlap，如B-H有2个共同邻居，B-E和A-B都只有1个共同邻居。

7. local neighborhood overlap：捕获节点的共同邻居数

common neighbors的问题在于度数高的点对就会有更高的结果，Jaccard’s coefficient是其归一化后的结果。

Adamic-Adar index在实践中表现得好。在社交网络上表现好的原因：有一堆度数低的共同好友比有一堆名人共同好友的得分更高。

8. global neighborhood overlap

local neighborhood overlap的限制在于，如果两个点没有共同邻居，值就为0。

但是这两个点未来仍有可能被连接起来。所以我们使用考虑全图的global neighborhood overlap来解决这一问题。

Katz index：计算点对之间所有长度路径的条数

计算方式：邻接矩阵求幂

• 邻接矩阵的k次幂结果，每个元素就是对应点对之间长度为k的路径的条数
• 证明：

• 从而得到Katz index的计算方式：discount factor β \betaβ 会给比较长的距离以比较小的权重，exponentially with their length.

closed-form闭式解，解析解8

解析解的推导方法我去查了，见尾注9

9. Summary

• Distance-based features: Uses the shortest path length between two nodes but does not capture how neighborhood overlaps.
• Local neighborhood overlap:

Captures how many neighboring nodes are shared by two nodes.

Becomes zero when no neighbor nodes are shared.

• Global neighborhood overlap:

1. Uses global graph structure to score two nodes.
2. Katz index counts #paths of all lengths between two nodes.

4. Traditional Feature-based Methods: Graph

1. 图级别特征构建目标：找到能够描述全图结构的特征
2. Background: Kernel Methods

就是，核这一部分其实我一直都没搞懂，以前看SVM啥的时候就没好好学都是直接跳的，所以核本来是什么我也不知道……

b/w=between

off-the-shelf现成的

半正定矩阵特征值非负的证明开我之前写的博文：从0开始的GNN导学课程笔记

3. Overview

4. graph kernel: key idea

bag-of-words相当于是把文档表示成一个向量，每个元素代表对应word出现的次数。

此处讲述的特征抽取方法也将是bag-of-something的形式，将图表示成一个向量，每个元素代表对应something出现的次数（这个something可以是node, degree, graphlet, color）

光用node不够的话，可以设置一个degree kernel，用bag-of-degrees来描述图特征

5. graphlet features

• Key idea: Count the number of different graphlets in a graph.
• 注意这里对graphlet的定义跟上文节点层面特征抽取里的graphlet不一样。区别在于：

1.Nodes in graphlets here do not need to be connected (allows for isolated nodes)

2.The graphlets here are not rooted.

• 对每一种节点数，可选的graphlet：

• graphlet count vector：每个元素是图中对应graphlet的数量

• graphlet kernel就是直接点积两个图的graphlet count vector得到相似性。对于图尺寸相差较大的情况需进行归一化

skew扭曲

h捕获了图中我们要的graphlet的frequency或proportion

• graphlet kernel的限制：计算昂贵（这一部分的知识对我来说超纲了，我就只知道有这么回事就完了，我来不及学为啥了）

6. Weisfeiler-Lehman Kernel：相比graphlet kernel代价较小，效率更高。

用节点邻居结构迭代地来扩充节点信息（vocabulary在此仅作引申义？）

• 实现算法：Weisfeiler-Lehman graph isomorphism test=color refinement

• color refinement示例

把邻居颜色聚集起来

对聚集后颜色取哈希值

把邻居颜色聚集起来

对聚集后颜色取哈希值

• 进行K次迭代后，用整个迭代过程中颜色出现的次数作为Weisfeiler-Lehman graph feature

第一个图的特征应该是算错了，最后3个元素应该是2 1 0

• 用上图的向量点积计算相似性，得到WL kernel

• WL kernel的优势在于计算成本低

w.r.t: with respect to

颜色个数最多是节点的个数：每一次就最多这么多个点上有颜色……

7. Summary

这个color refinement方法与GNN的相似性我认为有二，一在都聚集了节点邻居信息13，GNN详情见我撰写的后续课程笔记（就后面好几节课都讲了GNN）；二在在Lecture 9中会讲的GIN14。

5. 本章总结

• Traditional ML Pipeline

Hand-crafted feature + ML model

• Hand-crafted features for graph data

1. Node-level:

Node degree, centrality, clustering coefficient, graphlets

2. Link-level:

Distance-based feature

local/global neighborhood overlap

3. Graph-level:

Graphlet kernel, WL kernel

• 因为感觉一般attribute和property都翻译成特征，所以有点迷惑他们有什么区别，简单看了一下ResearchGate问题：What are the differences between attribute and properties ?

最高赞回答：区别微妙，attribute是对物体的附加属性，property是体现物体本身特征的属性。一般来说，是同义词。 ↩︎

• 谷歌了一下，发现这个定理挺难的，没看懂。

……数学太难为我了，我放弃了。 ↩︎

• 对聚集系数进行解释的其他参考资料：

聚集系数 - 百度百科

Clustering coefficient(集聚系数)

我还没有仔细学习具体定义。仅供参考。

• 参考资料：

① 知乎问题：很多地方的组合数记法为什么要用两个圆括号包起来而不是用原来的C下标上标？

② 知乎问题： 如何通俗的解释排列公式和组合公式的含义？

③ 百度知道问答：排列组合中A和C怎么算啊

• subgraph, induced subgraph等概念可参考cs224w课程第12章Frequent Subgraph Mining with GNNs。我以后也会写相应的笔记

• 对connected的定义可以参考我之前写的cs224w第一章笔记，里面有写：cs224w（图机器学习）2021冬季课程学习笔记1

对这部分的讲解参考了这篇博文：【图神经网络】——“斯坦福CS224W”课程笔记（三）

这篇博文做的是19版课程的笔记，主要讲的是motif和graphlet相关概念。这些概念在21版课程中会放到后面讲（还是在第12章的位置），后面我也会做到相应的笔记。

• 参考知乎问题：什么叫闭型（closed-form）？

• 

参考资料：

①Katz 指标（The Katz Index,KI）的讲解与详细推导

②刘建国, 任卓明, 郭强,等. 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 2013(17):9-18. 论文下载地址

③维基百科：Katz centrality 就是，这个Katz centrality就是Katz index的一个求和。所以如果需要的话也可以查看Katz centrality的相关资料。但我没看毕竟我不想看

④Katz, L. (1953). A new status index derived from sociometric analysis. Psychometrika, 18(1), 39–43. 论文下载地址 据我观察这个应该是原始论文了。但我没看毕竟我不想看

⑤Junker B H, Schreiber F. Analysis of biological networks[M]. John Wiley & Sons, 2011. 谷歌学术提供的书籍下载地址 据我观察，这本书里应该有讲为什么 β \betaβ 需小于邻接矩阵A最大特征值的倒数……但这TM是一本书（358页！）我怎么可能看，我安详地死了。

⑥Martinez V , Berzal F , Cubero J C . A Survey of Link Prediction in Complex Networks[J]. Acm Computing Surveys, 2017, 49(4):69.1-69.33. 论文下载地址 一篇链接预测的综述。但我没看毕竟我不想看 ↩︎

• 说来无用，但是我觉得这个表示形式很像图数据在谱域上的卷积。

……但是这就像洛伦兹力的形式很像万有引力定律的公式，感觉我看到了也没什么用。 ↩︎

• 

• color refinement的结束条件是设置迭代次数还是达到收敛我有点没搞懂，但是这玩意真的能收敛到稳定状态吗？看起来不行啊！ ↩︎

• 关于这个GNN空间方法为什么是聚集邻居信息啊，我主要看到过两种说法，一种是它反正就是这么干的，这么干本来就很符合直觉嘛（马克思说过，人是社会性的动物，节点受其邻居影响是很直觉的嘛，就像KNN一样）；另一种是其做法发源自其他方法，一说是来源于谱方法（但是具体怎么来的我没搞懂，反正就是好像经过一番推导可以从谱方法简化到空间方法），一说是受belief propagation启发，一说是受CNN启发。

真是太复杂了，我搞不懂。 ↩︎

可参考我撰写的博文：cs224w（图机器学习）2021冬季课程学习笔记11 Theory of Graph Neural Networks ↩︎