去中心化联邦学习中的拜占庭节点放置优化

若攻击者只能破坏 m 个参与者，应选哪些节点，才能在有限训练轮数内最大化对诚实节点的影响。

• 场景：去中心化联邦学习（DFL）把聚合分散到通信图上。作者认为，恶意信息要经过多轮聚合才能到达远处节点，因此同样基数的两个拜占庭集合，对诚实网络的效果可以差很多（Figure 1）。
• 现有做法的不足：作者称，拜占庭节点常被随机选取、预先固定、临时放置，或按拓扑结构性质选取；虽已有战略放置工作，仍缺少按对去中心化训练的实际有限时间影响来选集合的通用准则。任意放置可能低估攻击能力，防御也可能只是因为节点位置差而看起来有效。
• 核心观察：有限轮数 T 内，毒化质量传播多快决定放置是否有效；后门影响只在离源若干跳内保留（Figure 2）。中心性按单节点打分且与训练轮数无关，最短路径分离也只是代理。
• 威胁模型：
  • 目标：外部攻击者在训练开始前选定 B ⊂ V，|B|=m，H ∩ B = ∅，最大化 T 轮后诚实节点漂移的期望（式 5）。
  • 知识：假设 (A2)，攻击者知道通信拓扑 G，每个拜占庭节点知道完整集合 B。
  • 能力：拜占庭节点偏离协议，做模型与数据投毒；扰动写成干净更新加上 αu。不能在训练开始后改拓扑（A1）。
  • 受害系统：n 个节点的无向连通图上的 DFL；主设定下诚实节点不用鲁棒聚合（A3），混合用 Metropolis 权重。
• 提出的方法：Byzantine Placement Influence（BPI），由 gossip 动态得到的集合级、有限时间暴露分数，以及 Greedy-BPI、Swap-BPI 两种不必执行训练即可找高影响放置的算法。

• 全连接或未优化放置：LEARN [9] 用全连接网络，节点结构等价，放置无关。SelfishAttack [10] 主要假设全连接，自私客户端是索引中最后 m 个；也考虑部分连接随机图，但不按拓扑位置选取。UBAR [3] 在由连接概率生成的随机图上随机加入拜占庭节点。BALANCE [5] 主要评测正则图，并考虑全连接、Erdős–Rényi、small-world、ring 和随机图，恶意节点在图实例中固定，没有拓扑感知的选择规则。
• 特定拓扑或临时放置：ClippedGossip [4] 评测 dumbbell、small-world、torus 和 ring；在 small-world 与 torus 上，先建诚实拓扑再把额外拜占庭工人接到随机选出的正则工人，其他实验则把拜占庭节点加在临时位置。其分析强调局部拜占庭邻居所占聚合权重，而不只看全局拜占庭节点数。Bhattacharya et al. [6] 在 small-world 与 scale-free 上，把拜占庭节点放在重连 Watts–Strogatz 边的关联节点以及 scale-free 的高度节点上，策略仍针对这些图族。CS+-RG [8] 在 Two Worlds 与 Erdős–Rényi 上分析拜占庭鲁棒 gossip：前者一整团为拜占庭，后者每个节点与四个恶意节点相邻。Table I 汇总了这些拓扑与放置。
• 战略放置：Syros et al. [11] 在点对点联邦学习中研究破坏结构上有影响的参与者对后门传播的作用，节点指标包括 degree、Effective Network Size、PageRank 和 clustering coefficient；作者称其准则是静态结构启发式，且专门在后门攻击中研究。Piaseczny et al. [7] 把放置写成协同对抗问题，提出 MaxSpAN-FL：用 BFS 影响区域并贪心减少重叠，以最短路径分离作为影响代理；评测限于一种基于 FGSM 的数据投毒和三类图（directed geometric、Erdős–Rényi、preferential-attachment）。
• 基线方法与基准：实验基线为 uniform random、Degree、Betweenness、Eigenvector centrality 和 MaxSpAN-FL。主实验拓扑为 Table II 的 Ring-of-Cliques、Dragonfly、Scale-Free、DC-SBM、Core-Periphery、Random-Geometric；数据为 MNIST。鲁棒聚合对照使用 BALANCE 评测中的 Ring 与 Erdős–Rényi 配置。

