Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper deals with Federated Learning (FL) for graphs. Specifically, the authors investigate FL for heterogeneous graph distributions that can arise when the local graphs belong to different communities within the larger global graph. To tackle the threat of knowledge collapse of the server's GNN model, the introduced method, FED-PUB, tries to identify interrelated local graphs through functional embeddings and aims for their joint improvement. A weighted averaging on the server-side and locally learned weight masks achieve the combined local improvement. The authors evaluate FED-PUB on six different datasets.
strengths_and_weaknesses: Strengths: 

- Combination of FL with the graph-theoretical concept of communities
- An improved design to ensure data privacy and security via functional embeddings of random graphs
- Providing a different perspective on the graph FL problem by aiming to improve local graph models

Weaknesses/Open Aspects:

- Please provide graph statistics to investigate the diversity of your evaluation settings across the six datasets
- Please elaborate on the theory of network homophily and the specific statements you build your arguments on, cf. citation [31]
- Please clarify the necessity of personalized sparse masks and quantify the drift to the local training distribution. Please provide insights for the specific choice of $\lambda_2$.
- For a more transparent comparison, the authors should analyse FED-Pub on the graph partitioning presented in [43]

Minor:

- There is a gap between the provided real-world motivation and the artificially constructed client graphs. Please give some insight into how well the shown setting translates to real scenarios.

### Originality

The topic of FL for graphs has been picked up only recently (most papers are from 2020 and 2021). Within this evolving research field, the authors introduce the challenge of appropriately dealing with heterogeneous graphs on the client-side. The authors combine graph FL with the well-defined notion of community detection from graph theory to address heterogeneous local graphs.

### Quality

- The authors motivate their work well, and the shown evaluation fits their claims
- The methods used are appropriate and clear.
- The presented work is complete with multiple references to the supplement materials
  
Negatives:

- The claims on community detection and network homophily should be supported with additional theory. The authors, however, provide good intuition why their introduced setting and evaluation are valid.
- The authors lack the chance to discuss weaknesses in the paper's main text.

### Clarity

- The paper is well written
- The authors present their work well structured
- The test is mostly self-contained

Minor:

- Introduction to GNNs is relatively shallow
- The authors exaggerate at times, "Seemingly impossible task" (4.1), "an even more serious issue" (1.), and "crucial drawback"
- Cite the inspiration paper [17] earlier

### Significance

- Dealing with FL, this work is essential for areas where data is not publically available due to privacy constraints.
- The benchmark for overlapping and non-overlapping subgraphs is new and can inspire future evaluations for graph FL
- The connection to graph theory (community) is valuable
  
Negatives:

