Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents a new GNN architecture, which performs message passing on a hierarchical H-tree structure constructed from the original graph. Nodes in the H-tree represent subgraphs of the original graph, and thus message passing on H-tree can achieve higher expressive power by going beyond the node-to-node communication. Theoretical results show that the proposed neural tree architecture can approximate any smooth probability distribution function over an undirected graph. Such expressive power is achieved with number of parameters exponential with the width of the H-tree and linear with the original graph size. Experiments on a scene graph and a citation network show neural tree with existing GNN aggregation functions outperform the corresponding GNN alone. 
main_review: ## Originality

The idea of constructing an H-tree for GNN message passing seems quite original. The theoretical results on approximating any smooth probability distribution over undirected graphs also bring novel insights on the expressive power. 

Although the idea of tree decomposition (e.g., constructing junction tree) and passing messages among tree nodes is known in the literature of probabilistic graphical models, it is valuable to extend such decomposition to the H-tree structure and further make connection to the GNN models. 

## Quality

The overall algorithm design seems reasonable, although there does exist some part that seems unintuitive (see "other questions on the model design"). My main concerns on the design are with respective to scalability and generalization. My main concern on the experiments is whether they can scientifically validate the theoretical claims. Overall, even though the model enjoys some nice theoretical properties (under some strong / unrealistic assumptions, see "questions on the proof"), I doubt if it can have much practical use. 

**Scalability and generalization**

From Theorem 7, the number of parameters of a neural tree is proportional to the number of nodes in the graph. From Eq 8, we also see that each node needs to have its own aggregation parameter $a_{u,t}$ and $b_{u,t}$. This makes the scaling of neural trees to large graphs quite challenging. Intuitively, this can also hurt generalization, since the learned model is so tightly coupled with the specific input graph structure. The experiments also seem to indicate the issue in generalization (small number of training nodes corresponds to lower accuracy of NT-GCN than GCN). Note that this is not the case for other GNN models. For example, GIN can establish the equivalence with 1-WL by sharing all weight parameters among all nodes. Overall, I feel that letting each node have its own parameter seems to be a restrictive setup, and this may make the theoretical results less interesting. 

As for the scalability, there are many factors in the design that may hurt scalability to large graphs. For example, the total number of parameters need to be exponential with the tree width and linear with the graph size. It is argued that the tree width can be practically reduced by subsampling. However, the expressivity analysis does not hold under subsampling, and the tree width may grow with the graph size. Even the tree decomposition step can be quite expensive: the $O(E(k^2+ V))$ complexity is polynomial with the graph size, but can be practically very expensive already (e.g., consider the medium scale graphs with 1 million nodes in the Open Graph Benchmark). 

In addition, it would be nice if the authors can profile the total training time to understand the tradeoff between computation complexity and accuracy for the proposed NT model. 

**Questions on the proof**

For the supporting Lemma 6 of Theorem 7, the assumption that $\Sigma h$ is bounded within 0 and 1 seems quite unrealistic. Each $h$ is between 0 and 1, and how can the sum be bounded? Is it even a valid assumption?

For Theorem 3, how can we directly conclude from Eq A17 that $f$ is $G$-compatible? In other words, there seems to be a missing connection with max cliques of the graph?

**Questions on the experiments**

Please clarify the aggregation function of NT-GCN used in experiments. Does the aggregation follow Equation 8, or does it have parameter sharing among nodes? If NT-GCN does not have different $a_{u,t}$ and $b_{u,t}$ for each $u$, then I regard this as major discrepancy between the theoretical and experimental setups. The experiments thus cannot verify the analysis on expressive power, and also can hardly resolve the concern on generalization. 

The scalability and generalization concerns are similarly posed to the experiments. The evaluated datasets are both very small, indicating the challenge in scalability. 

As for baselines, more expressive models such as GIN and GAT may be more reasonable than GCN, since the main claim in the paper is w.r.t. improvement on expressive power. Therefore, for the citation network, it may be better to also include evaluation on GIN, GraphSAGE and GAT. 

**Other questions on the model design**

I wonder the intuition behind applying aggregators such as GCN on H-tree. On the original graph, the GCN can learn its spectral property, and the aggregation operation can be understood as smoothing of the node features. However, with NT-GCN, what are the meaningful spectral properties associated with the H-tree structure? In addition, since the H-tree nodes follow an explicit hierarchical relation (e.g., leaf and root), would it be more reasonable that the aggregation makes use of such hierarchy? In the current design, the aggregation doesn't differentiate if a neighbor is a root or a leaf. 

What is the relation between the design by Eq 8 and the other designs such as NT-GCN and NT-GraphSAGE? For example, for NT-GraphSAGE, does it still have a learnable parameter, $a_{u,t}$, distinct for every node $u$, or does it simply perform mean of features. 


## Clarity

The paper is clearly written. The neural tree design is illustrated with examples, which helps with understanding. It would be better to clarify a few doubts on the theoretical results, as listed above. 


## Significance

On the positive side, the design connects probabilistic graphical models with GNNs, and can possibly lead to future exploration. 

The biggest factors that limit the significance of neural tree are the scalability and generalization. Even though the design may enjoy some nice theoretical properties, I am not convinced that it can significantly advance the current models that are used in practice. 

In its current form, I'm not sure if the theorems are correct. The experiments also doesn't seem to validate the theorems due to quite different setup. If the authors can clarify the two questions in "Questions on the proof", and the NT-GCN question in "Questions on the experiments", I am willing to increase the score. 
limitations_and_societal_impact: The paper does not discuss potential negative societal impact. 