作者把本文定位为：不用节点中心性或最短路径分离作代理，而从 gossip 动态本身导出有限时间、集合级准则，使其能跨通信拓扑和投毒目标评价拜占庭集合。

在假设 (A1)–(A3) 下，作者把直接最大化 T 轮诚实漂移的期望，松弛为最大化只依赖混合矩阵 W、集合 B 和轮数 T 的 Byzantine Placement Influence（BPI），再用两种启发式近似求解。

问题设定与攻击者目标

• 网络：无向图 G=(V,E)，|V|=n。节点 i 优化本地目标 fi，持有参数 θ。诚实节点集 H 要最小化平均本地损失（式 1）。每轮本地产生更新后，按双随机 gossip 矩阵 W 做线性组合（式 2）；边权为 Metropolis–Hastings 形式（式 3）。连通图上，Wt 在 t→∞ 时趋于均匀矩阵。
• 扰动：拜占庭消息写成 θ̃i(t)=θi(t)+αu，∥u∥=1，α>0。作者把任意投毒分解成干净更新加对抗扰动，放置问题只关心扰动如何传播，不关心 α 和 u 如何产生。
• 经验漂移：δi(t) 是同一初始化、数据划分和随机性下，放置 B 相对 B=∅ 的模型偏差。诚实网络漂移 DH(t)(B) 是 H 上这些偏差的平均（式 4）。攻击者选 |B|=m 以最大化 E[DH(T)(B;ξ)]（式 5）。
• 为何不直接优化：对一个候选 B 要跑两次训练（干净与投毒）并跨随机种子估计期望；候选数为 C(n,m)，穷举对中等图就不可行。

BPI 分数

• 线性漂移：Δ̂(t+1)=WΔ̂(t)+α(W1B)⊗u（式 6）。初值 Δ̂(0)=0 时，T 轮闭式为 α 乘以各步 Wt1B 再乘 u（式 7）。
• 定义：ΦT(W,B)=(1/|H|) 1H⊤ (∑_{t=1}^{T} Wt) 1B（式 9）。作者解释为：诚实节点在 T 轮内对拜占庭源的平均总暴露，由 gossip 权重加权。它不需要训练，也不需要攻击方向 u 或本地数据分布。
• 与中心性的两点差别：BPI 是集合值的，会计入多个拜占庭源扩散的重叠；它是有限时间的，只计 T 轮内实际传到的质量。最大化式 8 的参考漂移被近似为最大化 ΦT（式 10）。作者写明两处间隙：线性化忽略 gossip 步之外的训练动态（本地 SGD 噪声、数据异质），并且按构造去掉了外生随机性 ξ。

Greedy-BPI 与 Swap-BPI

• Greedy-BPI（Algorithm 1）：从 B=∅ 开始，每步加入使 ΦT(W, B∪{r}) 最大的 r，直到 |B|=m。作者说明它只对当前部分解局部最优：边际增益依赖已选节点，且加入 r 会把 r 移出 H；早期选择可能把集合带进局部集中区域。不保证达到全局最优。
• 复杂度：迭代计算 Wt1B 时，单次 ΦT 为 O(T·|E|)；贪心为 O(m·n·T·|E|)。
• Swap-BPI（Algorithm 2）：以贪心解初始化，穷举所有 1-swap B̃=(B{b})∪{r}，接受 ΦT 提升最大的交换，直到不存在改进交换。作者称所得集合对所有 1-swap 局部最优；因每次接受严格增大 ΦT 且大小为 m 的放置有限，过程在有限步内终止。每轮交换代价为 O(m(n−m)·T·|E|)。
• 实验中的协议细节：拜占庭节点不聚合来自其他拜占庭节点的模型，以去掉拜占庭之间的自我强化。主实验诚实节点用 Metropolis 权重。

