第 101 题：Graph Embedding的随机游走，DeepWalk与Node2Vec的偏置参数？
题目
Graph Embedding的随机游走，DeepWalk与Node2Vec的偏置参数？
完整讲解
一、Graph Embedding 与随机游走
图嵌入将节点映射为低维向量，使图上「相近」的节点向量接近。随机游走从某节点出发，按边随机跳转得到节点序列，把序列当作「句子」、节点当作「词」，用 Skip-gram 等语言模型学习嵌入，从而把图结构转化为共现关系。
二、DeepWalk 的偏置参数
DeepWalk 采用均匀随机游走：从当前节点 $u$ 出发，下一跳以等概率选邻居，即 $P(v \mid u) = 1/\text{deg}(u)$。无额外偏置参数，实现简单，适合无权图或边权无差别时的结构相似性（同质性与短路径）。
三、Node2Vec 的偏置参数 $p$、$q$
Node2Vec 引入二阶偏置，用两个参数控制游走形态：
- 返回参数 $p$：从 $u$ 经 $t$ 走到 $v$ 后，下一步回到 $t$ 的概率正比于 $1/p$。$p$ 小则易回到上一跳（局部游走），$p$ 大则不易回（更发散）。
- 进出参数 $q$：下一步走到 $t$ 的其他邻居（与 $v$ 不相邻）的概率正比于 $1/q$。$q$ 小则倾向「往外走」（BFS 式，多跳邻居），$q$ 大则倾向「在 $v$ 附近」（DFS 式，局部邻域）。
形式上，从 $v$ 到 $x$ 的未归一化转移权重为 $\alpha_{pq}(t,x)$：若 $x=t$ 为 $1/p$，若 $x$ 与 $t$ 相邻为 $1$，若 $x$ 为 $t$ 的其它邻居为 $1/q$。通过调 $p,q$ 在同质性（相邻节点相似）与结构等价性（结构角色相似）间权衡。
四、工程要点
- DeepWalk 无超参、易实现；Node2Vec 需调 $p,q$，通常 $p,q \in [0.25, 4]$，$p$ 小 $q$ 大偏 BFS，$p$ 大 $q$ 小偏 DFS。
- 游走长度与每节点游走次数影响共现覆盖与训练规模，需在效果与耗时间折中。
面试要点
- 能说明随机游走 + Skip-gram 的图嵌入思路，以及 DeepWalk 的均匀游走（无偏置）。
- 能写出 Node2Vec 的 $p$（回退）、$q$（BFS/DFS）含义及对游走形态的影响。
- 能说清 $p$ 小易回退、$q$ 小偏 BFS、$q$ 大偏 DFS，以及同质性 vs 结构等价性的取舍。
记忆要点
- DeepWalk：均匀随机游走，无偏置；Node2Vec：$p$ 控制回退、$q$ 控制 BFS/DFS。
- $p$ 小→易回上一跳（局部）；$q$ 小→往外走（BFS），$q$ 大→邻域内（DFS）。
- 同质性用较小 $q$；结构角色相似用较大 $q$；$p,q$ 常取 [0.25, 4]。