FedStruct：互连图上的联合解耦学习

Javad Aliakbari Johan Östman Alexandre Graell i Amat

摘要

我们解决了跨多个客户端分布的图结构数据的联邦学习的挑战。具体来说，我们关注互连子图的普遍场景，其中不同客户端之间的互连发挥着关键作用。我们针对这种情况提出了一个新颖的框架，名为 FedStruct，它利用了深层的结构依赖性。为了维护隐私，与现有方法不同，FedStruct 消除了在客户端之间共享或生成敏感节点特征或嵌入的必要性。相反，它利用显式的全局图结构信息来捕获节点间依赖关系。我们通过在六个半监督节点分类数据集上进行的实验结果验证了FedStruct的有效性，展示了在各种场景中接近集中式方法的性能，包括不同的数据分区方法、不同级别的标签可用性、和客户数量。

机器学习、ICML

gnn Short = GNN，long = 图神经网络 fl Short = FL，long = 联邦学习 ml Short = ML，long = 机器学习 dnn Short = DNN，long = 深度神经网络 sdsfl Short = SDSFL，long = 结构解耦子图联邦学习sfvshort=SFV，long=结构特征向量rsfvshort=RSFV，long=随机结构特征向量sfmshort=SFM，long=结构特征矩阵sflshort=SFL，long=子图联邦学习fedavgshort=FedAvg，long=联邦平均spm Short = SPM，long = 结构预测器模型 fpm Short = FPM，long = 特征预测器模型 gdv Short = GDV，long = 图基度向量 nfe Short = NFE，long = 节点特征嵌入 nse Short = NSE，long = 节点结构嵌入sem Short = SEM，long = 结构嵌入矩阵 fem Short = FEM，long = 特征嵌入矩阵 sel Short = SEL，long = 结构嵌入损失 dgcn Short = 解耦-GCN，long = 解耦-GCN mlp Short = MLP，long = multi层感知器

1简介

许多现实世界的数据都是图结构的，其中节点代表实体，边封装它们之间的关系或连接。例如，在能源网的需求预测中，节点代表发电站或变电站，边缘代表输电线路。同样，全球供应链中脆弱性的识别涉及作为个体公司或生产设施的节点和作为它们互连的边缘。另一个现实场景是反洗钱，节点象征账户，边缘对应交易，交易是严格保密的。

图神经网络（GNN）是一类为图结构数据量身定制的神经网络架构，在药物发现、社交网络或交通流建模等各个领域都取得了成功（Stokes 等人，2020；Fan 等）人，2019；蒋、罗，2022）。在实际的实际应用中，图数据通常自然地分布在多个客户端上，即全局图包含多个不重叠的子图。例如，能源网、全球供应链和反洗钱的例子分别涉及描绘区域能源网、不同公司的内部供应链和金融机构的内部交易网络的本地图。

对于这些和许多其他应用程序，由于隐私、法规或专有限制，客户端之间的数据共享是不可行的。在这种背景下，联邦学习（FL）（McMahan等人，2017）成为一种有前景的方法，可以在保护数据隐私的同时利用（全球）图结构数据。存在各种类型的联合图神经网络（Liu 等人，2022）。在这项工作中，我们的重点是最普遍的场景之一：子图 FL （Zhang 等人，2021），其中客户端持有不相交节点的子图，这些子图集成到一个全面的全局图中，并且各个节点之间具有互连。不同的局部子图。

训练 GNN 需要聚合相邻节点的特征表示，以生成更具表现力的嵌入（Kipf & Welling，2017；Hamilton 等人，2017；Veličković 等人，2018）。在子图 FL 中，一个关键的挑战是当一些相邻节点驻留在其他客户端时促进训练。人们提出了几种方法来应对这一挑战（Zhang 等人，2021；Peng 等人，2022；Chen 等人，2021；Du & Wu，2022；Lei 等人，2023）。所有这些方法的普遍问题在于它们依赖于与其他客户端共享原始或生成的节点特征或节点嵌入。在节点特征敏感的情况下，这会引起严重的隐私问题。此外，这些方法依赖于同质性，假设连接的节点之间具有很强的相似性。

我们的贡献。我们解决了全局图中节点分类的子图 FL 问题，该全局图中包含属于不同客户端的多个不重叠的子图。对于这种情况，我们提出了一种新颖的子图 FL 框架，名为 FedStruct，它利用了深层结构依赖性。为了保护隐私，FedStruct 将图结构和节点特征信息解耦：与现有方法不同，FedStruct 消除了共享（或生成）节点特征和/或嵌入的需要。相反，它利用全局图结构信息来捕获客户端之间的节点间依赖关系。源代码已公开。¹¹1https://anonymous.4open.science/r/FedStruct-B70D/

我们的主要贡献包括：

•

我们提出了针对不同实际场景定制的两个版本的 FedStruct：第一个版本适应具有敏感节点特征但不敏感且可公开访问的边的全局图，而另一个则解决本地子图边也存在的情况。机密的。对于后一种情况，FedStruct采用解耦图卷积网络（解耦GCN）（Liu等人，2020）作为底层GNN，限制客户端之间的信息交换。
•

我们引入了一种生成任务相关节点结构嵌入的方法 Hop2Vec，该方法能够适应图形，并与诸如 Node2Vec 等任务无关方法相比表现出有竞争力的性能（Grover & Leskovec，2016）和图基元计数（Pržulj，2007）。值得注意的是，与这些方法相比，Hop2Vec 不需要了解全局图。
•

我们通过集成解耦的 GCN 并利用全局图中的深层结构依赖关系来解决半监督学习场景。借助这些组件，FedStruct 在标记训练节点数量有限的场景中可以产生出色的性能。在高度半监督的环境中，它的表现明显优于 FedSage+。此外，FedStruct依赖于非局部邻居扩展和层间组合，这些技术通常用于处理异亲图（Zheng等人，2022）。据我们所知，FedStruct 是第一个能够处理异嗜图的子图 FL 框架。
•

我们在六个数据集上验证了 FedStruct 进行半监督节点分类的有效性，在具有不同数据分区方法、训练标签可用性和客户端数量的多个场景中展示了接近集中式方法的出色性能。

2相关工作

子图联邦学习。与我们关系最密切的作品有FedSage+ (Zhang 等人, 2021)、FedNI (Peng 等人, 2022)、FedCog （雷等人，2023），以及的作品（张等人，2022；刘等人，2023；张等人，2024；陈等人，2021；杜、吴，2022）。 FedSage+ (Zhang 等人, 2021)，第一种解决子图 FL 的方法，假设不知道跨子图互连。为了处理丢失的链接，它通过修复跨子图 $1$ 跳丢失的邻居来增强局部子图。具体来说，它依赖于强同质性假设来估计每个节点丢失的邻居的数量并生成这些邻居的特征。 FedNI (Peng 等人, 2022) 提出了类似的修复策略，利用生成对抗网络（GAN）来生成丢失的邻居及其特征，从而提高生成节点特征的质量。这种修复的想法已经扩展到适应具有不同节点类型的图（Zhang等人，2022）以及子图之间缺失的链接（Liu等人，2023）。为了利用更深层次的结构依赖关系，在 FedSage+ 的基础上，Zhang 等人 (2024) 为缺失的邻居生成节点嵌入，其中包含有关节点的 $k$ 的信息 -跳邻居。 FedCog (Lei 等人, 2023) 针对子图 FL 提出了一种不同的方法，将局部子图解耦为内部图和边界图表。相应地，底层GCN中的图卷积在两个解耦的图上分为两步。 FedCog 需要与相邻客户端共享本地节点的中间嵌入，在这种情况下，它相当于全局图上的图卷积。其他工作通过采样技术解决子图 FL 问题（Chen 等人，2021；Du & Wu，2022）。重要的是，所有这些先前的方法（Zhang 等人，2021；Peng 等人，2022；Lei 等人，2023；Zhang 等人，2022；Liu 等人，2023；Zhang 等人，2024；Chen 等人， 2021；Du & Wu，2022）要求在客户端之间共享原始或生成的节点特征或嵌入，并在同质假设下运行，但这在许多实际场景中并不成立。

GNN 中的结构信息。

最近的研究揭示了 GNN 捕获底层图结构的能力的局限性。为了克服这一障碍，一些作品明确地将结构信息纳入学习中，与标准 GNN 相比表现出优越的性能（Bouritsas 等人，2023；Tan 等人，2023）。为了提高 GNN 的表示能力，（Bouritsas 等人，2023）将结构信息引入到聚合函数中。作者证明，所提出的架构比标准 GNN 更具表现力。在 FL 环境中，（Tan 等人，2023）在客户之间分享通用结构知识，以提高本地绩效。据我们所知，还没有工作在子图 FL 中集成显式的结构信息。

3 预赛

图形符号。我们考虑一个由 $\mathcal{G}=(\mathcal{V},\mathcal{E},\boldsymbol{X},\boldsymbol{Y})$ 表示的图，其中 $\mathcal{V}$ 是 $n$ 节点的集合， $\mathcal{E}$ 边的集合， $\boldsymbol{X}\in\mathbb{R}^{n\times d}$ 节点特征矩阵， $\boldsymbol{Y}\in\mathbb{R}^{n\times c}$ 标签矩阵。对于每个节点 $v\in\mathcal{V}$ ，我们用 $\boldsymbol{x}_{v}\in\mathbb{R}^{d}$ 表示其相应的特征向量，并用 $\boldsymbol{y}_{v}\in\mathbb{R}^{c}$ 表示其相应的one-hot编码标签向量。我们考虑半监督学习场景，并用 $\tilde{\mathcal{V}}\subseteq\mathcal{V}$ 表示拥有标签的节点集。其余节点的标签设置为 $\boldsymbol{0}$ 。我们还用 $\mathcal{N}_{\mathcal{G}}(v)=\{u|(u,v)\in\mathcal{E}\}$ 表示节点 $v$ 的邻居。

对于给定矩阵 $\boldsymbol{M}$ ，令 $m_{uv}$ 为其第 $(u,v)$ 元素。整个图的拓扑信息由邻接矩阵 $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 描述，其中 $a_{uv}=1$ if $(u,v)\in\mathcal{E}$ 。我们将节点度数的对角矩阵定义为 $\boldsymbol{D}\in\mathbb{R}^{n\times n}$ ，其中 $d_{uu}=\sum_{v}{a_{uv}}$ 。此外，我们将 $\boldsymbol{\tilde{A}}=\boldsymbol{A}+\boldsymbol{I}$ 表示为自循环邻接矩阵，将 $\boldsymbol{\hat{A}}=\boldsymbol{\tilde{D}}^{-1}\boldsymbol{\tilde{A}}$ 表示为归一化自循环邻接矩阵，其中 $\tilde{d}_{uu}=\sum_{v\in\mathcal{V}}\tilde{a}_{uv}$ 。我们也表示 $[m]=\{1,\dots,m\}$ 。

图神经网络。现代 GNN 使用邻域聚合（传播步骤）和学习变换（变换步骤）来迭代更新每一层的节点表示。令 $\boldsymbol{h}_{v}^{(l)}$ 为节点 $v$ 在层 $l$ 的特征嵌入，其中 $\boldsymbol{h}_{v}^{(0)}=\boldsymbol{x}_{v}$ 。在 GNN 的 $l\in[L]$ 层，我们有

	$\displaystyle\boldsymbol{h}_{\mathcal{N}_{\mathcal{G}}(v)}^{(l)}$	$\displaystyle=\textsc{Aggregate}^{(l)}\bigg{(}\Big{\{}\boldsymbol{h}_{u}^{(l-1)},~{}\forall u\in\mathcal{N}_{\mathcal{G}}(v)\Big{\}}\bigg{)}$		(1)
	$\displaystyle\boldsymbol{h}_{v}^{(l)}$	$\displaystyle=\textsc{Update}^{(l)}\Big{(}\boldsymbol{h}_{v}^{(l-1)}\,,\,\boldsymbol{h}_{\mathcal{N}_{\mathcal{G}}(v)}^{(l)}\,,\boldsymbol{\Theta}^{(l)}\Big{)}\,,$		(2)

其中 $\boldsymbol{\Theta}^{(l)},\textsc{Aggregate}^{(l)}$ 和 $\textsc{Update}^{(l)}$ 分别表示与GNN层 $l$ 相关的权重矩阵、聚合函数和变换函数。

解耦图卷积网络。 GNN 的一个显着局限性是过度平滑（Li 等人，2018；Li 等人，2018；Li 等人，2020；Dong 等人，2021），这会导致应用多层时性能下降。过度平滑的特点是节点嵌入变得不可分割，这使得区分它们变得困难。最近的研究（Li 等人，2018；Li 等人，2020；Dong 等人，2021）将这种现象归因于每个 GNN 层内传播和转换步骤的交织。为了解决过度平滑的问题，一个众所周知的解决方案（以下称为解耦GCN)是将传播和转换步骤解耦（Liu等人，2020；Dong等人，2021）。令 $\boldsymbol{f}_{\boldsymbol{\theta}}(\boldsymbol{x}_{v})$ 为 MLP 网络，采用节点特征 $\boldsymbol{x}_{v}$ 和学习参数 $\boldsymbol{\theta}$ 并返回标签预测 $\hat{\boldsymbol{y}}^{(\text{MLP})}_{v}$ ，

\hat{\boldsymbol{y}}^{(\text{MLP})}_{v}=\boldsymbol{f}_{\boldsymbol{\theta}}(\boldsymbol{x}_{v})

(3)

解耦的 GCN 可以用模型来描述

\boldsymbol{H}^{(L)}=\boldsymbol{\bar{A}}\boldsymbol{F}_{\boldsymbol{\theta}}(\boldsymbol{X})\,,

(4)

其中 $\boldsymbol{\bar{A}}=\sum_{l=1}^{L}{\beta_{l}\boldsymbol{\hat{A}}^{l}}$ , $\boldsymbol{F}_{\boldsymbol{\theta}}(\boldsymbol{X})=||(\boldsymbol{f}_{\boldsymbol{\theta}}(\boldsymbol{x}_{v})^{\mathsf{T}}\quad\forall v\in\mathcal{V})$ , $||$ 表示串联操作，^T表示转置操作。我们将 $\boldsymbol{\bar{A}}$ 称为 $L$ -hop组合邻域邻接矩阵。它的元素反映了图中两个节点的接近程度， $\beta_{l}$ 确定了每一跳的贡献。参数 $\{\beta_{l}\}_{l=1}^{L}$ 可以手动设置，也可以在训练过程中学习。方程 (3) 和 (4) 分别对应于解耦 GCN 的变换和传播步骤。

4系统模型

我们考虑这样一种场景，其中数据根据全局图 $\mathcal{G}=(\mathcal{V},\mathcal{E},\boldsymbol{X},\boldsymbol{Y})$ 进行结构化。全局图分布在 $K$ 客户端之间，以便每个客户端拥有较小的本地子图。我们用 $\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{V}_{i}^{*},\mathcal{E}_{i},\mathcal{E}_{i}^{*},\boldsymbol{X}_{i},\boldsymbol{Y}_{i})$ 表示客户机 $i$ 的子图，其中 $\mathcal{V}_{i}\subseteq\mathcal{V}$ 是驻留在客户机 $i$ 中的 $n_{i}$ 节点的集合，称为 内部节点，客户机 $i$ 知道它们的特征。 $\mathcal{V}_{i}^{*}$ 是一组不驻留在客户端 $i$ 中但至少与 $\mathcal{V}_{i}$ 中的节点有一个连接的节点。我们将这些节点称为外部节点。客户端 $i$ 无权访问 $\mathcal{V}_{i}^{*}$ 中节点的功能。此外， $\mathcal{E}_{i}$ 表示客户端 $i$ 拥有的节点之间的边集（内部连接）， $\mathcal{E}_{i}^{*}$ 是客户端 $i$ 和其他客户端的节点（互连）， $\boldsymbol{X}_{i}\in\mathbb{R}^{n_{i}\times d}$ 节点特征矩阵，以及 $\boldsymbol{Y}_{i}\in\mathbb{R}^{n_{i}\times c}$ 子图 $\mathcal{G}_{i}$ 内节点的标签矩阵>，我们用 $\tilde{\mathcal{V}}_{i}$ 表示拥有标签的节点集。最后，与图 $\mathcal{G}$ 类似，我们用 $\mathcal{N}_{\mathcal{G}_{i}}(v)$ 、 $\boldsymbol{A}^{(i)}$ 和 $\boldsymbol{D}^{(i)}$ 表示局部邻居的集合，即局部邻接矩阵，以及子图 $\mathcal{G}_{i}$ 的局部对角矩阵。