实验设置

• 任务与模型：除非另述，用 MNIST，训练样本 i.i.d. 分给参与者。每个客户端是两层 MLP：128 单元 ReLU 隐藏层加 10 单元输出，交叉熵，Adam，学习率 0.01，batch size 64，每通信轮一个本地 epoch。
• 主设定：n=50，m=5（10%），T=30。五个种子 {33, 99, 5, 42, 123}。DC-SBM、Core-Periphery、Random-Geometric、Scale-Free 按种子重生成，不连通则重采样直到连通；Dragonfly 与 Ring-of-Cliques 确定性，各种子相同。六类图平均度大约在 4 到 5 之间（Table II）。
• 放置基线：Greedy-BPI、Swap-BPI，对照 uniform random、Degree、Betweenness、Eigenvector centrality、MaxSpAN-FL。中心性取分数最高的 m 个节点。Random 对每个拓扑和种子无放回均匀抽一个大小为 m 的集合，表中每格对应五个独立放置。
• FixedBias：开局用种子采 u∼N(0,1) 并归一化到 ∥u∥2=1，全体拜占庭节点共用。节点首次攻击时记录 ∥θi,1∥2 并冻结；之后发布 θi,t+α∥θi,1∥2 u，主实验 α=64。
• BadNets：每个拜占庭参与者毒化本地训练数据的固定 20%；样本右下角盖 3×3 白块并改标为 y∗=0。恶意客户端本地优化与诚实客户端相同。
• 指标：RQ1 用式 4 的 DH(t)。无目标攻击用诚实节点准确率下降 ΔAt，主比较报告 T=30 的 ΔAT，单位为百分点，五种子上的均值 ± 95% Student-t 置信区间。后门用触发测试样本上的诚实节点 ASRH（式 12）。Figure 4 另用 5000 个均匀抽样的五节点放置看 ΦT 分布。

主结果

FixedBias 下最终诚实准确率下降 ΔA30（百分点，Table III，均值；± 为 95% Student-t 区间，五种子）：

表格较宽，可左右滑动

拓扑	Random	Degree	Eigenvector	MaxSpAN-FL	Greedy-BPI	Swap-BPI
Ring-of-Cliques	18.2±1.0	18.4±2.4	14.3±4.5	20.9±1.1	21.0±1.0	21.2±1.1
Dragonfly	19.8±1.3	19.9±1.6	18.5±2.3	20.7±1.2	20.9±1.1	20.8±1.0
Scale-Free	14.1±3.0	19.6±1.0	18.4±1.1	17.1±1.3	20.2±1.0	20.5±0.7
DC-SBM	16.1±0.5	20.6±1.8	19.7±2.4	16.5±3.8	21.3±1.5	21.3±1.6
Core-Periphery	13.1±3.7	19.3±0.8	18.8±0.9	17.1±2.4	20.6±0.9	20.8±0.9
Random-Geometric	15.2±1.5	15.3±1.9	9.1±4.5	18.4±2.4	20.8±0.6	20.6±0.8

Betweenness 的 ΔA30 均值：Ring-of-Cliques 18.4、Dragonfly 18.8、Scale-Free 19.4、DC-SBM 20.4、Core-Periphery 19.8、Random-Geometric 14.0（均来自 Table III）。

