本文旨在解决不同子图作为不同的client，由于client是locally accessible，所以client间存在的missing edges无法被server捕获的情况。与FedSage仅仅基于自身连接来expand missing neighbors（并且最小化生成neighbor和其他所有子图的距离） 的missing neighbors生成方式不同，本文提出的FedPub考虑了子图的社区结构，即不同社区的子图相互之间的边连接关系应该较弱，处于同一个社区的子图应存在更强的边连接关系。

Personalized Subgraph FL (Overall)

对于每个子图 $G_i \in \mathcal{G}$，传统的方法优化方式是学习global optimal parameters $\bar{\theta}$，使得该参数在所有clients上的总loss最小： $\min_{\overline{\theta}} \sum_{G_i \subset \mathcal{G}} \mathcal{L}\left(G_i ; \overline{\theta}\right)$。但是由于处在不同社区中的子图异质性很严重，并且不同社区的子图间的edges也很稀疏，这种强异质性很难学习到一个对所有子图都最优的 $\bar{\theta}$。因此本文提出，在同一个community的子图间共享参数，不同community的子图不共享参数，而不是使用全局通用参数 $\bar{\theta}$。因此，Personalized Subgraph FL的形式如下：

$$ \begin{aligned} & \min_{\left\{\boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right\}_{i=1}^K} \sum_{G_i \subseteq \mathcal{G}} \mathcal{L}\left(G_i ; \boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right), \quad \boldsymbol{\theta}_i \leftarrow \boldsymbol{\mu}_i \odot\left(\sum_{j=1}^K \alpha_{i j} \boldsymbol{\theta}_j\right) \\ & \text { with } \alpha_{i k} \gg \alpha_{i l} \text { for } G_k \subseteq C \text { and } G_l \nsubseteq C \end{aligned} $$ 其中 $K$是client数量， $\theta_i$是属于community $C$ 的client $G_i$的可训练权重， $\alpha_{ij}$是client $i$ 和 $j$的权重聚合coefficient。如果client $k$和 $i$属于同一个community，而client $l$和 $i$不属于同一个community，那么它们关于 $i$的参数聚合系数 $\alpha_{i k} \gg \alpha_{i l}$。通过这种方式模型可以隐式地考虑不同subgraph之间的关系。

虽然 $\alpha_{i,:}$指示了client之间的相关程度，但是未能指示那些参数与 $i$ 相关，这里用一个size和 GNN 权重相同的mask矩阵 $\mu_i$来过滤无关权重。

FedPub (Detailed)

为了实现上式，首先要基于子图之间的相似度为图中的子图分配communities。由于每个子图是local accessibility的，服务器只能接收到每个client的GNN参数，所以需要从子图的GNN模型参数中获得辅助信息来计算子图之间的相似度。

Functional Embeddings for Subgraph Similarities

为了解决上述问题，本文通过向所有 local GNN 模型提供相同的输入，然后使用它们的输出计算相似度来测量 GNN 的functional similarity。基于stochastic block model构建一个有5个communities，每个community 100个节点的random community graph $\tilde{G}=(\tilde{\mathcal{V}}, \tilde{\mathcal{E}})$。令 $\tilde{\boldsymbol{h}}_i=\operatorname{AVG}\left(f\left(\tilde{G} ; \boldsymbol{\theta}_i\right)\right)$表示client $i$上的局部模型对 $\tilde{G}$的所有node embedding输出的均值。那么client $i$和 $j$之间的GNN functional similarity 可以用下式表示：

$$ S(i, j)=\frac{\tilde{\boldsymbol{h}}_i \cdot \tilde{\boldsymbol{h}}_j}{\left|\left|\tilde{\boldsymbol{h}}_i\right|\right|\left|\left|\tilde{\boldsymbol{h}}_j\right|\right|} $$

Personalized Weight Aggregation

在得到子图之间的相似度衡量标准后，对于client $i$，可以计算client $j$与它的normalized subgraph similarity：

$$ \alpha_{i j}=\frac{\exp (\tau \cdot S(i, j))}{\sum_k \exp (\tau \cdot S(i, k))} $$

其中 $\tau$是一个相似度放缩参数。然后在同一个社区中的client尽可能共享更多的参数：

$$\overline{\boldsymbol{\theta}}_i \leftarrow \sum_{j=1}^K \alpha_{i j} \cdot \boldsymbol{\theta}_j$$

Adaptive Weight Masking

上面加权聚合所有client local GNN参数的方式得到 $\overline{\boldsymbol{\theta}}_i$只考虑到how much each local model from other clients is relevant to $i$，因为 $\alpha_{i j}$仅用来衡量client $j$与client $i$在社区层面的相关程度，然后就依据相关性聚合来自client $j$的所有参数 $\boldsymbol{\theta}_j$。并没有考虑到聚合而来的参数 $\overline{\boldsymbol{\theta}}_i$中，哪些与client $i$是相关的。因此这里用一个可学习的参数mask $\boldsymbol{\mu}_i$来从 $\overline{\boldsymbol{\theta}}_i$中过滤出与client $i$有关的参数：

$$ \boldsymbol{\theta}_i=\overline{\boldsymbol{\theta}}_i \odot \boldsymbol{\mu}_i $$

这里得到的 $\boldsymbol{\theta}_i$作为client $i$上local GNN的参数。对于local client的训练过程，由于 $\boldsymbol{\mu}_i$仅在本地数据上训练，并不与其他client共享参数，因此容易与本地数据过拟合，即完全mask掉所有其他client的信息。为了缓解该问题，在局部损失函数上添加一个proximal term来使得 $\boldsymbol{\theta}_i$保留更多全局模型信息： $$ \min _{\left(\boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right)} \mathcal{L}\left(G_i ; \boldsymbol{\theta}_i, \boldsymbol{\mu}_i\right)+\lambda_1\left|\left|\boldsymbol{\mu}_i\right|\right|_1+\lambda_2\left|\left|\boldsymbol{\theta}_i-\overline{\boldsymbol{\theta}}_i\right|\right|_2^2 $$