图采样与子图抽取：随机游走、k-hop 与偏差评估

1. 规模：十亿节点/百亿边，全图遍历一次的成本不可接受
   （GNN 训练每轮都要聚合邻居，全图跑一轮可能几小时）
2. 内存：图算法（PageRank/社区发现）在单机上装不下全图
3. 可视化：人眼能看的节点数在几百到几千量级
4. 合规：对外提供数据前必须脱敏并降低可识别性
→ 采样是「用可控的偏差换可承受的成本」，不是免费的午餐

目标是「估计全局统计量」→ 要求无偏/低偏差，方差可估计
  （如估计平均度数、估计社区规模、估计度分布尾部）
目标是「训练模型」→ 允许有偏，但训练与推理的分布要一致
  （训练用邻居采样，推理也要用同样的邻居采样）
目标是「可视化」→ 要求结构保真（社区、枢纽、桥接可见）
目标是「对外共享」→ 要求隐私保真（无法反推个体）
→ 先写清目标，再选方法；「随便抽一点」是最常见的错误起点

均匀节点采样：每个节点以概率 p 独立入选
  采样图 = 入选节点 + 两端都入选的边
  偏差：高度数节点与低度数节点被抽中的概率相同，
        但高度数节点「两端都入选」的边更多 → 边密度被高估
  后果：采样图平均度数偏高、连通性偏好，稀疏尾部丢失

加权节点采样：按度数（或 PageRank）加权抽取
  用途：故意保留枢纽，做「重要节点优先」的子图
  代价：度分布被人为扭曲，不能用来估计全局统计量

思路 A：改游走规则（让稳态分布变成想要的分布）
  Metropolis-Hastings 游走：以 min(1, deg(u)/deg(v)) 的概率接受转移
  → 稳态分布变成均匀分布，代价是接受率低、需要更多步数
  带重启的游走（RWR）：以概率 α 跳回种子
  → 稳态分布偏向种子附近，适合「以某节点为中心」的采样

思路 B：不改游走，改权重（重要性采样）
  对访问到的节点按 1/π(v) 加权，用加权估计替代简单平均
  → 无偏但方差可能很大（高度数节点权重极小）
  实践中常用「裁剪权重」控制方差，代价是引入少量偏差

import random

def random_walk(adj, seed, steps, alpha=0.15):
    """带重启的随机游走：alpha 概率跳回种子，抑制长程漂移"""
    path, cur = [seed], seed
    for _ in range(steps):
        if random.random() < alpha or not adj.get(cur):
            cur = seed
        else:
            nbrs, weights = zip(*adj[cur])
            cur = random.choices(nbrs, weights=weights, k=1)[0]
        path.append(cur)
    return path

def walks_from_seeds(adj, seeds, walks_per_seed, steps):
    """每个种子发多条游走，拼成训练样本序列"""
    return [random_walk(adj, s, steps)
            for s in seeds for _ in range(walks_per_seed)]

k-hop 子图的两个致命问题：
1. 超节点：种子附近若有一个连接百万条边的枢纽，
   2 跳就可能把整个图拉进来 → 必须有「每跳节点数上限」保护
2. 边界节点：k 跳边界的节点只有部分邻居被包含，
   它们的特征与全图上的特征不一致（度数被截断）

A. 采样固定邻居数（GraphSAGE 式）：每层固定采样 N 个邻居（如 25），
   层数 × 采样数决定感受野；计算量固定、可批处理，但引入采样噪声
B. 边界节点特征置零/标记：给边界节点打「is_boundary」标记，
   让模型知道邻域不完整；实现简单，但模型要额外学这个信号
C. 扩展一圈（抽 k+1 跳、只用 k 跳）：让第 k 跳节点邻居完整，
   但只用前 k 跳做聚合；无截断，代价是抽取成本上升
→ 生产上 A + B 组合最常见：固定邻居采样 + 边界标记