• 作者的解读：没有任何一种传统结构启发式在所有图族上都强。Degree 与 Betweenness 在 Scale-Free、DC-SBM、Core-Periphery 上接近 BPI，但在 Random-Geometric 上 Degree 为 15.3、Betweenness 为 14.0，而 Greedy-BPI 为 20.8；在 Ring-of-Cliques 和 Dragonfly 上相对 Random 优势也不大。MaxSpAN-FL 在 Ring-of-Cliques（20.9）、Dragonfly（20.7）、Random-Geometric（18.4）上较强，在 Scale-Free（17.1）、DC-SBM（16.5）、Core-Periphery（17.1）上较弱。Eigenvector 在 Ring-of-Cliques、Dragonfly、Random-Geometric 上是最弱策略。
• BPI：作者称 Greedy-BPI 或 Swap-BPI 在每个被评测拓扑上都取得最大均值下降。两者差距小：Greedy-BPI 在 Dragonfly 与 Random-Geometric 上均值最高，并在 DC-SBM 上与 Swap-BPI 并列；Swap-BPI 在 Ring-of-Cliques、Scale-Free、Core-Periphery 上略高。作者给出的拓扑平均下降为 20.8 与 20.9 个百分点。作者说明 Swap-BPI 保证的是 BPI 目标不降，不是下游准确率下降，因此两者出现小幅反转是预期的。
• Figure 4：5000 个均匀随机五节点放置的 ΦT 直方图上，作者称常规启发式的相对质量随图族变化很大；Greedy-BPI 与 Swap-BPI 在六个图族上都位于分布的高暴露端。坐标上可见的刻度包括 Ring-of-Cliques 约 2.1–2.7、Random-Geometric 约 1.6–2.8；n=50，T=30。

有限时间暴露与经验漂移（RQ1）

• 测了什么：Figure 3 在 50 节点 Ring-of-Cliques、FixedBias 上比较四个 ΦT 递增的放置：Minimum、Eigenvector、Random、Swap-BPI。图注给出 Φ30：Minimum 1.46、Eigenvector 2.36、Random 2.66、Swap-BPI 2.94。纵轴为 honest empirical drift DH(t)，横轴为 Round 0–30。
• 结果：作者称轨迹顺序与 BPI 相同。图中 Swap-BPI 曲线最高，Minimum 最低；纵轴刻度到 2500。作者称暴露越大，诚实模型漂移越快、越大；ΦT 最大的 Swap-BPI 在整个训练中经验漂移也最大。

跨攻击目标（RQ3，BadNets）

ASRH 均值（%，Table IV，五种子，± 为 95% Student-t 区间）：

表格较宽，可左右滑动

拓扑	Random	Degree	MaxSpAN-FL	Greedy-BPI	Swap-BPI
Ring-of-Cliques	38.6±6.8	37.0±6.6	42.7±0.9	44.6±1.6	44.0±2.5
Dragonfly	41.4±1.8	39.1±7.4	46.0±2.0	44.2±2.2	45.3±4.4
Scale-Free	19.7±8.1	49.6±2.1	34.3±7.4	56.1±9.5	59.5±10.4
DC-SBM	27.2±10.2	56.0±13.4	29.7±22.8	63.1±8.1	64.7±8.8
Core-Periphery	17.0±9.8	50.4±9.0	31.9±11.9	60.3±4.8	60.6±5.7
Random-Geometric	32.3±7.8	29.3±6.8	35.6±8.6	49.5±5.5	48.9±6.9

Betweenness / Eigenvector 的 ASRH 均值：Ring-of-Cliques 37.0 / 26.9；Dragonfly 31.6 / 32.6；Scale-Free 47.7 / 39.2；DC-SBM 53.4 / 47.1；Core-Periphery 54.2 / 46.6；Random-Geometric 19.6 / 14.7（Table IV）。

