Unsupervised Federated Graph Learning

R1 to Q1: Thank you for this valuable comment. There are two main reasons for using low-rank tensor decomposition. First, most federated aggregation methods perform parameter aggregation at the matrix level and cannot capture high-order correlations between different clients. The so-called high-order correlation refers to the consistency and complementary information across clients, and low-rank tensor decomposition is used to enhance information fusion between clients. Second, the client weight calculation method based on the number of samples often cannot truly reflect the actual degree of client contribution. For example, although some clients have a large number of nodes, they might be extremely heterogeneous and cannot play a positive role in the optimization direction of the global model. Therefore, an adaptive weight learning method is needed.

R2 to Q2: Thanks for this insightful comment. We expect to learn a set of representative anchors and reduce the running cost as much as possible, so the number of anchors should be small. Since we do not impose any constraints between anchors, for example, different anchors should be as dissimilar as possible. Therefore, too many anchors may cause the collapse of the anchor space, which is not conducive to the alignment of the representation space across clients.

R3 to Q3: Thanks for this meaningful comment. The computation complexity mainly originates from two aspects: the FGW-OT for aligning representation spaces and the low-rank tensor optimization for adaptively learning global model parameters. For the FGW-OT, the computation of $G$ (an intermediate variable) takes $\mathcal{O}(N_{E}M+M^{2}N)$, where $N_{E}$ denotes the number of edges, $M$ denotes the number of anchors, and $N$ denotes the number of nodes. Notably, the adjacency matrices are often sparse, so the computational complexity can be significantly decreased. Likewise, the OT based on Sinkhorn algorithm takes $\mathcal{O}(MN)$. Then, the FGW-OT takes $\mathcal{O}(N_{E}M+M^{2}N+MN)$. For the low-rank tensor optimization, the update of $\boldsymbol{\mathcal{G}}$ with $D_{l,1}\times D_{l,2}\times K$ occupies the dominant computational complexity. First, the FFT and the inverse FFT require $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K))$, where $D_{l,1}$ and $D_{l,2}$ are the dimensions for the $l$-th layer's parameters, $K$ is the number of clients, and $D_{l,1}$ is the higher dimension. Second, the T-SVD costs $\mathcal{O}(D_{l,1}D_{l,2}^{2}K)$. Then, the low-rank tensor optimization takes $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$. Overall, the computational complexity for the proposed FedPAM is $\mathcal{O}(N_{E}M+M^{2}N+MN+D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$.

R1 to W1: Thank you for this good comment. The computation complexity mainly originates from two aspects: the FGW-OT for aligning representation spaces and the low-rank tensor optimization for adaptively learning global model parameters. For the FGW-OT, the computation of $G$ (an intermediate variable) takes $\mathcal{O}(N_{E}M+M^{2}N)$, where $N_{E}$ denotes the number of edges, $M$ denotes the number of anchors, and $N$ denotes the number of nodes. Notably, the adjacency matrices are often sparse, so the computational complexity can be significantly decreased. Likewise, the OT based on Sinkhorn algorithm takes $\mathcal{O}(MN)$. Then, the FGW-OT takes $\mathcal{O}(N_{E}M+M^{2}N+MN)$. For the low-rank tensor optimization, the update of $\boldsymbol{\mathcal{G}}$ with $D_{l,1}\times D_{l,2}\times K$ occupies the dominant computational complexity. First, the FFT and the inverse FFT require $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K))$, where $D_{l,1}$ and $D_{l,2}$ are the dimensions for the $l$-th layer's parameters, $K$ is the number of clients, and $D_{l,1}$ is the higher dimension. Second, the T-SVD costs $\mathcal{O}(D_{l,1}D_{l,2}^{2}K)$. Then, the low-rank tensor optimization takes $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$. Overall, the computational complexity for the proposed FedPAM is $\mathcal{O}(N_{E}M+M^{2}N+MN+D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$.

In addition, we also report the running time on Cora, CiteSeer, and PubMed in Table 1. We can see that the proposed FedPAM does indeed have lower runtime efficiency than most comparison algorithms, but in order to achieve satisfactory results, a longer runtime is necessary. At the same time, it is worth noting that compared to FedU$^2$, FedPAM is still acceptable in terms of runtime.