4.1 节点嵌入

我们的重点是节点分类，目标是根据底层图数据对每个节点进行分类。更准确地说，我们假设每个客户端都采用 GNN 模型，该模型使用节点特征和子图连接为每个节点生成嵌入。形式上，对于客户端 $i$ ，得到的特征嵌入矩阵为

\displaystyle\boldsymbol{H}_{i}^{(L)}=\text{fGNN}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})\,,

(5)

其中fGNN是生成节点特征嵌入（NFE）的GNN模型， $L$ 是传播层数， $\boldsymbol{\theta}_{{\mathsf{f}}}$ 是fGNN的参数向量。还有 $\boldsymbol{H}_{i}^{(L)}=||\big{(}(\boldsymbol{h}_{v}^{(L)})^{\mathsf{T}}\quad\forall v\in\mathcal{V}_{i}\big{)}$ ，其中 $\boldsymbol{h}_{v}^{(L)}$ 是节点 $v$ 的 NFE。

4.2联邦学习

Refer to caption — 图1： FedStruct 框架的总体设计。

FL 问题可以形式化为学习模型参数，以最小化客户之间的总损失，

\boldsymbol{\theta}^{*}=\operatorname*{arg\,min}_{\boldsymbol{\theta}}\;\mathcal{L}(\boldsymbol{\theta})\,,

(6)

和

\displaystyle\mathcal{L}(\boldsymbol{\theta})=\frac{1}{|\tilde{\mathcal{V}}|}\sum_{i=1}^{K}{\mathcal{L}_{i}(\boldsymbol{\theta})},\quad\text{and}\quad\mathcal{L}_{i}(\boldsymbol{\theta})=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\mathrm{CE}(\boldsymbol{y}_{v},\hat{\boldsymbol{y}}_{v})}\,,

(7)

其中 $\mathrm{CE}$ 是真实标签 $\boldsymbol{y}_{v}$ 和预测标签 $\hat{\boldsymbol{y}}_{v}$ 之间的交叉熵损失函数。

模型 $\boldsymbol{\theta}$ 经过多个 epoch 迭代训练。在每个时期，客户端计算本地梯度 $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ 并将其发送到中央服务器。服务器通过梯度下降更新模型，

\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta}),\quad\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})=\frac{1}{|\tilde{\mathcal{V}}|}\sum_{i=1}^{K}{\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})}\,,

(8)

其中 $\lambda$ 是学习率。

5 FedStruct-A：具有全局图知识的子图 FL

在本节中，我们将介绍 FedStruct，这是一种新颖的子图 FL 框架，旨在利用客户端之间的节点间依赖关系，同时保护隐私。 FedStruct 的中心概念是利用有关整个图底层结构的显式信息，同时确保服务器和客户端都无法访问节点功能。具体来说，在本节中，我们介绍 FedStruct 的第一个版本，称为 FedStruct-A，它在服务器完全了解图连接的假设下运行。这种场景在智能电网和流行病预测等应用中经常遇到。重要的是，在 FedStruct-A 中，客户端仍然不知道其他客户端的本地图。在第 6 节中，我们提出了 FedStruct 的第二个版本，它假设服务器缺乏全局图连接的知识。图1说明了FedStruct框架。下面，我们描述FedStruct-A。

节点结构特点。我们提出的方法依赖于节点结构特征（NSF），它封装了节点的结构信息，例如节点度和局部邻域连接模式，以及位置信息，例如到节点中其他节点的距离。图形。对于每个节点 $v\in\mathcal{V}$ ，相应的 NSF $\boldsymbol{s}_{v}\in\mathbb{R}^{d_{\mathsf{s}}}$ 是边集 $\mathcal{E}$ 、 $\boldsymbol{s}_{v}=\boldsymbol{Q}_{\mathsf{NSF}}(\mathcal{E})$ 的函数。我们将包含所有 NSF 的矩阵定义为 $\boldsymbol{S}=||(\boldsymbol{s}_{v}^{\mathsf{T}},\quad\forall v\in\mathcal{V})$ 。

函数 $\boldsymbol{Q}_{\mathsf{NSF}}$ 可以通过各种节点嵌入算法来定义，例如one-hot度向量(Xu 等人, 2019; Cui 等人, 2022), gdv ( Pržulj，2007），或 Node2Vec （Grover & Leskovec，2016）。我们在附录A中描述了这些不同的节点嵌入。

节点结构嵌入。从 one-hot 度向量、GDV 和 Node2Vec 派生的 NSF 本质上是与任务无关的。要使用 NSF 进行标签预测，需要一个学习模型。为此，服务器采用 GNN（此处称为 sGNN），生成包含来自 NSF 和全局图连接的信息的节点结构嵌入 (NSE)。令 $L_{\mathsf{s}}$ 为sGNN的传播层数， $\boldsymbol{S}^{(L_{\mathsf{s}})}=||\big{(}(\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}){{}^{\mathsf{T}}}\quad\forall v\in\mathcal{V}\big{)}$ 为 $L_{\mathsf{s}}$ 层的NSE矩阵，其中 $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ 为节点 $v$ 。形式上， $\boldsymbol{S}^{(L_{\mathsf{s}})}$ 的获取方式为

\displaystyle\boldsymbol{S}^{(L_{\mathsf{s}})}=\text{sGNN}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})\,,

(9)

其中 $\boldsymbol{\theta}_{\mathsf{s}}$ 是sGNN的参数。

节点预测。创建 NSE 后，服务器将它们发送到相应的客户端。在每个客户端 $i\in[K]$ ，节点预测是基于NFE（在每个客户端本地计算，参见第4.1节）和NSE来执行的。为此，我们将它们传递给带有参数 $\boldsymbol{\Theta}_{\mathsf{c}}$ （从服务器获取）的全连接层，

	$\displaystyle\hat{\boldsymbol{y}}_{v}$	$\displaystyle=\mathrm{softmax}(\boldsymbol{\Theta}_{\mathsf{c}}^{\mathsf{T}}\big{(}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}\|\|\boldsymbol{h}_{v}^{(L)}))$		(10)
		$\displaystyle=\mathrm{softmax}\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}+(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)})\big{)}\quad\forall v\in\mathcal{V}_{i}\,,$

其中 $\boldsymbol{h}_{v}^{(L)}$ 和 $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ 分别基于(5)和(9)获得。我们用 $\boldsymbol{\theta}_{\mathsf{c}}$ 表示 $\boldsymbol{\Theta}_{\mathsf{c}}$ 的矢量化版本。从 (10) 开始，我们得到 $\boldsymbol{\theta}_{\mathsf{c}}=\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{s})}\,||\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{f})}$ 。

请注意，由于 NSE 是由服务器生成的，因此它们捕获全局图的所有连接的知识。因此，与仅依赖 NFE 的分类器相比，NSE 的使用预计将增强节点分类。

损失函数的梯度。我们使用随机梯度下降法优化 FedStruct-A, $\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})$ 的学习参数，求解 (6)-(7)，其中 $\hat{\boldsymbol{y}}_{v}$ 在 (10) 内。

定理1。

令 $\mathcal{L}_{i}(\boldsymbol{\theta})$ 、 $\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})$ 为客户端 $i$ 在 (7) 和 $\hat{\boldsymbol{y}}_{v}$ 中的本地训练损失在(10)中给出。梯度

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})=||\left(\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{j}}}\quad\forall j\in[|\boldsymbol{\theta}|]\right)\,

(11)

是（谁）给的

	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{s},j}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{\mathsf{s},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{s}}\|],$
	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{f},j}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\boldsymbol{h}_{v}^{(L)}}}{\partial{\theta_{\mathsf{f},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{f}}\|],$
	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{s})}\|],$
	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{f})}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}}{\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{f})}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{f})}\|]\,,$

其中 $\theta_{\cdot,j}$ 表示向量 $\boldsymbol{\theta}_{\cdot,j}$ 的第 $j$ 条目。

证明。

请参阅附录B。 ∎

请注意，客户端 $i$ 无法直接计算 $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ ，因为计算 $\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{\mathsf{s},j}}}$ 需要了解全局图连接。因此，服务器必须为所有 $v\in\tilde{\mathcal{V}}_{i}$ 提供 $\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{\mathsf{s},j}}}$ 以及 $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ 。 FedStruct-A 框架在算法 1 中进行了描述。

算法1 FedStruct-A 算法

0: Global graph

\mathcal{G}

, sGNN and fGNN models, NSF generator function

\boldsymbol{Q}_{\mathsf{NSF}}

K

clients with respective subgraphs

\{\mathcal{G}_{i}\}_{i=1}^{K}

, model parameters

\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})

\boldsymbol{S}\leftarrow\boldsymbol{Q}_{\text{NSF}}(\mathcal{E})

for e=1 to Epochs do

\boldsymbol{S}^{(L_{\mathsf{s}})}\leftarrow\text{sGNN}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})

for i=1 to K do

Client

i

collects

\boldsymbol{\theta}

from the server

Client

i

collects

\{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})},\forall v\in\tilde{\mathcal{V}}_{i}\}

from the server

Client

i

collects

\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{\theta}_{\mathsf{s}}}},\forall v\in\tilde{\mathcal{V}}_{i}\}

from the server

\boldsymbol{H}_{i}^{(L)}=\text{fGNN}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})

for

v\in\tilde{\mathcal{V}}_{i}

\hat{\boldsymbol{y}}_{v}=\mathrm{softmax}(\boldsymbol{\Theta}_{\mathsf{c}}^{\mathsf{T}}.(\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}||\boldsymbol{h}_{v}^{(L)}))

end for

Calculate

\mathcal{L}_{i}(\boldsymbol{\theta})

based on (7)

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})

from 1

Send

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})

to the server

end for

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})

based on (8)

\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})

end for

5.1任务相关节点结构特征向量

理想情况下，NSF 应该增强节点的独特性，同时展示有利于节点分类的可识别模式。对于以远程依赖为特征的图，NSF 需要捕获直接邻居之外的结构信息。此外，NSF 最好应该是任务相关的。与 one-hot 度向量相比，GDV 和 Node2Vec 捕获更长范围的依赖关系。然而，它们仍然与任务无关，并且取决于同质性假设（参见附录A)。为了克服这些缺点，我们引入了一种生成 NSF 的新方法，称为 Hop2Vec，其设计为任务依赖型且适用于异嗜图。

Hop2Vec 构建 NSF 如下。首先，用随机向量初始化 NSF，然后在 FedStruct 的训练期间从图结构中学习它们。因此，NSF 本质上是依赖于任务的，旨在最大限度地减少错误分类。为了优化 NSF，我们修改目标函数 (7) 以取决于矩阵 $\boldsymbol{S}$ ，即 $\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})$ 。 NSF 通过求解来优化

\boldsymbol{S}^{*}=\operatorname*{arg\,min}_{\boldsymbol{S}}{\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})}\,.

(12)

通过梯度下降进行优化，

\boldsymbol{S}\leftarrow\boldsymbol{S}-\lambda_{\mathsf{s}}\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})\,,

(13)

其中 $\lambda_{\mathsf{s}}$ 表示学习率。

定理2。

让 $\mathcal{L}_{i}(\boldsymbol{\theta})$ 表示客户端 $i$ 的 (7) 中的本地训练损失， $\boldsymbol{S}$ 表示由 Hop2Vec 方法。另外，令 $\hat{\boldsymbol{y}}_{v}$ 与 (10) 相同。梯度

\displaystyle\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta}_{i},\boldsymbol{S})=||\big{(}(\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S}))^{\mathsf{T}}\quad\forall q\in\mathcal{V}\big{)}

(14)

是（谁）给的

\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})=\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})\quad\forall q\in\mathcal{V}\,.

(15)

证明。

请参阅附录C。 ∎

要计算 (15)，客户端 $i$ 必须从服务器接收 $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}},\,\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}$ 。具有 Hop2Vec 的 FedStruct-A 框架在附录D<中的算法 2中描述。 /t6>。

5.2半监督学习

在节点数量有限的半监督学习场景中，GNN 必须采用更多层来有效捕获更远距离的依赖关系（刘等人，2020）。然而，当层数很大时，标准 GNN 会出现过度平滑的问题。为了解决这个问题，特别是在半监督学习任务中，FedStruct-A 采用解耦的 GCN 作为底层 GNN。

对于客户端 $i\in[K]$ 和节点 $v\in\mathcal{V}_{i}$ ，令 $\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{v})$ 和 $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{v})$ 为负责利用节点特征和节点结构特征的MLP网络，分别。为了在 FedStruct 中使用解耦的 GCN，我们使用 (4) 将 sGNN 和 fGNN 模型定义为

	$\displaystyle\boldsymbol{H}_{i}^{(L)}$	$\displaystyle=\text{fGNN}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})=\boldsymbol{\bar{A}}^{(i)}\;\boldsymbol{F}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i})$		(16)
	$\displaystyle\boldsymbol{S}^{(L_{\mathsf{s}})}$	$\displaystyle=\text{sGNN}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})=\boldsymbol{\bar{A}}\;\boldsymbol{G}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S})$		(17)

其中， $\boldsymbol{F}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i})=||(\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})^{\mathsf{T}}\;\forall u\in\mathcal{V}_{i})$ 、 $\boldsymbol{G}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S})=||(\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})^{\mathsf{T}}\;\forall u\in\mathcal{V})$ 和 $\boldsymbol{\bar{A}}$ 和 $\boldsymbol{\bar{A}}^{(i)}$ 分别是图 $\mathcal{G}$ 和 $\mathcal{G}_{i}$ 的 $L$ 跳组合邻接矩阵。

6 FedStruct-B：不了解全局图的子图 FL

为了预测节点标签，FedStruct 利用节点特征和结构特征。在 FedStruct-A 中，服务器利用其全局图连接知识来利用结构特征。然而，在许多情况下，服务器不具备这些知识，导致其无法利用结构特征。为了解决这个限制，我们引入了 FedStruct-B，它消除了对此类全局知识的需求。在这种情况下，为了让学习框架利用客户端之间的节点间依赖关系，必须在每个客户端本地生成结构特征。这需要客户端有选择地与其他客户端共享特定的本地图结构信息。为了保护隐私，这种信息共享必须谨慎进行。下面，我们描述 FedStruct-B 的不同组件。

节点结构特征向量。值得注意的是，Node2Vec 和 GDV 以及其他众所周知的方法需要了解节点的 $L$ 跳邻域。因此，在服务器缺乏全局图连接知识的情况下，无法使用这些方法。相反，我们的方法 Hop2Vec 不需要了解 $L$ 跳邻域信息。我们在FedStruct-B中使用Hop2Vec来生成NSF。

解耦 GCN。对于服务器缺乏全局图知识的场景，需要在本地生成NSE。不幸的是，标准 GNN 不适合本地生成 NSE。每个 GNN 层中的传播和转换步骤交织在一起带来了挑战。具体来说，对于要计算 GNN 给定层的新嵌入的客户端，它们需要驻留在其他客户端中的相邻节点的先前层的嵌入。这将允许客户推断全局图结构。为了解决这个隐私问题，FedStruct-B 采用了解耦的 GCN。解耦的 GCN 将传播和转换步骤分开。传播步骤不涉及学习，可以在训练之前计算所有传播层。这使我们能够查明其他客户端训练所需的信息，并将信息交换限制在这些细节上，从而与标准 GNN 相比，最大限度地减少与每个客户端的信息交换，如下所示。

结构信息共享。对于给定的客户端 $i$ ，训练 FedStruct 涉及计算 $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ 和预测节点标签 $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$ 。我们的目标是设计一种机制，允许在不依赖全局图的完整知识的情况下进行 FedStruct 的本地训练。下面，我们展示了对于利用分类交叉熵损失函数的节点分类任务，解耦 GCN 的结合使得能够在全局图知识有限的情况下进行 FedStruct 的训练。为此，我们用 $\boldsymbol{\bar{A}}^{[i]}=||(\boldsymbol{\bar{a}}_{v}^{\mathsf{T}},\quad\forall v\in\tilde{\mathcal{V}}_{i})$ 表示客户端 $i$ 的 $\boldsymbol{\bar{A}}$ 本地分区，其中 $\boldsymbol{\bar{a}}_{v}=||(\bar{a}_{vu},\quad\forall u\in\mathcal{V})$ 。