• 作者的解读：结构基线更不稳定。Degree 在 Scale-Free、DC-SBM、Core-Periphery 上为 49.6%、56.0%、50.4%，在 Random-Geometric 上降到 29.3%。Betweenness 在 Core-Periphery 为 54.2%、DC-SBM 为 53.4%，在 Dragonfly 为 31.6%、Random-Geometric 为 19.6%。MaxSpAN-FL 在 Dragonfly 最强（46.0%），在 Scale-Free、DC-SBM、Core-Periphery 为 34.3%、29.7%、31.9%。Eigenvector 从未最强，Random-Geometric 上仅 14.7%。Random 在 Scale-Free、DC-SBM、Core-Periphery 上为 19.7%、27.2%、17.0%。
• BPI：作者称 BPI 引导策略在六张图中的五张上平均 ASR 最大。唯一例外是 Dragonfly：MaxSpAN-FL 46.0%，Swap-BPI 45.3%，差 0.7 个百分点。作者认为 BadNets 并不由推导 BPI 时用的对齐加性扰动描述，同一跨拓扑行为说明 BPI 抓住的是通信过程本身的性质。Figure 5 被作者用来说明：后门不限于拜占庭节点的直接邻居，非邻居诚实节点在若干轮后也可以得到可观 ASR；因此不能只用度这类一跳量刻画放置。
• Figure 2：Ring 上 BadNet 传播示意。拜占庭源为红，诚实节点为白；节点旁数字是触发测试样本上的最终本地 ASR，颜色从低 ASR 的绿到高 ASR 的红。正文未给出这些 ASR 的具体数值。

非线性鲁棒聚合（RQ4）

• 设置：对照 BALANCE 评测所用的 Ring 与 Erdős–Rényi 配置及其拜占庭放置，并与 Swap-BPI 比较。n=20，m=4（20%）。BALANCE 参数 αBAL=0.25，κ=0.5，λ(t)=t/T，γ=1.5。节点 i 在邻居 j 满足距离阈值时接受该邻居；正文在阈值处被截断为系数 1.5，完整不等式后半未在可读文本中给出。另有 FixedBias、尺度因子 α=2.5、T=300 的实验，Figure 7 比较原始 BALANCE 放置与 Swap-BPI。
• 作者的解读：作者称 BALANCE 的观测鲁棒性强烈依赖于拜占庭节点位置；原始放置没有暴露这种最坏情形，而拓扑感知放置给出损害更大的配置。作者还称，在 BadNets 下 BALANCE 的 ASRH 可以高于普通平均，过滤邻居模型可能改变相对影响，使仍落在接受阈值内的恶意更新受益。对 α=2.5、T=300 的 FixedBias，作者称原始放置的下降有限，BPI 引导放置使准确率差距随训练变大，放置效应在非线性聚合下的无目标攻击中仍然存在。可读文本没有给出该实验的 ASRH 或 ΔAt 数值表。

其他消融与分析

• 论文未报告对 m、T、α 或图密度的系统消融表；主实验固定 n=50、m=5、T=30、α=64，RQ4 的 FixedBias 长视野使用 α=2.5、T=300、n=20、m=4。
• Greedy 与 Swap 的下游差距：作者称拓扑平均 ΔA 下降为 20.8 与 20.9 个百分点，并指出 BPI 是完整学习动态的代理，故小反转可预期。
• 负面结果：Table III 中 Eigenvector 在 Random-Geometric 的 ΔA30 为 9.1±4.5，低于 Random 的 15.2±1.5；Table IV 中 Dragonfly 上 MaxSpAN-FL（46.0%）高于 Swap-BPI（45.3%）和 Greedy-BPI（44.2%）。

作者指出的局限与后续方向

• 近似间隙（Section IV-C）：相对式 5，BPI 是线性化，忽略 gossip 步之外的训练动态（本地 SGD 噪声、数据异质），并按构造去掉外生随机性 ξ。
• 贪心非全局最优（Section V-A）：Greedy-BPI 不保证达到大小为 m 的全局最优 B∗；早期选择可能把集合带向图的局部集中区域。
• Swap 只对 BPI 而非下游指标最优（Section VI-B）：Swap-BPI 保证改进或保持的是 BPI 目标，不是下游准确率下降。
• 拓扑发现不在范围内（Justifying (A2)）：作者称，实践中重建网络的能力取决于具体实现，刻画这类发现机制与本文目标正交，因此留在工作范围之外。
• 不把某个鲁棒聚合写进 BPI（Justifying (A3)）：作者称，把特定鲁棒聚合器放进 BPI 会使放置准则变成依赖防御和攻击的，而不再只依赖拓扑；因此在线性聚合下推导 BPI，再在 Section VI-D 单独看推荐是否迁移到拜占庭鲁棒聚合。
• 静态图（Justifying (A1)）：作者采用训练期间不变的通信图，以便把拜占庭放置与拓扑操纵分开；若链路可在训练中变化或被攻击者修改，有效性会把两者混在一起。论文没有单独的 Limitations 或 Future Work 小节；Conclusion 在可读文本中只保留了开头一句，未看到作者列出的后续工作清单。

