Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces a method called "variational edge partition model" that is generative graph learning framework. VEPM views edges and labels as overlapping community structures. The authors formalize the training of VEPM, and perform experiments evaluating its performance.
strengths_and_weaknesses: Originality: The work has high originality as it views the edges of GNNs very differently compared to existing K-hop GNN idea.
Quality: The work is of quality.
Clarity: The paper is clearly written. I have pointed out a few minor points below though.
Significance. The contribution seems significant as I have indicated above for my point about the work's originality.

Minor points:
- Line 58, put a comma after "From these scores"
- Line 101, end the sentence at "impractical".
- Line 171, typo on "community"
questions: Q1. The location of the "Related Work" is a bit strange. I would actually move it before Variational Edge Partition Model. Is there a particular reason why you did it this way?

Q2. A bit of a theoretical analysis of why the current method works would make the paper more complete. Any plans to include some analysis?

Q3. Why not release the code to make your work reproducible and your claims stronger? 
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposed a variational edge partition method for supervised graph representation learning. The proposed method learns the community affiliation matrix $\mathbf{\Phi}$, generates $K$ partitioned graph representing different communities, and learn from all of when with two stages of GNNs. The idea of partitioning the graph into overlapping latent communities is very interesting, and extensive experimental results showed the effectiveness of the proposed method.
strengths_and_weaknesses: Strengths:

s1. This paper is clearly written and easy to follow.\
s2. The idea of edge partitioning with generative method is very interesting.\
s3. Extensive experiments validated the effectiveness of the proposed method.\
s4. The case study in Figures 3, 5-13 is shows that the proposed method successfully separates the community structures in the graph.

Weakness:

w1. It seems the method needs to back-propagate through all $K$ adjacency matrices $A^{(1)}, \dots, A^{(K)}$, which could be expensive on the space when the graph is large. \
w2. The complexity analysis in Section 4.4 is pretty vague. I wonder if the authors can analyze in exact terms such as $N/K/F$ instead of GCN/GIN.
questions: Other than the weaknesses in the previous section, I also have two more questions:

1. I wonder why many numbers are missing from Table 2. I would suggest the authors to get them if possible.

2. In my understanding, the proposed method need to back-propagate through all $K$ adjacency matrices (as mentioned in w1). If this is correct, then the space complexity should be at least $O(N^2)$ instead of the given one in Section 4.4 (assuming $H << N$). If my understanding is wrong, please clarify.
limitations: n/a
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a novel variational auto-encoder that learns to separate the graph into different communities, and then perform a graph learning task by aggregating over those separate inferred community subgraphs. 

The model works by learning a variational distribution for a node affiliation matrix, which essentially says how affiliated a node is with each community. From that, edges are are sampled using a poisson distribution based on how well adjacent nodes' affiliations overlap. The edges are then partitioned using an edge partitioner. Once partitioned, each community graph goes through a separate GNN encoder, and then the representations are composed using another model. The overall training algorithm has three objective terms corresponding to the classification task, the reconstruction task, and the KL divergence regularization.

The model is evaluated on node and graph classification tasks against a suite of relevant baselines. In addition, multiple visualizations and ablations are performed. 
strengths_and_weaknesses: Originality:

++ Seems to be a novel model overall and involves interesting ideas to learn these community associations through an unsupervised process.

Quality:

++ Paper is a complete work, it is well evaluated. In addition, the authors perform some good ablation studies and visualizations.

-- I would like to see more ablations indicating where the model improvement comes from. How much does the edge partitioner matter? How about the composer? Would replacing these with super simple versions hurt performance? I think there are some questions potentially about where the gains in performance might be coming from

- The analysis of space complexity is incorrect. It shows the parameter space complexity, not the space complexity. For example, if a model requires an N x N adjacency matrix in memory, that is O(N^2) space complexity even if there are no parameters. (This might just be a clarity issue, the authors should specify that this is analysis of the number of parameters).

Clarity:

++ Paper is very well written, and is precise. 

+ Figure 1 is very helpful

- Figure 1 could be improved by incorporating the different loss terms in the diagram.

-Should probably specify that the optimization in equation 6 is maximization. 

Significance:

++ Model is definitely significant in that it improves the state of the art as well as introducing some new ideas.

-- Unclear what the scalability of the method is in practice. No large graphs were tested. 

Grammar/Spelling:

line 116: disjuction -> disjunction
line 271 "amount of label" -> "amount of labelled data"

questions: In no particular order:
(Some of these are just open questions/ablations that do not necessarily have to be performed)

1) In figure 1, should the concatenation of X and Phi be horizontally concatenated instead of vertically?