Table 1: Comparison of running time (seconds) on three datasets.

R2 to W2: Thank you for this interesting suggestion. Privacy protection is an important issue in federated learning, where $\mathcal{E}$ contains client-specific information. Once the centralized server is attacked, this may cause client privacy leakage. The current tensor decomposition method has an explicit bias tensor $\mathcal{E}$. Therefore, in order to protect the client's privacy information from being exposed, we can use the tensor Tucker decomposition to decompose a core (low-rank) tensor and a set of factor (bias) matrix. The mathematic form is written as

$\mathcal{W}=\mathcal{L} \times_1 U_1 \times_2 U_2 \cdots \times_M U_M$,

where $\mathcal{W}$, $\mathcal{L}$, and ${U_{i}}\_{i=1}^{M}$ denote the original tensor, the low-rank tensor, and a set of factor matrix. Since the factor matrices integrate the information of multiple clients, they will not expose client-specific information. Limited by the rebuttal time, we will further investigate a novel method for unsupervised FGL with strict privacy protection in the future.

R3 to W3: Thanks for this insightful comment. In federated learning, low client weights can lead to privacy leaks (for example, by inferring client data distribution or sample information through reverse engineering). To avoid this problem, low-weight clients can be clustered with similar clients based on their data distribution or model parameter similarity to form virtual "super clients." Parameters are first aggregated within the group, and then the group participates in global aggregation, masking individual contributions. Clients within the group share the aggregated weights, preventing individual clients from having too low a weight. This is a very interesting research topic that we will further explore in future work.

R1 to Q1: Thank you for this interesting question. We continue to increase the value of $\lambda$ to test whether FedPAM will encounter a performance bottleneck. The experimental results are reported in Table 2. We can see that when $\lambda$ rises to 500 or 600, FedPAM encounters a performance bottleneck. However, it is worth noting that a larger value of $\lambda$ is conducive to achieving satisfactory performance, thanks to the global anchor-guided representation space alignment. From the experimental results, to achieve satisfactory results, the weight of $\lambda$ relative to SSL weight should be at least 10.

Table 2: Performance comparison with different values of $r$.

R2 to Q2: Thank you for this good advice. In essence, the proposed AGPL module is a plug-and-play component. To verify its effectiveness, we stitch the AGPL module with the existing federated learning algorithm. Notably, we focus on testing the federated learning algorithm without special aggregation methods on the server side. The experimental results are reported in Table 3. We can see that when the existing federated learning algorithm is combined with the proposed AGPL module, the performance will be improved, which illustrates the effectiveness of the AGPL module.

Table 3: Performance comparison when the proposed AGPL is combined with different FL methods.

R1 to W1: Thank you for this rigorous advice. We found that the current form of writing is somewhat unclear. After checking previous work, we changed the forward propagation formula to the following form:

$\mathbf{z}_i^{l+1} =\sigma(\mathbf{z}_i^l, AGG(\mathbf{z}\_{j}^l; j\in\mathcal{N}_i)), \forall l\in[L]$,

where $\sigma(\cdot)$ denotes the activation function, $A G G(\cdot)$ denotes the aggregation method, $\mathcal{N}_{i}$ denotes the neighborhood node set for the $i$-th node.

R2 to W2: Thanks for this good question. Using cosine similarity is a more common method. In Eq. (11), we also use cosine similarity to calculate the similarity between \mathbf{P\}_{k} and $\mathbf{Z}\_{k}$, and then compare the experimental results of different calculation methods in Table 1. The difference in results between using the product and using cosine similarity is not significant. This is because entropy regularization smooths the solution space in the OT calculation, which has a certain normalization effect. Therefore, using the product calculation can still guarantee satisfactory results.

Table 1: Performance conparison with different similarity calculation methods.

R3 to W3: Thanks for this rigorous comment. We will further improve the notations in the following revisions.

R4 to W4: Thank you for this good comment. It is worth noting that Simsiam, SimCLR, and BYOL are the three most widely used self-supervised learning methods, applicable in almost all fields. In the field of graphs, the augmented view is achieved by perturbing the edges and masking some feature elements, while the contrast loss is no different, such as work [1] and work [2]. Of course, there are some more complex graph self-supervised learning methods, however, our focus is on how to achieve unsupervised joint modeling in distributed graph scenarios, and local contrast loss is not the focus of research.

