deepwalk

DeepWalk 的最终目标是——

把图中的每个节点，用一个低维向量表示（embedding）出来，使得结构相似的节点在向量空间中也接近。

也就是说，如果两个节点在图上经常“一起出现”（相连、同社群等），那它们的 embedding 也应该相似。

主要思想

将图结构转化为“序列语料”：
- 在图上做 随机游走（random walks），生成顶点序列，类似于自然语言中的“句子”。
将随机游走得到的序列输入 Skip-Gram 模型，学习节点的低维嵌入表示。
学到的嵌入能捕捉到 邻居相似性、社区结构，可用于分类、聚类、链路预测等任务。

输入 & 输出

输入：图结构 $G=(V,E)$，随机游走参数（步长 $t$，次数 $\gamma$，窗口大小 $w$），嵌入维度 $d$。
输出：节点嵌入矩阵 $\Phi \in \mathbb{R}^{|V|\times d}$。

关键公式与目标

随机游走生成“句子”：
- 从某个顶点 $v_i$ 出发，采样一个长度为 $t$ 的随机游走序列：
  $$ W_{v_i} = (v_i, v_{i+1}, \dots, v_{i+t}) $$
生成的序列 $W_{v_i}$ 就是一句“话”，用来训练 Skip-Gram 模型。在这些序列中，如果两个节点经常在相邻位置出现，就表示它们关系密切。
```
["A", "B", "C", "D"]
```
Skip-Gram 目标函数：
- 现在我们用 Word2Vec 的思想：对于一句话 ["A", "B", "C", "D"]，假设窗口大小 $w = 1$，也就是每个节点只看它的邻居。那么训练样本是这样的：
  
  中心节点它要预测的邻居
  
  A B
  
  B A, C
  
  C B, D
  
  D C
  
  模型要学的是：
  
  “给我节点 B，我要能预测出 A 和 C。” “给我节点 C，我要能预测出 B 和 D。”
- 于是就有这个公式，给定中心节点 $v_i$，最大化其上下文窗口内邻居节点的条件概率：
  $$ \max_{\Phi} \sum_{i=1}^{|V|} \sum_{u \in \mathcal{N}_w(v_i)} \log Pr(u \mid \Phi(v_i)) $$
- 其中 $\mathcal{N}_w(v_i)$ 表示在随机游走序列中，窗口大小 $w$ 内的上下文节点。
- 我希望模型能学到这样一种 embedding：中心节点 $v_i$ 能够高概率预测出它周围的邻居 $u$。
优化形式（负对数似然）：

就是把上面的最大化目标，改写成一个最小化损失函数。

最大化“好事”（邻居出现的概率）= 最小化“坏事”（邻居预测错误的概率） $$ \min_{\Phi} - \log Pr\big( {v_{i-w},\dots,v_{i+w}} \mid \Phi(v_i) \big) $$
概率建模（Hierarchical Softmax 或 Negative Sampling）：
$$ Pr(u \mid \Phi(v_i)) = \frac{\exp\big( \Phi(u) \cdot \Phi(v_i) \big)}{\sum_{v \in V} \exp\big( \Phi(v) \cdot \Phi(v_i) \big)} $$ 这相当于用 Softmax 把所有节点的相似度转成概率分布。其中：
- 分子：中心节点和邻居节点的相似度（点积越大越相似）；
- 分母：所有节点的相似度和（用来归一化成概率）。

中心节点	它要预测的邻居
A	B
B	A, C
C	B, D
D	C

如果 $u$ 是 $v_i$ 的邻居，那么 $\Phi(u)$ 与 $\Phi(v_i)$ 的点积就应更大。

例子

想象你是个“社交分析师”：

你观察到小明每天都和小红、小刚一起出现；
而小明几乎从不和小李在一起；
那你自然会说：小明和小红、小刚的关系更近。

DeepWalk 就是通过“随机游走 + 预测邻居”这个机制，自动学出“谁跟谁关系近”的数值表示。

