RWR：带重启的随机游走【图算法】

yinda_peng

RWR(Random Walk with Restart)带重启的随机游走是一种在图上面衡量节点相似性或节点与特定种子节点关联度的经典算法，在随机游走RW上增加了一个Rerstart模块。


Random Walk:以 1-r 概率从当前节点移动到一个随机邻居节点。
Restart:以 r 概率回到开始时的那个种子节点（也就是说从种子节点出发开始游走）


数学定义：

r作为超参数，可以根据不同的数据集，不同的应用目的进行调参，使之适合数据集或者适合你的使用目的。

值得一提，RWR和RW并不是谁更优，而是侧重不同的情景。

我们来看看计算一个种子节点和其他所有节点关联度的RWR代码，这里r默认0.15，因为要跑到其他所有节点，所以应该少restart

1. import numpy as np
   
2. from scipy.sparse import csr_matrix
   
3. 
   
4. def rwr_scores(adj_matrix, seed_node, r=0.15, max_iter=100, tol=1e-6):
   
5.     """
   
6.     计算所有节点与种子节点的RWR关联度得分。
   
7. 
   
8.     参数:
   
9.         adj_matrix: scipy.sparse 的邻接矩阵 (N x N), 可以是coo, csr等。
   
10.         seed_node: 种子节点的索引 (int)。
    
11.         r: 重启概率 (float, 0<r<1)。
    
12.         max_iter: 最大迭代次数。
    
13.         tol: 收敛阈值。
    
14. 
    
15.     返回:
    
16.         scores: numpy array of shape (N,), 每个节点的得分（越高越相关）。
    
17.     """
    
18.     N = adj_matrix.shape[0]
    
19.    
    
20.     # 构建行归一化的转移矩阵 W: W[i,j] = 1 / degree(i) 如果 i->j 有边
    
21.     degrees = np.array(adj_matrix.sum(axis=1)).flatten()
    
22. 
    
23.     deg_inv = 1.0 / np.maximum(degrees, 1e-12)    # 避免除零
    
24.     D_inv = csr_matrix((deg_inv, (np.arange(N), np.arange(N))), shape=(N, N))
    
25.     W = D_inv @ adj_matrix
    
26.    
    
27.     # 初始向量：种子节点为1，其余为0
    
28.     p0 = np.zeros(N)
    
29.     p0[seed_node] = 1.0
    
30.    
    
31.     p = p0.copy()
    
32.    
    
33.     for it in range(max_iter):
    
34.         p_new = (1 - r) * (W @ p) + r * p0
    
35.         if np.linalg.norm(p_new - p, ord=1) < tol:    # 检查收敛
    
36.             break
    
37.         p = p_new
    
38.    
    
39.     return p

复制代码

下面是子图采样的RWR代码，这里因为目的是得到一个局部子图，所以为了有足够的节点且跟种子节点保持紧密关系，r设置的很高

1. def generate_rwr_subgraph(dgl_graph, subgraph_size):
   
2.     all_idx = list(range(dgl_graph.number_of_nodes()))
   
3.     reduced_size = subgraph_size - 1
   
4.     # 首次游走：重启概率为 1（相当于直接采样固定长度的随机游走。这里参数 restart_prob=1 是特殊的）
   
5.     traces = dgl.contrib.sampling.random_walk_with_restart(
   
6.         dgl_graph, all_idx, restart_prob=1, max_nodes_per_seed=subgraph_size*3
   
7.     )
   
8.     subv = []
   
9.     for i, trace in enumerate(traces):
   
10.         subv.append(torch.unique(torch.cat(trace), sorted=False).tolist())
    
11.         retry_time = 0
    
12.         while len(subv[i]) < reduced_size:
    
13.             # 若游走长度不足，则以 0.9 的重启概率重新采样，直到满足大小
    
14.             cur_trace = dgl.contrib.sampling.random_walk_with_restart(
    
15.                 dgl_graph, [i], restart_prob=0.9, max_nodes_per_seed=subgraph_size*5
    
16.             )
    
17.             subv[i] = torch.unique(torch.cat(cur_trace[0]), sorted=False).tolist()
    
18.             retry_time += 1
    
19.             if (len(subv[i]) <= 2) and (retry_time > 10):
    
