图分区算法：Edge-cut vs Vertex-cut 与 METIS 工程解析

副标题 / 摘要
图分区不是“离线预处理小优化”，而是生产级图数据库的主性能开关：分错了，查询延迟和网络流量会一起失控。本文按 ACERS 模板，讲清 Edge-cut / Vertex-cut 的取舍、METIS 的多层思想，以及工程里真正有效的评估指标。

预计阅读时长：18~22 分钟
标签：图分区、Edge-cut、Vertex-cut、METIS
SEO 关键词：Graph Partitioning, Edge-cut, Vertex-cut, METIS, Query Latency
元描述：从目标函数到工程指标，系统理解图分区如何影响查询时延与网络通信，并给出可运行代码与调优步骤。

目标读者

做图数据库、图计算平台、风控图谱、推荐图谱的后端工程师
需要把“查询慢”拆解到分区层面定位根因的性能工程师
想从概念级迈到工程可落地的算法同学

背景 / 动机

关系数据库里你可以靠索引、Join 重排、缓存命中优化性能；图数据库里，跨机边往往才是第一瓶颈。
当一条查询路径频繁跨分区，就会触发：

远程 RPC 往返（RTT）
远端子图拉取与反序列化
多分区并发协调与结果合并

所以在生产环境里，图分区直接影响两件核心指标：

查询延迟（p95/p99）
网络通信量（bytes/s、cross-partition messages）

一句话：如果你做的是生产级图数据库，分区算法不是锦上添花，是基础能力。

核心概念

Graph Partitioning：把图切成 k 个分区，同时尽量减少分区间耦合并保持负载均衡。
Edge-cut：最小化跨分区边数量，节点只归属一个分区。
Vertex-cut：按边分区，允许节点在多个分区复制，目标是降低热点边带来的倾斜。
Balance Constraint：分区负载不能严重倾斜，常见约束 |V_i| <= (1+ε)|V|/k 或按边负载约束。
METIS（思想）：多层法（Coarsen -> Initial Partition -> Uncoarsen + Refine），通过“先缩图再细化”降低全局搜索成本。

快速掌握地图（60-120 秒）

问题形状：大图拆成 k 个分区，最小化跨机访问并保持负载均衡。
一句话核心：先选目标函数（Edge-cut/Vertex-cut），再用多层法求初解并做增量修正。
何时用 / 何时避免：静态或缓变图适合离线基线分区；高频动态图需要增量重平衡配套。
复杂度速览：最优划分组合复杂，工程上靠近似算法 + 监控闭环。
常见失败模式：只优化 cut，不优化 balance，结果 p99 反而上升。

主心智模型（Master Mental Model）

核心抽象：图分区是“带约束的图割优化问题”。
问题族归类：组合优化 + 局部搜索 + 多目标权衡（通信、延迟、负载）。
与已知模板同构：
- 离线阶段类似“多层 coarse-to-fine 优化”；
- 在线阶段类似“局部 hill-climbing + 预算受限迁移”。

可行性与下界直觉

对于连接紧密且社区边界不明显的图，cut 的理论下界不会很低。
当查询模板天然跨社区（比如跨域风控链路），即使分区完美，跨机访问也无法归零。
当图的幂律特征显著（少量超高出度节点），单纯 Edge-cut 会遇到热点下界：
- 你能减少 cut，但很难同时把热点压平。

反例：
如果一个超级节点连接 10 万条边，且访问集中在该节点周围，强行保持节点不复制会让单分区压力显著偏斜。此时 Vertex-cut 往往比 Edge-cut 更现实。

问题建模与约束规模

实际工程里建议把目标拆成显式函数：

\[ \text{Score} = \alpha \cdot \text{CutCost} + \beta \cdot \text{ImbalanceCost} + \gamma \cdot \text{HotspotCost} \]

其中：

CutCost：跨分区边数或带权跨边和
ImbalanceCost：分区负载偏离目标容量的惩罚
HotspotCost：热点节点或热点边造成的局部拥塞惩罚
α,β,γ：业务权重（由 SLA 倒推）

