Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a generalized node classification model over a distributed sub-graph system without data-sharing. The FedSage is a globally shared K-layer graph classifier model, trained with average gradients over distributed sub-graphs without data-sharing. The awareness of potentially existing links between sub-graphs motivate the authors to design a  missing neighbor model to help improve the performance of the node classifier model named FedSage+, which has been empirically shown to outperform the FedSage. 


main_review: NeighGen, consisting of fGen and dGen, is the model proposed to mend the impaired graph and predict the missing neighbors features. fGen is the linear model (parameter multiplying the feature of node i) to predict the missing neighbors of  node i. And dGen tries to predict the missings based on the output of fGen. As they are both simple supervised linear models  (one layer neural network), their effectiveness to  achieve the author’s primary goal - predicting the missing neighbors’ node features, can be questionable. I would expect the author to conduct simple intermediate experiments to show the power of NeighGen on predicting missing neighbors.

Some notations are not defined before use in this section, although I could infer from context. For example, line 183 $\tilde{x}_i$, the number of missing neighbors for node i, Similarly in the eq. (5), $\tilde{n}_v$ is the estimated/predicted number of missing neighbors and $n_v$ is the ground truth number of missing neighbors for node v. Does the $x^q_v$ represent the raw node features for node v in eq(5)?
I also want to know the details about how the dGen model outputs the integer number as it tries to approximate the true missing neighbors numbers.

Since dGen is a supervised model, I would expect the author to present some statistical results to validate that this linear regression dGen model indeed achieves its goal - predicting the number of missing neighbors.

For section 4.3, I am a little confused about the definition of “without data sharing ”.  For example, in the appendix of FedSage + algorithm, on the data owner side, they all send the node features to the Server, will this behavior violate the rule of “no data sharing”. If this is the case, can a Server directly collect all the information from data owner and process , then distribute the results/trained model to all data owners. 

In table 2, Cora dataset, the FedSage+ outperforms the GlobalSage, which collects all the information without any missing links. What do you think are possible reasons for this?
 
Minor Problems and Typos:
Eq.4, the second $\tilde{n}^i$ should be $\tilde{n}_i$
Line 118, to be rigorous, $i \neq j$ can’t be neglected although that’s obvious from context.





limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigates the problem of subgraph federated learning, with the goal of obtaining a generalized node classification model in a distributed subgraph system without data sharing. To handle this issue, the authors propose a novel framework named FedSage, with interweaving the GraphSage and FedAvg. Besides, a novel missing neighbor generator NeighGen is proposed to tackle the realistic yet unexplored issue of missing cross-subgraph links. Extensive experiments demonstrate the effective performance of FedSage.
main_review: Originality: Conceptually, this paper studies a novel and important setting of graph federated learning, where smaller subgraphs of a larger global graph are separately owned by different local data owners. The setting is well-motivated with an example of healthcare network distributed in individual hospitals (although no real experiments are done in this setting). Technically, this paper then focuses on an interesting and realistic challenge that the links across subgraphs are missing / not collected by any data owner. This challenge is indeed unique for federated learning on graph data with this subgraph setting, and the authors developed novel techniques to address it. Empirically, the authors conducted experiments on four real-world network datasets from the smaller commonly benchmarked ones and some larger ones. The results show consistent performance improvements of the proposed FedSage+ algorithm, but why the improvements are larger in some particular settings are not that clear.

Quality: The techniques developed in this paper are novel and rich. The leverage of GraphSage with FedAvg is straightforward, and the joint training with the NeighGen model for missing link prediction is new. I also find the particular design of NeighGen pretty novel and interesting, which I have not seen in existing works on GNNs, while the joint prediction of numbers of missing links and virtual missing neighbors is reasonable. Section 4.3 is clear but required some reading to really understand, and the sharing of a NeighGen model is probably conceptually related to meta learning, which is not made clear by the authors. The experiments are comprehensive and mostly convincing, although more detailed analysis could be done with the efficiency (I doubt the algorithm with a shared NeighGen, although without many missing links to predict, can still encounter significant communication overhead, which makes Figure 4(c) not perfectly convincing).