20.                 subv[i] = (subv[i] * reduced_size)
    
21.         subv[i] = subv[i][:reduced_size]
    
22.         subv[i].append(i)   # 确保种子节点包含在内
    
23.     return subv

复制代码

restart_prob=1：首次调用时重启概率为 1，实际等价于对每个节点独立采样固定长度的随机游走序列（因为重启概率为 1 表示每次都回到起点，但 max_nodes_per_seed 限制了总步数，所以这里实际会生成从起点出发的随机游走轨迹）。


restart_prob=0.9：若第一次游走得到的节点数不足 subgraph_size-1，则以 0.9 的重启概率（即 90% 概率跳回起点，10% 概率继续随机游走）重新采样，直到获得足够多的节点。


该函数最终为每个节点返回一个包含 subgraph_size 个节点的列表（包括该节点自身）， subgraph_size 是一个固定值，你根据每个数据集可以使用不同的数值，比如：

1. if args.subgraph_size is None:
   
2.     if args.dataset in ['cora','citeseer']:
   
3.         args.subgraph_size = 4
   
4.     elif args.dataset in ['books','BlogCatalog','Flickr','Weibo']:
   
5.         args.subgraph_size = 5

复制代码

FishC

鱼油你好！关于RWR（带重启的随机游走）这个算法，我来帮你梳理一下它的原理和代码的关键点。

【算法核心】
RWR 是在普通随机游走（Random Walk）的基础上增加了重启（Restart）机制。每一步有两种选择：
- 以概率 1-r 从当前节点随机移动到它的一个邻居节点。
- 以概率 r 直接跳回到一开始选择的种子节点（即重启）。

这样做的目的是让游走过程不会“漂太远”，始终围绕种子节点探索局部结构。最终每个节点被访问的概率（或得分）反映了它与种子节点的“关联度”。

【代码解读】
你给出的函数 rwr_scores 实现了一个经典的迭代计算方法：

1. 
   
2. def rwr_scores(adj_matrix, seed_node, r=0.15, max_iter=100, tol=1e-6):
   
3.     n = adj_matrix.shape[0]
   
4.     # 列归一化邻接矩阵（概率转移矩阵）
   
5.     norm_adj = adj_matrix / adj_matrix.sum(axis=0)
   
6.     # 初始概率分布：只从种子节点出发
   
7.     p = np.zeros(n)
   
8.     p[seed_node] = 1.0
   
9.     # 重启向量：始终指向种子节点
   
10.     e = np.zeros(n)
    
11.     e[seed_node] = 1.0
    
12.     # 迭代直到收敛
    
13.     for _ in range(max_iter):
    
14.         p_new = (1 - r) * (norm_adj @ p) + r * e
    
15.         if np.linalg.norm(p_new - p, 1) < tol:
    
16.             break
    
17.         p = p_new
    
18.     return p
    

复制代码

关键点：
1. norm_adj 是按列归一化的转移矩阵（每个邻居的权重之和为1），表示从某个节点走到邻居的概率。
2. 初始向量 p 只将种子节点设为1，其他为0。
3. 重启向量 e 是种子节点的 one-hot 编码。
4. 迭代公式：p_new = (1-r) * (norm_adj @ p) + r * e 精确对应了“以 (1-r) 概率游走，以 r 概率重启”。
5. 收敛判据采用 L1 范数变化量小于容差 tol。
6. 返回的 p 就是每个节点与种子节点的关联度得分。

【参数说明】
- r=0.15 是一般推荐值，适合需要全局探索的场景。如果希望更保守（更聚焦种子节点局部），可以增大 r，比如 0.3~0.5；如果想探索更远，可以减小 r。
- max_iter 和 tol 控制迭代终止条件，保证在有限步内得到近似解。

【使用示例】
假设你有一个 5×5 的邻接矩阵 adj (稀疏格式)，想计算节点 0 与其他节点的关联度：

1. 
   
2. from scipy.sparse import csr_matrix
   
3. adj = csr_matrix(...)  # 你的图
   
4. scores = rwr_scores(adj, seed_node=0)
   
5. print(scores)
   

复制代码

如果对算法有进一步疑问（比如如何选择 r，或者普通随机游走与 RWR 的差异），欢迎继续交流！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。