1. 按种子批（batch）抽取，而不是一次抽全图
2. 每个种子的子图设置硬上限（节点数/边数/跳数），超限即截断并标记
3. 去重：批量抽取时子图之间会大量重叠，先合并去重再送下游
4. 缓存：同一批种子的子图结构可在多轮训练中复用（结构不变时）
5. 边方向：有向图要明确「只沿出边」还是「双向」，两者结果差异巨大
6. 超节点处理：抽样边（只保留随机 N 条并标记）、剪枝（排除度数超阈值的
   节点）、或拆分（按属性分片成多个虚拟节点）——不处理则 k-hop 在枢纽处失控

按什么分层：
- 社区（先用社区发现算法打标签，每个社区按比例抽）
- 度数分桶（低/中/高度数各抽一批，保证度分布覆盖）
- 业务标签（客户等级、地区、行业）
- 时间（老节点/新节点各抽）
→ 分层的价值：避免「均匀采样恰好把某个小社区全部漏掉」
→ 代价：需要先有一份分层标签，且分层维度要与下游目标相关

常见错误：对全量数据做均匀采样
  → 采样子图里「老节点」被过度代表（它们存在时间长、边多）
  → 用它训练时序模型，会系统性低估新节点的活跃度

正确做法：
- 按时间窗口采样（每个窗口内采固定比例），保留时间趋势
- 时间切分（训练用前 80% 时间、验证用后 20%），避免时间穿越
- 对新增节点做「加权补偿」，纠正新老节点的比例失衡

用途：想让「稀有但重要」的结构（如欺诈环、桥接节点）
      在样本里出现得更频繁
做法：
  1. 定义重要性 w(v)（如度数、PageRank、异常分）
  2. 按 w 抽样得到样本
  3. 估计时除以抽样概率（1/w 修正），保证估计无偏
陷阱：w 极端倾斜时，修正后的权重方差爆炸，
      少数样本主导整个估计 → 必须裁剪权重或增加样本量

均匀负采样：从全图随机取节点对 → 大部分是「容易的」负样本
按度数负采样：负样本按 deg^0.75 采样（类似 word2vec）
  → 让负样本更多来自高度数节点，避免「太容易」的样本
难负采样（hard negative）：选「嵌入空间接近但不连边」的节点对
  → 训练信号更强，但容易引入假阴性（实际有边但未被观测）
→ 负采样策略直接影响嵌入质量，必须与评估指标一起调

必查的六个统计量：
1. 节点数 / 边数比例（是否与采样率一致）
2. 度分布（对数坐标下的尾部形状是否一致）
3. 平均聚类系数（社区结构的保真度）
4. 连通分量数（采样是否把图切碎了）
5. 平均路径长度 / 直径（小世界性质是否保留）
6. 社区规模分布（社区是否被均匀保留）
→ 任一统计量偏离超过阈值，就说明采样方法引入了系统性偏差

def estimate_mean_degree(adj_sample, rate):
    """采样图上的平均度数是有偏的，需按采样率修正"""
    n_s = len(adj_sample)
    m_s = sum(len(v) for v in adj_sample.values()) / 2
    return (2 * m_s / n_s) / rate if rate > 0 else None

def degree_distribution(adj):
    """度分布：比较采样图与原图的尾部形状"""
    degs = sorted(len(v) for v in adj.values())
    n = len(degs)
    return {d: sum(1 for x in degs if x >= d) / n for d in (1, 5, 10, 50, 100)}

1. 属性层面：泛化（具体年龄 → 年龄段）、抑制（直接删除敏感属性）、
   假名化（ID 换成随机标识，但保留结构）
2. 结构层面：
   - 加噪：随机增删少量边（破坏精确结构匹配）
   - 聚类：把相似的节点合并为「超级节点」（k-匿名思路）
   - 采样：只发布子图——但采样不提供隐私保证！
3. 差分隐私（DP）：对查询结果加噪，提供可证明的隐私保证
   - 边级 DP：相邻数据集差一条边，输出分布相近
   - 节点级 DP：差一个节点及其所有边（更强，也更难实现）
→ 采样 ≠ 隐私：采样子图仍可能暴露个体，必须叠加真正的隐私机制

