Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper proposes a new graph pooling method by learning the node assignments from a CRF based structure prediction formulation. Different from existing pooling methods, the proposed model explicitly captures high-order structural relationships between nodes via a CRF, and the pairwise energy in the CRF is defined by a $l$-hop connection instead of the original neighborhoods. The paper is written clearly, and the experimental results are good. The sensitivity analysis is also complete.

Integrating CRFs with GNNs for node classification is not new ([1][2][3]), but this paper extended energy definition to capture high-order connections and use it for a new subsequent task: graph pooling. It is interesting and novel, but maybe not very significant. (BTW, it is better to add the related works which combined CRF and GNNs, considering the close connection to this paper.)

The sensitivity analysis in the paper is very useful, but it lacks one important ablation study. To justify the usefulness of CRFs instead of other clustering methods for node assignment, I think there should be a baseline which removes the pairwise energy and just use the unary energy for node clustering. Moreover, the paper may also need to compare with a more recent state-of-the-art pooling model SAGPool [4].


[1]Gao, H., Pei, J., & Huang, H. (2019). Conditional Random Field Enhanced Graph Convolutional Neural Networks. In KDD2019.
[2]Ma, T., Xiao, C., Shang, J. and Sun, J., (2018). CGNF: Conditional Graph Neural Fields. https://openreview.net/forum?id=ryxMX2R9YQ
[3]Qu, M., Bengio, Y., & Tang, J. (2019). GMNN: Graph Markov Neural Networks. In ICML2019.
[4]Lee, J., Lee, I., & Kang, J. (2019). Self-Attention Graph Pooling. In ICML 2019.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The authors here introduces a novel  graph pooling technique called StructPool that uses the underlying graph’s structural information to behave as a node clustering algorithm and learns a node clustering matrix.

Graph level classification requires learning good graph level representation, especially for  aggregating low level information for high . Recent work in pooling does not take advantage of important structural information of the relationship between different  nodes. Here, the authors formulate  graph pooling as a structured prediction problem, control clique set in the CRFs and use mean filed approximation to calculate assignments. 

A cluster assignment matrix assigns each node in the original graph to a cluster in the new graph. The assignment not only depends on the node features but also on the cluster assignment of the other nodes. The authors therefore draw connection with finding the optimal assignment to minimizing the Gibbs energy. The authors propose to learn clustering assignment via CRF conditioned on the global feature representation of the nodes.

The unary potentials of the cliques are computed used the GCN to measure energy of each node. The novelty in accommodating topology information is in using l hop connectivity based on adjacency A to define pairwise cliques thus building pairwise relationship between pairs of nodes thus allowing the Gibbs energy formulation of the cluster assignment thereby using GCN to also compute this pairwise energy. 

I have  a few questions as below:
I think the authors can better elucidate the motivation for using  the attention matrix over Gaussian kernels to measure pairwise energy in section 3.3; an  empirical experiment for drawing comparison wrt to the computational time and number of feature dimensions on a toy problem seems important. 
How is the computation  of the unary potential and pairwise energy influenced by the connectivity of the graph G for the datasets considered? It would be interesting to see how the pairwise energy, unary energy varies over different layers of GCNs. 
Further, how is the cluster assignment affected by the l-hop connectivity? 
Is there a notion of the minimum value of ‘k’ in the context of convergence?
What happens in case of very different graph features, or structural assumptions where the cliques are not enforced? 
Is there a notion of how the method performs on datasets with a high percentage of isomorphism bias: repeating instances or repeating instances with different labels?
It will be interesting to see a discussion on how the performance varies with respect to the depth of the overall architecture,  positioning of the structpool and some results on how effective they are on  hierarchical features and multiple pooling ops as in architectures such as Graph UNet.
Avoid repetition in 2.2 Related work section and in other sections throughout. Otherwise, the paper is rather well written and has clarity.
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: Strength:
-- An interesting idea to use CRF idea to cluster the nodes on a graph for pooling purpose
-- The paper is well written and easy to follow
--  On a few datasets and task, the proposed method works pretty well

Weakness:
-- The computational complexity of the proposed algorithm is on(n^3), which is too expensive 

This paper studied to use CRF to define the cluster assignment of the nodes  for graph pooling, which model the dependency of the cluster assignments between the nodes. Experiments on a few data sets and experiments prove the effectiveness of the proposed approach over competitive baselines. 

Although the proposed approach is interesting and works well on different datasets,  one strong concern I have is the high computational complexity of the algorithm, which is as high as o(n^3) (n is the number of nodes). This limits the applicability of the algorithm to large graphs.  Besides, I also have the following questions:
(1) In the experiments, I assume one CRF pooling layer is used. What would be the results if multiple layers are used?

(2) How did you select the number of clusters K? How would the performance change w.r.t. different K?

review_title: Official Blind Review #1

Meta-review: The paper proposed an operation called StructPool for graph-pooling by treating it as node clustering problem (assigning a label from 1..k to each node) and then use a pairwise CRF structure to jointly infer these labels. The reviewers all think that this is a well-written paper, and the experimental results are adequate to back up the claim that StructPool offers advantage over other graph-pooling operations. Even though the idea of the presented method is simple and it does add more (albeit by a constant factor) to the computational burden of graph neural network, I think this would make a valuable addition to the literature.
Decision: Accept (Poster)