规模建议（可作为起步阈值，不是硬标准）：

节点千万级、边亿级：优先离线多层法 + 周期校准
分区数 k 增大时：先看网络瓶颈，再看单机瓶颈，避免盲目加分区
ε（负载松弛）常见从 0.03 到 0.10 做扫描

A — Algorithm（题目与算法）

题目还原（工程化）

给定一张大图 G=(V,E)，要切成 k 个分区，满足：

分区负载尽量均衡；
查询常走的边尽量留在分区内；
网络通信量最小化；
对热点节点有可控策略（避免单机打爆）。

输入输出

名称	类型	描述
`G`	图	生产图（可带权）
`k`	int	分区数
`obj`	enum	目标函数：Edge-cut 或 Vertex-cut
`constraint`	配置	负载均衡阈值、热点阈值
返回	`part(v)` / `part(e)`	节点或边到分区的映射

示例（8 节点、2 分区）

社区 A: 0-1-2-3-0
社区 B: 4-5-6-7-4
桥接边: (1,4), (2,5), (3,6)

若按社区切：P0={0,1,2,3}, P1={4,5,6,7}，Edge-cut = 3
若随机切：常见会出现 Edge-cut >= 6

这就是“查询延迟差一倍以上”的来源：跨分区边越多，查询越容易变成分布式回路。

思路推导（从暴力到可用）

朴素暴力

枚举所有分区分配方式，再计算 cut 与 balance
复杂度指数级，不可落地

关键观察

生产图通常稀疏但规模大，必须用近似最优而非全局最优
绝大多数收益来自：
- 减少跨分区边
- 避免热点分区
“算法名字”不是第一位，目标函数 + 约束 + 指标闭环才是第一位

方法选择

Edge-cut 主线：OLTP 图查询、短路径、k-hop 检索常用
Vertex-cut 主线：超高出度节点（明星点、超级账户）明显时更稳
METIS 思想：离线基线分区的工业默认选项之一

C — Concepts（核心思想）

1) Edge-cut vs Vertex-cut

Edge-cut（节点唯一归属）

目标函数（简化）：

[ \min \sum_{(u,v)\in E} [part(u) \neq part(v)] ]

优点：模型直观、查询路由简单
缺点：超级节点会把大量边拖成跨分区通信

Vertex-cut（边归属，节点可复制）

常见指标是复制因子：

[ RF = \frac{1}{|V|}\sum_{v\in V} |A(v)| ]

其中 A(v) 是节点 v 所在分区集合。RF 越低越好。

优点：能把高出度节点边均摊到多机
缺点：节点副本一致性与读写路径更复杂

2) METIS 的多层思想（必须懂）

METIS 核心不是某个魔法公式，而是三段式流程：

Coarsening：重边优先匹配（heavy-edge matching）缩图
Initial Partition：在小图上快速做初始划分
Uncoarsen + Refine：逐层还原并用 FM/KL 类局部优化减小 cut

工程价值：把“大图难题”变成“多层小步修正”，通常比直接在原图上贪心更稳定。

Deepening Focus（PDKH）

本文重点深化 2 个概念：

概念 A：Edge-cut 目标与查询延迟映射
概念 B：METIS 多层分区流程

概念 A：Edge-cut -> 延迟

Problem Reframe：分区质量本质是在压缩跨机 hop。
Minimal Example：同一查询模板在 Edge-cut=3 与 Edge-cut=7 时，跨机请求数近似翻倍。
Invariant：在负载约束不破坏前提下，减少跨分区边不会增加远程 hop 的期望值。
Formalization：
- latency ≈ local_cpu + remote_rtt * cross_hops + deserialize_cost
- cross_hops 与 cut ratio 高相关。
Correctness Sketch：若查询模板固定，跨分区边越少，触发远程访问的边界事件越少。
Threshold：当 cut_ratio > 0.25 时，很多线上图查询 p99 会明显恶化（经验阈值，需按业务校正）。
Failure Mode：只压 cut 不看负载，会导致单分区热点，整体吞吐反而下降。
Engineering Reality：必须和分区负载、热点度分布一起看，不能单指标驱动。

