【CCS'24】Graphiti: Secure Graph Computation Made More Scalable

AI 辅助生成声明：本文由 AI 辅助生成，请自行判断内容是否准确，并建议回到原文确认关键公式、实验数值与结论。

论文信息

先用一张图看懂这篇论文的主线

把安全图计算从线性扫描改成常数轮消息传递

Graphiti 解决的是一个很现实的问题：图数据经常同时包含敏感拓扑和敏感属性。社交网络里谁和谁相连、金融交易网络里哪些账户之间有边、接触追踪里谁接触过谁，这些信息本身就可能比节点标签更敏感。传统图算法直接看明文图，隐私风险很大；直接用通用 MPC 跑图算法，又容易被图规模拖垮。

这篇论文的核心不是提出一个新的 BFS 或 PageRank 算法，而是重新设计安全图计算的执行框架。它继承 GraphSC 的 DAG-list 表达，把图里的顶点和边都放进一个长度为 N=|V|+|E| 的列表，然后用 message passing 的方式表达图算法：节点向边发送消息，节点从入边聚合消息，再更新节点状态。

GraphSC 的问题在于 Scatter/Gather 需要沿 DAG-list 做扫描；即便已有 round-optimized 版本，轮复杂度仍会以 \log N 形式依赖图规模，并且通信会出现 O(N\log N)。Graphiti 的关键观察是：许多图算法的 Gather 聚合是线性的，线性操作在 secret-sharing MPC 里可以非交互完成。因此，真正要优化的是列表顺序和数据分量的设计，让本来需要交互扫描的步骤变成加减法、前缀和与少量安全 shuffle。

Graphiti 把安全图计算的瓶颈从“逐项安全扫描 DAG-list”转成“少量预先设计好的列表重排 + 非交互线性操作”。这个转变让 message-passing 的轮复杂度不再依赖 N，也让 10^7 级别的 contact tracing benchmark 进入分钟级。

论文速览

一句话

Graphiti 是一个基于 MPC 的通用安全图计算框架，它通过 decoupled Scatter、vertex order、常数轮 Propagate/Gather 和 2PC-with-helper 安全 shuffle，把 GraphSC 的图规模相关轮复杂度降到与图规模无关，并在 contact tracing 任务上取得最高 1034x 的在线运行时间提升。

问题

隐私保护图分析要同时保护三类信息：图拓扑、节点数据和边数据。已有方案有两条常见路线：邻接矩阵路线轮数可以小，但对稀疏图有 O(|V|^2) 表示开销；GraphSC 一类 DAG-list 路线更适合稀疏图，但 Scatter/Gather 的扫描和列表顺序转换会成为 MPC 轮数与通信瓶颈。

论文用 contact tracing 作为代表场景。接触网络中节点是人，边是物理接触；从感染者节点做 BFS 可以找出阈值距离内的潜在风险人群。但边的存在本身就是隐私，不能把全局接触图交给某个中心方明文计算。

方法

方法主线：Graphiti 把 GraphSC 的 Scatter 拆成 Propagate + ApplyE。Propagate 只负责把节点数据复制到出边，ApplyE 再对边数据应用用户函数。这样，Propagate 可以被设计成只含加减法和列表重排的常数轮协议；如果算法需要复杂函数，复杂度只留在 ApplyE，而不再乘上 DAG-list 的扫描长度。

同时，Graphiti 引入 vertex order：所有顶点先按编号排好，所有边排在后面。每轮 message passing 从 vertex order 开始，经 source order 做 Propagate 和 ApplyE，再经 destination order 做 Gather，最后回到 vertex order 做 ApplyV。顺序切换依赖初始化阶段生成的映射和安全 shuffle。

结果

论文报告的核心结果有三组：

  • Scatter/Gather primitive：在 N=10^7 时，Graphiti 的 Scatter 在线时间约 3.72s，GraphSC linear 约 5278.41s，GraphSC RO 约 434.78s；运行时间最高提升 1418\times 和 116\times。
  • simple contact tracing：10-hop BFS 在 N=10^7 时，Graphiti 在线总时间约 101.90s，GraphSC linear 约 105464.60s，GraphSC RO 约 8716.64s；在线运行时间最高提升 1034\times 和 85\times。
  • secure shuffle：在 |T|=10^7 的 64-bit 向量上，Graphiti 的 shuffle 在线时间约 1710.27ms，预处理约 2418.10ms，相比适配到 2PC-with-helper 的已有 shuffle 在线运行最高提升 1.83\times。

读法建议

