Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper develops Edge-Partition Modulated Graph Convolutional Networks, a GNN architecture that explicitly models latent relations between nodes in a graph. The key idea is that nodes may be organized as overlapping "communities", where each community represents a particular type of relation. For example, in a citation network of papers, where the task is to predict the category of each paper, all papers from a research group could form one latent community. If one could infer this latent community information, then this could help predict unknown labels.

To accomplish this task, the model learns a community affiliation matrix whose entries express how strongly each node is affiliated to a particular community. Once we have this matrix, the adjacency matrix is partitioned as a sum of K adjacency matrices, where K is the number of communities. The model then runs K different GCN models using the same node features but K different adjacency matrices, and the outputs of all these GCN models are concatenated. Finally, we apply a GCN model using these composite node features and the __original__ adjacency matrix, to get a final classification for each node. These GCN models together comprise the "generative network".

The different weights are learned using an intricate training procedure. First, the model learns a good initial community affiliation matrix, by maximizing the posterior probability of the community matrix given the adjacency matrix. This stage is entirely unsupervised, because it uses only the observed edges and not the edge labels.

In the next stage, the model iteratively runs inference (where the community affiliation matrix is learned by optimizing the ELBO using label supervision) and learning (where the community matrix is held fixed but the generative GCN models are trained). Inference and learning are repeated till convergence.

Finally, a community matrix is sampled from the learned posterior and this is used along with the generative network to predict unknown labels.

The authors evaluate their model on a variety of node classification and graph classification benchmarks. They also visualize some embeddings for better interpretability, and perform some ablation studies.

main_review: **Strengths :**

1. Novel technique. While community detection has been explored before, using this community information to predict better labels is something that I have not come across. The model training procedure with the unsupervised pretraining followed by iterative supervised learning is interesting.
2. Thorough evaluation across 11 datasets to demonstrate that the model works well in practice.

**Weaknesses :**

1. Problem needs to be better motivated. What are some examples of real world datasets with latent relations/communities? For example, what could be the latent communities in a citation network? I made an attempt to construct an example in the summary section above based on my understanding, but it would be nice to see something of the sort in the introduction.

2. The ablation studies aren’t very comprehensive - they only compare across a) different input features, b) different numbers of latent communities, and c) different numbers of GCN layers. A better ablation study, in my opinion, would be to modify key parts of the model and not just change hyperparameters. Example - what is the performance with and without the unsupervised pretrain? What if we didn’t compose $X$ with $\Phi$ to get $X*$?

More thoughts / Questions for the authors :

1. In the Edge Partitioner module, is $\tau$ always chosen such that the generated adjacency matrices are binary? I assume that must be so, because otherwise one cannot apply a GCN to a non-binary adjacency matrix. But it would be nice to have this clarified.

2. Do all the baselines use hand-crafted features as in Xu et al (2019)? I couldn’t find this mentioned anywhere.

3. Here is a thought - what if we were to take a multi-relational graph, homogenize the edges, then see what latent relations are predicted by your model and how well they track the original relations that we started with?

Minor comments :

1. It would be nice if the $||$ notation for concatenation could be explicitly defined somewhere. It becomes obvious after a little more reading, but it confused me the first time.

2. Typos - “interatively” (page 5), “represnetation” (page 7), “edge-formation contributionedge-formation contribution” (page 9).
summary_of_the_review: Overall this paper makes an interesting contribution to the field. The technique/key idea are, in my opinion, novel, and the evaluation is thorough. My concerns are limited to the problem motivation as presented in the paper, and the extent of the ablation studies.

It is possible that my understanding of the variational inference and ELBO optimization part is insufficient. I have not checked these parts for correctness, and I am not familiar with related work in the area. I have therefore indicated that my confidence in my assessment is slightly lower.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper investigates how an edge is formed by different latent inter-node relations and extends the community-based edge formulation mechanism to graph neural networks. A variational inference framework has been proposed to jointly learn how to partition the edges into different communities and combine relation-specific GCNs for the end classification tasks. Experiments on several real-world graph datasets demonstrate the effectiveness of the proposed method in both node-level and graph-level representation learning problems.
main_review: Overall, this paper is well-organized. It is interesting to investigate how an edge is formed to make use of the inter-node relation to enhance GNNs for node representation learning. Experimental results on several graphs demonstrate the effectiveness of the proposed method in both node-level and graph-level tasks.

However, I have some major concerns:
- Lack of theoretical analysis. There is no theoretical analysis of the proposed method especially on the relationship between community information and embedding propagation.
- Studies of different relations. Although the aggregated representations of all relations have been visualized in Figure 2, it may provide more information to explore each relation in contributing to form edges and learning representations.
- Performance of community learning. Although in the visualization some community structures have been shown in Figure 2, it would be interesting to show quantitatively the performance of community detection.  