定理3。

要使用解耦的 GCN 获取 (10) 中的 $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$ ，客户端 $i$ 只需外部输入 $\boldsymbol{\bar{A}}^{[i]}$ 和 $\boldsymbol{S}$ 。

证明。

对于节点 $v\in\tilde{\mathcal{V}}_{i}$ ，展开 (16) 和 (17) 会导致

	$\displaystyle\boldsymbol{h}_{v}^{(L)}$	$\displaystyle=\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}$		(18)
	$\displaystyle\boldsymbol{s}_{v}^{(L_{s})}$	$\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}\,,$		(19)

其中 $\boldsymbol{h}_{v}^{(L)}$ 和 $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ 分别表示节点 $v$ 的NFE和NSE。在 (10) 中使用 (18) 和 (19) 会导致

\displaystyle\hat{\boldsymbol{y}}_{v}

\displaystyle=\mathrm{softmax}\Big{(}\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,

(20)

其中 (20) 来自将 $\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})}$ 和 $\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}$ 分别集成到 $\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})$ 和 $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$ 中。方程(20)仅取决于 $\boldsymbol{\bar{A}}^{[i]}$ 和 $\boldsymbol{S}$ ，从而得出证明。 ∎

定理4.

令 $\mathcal{L}_{i}(\boldsymbol{\theta})$ 为(7)中定义的局部训练损失，令 $\hat{\boldsymbol{y}}_{v}$ 与(20)中定义的一样。局部梯度

\displaystyle\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})=||\left(\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{j}}}\quad\forall j\in[|\boldsymbol{\theta}|]\right)

是（谁）给的

	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{s},j}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i},u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}$		(21)
	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{f},j}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i},u\in\mathcal{V}_{i}}{\bar{a}^{(i)}_{vu}\frac{\partial{\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}}{\partial{\theta_{\mathsf{f},j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}.$		(22)

证明。

请参阅附录E。 ∎

定理5。

对于客户端 $i$ ,FedStruct-b的训练，即计算 $\{\hat{\boldsymbol{y}}_{v},\forall v\in\tilde{\mathcal{V}}_{i}\}$ 和 $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})$ ，只需要本地分区 $\boldsymbol{\bar{A}}^{[i]}$ 和 $\boldsymbol{S}$ 。

证明。

通过结合定理 3 和 4 得出结论。 ∎

根据定理 5，不需要了解全局邻接矩阵即可预测节点的标签或计算给定客户端的梯度。相反，只需要全局 $L$ 跳组合邻接矩阵 $\boldsymbol{\bar{A}}^{[i]}$ 的局部分区来操作 FedStruct-b。客户端必须协同计算 $\boldsymbol{\bar{A}}^{[i]}$ 。在附录训练G中，我们提供了一种算法，可以在训练开始之前获取 $\boldsymbol{\bar{A}}^{[i]}$ ，而无需获取有关全局的任何其他信息图形。而且，由于图同构， $\boldsymbol{\bar{A}}^{[i]}$ 不能用来唯一确定其他客户端的邻接矩阵。 FedStruct-B 框架在附录H中的算法4中描述。

使用任务相关的节点结构特征向量。使用Hop2Vec，我们注意到 $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$ 的学习等同于 $\boldsymbol{s}_{u}$ 的学习。将 NSF 通过 sGNN 的目的是生成任务相关的 NSE。由于 Hop2Vec 生成的 NSF 是在训练过程中学习的，因此它们已经是任务相关的。因此，我们不需要考虑sGNN的变换步骤 $\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})$ ，而只需要考虑传播步骤。这是基于 MLP 参数 $\boldsymbol{\theta}_{\mathsf{s}}$ 和结构特征 $\boldsymbol{s}_{u}$ 都需要优化的事实。因此，使用Hop2Vec，(20)可以重写为

\hat{\boldsymbol{y}}_{v}=\mathrm{softmax}\Big{(}\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{s}_{u}}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,.

(23)

定理 6.

令 $\mathcal{L}_{i}(\boldsymbol{\theta})$ 表示客户端 $i$ 中 (7) 中的本地训练损失， $\boldsymbol{S}=||(\boldsymbol{s}_{q}^{\mathsf{T}},\quad\forall q\in\mathcal{V})$ 表示包含 Hop2Vec。另外，令 $\hat{\boldsymbol{y}}_{v}$ 如(23)中那样。梯度 $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ 由下式给出

\displaystyle\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\boldsymbol{\bar{a}}_{v}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})^{\mathsf{T}}}\,.

(24)

证明。

请参阅附录F。 ∎

要计算 (24)，客户端 $i$ 只需要 $\boldsymbol{\bar{A}}^{[i]}$ 。具有 Hop2Vec 的 FedStruct-B 框架在附录中的算法 5中描述 I。

7评估

表格1：具有随机分区的各种子图 FL 方法的节点分类精度。节点被分为train-val-test为10%-10%-80%。对于每种方法，显示

10

独立运行的平均值和标准差。

	Cora			Citeseer			Pubmed
Central GNN	82.06 $\pm$ 1.09			69.17 $\pm$ 0.90			87.71 $\pm$ 0.34
	5 clients	10 clients	20 clients	5 clients	10 clients	20 clients	5 clients	10 clients	20 clients
FL GNN	68.47 $\pm$ 1.12	65.06 $\pm$ 1.92	64.59 $\pm$ 1.56	64.92 $\pm$ 1.84	63.47 $\pm$ 1.29	63.78 $\pm$ 1.46	86.14 $\pm$ 0.38	85.91 $\pm$ 0.42	85.31 $\pm$ 0.56
FedSage+	68.42 $\pm$ 1.73	66.32 $\pm$ 1.81	64.19 $\pm$ 1.54	64.65 $\pm$ 1.28	63.37 $\pm$ 1.45	62.69 $\pm$ 1.35	85.89 $\pm$ 0.39	85.37 $\pm$ 0.55	85.14 $\pm$ 0.28
FedSage-true	81.74 $\pm$ 1.29	80.85 $\pm$ 1.55	79.96 $\pm$ 1.27	69.52 $\pm$ 1.57	68.91 $\pm$ 1.30	69.26 $\pm$ 1.49	85.40 $\pm$ 0.77	85.66 $\pm$ 0.37	85.10 $\pm$ 0.80
FedStruct (Deg)	71.87 $\pm$ 2.52	68.64 $\pm$ 1.51	65.06 $\pm$ 2.12	66.33 $\pm$ 1.68	63.81 $\pm$ 1.31	61.50 $\pm$ 1.52	84.92 $\pm$ 0.53	85.09 $\pm$ 0.48	85.40 $\pm$ 0.52
FedStruct (GDV)	73.81 $\pm$ 1.99	72.19 $\pm$ 1.62	70.32 $\pm$ 1.64	66.56 $\pm$ 1.81	64.44 $\pm$ 0.84	62.89 $\pm$ 1.47	85.60 $\pm$ 0.44	86.12 $\pm$ 0.56	86.01 $\pm$ 0.49
FedStruct (N2V)	80.37 $\pm$ 1.13	80.68 $\pm$ 1.77	79.80 $\pm$ 1.36	67.84 $\pm$ 1.51	66.28 $\pm$ 1.04	65.33 $\pm$ 1.28	86.52 $\pm$ 0.43	87.09 $\pm$ 0.44	86.92 $\pm$ 0.52
FedStruct (H2V)	79.53 $\pm$ 1.52	80.28 $\pm$ 1.44	79.39 $\pm$ 0.90	67.33 $\pm$ 1.43	66.29 $\pm$ 0.87	65.24 $\pm$ 1.49	86.07 $\pm$ 0.35	86.65 $\pm$ 0.53	86.24 $\pm$ 0.56
Local GNN	49.60 $\pm$ 2.13	39.23 $\pm$ 1.21	32.25 $\pm$ 1.68	50.77 $\pm$ 1.78	38.99 $\pm$ 1.60	32.40 $\pm$ 1.57	82.58 $\pm$ 0.28	79.10 $\pm$ 0.54	73.31 $\pm$ 0.41

	Chameleon			Amazon Photo			Amazon Ratings
Central GNN	54.43 $\pm$ 2.44			93.99 $\pm$ 0.48			41.32 $\pm$ 1.03
	5 clients	10 clients	20 clients	5 clients	10 clients	20 clients	5 clients	10 clients	20 clients
FL GNN	39.98 $\pm$ 1.56	35.70 $\pm$ 2.29	34.72 $\pm$ 1.72	92.70 $\pm$ 0.28	90.74 $\pm$ 0.58	89.27 $\pm$ 0.55	37.11 $\pm$ 0.47	36.25 $\pm$ 0.46	36.22 $\pm$ 0.62
FedSage+	39.43 $\pm$ 1.65	35.48 $\pm$ 1.23	34.33 $\pm$ 1.49	92.57 $\pm$ 0.49	90.80 $\pm$ 0.48	89.39 $\pm$ 0.58	36.82 $\pm$ 0.53	36.18 $\pm$ 0.77	36.09 $\pm$ 0.33
FedSage-true	52.66 $\pm$ 1.73	50.75 $\pm$ 2.82	49.35 $\pm$ 1.54	92.94 $\pm$ 3.84	90.95 $\pm$ 5.27	92.60 $\pm$ 2.35	40.44 $\pm$ 0.92	39.98 $\pm$ 0.68	39.93 $\pm$ 0.55
FedStruct (Deg)	44.16 $\pm$ 1.82	41.01 $\pm$ 1.26	40.90 $\pm$ 1.83	90.83 $\pm$ 0.41	89.59 $\pm$ 0.88	88.39 $\pm$ 1.21	39.32 $\pm$ 0.49	39.08 $\pm$ 0.57	38.65 $\pm$ 0.61
FedStruct (GDV)	42.48 $\pm$ 2.17	39.54 $\pm$ 2.46	39.14 $\pm$ 2.35	90.93 $\pm$ 0.37	90.51 $\pm$ 0.45	89.23 $\pm$ 1.17	39.92 $\pm$ 0.61	39.53 $\pm$ 0.87	39.51 $\pm$ 0.36
FedStruct (N2v)	46.35 $\pm$ 1.83	43.49 $\pm$ 1.93	44.53 $\pm$ 2.05	91.62 $\pm$ 0.41	91.19 $\pm$ 1.05	90.06 $\pm$ 0.86	41.45 $\pm$ 0.43	41.43 $\pm$ 0.52	41.77 $\pm$ 0.44
FedStruct (H2V)	53.06 $\pm$ 1.28	52.36 $\pm$ 2.63	52.76 $\pm$ 1.69	91.99 $\pm$ 0.39	91.83 $\pm$ 0.39	90.41 $\pm$ 1.32	41.18 $\pm$ 0.31	41.23 $\pm$ 0.38	41.16 $\pm$ 0.52
Local GNN	35.52 $\pm$ 1.65	28.51 $\pm$ 1.59	24.89 $\pm$ 2.19	88.19 $\pm$ 0.61	79.66 $\pm$ 1.15	63.16 $\pm$ 0.98	34.52 $\pm$ 0.84	32.81 $\pm$ 0.46	31.29 $\pm$ 0.52

为了证明 FedStruct 的性能和多功能性，我们在与节点分类相关的六个数据集上进行了实验，这些数据集具有不同的 i) 标记训练节点数量、ii) 客户端数量和 iii) 数据分区方法。客户端之间的互连很大程度上取决于后者。考虑的数据集是：Cora (Sen 等人, 2008)、Citeseer (Sen 等人, 2008)、Pubmed (Namata 等人, 2012) t2>、变色龙（Pei 等人，2020）、亚马逊照片（Shchur 等人，2018）和亚马逊评级（Platonov 等人，2023）. 附录J给出了不同数据集的统计数据及其边同质率，测量连接相似标签的节点的边的比例，范围在0（异质）到1（同质）之间（朱等人，2020）。

实验设置。我们专注于强半监督设置，其中数据被分为训练集、验证集和测试集，其中包含节点的 $10\%$ 、 $10\%$ 和 $80\%$ ，分别。我们人为地将数据集划分为互连的子图，然后将其分配给客户端。在这里，我们考虑数据集的随机划分，它将节点均匀地随机分配给子图，从而导致子图之间存在显着的互连性。这种划分与交易网络等相关，其中账户不一定优先与同一子图中的节点进行交互。随机分区构成了最具挑战性的场景，因为互连的数量很高，因此学习方案必须利用此类连接。在附录K中，我们还提供了使用Louvain算法的其他两个分区的详细信息和结果，如（Zhang等人，2021）和K-means算法（雷等人，2023）。

为了提供上限和下限基准，所有实验还针对利用全局图的集中设置和仅使用局部子图的局部设置进行。在附录 K 中，我们还给出了 MLP 方法的结果，以强调利用数据中的空间结构的重要性。对于 GNN，我们依赖于具有两层或三层的 GraphSage (Hamilton 等人，2017)，具体取决于数据集。我们进一步将 FedStruct 与不利用互连的普通 FL (FL GNN) 和 FedSage+ (Zhang 等人, 2021 ）。 FedSage+ 不知道丢失的邻居属于哪个客户端。为了进行同类比较，我们提供了 FedSage+（和 FedNI)的版本，表示为 FedSage-true，其中此信息是已知的缺失的一跳邻居的修复被它们的真实特征所取代。此方法提供了 FedSage+ 和 FedNI 性能的上限。对于与 FedStruct 相关的结果，我们考虑四种不同的方法来创建 NSF：one-hot 度向量 (Deg)、GDV、Node2Vec (N2V)，以及 5.1 节中提出的任务相关方法 Hop2Vec (H2V)，详情参见附录A。

整体表现。在表1中，我们报告了 $10$ 独立运行中随机分区在不同数据集上的节点分类准确性。中央 GNN 和本地 GNN 之间的准确度差异让我们深入了解利用 FL 的潜在收益。例如，在具有 $10$ 客户端的 Cora 和 Amazon Ratings 数据集上，差距分别为 $43.78\%$ 和 $9.05\%$ 。对于这些数据集，FL GNN 分别缩小了与 $16.94\%$ 和 $5.24\%$ 的差距。对于所有数据集，FedSage+ 的性能与 FL GNN 类似。结合修正节点的真实节点功能 (FedSage-true) 使性能接近集中式方法。但请注意，访问缺失邻居中的节点特征完全侵犯了隐私。

对于 FedStruct，我们将解耦的 GCN 视为底层 GNN，在这种情况下，FedStruct-A 和 FedStruct-B 会产生相同的性能，如下所示来自定理5。从表1可以看出，FedStruct相比FL GNN和FedSage+进一步提高了性能。对于 Cora 和 Chameleon 数据集来说，这一改进非常显着。对于 Chameleon 和 20 个客户端，FedStruct 与 Hop2Vec 的准确率达到 52.76%，而 FedSage+ 的准确率为 34.33%。该表还显示，结构特征能够收集更多全局信息，从而提高了性能，从 DEG、GDV 和 Node2Vec 之间的改进可以看出t2>。对于除 Chameleon 之外的所有数据集，Hop2Vec 的性能与 Node2Vec 类似，Chameleon 的性能显着优于 Node2Vec。我们进一步回忆一下，如果不了解全局图连接，则无法在场景中使用Node2Vec。

值得注意的是，FedStruct 与 Hop2Vec 实现了接近集中式方法的性能。例如，在 Cora 和 Amazon Photo 上，中央 GNN 和 Hop2Vec 之间的差距分别为 $2.56\%$ 和 $0.3\%$ 。在所有数据集中都观察到了相似大小的差距。此外，与 FL GNN 等相比，FedStruct 对越来越多的客户端仍然具有鲁棒性，并且如附录 K 所示，跨不同的分区方法，强调其利用客户端之间互连的能力。附录 K 中提供了各种分区、不同数量的标记训练节点以及不同程度的异质性的其他结果。

8结束语

我们提出了 FedStruct，这是一个基于互连图的 FL 框架，它解耦节点和结构特征，显式地利用深层结构依赖关系。 FedStruct 的独特优势概述如下。