先读 GraphSC 的 DAG-list 与 Scatter/Gather，再读 Graphiti 的 Propagate、Gather 和 complete framework。实验部分重点看 Scatter/Gather primitive、simple contact tracing 和 shuffle 三组表格。不要只看 1034x 这个数字，还要同时看初始化成本、helper 假设、半诚实安全边界和线性聚合限制。

论文详读

为什么安全图计算卡在图规模上

图算法和普通表格计算不同。一个节点的状态更新通常依赖邻居，邻居又依赖边的方向和顺序。因此，安全执行图算法不仅要保护每个节点/边上的数据，还要保护边是否存在、边连接谁、入边/出边关系如何。

早期通用安全计算可以把图编码成邻接矩阵，再用 MPC 或 garbled circuit 计算。但稀疏图里 |E| 远小于 |V|^2，邻接矩阵会引入大量无用位置。GraphSC 改用 data augmented graph list，也就是 DAG-list，把顶点和边作为列表项存储。每个列表项包含类似 src、dst、isV、data 的字段：顶点项满足 src=dst=v, isV=1，边项满足 src=u, dst=v, isV=0。

这种表示对稀疏图更友好，但 message passing 要靠不同排序来完成：

  • source order：一个顶点紧跟着它的出边，方便 Scatter；
  • destination order：一个顶点的入边排在它前面，方便 Gather；
  • vertex order：Graphiti 新增，所有顶点先出现，边随后出现，方便用线性差分修正传播值。

GraphSC 的瓶颈在 Scatter/Gather 的扫描。安全扫描 DAG-list 时，协议要在每个条目上判断当前项是顶点还是边，并决定是“拿起”数据还是“放下/聚合”数据。这个过程在 MPC 里会产生多轮交互，导致轮复杂度随 N 增长。

Graphiti 的第一刀：把 Scatter 拆开

GraphSC 的 Scatter 可以抽象成：

\textnormal{for every } e(u,v)\in E,\quad e.\textnormal{data}=f(e.\textnormal{data},u.\textnormal{data}).

Graphiti 把这件事拆成两段：

\textnormal{Propagate:}\quad e.\textnormal{data}=e.\textnormal{data}\,\|\,u.\textnormal{data},
\textnormal{ApplyE:}\quad e.\textnormal{data}=f(e.\textnormal{data}).

这个拆分很重要。Propagate 只负责把源节点数据送到出边，不再执行用户函数 f。于是 Propagate 可以用非常规则的列表操作实现；如果 f 很复杂，它只在 ApplyE 里执行一次，而不会和对 N 个列表项的安全扫描纠缠在一起。

Graphiti Propagate：从 vertex order 到 source order 的线性传播修正

Graphiti 的 Propagate 关键在 vertex order。在 vertex order 中，顶点按编号连续排列。协议先把每个顶点要传播的值改成相邻顶点数据的差分。直觉上，如果顶点数据是累积台阶，那么差分以后再做前缀和，就能在 source order 里恢复出每条边应该拿到的源节点数据。

论文中 Algorithm 3 的核心形式可以概括为：

G[i].\textnormal{datar}=G[i].\textnormal{datas}-G[i-1].\textnormal{datas} \quad (i=|V|,\ldots,2),

然后把 DAG-list 切到 source order，再做线性累加：

G[i].\textnormal{datar}=\sum_{j=1}^{i}G[j].\textnormal{datar}-G[i].\textnormal{datas}.

这些都是加减法和求和。对 additive secret sharing 来说，它们可以非交互执行；交互成本主要留给顺序切换，也就是一次安全 shuffle。

Graphiti 的第二刀：把 Gather 也变成线性聚合

Gather 的目标是让每个节点从入边聚合数据：

v.\textnormal{data}=v.\textnormal{data}\,\|\,\bigoplus_{e(u,v)\in E}e.\textnormal{data}.

Graphiti 重点利用的是 \oplus 的线性性。许多图算法可以表示为线性聚合，例如 BFS、PageRank、histogram、matrix factorization 和一些 GNN message aggregation。只要 Gather 的聚合是线性的，MPC 里的求和就不需要交互。

Graphiti Gather：在 destination order 中聚合入边并回到 vertex order 修正

具体地，DAG-list 切到 destination order 后，每个节点的入边会排在节点前面。Graphiti 先对 datar 做累计和，得到一个包含“正确聚合值 + 多余前缀项”的中间量；再切回 vertex order，用相邻节点之间的差分去掉多余部分。这个思路和 Propagate 对称：先用便宜的线性扫描制造可修正的累计量，再用排序结构把不该有的前缀项减掉。