概念 B：METIS 多层流程

Problem Reframe：不是一次算完，而是“缩图求粗解，再逐层修正”。
Minimal Example：1000 万边图先缩到 20 万边，再做初分与回放优化。
Invariant：每次 refinement 只接受降低目标值或保持平衡约束的迁移。
Formalization：Coarsen -> Partition -> Uncoarsen/Refine。
Correctness Sketch：虽非全局最优，但局部单调改进确保目标函数不恶化。
Threshold：图越大、社区结构越明显，多层法收益越稳定。
Failure Mode：动态图变化太快，离线分区过期，收益迅速衰减。
Engineering Reality：必须配增量重平衡策略（周期重分 + 热点迁移）。

实践指南 / 步骤

定义目标函数：先决定 Edge-cut 还是 Vertex-cut，不要先选算法名。
定义约束：分区容量、热点阈值、迁移预算。
离线求初分区：用 METIS 思想得到 baseline。
线上观察指标：cut_ratio、RF、p95/p99、cross-partition bytes。
局部重平衡：按热点与跨边贡献做小步迁移，避免全量重分区。
回归验证：压测典型查询模板，而不是只看单次批处理统计。

决策准则（Selection Guide）

按度分布选目标：
- 平滑度分布：先尝试 Edge-cut。
- 明显幂律分布：优先评估 Vertex-cut。
按查询类型选目标：
- 短路径、局部子图读取：Edge-cut 更容易优化路由。
- 批遍历、消息传播：Vertex-cut 在热点压力下更稳。
按机器内存选策略：
- 内存紧张：减少复制，谨慎使用 Vertex-cut。
- 内存相对充裕：可用复制换吞吐稳定性。
按迁移预算选节奏：
- 低迁移预算：做局部增量修正。
- 可接受窗口：做离线重分区 + 增量回填。

可运行示例（Python）

下面是一个可运行的“平衡约束 + cut 代价”本地搜索示例（用于理解目标函数，不是完整 METIS 实现）：

from collections import defaultdict
from typing import Dict, List, Tuple

Edge = Tuple[int, int]


def edge_cut(edges: List[Edge], part: Dict[int, int]) -> int:
    return sum(1 for u, v in edges if part[u] != part[v])


def partition_sizes(part: Dict[int, int], k: int) -> List[int]:
    sizes = [0] * k
    for node in part:
        sizes[part[node]] += 1
    return sizes


def greedy_balanced_partition(
    nodes: List[int],
    edges: List[Edge],
    k: int,
    max_imbalance: float = 0.10,
    max_iter: int = 20,
) -> Dict[int, int]:
    part = {node: node % k for node in nodes}
    limit = int((1.0 + max_imbalance) * len(nodes) / k) + 1

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    for _ in range(max_iter):
        improved = False
        sizes = partition_sizes(part, k)

        for node in nodes:
            current = part[node]
            best_part = current
            best_gain = 0

            for candidate in range(k):
                if candidate == current:
                    continue
                if sizes[candidate] + 1 > limit:
                    continue

                # 估算 node 迁移后的 cut 变化（正值表示 cut 下降）
                gain = 0
                for nei in adj[node]:
                    before_cross = 1 if part[nei] != current else 0
                    after_cross = 1 if part[nei] != candidate else 0
                    gain += (before_cross - after_cross)

                if gain > best_gain:
                    best_gain = gain
                    best_part = candidate

            if best_part != current:
                sizes[current] -= 1
                sizes[best_part] += 1
                part[node] = best_part
                improved = True

        if not improved:
            break

    return part


def main() -> None:
    nodes = list(range(8))
    edges = [
        (0, 1), (1, 2), (2, 3), (3, 0),
        (4, 5), (5, 6), (6, 7), (7, 4),
        (1, 4), (2, 5), (3, 6),
    ]
    k = 2

    init_part = {node: node % k for node in nodes}
    init_cut = edge_cut(edges, init_part)

    opt_part = greedy_balanced_partition(nodes, edges, k=k)
    opt_cut = edge_cut(edges, opt_part)

    print("init part:", init_part, "cut=", init_cut)
    print("opt part :", opt_part, "cut=", opt_cut)