隐私。现有的子图 FL 框架需要在客户端之间共享原始或生成的节点特征和/或嵌入，与此不同，FedStruct 消除了这种需求，共享不太敏感的信息。在附录L.1中，我们讨论了FedStruct的隐私考虑因素。

半监督学习。 FedStruct 表现出出色的性能，接近集中式方法，即使在标记节点比例较低的重度半监督学习场景中（参见附录 K)，并且显着优于集中式方法FedSage+ 在这些具有挑战性的场景中。

异性。 FedStruct 对于严重异嗜性数据集具有出色的性能，在这些设置中显着优于 FedSage+（请参阅附录 K)。

跨不同分区的稳健性。与 FedSage+ 等其他方法相比，FedStruct 在不同分区（附录 K)和不同数量的客户端上表现出鲁棒性。

任务相关的 NSF。与Node2Vec和GDV等众所周知的方法相反，所提出的Hop2Vec不需要全局图的知识。

参考

Abu-El-Haija et al. (2019) Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Galstyan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, 2019.
Bouritsas et al. (2023) Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis & Machine Intelligence, 45(1), 2023.
Chen et al. (2021) Chen, F., Li, P., Miyazaki, T., and Wu, C. Fedgraph: Federated graph learning with intelligent sampling. IEEE Transactions on Parallel and Distributed Systems, 33(8):1775–1786, 2021.
Cui et al. (2022) Cui, H., Lu, Z., Li, P., and Yang, C. On positional and structural node features for graph neural networks on non-attributed graphs. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022.
Dong et al. (2021) Dong, H., Chen, J., Feng, F., He, X., Bi, S., Ding, Z., and Cui, P. On the equivalence of decoupled graph convolution network and label propagation. In Proceedings of the Web Conference, 2021.
Du & Wu (2022) Du, B. and Wu, C. Federated graph learning with periodic neighbour sampling. In IEEE International Symposium on Quality of Service (IWQoS), 2022.
Fan et al. (2019) Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., and Yin, D. Graph neural networks for social recommendation. In The world wide web conference, 2019.
Fox & Rajamanickam (2019) Fox, J. and Rajamanickam, S. How robust are graph neural networks to structural noise? arXiv:1912.10206, 2019.
Grover & Leskovec (2016) Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In International conference on Knowledge discovery and data mining (SIGKDD), 2016.
Hamilton et al. (2017) Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. Neurips, 30, 2017.
Jiang & Luo (2022) Jiang, W. and Luo, J. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207, 2022.
Kipf & Welling (2017) Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Lei et al. (2023) Lei, R., Wang, P., Zhao, J., Lan, L., Tao, J., Deng, C., Feng, J., Wang, X., and Guan, X. Federated learning over coupled graphs. IEEE Transactions on Parallel and Distributed Systems, 34(4), 2023.
Li et al. (2018) Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI conference on artificial intelligence, volume 32, 2018.
Liu et al. (2023) Liu, L., Chen, J., Zhu, S., Zhang, J., and Zhang, C. Federated graph learning with cross-subgraph missing links recovery. In IEEE International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA), volume 3, 2023.
Liu et al. (2020) Liu, M., Gao, H., and Ji, S. Towards deeper graph neural networks. In International conference on knowledge discovery & data mining (SIGKDD), 2020.
Liu et al. (2022) Liu, R., Xing, P., Deng, Z., Li, A., Guan, C., and Yu, H. Federated graph neural networks: Overview, techniques and challenges. arXiv:2202.07256, 2022.
McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, 2017.
Namata et al. (2012) Namata, G., London, B., Getoor, L., Huang, B., and Edu, U. Query-driven active surveying for collective classification. In International workshop on mining and learning with graphs (MLG), volume 8, 2012.
Pei et al. (2020) Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-GCN: Geometric graph convolutional networks. In ICLR, 2020.
Peng et al. (2022) Peng, L., Wang, N., Dvornek, N., Zhu, X., and Li, X. Fedni: Federated graph learning with network inpainting for population-based disease prediction. IEEE Transactions on Medical Imaging, 2022.
Platonov et al. (2023) Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at evaluation of gnns under heterophily: Are we really making progress? In ICLR, 2023.
Pržulj (2007) Pržulj, N. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2), 2007.
Ribeiro et al. (2017) Ribeiro, L. F., Saverese, P. H., and Figueiredo, D. R. struc2vec: Learning node representations from structural identity. In International conference on knowledge discovery and data mining (SIGKDD), 2017.
Sen et al. (2008) Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. Collective classification in network data. AI magazine, 29(3), 2008.
Shchur et al. (2018) Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv:1811.05868, 2018.
Stokes et al. (2020) Stokes, J. M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A., Bloom-Ackermann, Z., et al. A deep learning approach to antibiotic discovery. Cell, 180(4), 2020.
Tan et al. (2023) Tan, Y., Liu, Y., Long, G., Jiang, J., Lu, Q., and Zhang, C. Federated learning on non-iid graphs via structural knowledge sharing. In AAAI conference on artificial intelligence, volume 37, 2023.
Veličković et al. (2018) Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Xu et al. (2019) Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019.
Zhang et al. (2021) Zhang, K., Yang, C., Li, X., Sun, L., and Yiu, S. M. Subgraph federated learning with missing neighbor generation. Neurips, 34, 2021.
Zhang et al. (2022) Zhang, K., Xie, H., Gu, Z., Li, X., Sun, L., Yiu, S. M., Yao, Y., and Yang, C. Subgraph federated learning over heterogeneous graphs. In FedGraph, 2022.
Zhang et al. (2024) Zhang, K., Sun, L., Ding, B., Yiu, S. M., and Yang, C. Deep efficient private neighbor generation for subgraph federated learning. In Siam Conference on Data Mining (SDM), 2024.
Zheng et al. (2022) Zheng, X., Liu, Y., Pan, S., Zhang, M., Jin, D., and Yu, P. S. Graph neural networks for graphs with heterophily: A survey. arXiv:2202.07082, 2022.
Zhu et al. (2020) Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Neurips, 33, 2020.

附录A节点结构特征生成

在本附录中，我们提供了一些有关结构特征创建的背景。本文考虑的最简单的方法是单热度编码(Deg)，它简单地创建一个具有单个非零条目的向量，其位置指示节点度。当然，one-hot 编码无法捕获超出 1 跳邻居的任何内容。

图基度向量 (GDVs) 通过表示节点结构特征 (NSF) 内节点的局部结构，超越了 1 跳邻域。这是通过对每个节点计算预定义的图基集（Pržulj，2007）中出现的次数来实现的。尽管 GDV 比 Deg 更具表现力，但这种方法的复杂性很高，因为图基数的数量随着节点数量的增加而增长得非常快。

Node2Vec 是一种无监督节点嵌入算法，它通过捕获局部和全局属性，从图中的随机游走创建 NSF（Grover & Leskovec，2016）。它使用受控随机游走来探索图，生成类似于语言中的句子的节点序列。对于图中的每个节点，执行多次随机游走，创建节点序列的大型语料库。然后使用这些序列来训练skip-gram模型来预测给定节点的上下文，即随机游走中的相邻节点。训练完成后，通过使用节点查询 Skip-Gram 模型并提取其潜在表示来获得 NSF。

在 FedStruct 的上下文中，Node2Vec 与 Deg 和 GDV 相比显示出卓越的性能，请参阅第 7和附录J，由于它能够捕获图的全局属性，使用连续表示具有更高的表达性，并且针对给定图进行了优化。此外，通过适当的调整，NSF 可能依赖于同质性或结构等效性（Grover & Leskovec，2016）。然而，Node2Vec 的目标函数包含多个超参数并且与任务无关，即，其表示不考虑手头的节点分类任务。此外，Node2Vec 需要访问整个邻接矩阵才能收集随机游走。因此，它不能用于不了解全局图的场景。

为了利用 Node2Vec 的优点，同时减轻其在我们的设置中的缺点，我们提出 Hop2Vec。在 Hop2Vec 中，我们不是在 FedStruct 启动之前学习 NSF，而是从随机 NSF 开始，并在 FedStruct 中训练生成器。因此，我们获得了针对任务量身定制的 NSF，例如，最大限度地减少错误分类。值得注意的是，与Node2Vec形成鲜明对比，Hop2Vec不需要了解完整的邻接矩阵。此外，与Node2Vec相比，Hop2Vec速度更快，并且不需要任何超参数调整。最后，当与解耦 GCN (DGCN) 配合使用时，它能够捕获图的全局属性。表 2 总结了不同的 NSF 生成方法。

表2：比较 NSF 生成器算法

Data	Deg	GDV	Node2Vec	Hop2Vec
task dependent	✗	✗	✗	✓
global properties	✗	✗	✓	✓DGCN
fast	✓	✗	✗	✓
no parameter tuning	✓	✓	✗	✓
locally computable	✓	✗	✗	✓

附录 B 1 的证明

为了证明1，我们需要以下引理。

引理1。

设 $\hat{\boldsymbol{y}}=\mathrm{softmax}(\boldsymbol{z})$ 和 $\mathcal{L}=\mathrm{CE}(\boldsymbol{y},\hat{\boldsymbol{y}})$ ，其中 $\mathrm{CE}$ 是交叉熵损失函数， $\boldsymbol{y}$ 是对应于输入向量 $\boldsymbol{z}$ ，其中 $\sum_{i=1}^{c}{y_{i}}=1$ 和 $c$ 是类的数量。 $\mathcal{L}$ 相对于 $\boldsymbol{z}$ 的梯度等于

\nabla_{\boldsymbol{z}}\mathcal{L}=\hat{\boldsymbol{y}}-\boldsymbol{y}\,.

(25)

证明。

使用交叉熵的定义

\displaystyle\mathrm{CE}(\boldsymbol{y},\hat{\boldsymbol{y}})=-\sum_{i=1}^{c}{y_{i}\mathrm{log}(\hat{y}_{i})}\,,

(26)

以及softmax的定义，

\displaystyle\mathrm{softmax}(\boldsymbol{z})=||\left(\frac{e^{z_{i}}}{\sum_{j=1}^{c}{e^{z_{j}}}}\quad\forall i\in[c]\right)\,,

(27)

我们可以将 $\mathcal{L}$ 重写为

$\displaystyle\mathcal{L}$	$\displaystyle=\sum_{i=1}^{c}{y_{i}\big{(}\mathrm{LSE}(\boldsymbol{z})-z_{i}\big{)}}$
	$\displaystyle=\mathrm{LSE}(\boldsymbol{z})\sum_{i=1}^{c}{y_{i}}-\sum_{i=1}^{c}{y_{i}z_{i}}$
	$\displaystyle=\mathrm{LSE}(\boldsymbol{z})-\boldsymbol{z}^{\mathsf{T}}\boldsymbol{y}\,,$	(28)

其中 $\mathrm{LSE}(\boldsymbol{z})=\mathrm{log}(\sum_{j=1}^{c}{e^{z_{j}}})$ 是 log-sum-exp 函数。 $\mathrm{LSE}(\boldsymbol{z})$ 对 $\boldsymbol{z}$ 的偏导数是 $\mathrm{softmax}$ 函数

$\displaystyle\nabla_{\boldsymbol{z}}\mathrm{LSE}(\boldsymbol{z})$	$\displaystyle=\|\|(\frac{\partial{\mathrm{LSE}(\boldsymbol{z})}}{\partial{z_{k}}}\quad\forall k\in[c])$
	$\displaystyle=\|\|(\frac{e^{z_{k}}}{\sum_{j=1}^{c}{e^{z_{j}}}}\quad\forall k\in[c])$
	$\displaystyle=\mathrm{softmax}(\boldsymbol{z})\,.$	(29)

因此，使用 (B) 并取 (B) 对于 $\boldsymbol{z}$ 的导数会导致

\displaystyle\nabla_{\boldsymbol{z}}\mathcal{L}

\displaystyle=\nabla_{\boldsymbol{z}}\mathrm{LSE}(\boldsymbol{z})-\nabla_{\boldsymbol{z}}(\boldsymbol{z}^{\mathsf{T}}\boldsymbol{y})=\hat{\boldsymbol{y}}-\boldsymbol{y}\,.

∎

使用1，我们现在可以证明1。根据链式法则和 1，我们有

	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{j}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{j}}}\nabla_{\boldsymbol{z}_{v}}\mathcal{L}_{i}(\boldsymbol{\theta})}$
		$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall j\in[\|\boldsymbol{\theta}\|]\,,$		(30)

其中 $\boldsymbol{z}_{v}=(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}+(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)}$ 。对 $\boldsymbol{\theta}$ 的不同条目求 $\boldsymbol{z}_{v}$ 的导数导致

$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{s},j}}}$	$\displaystyle=\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\theta_{\mathsf{s},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{s}}\|]$	(31)
$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{f},j}}}$	$\displaystyle=\frac{\partial{\boldsymbol{h}_{v}^{(L)}}}{\partial{\theta_{\mathsf{f},j}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{f}}\|]$	(32)
$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}$	$\displaystyle=\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})})^{\mathsf{T}}\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{s})}}}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{s})}\|]$	(33)
$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{f})}}}$	$\displaystyle=\frac{\partial{\big{(}(\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{f})})^{\mathsf{T}}\boldsymbol{h}_{v}^{(L)}\big{)}}}{\partial{\theta_{\mathsf{c},j}^{(\mathsf{f})}}}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{c}}^{(\mathsf{f})}\|]\,.$	(34)

将 (31)、(32)、(33) 和 (34) 代入 (B) 得出证明。

附录C2的证明

使用链式法则和 1，我们有

	$\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}\nabla_{\boldsymbol{z}_{v}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})}$
		$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall q\in\mathcal{V}\,,$		(35)

\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}=\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}}\boldsymbol{\Theta}_{\mathsf{c}}^{(\mathsf{s})}\quad\forall q\in\mathcal{V}\,.

(36)

将 (36) 代入 (C) 得出证明。

附录 D 任务相关 FedStruct-A 算法

算法 2 中描述了具有 Hop2Vec 的框架 FedStruct-A。

算法2 任务相关的 FedStruct-A 算法

0: global graph

\mathcal{G}

, sGNN and fGNN functions, NSF generator function

\boldsymbol{Q}_{NSF}

, K client with their respective subgraph

\{\mathcal{G}_{i}\}_{i=1}^{K}

FedStruct model parameters

\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}}||\boldsymbol{\theta}_{\mathsf{c}})

Create

\boldsymbol{S}

by randomly initialize

\boldsymbol{s}_{v}\quad\forall v\in\mathcal{V}

for e=1 to Epochs do

\boldsymbol{S}^{(L_{\mathsf{s}})}\leftarrow\text{sGNN}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{S},\mathcal{E})

for i=1 to K do

Client

i

collects

\boldsymbol{\theta}

from the server

Client

i

collects

\{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})},\forall v\in\tilde{\mathcal{V}}_{i}\}

from the server

Client

i

collects

\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{\theta}_{\mathsf{s}}}},\forall v\in\tilde{\mathcal{V}}_{i}\}

from the server

Client

i

collects

\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}},\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}

from the server

\boldsymbol{H}_{i}^{(L)}=\text{fGNN}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{X}_{i},\mathcal{E}_{i})

for

v\in\tilde{\mathcal{V}}_{i}

\hat{\boldsymbol{y}}_{v}=\mathrm{softmax}(\boldsymbol{\Theta}_{\mathsf{c}}^{\mathsf{T}}.(\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}||\boldsymbol{h}_{v}^{(L)}))

end for

Calculate

\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

based on (7)

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

from 1

Calculate

\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

from 2

Send

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

and

\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

to the server

end for

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

based on (8)

Calculate

\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})=\frac{1}{|\tilde{\mathcal{V}}|}\sum_{i=1}^{K}{\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})}

\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

\boldsymbol{S}\leftarrow\boldsymbol{S}-\lambda_{\mathsf{s}}\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

end for

附录E4的证明

使用 (B) 我们有

\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{j}}}=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{j}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\,,

其中 $\boldsymbol{z}_{v}=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}$ 。对 $\boldsymbol{\theta}$ 的不同条目求 $\boldsymbol{z}_{v}$ 的导数导致

	$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{s},j}}}$	$\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},j}}}}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{s}}\|]$		(37)
	$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\theta_{\mathsf{f},j}}}$	$\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{h}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{f},j}}}}\quad\forall j\in[\|\boldsymbol{\theta}_{\mathsf{f}}\|]$		(38)