这一点解释了为什么 Graphiti 的设计不是单纯“换一个更快 shuffle”。shuffle 只是让列表在不同 order 间移动；真正的协议收益来自它把 Scatter/Gather 重新写成了适合 secret-sharing 的线性操作。

完整框架如何跑一轮 message passing

Graphiti 一轮 message passing 的 vertex/source/destination order 转换流程

一轮 Graphiti message passing 可以按下面理解：

  1. 从 vertex order 开始，运行 Propagate 的第一段线性差分。
  2. 通过安全 shuffle 切到 source order，运行 Propagate 的第二段线性传播。
  3. 对边运行 ApplyE，也就是用户定义的边函数。
  4. 切到 destination order，运行 Gather 的第一段线性聚合。
  5. 再切回 vertex order，运行 Gather 的修正步骤。
  6. 对节点运行 ApplyV，更新每个节点的新状态。

Graphiti 在初始化阶段会生成从 vertex order 到 source order、destination order 的映射。论文沿用 shuffle-then-sort 范式：先做安全 shuffle 隐藏真实排列，再做不安全排序得到公开映射。这样，后续多轮 message passing 可以复用这些映射，避免每轮重新做昂贵排序。

这里有一个边界条件需要注意：初始化本身不免费。论文 Table 12 报告，N=10^7 时初始化在线时间约 1727.07s、预处理约 624.09s，在线通信约 61.20GB、预处理通信约 23.91GB。所以 Graphiti 最适合的不是“一次性跑一小轮、马上丢弃”的任务，而是多轮 message passing 或大图场景，在那里初始化成本能被后续迭代摊薄。

安全 shuffle 为什么单独成为贡献

Graphiti 依赖安全 shuffle 来切换 DAG-list 的顺序。论文考虑的是 2-party with a helper 设置：两个计算方在线参与安全计算，另有一个不可腐化 helper 只在预处理阶段生成材料。Graphiti 以半诚实对手为安全模型。

2PC-with-helper 安全 shuffle 的预处理和在线阶段

论文把已有 2PC shuffle 协议适配到 helper setting 后作为 baseline，然后给出新的 shuffle 协议。新的协议在线轮数少一轮，通信大体相当。实验中，当输入向量大小为 10^7、元素为 64 bit 时，Graphiti shuffle 在线时间为 1710.27ms，预处理时间为 2418.10ms，在线通信约 1600MB，预处理通信约 1760MB。

这一节的价值不只在 Graphiti。shuffle 是很多隐私保护数据处理协议里的基础组件；因此这个 2PC-with-helper shuffle 可以作为独立 building block 使用。

Contact tracing 实验说明了什么

论文用两类 contact tracing 展示 Graphiti 的可扩展性。

simple contact tracing 对应普通 BFS：从感染者节点出发，迭代 \tau 轮 message passing，找出距离不超过 \tau 的节点。这里每轮只需要 Scatter、source-to-destination transition 和 Gather，最后一轮用 ApplyV 判断聚合值是否大于 0。

simple contact tracing 在不同图规模下的在线时间和通信对比

当 \tau=10、N=10^7 时：

  • GraphSC linear 总在线时间约 105464.60s；
  • GraphSC RO 总在线时间约 8716.64s；
  • Graphiti 总在线时间约 101.90s。

这个结果是全文最强的工程信号：Graphiti 不只是把某个微基准变快，而是让一个真实 message-passing 任务在千万级 DAG-list 上变成分钟级在线计算。

probabilistic contact tracing 更能体现 decoupled Scatter 的意义。它在传播感染时增加了边函数：

f_{\mathrm{AE}}(\textnormal{data})=\textnormal{data}\cdot \mathbf{1}\{r<p\}.

这个函数需要安全比较和乘法。如果沿 GraphSC 的扫描式 Scatter 做，复杂函数会和列表扫描耦合；Graphiti 则把传播和函数应用拆开，使 Propagate 仍保持与 N 无关的轮复杂度，而复杂度集中在 ApplyE。

probabilistic contact tracing 中 GraphSC、decoupled Scatter 和 Graphiti 的对比

论文报告，中间方案“只拆 Scatter，但不用 Graphiti 新 Propagate”已经相对 GraphSC 有明显提升；Graphiti 进一步相对该中间方案在 probabilistic contact tracing 中达到约 1000\times 和 27\times 的改进。这说明真正的收益来自两层：先把函数从传播里拆出来，再把传播本身改写成常数轮线性过程。