[1] Deep Graph Contrastive Representation Learning

[2] Deep Graph Infomax

R1 to Q1: Thanks for this rigorous comment. $\mathbf{L}_{k}$ is the $k$-th slice of low-rank tensor $\mathcal{L}$ corresponding to the parameters of the kth client.

R2 to Q2: Thanks for this good comment. The original intention behind the optimization objective of Eq. (17) comes from two aspects: The original intention behind the optimization objective of Eq. (17) stems from two aspects: First, matrix-based aggregation methods cannot capture higher-order correlations between different clients, and the complementary information between clients cannot be fully utilized. Therefore, we stack the parameters of different clients into a third-order tensor and use low-rank tensor decomposition in high-dimensional space to explore the complementarity between clients. Second, traditional federated aggregation performs weighted aggregation based on sample size, which cannot adaptively learn optimal parameters. Therefore, we aim to learn a set of adaptive client weights while adaptively aggregating model parameters from different clients to obtain optimal global model parameters. Based on these two aspects, we establish a joint optimization loss, as shown in Eq. (17).

R3 to Q3: Thanks for the good question. When $\mathcal{E}$ is updated, the other variables are viewed as constants, the subproblem is formulated as

$$\min_{\boldsymbol{\mathcal{E}}}\beta||\boldsymbol{\mathcal{E}}||_{1} + \langle\boldsymbol{\mathcal{Y}},\boldsymbol{\mathcal{W}}-\boldsymbol{\mathcal{L}}-\boldsymbol{\mathcal{E}}\rangle + \frac{\mu}{2}||\boldsymbol{\mathcal{W}}-\boldsymbol{\mathcal{L}}-\boldsymbol{\mathcal{E}}||\_{F}^{2}$$ $$= \min\_{\boldsymbol{\mathcal{E}}}\beta||\boldsymbol{\mathcal{E}}||_{1} + \frac{\mu}{2}||\boldsymbol{\mathcal{E}}-(\boldsymbol{\mathcal{W}}-\boldsymbol{\mathcal{L}}+\boldsymbol{\mathcal{Y}}/\mu)||\_{F}^{2}$$

For the $l_1$-norm subproblem, we adopt the solution proposed in the work [3], then obtain the update rule for $\mathcal{E}$, the details can be referred in [3].

[3] The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

R4 to Q4: Thanks for this valuable comment. $r$ is a constant to smooth the distribution of client weights, the larger the value of $r$, the smoother the client weights, otherwise the sharper they are. it is set to 2 on all datasets. We test the FedPAM's performance with differen $r$ in Table 2, it can be seen that most of the experimental results are best when $r=2$, which shows that a slightly smooth client weight distribution is conducive to achieving considerable results. A smooth client weight distribution is conducive to balancing the information of multiple clients, while a sharp client weight distribution will amplify the influence of some clients, resulting in biased fusion.

Table 2: Performance compasiron (ACC %) with different values of $r$.

R5 to Q5: Thanks for this valuable comment. First, unsupervised federated learning is still an unexplored field, with limited works and few available comparison methods. Second, we refer to the baseline setting method of unsupervised federated learning work [5] and conduct three types of comparisons based on model architecture. When using different SSL losses, the comparison methods used are also different, which is determined by the model design. For example, FedU, FedEMA, and Orchestra are based on the architecture with online network and target network. Therefore, when the SSL loss is Simsiam or SimCLR, these methods are not applicable. MOON uses the output of the global model to calibrate the output of the local model, and is also not applicable to the online network and target network architecture. In summary, when using different SSL losses, only some baselines are available.

[5] Rethinking the representation in federated unsupervised learning with non-iid data

R1 to W1: Thank you for this valuable comment. We test the proposed FedPAM with more clients. The experimental results are reported in Tables 1 and 2. We can see that FedPAM can still maintain its leading position in large-scale client scenarios. Although FGW-OT and low-rank tensor decomposition bring a large amount of computation, it is worth it.

Table 1: Performance comparison with 50 clients, where the SimCLR is employed in local training.

