诸神缄默不语-个人CSDN博文目录
本博文主要关注如何用代码实现图采样、随机游走、subgraph（为什么这些东西放在一起写，我感觉还蛮直觉的）。
随机游走和subgraph我之前都写过不少博文了，可以参考↑
这个主要是我前年还在干GNN时候接到过一个做数据集的项目，所以需要实现这些小功能。不过后来我不干那个项目了，也不干GNN了……然后这是我最近突然翻出来我当年写的有道云笔记，所以总结整理一下发出来分享技术。
关于subgraph还可以参考维基百科：Induced subgraph - Wikipedia
1. 图采样
随机游走算是一种图采样的方式吧，所以放到一块写。
- 主要参考这个项目（用NetworkX实现的）：Ashish7129/Graph_Sampling: Graph Sampling is a python package containing various approaches which samples the original graph according to different sample sizes.
- sampling by exploration（用随机游走或者traversal实现采样）
- Simple Random Walk Sampling (SRW)（node2vec差不多就是这个意思）
随机选择一个起始节点，随机游走直至达到指定长度
这个的实现方式：每走一步，抽样这个邻居节点，及这两个节点之间产生的边。考虑到图的连通性，如果每T次迭代新增的节点数少于growth_size，就换一个起始节点重新开始 - Random Walk Sampling with Fly Back Probability (RWF)：RWR版本
- Induced Subgraph Random Walk Sampling (ISRW)：SWR找出随机游走产生的节点序列后返回node-induced subgraph
用NetworkX内置的subgraph函数实现的 - Snowball Sampling (SB) （这个缩写我很难评）
每次抽样k个节点的BFS：随机抽k个节点作为第一stage，每次抽这一stage的每个节点的k个邻居（如果邻居小于k个，就抽所有邻居）形成下一stage的节点。
（stage就是epoch，我忘了我当时学BFS的时候用的是哪个版本的教程了反正用的就是这个术语，力扣或者DPV吧反正） - ForestFire Sampling (FF)：随机抽取一个节点烧了（加入采样图），点燃外向边，被点燃的边的另一头的节点有一定概率被烧（加入采样图）。没得烧了就换个随机节点。
（这个函数感觉原项目中实现得不够有随机性，是选择了一个节点的前random.randint个邻居。但是我记得NetworkX的邻居排列好像是不随机的，所以这个代码可能不够有随机性） - Metropolis Hastings Random Walk Sampling (MHRW)：首先选一个节点（度数不能是0）作为种子
v
v
v，然后定义proposal function
Q
(
v
)
=
k
v
Q(v)=k_v
Q(v)=kv，在
v
v
v的邻居中随机选一个
w
w
w、并生成一个随机数
ρ
∈
U
(
0
,
1
)
\rho\in U(0,1)
ρ∈U(0,1)，如果
ρ
≤
Q
(
v
)
/
Q
(
w
)
\rho ≤ Q(v)/Q(w)
ρ≤Q(v)/Q(w)，就将新节点加入采样，否则就停留在
v
v
v
感觉是加上一点概率采样、鼓励度数小的节点被抽样到的随机游走采样。 - Induced Metropolis Hastings Random Walk Sampling (Induced-MHRW)：MHRW，但是用MHRW的节点生成的induced subgraph
- Simple Random Walk Sampling (SRW)（node2vec差不多就是这个意思）
- Edge Sampling
- Total Induction Edge Sampling (TIES)1：就直接从原图中随机抽边，然后生成edge-induced subgraph，然后再用这些节点生成node-induced subgraph
- sampling by exploration（用随机游走或者traversal实现采样）
- 终止条件：达到最大迭代数、达到最大节点/边数（或节点/边在原节点/边中所占的数量比例）
- 参考相关采样算法进行补充：
- 随机点采样（Random Node, RN）
- 随机边采样（Random Edge, RE）
- 双网络图采样（Bi-graph Random Walk, BRW）：针对有向图，在种子节点上先在出度和入度之间二选一，然后再在选中方向上随机选择一个节点
- 随机点采样（Random Node, RN）
- 其他抽样方法（我都还没看，哈哈）
- GraphSAINT
官方GitHub项目：https://github.com/GraphSAINT/GraphSAINT（我看这个项目里也实现了好几种sampler） - Sampling from Large Graphs
- Network Sampling via Edge-based Node Selection with Graph Induction
-
Sampling methods for efficient training of graph convolutional networks: A survey
（这个大概应该指的是类似GraphSAGE那种……就也算是采样边） - PinSage
可以参考博文：PinSage：GCN在商业推荐系统首次成功应用
- GraphSAINT
2. 随机游走
torch_cluster的random_walk（返回节点序列） https://github.com/rusty1s/pytorch_cluster/blob/86f2e4a0f6bff4ad966787e0e3902f8bcdfa64a0/README.md#randomwalk-sampling
这个返回值是有重复的。可以看看别的随机游走采样的实现方式里面如何处理重复节点的文章来源：https://www.toymoban.com/news/detail-582911.html
3. subgraph
- node-induced subgraph（已知节点索引）
如果已知邻接矩阵，没什么好说的，直接切片就行
如果已知edge_index，参考PyG的subgraph函数（https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/utils/subgraph.html）的实现方式
NetworkX内置subgraph函数 - edge-induced subgraph（已知edge_index的话也很直觉）
- k-hop subgraph
PyG的实现：https://pytorch-geometric.readthedocs.io/en/latest/modules/utils.html#torch_geometric.utils.k_hop_subgraph
-
Graph_Sampling官方给的参考文献是这篇：Network Sampling via Edge-based Node Selection with Graph Induction ↩︎文章来源地址https://www.toymoban.com/news/detail-582911.html
到了这里，关于图采样、随机游走、subgraph的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