- For a more transparent comparison, the authors should analyse FED-Pub on the graph partitioning preneted in [43]
questions: - The results for FedSage are worse compared to the original publication. How does FED-PUB perform for the subgraph division from [43](<https://proceedings.neurips.cc/paper/2021/hash/34adeb8e3242824038aa65460a47c29e-Abstract.html>)?
- The functional embeddings on random graphs, what are the failure cases of this approach? What if the graph distribution of these random graphs is off? SBM surely does not capture real-world graph properties. How does this translate?
- What is the effect of local graph size vs. heterogeneity and how well are the chosen graphs suited for/ support the presented method.
- Why is it not enough to average parameters according to similarity (Eq.4)? Please clarify the importance of local masks $\mu$ (4.2)?
  
Minor:

- Can you quantify to what degree training runs faster using local masks $\mu_k$?
- What is the influence of the scaling parameter $\tau$ (Eq.4)?
- Why this specific choice of $S(i,j)=\frac{h_i h_j}{\lVert h_i \rVert \lVert h_j \rVert}$ (Eq.3)?
- How are communication costs computed, cf. 52?
- What does the colouring indicate for Fig.6a "Missing edges"?
limitations: -
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper introduces a personalized FL framework to train graph neural network model across subgraphs owned by different clients. The authors argue that the heterogeneity of subgraphs will cause the unexpected knowledge collapse when using the same global model to fit all the data from different subgraphs. The authors first group subgraphs into different communities and then train personalized model parameters for clients in each community by introducing adaptive aggregation weights and unique parameter masks. Experimental results support the advantage of the proposed method FED-PUB on six datasets.
strengths_and_weaknesses: Strengths
	Compared with existing popular methods, the proposed framework achieves competitive results on six popular federated graph benchmarks in a more communication efficient and privacy-preserved manner, without sharing features or embeddings of nodes in graphs. 
	The method to identify the similarity between subgraphs is novel, which uses input-based functional similarity instead of the inner of model parameters (i.e. cossim) to estimate the communities of user data. 
	The proposed method can potentially handle the missing edges problem by only consider the model aggregation in the same community for each client, since the edges and neighbors are dense in the same community.

Weaknesses
	This work tackles the heterogeneity of different subgraphs by mitigating incompatible knowledge collapse when using only one global model to fit all the data. However, the explaination for this incompatibility between different communities is not adequate. I wonder whether the too small model size or the missing edges between nodes cause such incompatibility. Maybe the direct model training on the whole datasets is needed as the oracle case to show such incompatibility.
	The proposed method is not validated in the cases where the nodes and edges of the whole graph are uniformly distributed across clients. Due to the complex distribution of graph data in practice, the performance of the method in such case or cases where there are not obvious communities should be also considered. 

questions: See Weakness.
Plus, why not compare with FedSage+ [43]?
limitations: See Weakness.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes an algorithm for personalized FL subgraph learning, FED-PUB.

The server compute similarities among clients based the output of the local GNNs using random graphs as inputs. It then use them to perform weighted averaging for models.

Each client also learns a personalized sparse mask to select and update only part of the aggregated parameters.

Experiments show the performance.
strengths_and_weaknesses: Strengths:
1. The weighted aggregation based on similarities of outputs of random graphs is interesting.
2. The personalized sparse mask looks helpful.
3. Code is provided.

Weaknesses:
1. The advantages by using outputs of random graphs are not convincing to me. The random graph based on SBM has too much randomness. Especially with random node features with normal distribution.
2. The code only provides fedavg and fedpub. 

questions: 1. Why not directly use local node label distributions to calculate the similarities among clients? The authors could add a comparison with this method.

2. The non-overlapping node scenario is more challenging since it is more heterogeneous. Why does FedAvg (Table 2) in non-overlapping have better performance than FedAvg (Table 1) in overlapping.

3. In Appendix B.3, for small datasets, namely Cora, CiteSeer and PubMed, the experiments set the number of local training epoch as 1. The setting is equal to distributed training. Why does FedAvg perform poorly in this setting? Is it due to missing edges?




limitations: The intuition of weighted aggregation by similarity has been widely adopted. But the mechanism of similarity calculation by a single random input is not convincing to me. A performance comparison with other similarity methods (label similarity, gradient similarity, model similarity) will also be very helpful.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Aiming to solve the data heterogeneity problem in subgraph federated learning (FL), this paper presents a novel research problem, namely personalised subgraph FL. Focus on this personalised FL scenario, the authors propose a new learning method named FED-PUB. To train local models effectively, FED-PUB considers two key designs, i.e., functional embedding-based similarity estimation and adaptive parameter masking. Extensive experiments validate the effectiveness of FED-PUB.
strengths_and_weaknesses: Pros:
1. The research problem is interesting.
This paper first proposes to study the personalized problem of graph federated learning. The novel research problem is interesting and challenging, which may inspire future studies in the community.
2. The experiments are extensive.
The authors conduct sufficient experiments to compare the performance with baseline methods and discover the property of the proposed method. The proposed method achieves outstanding results, which proves its effectiveness.

Cons:
1. The novelty of the proposed method is limited.
Despite some interesting designs in the proposed model, the core idea of this paper is not novel enough and similar to some existing works. For instance, using shared data to calculate the similarity between local models has been proposed in [*1]. There is a branch of works that incorporate auxiliary data to assist the federated training procedure, such as [*2], [*3], and [*4].
[*1] Makhija, Disha, et al. "Architecture Agnostic Federated Learning for Neural Networks." arXiv preprint arXiv:2202.07757 (2022). (Accepted by ICML 2022)
[*2] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." Advances in Neural Information Processing Systems 33 (2020): 2351-2363.
[*3] Sattler, Felix, et al. "Fedaux: Leveraging unlabeled auxiliary data in federated learning." IEEE Transactions on Neural Networks and Learning Systems (2021).
[*4] Zhu, Zhuangdi, Junyuan Hong, and Jiayu Zhou. "Data-free knowledge distillation for heterogeneous federated learning." International Conference on Machine Learning. PMLR, 2021.
2. The relationship between the key design (i.e. weight masking) and the research problem is unclear.
The authors claim that the weight masking mechanism is to select the relevant parameters for each subgraph. However, it seems like a general solution for personalized FL under heterogeneity and is less relevant to the specific subgraph FL problem. Although it brings some performance improvement, how it benefits the node classification problem is unknown.
3. The motivation behind personalized subgraph FL is not convictive enough.
In the introduction section, the authors use an intuitive explanation (with Fig 1) and a tiny experiment on the synthetic dataset to demonstrate the heterogeneity problem and further show the need for personalized subgraph FL. However, how serious the heterogeneity problem on real-world datasets under the subgraph FL setting is still unknown. The real-world experiments, to a certain extent, demonstrate the issue, but what if the clients' number is much smaller than 10? Maybe more comprehensive experiments will better show the significance of personalized FL.
4. The capability of dealing with missing edges is over-claimed.
In Sec 4.1 (Line 230) and Sec 5.2 (Line 348), the authors claim that FED-PUB can handle the missing edges problem in an implicit manner. This is not persuasive enough. In Fig 10, we can still find that FED-PUB(neighbor) has sub-optimal performance, and the performance gap between (local) and (neighbor) is similar among different methods. In another word, the good performance in this setting cannot prove that the performance gain is caused by handling the missing edges problem. 
questions: 1. What is the meaning of J in Eq. (2)? If J is the number of subgraphs within a community, how to find a specific community for each subgraph during model training? And does that mean the aggregation is only executed within the subgraph in a community?
2. In Line 45, the authors claim that the algorithms in [40] and [43] may compromise data privacy. Is there any further evidence to prove that?
3. In the formulation of existing subgraph FL (Line 169) and personalized FL (Eq. (2)), what is the optimized parameter? It's better to highlight this under the "min" operation.
4. Could you provide a theoretical analysis for the techniques proposed in this paper?
limitations: The authors have discussed the limitations and potential negative social impacts in Appendix D.
review_title: null

Meta-review: metareview: The author(s) present(s) a new subgraph federated learning approach to learn a single GNN model that computes embeddings based on the relationship between local graphs. This approach goes beyond the previous approaches that consider the local subgraphs separately.

 The paper is interesting and present some novel ideas but it should address two fundamental critiques by the reviewers before acceptance. In particular the authors should:
- clarify the novelty of their approach(especially considering the missing discussion with previous work)
- improve the experimental section. The current results are interesting but not fully convincing and the experimental section could be improved significantly by including additional settings suggested by the reviewers

Overall, the paper is interesting but it is not ready for publication at this point
confidence: Certain
Decision: Reject