将 (37) 和 (38) 代入 (B) 并在不同客户端上分离 $\mathcal{V}$ 的总和得出结论证据。

附录F6的证明

首先注意到

\displaystyle\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})=||\big{(}(\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S}))^{\mathsf{T}}\quad\forall q\in\mathcal{V}\big{)}\,.

(39)

使用 (C) 我们有

\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall q\in\mathcal{V}\,,

其中 $\boldsymbol{z}_{v}=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\boldsymbol{s}_{u}}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}$ 。对 $\boldsymbol{z}_{v}$ 对 $\boldsymbol{s}_{q}$ 求导可得出

$\displaystyle\frac{\partial{\boldsymbol{z}_{v}}}{\partial{\boldsymbol{s}_{q}}}$	$\displaystyle=\sum_{u\in\mathcal{V}}{\bar{a}_{vu}\frac{\partial{\boldsymbol{s}_{u}}}{\partial{\boldsymbol{s}_{q}}}}$
	$\displaystyle=\bar{a}_{vq}\frac{\partial{\boldsymbol{s}_{q}}}{\partial{\boldsymbol{s}_{q}}}$
	$\displaystyle=\bar{a}_{vq}\boldsymbol{I}\quad\forall q\in\mathcal{V}$	(40)

将 (F) 替换为 (C) 可得出

\displaystyle\nabla_{\boldsymbol{s}_{q}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\bar{a}_{vq}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})}\quad\forall q\in\mathcal{V}

(41)

将 (41) 代入 (39) 验证该定理。

附录G获取 $\boldsymbol{\bar{A}}^{[i]}$

正如6节中所讨论的，具有解耦GCN的FedStruct仅要求客户端能够访问全局 $L$ 跳组合邻接矩阵的本地分区，即 $\boldsymbol{\bar{A}}^{[i]}$ 。在本附录中，我们提出了一种算法，使客户能够私下获取该矩阵。

我们用 $\boldsymbol{\tilde{A}}^{[i]}=||(\boldsymbol{\tilde{a}}_{v}^{\mathsf{T}},\quad\forall v\in\tilde{\mathcal{V}}_{i})$ 和 $\boldsymbol{\hat{A}}^{[i]}=||(\boldsymbol{\hat{a}}_{v}^{\mathsf{T}},\quad\forall v\in\tilde{\mathcal{V}}_{i})$ 表示属于客户端 $i$ 的标记节点的 $\boldsymbol{\tilde{A}}$ 和 $\boldsymbol{\hat{A}}$ 的本地分区> 分别。另外，请注意 $\boldsymbol{\hat{A}}^{[i]}=\big{(}\boldsymbol{\tilde{D}}^{[i]}\big{)}^{-1}\boldsymbol{\tilde{A}}^{[i]}$ ，其中 $\boldsymbol{\tilde{D}}^{[i]}\in\mathbb{R}^{|\tilde{\mathcal{V}}_{i}|\times|\tilde{\mathcal{V}}_{i}|}$ 是节点度数的对角矩阵，其中 $\boldsymbol{\tilde{D}}^{[i]}(v,v)=\sum_{u\in\mathcal{V}}{\tilde{a}_{vu}}$ 、 $\forall v\in\tilde{\mathcal{V}}_{i}$ 。另外，令 $\boldsymbol{\tilde{A}}^{[i]}_{j}\in\mathbb{R}^{|\tilde{\mathcal{V}}_{i}|\times|\mathcal{V}_{j}|}$ 表示 $\boldsymbol{\tilde{A}}^{[i]}$ 的条目，该条目将客户端 $i$ 连接到 $j\in[K]$ 的客户端 $j$ 并定义 $\boldsymbol{\hat{A}}^{[i]}_{j}$ 类似。因此，我们有 $\boldsymbol{\hat{A}}^{[i]}_{j}=\big{(}\boldsymbol{\tilde{D}}^{[i]}\big{)}^{-1}\boldsymbol{\tilde{A}}^{[i]}_{j}$ 。我们注意到，客户端 $i$ 可以在本地计算 $\boldsymbol{\hat{A}}^{[i]}_{j}$ ，因为它知道其传出边缘的目的地，即所有 $j\in[K]$ 的 $\boldsymbol{\tilde{A}}^{[i]}_{j}$ ，并且可以计算 $\boldsymbol{\tilde{D}}^{[i]}$ 。

在客户端 $i$ 中，我们感兴趣的是获取其 $\boldsymbol{\bar{A}}$ 的本地分区，即 $\boldsymbol{\bar{A}}^{[i]}$ 。对于 $L_{s}=2$ ，我们有

\displaystyle\boldsymbol{\bar{A}}^{[i]}_{j}

\displaystyle=\beta_{1}\boldsymbol{\hat{A}}^{[i]}_{j}+\beta_{2}\sum_{k\in[K]}\boldsymbol{\hat{A}}^{[i]}_{k}\boldsymbol{\hat{A}}^{[k]}_{j},\quad j\in[K]\,.

(42)

我们引入符号 $[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}=\sum_{k\in[K]}\boldsymbol{\hat{A}}^{[i]}_{k}\big{[}\boldsymbol{\hat{A}}^{[k]}_{j}\big{]}^{\ell-1}$ 并写

	$\displaystyle[\boldsymbol{\hat{A}}^{[i]}_{j}]^{2}$	$\displaystyle=\sum_{k\in[K]}\boldsymbol{\hat{A}}^{[i]}_{k}\boldsymbol{\hat{A}}^{[k]}_{j},\quad j\in[K]$		(43)
		$\displaystyle=(\boldsymbol{\tilde{D}}^{[i]})^{-1}\sum_{k\in[K]}\underbrace{\boldsymbol{\tilde{A}}^{[i]}_{k}\boldsymbol{\hat{A}}^{[k]}_{j}}_{\text{computed at client }k},\quad j\in[K]\,.$		(44)

从 (44) 中，我们注意到客户端 $i$ 将为所有 $j\in[K]$ 存储 $[\boldsymbol{\hat{A}}^{[i]}_{j}]^{2}$ ，因此也存储 $[\boldsymbol{\hat{A}}^{[i]}]^{2}$ 。对于整数 $\ell\geq 2$ ，我们可以利用前几轮中获取的信息：

\displaystyle[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}=(\boldsymbol{\tilde{D}}_{i})^{-1}\sum_{k\in[K]}\underbrace{\boldsymbol{B}_{ijk}}_{\text{computed at client }k},\quad j\in[K]\,.

(45)

其中 $\boldsymbol{B}_{ijk}=\boldsymbol{\tilde{A}}^{[i]}_{k}[\boldsymbol{\hat{A}}^{[k]}_{j}]^{\ell-1}$ 是可以在客户端 $k$ 中计算的 $n_{i}\times n_{j}$ 矩阵。因此，客户端可以按顺序计算 $\boldsymbol{\bar{A}}^{[i]}_{j}$

\displaystyle\boldsymbol{\bar{A}}^{[i]}_{j}

\displaystyle=\beta_{1}\boldsymbol{\hat{A}}^{[i]}_{j}+\sum_{\ell=2}^{L_{s}}\beta_{\ell}[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell},\quad j\in[K]\,.

(46)

算法结果如算法 3 所示。最后，我们注意到算法 3 要求每个客户端评估 $L_{s}K^{2}$ 矩阵乘积并传达 $L_{s}(K-1)K$ 矩阵。尽管复杂度很大，但我们强调该算法仅在训练开始前执行一次。

算法3 私人收购

\boldsymbol{\bar{A}}^{[i]}

\big{\{}\boldsymbol{\tilde{A}}^{[i]}_{j},\boldsymbol{\tilde{A}}^{[j]}_{i}\big{\}}_{j=1}^{K},\boldsymbol{\tilde{D}}^{[i]}

, power

L

, and list of weights

\{\beta_{\ell}\}_{\ell=1}^{L}

0: local matrix

\{\boldsymbol{\bar{A}}^{[i]}\}

for

i=1

K

for

j=1

K

Initialize

\boldsymbol{\bar{A}}^{[i]}_{j}=\beta_{1}(\boldsymbol{\tilde{D}}^{[i]})^{-1}\boldsymbol{\tilde{A}}^{[i]}_{j}

end for

for

\ell=2

L_{s}

for

i=1

K

Client

i

collects

\boldsymbol{B}_{ijk}=\boldsymbol{\tilde{A}}^{[i]}_{k}[\boldsymbol{\hat{A}}^{[k]}_{j}]^{\ell-1}

from clients

k\in[K]

Client

i

stores

[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}=(\boldsymbol{\tilde{D}}^{[i]})^{-1}\sum_{k=1}^{K}\boldsymbol{B}_{ijk}

for

j\in[K]

\boldsymbol{\bar{A}}^{[i]}_{j}\leftarrow\textasciiacute\boldsymbol{\bar{A}}^{[i]}_{j}+\beta_{\ell}[\boldsymbol{\hat{A}}^{[i]}_{j}]^{\ell}

for

j\in[K]

end for

附录 H FedStruct-B 算法

FedStruct-B 框架在算法 4 中描述。

算法4 美联储结构-B

0: K client with their respective subgraph

\{\mathcal{G}_{i}\}_{i=1}^{K}

FedStruct model parameters

\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}})

for i=1 to K do

Collaboratively obtain

\boldsymbol{\bar{A}}^{[i]}

based on Algorithm 3

Locally compute NSFs

\mathcal{S}_{i}=\{\boldsymbol{s}_{u},\forall u\in\mathcal{V}_{i}\}

\mathcal{S}_{i}

with all the clients

end for

for e=1 to Epochs do

for i=1 to K do

Client

i

collects

\boldsymbol{\theta}

from the server

for

v\in\tilde{\mathcal{V}}_{i}

Calculate

\hat{\boldsymbol{y}}_{v}

based on (20)

end for

Calculate

\mathcal{L}_{i}(\boldsymbol{\theta})

based on (7)

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})

based on 4

Send

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta})

to the server

end for

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})

based on (8)

\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta})

end for

附录 I FedStruct-B 与 Hop2Vec 算法

FedStruct-B使用Hop2Vec的训练过程在算法5中描述。

算法5 任务相关 FedStruct-B

0: K client with their respective subgraph

\{\mathcal{G}_{i}\}_{i=1}^{K}

FedStruct model parameters

\boldsymbol{\theta}=(\boldsymbol{\theta}_{\mathsf{f}}||\boldsymbol{\theta}_{\mathsf{s}})

Serrver initialize

\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})=\boldsymbol{0}

for i=1 to K do

Collaboratively obtain

\boldsymbol{\bar{A}}^{[i]}

based on Algorithm 3

Create

\mathcal{S}_{i}=\{\boldsymbol{s}_{u},\forall u\in\mathcal{V}_{i}\}

by randomly initialize

\boldsymbol{s}_{u}\quad\forall u\in\mathcal{V}_{i}

\mathcal{S}_{i}

with all the clients

Collect

\mathcal{S}_{j}\quad\forall j\in[K]

and create

\boldsymbol{S}=||(\boldsymbol{s}_{v}^{\mathsf{T}},\quad\forall v\in\mathcal{V})

end for

for e=1 to Epochs do

for i=1 to K do

Client

i

collects

\boldsymbol{\theta}

from the server

Client

i

collects

\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

from the server

Client

i

updates

\boldsymbol{S}\leftarrow\boldsymbol{S}-\lambda_{\mathsf{s}}\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

for

v\in\tilde{\mathcal{V}}_{i}

Calculate

\hat{\boldsymbol{y}}_{v}

based on (23)

end for

Calculate

\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

based on (7)

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

based on 4

Calculate

\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

based on 6

Send

\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

and

\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})

to the server

end for

Calculate

\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

based on (8)

\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\lambda\nabla_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})

Calculate

\nabla_{\boldsymbol{S}}\mathcal{L}(\boldsymbol{\theta},\boldsymbol{S})=\frac{1}{|\tilde{\mathcal{V}}|}\sum_{i=1}^{K}{\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})}

end for

附录J实验设置

在本节中，我们将在第 7 节和附录 K 中提供有关实验的更多详细信息。表3显示了不同数据集的统计数据。边同质性比率测量连接具有相同标签的节点的边的分数，提供了数据集中同质性的度量。通常，高于 $0.5$ 的值被视为同质（Zheng 等人，2022）。根据这一经验法则，在本文考虑的数据集中，有两个数据集被认为是异性的，即 Chameleon 和 Amazon Ratings。

接下来，我们提供实验的超参数。在表4中，我们提供了训练期间梯度下降步骤的步长 $\lambda$ 和 $\lambda_{\mathsf{s}}$ 、L2正则化中的权重衰减、数量训练迭代次数（epochs）、节点特征嵌入中的层数 $L$ 、DGCN中的层数 $L_{\mathsf{s}}$ 、NSF的维数、 $d_{\mathsf{s}}$ ，以及节点特征和节点结构特征预测器的模型架构，分别为 $\boldsymbol{f}_{{\boldsymbol{\theta}}_{\mathsf{f}}}$ 和 $\boldsymbol{g}_{{\boldsymbol{\theta}}_{\mathsf{s}}}$ 。

表3：数据集的统计。

Data	Cora	CiteSeer	PubMed	Chameleon	Amazon Photo	Amazon Ratings
$\#$ Classes	7	6	3	5	8	5
$\|\mathcal{V}\|$	2708	3327	19717	2277	7650	24492
$\|\mathcal{E}\|$	5278	4676	44327	36101	238162	93050
$\#$ Features	1433	3703	500	2325	745	300
Edge homophily ratio	0.81	0.74	0.80	0.23	0.82	0.38

表 4：数据集的超参数。

Data	Cora	CiteSeer	PubMed	Chameleon	Amazon Photo	Amazon Ratings
$\lambda$	0.002	0.002	0.008	0.003	0.005	0.002
$\lambda_{\mathsf{s}}$	0.002	0.002	0.008	0.003	0.005	0.002
Weight decay	0.0005	0.0005	0.001	0.0003	0.001	0.0002
Epochs	40	60	125	60	150	70
$L$	2	2	2	1	1	2
$L_{\mathsf{s}}$	10	20	20	1	3	5
$d_{\mathsf{s}}$	256	256	256	256	256	256
$\boldsymbol{\theta}_{\mathsf{f}}$ layers	[1433,64,7]	[3703,64,6]	[500,128,3]	[2325,64,5]	[745,256,8]	[300,64,5]
$\boldsymbol{\theta}_{\mathsf{s}}$ layers	[256,256,7]	[256,128,64,6]	[256,128,3]	[256,256,5]	[256,256,8]	[256,256,5]

附录 K其他结果

在本附录中，我们提供了由于空间限制而无法包含在主论文中的其他结果。

K.1 不同的分区

在本节中，我们提供不同类型的数据分区的结果。我们考虑三种不同的划分方法：Louvain 算法、K-means 算法和随机划分。

Louvain算法旨在寻找具有高链接密度的社区，有效地创建具有有限互连的子图。在这里，我们遵循 (Zhang 等人, 2021)，首先使用 Louvain 算法将全局图划分为多个子图。当我们努力在客户端中拥有偶数个节点时，我们检查子图的大小，如果有超过 $n/K$ 节点，则将其分成两部分。重复此过程，直到没有子图具有超过 $n/K$ 节点。接下来，由于子图的数量可能大于 $K$ ，因此必须合并一些子图。为此，我们按照子图大小的降序对子图进行排序，并将第一个 $K$ 子图分配给 $K$ 客户端。如果有多个 $K$ 个子图，我们通过迭代 $K$ 客户端并将其分配给第一个客户端来分配第 ( $K+1$ ) 个子图。合并后的节点总数不会超过 $n/K$ 。重复此过程，直到只剩下 $K$ 子图。此过程会产生具有大致相同数量的节点和少量互连的子图。

对于K-means算法，我们遵循（Lei等人，2023）并根据节点特征空间中的邻近度将数据划分为 $K$ 簇。与 Louvain 分区类似，我们将超过 $n/K$ 节点的任何子图分成两部分，并将其分配给另一个子图，使得生成的节点数小于 $n/K$ 。与之前的划分相比，K-means 方法不考虑拓扑，因此与基于 Louvain 的划分相比，不同子图之间会有更多的互连。此外，正如（Lei等人，2023）中强调的那样，由于具有相似特征的节点往往具有相同的标签，因此这种划分方法创建了高度异构的划分，因为每个子图往往具有过度表示给定类的节点。