There are some minor comments:
- Why Community ENCoder is part of model training?
- Notation r has been used as parameters on Page 3 and also as relations on Page 4.
- what does RHS mean under Eq (3)?
- There are some typos:  (1) In REPresentataion COMPoser: denotes -> denote, after Eq (3), Where -> where
summary_of_the_review: The paper provides an interesting and novel solution to learn better representation with the investigation of edge formulation. However, several claims are not well-explained.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposed a edge partition based graph neural network model. It samples a K sets of edges based on learnable node affinity matrixes. A composer layer is used to combine node representations from each partitions. To improve training stability, the paper trains the edge partition part first with unsupervised then finetune it on supervised learning task. Built upon mature techniques, the authors suggest this model has superior performance with experiments on both node classification and graph  classification data.
main_review: Strengths:
1) The proposed methods perform favorably in the experiments.
2) The presentation of the paper is clear and easy to follow.

Weakness:
1) The motivation of designing such partition based GNN is not clear. Why it is important to consider the latent inter-node relations? What are the implications should such relations are ignored assuming their existence? 
2) It lacks a comprehensive analysis of the learned partition weights (called node community affinity matrix). While the paper provides the T-SNE plot of the learned matrix, there are not quantitative measure of the properties of learned affinity. Do these K groups of affinity scores have similar structures? Are there clear pattern of partitions when we adjust the temperature parameter?
3) The ablation study section misses a few important dimensions. a) The impact of doing pretraining step introduced in this paper. And why there are instability issues with end-to-end training. Is it sensitive to any of the parameters of the node affinity matrix? b) Does the proposed method only work with GNN? 
4) The methods proposed in this paper are based mature and well-known techniques. The novelty is limited.
summary_of_the_review: This paper uses the graph generation model and a soft-max transformation with temperature term to implement the idea of doing K graph edge partitions in side GNN computation. The presentation of paper is well organized and experiments results are generally favorable. However, the motivations and assumptions are not discussed clearly and verified carefully. The ablation study does not address some of the key design in this model. The overall novelty of this paper is limited.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This article proposes a new architecture to solve node and graph classification tasks. The main idea is that an initial transformation is used to map nodes to K different communities, after which community-independent node features are computed and used together to classify the nodes/graph. The training process undergoes an initial unsupervised pre-training stage, followed by a supervised finetuning stage that, for some reason not well understood, alternates the optimization of two supervised objectives (one of which is included in the other), by fixing different parts of the end-to-end architecture at each step.

main_review: Apart from statements that need clarification or adjustments, the paper is generally well presented and organized. Technically speaking, there are three main issues with the submission that can be summarized by: i) lack of proper motivations for the proposed architecture; ii) missing or ambiguous technical details; iii) robustness of the empirical evaluation. This review will proceed by sections, by listing major and minor comments to provide a feedback as complete as possible.

### Abstract

#### Major

From "In this paper" to "OR mechanism", the text is too dense and does not help the reader grasp the intuition of what is happening. Also, it is not clear why modeling latent node communities should be important to solve the main supervised task (point i) above).

#### Minor

"have demonstrated the working mechanisms" should be removed, as the paper does not fulfil the promise made by the authors.

### Introduction

#### Major

When referring to GCNs works, the authors did not mention two of the earliest works in the graph learning literature, namely GNN (Scarselli et al, 2009) and NN4G (Micheli, 2009). It is recommended that at least these two works are added to the paper.

From "the absence of relational inference" to the end of the paragraph: this statement looks like pure speculation unless supported by scientific evidence or concrete examples. 

The paper seems to lack proper motivations, apart from the "need of modeling latent communities". Since the empirical evaluation relies on numeric results and a qualitative visualization, it is unclear why one should really need to model latent communities by using multiple GCNs. It is strongly recommended that the authors provide convincing motivations and justification for the development of their approach, other than stating that "it performs better" (see my comments below on the empirical evaluation).

#### Minor

Q: why is the GAT aggregation too "ad-hoc"? It seems pretty general and completely adaptive. And what does "ad-hoc" refers to?

Q: could the authors please describe how and why "extra information provided with the observed edges remedies optimization issues caused by the scarcity of label supervision"? Otherwise this seems another claim unsupported by evidence (either from the paper or from the literature).

Q: what are "observed (target) labels"? Are we considering a specific kind of task that considers unobserved and observed targets, like the semi-supervised setting of node classification? If that is the case, the authors should specify it, since that statement does not hold in general.

Please avoid using terms like "insatiable".

### Methodology

#### Major