实验覆盖范围

• 主实验：MNIST、i.i.d.、两层 MLP；六类拓扑（Table II），n=50，m=5，T=30，五个种子；聚合为 Metropolis 权重；攻击为 FixedBias（α=64）与 BadNets（本地数据 20% 投毒，目标类 0）。
• 放置对照：Random、Degree、Betweenness、Eigenvector、MaxSpAN-FL、Greedy-BPI、Swap-BPI。Figure 4 对每种拓扑用 5000 个均匀随机的五节点放置作 ΦT 参照。
• RQ1：Figure 3 只报告 50 节点 Ring-of-Cliques 上四个放置的 DH(t) 轨迹，并标注 Φ30。
• RQ4：n=20、m=4 的 Ring 与 Erdős–Rényi，对照 BALANCE 原放置与 Swap-BPI；BALANCE 使用 αBAL=0.25、κ=0.5、λ(t)=t/T、γ=1.5。另有 FixedBias、α=2.5、T=300 与 Figure 7。论文未报告该组的数值表。
• 协议细节：拜占庭节点不聚合其他拜占庭节点的模型。指标为 DH、ΔA30 和 ASRH，置信区间为五种子上的 95% Student-t。论文未报告查询次数或墙钟时间；放置算法的代价以 O(m·n·T·|E|) 和每轮交换 O(m(n−m)·T·|E|) 给出。

作者把 DFL 中“破坏哪 m 个节点”写成攻击者在固定预算下的优化问题，并用 BPI 近似有限轮内诚实节点受到的拜占庭暴露。

• 问题：聚合沿通信图进行时，同样数量的拜占庭节点，位置不同则影响不同。随机、固定或只按中心性放置，作者认为可能低估攻击或使防御看起来过好。
• 方法：在拓扑固定、攻击者知道 G、诚实节点线性聚合的假设下，ΦT 是诚实节点对 ∑_{t=1}^{T} Wt 1B 的平均暴露。Greedy-BPI 逐步加入边际增益最大的节点，Swap-BPI 再做 1-swap，直到没有能提高 ΦT 的交换。分数不需要跑训练，也不需要攻击方向或数据分布。
• FixedBias：n=50、m=5、T=30、MNIST、α=64、五种子。Table III 中，Greedy-BPI 或 Swap-BPI 在六类图上的 ΔA30 均值都是该行最高（约 20.5–21.3 个百分点）；作者给出的拓扑平均为 20.8 与 20.9 个百分点。Eigenvector 在 Random-Geometric 上为 9.1，是该行最低。
• BadNets：Table IV 中 BPI 引导策略在五张图上 ASRH 均值最高，DC-SBM 上 Swap-BPI 为 64.7%；Dragonfly 上 MaxSpAN-FL 为 46.0%，高于 Swap-BPI 的 45.3%。
• 其他：Figure 3 中 Φ30 从 1.46 到 2.94 的四个放置，经验漂移顺序与 BPI 一致。作者称在 BALANCE 非线性聚合（n=20、m=4）下，换用 Swap-BPI 会改变表观鲁棒性，且 BadNets 的 ASRH 可以高于普通平均；该组没有数值表。
• 作者的结论：拜占庭放置是 DFL 威胁模型和鲁棒性评测中关键但建模不足的维度；固定或任意的攻击者配置会导致过于乐观的安全评估。