Clarity: This paper is overall very well organized, although the detailed writings are occasionally hard to understand, maybe due to some unnecessarily lengthy sentences. Some typos can also be fixed through more careful proofreading.

Significance: This paper focuses on a realistic setting of subgraph federated learning, with identifying and addressing the unique challenge of missing cross-subgraph links. The novel NeighGen module provides a good remedy, and might be of broader interest to the GNN community beyond federated learning. 
limitations_and_societal_impact: Please see Main Review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a federated learning framework for training federated GNNs under the scenario where each dataholder holds disjoint a disjoint subgraph. The paper introduces FedSAGE, which extends GraphSAGE to the federated setting, and FedSAGE+, which further enhances FedSAGE with a missing neighbor generator. The key insight of FedSAGE+ is that the links between subgraphs will be missing, and the neighbor generator is trained to generate missing neighbors. The authors demonstrate their framework using experiments on Cora, Citeseer, Pubmed and MSAcademic, where FedSAGE+ shows improvement over LocalSAGE without the missing neighbor generation. 
main_review: **Strengths**: 
- **Novel setting**. I think this paper considers a novel setting of training GNNs in a federated manner, i.e. each party holds a subgraph, and different subgraphs are disjoint, which motivates the problem of missing links. This should be a novel problem setting to consider the topic. 
- **Clarity**: This paper is in general well written and easy to follow. 

**Weaknesses**: 
- **Unclear how to deal with missing edges.** I appreciate the authors' setting of missing neighbors. However, throughout the paper, I can only see that the authors try to reconstruct the missing nodes $V_i^h$, but not the missing edges $E_i^h$ through optimization. Therefore, I am unclear about how the generated pseudo nodes $\tilde{X}_i$ are connected to the remaining of the graph $\hat{G}_i$. Therefore, I cannot clearly see how the missing neighbor generation is done and contributes to the overall model learning. 
- **Privacy Concerns**. In Eqn. 7, one term of the optimization objective involves $\sum_{j\in [M]\backslash i}\min_{v_q\in V_j^h}\|x_v^p-x^q\|_2^2$. From my point of view, optimizing this requires the knowledge of $x^q$, which are features from other subgraphs. Does that leak privacy (node features)? From my point of view, it does. Please point out if I have any misunderstandings. 
- **Lack of appropriate model analysis**. Please justify the need to use separate NeighGen functions, as no ablation studies on it is done. Also, no ablation studies on parameters are done. I particularly want to see the ablation studies on $\alpha$ in Eqn. 7, as this parameter is related to the use of information from other subgraphs. Also, I want to see the ablation studies on $h$ to see the potential limitations of this model. 

**Minor Comments**: 
- I was wondering how you manage to train GraphSAGE on Cora and Pubmed to >90\%. From my experience, if you use the split given by DGL, in general, I can only achieve a little >80\%. Please justify the need to use another split. 
- Figure 3b, I cannot see the point to show the global distribution of labels, as even if you have the same predicted label distribution, the performance may differ a lot. 
- The formulation in Eqn. 1 seems unnecessarily complex. I find it hard to understand, and the notations are not used afterwards. 
- Plesse consider using larger datasets, such as Reddit, OGB-products. As Cora, Citeseer, Pubmed are somehow small. 

To summarize, due to the limitations in modeling edge information, and the possible leakage of private features, I cannot recommend acceptance at this time. 

===================UPDATE============================

The authors successfully address my confusions and concerns through the discussion. I am willing to raise the score from 4 to 6. 
limitations_and_societal_impact: Limitations are stated.
review_title: null

Meta-review: The paper studies federated learning of graphs. It is assumed that the nodes of the graph are separated between the parties and cross-party edges are not observed. The authors suggest algorithms for learning in this scenario and experiment with them on several datasets.

The reviewers had some concerns about this work, but the authors have used the discussion to explain some ideas. This allowed the reviewers to reach a consensus that this work is above the acceptance threshold.



Decision: Accept (Spotlight)