if __name__ == "__main__":
    main()

运行方式：

python3 graph_partition_demo.py

可运行示例 2：Vertex-cut 复制因子估算

from collections import defaultdict
from typing import Dict, List, Tuple

Edge = Tuple[int, int]


def replication_factor(edges: List[Edge], edge_part: Dict[Edge, int], n_nodes: int) -> float:
    node_parts = defaultdict(set)
    for (u, v), p in edge_part.items():
        node_parts[u].add(p)
        node_parts[v].add(p)
    total = sum(len(node_parts[node]) if node in node_parts else 1 for node in range(n_nodes))
    return total / n_nodes


def main() -> None:
    # 简化示例：3 个分区
    edges = [(0, 1), (0, 2), (0, 3), (4, 5), (5, 6), (6, 7), (3, 4)]
    edge_part = {
        (0, 1): 0,
        (0, 2): 1,
        (0, 3): 2,
        (4, 5): 1,
        (5, 6): 1,
        (6, 7): 1,
        (3, 4): 2,
    }
    rf = replication_factor(edges, edge_part, n_nodes=8)
    print("replication factor =", round(rf, 3))


if __name__ == "__main__":
    main()

这个示例用于直观看 RF 的变化趋势：同样的图，在分区策略不同的情况下，节点复制开销会显著不同。

解释与原理（为什么这么做）

这个示例的核心价值是把“分区优劣”量化出来：

你可以直接看到 cut 从多少降到多少；
你可以加上业务查询权重，把关键边赋更高权重；
你可以把 balance 约束收紧，观察延迟与吞吐的拐点。

真实生产里，METIS 会在更大规模图上更系统地做“缩图 + 回放优化”，但底层思想仍是：

有目标函数；
有约束；
有可观测指标闭环。

Worked Example（Trace）

以下给出一次“分区迁移是否值得”的简化追踪：

初始：cut_ratio = 0.29, p99 = 410ms, cross_bytes = 1.8GB/min
候选迁移：把 2 万节点子图从 P3 迁到 P5
预估收益：cut_ratio -> 0.23，P5 CPU +5%，P3 CPU -8%

执行后观测：

第 1 小时：p99 降到 330ms，cross_bytes 降到 1.3GB/min
第 6 小时：P5 负载稳定，未触发热点告警
第 24 小时：业务高峰 p99 稳定在 300~320ms

结论：如果迁移后负载仍在阈值内，降低跨边通常能稳定带来延迟收益。

正确性（Proof Sketch）

这里不证明“全局最优”，而证明“局部迁移策略的单调改进性质”：

不变式：每次迁移都必须满足容量约束与热点约束。
保持性：只有当 Score 下降（或同等分数但更稳）时才接受迁移。
终止性：当没有候选迁移能继续下降 Score，局部搜索停止。

因此你至少得到一个满足约束的局部最优解，而不是随机波动的不可控状态。

复杂度与阈值

离线多层法通常近似线性到次线性可扩展（依赖实现与图结构）。
在线局部迁移每轮复杂度取决于候选集合大小 |C| 与增量评估成本。
工程上更重要的阈值不是 Big-O，而是：
- 每轮迁移窗口（例如 5~15 分钟）
- 每轮迁移预算（例如最多迁移 0.5% 节点）
- 回滚阈值（例如 p99 连续 5 分钟上升即回滚）

常数因子与工程现实

序列化成本：跨机边导致对象解码，常数因子很高。
缓存局部性：分区后局部子图更集中，缓存命中会显著影响收益上限。
批处理窗口：离线重分区如果超过维护窗口，会吞掉全部理论收益。
副本一致性：Vertex-cut 的写入路径更复杂，读写混合业务要谨慎。

上线排障 Checklist（生产必备）

分区方案上线后，不要只看“平均延迟下降”就结束，建议按下面清单做 24 小时回放：