表 5：具有底层解耦 GCN 的 FedStruct 的分类精度。显示 10 个客户端的结果，训练-验证-测试分割为 10-10-80。

	Cora			Citeseer			Pubmed
Central GNN	82.06 $\pm$ 1.09			69.17 $\pm$ 0.90			87.71 $\pm$ 0.34
Central MLP	65.31 $\pm$ 1.75			64.18 $\pm$ 0.89			85.80 $\pm$ 0.33
	Louvain	random	kmeans	Louvain	random	kmeans	Louvain	random	kmeans
FL MLP	64.42 $\pm$ 0.54	63.71 $\pm$ 1.59	64.24 $\pm$ 2.02	63.39 $\pm$ 0.68	63.98 $\pm$ 1.53	64.92 $\pm$ 1.39	85.39 $\pm$ 0.33	85.58 $\pm$ 0.39	85.00 $\pm$ 0.32
FL GNN	80.99 $\pm$ 1.33	65.06 $\pm$ 1.92	67.12 $\pm$ 2.01	68.55 $\pm$ 1.25	63.47 $\pm$ 1.29	65.07 $\pm$ 1.39	85.31 $\pm$ 0.44	85.91 $\pm$ 0.42	86.02 $\pm$ 0.35
Fedsage+	80.75 $\pm$ 0.88	66.32 $\pm$ 1.81	67.08 $\pm$ 2.19	68.20 $\pm$ 1.34	63.37 $\pm$ 1.45	64.32 $\pm$ 1.25	85.55 $\pm$ 0.59	85.37 $\pm$ 0.55	85.83 $\pm$ 0.44
Fedsage-TRUE	82.38 $\pm$ 1.28	80.85 $\pm$ 1.55	80.58 $\pm$ 1.30	68.99 $\pm$ 1.33	68.91 $\pm$ 1.30	69.53 $\pm$ 1.25	84.69 $\pm$ 1.14	85.66 $\pm$ 0.37	85.81 $\pm$ 0.80
FedSruct (Deg)	81.64 $\pm$ 2.33	68.64 $\pm$ 1.51	70.25 $\pm$ 2.33	68.41 $\pm$ 1.20	63.81 $\pm$ 1.31	66.16 $\pm$ 1.31	84.52 $\pm$ 0.47	85.09 $\pm$ 0.48	85.22 $\pm$ 0.37
FedSruct (GDV)	80.60 $\pm$ 2.55	72.19 $\pm$ 1.62	73.24 $\pm$ 2.06	68.30 $\pm$ 1.06	64.44 $\pm$ 0.84	66.71 $\pm$ 1.62	84.63 $\pm$ 0.36	86.12 $\pm$ 0.56	85.79 $\pm$ 0.45
FedSruct (N2V)	82.78 $\pm$ 1.03	80.68 $\pm$ 1.77	80.59 $\pm$ 1.50	68.42 $\pm$ 1.24	66.28 $\pm$ 1.04	67.58 $\pm$ 1.18	84.72 $\pm$ 0.44	87.09 $\pm$ 0.44	86.64 $\pm$ 0.49
FedSruct (H2V)	81.23 $\pm$ 1.14	80.28 $\pm$ 1.44	79.80 $\pm$ 1.53	68.50 $\pm$ 0.93	66.29 $\pm$ 0.87	67.20 $\pm$ 1.52	83.74 $\pm$ 0.39	86.65 $\pm$ 0.53	86.01 $\pm$ 0.38
Local GNN	75.52 $\pm$ 1.45	39.23 $\pm$ 1.21	46.80 $\pm$ 4.59	58.75 $\pm$ 1.37	38.99 $\pm$ 1.60	49.15 $\pm$ 5.21	81.17 $\pm$ 0.37	79.10 $\pm$ 0.54	81.34 $\pm$ 0.63
Local MLP	66.33 $\pm$ 1.12	38.57 $\pm$ 1.55	45.81 $\pm$ 3.90	53.27 $\pm$ 1.02	39.50 $\pm$ 1.19	50.12 $\pm$ 5.80	82.78 $\pm$ 0.67	78.51 $\pm$ 0.57	80.81 $\pm$ 0.56

	Chameleon			Amazon Photo			Amazon Ratings
	Louvain	random	kmeans	Louvain	random	kmeans	Louvain	random	kmeans
Central GNN	54.43 $\pm$ 2.44			93.99 $\pm$ 0.48			41.32 $\pm$ 1.03
Central MLP	32.15 $\pm$ 1.42			88.68 $\pm$ 0.98			37.56 $\pm$ 0.48
FL MLP	31.77 $\pm$ 2.32	31.72 $\pm$ 1.93	32.33 $\pm$ 3.27	88.65 $\pm$ 1.11	88.04 $\pm$ 1.36	88.37 $\pm$ 0.88	37.43 $\pm$ 0.68	37.62 $\pm$ 0.61	37.48 $\pm$ 0.73
FL GNN	47.74 $\pm$ 2.11	35.70 $\pm$ 2.29	38.85 $\pm$ 2.41	93.75 $\pm$ 0.40	90.74 $\pm$ 0.58	90.92 $\pm$ 0.77	41.68 $\pm$ 0.76	36.25 $\pm$ 0.46	36.78 $\pm$ 0.49
Fedsage+	46.67 $\pm$ 1.13	35.48 $\pm$ 1.23	38.24 $\pm$ 1.86	92.86 $\pm$ 3.21	90.80 $\pm$ 0.48	90.87 $\pm$ 0.38	41.21 $\pm$ 0.38	36.18 $\pm$ 0.77	37.26 $\pm$ 0.82
Fedsage-TRUE	53.89 $\pm$ 1.72	50.75 $\pm$ 2.82	52.13 $\pm$ 2.78	93.65 $\pm$ 1.41	90.95 $\pm$ 5.27	93.58 $\pm$ 0.75	41.74 $\pm$ 0.60	39.98 $\pm$ 0.68	39.61 $\pm$ 0.55
FedSruct (Deg)	48.65 $\pm$ 2.39	41.01 $\pm$ 1.26	42.26 $\pm$ 2.60	91.20 $\pm$ 1.24	89.59 $\pm$ 0.88	89.84 $\pm$ 0.53	41.37 $\pm$ 0.61	39.08 $\pm$ 0.57	38.61 $\pm$ 0.58
FedSruct (GDV)	47.87 $\pm$ 1.88	39.54 $\pm$ 2.46	41.09 $\pm$ 2.17	91.69 $\pm$ 0.87	90.51 $\pm$ 0.45	90.60 $\pm$ 0.57	41.92 $\pm$ 0.53	39.53 $\pm$ 0.87	39.44 $\pm$ 0.61
FedSruct (N2V)	50.91 $\pm$ 1.88	43.49 $\pm$ 1.93	46.27 $\pm$ 2.26	91.68 $\pm$ 0.74	91.19 $\pm$ 1.05	91.60 $\pm$ 0.47	41.95 $\pm$ 0.69	41.43 $\pm$ 0.52	41.27 $\pm$ 0.51
FedSruct (H2V)	54.00 $\pm$ 1.71	52.36 $\pm$ 2.63	53.97 $\pm$ 2.73	90.45 $\pm$ 1.23	91.83 $\pm$ 0.39	91.44 $\pm$ 0.80	41.28 $\pm$ 0.65	41.23 $\pm$ 0.38	40.38 $\pm$ 0.59
Local GNN	45.26 $\pm$ 2.08	28.51 $\pm$ 1.59	31.08 $\pm$ 3.09	91.47 $\pm$ 0.66	79.66 $\pm$ 1.15	80.60 $\pm$ 1.57	40.88 $\pm$ 0.95	32.81 $\pm$ 0.46	35.57 $\pm$ 0.57
Local MLP	29.50 $\pm$ 2.03	21.06 $\pm$ 0.89	24.52 $\pm$ 3.22	88.34 $\pm$ 0.71	71.25 $\pm$ 1.30	75.07 $\pm$ 1.24	37.77 $\pm$ 0.67	33.24 $\pm$ 0.50	35.36 $\pm$ 0.59

最后，我们考虑随机分区，其中每个节点均匀随机分配给客户端。由于这种划分没有考虑拓扑或特征，因此我们最终得到大量互连，其中每个子图在类标签上具有相同的分布，即数据在客户端之间是同质的。值得注意的是，考虑到大量的互连，这种设置可以说构成了子图 FL 中最具挑战性的场景，因为利用互连来实现良好的性能至关重要。

在表5中，我们展示了FedStruct在 $10$ 客户端的每个不同分区上的性能以及根据10进行的train-val-test分割%-10%-80%。我们利用这种划分来关注具有挑战性的半监督场景。此外，每个结果均使用从 $10$ 独立运行获得的平均值和标准差来报告。

首先，由于 GNN 训练的中心版本不依赖于分区，因此与表 1 相同。我们还报告了 MLP 方法的性能。通过比较中央 GNN 与中央 MLP 的性能，人们可以推断出考虑数据内空间结构的增益。如表中所示，利用图结构为 Cora 和 Chameleon 带来了最大的好处。

本着类似的精神，本地 GNN(本地 MLP)和中央 GNN(中央 MLP)之间的性能差距表明客户之间采用协作学习的潜在收益。值得注意的是，这种差距取决于分区。从表5可以看出，对于所有数据集，随机划分的差距最大，其次是K-means算法。这是预料之中的，因为本地训练受到大量互连的影响。例如，在 Cora 中，随机划分、K 均值划分和 Louvain 划分的差距分别为 42.83%、35.26% 和 6.54%。

考虑FL GNN，可以看出所有场景都受益于协作学习。对于 Louvain 分区，由于其基于社区的分区且互连数量较少，FL GNN 在所有数据集上都表现良好。对于 K 均值和随机分区，FL GNN 的性能较差，其中 Cora、Chameleon 和 Amazon Ratings 的性能最差。 FedSage+ 实现了与 FL GNN 类似的性能。 FedSage-TRUE 方案结合了其他客户端中丢失邻居的节点 ID 知识，基于对丢失的一跳邻居进行完美修复的修正图。因此，该方案作为基于一跳邻居修复的技术的上限，例如 FedSage+ 和 FedNI。值得注意的是，该方案完全侵犯了隐私，因为丢失客户端的节点特征无法在客户端之间共享。从表5中，我们看到该方案通过提供接近中央GNN的一致性能，对不同的分区具有鲁棒性。

我们将带有解耦 GCN 的 FedStruct 视为底层 GNN。请注意，在这种情况下，FedStruct-A 和 FedStruct-B 产生相同的性能。我们考虑使用 FedStruct 四种不同的方法来生成 NSF：one-hot 度向量 (Deg)、图元匹配 (GDV)、node2vec (N2V)，以及我们的任务相关方法Hop2Vec(H2V)，请参阅附录A了解信息。超参数的选择如表4所示。在表5中，可以看出DEG和GDV只能捕获局部结构，性能比能够捕获局部结构的方法差。捕获图形的更多全局属性。对于 K 均值和随机划分尤其如此。 Node2Vec 和 Hop2Vec 在所有场景中实现相似的性能。然而，应该注意的是，Node2Vec 需要完全了解邻接矩阵才能创建 NSF，而我们提出的 Hop2Vec 是在本地执行的，只需要了解 $L$ -跳邻接矩阵。因此，在客户端的内部边缘是私有的情况下，Hop2Vec是首选的 NSF 生成方法。此外，可以看出 Hop2Vec 在所有场景下的表现都接近于 FedSage-TRUE，并且有时表现更出色，例如在 Chameleon 数据集上。这凸显了某些数据集超越一跳邻居的重要性，而这在 FedSage-TRUE 中是不可能的。

K.2 标记训练节点数量的影响

图2：具有随机分区的 Cora 的准确度与训练比。

正如（Liu等人，2020）中强调的那样，解耦的GCN适用于过度平滑成为瓶颈的情况。 (Dong 等人, 2021) 进一步表明，解耦 GCN 特别适合半监督学习，因为它能够在训练过程中利用来自所有未标记节点的伪标签。在图 2 中，我们展示了 FedStruct 与底层解耦 GCN 的性能(FedStruct-A 和 FedStruct-B 在这种情况下产生相同的性能）在 Cora 训练数据集上使用不同的 NSF 生成器来处理集合中不同数量的标记节点。特别是，我们使用 $x$ %-10%- $(1-x)\%$ train-val-test 分割，其中 $x$ 表示标记训练节点的比率。

从图2可以看出，FedStruct与N2V和H2V的性能非常接近中央 GNN 用于训练集中标记节点的所有部分。值得注意的是，FedStruct 即使在高度半监督的场景中也表现得非常好：它已经在 5% 的标记训练节点上表现出色，实现了接近 80% 的 top-1 准确率。不利用全局图结构的联合方法（例如 FedSage+)对于一小部分标记节点表现出性能急剧下降。例如，FedSage+ 的 top- $1$ 训练准确度从集合中 50% 标记节点的 75% 左右下降到 5% 标记节点的 60% 以下。 FedStruct 的性能在所有水平节点分数中都更胜一筹，而且下降幅度更小，从训练集中 50% 标记节点的约 84% 下降到 FedStruct 和 N2V 中 5% 标记节点的约 78%。最后，局部 GNN 的性能因标签稀缺而显着恶化。

在图 3 中，为了演示将解耦 GCN 合并到我们的框架中的优势，我们提供了具有底层解耦 GCN 和标准 GNN 的 FedStruct 结果(GraphSage)用于具有不同比例标记训练节点的半监督学习场景具体来说，我们展示了涉及 50%、10% 和 1% 标记节点的场景的准确性。对于 50% 和 10% 的标记节点，具有底层解耦 GCN 和标准 GNN 的 FedStruct 会产生相似的结果。然而，在高度半监督的场景中（如反洗钱等应用中遇到的情况），使用标准 GNN 的 FedStruct 的准确性会显着下降。相比之下，即使在如此具有挑战性的场景中，具有解耦 GCN 的 FedStruct 也能实现接近中央 GNN 的性能。这凸显了采用解耦 GCN 来有效解决半监督学习场景的关键作用。

图3：准确率与带有 FedStruct 标签的训练节点分数，在具有 K-means 分区的 Amazon Photo 数据集上具有底层解耦 GCN 和底层标准 GNN (GraphSage)。

K.3 解耦 GCN 中层数的影响

在本节中，我们提供了 Cora 数据集上 FedStruct 中解耦 GCN $L_{s}$ 中使用的层数影响的结果。在图 4 中，我们显示了使用 NFV 和 NSF 训练 FedStruct 后的 top-1 准确率，但在推理时，我们仅使用 NSF (s) 或 NSF 和 NFV (s+f)。 Central GNN 和 FL GNN 依赖于 GraphSage 和 $3$ 层，因此独立于中使用的层解耦的 GCN。

首先，我们观察到 Deg s+f 和 GDV s+f 的 top-1 精度相对于 $L_{s}$ 没有显着变化。对于Node2Vec(N2V)和Hop2Vec(H2V)，情况有所不同。对于 $L_{s}$ 低于10和高于30，H2V的性能较低，在 $10$ 和 $20$ 层之间实现最佳性能。这是因为 NSF 无法学习小 $L_{s}$ 的扩展邻域，而对于大 $L_{s}$ ，过度平滑成为瓶颈。相比之下，由于已经学习了结构，N2V 对于小 $L_{s}$ 也表现出很强的性能，但它仍然受到过度平滑的影响。我们还可视化 N2V s 和 H2V s 以突出 NSF 本身的影响。对于 $L_{s}=10$ ,N2V s 实现 $76\%$ top-1 精度，而 N2V s+f 实现接近 $82\%$ 。类似地，H2V s 实现 $75\%$ ，而H2V s+f 实现 $80\%$ top1 精度。从这里，我们得出结论，仅 NSF 就可以传达有用的信息来预测标签，但 NFV 需要实现接近中央 GNN 的性能。

图4：精度与采用 K 均值分区的 Cora 上解耦 GCN 传播层

L_{s}

的数量。

附录L讨论