2) (ablation) What would happen if there was no edge partitioner and all edges were passed to each GNN? Or randomly partitioned?

3) (ablation) What if the composer was just a mean of the representations? Or weighted sum of the representations based on each nodes' affiliation scores? This would further tests the idea that the GNN community bank is doing a significant amount of work. 

4) Are there any datasets with community labels that we could see if the learned communities align with?
limitations: Adequately addressed
review_title: null

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: This works aim at modeling the community structure of graphs via the latent variable of the generative model, that captures which nodes are assigned to which communities and then leverages such information on message passing of GNNs, all of which are trainable in an end-to-end fashion with a variational inference framework. In particular,
* The authors model the community structure in the latent variable of the graph generative process, where they first calculate the affinity scores of nodes to the community and then use that scores for weighting edges during the aggregation of neighboring nodes in GNNs.
* The authors use different GNNs for different communities and then merge representations from them to make a prediction for downstream tasks.
* The authors formulate the proposed community-based generative model over a variational inference framework, making the proposed VEPM trainable.
* The authors verify the performance of the proposed VEPM on node and graph classification tasks and also conduct analyses to see its efficacy.
strengths_and_weaknesses: ### Strengths
* This work models the community structure into the latent variable of the graph generative process, which is reasonable, convincing, and interesting. I like the core idea that, the method captures community structures based on edge weights calculated from affinity scores of nodes to communities, which are then used for aggregating neighborhood features in GNNs.
* This paper is well-structured and easy to follow.


### Weaknesses
* There is relevant work [1, 2] that considers latent community (cluster) structures of nodes, which should be discussed.
* There is relevant work [3] that breaks down the entire training process into unsupervised training for capturing graph (edge) structures and supervised training for performing on downstream tasks, which is similar to this work's training process in Lines 182-192.
* The performance improvements are not significant. Specifically, in Table 2 and 3, the proposed VEPM has huge variances, and, considering the variance, the results are not significant against baselines. Also, the powerful FactorGCN model is only compared on two datasets, namely IMDB-B and MUTAG among eight different datasets, on which the FactorGCN may outperform the proposed VEPM.
* The authors should evaluate on recent benchmark datasets, namely OGB [4]. The used datasets, namely Cora, Citeseer, and Pubmed for node classification; TU datasets for graph classification, are relatively easy and somewhat outdated.
* The analyses on the MUTAG dataset may be problematic. This is a very small dataset only having less than 200 graphs, compared to other datasets (e.g., the PROTEINS dataset has more than 1,000 graphs), and also known as showing high variance due to its size. Thus, I suggest authors analyze their model with larger datasets.

---

[1] StructPool: Structured Graph Pooling via Conditional Random Fields. ICLR 2020.

[2] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR 2021.

[3] Data Augmentation for Graph Neural Networks. AAAI 2021.

[4] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2021.
questions: ### Major Questions and Suggestions
* Firstly, see the weaknesses above.
* As shown in Table 5, if the proposed VEPM including inference and generative networks is trained jointly without pre-training, it totally fails on downstream tasks when comparing its performance to other baselines. More explanations are needed for this particular behavior.
* I am wondering does the captured community by the proposed VEPM follow the community pattern extracted from existing community detection methods, for example, the METIS graph partitioning algorithm.


### Minor Questions and Suggestions
* Explaining how the generated edge weights are used in GNNs may be necessary. The form of a GNN layer in equation (1) lacks an expression of edges during neighborhood aggregation, which might be confusing for readers who are not familiar with GNNs.
* The claims on "state-of-the-art graph classification performance" should be tone-downed. The compared works are mostly before 2021, and there are lots of works achieving remarkable performances [2, 5]. 
* More analysis of the temperature scaling value in equation (4) would be valuable. I would like to see the chaining communities of the proposed VEPM by varying the temperature value (i.e., from soft to hard community assignments and their performances).
* The visualization in Figure 3 is extremely hard to see when I see this in a printed version. I would like to suggest authors visualize lesser nodes (e.g., 50 instead of the current 200).


---

[5] MaximumEntropy Weighted Independent Set Pooling for Graph Neural Networks. arXiv 2021.
limitations: The authors discuss the limitations and potential societal impact of their work in Section F of the supplementary file.
review_title: null

Meta-review: metareview: This paper has novel ideas and good experimentations, and is well written. In particular, the novelty is a highlight in this paper, as compared with many existing k-hop ideas. Overall, it is a good addition to the general GNN literature. There was some initial disagreement on the evaluation of the method, which was later addressed by the authors' detailed response.
confidence: Certain
Decision: Accept