核心指标四件套是否同向改善
- p95/p99 是否下降
- cross-partition bytes 是否下降
- cut_ratio 或 RF 是否朝目标方向变化
- 单分区 CPU / 内存是否未越过告警阈值
查询分布是否被“平均值掩盖”
- Top 10 慢查询模板是否真的改善
- 长尾查询是否出现反向劣化
- 峰值流量时段是否保持趋势一致
迁移副作用是否可控
- 迁移窗口内是否出现写入抖动
- 缓存命中率是否短时跌穿保护线
- 回滚脚本是否演练成功（至少一次）
热点分区是否发生漂移
- 今天最热分区与昨天是否一致
- 热点是否从单机转移到另一单机（“热点搬家”）
- 是否需要进一步做热点节点专门策略
容量边界是否提前暴露
- 未来 7 天边增长预测下，当前 k 是否仍可承载
- 复制因子增长趋势是否会压垮内存预算
- 是否要提前预留分区扩容窗口

为了让排障可复用，建议把分区变更记录成结构化日志：

{
  "change_id": "part-2026-02-09-01",
  "strategy": "edge_cut_with_balance",
  "before": {"cut_ratio": 0.27, "p99_ms": 380, "cross_bytes_mb_min": 1540},
  "after": {"cut_ratio": 0.21, "p99_ms": 305, "cross_bytes_mb_min": 1090},
  "risk": {"hot_partition_cpu_max": 0.72, "rollback_ready": true}
}

这份结构化记录会在复盘时非常关键：你能回答“为什么有效”“是否可复制”“下一次怎么更稳”。

指标计算口径（避免团队内口径不一致）

很多团队分区讨论无效，不是因为算法差，而是口径不统一。建议固定以下定义：

cut ratio
- 定义：跨分区边数 / 总边数
- 口径：按“活跃子图边”与“全图边”分别统计，避免互相污染
cross-partition bytes
- 定义：跨分区请求的网络字节总量
- 口径：分读请求与写请求，读多写少业务要单独看读路径
partition hotspot index
- 定义：max_partition_qps / avg_partition_qps
- 口径：按 1 分钟窗口和 5 分钟窗口各算一次，分别反映抖动与趋势
replication factor（仅 Vertex-cut）
- 定义：节点平均副本数
- 口径：对在线活跃节点单独算一次，避免静态冷数据稀释风险

若这四项口径固定，你就能把“分区优化”从经验讨论变成可审计的工程过程。

回放压测模板（Python）

import csv
import statistics
from dataclasses import dataclass
from typing import List


@dataclass
class QuerySample:
    template: str
    latency_ms: float
    cross_bytes: int
    cross_hops: int


def load_samples(path: str) -> List[QuerySample]:
    result: List[QuerySample] = []
    with open(path, "r", encoding="utf-8") as f:
        reader = csv.DictReader(f)
        for row in reader:
            result.append(
                QuerySample(
                    template=row["template"],
                    latency_ms=float(row["latency_ms"]),
                    cross_bytes=int(row["cross_bytes"]),
                    cross_hops=int(row["cross_hops"]),
                )
            )
    return result


def p99(values: List[float]) -> float:
    if not values:
        return 0.0
    values_sorted = sorted(values)
    idx = int(0.99 * (len(values_sorted) - 1))
    return values_sorted[idx]


def summarize(samples: List[QuerySample]) -> None:
    latency = [item.latency_ms for item in samples]
    cross_bytes = [item.cross_bytes for item in samples]
    cross_hops = [item.cross_hops for item in samples]
    print("count =", len(samples))
    print("avg_latency_ms =", round(statistics.mean(latency), 2))
    print("p99_latency_ms =", round(p99(latency), 2))
    print("avg_cross_bytes =", int(statistics.mean(cross_bytes)))
    print("avg_cross_hops =", round(statistics.mean(cross_hops), 3))


if __name__ == "__main__":
    baseline = load_samples("baseline.csv")
    candidate = load_samples("candidate.csv")
    print("baseline")
    summarize(baseline)
    print("candidate")
    summarize(candidate)