训练逻辑

1）加载 10+1 张图

A_list = [A100, A101, ..., A110]

我们取前 10 张作为输入，最后一张作为真实标签。

2）对每一个时间步的图做 DeepWalk

for t in range(100, 110):
    emb_t = DeepWalk(A_t)

每张图 $A_t$ 都独立训练一个 节点 embedding（比如 400×64）。 400是节点数，64是嵌入维数
embedding 就是每个节点在这一时刻的“语义坐标”。
训练目标是：让在图里常相邻的节点在 embedding 空间也靠得近。

可以理解成：

DeepWalk 把图结构变成“节点的向量表示”。

3）拼接成时间序列特征（10步）

对每对节点 (i, j)，你把过去10个时间步的 embedding 拿出来，计算每步的 Hadamard积（元素乘）：

feats = [emb100[i]*emb100[j], emb101[i]*emb101[j], ..., emb109[i]*emb109[j]]
X_ij = concatenate(feats)

每个节点对 (i, j) → 一个 10×64 = 640 维的特征；
这 640 维包含了它俩“过去10步的相似度变化轨迹”。

白话理解：

这个特征就像是“节点对关系的时间切片”。

如果两人（节点）经常靠得近 → 向量相似；如果逐渐靠近 → 特征会呈现变化趋势。

4）第11步图作为真实答案（标签）

A_target = A110
y_ij = 1 if 节点i和j在第110步相连 else 0

每个节点对 (i, j) 的标签就是第11步的真相；
如果在第11步有边 → 正样本；
没边 → 负样本。

5）平衡样本（1:1）

因为稀疏图中没连边的太多：

原来是 9,237 个正样本 vs 70,563 个负样本；
现在我们随机保留同样数量的负样本；
所以训练时正负样本平衡：9,237 : 9,237。

✅ 这样模型不会再“全猜没边”。

6）训练 MLP 来做预测

MLP(X) → 输出每个节点对在第110步连边的概率

输入：每个节点对的 640 维特征；
输出：一个 [0,1] 概率；
Loss：二分类交叉熵（BCELoss）；
优化器：Adam。

🧠 白话解释：

MLP 在学“什么样的历史关系轨迹会导致下一步产生连接”。

7）用真实 A110 对照预测结果

模型预测完后：

它给每对节点一个连边概率；
我们用阈值 0.5 分成「有边/无边」；
然后与真实的 $A_{110}$ 比较，得到：

指标	含义
AUC=0.8279	模型能区分哪些节点会连边、哪些不会（非常好）
ACC=0.7223	有约 72% 的节点对被正确分类（相对平衡后的准确率）

（1）静态图版本

你只有一张图，比如社交网络的当前关系：

DeepWalk 学出 embedding；
然后用 MLP 或逻辑回归，预测那些“目前没边但 embedding 很接近”的节点对；
这些就是「潜在朋友」→ 即未来可能建立连接的边。

📘 所以静态链路预测其实是：

用当前结构的 embedding 相似度，预测将来是否可能连边。

（2）动态图版本

你有多帧图，比如第100~109步（连续的10个时间片）：

每一步都用 DeepWalk 得到 embedding；
然后把每个节点对的“10帧特征”拼起来；
喂给 MLP 预测第110步是否连边。

📘 动态版本其实是：

把「节点关系的历史轨迹」作为输入，预测下一个时间步的关系变化。

DeepWalk 的本质：

是一个 图嵌入算法（Graph Embedding Method），输入图结构，输出节点的向量表示（embedding）。

也就是说：

每次运行 DeepWalk，相当于重新学习节点的 embedding；
embedding 本身就是最终结果，不需要“恢复模型状态”去推理；
它不具备像神经网络那样“泛化到新数据”的功能。

所以：

✅ DeepWalk 的输出 = checkpoint ✅ DeepWalk 的 embedding = 可直接保存 / 复用的结果 ❌ 不需要保存训练中间的模型权重