The use of the terms "generative" and "inference" in contraposition can create confusion among readers. One of the reasons is that  the term "generative model" is often synonym of probabilistic models that perform inference, so "reconstruction" or "community encoder" could be more appropriate and disambiguating here. This distinction seems to confuse the authors as well: the "generative" model is associated with parameters \theta at the beginning of Section 2, but it seems that it is the other way round, with the parameters of the community encoder being \omega.
It would also benefit the presentation to state what is the role of the generative and inference models, to have a clearer picture in mind of what is to come.

Notation-wise, at this stage it remains unclear why the distinction between y_o and y_u has to be made, and the symbols representing the original and reconstructed adjacency matrix coincide. 

The last statement of Sec 2.1.1 is crucial to the justification of your work, but it is again unsupported by scientific evidence.

Throughout the full text, there seems to be no reference whatsoever to the temperature values tried in the experiments. Please specify them.

The manuscript would probably benefit from a descriptive and empirical comparison with respect to Relational GCN (Schlichtkrull et al 2018), to understand why and whether or not your inductive bias is really more effective. For instance, R-GCN could be applied to the different adjacency matrices identified by the community encoder, as if edges had different types.

There is not proof or derivations for the equations of the community encoder in Sec 2.2.1, and the analytical expression of L_KL should be described somewhere.

From "and the model design that involves... to the end of the paragraph": this is another claim unsupported by scientific evidence, and it is even not very clear. It could be better to drop it or add some support to it.

Since the model is end-to-end trainable, it is not completely intuitive why the supervised finetuning stage should alternate between two different supervised optimizations, one of which is included into the other. The suspect is that this is a choice driven by necessity of convergence than to make the edge partition "more facilitative to the classification task". It would be appropriate to conduct an ablation study in which the model is finetuned in an end-to-end fashion, to show that this peculiar training strategy is indeed effective. Note that, at this stage of the article, it is still unclear what is the purpose of y_o and y_u.

Setting S=1 cannot be justified by mere simplicity. The value of S has an important effect on the quality of the approximation, so it would be appropriate to rephrase that or conduct a study that shows how S=1 is indeed sufficient to provide good performances.

#### Minor

Q: what is the meaning of "unsupervised parts of labels"?

It would help the discussion to see an actual example of community-specific adjacency matrices, as well as computing a discrepancy score between them.

Please refer to equations instead of "link functions"

"K positive-weighted edges" --> "K positive-weighted matrices"

"edge partitioner represents" --> represent refers to "edge weights", please correct these severe mistakes across the manuscript.

Could the authors please define "underqualified" and "data-label ratio"? This would help the comprehension of the manuscript.

### Empirical Evaluation

#### Major

All empirical evaluations in the paper follow protocols that have been heavily criticized by the community [1,2], either because they  are unfair, not robust, optimized wrt the test set, or all of the previous. The node classification tasks should have averaged the results over different train/val/test splits, and the 10-fold cv procedure of Xu et al. is known to optimize hyper-parameters on the test set. For these reasons, the empirical results in this paper should not be considered of sufficient quality, and the authors should set up a proper empirical evaluation. This includes:

1) Being clear in separating model selection from model assessment, as well as stating the protocols used in the paper
2) Testing a sensible amount of hyper-parameters configurations during model selection, rather than fixing most of them like in this paper. This is a computationally heavy phase, but it cannot be avoided in general.
3) Conducting ablation studies and hyper-parameters sensitivity tests as part of the output produced during model selection (on the validation set). In this paper, it is evident that the results of Table 3 are the result of the analysis of different configurations of Table 5, meaning the hyper-parameters have been optimized on the test set (see MUTAG and PTC, for example). The effect of hyper-parameters should never be studied on the test set.

[1] Shchur, Oleksandr, et al. "Pitfalls of graph neural network evaluation." arXiv preprint arXiv:1811.05868 (2018).

[2] Errica, Federico, et al. "A fair comparison of graph neural networks for graph classification." ICLR 2020.

summary_of_the_review: In light of the above considerations, the paper needs substantial rewriting and the empirical evaluations must be done following a proper protocol. It cannot be accepted as is, and probably there is no time to properly fix these points in the rebuttal phase.
review_title: null

Meta-review: The weaknesses of the paper can briefly be summarised as follows: i) the suggested motivation is not so clear, and in addition the experimental results (by themselves questionable in the way they are obtained) do not support the main claim of the paper that "...edges are generated by aggregating the node interactions over multiple overlapping node communities, each of which represents a particular type of relation that contributes to the edges via a logical OR mechanism." In fact, the observed separation among components is not proven to be of the predicted nature. ii) empirical results are obtained using a deprecated experimental protocol. For the field to make real progress, experimental assessments should follow statistically sound protocols. Already published papers that were not following a sound protocol should not be taken as reference for future empirical assessments.
The last point alone is a strong motivation for rejecting the paper.
Decision: Reject