这段脚本适合做“改分区前后”的最小回放对比：同一批模板、同一批输入、统一口径输出，避免拍脑袋结论。

E — Engineering（工程应用）

场景 1：在线图查询（Edge-cut 主导）

问题：k-hop / 路径查询 p99 偏高。
做法：优先降低常用查询边界上的跨分区边，并保负载均衡。
收益点：降低跨机 hop 次数，稳定 p95/p99。

目标：cut_ratio 从 0.31 -> 0.18
结果：路径查询 p99 从 420ms -> 230ms（示例口径）

场景 2：超级节点图谱（Vertex-cut 更稳）

问题：少数节点出度极高，Edge-cut 下单机热点严重。
做法：按边分区并允许节点复制，控制复制因子 RF。
收益点：把热点写入/遍历压力摊到多分区。

场景 3：图分片与容量规划（METIS baseline + 增量迁移）

问题：全量重分区成本高，业务不能频繁停机迁移。
做法：离线周期性重算 baseline，线上仅迁移“高收益候选子图”。
收益点：在迁移预算内持续修正分区质量。

R — Reflection（反思与深入）

复杂度与工程代价

分区问题本身组合复杂，追全局最优不现实。
工程上更关注“可持续优化路径”：
- 有 baseline
- 有监控
- 有增量修复

替代方案与取舍

方案	优点	缺点	适用
Edge-cut	查询路由简单	超级节点易热点	OLTP 图查询
Vertex-cut	热点更可控	副本一致性复杂	Power-law 图
随机分片	实现简单	通信成本高	仅早期 PoC

量化对比（示例口径）

指标	方案 A（随机）	方案 B（Edge-cut）	方案 C（Vertex-cut）
cut ratio	0.34	0.19	0.22
RF	1.00	1.00	1.38
查询 p99	480ms	260ms	290ms
网络字节	2.1GB/min	1.2GB/min	1.0GB/min

解读：

Edge-cut 在读路径上更干净；
Vertex-cut 在热点和网络字节上可能更优，但要付复制管理成本；
真正选择取决于你的读写比例和一致性要求。

常见误区

只看算法名，不看目标函数：上线后常出现“理论很好、指标很差”。
只压 cut，不控 balance：延迟降了但吞吐掉了。
只做离线一次分区：动态图场景下效果会自然劣化。

反例（必须记住）

假设你把所有热门节点放同一分区以降低 cut，短期看通信下降；但该分区 CPU 飙升导致排队，最终 p99 更差。
这说明：分区优化是多目标问题，不是单目标极限优化。

常见问题与注意事项

METIS 能直接解决在线动态重分区吗？
不能。METIS 更适合作离线初分区基线，在线要配合增量迁移策略。
Edge-cut 一定优于 Vertex-cut 吗？
不一定。高出度节点极端不均时，Vertex-cut 往往更稳。
如何判断该不该重分区？
看趋势而非单点：cut_ratio 上升、跨分区字节上升、p99 上升并持续一段时间。
分区数 k 怎么选？
先按机器预算给上限，再压测 k 对 p95/p99 与通信量的联合曲线，找拐点。

最佳实践与建议

先定义查询主路径，再定义分区目标函数
用业务权重边，而不是无差别边权
每次迁移设预算上限，避免全网抖动
同时看 cut_ratio、RF、p99、网络字节，不做单指标决策
为热点节点准备单独策略（复制、旁路索引或缓存）

迁移路径（Skill Ladder）

如果你已掌握本文内容，建议下一步按以下顺序进阶：

动态图增量分区：学习如何只迁移高收益局部子图
查询感知分区：让查询日志参与分区权重建模
多层图存储协同：把分区策略和冷热分层、缓存策略一起优化
在线 A/B 验证框架：让分区策略具备可回滚、可比较、可审计能力

S — Summary（总结）

图分区直接决定图数据库的延迟上限和网络成本。
Edge-cut 与 Vertex-cut 没有绝对优劣，关键看业务负载形态。
METIS 的核心价值是“多层缩放 + 局部优化”，不是一次求全局最优。
生产可用分区策略必须有：目标函数、约束、监控、增量修复。