It may be worthwhile to discuss how the neural tree design can affect the energy consumption in training. As mentioned above, the design seems to come with much higher computation complexity than traditional GNNs.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 
The work presented in this paper tackles the expressivity issue with graph neural networks (GNN). Drawing from the probabilistic graphical models' literature, the authors define the notion of G-compatible functions (i.e. can be factorized over the list of maximal cliques in graph G) and show how they are linked to G-invariant functions (i.e. invariant to node permutation). Then, the authors propose their new GNN architecture called Neural Tree. In their approach, an intermediate tree-structured representation, called H-tree, of the input graph G is constructed first. Traditional message passing is then performed on that H-tree instead of the input graph. The authors go on to show how neural trees can approximate G-compatible functions, thus capable of learning graph invariant functions.

Node classification experiments were conducted on two types of graphs: 3D scene graphs, and citation networks. The neural tree architecture was tested with four different aggregation functions (used during message passing) and compared against their typical architecture implementation (GCN, GraphSAGE, GAT, and GIN). Empirically, using the proposed neural tree architecture always yields higher accuracy. Additional experiments were done to measure the impact on the accuracy when changing the size of the training data (% of labeled nodes), and the number of iterations of message passing. Neural trees appear to be better when having access to a limited amount of labeled nodes, and the optimal number of iterations of message passing seems to follow a similar trend as with the standard GCN architecture.
main_review: ## Overview

To the extent of my knowledge, the proposed method is novel. The authors have tested it on standard nodes classification datasets against several techniques found in the literature. In addition, ablation studies were made to measure the impact of changing the size of the training data and the number of iterations of message passing. Moreover, the claims made in this paper are supported by both theoretical analysis and experimental results. To me, this submission appears to be technically sound. The paper is well written and organized, and it provides enough information for me to reproduce the results (Algorithm 1 + Supplementary material). In addition to advancing the state of the art, I believe this paper can encourage the community to design novel methods that are more mathematically sound. Overall, I recommend this paper for acceptance.


## What I like about this paper

- The proposed architecture is based on theory from probabilistic graphical models.
- The paper is clearly written and well-paced. The different concepts/definitions are introduced as you need them.


## Comments
- The paper focuses on undirected graphs, what about directed ones?
- At the end of section 7.1, it is mentioned that "optimal T is empirically close the average diameter of the H-Trees". Would it make sense to have an adaptive T, i.e. that varies according to the diameter of the H-tree provided in input?


-----
## Typos
- p.4, line 137: G-invaraint -> G-invariant
limitations_and_societal_impact: The authors have described a limitation of their method regarding large treewidth and suggested a graph subsampling technique to overcome that limitation. They show empirical evidence that the subsampling trick works on large graphs.

Regarding any potential negative societal impacts of their work, the authors said there is no direct impact. Since the approach heavily relies on tree-decomposition algorithms, in their experiments they used the junction-tree decomposition, I'm wondering if the authors are aware of any bias that such tree decomposition could have in the resulting tree (dropping rare edge, bias toward nodes with few/large neighbors, etc.)?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a new GNN architecture based on performing message passing on the tree structures of the input graph, and theoretically and empirically demonstrates its strong expressive power.
main_review: Originality: This work proposes a novel GNN architecture which is very different from most existing GNN architectures. The key novelty of the new method is that the message passing is not performed on the input graph, but a hierarchical tree structure of the input graph. Such operations are demonstrated to be G-compatible, and equivalently be G-invariant/equivariant.

Quality: The authors have done empirical studies on 3d scene graph dataset and citation network dataset. The experiment results are very sound, showing the consistent performance boost over various of message passing mechanisms when using the proposed hierarchical tree structures. The ablation studies can technically support the theoretic claim of the new method.

Clarity: The paper is clearly written and well organized.

Significance: I personally think this is a very solid and enlightening work. It introduces the concept of G-compatible functions and theoretically demonstrate its relation with the expressive ability of graph neural networks, which is a unique and fundamental contribution in the related research area. I believe this work can attract more researchers to pay attention to G-compatible GNN structures in the future.

Considering the novelty, solid contribution, and good empirical studies, I recommend to accept this paper. My only concern is that the proposed method focuses on the semi-supervised node classification problem. I think the proposed method can be a general feature extractor for graph data. I am wondering can the proposed method be applied to graph-level problems (e.g., molecular graph classification)? If so, I believe additional experiments on such problems can make this work more comprehensive.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a modification to GNN by first computing an H-tree and then running a GNN on it.

In the theoretical section they prove that this is a universal approximation for graph invariant functions which is a significant contribution, and show good empirical results. 
main_review: I like the approach but my main concern is about the validity of the proof of theorem 7, I would gladly change my score if and when it is resolved. 

- in equation 8 you define the aggregation but are not concerned with it being an invariant function as each edge has its own weight (also the common approach is to have w as a matrix not vector).

Because of this later in assertion 1 and 2 you assume you can send information from a specific edge, but that in itself contradicts invariance.
- If you claim invariance then this is a contradiction, if not then the theorem is not interesting as we could just use a MLP and approximate an invariant function using standard universality claims.

Other remarks:
- k-WL can be used efficiently for k=3, see "Provably Powerful Graph Networks".
- I found the 5.2 section very unclear and hard to follow.

limitations_and_societal_impact: The authors clearly state the limitations of their method - graphs with  large tree width
review_title: null

Meta-review: The paper proposes novel GNN architecture that is based on theory from probabilistic graphical models. The literature on GNNs is vast yet this approach seems to be unique and furthermore well grounded in theory of PGMs. Currently the manuscript focuses on undirected graphs, but extension to directed graphs should be straightforward. Very well written paper applying rich theory on PGMs in the elegant, practical way. 
Decision: Accept (Poster)