L.1隐私

子图 FL 的先前框架（Zhang 等人，2021；Peng 等人，2022；Lei 等人，2023；Zhang 等人，2022；Liu 等人，2023；Zhang 等人，2024；Chen 等人，2021 ；Du & Wu，2022）要求在客户端之间共享原始或生成的节点特征和/或嵌入。与此形成鲜明对比的是，我们提出的框架 FedStruct 消除了这种需求，共享不太敏感的信息。

在服务器了解全局图连接的情况下，我们提出的框架 FedStruct-A 限制服务器对节点 NSF 和客户端本地梯度的访问。反过来，客户端仅接收 NSE 的梯度。

对于不了解全局图的场景，客户端需要与其他客户端共享一些信息。接下来，我们讨论与 FedStruct-B 相关的一些隐私注意事项。我们通过发起潜在的攻击来开始我们的讨论，以表明某些信息可能会从其他客户端泄露。此后，我们讨论通过避免共享有关节点的个人信息来减轻此类攻击的策略。具体来说，我们提出了稍微不同的 FedStruct-B 版本，它依赖于在客户端之间共享聚合数量，而不影响原始版本的性能。

在使用任务无关 NSF 的 FedStruct-B 中，为每个客户端提供 $\boldsymbol{S}$ ，即所有客户端的 NSF。考虑一个诚实但好奇的客户 $i$ ，其 NSF $\{\boldsymbol{s}_{u}\mathrel{\mathop{\mathchar 58\relax}}u\in\mathcal{V}_{i}\}$ 。客户端 $i$ 可以通过识别客户端 $j$ 内与它自己的一些NSF紧密匹配的NSF来定位客户端 $j$ 。通过这个简单的过程，客户端 $i$ 可以比较匹配的本地节点的拓扑并推断 $j$ 内的一些节点的拓扑。此外，由于 $\boldsymbol{\theta}_{s}$ 在所有客户端之间共享，因此客户端 $i$ 将能够猜测客户端 $j$ 内已识别节点的标签。给定节点的标签和拓扑，还可以进一步推断有关节点特征的信息。使用任务相关的 NSF，即 Hop2Vec，情况类似。

接下来，我们从任务无关的 NSF 生成器开始讨论如何更改 FedStruct-B 以防止本地 NSF 重建，从而减轻上述攻击。从3和4，对 $\mathcal{V}$ 的求和可以被分成对客户的求和。客户端 $i$ 的预测和局部梯度可以写为

	$\displaystyle\hat{\boldsymbol{y}}_{v}$	$\displaystyle=\mathrm{softmax}\Big{(}\sum_{j\in[K]}\sum_{u\in\mathcal{V}_{j}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}+\sum_{u\in\mathcal{V}_{i}}{\bar{a}_{vu}^{(i)}\boldsymbol{f}_{\boldsymbol{\theta}_{\mathsf{f}}}(\boldsymbol{x}_{u})}\Big{)}\,,\quad v\in\tilde{\mathcal{V}}_{i},$		(47)
	$\displaystyle\frac{\partial{\mathcal{L}_{i}(\boldsymbol{\theta})}}{\partial{\theta_{\mathsf{s},q}}}$	$\displaystyle=\sum_{v\in\tilde{\mathcal{V}}_{i}}\sum_{j\in[K]}{\sum_{u\in\mathcal{V}_{j}}\bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},q}}}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})},\quad\forall q\in[\|\boldsymbol{\theta}_{s}\|].$		(48)

值得注意的是，客户端 $i$ 可以评估其本地梯度提供的访问

	$\displaystyle\bar{\boldsymbol{s}}^{(j)}_{v}$	$\displaystyle=\sum_{u\in\mathcal{V}_{j}}{\bar{a}_{vu}\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})},\quad\forall v\in\tilde{\mathcal{V}}_{i}$		(49)
	$\displaystyle\tilde{\boldsymbol{s}}^{(j)}_{vq}$	$\displaystyle=\sum_{u\in\mathcal{V}_{j}}\bar{a}_{vu}\frac{\partial{\boldsymbol{g}_{\boldsymbol{\theta}_{\mathsf{s}}}(\boldsymbol{s}_{u})}}{\partial{\theta_{\mathsf{s},q}}},\quad\forall q\in[\|\boldsymbol{\theta}_{s}\|],\forall v\in\tilde{\mathcal{V}}_{i}$		(50)

对于每个客户端 $j\in[K]$ 。为了使客户端 $j\neq i$ 能够评估这些数量，它需要访问所有 $v\in\tilde{\mathcal{V}}_{i}$ 和 $u\in\tilde{\mathcal{V}}$ 的 $\bar{a}_{vu}$ ，即加权从客户端 $i$ 中的节点到客户端 $j$ 中的节点的 $\ell$ 跳路径的总和， $\ell\in[L]$ 。按照附录G，客户端 $j$ 可以访问 $v\in\tilde{\mathcal{V}}_{j}$ 和 $u\in\mathcal{V}$ 的 $a_{vu}$ 。值得注意的是， $a_{vu}\neq a_{uv}$ 归因于不同程度的标准化。因此，为了获得 (49) 和 (50) 中所需的数量，客户机 $i$ 可以在附录 G 中的算法完成后，与客户机 $j\in[K]$ 共享 $\{\bar{a}_{vu}\mathrel{\mathop{\mathchar 58\relax}}v\in\tilde{\mathcal{V}}_{i},u\in\mathcal{V}_{j}\}$ 。

与FedStruct-B相比，上述方法的梯度无法在本地计算，但带来的好处是客户端只知道自己本地的NSF，而不是其他人的单独NSF。因此，每次迭代训练必须分两个阶段完成，其中阶段 1 负责每个客户端 $i\in[K]$ 收集 (49) 和 (50)来自所有其他客户端，每个客户端计算本地梯度并在第 2 阶段与服务器共享这些梯度。请注意，每次训练迭代中的通信复杂性不会增加，因为 (49) 和 (50) 相当于共享 $|\tilde{\mathcal{V}}_{i}|c$ 和 $|\boldsymbol{\theta}_{s}|c$ 参数，其中 $c$ 是类标签的数量。因此，总的来说，每个客户端 $i$ 必须在每次迭代中与其他客户端共享 $(|\tilde{\mathcal{V}}\setminus\tilde{\mathcal{V}}_{i}|+|\boldsymbol{\theta}_{s}|)c$ 参数。请注意，此共享可以通过服务器或点对点链接进行。

尽管正式的隐私分析看起来很困难，但我们可以遵循类似于（Lei等人，2023）的方法来争论完美重建本地NSF的难度。为此，我们采取保守的方法，考虑诚实但好奇的客户，其中除了一个客户外，所有客户都在串通。因此，我们可以考虑两个客户端，其中客户端 1 是攻击者，客户端 2 是目标。在每次迭代中，客户端 1 接收 $v\in\tilde{\mathcal{V}}_{1}$ 和 $q\in[|\boldsymbol{\theta}_{2}|]$ 的 $\tilde{\boldsymbol{s}}_{v}^{(2)}\in\mathbb{R}^{c}$ 和 $\tilde{\boldsymbol{s}}^{(2)}_{vq}\in\mathbb{R}^{c}$ 。为了评估 $\tilde{\boldsymbol{s}}_{v}^{(2)}$ ，客户端 2 使用 $\mathinner{\!\left\lVert\boldsymbol{a}_{v}\right\rVert}_{0}$ $d_{s}$ 维 NSF，其中 L0 范数计算非零元素的数量。因此，对于每个收到的聚合 $\tilde{\boldsymbol{s}}_{v}^{(2)}$ ，客户端 $1$ 从 $\mathinner{\!\left\lVert\boldsymbol{a}_{v}\right\rVert}_{0}d_{s}$ 未知数中获取 $c$ 观察值。总的来说，客户端 $1$ 将收集 $|\tilde{\mathcal{V}}_{1}|$ 这样的观察结果，即它观察 $c|\tilde{\mathcal{V}}_{1}|$ 参数。假设对于客户端 $2$ ，最坏的情况是所有 $\boldsymbol{a}_{v}$ 在相同位置均非零且 $m$ 非零元素，客户端 $2$ 将为客户端 $1$ 中的每个观察使用相同的输入。因此，如果 $nd_{s}>c|\tilde{\mathcal{V}}_{1}|$ ，客户端 $1$ 无法从客户端 $2$ 恢复各个 NSF。值得注意的是，客户端 $2$ 具有完全控制权，因为它知道 $m$ ，并且可以计算来自客户端 $1$ 的查询数量，如果超过 $md_{s}/c$ 类似地，为了评估 $\tilde{\boldsymbol{s}}^{(2)}_{vq}$ ，客户端2利用 $\mathinner{\!\left\lVert\boldsymbol{a}_{v}\right\rVert}_{0}$ $d_{s}$ 维度输入来计算 $c$ 维度输出。因此，客户端 $2$ 将共享 $|\boldsymbol{\theta}_{s}|c$ 参数，这些参数是根据 $\mathinner{\!\left\lVert\boldsymbol{a}_{v}\right\rVert}_{0}d_{s}$ 参数 $|\tilde{\mathcal{V}}_{1}|$ 次计算得出的。因此，再次考虑最坏情况，如果 $md_{s}>c|\boldsymbol{\theta}_{s}||\tilde{\mathcal{V}}_{1}|$ ，客户端 $1$ 无法重建局部梯度。同样，客户端 $2$ 可以监视查询的数量，以便不违反条件。

当使用 Hop2Vec 作为 NSF 生成器时，我们不再对 $\boldsymbol{\theta}_{s}$ 进行优化，而是直接对 NSF $\boldsymbol{S}$ 进行优化。我们在 FedStruct-B 中面临的问题是每个客户端都可以访问 $\boldsymbol{S}$ 。为了缓解这个问题，我们使用定理 6 将求和分解为 $\mathcal{V}$ 以获得

\displaystyle\bar{\boldsymbol{s}}^{(j)}_{v}

\displaystyle=\sum_{u\in\mathcal{V}_{j}}\bar{a}_{vu}\boldsymbol{s}_{u},\quad\forall v\in\tilde{\mathcal{V}}_{i}.

(51)

此外，客户端 $i$ 中 NSF 的局部梯度给出为

\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})=\sum_{v\in\tilde{\mathcal{V}}_{i}}{\boldsymbol{\bar{a}}_{v}(\hat{\boldsymbol{y}}_{v}-\boldsymbol{y}_{v})^{\mathsf{T}}}.\,

(52)

我们注意到，需要 (51) 来计算 $\tilde{\mathcal{V}}_{i}$ 上的局部预测，从而获得 (52)。在这个版本的FedStruct-B中，训练过程将分为三个阶段。第 1 阶段相当于每个客户为所有其他客户评估 (51) 并共享结果。这导致每个客户端总共共享 $|\tilde{\mathcal{V}}\setminus\tilde{\mathcal{V}}_{i}|c$ 。第 2 阶段相当于每个客户端评估 (52) 中的本地梯度并将其与服务器共享，类似于原始的 FedStruct-B。接下来，服务器聚合 $\boldsymbol{S}$ 上的本地梯度，并根据每个客户端中的条目对结果进行分区（服务器必须知道客户端中唯一的节点 ID），并仅返回对应的 NSF 梯度到驻留在每个客户端的节点。使用此过程，客户端将仅获得有关与其本地节点相关的 NSF 的信息。

接下来，我们再次考虑诚实但好奇的客户，除了一个之外，所有客户都串通一目标。我们将共谋客户端表示为客户端 $1$ ，将目标表示为客户端 $2$ 。客户端 $1$ 观察(51)，它构成来自 $\mathinner{\!\left\lVert\boldsymbol{a}_{v}\right\rVert}_{0}$ $c$ 维度输入的 $c$ 观察。假设在最坏的情况下，所有 $\boldsymbol{a}_{v}$ 在相同位置都有 $m$ 非零条目，客户机 $1$ 从 $m c$ 输入中总共观测到 $c|\tilde{\mathcal{V}}_{1}|$ 个参数。因此，为了防止客户端 $1$ 完美地重建各个NSF，客户端 $2$ 必须确保 $m>|\tilde{\mathcal{V}}_{1}|$ 。同样，客户端 $2$ 通过计算查询数量来完全控制这一点，确保其低于 $m$ 。

总而言之，我们能够更改 FedStruct-B 以在不影响性能的情况下显示有关各个节点的更少信息。此外，每个客户端可能通过限制与其他客户端共享的信息量来阻止完美重建的实现。超越完美重建并了解近似重建的风险似乎是艰巨的。

表 6： FedStruct 的通信复杂性。

Data	before training	training
FedStruct-A	0	$\mathcal{O}(E\cdot K\cdot\|\boldsymbol{\theta}\|+E\cdot n\cdot d\cdot\|\boldsymbol{\theta}\|)$
FedStruct-A + Hop2Vec	0	$\mathcal{O}(E\cdot K\cdot\|\boldsymbol{\theta}\|+E\cdot n\cdot d\cdot\|\boldsymbol{\theta}\|+E\cdot K\cdot n\cdot d+E\cdot n^{2}\cdot d^{2})$
FedStruct-B	$\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$	$\mathcal{O}(E\cdot K\cdot\|\boldsymbol{\theta}\|)$
FedStruct-B + Hop2Vec	$\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot n^{2})$	$\mathcal{O}(E\cdot K\cdot\|\boldsymbol{\theta}\|+E\cdot K\cdot n\cdot d)$
FedStruct-B pruning	$\mathcal{O}(K\cdot n\cdot d+L_{\mathsf{s}}\cdot p\cdot n)$	$\mathcal{O}(E\cdot K\cdot\|\boldsymbol{\theta}\|)$
FedSage	0	$\mathcal{O}(E\cdot K^{2}\cdot\|\boldsymbol{\theta}\|+E\cdot K\cdot n\cdot d)$

L.2 通信复杂性

在表6中，我们展示了FedStruct-A和FedStruct-BFedStruct-B的通信复杂度t4> 与 FedSage+ 一起。我们将通信复杂性分为两部分：离线部分，负责在训练开始之前发生的事件；在线部分，负责实际训练阶段。表中，参数 $E$ 、 $K$ 和 $n$ 分别表示图中的训练轮数、客户端和节点数。参数 $d$ 为节点特征尺寸（假设所有特征尺寸等于 $d$ )， $|\boldsymbol{\theta}|$ 为模型参数个数（所有模型参数假定具有相同的阶数）。下面，我们讨论 FedStruct 不同变体的复杂性。

•

在 FedStruct-A 中，没有离线阶段。训练过程中，每轮训练，每个客户端都会收集 $\boldsymbol{\theta}$ 并向服务器返回 $\nabla_{\boldsymbol{\theta}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ ，总共在训练过程中通信 $2E\cdot K\cdot|\boldsymbol{\theta}|$ 个参数。这在我们所有的框架中都是一致的。此外，在 FedStruct-A 中，服务器向每个客户端发送 $\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}$ 、 $\forall v\in\tilde{\mathcal{V}}_{i}$ 和 $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{\theta}_{\mathsf{s}}}},\forall v\in\tilde{\mathcal{V}}_{i}\}$ ，总计为 $E\cdot n\cdot d(|\boldsymbol{\theta}|+1)$ 参数。
•

FedStruct-A 与 Hop2Vec 需要一些额外的通信复杂性，对应于客户端 $i$ 收集 $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}},\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}$ ，构成 $E\cdot n^{2}\cdot d^{2}$ 参数，并向服务器发送 $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ ，构成 $E\cdot K\cdot n\cdot d$ 参数。在大图的实际场景中， $E\cdot n^{2}\cdot d^{2}$ 是两者中的主导项。
•

FedStruct-B 需要一个离线阶段，客户端从其他客户端获取 $\boldsymbol{\bar{A}}^{[i]}$ 和 $\mathcal{S}_{i}=\{\boldsymbol{s}_{u},\forall u\in\mathcal{V}_{i}\}$ 。该阶段的通信需求分别为 $L_{\mathsf{s}}\cdot n^{2}$ 和 $K\cdot n\cdot d$ 参数。除了离线阶段之外，与之前的方法类似， $\boldsymbol{\theta}$ 在训练阶段进行联合。
•

