作者文章归档：王半仙
关键问题：GNN 节点嵌入能否区分不同节点的局部邻域结构？
GNN 通过邻域定义的计算图生成节点嵌入：
由于 GNN 主要依赖节点特征，而不考虑节点 ID
因此 GNN 无法区分位置同构的节点（节点 1 和节点 2）
图训练的完整 Pipeline：
不同的任务级别需要不同的预测头（Prediction head）
$$ \widehat{\boldsymbol{y}}_v=\mathrm{Head}_{\mathrm{node}}(\mathbf{h}_v^{(L)})=\mathbf{W}^{(H)}\mathbf{h}_v^{(L)} $$
图神经网络（GNN）的通用框架：
所以单层 GNN 的计算过程可表示如下： $$ \begin{aligned} \mathbf{m}_u^{(l)}&=\mathrm{MSG}^{(l)}\left(\math
图数据的复杂性：
直接将邻接矩阵或节点特征输入到传统神经网络的问题：
置换不变性 vs 置换等价性
2006 年 12 月，国际会议 IEEE International Conference on Data Mining（ICDM）评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.
PageRank 是早期 Google 搜索的核心算法，决定了搜索结果中的网页展示顺序
PageRank 算法最初用于网页权重的计算，它将每个网作为一个节点，网页间的超链接作为边，而最终的网页 X 权重描述了以 X 为起点，通过超链接进行随机游走 $N$ 次后，再次返回网页 X 的概率。同时为了防止随机游走进入死循环，每次随机游走还有概率 $=\alpha$ 的情况随机跳转到任意网页，不同网页的随机跳转概率是相等的
PageRank 核心思想：
背景故事：啤酒与尿布
Aprior 算法的 3 个关键评价指标：
$$ Support(X,Y) = P(XY) = \frac{number(XY)}{num(All Samples)} $$ 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)
“啤酒与尿布”，购物篮分析的经典案例
该故事据传来自20世纪90年代的美国沃尔玛超市的销售数据分析：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中
这种独特的销售现象引起了管理人员的注意，其背后是美国育婴家庭的分工习惯：母亲一般在家中照看婴儿，年轻的父亲前去超市购买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒，这样就会出现啤酒与尿布这两件看上去不相干的商品经常会出现在同一个购物篮的现象。
沃尔玛发现了这一独特的现象，并在卖场尝试将啤酒与尿布摆放在相同的区域；沃尔玛从上个世纪 90 年代尝试将艾格拉沃发明的商品关联关系的计算方法—— Apri
K 近邻算法（k-nearest neighbors, KNN）是一种很基本的机器学习方法
算法步骤：给定样本，寻找最近的 K 个样本进行（分类/回归）预测
KNN的 3 个核心要素：
KNN 的主要优点：