06 — 随机游走特征 (DeepWalk / Node2Vec) 第一性原理
目标读者: 懂一点 ML、但不完全熟悉图推荐系统的同学。本文回答: 随机游走在图上到底做了什么、DeepWalk 的核心思想、Node2Vec 比 DeepWalk 多出来的 p/q 是什么、为什么游走 embedding 是 LightGCN 之外的互补信号、为什么本项目要用 7 个游走配置块、ensemble size 曲线怎么解释、游走特征与显式图/meta-path 特征的区别, 以及它为什么能提升泛化。 权威数字来源:
code/randomwalk_systematic_ablation.py+code/generate_randomwalk_ensemble_submission.py源码 +validation_runs/dynamic_seed202/randomwalk_systematic/下缓存产物, 与fact_sheet§2.3 / §2.5 对齐。
1. 随机游走在图上做什么: 一句话与一幅图
一句话: 随机游走 (random walk) 就是"在图上瞎逛"——从某个节点出发, 每一步随机跳到一个相邻节点, 走出一条节点序列; 把这张图上无数条这样的序列当作"句子", 喂给自然语言里的 Word2Vec, 就能给每个节点学出一个 embedding。
为什么这能产生 embedding? 因为 Word2Vec 的语言模型假设是"上下文相似的词, 语义相似"。我们把"节点"当成"词"、"游走序列"当成"句子", 那么它的潜台词就变成: 在游走里经常一起出现的节点, embedding 应该靠近。而在图上"经常一起出现"恰恰意味着"图距离近、邻域结构相似"——于是节点向量就编码了全局网络接近度, 这正是链路预测(本项目 = author-paper 推荐)所需要的信号。
伪代码层面的游走生成 (对应 code/randomwalk_systematic_ablation.py:139-157, DeepWalk 路径):
deepwalk_walks(G, walk_length, num_walks, seed):
rng = np.random.default_rng(seed)
walks = []
for r in range(num_walks): # 每个节点起 num_walks 条游走
order = shuffle(G.nodes, rng)
for start in order:
walk = [start]; cur = start
for step in range(walk_length - 1):
cur = uniform_choice(neighbors(cur)) # 均匀采样 = 无偏
walk.append(cur)
walks.append(walk)
return walks # 一堆"节点句子"
关键: 这里的 uniform_choice 是无差别地从邻居里均匀抽一个, 等价于 Node2Vec 里 $p=q=1$。这一点是 DeepWalk 与 Node2Vec 的分水岭, 第 3 节展开。
1.1 一个具体的"无直接边却频繁接近"的例子
这是理解游走特征价值的核心直觉。设:
- 作者 $a$ 读过论文 $p_1$;
- 论文 $p_1$ 被论文 $p_2$ 引用 ($p_1 \to p_2$);
- 另一位作者 $b$ 也读过 $p_2$;
- 现在要判断 $a$ 是否会读 $p_2$。
在显式图里, $a$ 和 $p_2$ 之间没有任何直接边。于是:
- LightGCN 的逐层传播在层数浅时, $a$ 的表示里几乎不含 $p_2$ 的成分;
- 显式 meta-path 特征(A-P-P、A-A-P 这类精确路径枚举)也得人为指定路径模式才数得到 $p_2$, 容易漏掉更长、更绕的通路。
但随机游走会反复走 $a \to p_1 \to p_2$ 这样的折线, 甚至 $a \to p_1 \to b \to p_2$ 这种经过合著者 $b$ 的二跳三跳通路。走多了之后, $a$ 的"句子"里 $p_2$(以及和 $p_2$ 邻域结构相似的论文)频繁与 $a$ 共现, Word2Vec 就会把 $\mathbf{e}a$ 与 $\mathbf{e}{p_2}$ 拉近。于是即便没有直接边, 它们的 embedding 相似度升高, 给链路预测一个正向信号。这就是"游走捕捉多跳、隐式、全局接近度"的本质——它不要求你事先指定路径模式, 而是把所有路径按概率加权地揉进 embedding。
2. DeepWalk 的核心思想: 图 → 语料 → Word2Vec
DeepWalk (Perozzi et al., 2014) 的三步法:
| 步骤 | 做什么 | 本项目对应 |
|---|---|---|
| 1. 截断随机游走 | 每个节点起 $N$ 条长 $L$ 的无偏游走, 拼成"语料" | deepwalk_walks, num_walks=10, walk_length=40 或 80 |
| 2. SkipGram | 用滑动窗口(半径 $w$)对每个中心节点预测上下文节点, 学 embedding | Word2Vec(sg=1, window=10, min_count=0, negative=5, epochs=3) (code/randomwalk_systematic_ablation.py:166-176) |
| 3. 取向量 | 每个节点得到 $d$ 维向量 | dim=128 或 256 |
为什么是 SkipGram (sg=1) 而不是 CBOW? SkipGram 是"用中心词预测周围词", 适合稀疏图——本项目二部图密度仅 $1.29\times10^{-3}$、约 56% 作者度=1, 极稀疏。SkipGram 对低频/孤立节点更友好。min_count=0 保证所有节点都被训练(包括度=1 的叶子作者), 不丢弃长尾; negative=5 是标准负采样数。
DeepWalk = 无偏随机游走 + SkipGram。它的 embedding 编码的是"节点在无向无权采样下被一起访问的概率", 即一种对称的、全局的接近度。
3. Node2Vec 比 DeepWalk 多什么: p 与 q 两个旋钮
DeepWalk 的"均匀抽邻居"把所有方向一视同仁。Node2Vec (Grover & Leskovec, 2016) 引入两个参数, 让游走有偏好地走:
| 参数 | 含义 | 大/小的效果 |
|---|---|---|
| $p$ (return parameter, 返回参数) | 刚刚离开节点 $t$ 来到 $w$, 现在要不要回头走到 $t$ | $p$ 大 → 抑制回头(鼓励往外探索); $p$ 小 → 爱走回头路 |
| $q$ (in-out parameter, 出入参数) | 下一步走"离 $t$ 近的节点"(往回走, 类 BFS) 还是"离 $t$ 远的节点"(往外走, 类 DFS) | $q$ 大 → 偏 BFS(局部、结构等价); $q$ 小 → 偏 DFS(远距离、社区同质) |
直觉: **BFS 偏好捕捉"结构等价"(structural equivalence)**——比如两个作者在各自社区里都是"枢纽", 即便相距很远, BFS 游走会让它们 embedding 相似; **DFS 偏好捕捉"同质性/社区归属"(homophily)**——同一社区/同一研究方向的节点走得近。
- DeepWalk = Node2Vec 在 $p=q=1$ 的特例: 无偏, 既不偏 BFS 也不偏 DFS。
- 本项目最终只保留了一个 Node2Vec 配置:
n2v_p2_q1($p=2.0, q=1.0$), 见code/randomwalk_systematic_ablation.py:114。它的 $p=2$ 抑制回访、$q=1$ 中性, 属于"往外探一点、结构略偏 BFS"的中间态, 与 DeepWalk 的无偏采样子空间不同 → 嵌入互补(见第 4 节)。
备注:
small_configs(L92-94) 还定义了n2v_bfs($p=1,q=2$)、n2v_dfs($p=1,q=0.5$)、n2v_bal($p=1,q=1$) 三个 Node2Vec, 但models/目录里没有对应的.model文件,ensemble_7也不用它们。即: 这些 BFS/DFS 极端配置在实验中被弃用了, 最终入模的只有 $p=2,q=1$ 这一份 Node2Vec。这是"定义了但没用"的典型坑。
4. 为什么游走 embedding 是 LightGCN 之外的互补信号
这是本特征族能进 stacking 的根本理由。逐点对比:
| 维度 | LightGCN (Stage-1 主分数) | DeepWalk/Node2Vec (本特征族) |
|---|---|---|
| 表示来源 | 端到端可学习的图卷积, 通过 BPR 损失反传 (train_val_lgcn_ensemble.py) |
不可训练的固定游走 + SkipGram 伪词嵌入 |
| 优化目标 | 排序损失(BPR), 直接为"区分正负 author-paper 对"优化 | 词共现似然, 与推荐任务无关, 是无监督的 |
| 邻域聚合 | 1/(L+1) 加权邻居均值, 层数浅、近邻主导 | 游走隐式做了多跳、按路径概率加权的聚合, 能到 3-5 跳 |
| 偏差 | 学出来的表示对训练正边拟合强, 易过拟合已知交互 | 无监督, 不直接看标签, 编码的是纯图结构, 偏差不同 |
| 对长尾 | 度=1 的叶子作者表示主要由其邻居决定, 表达力受限 | min_count=0 + 游走会把叶子节点也放进语料, 至少能学到它的一阶邻域 |
互补性来自哪里? 二者的归纳偏置(inductive bias)正交: LightGCN 像"任务特化的强拟合器", 游走 embedding 像"任务无关的结构先验"。一个 stacker 同时拿到这两种信号, 就能: (1) 用 LightGCN 的强排序能力兜底大多数简单对; (2) 用游走的多跳隐式通路(第 1.1 节例子)挽救那些"无直接边但图上相近"的对——这些正是 LightGCN 在浅层下会判错的边界样本。stacking 的 LightGBM meta-learner 自动学会"在对的情况下用哪种信号"。
5. 为什么是 7 个 RW blocks: 多样性即互补
单块游走 embedding 已经是有效特征, 但一块的方差有限(只覆盖一种游走策略/图结构)。本项目用 7 个配置块 来制造结构多样性, 让每块捕捉不同视角:
5.1 七个最终配置块(与 models/ 实存模型 + README 复现命令一致)
| 序 | version_name | 方法 | 图类型 | dim | walk_len | num_walks | window | p/q | seed | 定义行 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | dw_base_d128_l40_w10_win10 |
DeepWalk | full | 128 | 40 | 10 | 10 | — | 202 | L89 |
| 2 | dw_long_d128_l80_w10_win10 |
DeepWalk | full | 128 | 80 | 10 | 10 | — | 202 | L90 |
| 3 | dw_highdim_d256_l40_w10_win10 |
DeepWalk | full | 256 | 40 | 10 | 10 | — | 202 | L91 |
| 4 | dw_d256_l80_w10_win10 |
DeepWalk | full | 256 | 80 | 10 | 10 | — | 202 | L112 (extra) |
| 5 | dw_seed3407_d128_l40_w10_win10 |
DeepWalk | full | 128 | 40 | 10 | 10 | — | 3407 | L110 |
| 6 | dw_graph_ap_pp |
DeepWalk | ap_pp(A-P + P-P) | 128 | 40 | 10 | 10 | — | 202 | L102 |
| 7 | n2v_p2_q1_d128_l40_w10_win10 |
Node2Vec | full | 128 | 40 | 10 | 10 | 2.0/1.0 | 202 | L114 |
共 6 DeepWalk + 1 Node2Vec。多样性的三个旋钮:
- walk_length (40 vs 80): 长游走看到更远的结构(更 DFS、更全局), 短游走更局部。
- dim (128 vs 256): 高维编码更多结构细节但更易过拟合, 低维更平滑。
- seed (202 vs 3407): 不同随机种子 → 不同游走采样 → embedding 的随机性扰动, 多块平均能降噪(类似 bagging)。
- graph_type (full vs ap_pp):
full图同时含 A-P / A-A / P-P 三类边且 A-P 边权 3.0(build_graphL127-135, 合著/引用边权 1.0);ap_pp只保留 A-P 和 P-P(去掉了合著 A-A), 看的是"作者-论文-引用"纯学术链, 视角不同。 - method (DeepWalk vs Node2Vec): 无偏 vs 偏 BFS, 邻域结构不同。
边权设计很关键: A-P 边权 3.0、A-A/P-P 边权 1.0, 让游走优先沿作者-论文主任务边走, 同时保留合著/引用作为"捷径"。这是把任务先验注入无监督游走的小技巧。
5.2 每块产出 11 维 pair 特征
游走得到的是节点向量, 但我们的预测单元是 (author, paper) 对, 不是单个节点。所以要把两个节点向量融合成 pair 特征。pair_feature_block (code/randomwalk_systematic_ablation.py:216-270) 产出 11 列:
| 类别 | 特征 | 含义 |
|---|---|---|
| 直接交互 (5) | dot, cos, hadamard_mean, absdiff_mean, l2_distance |
两向量的点积、余弦、逐元素积均值、绝对差均值、欧氏距离 |
| 全局排序 (2) | dot_global_rank, cos_global_rank |
dot/cos 在全部验证对里的 rank01 归一 |
| 组内排序 (4) | dot_author_rank, cos_author_rank, dot_author_pct, cos_author_pct |
按 author groupby, 在该作者的所有候选 paper 内排序/百分位 |
为什么除直接交互还要组内排序? 因为一个高产作者的候选 paper 都打高分, 绝对 dot 没区分度, 但组内排名能区分"对这位作者而言, 这篇 paper 排第几"。这与全局 rank 互补——这就是本项目反复用的"score → features"套路(score_to_features: raw / zscore / rank / author_rank 四件套)在游走域的展开。
5.3 第 8 个"块": 一致性聚合 (11 维)
七块各 11 维共 77 维, 再加一个跨块一致性聚合 11 维 (generate_randomwalk_ensemble_submission.py:50-69 aggregate):
| 来源 | 聚合特征 |
|---|---|
| 7 块的 cos 列 | mean / std / max / min (4 列) |
| 7 块的 dot 列 | mean / std (2 列) |
7 块的 cos_author_pct 列 |
mean / std / max / min (4 列) |
7 块的 cos_author_pct ≥ 0.5 |
agree = 投票一致的块数 (1 列) |
agree 是亮点: 它数"有几块都认为这个对排在作者候选的前半", 是一种多模型投票/集成置信度。多块都同意 → 高置信正例。这把 ensemble 的"一致性"显式做成了特征喂给 LightGBM。
维度核对: 7×11 + 11 = 88 维 RW 特征族。最终 259 维特征里, RW 块占 77, aggregate 占 11(
fact_sheet§2.5)。
6. RW ensemble size 曲线怎么解释: 多样性的边际收益
把"单块 → 5 块 → 7 块"的验证 F1 画出来, 就是 ensemble size 图(论文常用素材):
| 配置 | 维度 | 验证 F1 (1:1 OOF) | Δ vs 上一档 |
|---|---|---|---|
最优单块 dw_d256_l80 |
84+11=95 | 0.963371 | — |
5 块 ensemble (dw_base/long/highdim/graph_ap_pp/n2v_p2_q1) |
84+5×11+11=150 | 0.963932 | +0.000561 |
7 块 ensemble (+dw_d256_l80+dw_seed3407) |
84+7×11+11=172 | 0.964921 | +0.000989 |
(来源: ensemble_5_ablation.csv、ensemble_7_ablation.csv, n_features 列与 F1 列; 单块 F1 由对应 _oof.npy + best_f1 重算。)
怎么解释这条曲线?
- 从 1 → 5: +0.000561, 边际明显。因为 5 块覆盖了不同 walk_length、不同图结构、不同方法(DeepWalk + Node2Vec), 嵌入子空间正交性强, 加进来立刻提供 LightGCN 看不到的新视角。
- 从 5 → 7: +0.000989, 边际更大。这里加的是
dw_d256_l80(256 维 + 80 长游走, 最强单块)和dw_seed3407(纯种子扰动)。前者补"高维+长游走"视角, 后者补"同结构不同采样"的去噪视角。两块都是与前 5 块差异最大的配置, 故增益反超第 2-5 块。 - 总链 +0.001550。注意: 这与某些 figures 标题写的 "+0.00182" 不严格吻合(据 CSV 重算 best-single→5→7 仅 +0.00155; 若以
dw_base=0.962734 为起点则 +0.00219)。fact_sheet不一致台账 #21 已裁决: 以 CSV 重算 +0.00155 为准, figures 数字偏高需更正。
一般规律: 多样性 ensemble 的增益不随块数单调递增, 而取决于"新加入块与已有块的差异度"。这就是为什么最终不是盲目堆满 16 个 RWConfig, 而是精选 7 个相互差异最大的配置。
7. RW 特征 vs 显式图 / meta-path 特征: 互补的两种"图结构"信号
二者都从图结构出发, 但哲学相反:
显式图 / meta-path (stack_rank_calibration.py) |
随机游走 (本特征族) | |
|---|---|---|
| 路径表示 | 枚举指定路径模式(A-P-A、A-A-P、A-P-P), 精确计数 | 采样所有路径, 按概率加权揉进 embedding |
| 可解释性 | 高(每列对应明确语义, 如"共读论文数") | 低(向量维度无明确语义) |
| 覆盖 | 只覆盖人为指定的几跳模式, 长/绕路径易漏 | 隐式覆盖任意长度路径 |
| 计算 | Python set 交/并集(stack_rank_calibration.py L120-142), 无稀疏矩阵 |
Word2Vec 训练 + 向量运算 |
| 失败模式 | 漏掉未指定的有用 meta-path | 维度高、有训练随机性 |
它们互补: 显式特征给出"确定性、可解释"的强信号(如共读论文数=3), 游走特征补上"模糊、多跳、全局"的软信号。LightGBM 同时用两类, 互为校验。
8. 为什么 RW 特征能提升泛化
回到 stacking 的目标: 对 ~205 万测试对输出稳健的 0/1。RW 特征提升泛化的三条机理:
- 任务无关先验, 抗过拟合。游走 embedding 不看推荐标签, 是纯结构无监督表示。把它作为手工特征喂给 meta-learner, 等于注入一个与 LightGCN 训练目标无关的结构先验, 降低 stacker 对 LightGCN 过拟合风险的依赖。
- 多块 + 一致性聚合 = 内置 bagging。7 块不同配置(种子、长度、维度、图、方法)本质是"同一结构问题的 7 个噪声视角", 它们的
agree/mean/std聚合降噪并量化不确定性——多块一致的对更可能真为正。这把集成思想做进了特征。 - 挽救长尾与无直接边对。第 1.1 节例子: 长尾作者(度=1)在 LightGCN 里表示弱, 但游走的
min_count=0保证它有向量, 且多跳游走能让它通过合著/引用链获得有意义的接近度。这部分样本正是 baseline 最容易错的, 游走特征提供了额外、正交的判据。
证据链(验证 F1, seed=202 1:1 OOF): rich content + BPR 基线 0.95990 → 加 DeepWalk/Node2Vec(旧 stacker)≈0.9621 → 7 块系统 ensemble 0.964921 → 再叠加 rich content 成 rich_rw7 stacker 0.964947 → 最终 + 高阶引用传播达 0.966874(公开 LB 0.96626)。游走族贡献了约 +0.005 的验证 F1, 是从中游(0.9599)迈向顶尖(0.9669)的关键一档。
数值归属提醒:
0.964921(ensemble_7_ablation.csv, 纯 7 块 RW ensemble) 与0.964947(rich_rw7, 叠加 rich content 的另一 stacker,final_report.mdL125) 不是同一个模型, 引用时需区分 stacker 层级(fact_sheet#22)。
9. 关键代码与缓存位置速查
| 内容 | 位置 |
|---|---|
16 个 RWConfig 定义(最终只用 7 个) |
code/randomwalk_systematic_ablation.py:87-115 |
RWConfig dataclass |
code/randomwalk_systematic_ablation.py:73-84 |
build_graph(按 graph_type 加边, A-P 权 3.0) |
code/randomwalk_systematic_ablation.py:118-136 |
deepwalk_walks(无偏游走) |
code/randomwalk_systematic_ablation.py:139-157 |
train_model(DeepWalk=Word2Vec sg=1/neg5/ep3; Node2Vec=batch_words=4096) |
code/randomwalk_systematic_ablation.py:160-191 |
embedding_arrays(avec 6611×d, pvec 79937×d; pp_only_author_mean 回退) |
code/randomwalk_systematic_ablation.py:194-213 |
pair_feature_block(11 维 + npz 缓存) |
code/randomwalk_systematic_ablation.py:216-270 |
build_base_features(84 维 X_base) |
code/randomwalk_systematic_ablation.py:273-300 |
aggregate(11 维一致性聚合) |
code/generate_randomwalk_ensemble_submission.py:50-69 |
make_subs(rank-cutoff + test_known_mask 强制 1) |
code/generate_randomwalk_ensemble_submission.py:25-47 |
| 7 个 Word2Vec 模型 | validation_runs/dynamic_seed202/randomwalk_systematic/models/*.model |
pair 特征缓存(键: version_npairs_sumaid_sumpid) |
validation_runs/dynamic_seed202/randomwalk_systematic/pair_features/*.npz |
| ensemble 5/7 验证 CSV | validation_runs/dynamic_seed202/randomwalk_systematic/ensemble_{5,7}_ablation.csv |
注意:
small_ablation_table.csv/graph_ablation_table.csv实测各仅 2 行且含绝对路径遗留(/data/lzc/...), 已被部分覆盖/截断, 不能作为完整单块 F1 来源; 单块 F1 以对应_oof.npy+best_f1重算为准(fact_sheet#23)。
可迁移到论文中的写法
以下为可直接进 TeX 的正式表述(中文论文, 术语保留英文)。
方法段落(随机游走特征):
为补充 LightGCN 端到端协同过滤表示在多跳隐式通路与长尾节点上的不足, 我们在异构图上额外训练了 7 个 DeepWalk/Node2Vec 随机游走 embedding 作为手工特征。具体地, 对每个配置, 我们在融合图(author-paper 边权 3.0, 合著与引用边权 1.0)上生成截断随机游走序列, 并以 SkipGram(
sg=1,min_count=0,negative=5,epochs=3)训练节点向量。其中 6 个为 DeepWalk(等价 Node2Vec $p=q=1$), 覆盖不同的嵌入维度 $d\in{128,256}$、游走长度 $L\in{40,80}$、随机种子与图结构(full / ap_pp); 1 个为 Node2Vec($p=2.0, q=1.0$)以引入与无偏游走正交的结构等价偏置。对每个候选 (author, paper) 对, 我们由双方节点向量构造 11 维 pair 特征, 包括点积、余弦相似度、Hadamard 积均值、绝对差均值、欧氏距离, 以及全局与作者组内的相似度排序特征。此外, 我们将 7 个配置的相似度与排序统计量跨块聚合为 11 维一致性特征(含均值/标准差/极值及多块投票一致计数agree), 显式编码集成置信度。
动机段落(为何互补):
与 LightGCN 通过 BPR 排序损失反传、直接为推荐任务优化的可学习表示不同, 随机游走 embedding 是与任务标签无关的无监督结构先验。其归纳偏置与 LightGCN 正交: 它通过概率加权的多跳游走隐式覆盖任意长度路径, 无需人为指定 meta-path, 从而能捕获那些"无直接边但图上相近"的候选对。两者共同作为 LightGBM 二级 stacker 的输入, 使 meta-learner 能在不同样本上自适应地选择更可信的信号源。
实验段落(ensemble size):
我们考察了随机游走集成规模对验证 F1 的影响。最优单块(
dw_d256_l80, $d{=}256, L{=}80$)取得 F1 = 0.9634; 加入覆盖不同游走长度、图结构与方法(Node2Vec)的 4 块后, 5 块 ensemble 提升至 0.9639(+0.0006); 进一步加入高维长游走块与种子扰动块后, 7 块 ensemble 达到 0.9649(较最优单块累计 +0.0016)。增益随新加入配置与已有配置的差异度增大, 而非单纯随块数递增, 表明配置多样性而非数量是收益的主要来源。
消融表(可直接做表格):
| 模型 | 特征维度 | 验证 F1 |
|---|---|---|
| 最优单块 RW | 95 | 0.9634 |
| 5 块 RW ensemble | 150 | 0.9639 |
| 7 块 RW ensemble | 172 | 0.9649 |
引用注: 引用 7 块 ensemble 时需注明 F1=0.9649 来自
ensemble_7_ablation.csv(纯 RW ensemble); 报告中出现的 0.9649 属同一量级但属叠加 rich content 的 rich_rw7 stacker, 二者层级不同, 勿混用。