- 明确共享目的与最小必要字段（能不给就不给）
- 属性脱敏 + 结构加噪 + 假名化组合使用
- 发布前做「再识别演练」：尝试用公开数据反推个体
- 记录数据血缘与接收方，签数据使用协议
- 定期复审（公开数据越多，历史匿名图的再识别风险越高）
→ 脱敏不是一次性动作，而是随外部数据增长持续复评的过程

目标：训练模型（允许有偏，但训练与推理必须同分布）
约束：单次训练样本不超过 500 万边；必须覆盖足够多的可疑样本
方法：以「可疑账户 + 其 2 跳邻域」为种子抽取，
      叠加「随机账户 + 2 跳邻域」做背景样本（保证正负比例合理）

from collections import defaultdict

MAX_NODES, MAX_DEG = 2000, 500     # 单种子节点上限、超节点阈值

def extract_khop(driver, seed_id, k=2):
    """抽 k-hop 子图；超限截断并标记，超节点做边抽样"""
    q = """
    MATCH (c:Account {id: $seed})
    CALL apoc.path.subgraphAll(c, {maxLevel: $k}) YIELD nodes, relationships
    RETURN [n IN nodes | {id: n.id, deg: size((n)-[]-())}] AS nodes,
           [r IN relationships | {s: startNode(r).id, e: endNode(r).id}] AS rels
    """
    with driver.session() as s:
        rec = s.run(q, seed=seed_id, k=k).single()
    if rec is None:
        return None
    nodes, rels = rec["nodes"], rec["rels"]
    truncated = len(nodes) > MAX_NODES
    if truncated:                        # 截断：保留度数最高的 MAX_NODES 个
        nodes = sorted(nodes, key=lambda x: -x["deg"])[:MAX_NODES]
        keep = {n["id"] for n in nodes}
        rels = [r for r in rels if r["s"] in keep and r["e"] in keep]
    deg, per, sampled = defaultdict(int), defaultdict(int), []
    for r in rels:                       # 统计度数用于超节点判定
        deg[r["s"]] += 1
        deg[r["e"]] += 1
    for r in rels:                       # 超节点边抽样
        if deg[r["s"]] > MAX_DEG or deg[r["e"]] > MAX_DEG:
            if per[r["s"]] < MAX_DEG and per[r["e"]] < MAX_DEG:
                sampled.append(r); per[r["s"]] += 1; per[r["e"]] += 1
        else:
            sampled.append(r)
    return {"seed": seed_id, "nodes": nodes, "rels": sampled,
            "truncated": truncated}

def build_dataset(seeds, extractor):
    """批量抽取 → 全局去重 → 导出（子图重叠极多，必须去重）"""
    seen_nodes, all_rels = set(), {}
    for s in seeds:
        g = extractor(s)
        if not g:
            continue
        seen_nodes.update(n["id"] for n in g["nodes"])
        for r in g["rels"]:
            all_rels[(r["s"], r["e"])] = r     # 按 (起点,终点) 去重
    return {"num_nodes": len(seen_nodes), "rels": list(all_rels.values())}

1. 下游指标莫名变差 → 先比度分布与连通分量，多半是采样偏差
2. 采样图节点数远少于预期 → 均匀边采样丢掉了低度节点，改节点采样
3. 采样图看起来「太稠密」→ 均匀节点采样的固有边密度高估
4. 训练/推理效果不一致 → 训练与推理的抽取参数不同（最常见）
5. 抽取很慢/内存爆 → 超节点未处理，k-hop 在枢纽处失控
6. 样本里几乎全是老节点 → 未做时间分层采样
7. 训练不稳定、方差大 → 样本量不足，增加种子或游走条数
8. 对外数据被反推出个体 → 只做了属性脱敏，结构未处理

1. 记录采样参数：种子来源、采样率、跳数、随机种子
   （不记录就无法复现，也无法排查下游问题）
2. 保存抽样诊断报告：度分布、聚类系数、连通分量、社区规模对比
3. 多次采样：用方差判断「方法有偏」还是「样本不够」
→ 采样是「有损压缩」，必须知道损失了什么，才能判断下游能不能用