具有 Hop2Vec 的 FedStruct-B 与不具有 Hop2Vec 的情况共享相同的离线阶段。然而，在训练阶段，客户端交换梯度 $\nabla_{\boldsymbol{S}}\mathcal{L}_{i}(\boldsymbol{\theta},\boldsymbol{S})$ ，这需要额外的复杂性 $E\cdot K\cdot n\cdot d$ 。
•

在 FedSage 中，特征生成器参数和节点嵌入向量在所有客户端之间共享，分别相当于 $E\cdot K^{2}\cdot|\boldsymbol{\theta}|$ 和 $E\cdot K\cdot n\cdot d$ 参数的通信开销。

讨论。在 FedStruct-A 中，服务器知道全局图，客户端仅与服务器通信。因此，没有训练前的信息交换。在线复杂度的主导项是 $E\cdot n\cdot d\cdot|\boldsymbol{\theta}|$ ，它与 $n$ 成比例。因此，FedStruct-A 的复杂度与 FedSage 的复杂度相同。

在具有 Hop2Vec 的 FedStruct-A 中，主要复杂度项约为 $n^{2}$ ，这对于大型网络来说是不切实际的。然而，应该指出的是，现实世界的图结构数据集是稀疏的。此外，每个节点仅依赖于其 $L_{\mathsf{s}}$ 跳邻居。因此，许多值 $\{\frac{\partial{\boldsymbol{s}_{v}^{(L_{\mathsf{s}})}}}{\partial{\boldsymbol{s}_{q}}},\forall v\in\tilde{\mathcal{V}}_{i},q\in\mathcal{V}\}$ 为零并且不需要传送。假设平均节点度 $\bar{d}$ 和 $L_{\mathsf{s}}$ 层，每个节点都可以访问 $\bar{d}^{L_{\mathsf{s}}}$ 节点，则FedStruct-A的复杂度> 与 Hop2Vec 的数量级为 $\min\{n\cdot\bar{d}^{L_{\mathsf{s}}},n^{2}\}$ 。对于较小的平均度 $\bar{d}$ 和 $L_{\mathsf{s}}$ ，复杂度因此可以显着降低。

FedStruct-B 在训练之前包括一个离线阶段。 FedStruct-B的在线复杂度明显低于FedSage，约为 $n$ 量级。另一方面，FedStruct-B 与 Hop2Vec 的在线复杂度也约为 $n$ 。 FedStruct-B 的离线复杂度约为 $n^{2}$ 。虽然离线复杂性不如在线复杂性那么重要，但对于大型网络来说，按 $n^{2}$ 进行扩展可能不切实际。在附录L.2.1中，我们提供了一种修剪方法来降低这种复杂性，而不会显着影响性能。

表 7：有剪枝（剪枝参数

p=30

)和无剪枝的FedStruct-B的分类精度。修剪结果以粗体显示。显示 10 个客户端的结果，训练-验证-测试分割为 10-10-80。

	Cora			Citeseer			Pubmed
Central GNN	82.06 $\pm$ 1.09			69.17 $\pm$ 0.90			87.71 $\pm$ 0.34
Central MLP	65.31 $\pm$ 1.75			64.18 $\pm$ 0.89			85.80 $\pm$ 0.33
	Louvain	random	kmeans	Louvain	random	kmeans	Louvain	random	kmeans
FedStruct (Deg)	82.14 $\pm$ 0.76	67.83 $\pm$ 2.73	70.82 $\pm$ 0.88	67.98 $\pm$ 1.58	64.13 $\pm$ 1.24	65.46 $\pm$ 2.11	84.65 $\pm$ 0.41	84.87 $\pm$ 0.38	85.31 $\pm$ 0.60
FedStruct (GDV)	80.79 $\pm$ 2.05	72.34 $\pm$ 2.69	73.52 $\pm$ 0.78	68.02 $\pm$ 1.96	65.07 $\pm$ 0.92	66.28 $\pm$ 1.70	84.67 $\pm$ 0.52	85.94 $\pm$ 0.32	85.97 $\pm$ 0.54
FedStruct (N2V)	82.25 $\pm$ 0.86	80.53 $\pm$ 0.88	80.61 $\pm$ 0.91	68.06 $\pm$ 1.85	66.58 $\pm$ 1.16	67.13 $\pm$ 1.23	84.66 $\pm$ 0.55	86.75 $\pm$ 0.30	86.81 $\pm$ 0.45
FedStruct (H2V)	80.81 $\pm$ 1.32	80.00 $\pm$ 1.21	80.01 $\pm$ 1.51	67.99 $\pm$ 1.85	66.73 $\pm$ 1.45	66.93 $\pm$ 1.29	83.97 $\pm$ 0.49	86.05 $\pm$ 0.48	86.25 $\pm$ 0.50
FedStruct (Deg)	81.82 $\pm$ 0.89	69.23 $\pm$ 2.21	71.48 $\pm$ 1.16	68.01 $\pm$ 1.93	63.97 $\pm$ 1.31	65.83 $\pm$ 1.79	84.68 $\pm$ 0.43	84.74 $\pm$ 0.41	85.46 $\pm$ 0.60
FedStruct (GDV)	82.10 $\pm$ 0.63	70.49 $\pm$ 2.53	72.48 $\pm$ 0.82	67.98 $\pm$ 1.82	64.20 $\pm$ 1.06	65.36 $\pm$ 1.90	84.57 $\pm$ 0.50	84.89 $\pm$ 0.34	85.33 $\pm$ 0.54
FedStruct (N2V)	82.18 $\pm$ 1.30	80.38 $\pm$ 0.89	80.18 $\pm$ 0.94	68.00 $\pm$ 2.03	66.34 $\pm$ 1.00	67.29 $\pm$ 1.20	84.46 $\pm$ 0.53	85.77 $\pm$ 0.34	86.06 $\pm$ 0.49
FedStruct (H2V)	80.19 $\pm$ 1.28	79.36 $\pm$ 1.59	79.92 $\pm$ 1.40	67.85 $\pm$ 2.01	66.12 $\pm$ 1.36	66.96 $\pm$ 1.54	82.39 $\pm$ 0.76	84.18 $\pm$ 0.38	84.25 $\pm$ 0.70

	Chameleon			Amazon Photo			Amazon Ratings
	Louvain	random	kmeans	Louvain	random	kmeans	Louvain	random	kmeans
Central GNN	54.43 $\pm$ 2.44			93.99 $\pm$ 0.48			41.32 $\pm$ 1.03
Central MLP	32.15 $\pm$ 1.42			88.68 $\pm$ 0.98			37.56 $\pm$ 0.48
FedStruct (Deg)	41.38 $\pm$ 2.21	48.09 $\pm$ 1.58	42.97 $\pm$ 2.27	91.92 $\pm$ 0.37	89.84 $\pm$ 0.52	89.21 $\pm$ 1.09	41.12 $\pm$ 0.34	38.90 $\pm$ 0.50	39.04 $\pm$ 0.51
FedStruct (GDV)	40.02 $\pm$ 1.89	48.09 $\pm$ 1.05	41.42 $\pm$ 1.89	92.04 $\pm$ 0.46	90.47 $\pm$ 0.68	90.25 $\pm$ 0.97	41.39 $\pm$ 0.43	39.53 $\pm$ 0.34	39.80 $\pm$ 0.47
FedStruct (N2V)	44.72 $\pm$ 1.49	49.48 $\pm$ 0.74	45.84 $\pm$ 2.73	92.03 $\pm$ 0.44	91.65 $\pm$ 0.53	91.48 $\pm$ 0.73	41.70 $\pm$ 0.48	41.63 $\pm$ 0.50	41.48 $\pm$ 0.35
FedStruct (H2V)	52.02 $\pm$ 1.71	52.36 $\pm$ 1.54	53.01 $\pm$ 1.88	92.07 $\pm$ 0.42	91.98 $\pm$ 0.58	91.79 $\pm$ 0.70	41.07 $\pm$ 0.45	40.93 $\pm$ 0.71	40.72 $\pm$ 0.59
FedStruct (Deg)	41.40 $\pm$ 2.19	47.57 $\pm$ 1.18	42.58 $\pm$ 2.24	91.98 $\pm$ 0.41	89.72 $\pm$ 0.50	89.09 $\pm$ 1.10	40.97 $\pm$ 0.38	39.02 $\pm$ 0.42	39.07 $\pm$ 0.43
FedStruct (GDV)	39.67 $\pm$ 2.56	47.58 $\pm$ 1.03	41.34 $\pm$ 1.58	91.94 $\pm$ 0.27	89.75 $\pm$ 0.57	89.02 $\pm$ 0.95	40.95 $\pm$ 0.48	39.02 $\pm$ 0.54	39.29 $\pm$ 0.56
FedStruct (N2V)	44.66 $\pm$ 1.55	49.43 $\pm$ 1.57	45.70 $\pm$ 2.35	91.90 $\pm$ 0.41	90.72 $\pm$ 0.42	90.42 $\pm$ 0.99	41.65 $\pm$ 0.51	41.61 $\pm$ 0.40	41.46 $\pm$ 0.51
FedStruct (H2V)	52.80 $\pm$ 1.97	53.09 $\pm$ 1.59	52.83 $\pm$ 1.73	91.50 $\pm$ 0.40	91.16 $\pm$ 0.71	90.76 $\pm$ 0.81	40.76 $\pm$ 0.51	41.02 $\pm$ 0.56	40.44 $\pm$ 0.52

L.2.1 通过修剪降低复杂性

FedStruct-B 的离线复杂性组件随 $n^{2}$ 扩展，这使得它对于非常大的网络来说不切实际。在本节中，我们介绍 FedStruct-B 的修改版本，它显着降低了 $n^{2}$ 复杂性，同时实现了类似的性能。 FedStruct-B 的此修改版本基于现实世界的图结构数据集通常是稀疏的事实。

其主要思路是在使用附录 G 中的算法 3 获得共享矩阵 $\boldsymbol{\bar{A}}^{[i]}$ 时应用剪枝技术。更具体地说，我们选择一个整数 $p\ll n$ ，在每一轮离线通信中，只保留矩阵 $\boldsymbol{B}_{ijk}$ （最初的维数为 $n_{i}\times n_{j}$ ）的顶部 $p\cdot n_{i}$ 值。因此，复杂度从 $L_{\mathsf{s}}\cdot n^{2}$ 降低到 $L_{\mathsf{s}}\cdot p\cdot n$ 。总体而言，带有剪枝的 FedStruct-B 的复杂度与 FedSage 相同，即约为 $n$ 。表6中提供了具有修剪功能的FedStruct-B的通信复杂性。

FedStruct-B 修剪参数的性能如 Table 7 所示，用于修剪参数 $p=30$ 。可以看出，经过剪枝的 FedStruct-B 的性能与未在所有数据集和分区上进行剪枝的 FedStruct-B 类似。表 7还强调了FedStruct-B针对结构噪声存在的鲁棒性。也就是说，在存在不可靠或嘈杂连接的情况下，可以使用修剪来限制可靠连接，同时实现与所有连接都可靠的情况相当的性能（Fox＆Rajamanickam，2019）。

L.3异质性

与标准 GNN 相比，在 FedStruct 框架内采用解耦 GCN 允许节点访问更大的感受野。这在处理异质图方面被证明是有利的。这是因为在异亲图中，相邻节点可能不提供有关节点标签的大量信息。在这种情况下，来自高阶邻居的嵌入的混合涉及更多数量的同一类节点，从而促进同一类节点之间相似性的增加。高阶邻域混合是处理异亲图的著名方法之一（Zheng等人，2022）。值得注意的是，(Abu-El-Haija 等人，2019) 聚合来自多跳邻居的嵌入，与一跳邻居聚合相比表现出更优越的性能。为了说明为什么高阶邻域有助于异嗜环境，(Zhu 等人, 2020) 从理论上证明，平均而言， $2$ -hop 邻域的标签与当 $1$ 跳邻居的标签有条件独立于自我节点时，自我节点标签。

此外，可以训练或调整参数 $\{\beta_{j}\}_{j=1}^{L_{\mathsf{s}}}$ 来控制不同 $l$ 跳邻居的混合权重。这使得网络能够显式地捕获图中的局部和全局结构信息。具体来说，归一化邻接矩阵 $\boldsymbol{\hat{A}}^{l},\ l\in[L_{\mathsf{s}}]$ 的不同幂从图中的不同位置收集信息。较小的权力会捕获更多的本地信息，而较大的权力往往会收集更多的全球信息。因此，选择适当的参数 $\{\beta_{j}\}_{j=1}{L_{\mathsf{s}}}$ 使模型能够适应图中的各种结构属性。

正如（Zheng等人，2022）提出的那样，解决异性图的另一个成熟策略涉及发现潜在邻居。潜在邻居发现的概念通过识别可能不直接链接到自我节点但在图的不同区域中共享相似邻居模式的节点来拓宽邻居的定义。 Geom-GCN (Pei 等人, 2020) 引入了一种新颖的方法，通过定义几何欧几里德空间并为该潜在空间中邻近的节点建立新的邻域。为此，FedStruct 采用 NSF 来促进节点之间的远程相似性，这些节点在图中可能不是很接近，但在潜在结构空间中表现出接近性。具体来说，使用诸如 Struc2Vec (Ribeiro 等人，2017) 等方法来生成 NSF 可以创建共享相似性的向量，即使在可能不直接存在的节点之间也是如此。连接在图中。因此，这些 NSF 生成的 NSE 也表现出相似性，有助于一致的节点标签预测。这种方法展示了 FedStruct 捕获潜在结构关系的能力，并增强模型在异性图背景下做出准确预测的能力。

FedStruct 在处理异嗜图方面的稳健性在 Table 1 和 Table< 中得到了证明/t5> 5 用于 Chameleon 和 Amazon Ratings 数据集。此类数据集是异性数据集，其中 Chameleon 的异性程度高于 Amazon Ratings（见表 3)。对于这两个数据集，FedStruct 的性能接近中央 GNN，并且显着优于 FedSage+。在 Table 1 中，对于 Chameleon 数据集和 20 个客户端，FedStruct 与 Hop2Vec准确率达到 52.76%，而 FedSage+ 的准确率为 34.33%。对于 Amazon Ratings 数据集和 20 个客户端，使用 Node2Vec 的 FedStruct 的准确率达到 41.77%，而 FedSage+ 的准确率为 36.09%。请注意，对于异嗜性更强的数据集，改进更大。对于不同的分区方法可以观察到类似的结果，参见表5。对于 Chameleon，FedStruct 与 Hop2Vec 的性能优于 FedSage+，对于 Louvain、随机和 K 均值分区分别为 6.33%、16.88% 和 15.73%。对于 Amazon 评级，使用 Node2Vec 的 FedStruct 优于 FedSage+，对于 Louvain、随机和 K 均值分区分别为 0.74%、5.25% 和 4.01%，分别。

我们强调，我们没有专门优化 FedStruct 的参数来处理异性图结构，因此可能可以提高 FedStruct 对于这些异性图的性能。

FedStruct 对不同程度的同质/异质的鲁棒性（与 FedSage+ 等框架相比），强调了我们的框架对不同图场景的适应性和有效性，肯定了其具有广泛应用的潜力。

FedStruct：互连图上的联合解耦学习

摘要

1简介

2相关工作

3 预赛

4系统模型

4.1 节点嵌入

4.2联邦学习

5 FedStruct-A：具有全局图知识的子图 FL

定理1。

证明。

5.1任务相关节点结构特征向量

定理2。

证明。

5.2半监督学习

6 FedStruct-B：不了解全局图的子图 FL

定理3。

证明。

定理4.

证明。

定理5。

证明。

定理 6.

证明。

7评估

8结束语

参考

附录A节点结构特征生成

附录 B 1 的证明

引理1。

证明。

附录C2的证明

附录 D 任务相关 FedStruct-A 算法

附录E4的证明

附录F6的证明

附录G获取𝑨¯[i]

附录 H FedStruct-B 算法

附录 I FedStruct-B 与 Hop2Vec 算法

附录J实验设置

附录 K其他结果

K.1 不同的分区

K.2 标记训练节点数量的影响

K.3 解耦 GCN 中层数的影响

附录L讨论

L.1隐私

L.2 通信复杂性

L.2.1 通过修剪降低复杂性

L.3异质性

附录G获取 $\boldsymbol{\bar{A}}^{[i]}$