个人笔记

1 计算图与邻域信息

关键问题：GNN 节点嵌入能否区分不同节点的局部邻域结构？

GNN 通过邻域定义的计算图生成节点嵌入：

• 节点 1 和节点 5，因其度数不同而具有不同的邻域结构信息
• 节点 1 和节点 2，具有相同的邻域结构信息；二者在图中是对称的
• 节点 1 和节点 4，其 2 跳邻居的信息存在差异（邻居的度不同）

由于 GNN 主要依赖节点特征，而不考虑节点 ID

因此 GNN 无法区分位置同构的节点（节点 1 和节点 2）

2 GNN 的模型表达能力

Read more

图训练的完整 Pipeline：

1 GNN 的预测

不同的任务级别需要不同的预测头（Prediction head）

1. 节点（node-level）级预测：直接使用 $d$ 维的节点嵌入 $h_v^{(L)}$ 进行预测

$${\hat{\mathit{y}}}_v={\mathrm{Head}}_{\mathrm{node}}({\mathbf{h}}_v^{(L)})={\mathbf{W}}^{(H)}{\mathbf{h}}_v^{(L)}$$

2. 边（edge-level）级预测：使用

Read more

1 单层图神经网络

图神经网络（GNN）的通用框架：

• 可以发现，GNN 层的输入为一组向量，输出为单个向量
• 所以单层 GNN 的核心过程在于邻域信息的转换（1）和聚合（2）
• 在转换和聚合邻域信息时，还要注意考虑节点本身的信息保留

所以单层 GNN 的计算过程可表示如下： $$ \begin{aligned} \mathbf{m}_u^{(l)}&=\mathrm{MSG}^{(l)}\left(\math

Read more

1 深度学习基础

损失函数、梯度下降法族、基础神经元、 卷积神经网络

2 图神经网络的难点

图数据的复杂性：

• 存在任意大小和复杂的拓扑结构（不存在网格那样的空间局部性）
• 没有固定的节点顺序或参考点；通常是动态的并且具有多模式特征

直接将邻接矩阵或节点特征输入到传统神经网络的问题：

• $O(|V|)$ 级参数量，难以适用节点数较多的网络
• 无法适用不同尺寸的图/网络，传统网络对节点顺序敏感

置换不变性 vs 置换等价性

• 如果 $f(T(x))=f(x)$，则函数 $f(x)$ 对

Read more

2006 年 12 月，国际会议 IEEE International Conference on Data Mining（ICDM）评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.

1. C4.5 分类决策树
2. K-means 聚类算法
3. 1_study/algorithm/分类回归算法/支持向量机 SVM
4. Apriori 关联规则算法
5. EM 期望最大化算法
6. PageRank 排序算法
7. Adaboost 树集成算法
8. KNN 最近邻算法
9. Naive

Read more

PageRank 是早期 Google 搜索的核心算法，决定了搜索结果中的网页展示顺序

PageRank 算法最初用于网页权重的计算，它将每个网作为一个节点，网页间的超链接作为边，而最终的网页 X 权重描述了以 X 为起点，通过超链接进行随机游走 $N$ 次后，再次返回网页 X 的概率。同时为了防止随机游走进入死循环，每次随机游走还有概率 $=\alpha$ 的情况随机跳转到任意网页，不同网页的随机跳转概率是相等的

PageRank 核心思想：

• 根据网站的外部链接和内部链接的数量和质量衡量网站的价值
• 如果重要性为 $PR(i)$ 的页面 $i$ 有 $l_i$ 个外链（出度），则每个

Read more

背景故事：啤酒与尿布

Aprior 算法的 3 个关键评价指标：

1. 支持度（Support）：商品 X 和商品 Y 同时在数据集中出现的概率

$$Support(X,Y)=P(XY)=\frac{number(XY)}{num(AllSamples)}$$ 2. 置信度（Confidence）：商品 Y 出现后，商品 X 出现的概率 $$Confidence(X\Leftarrow Y)=P(X|Y)=P(XY)/P(Y)$$ 3. 提升度（Lift）：商品 X 出现的情况中，商品 Y 也出现的概率 $$ Lift(X \Leftarrow Y) = P(X|Y)

Read more

“啤酒与尿布”，购物篮分析的经典案例

该故事据传来自20世纪90年代的美国沃尔玛超市的销售数据分析：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中

这种独特的销售现象引起了管理人员的注意，其背后是美国育婴家庭的分工习惯：母亲一般在家中照看婴儿，年轻的父亲前去超市购买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒，这样就会出现啤酒与尿布这两件看上去不相干的商品经常会出现在同一个购物篮的现象。

沃尔玛发现了这一独特的现象，并在卖场尝试将啤酒与尿布摆放在相同的区域；沃尔玛从上个世纪 90 年代尝试将艾格拉沃发明的商品关联关系的计算方法—— Apri

Read more

K 近邻算法（k-nearest neighbors, KNN）是一种很基本的机器学习方法

算法步骤：给定样本，寻找最近的 K 个样本进行（分类/回归）预测

KNN的 3 个核心要素：

• K 值的选择，较小时容易过拟合；较大时泛化性好，但训练误差大
• 距离度量方式，比如欧氏距离、曼哈顿距离（常见距离测度）
• 决策规则，分类问题常用投票法，回归问题常用平均法

KNN 的主要优点：

• 理论成熟，思想简单，既可以用来做（非线性）分类也可以用来做回归
• 训练时间复杂度比支持向量机之类的算法低，仅为 O (n)
• 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
• 对于类域的交叉或重叠较多

Read more

前置知识： 特征工程_图

依赖环境：networkx

数据和环境准备：

import networkx as nx

G = nx.karate_club_graph()
# 空手道俱乐部 34 名成员的社交网络

图的平均度

def average_degree(num_edges, num_nodes):
    avg_degree = 2*num_edges/num_nodes
    avg_degree = int(round(avg_degree))
    return avg_degree

num_edges 

Read more