复杂度对比的真正含义

邻接矩阵、GraphSC、GraphSC RO 和 Graphiti 的轮数与通信复杂度对比

一轮 BFS message passing 的粗略复杂度可以这样看：

框架 轮复杂度 通信
邻接矩阵路线 O(1) O(|V|^2)
GraphSC linear O(N) O(N)
GraphSC RO O(\log N) O(N\log N)
Graphiti O(1) O(N)

这个表的重点是 Graphiti 同时拿到了两边的好处：它没有退回邻接矩阵的 O(|V|^2) 表示，也不保留 GraphSC 的图规模相关轮数。对于稀疏大图，O(N) 通信和 O(1) 轮数是它能扩展到 10^7 级别的根本原因。

不过，这个对比也说明了 Graphiti 的适用前提：它最适合能被 message passing 表达、且 Gather 聚合主要是线性的图算法。对于强非线性聚合、动态图持续变更、multigraph 或更复杂输入共享，论文把它们列为未来扩展方向，而不是已经完整解决。

批判性分析

值得肯定

第一，Graphiti 抓住了安全图计算里最实际的瓶颈：不是所有图算法都必须被通用电路吞掉，很多 message-passing 图算法可以靠列表顺序和线性操作来省掉交互轮数。这比单纯换一个 MPC backend 更有结构性价值。

第二，论文的贡献是可组合的。decoupled Scatter、vertex order、constant-round Propagate/Gather 和 secure shuffle 都可以分开理解；其中 shuffle 甚至是独立 building block。

第三，实验规模有说服力。N=10^7 的 contact tracing、scatter/gather primitive 和 shuffle benchmark 都直接对应论文声称的 scalability，而不是只给小图或理论复杂度。

关键假设

安全模型是半诚实，不是恶意安全。也就是说，各方按协议执行，但试图从中间消息推断额外信息。若参与方偏离协议、复用错误预处理材料、构造恶意输入或返回错误输出，本文的安全论证不覆盖。

helper 被假设为预处理阶段不可腐化。这个假设在许多 2PC-with-helper 工作中很常见，但部署时需要明确谁能担任 helper、helper 是否能被审计、预处理材料是否可复用，以及 helper 和计算方是否可能串谋。

Graphiti 的 Gather 依赖线性聚合。论文指出 BFS、PageRank、histogram、matrix factorization、部分 GNN evaluation 等都可以适配，但这不等于所有图算法都天然适配。如果核心聚合是非线性的，Graphiti 的优势可能会被 ApplyE/ApplyV 的安全函数成本抵消。

局限与风险

初始化成本不可忽略。N=10^7 时初始化在线时间达到 1727.07s，在线通信 61.20GB。这对一次性任务可能偏重；对多轮迭代任务则更容易摊薄。

输入阶段与真实多数据拥有者流程仍要细化。论文主要展示框架和 message-passing 阶段的可扩展性。现实中，不同数据拥有者如何对齐节点 ID、如何构造全局 DAG-list、如何处理重复边、动态图更新和缺失边证明，都会影响端到端系统。

benchmark 依赖 LAN 和具体实现设置。论文评测是在半诚实 2PC 外包计算设置和局域网环境下完成。广域网、跨组织协作、移动端参与或更高延迟网络下，shuffle 和 transition 的实际体验需要重新测。

复现判断

论文给出了主要协议思路、复杂度对比和关键实验数字。复现需要实现 DAG-list 表示、三种 order 的初始化映射、2PC-with-helper shuffle、Propagate/Gather 的线性操作、ApplyE/ApplyV 的安全函数，以及 GraphSC baseline。相关代码在https://github.com/Bhavishrg/Graphiti

最终判断

Graphiti 是一篇典型的“把抽象图算法结构和 MPC 成本模型对齐”的系统型密码论文。它最强的地方在于把 GraphSC 的扫描瓶颈拆开：用 vertex order 让传播/聚合变成线性可修正的列表运算，用安全 shuffle 管顺序切换，用 ApplyE/ApplyV 承载真正的用户函数。在适用的线性聚合 message-passing 图算法上，这个设计给出了比 GraphSC 明显更好的扩展性。

但它不是通用图隐私计算的终点。落地时必须重新评估 helper 信任、初始化摊销、半诚实安全边界、真实输入共享流程以及非线性图算法的成本。若这些前提成立，Graphiti 提供了一条很有工程价值的路线：在不暴露图拓扑和节点/边属性的情况下，把千万级稀疏图的安全 message passing 推到可运行的量级。