小结 / 结论

图数据库和关系数据库最大的工程差异之一，就是“跨边通信”会直接吞掉性能预算。
把图分区能力做扎实，你才能把查询性能从“偶尔可用”变成“长期可预测”。

参考与延伸阅读

METIS 官方与论文：Karypis & Kumar, Multilevel k-way Partitioning Scheme
PowerGraph（Vertex-cut 经典工程实践）
Pregel / Giraph 分布式图计算模型
Neo4j / JanusGraph 分片与查询实践资料

多语言参考实现（节选）

C++：计算 Edge-cut

#include <vector>
#include <utility>

int edgeCut(const std::vector<std::pair<int, int>>& edges,
            const std::vector<int>& part) {
    int cut = 0;
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        if (part[u] != part[v]) {
            cut += 1;
        }
    }
    return cut;
}

Go：计算分区负载

package main

func partitionSizes(part []int, k int) []int {
	sizes := make([]int, k)
	for _, partition := range part {
		sizes[partition]++
	}
	return sizes
}

JavaScript：计算复制因子

function replicationFactor(edgeParts, nodeCount) {
  const nodeToParts = Array.from({ length: nodeCount }, () => new Set());
  for (const item of edgeParts) {
    const [u, v, p] = item;
    nodeToParts[u].add(p);
    nodeToParts[v].add(p);
  }
  let total = 0;
  for (const parts of nodeToParts) total += Math.max(parts.size, 1);
  return total / nodeCount;
}

元信息

阅读时长：18~22 分钟
标签：图分区、Edge-cut、Vertex-cut、METIS
SEO 关键词：Graph Partitioning, Edge-cut, Vertex-cut, METIS, Query Latency
元描述：图分区如何影响查询延迟与网络通信量，并给出可运行示例与工程调优路径。

行动号召（CTA）

选一类你线上最慢的查询模板，统计其跨分区 hop 与网络字节，再对比一次分区优化前后 p95/p99。
你会很快看到：分区策略是图数据库性能工程的核心杠杆。

目标读者#

背景 / 动机#

核心概念#

快速掌握地图（60-120 秒）#

主心智模型（Master Mental Model）#

可行性与下界直觉#

问题建模与约束规模#

A — Algorithm（题目与算法）#

题目还原（工程化）#

输入输出#

示例（8 节点、2 分区）#

思路推导（从暴力到可用）#

朴素暴力#

关键观察#

方法选择#

C — Concepts（核心思想）#

1) Edge-cut vs Vertex-cut#

Edge-cut（节点唯一归属）#

Vertex-cut（边归属，节点可复制）#

2) METIS 的多层思想（必须懂）#

Deepening Focus（PDKH）#

概念 A：Edge-cut -> 延迟#

概念 B：METIS 多层流程#

实践指南 / 步骤#

决策准则（Selection Guide）#

可运行示例（Python）#

可运行示例 2：Vertex-cut 复制因子估算#

解释与原理（为什么这么做）#

Worked Example（Trace）#

正确性（Proof Sketch）#

复杂度与阈值#

常数因子与工程现实#

上线排障 Checklist（生产必备）#

指标计算口径（避免团队内口径不一致）#

回放压测模板（Python）#

E — Engineering（工程应用）#

场景 1：在线图查询（Edge-cut 主导）#

场景 2：超级节点图谱（Vertex-cut 更稳）#

场景 3：图分片与容量规划（METIS baseline + 增量迁移）#

R — Reflection（反思与深入）#

复杂度与工程代价#

替代方案与取舍#

量化对比（示例口径）#

常见误区#

反例（必须记住）#

常见问题与注意事项#

最佳实践与建议#

迁移路径（Skill Ladder）#

S — Summary（总结）#

小结 / 结论#

参考与延伸阅读#

多语言参考实现（节选）#

C++：计算 Edge-cut#

Go：计算分区负载#

JavaScript：计算复制因子#

元信息#

行动号召（CTA）#