Table 2: Performance comparison with 100 clients, where the SimCLR is employed in local training.

R2 to W2: Thank you for this insightful comment. First, due to the problem of data heterogeneity, the problem of representation space misalignment exists in both supervised and unsupervised scenarios. In the unsupervised scenario, this problem is more prominent. We centrally train a GNN model on the Cora dataset to output a representation space close to the ideal. Then we train a global model through FedAvg in the supervised and unsupervised scenarios respectively. Through wasserstein distance (WD) calculation, we found that the WD between the global representation output by the supervised FedAvg and the centrally trained representation is 3.67, while the WD between the global representation output by the unsupervised FedAbg and the centrally trained representation is 9.05. Therefore, in the unsupervised scenario, the representation space misalignment is much worse. At the same time, we also illustrate the problem of representation space misalignment in the unsupervised scenario in Figure 1(a). Second, the inability to adaptively learn optimal global model parameters is a problem common in both supervised and unsupervised federated graph learning. The proposed AGPL is a plug-and-play component that can also be used in supervised federated graph scenarios. In the response to weakness 3, we conducted experiments demonstrating its effectiveness in supervised scenarios. In summary, the proposed FedPAM addresses both the specific challenges of unsupervised federated graphs and the general challenges of federated graph learning, making it a significant work.

R3 to W3: Thanks for this interesting question. In fact, both of the proposed Representation Space Alignment (RSA) and Adaptive Global Parameter Learning (AGPL) can be used in supervised FGL systems. We compared the supervised federated graph learning algorithms with the proposed FedPAM and the experimental results are reported in Table 3. In the local training, the supervised CE loss is added into training loss. Notably, RSA is used to align the representation spaces of different clients, which is especially important in unsupervised scenarios. In supervised scenarios, since the label semantics of different clients are shared, this in itself is a strong alignment signal. Therefore, when only the RSA module is used (FedPAM-RSA), the effect is only slightly improved. AGPL aims to explore high-level correlations between clients and adaptively learn optimal global parameters, which is applicable in both unsupervised and supervised scenarios. Therefore, its performance is superior to FedPAM-RSA. When using the complete FedPAM, FedPAM achieves remarkable results, even surpassing SOTA unsupervised FGL on the CiteSeer dataset.

Table: 3 Performance comparison with various supervised FGL methods.

R4 to W4: Thank you for this valuable comment. The computation complexity mainly originates from two aspects: the FGW-OT for aligning representation spaces and the low-rank tensor optimization for adaptively learning global model parameters. For the FGW-OT, the computation of $G$ (an intermediate variable) takes $\mathcal{O}(N_{E}M+M^{2}N)$, where $N_{E}$ denotes the number of edges, $M$ denotes the number of anchors, and $N$ denotes the number of nodes. Notably, the adjacency matrices are often sparse, so the computational complexity can be significantly decreased. Likewise, the OT based on Sinkhorn algorithm takes $\mathcal{O}(MN)$. Then, the FGW-OT takes $\mathcal{O}(N_{E}M+M^{2}N+MN)$. For the low-rank tensor optimization, the update of $\boldsymbol{\mathcal{G}}$ with $D_{l,1}\times D_{l,2}\times K$ occupies the dominant computational complexity. First, the FFT and the inverse FFT require $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K))$, where $D_{l,1}$ and $D_{l,2}$ are the dimensions for the $l$-th layer's parameters, $K$ is the number of clients, and $D_{l,1}$ is the higher dimension. Second, the T-SVD costs $\mathcal{O}(D_{l,1}D_{l,2}^{2}K)$. Then, the low-rank tensor optimization takes $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$. Overall, the computational complexity for the proposed FedPAM is $\mathcal{O}(N_{E}M+M^{2}N+MN+D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$.

Furthermore, we report the running time of compared methods on three datasets in Table 4. We can see that the proposed FedPAM does indeed have lower runtime efficiency than most comparison algorithms, but in order to achieve satisfactory results, a longer runtime is necessary. At the same time, it is worth noting that compared to FedU$^2$, FedPAM is still acceptable in terms of runtime.

Table 4: Comparison of running time (seconds) on three datasets.

