Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a novel PAC-Bayesian analysis for the generalization ability of GNNs on the node-level semi-supervised learning tasks. 
main_review: This paper studies an important problem, the generalization ability of GNNs on node-level semi-supervised learning tasks. The proposed generalization bound is interesting, without relying on very strong assumptions. Experiments on several real-world datasets also demonstrate the effectiveness of the proposed theoretical analysis.

I have the following suggestions:

1. I would suggest the authors provide more details on how the generalization capability is linked to GNN fairness. What's the definition of GNN fairness?
2. Experiments are conducted on several small-scale data. Can it be easily generalized to large-scale graphs? 
limitations_and_societal_impact: None
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the non-IID sample generalization in Graph Neural Networks in a subgroup PAC-Bayesian analysis framework. Non-IID training samples are widely existing in real-world applications. It first derives several interesting theories based on several reasonable assumption on smoothness and node features. Several key observations are found between different subgroups in aggregated-feature and graph distance space support the theoretical discoveries.
main_review: In my opinion, this is a very good paper on two folds. First, non-IID samples are seen everywhere in the real-world applications, where IID annotations are hard to obtain. Without too many assumptions, the PAC generalization bound brings $\epsilon_m$ into the central role of the disparity or distance between groups. Second, the experiment design specifically constructs different subgroups and reproduce the outcome indicated by the theorem. By comparing Figure 2 and Figure 4, the author use the MLP ablation to reveal the graph homophily in an interesting perspective. 

One question:
Is the aggregated feature same as the final hidden representation (before activation) for GCNs? If not, the final hidden representation might be a unified measure for both graph distance and aggregated feature for subgroup.

I believe the proposed analysis framework can guide the fair(unbiased) training of graph neural networks in the community. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the subgroup generalization for graph neural networks. In particular, the authors present a PAC-Bayesian analysis for the generalization ability of GNNs on node-level semi-supervised learning tasks. By some theoretical analysis and empirical results, the authors demonstrate the claims to some extent.
main_review: This paper considers the subgroup generalization for GNNs, which may potentially influence the performance of different subgroups, thus it may partly contribute to the choice of test set in the experiments of GNNs. However, several main concerns should be addressed by the authors.

1. The paper indeed explores accuracy disparity across subgroups by three subgroup split methods, and through the theoretical analysis and empirical results, the diversity of subgroups may more or less involve some disparity across subgroups. But in my opinion, the investigation of influence on performance by different subgroups is a relatively trivial task, which is an easy thing to think about. In particular, the split of subgroups can be regarded as splitting the nodes by some kind of sensitive attribute. In other words, the proposed distance (such as aggregated-feature distance or geodesic distance) can be viewed as one specific kind of sensitive attribute.
Therefore, though with some theoretical analysis, I still think the main contribution of this paper is limited. That is, this paper first proposes several findings on subgroup generalization for GNNs, and then provides some theoretical analysis to these findings, yet no effective models/suggestions are proposed by the authors to deal with the underlying bias (or unfairness). This makes the paper tend to be a technical report.


2. In lines 109-110 of Sect-3.1, the authors said "Note that the analysis on any ... on the entire unlabeled set, as the entire set is a subset". I'm a bit confused here, and why the reason is "as the entire set is a subset"?

3. In Sect-5.1, the two-step aggregated features are calculated and they can facilitate the computation of distances between nodes. However, I doubt that the two-step aggregated features cannot truly reflect the involved feature information of each node in the two-layers aggregation, since in each GNN layer, the GNN model would filter the aggregated information (such as by transformation, or even attention mechanism to assign different weights) for each node instead of directly aggregating. This may impair the credibility of the results.

After rebuttal: I have read the authors' responses, and suggest the authors make further modifications to the current version to make it more solid.
limitations_and_societal_impact: Please see the Main Review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work presents PAC-Bayesian analysis for GNNs under a non-IID
semi-supervised learning setup. It first analyzes the generalization performance
for general settings, and then applies the results to GNNs. The theoretical
results have been backed up with empirical evaluations on several graph
benchmarks.

main_review: This work presents PAC-Bayesian analysis for GNNs under a non-IID
semi-supervised learning setup. It first analyzes the generalization performance
for general settings, and then applies the results to GNNs. The theoretical
results have been backed up with empirical evaluations on several graph
benchmarks.

The theoretical analysis is solid. It provides new theoretical results for
classification problems in non-IID semi-supervised settings. The implications
and findings from the theoretical and empirical results are also interesting,
which suggest that nodes with larger geodesic distance to the training nodes
suffer from a lower classification accuracy.

However, the main analysis is not specific to graphs and GNNs per se. The
majority of the theoretical work is more about PAC-Bayesian analysis for
subgroups under non-IID semi-supervised setting. Theorem 1 & 2 provide the
generalization bounds for stochastic and deterministic settings, respectively.
Theorem 3 applies Theorem 2 to obtain a subgroup generalization bound for GNNs.
However, the required assumption (Assumption 3) can be strong, for which
real-world graphs may not satisfy. Also, the generalization bound in Equation 6
depends on epsilon_m, how can this term be estimated in practice?

The fairness component of this work is relative weak compared to the
generalization performance analysis. Most of the theoretical contributions are
more devoted to generalization performance under the subgroup assumptions, while
the relationships to fairness is marginal. I suggest not emphasizing the
fairness aspect in the title.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The review scores are stable towards "clear accept". Some concerns raised by a reviewer are properly addressed during the discussion period, making the paper have a unanimous consensus. Also, it makes an interesting connection with "fairness" concerning accuracy disparity, thereby opening up interesting problems along with this direction in the community. 
Decision: Accept (Spotlight)