R5 to W5: Thanks for this good comment. In fact, we repeated each experiment five times and reported the mean values. To save space, we did not report the variances. Here, we supplemented the variances for the Cora in Table 5. It can be seen that the variance of the FGL algorithm is relatively small, and these algorithms are generally stable.

Table 5: Performance comparison with standard deviations

R1 to W1: Thank you for this constructive advice. For a comprehensive understanding of the proposed FedPAM, we provide the analysis for the generalization bounds and complexity analysis. Given a FL system, its generalization bound for the global model is defined as Lemma 1.

Lemma 1. Given a FL system with global distribution ${\mathcal{D}}$ and local distribution ${\mathcal{D}}_{k}$, the generalization error for any hypothesis with the probability at least $1-\delta$ ($0<\delta\leq 1$) is

$$\mathcal{R}\_{\mathcal{D}}(h) \leq \frac{1}{K} \sum\_{k \in[K]} \hat{\mathcal{R}}\_{\tilde{\mathcal{D}}\_k}\left(h\_k\right)+\frac{1}{K} \sum_{k \in[K]}\left(d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\right)+\lambda\_k\right) +\sqrt{\frac{4}{m}\left(d \log \frac{2 e m}{d}+\log \frac{4 K}{\delta}\right)}.$$

For the $\mathcal{H}$-divergence $d_{\mathcal{H}\Delta\mathcal{H}}(\tilde{\mathcal{D}}_{k},\tilde{\mathcal{D}})$, we further have

$$\begin{aligned} d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\right) & \leq d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right)+d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_l, \tilde{\mathcal{D}}\right) (K-1) d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\right) & \leq \sum\_{l \neq k}^K\left[d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right)+d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_l, \tilde{\mathcal{D}}\right)\right] \\ \end{aligned}$$

Assume $\forall l \in [K]$, $d\_{\mathcal{H}\Delta\mathcal{H}}(\tilde{\mathcal{D}}\_{l},\tilde{\mathcal{D}})\leq \epsilon\_{0}$, it can obtain

$$(K-1) d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\right) \leq \sum\_{l \neq k}^K\left[d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right)+\epsilon\_0\right]$$ $$\frac{1}{K} \sum\_{k \in[K]} d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\right) \leq \frac{1}{K(K-1)} \sum\_{k \in[K]} \sum\_{l \neq k}^K\left[d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right)+\epsilon\_0\right]\\$$ $$\leq \frac{1}{K(K-1)}\sum\_{k \in[K]} \sum\_{l \neq k}^Kd\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right) +\underbrace{\frac{1}{K(K-1)} \sum\_{k \in[K]} \sum\_{l \neq k}^K \epsilon\_0}\_\epsilon.$$

Then, we have following Theorem

Theorem 1. Given a FGL system with global distribution ${\mathcal{D}}$ and local distribution ${\mathcal{D}}\_{k}$, the generalization error for any hypothesis with the probability at least $1-\delta$ ($0<\delta\leq 1$) is

$$\mathcal{R}\_{{\mathcal{D}}}(h) \leq \frac{1}{K} \sum\_{k \in[K]} \hat{\mathcal{R}}\_{\tilde{\mathcal{D}}\_k}\left(h\_k\right) +\frac{1}{K(K-1)} \sum\_{k \in[K]} \sum\_{l \neq k}^K d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right)+\epsilon+\frac{1}{K} \sum\_{k \in[K]} \lambda\_k+\sqrt{\frac{4}{m}\left(d \log \frac{2 e m}{d}+\log \frac{4 K}{\delta}\right)}.$$

According to the GNN's generalization analysis in [1], we can obtain the upper bound of $d\_{\mathcal{H}\Delta\mathcal{H}}(\tilde{\mathcal{D}}\_{k},\tilde{\mathcal{D}}\_{l})$:

$$d\_{\mathcal{H} \Delta \mathcal{H}}\left(\tilde{\mathcal{D}}\_k, \tilde{\mathcal{D}}\_l\right) \\$$ $$\leq 1+\frac{B\_{rank}}{m} \sup \_f\left\|f\left(G\_k\right)-f\left(G\_l\right)\right\|\_F \\$$ $$\leq 1+\sup \_f B\_W^2 B\_X\left(\frac{D\_{\min }+m}{D\_{\min }^2 m}\right)\left\|\mathbf{A}\_k-\mathbf{A}\_l\right\|\_F+\frac{B\_W^2}{m}\left\|\mathbf{X}\_k-\mathbf{X}\_l\right\|\_F$$

where $B\_{rank}$, $B_{X}$, $D_{min}$ denote relevant constants, $\left\|\mathbf{A}_k-\mathbf{A}_l\right\|_F$ and $\left\|\mathbf{X}_k-\mathbf{X}_l\right\|_F$ measure the divergences between different topologies and features, respectively. Then, we can see that when the topological and feature differences of different client subgraphs are reduced, the generalization ability of the global model will be enhanced. The proposed FedPAM uses FGW-OT to achieve the optimal transport between the global anchor graph and each subgraph, which objectively reduces the differences between different subgraphs. Therefore, the generalization ability of the proposed FedPAM will be improved.

[1] Towards understanding generalization of graph neural networks.

Analysis for Computational Complexity: The computation complexity mainly originates from two aspects: the FGW-OT for aligning representation spaces and the low-rank tensor optimization for adaptively learning global model parameters. For the FGW-OT, the computation of $G$ (an intermediate variable) takes $\mathcal{O}(N_{E}M+M^{2}N)$, where $N_{E}$ denotes the number of edges, $M$ denotes the number of anchors, and $N$ denotes the number of nodes. Notably, the adjacency matrices are often sparse, so the computational complexity can be significantly decreased. Likewise, the OT based on Sinkhorn algorithm takes $\mathcal{O}(MN)$. Then, the FGW-OT takes $\mathcal{O}(N_{E}M+M^{2}N+MN)$. For the low-rank tensor optimization, the update of $\boldsymbol{\mathcal{G}}$ with $D_{l,1}\times D_{l,2}\times K$ occupies the dominant computational complexity. First, the FFT and the inverse FFT require $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K))$, where $D_{l,1}$ and $D_{l,2}$ are the dimensions for the $l$-th layer's parameters, $K$ is the number of clients, and $D_{l,1}$ is the higher dimension. Second, the T-SVD costs $\mathcal{O}(D_{l,1}D_{l,2}^{2}K)$. Then, the low-rank tensor optimization takes $\mathcal{O}(D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$. Overall, the computational complexity for the proposed FedPAM is $\mathcal{O}(N_{E}M+M^{2}N+MN+D_{l,1}^{2}D_{l,2}\log(K)+D_{l,1}D_{l,2}^{2}K)$.

R2 to W2: Thanks for this good comment. We have explained the computational complexity in R1. For the proposed FedPAM, its communication overhead is $2\times(K|\mathbf{W}\_{k}|+KML)$, where $|\mathbf{W}\_{k}|$ denotes the model parameter volume, $L$ denotes the dimension of anchors. Compared to other FGL methods, FedPAM additionally transmit a set of anchors, which are essentially multiple feature vectors and do not take up much communication traffic. For the scalability in practical federated environments, we test FedPAM with large-scale clients, e.g. 50 and 100 clients. The experimental results are reported in Tables 1 and 2. We can see that FedPAM still achieves superior performance.

Table 1: Performance comparison with 50 clients, where the SimCLR is employed in local training.

Table 2: Performance comparison with 100 clients, where the SimCLR is employed in local training.

R3 to W3: Thank you for this valuable suggestion. We added a new unsupervised FL algorithm, namely FLPD [1]. The experimental results are shown in Table 3. It can be seen that the proposed FedPAM achieves more superior performance. The differences between FedPAM and the three works [2][3][4] are from two aspects. First, we propose a new framework for unsupervised federated subgraph learning. To the best of our knowledge, we are the first to study this task. Second, the two proposed modules, RSA and AGPL, are novel and can well address the challenges of unsupervised federated graphs.

Table3: Performance comparison with a new unsupervised FL method FLPD.

[1] Prototype similarity distillation for communication-efficient federated unsupervised representation learning

[2] Federated Contrastive Learning of Graph-Level Representations

[3] Federated Self-Explaining GNNs with Anti-shortcut Augmentations

[4] Subgraph Federated Unlearning