Neural Trees for Learning on Graphs
Authors: Rajat Talak
Siyi Hu
Lisa Ruihong Peng
Luca Carlone
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural networks
geometric deep learning
universal function approximation
tree-decomposition
semi-supervised node classification
3D scene graphs

Abstract: Graph Neural Networks (GNNs) have emerged as a flexible and powerful approach for learning over graphs. Despite this success, existing GNNs are constrained by their local message-passing architecture and are provably limited in their expressive power. In this work, we propose a new GNN architecture – the Neural Tree. The neural tree architecture does not perform message passing on the input graph, but on a tree-structured graph, called the H-tree, that is constructed from the input graph. Nodes in the H-tree correspond to subgraphs in the input graph, and they are reorganized in a hierarchical manner such that the parent of a node in the H-tree always corresponds to a larger subgraph in the input graph. We show that the neural tree architecture can approximate any smooth probability distribution function over an undirected graph. We also prove that the number of parameters needed to achieve an $\epsilon$-approximation of the distribution function is exponential in the treewidth of the input graph, but linear in its size. We prove that any continuous G-invariant/equivariant function can be approximated by a nonlinear combination of such probability distribution functions over G. We apply the neural tree to semi-supervised node classification in 3D scene graphs, and show that these theoretical properties translate into significant gains in prediction accuracy, over the more traditional GNN architectures. We also show the applicability of the neural tree architecture to citation networks with large treewidth, by using a graph sub-sampling technique.

Neural Trees for Learning on Graphs
Rajat Talak, Siyi Hu, Lisa Peng, and Luca Carlone Laboratory of Information and Decision Systems (LIDS) Massachusetts Institute of Technology {talak, siyi, lisapeng, 1carlone)@min @mit edu
Abstract
Graph Neural Networks (GNNs) have emerged flexible and powerful approach for learning over graphs. Despite this success, existing GNNs are constrained by architecture and are provably limited in their expressive
their local message- power. In this work, we propose new GNN architecture - the Neural Tree. The neural tree architecture does perform message passing on the input graph, but on a tree-structured graph, called the H-tree, that is constructed from the input graph. Nodes in the H-tree correspond subgraphs in the input graph, and they are reorganized in a hierarchical manner such that the parent of a node in the H-tree always corresponds
larger subgraph in the input graph. We show that the neural tree architecture can approximate any smooth probability distribution function over an undirected graph. We also prove that the number of parameters needed to achieve an e-approximation of the distribution function is exponential in the treewidth of the input graph, but linear in its size. We prove that any continuous G-invariant/equivariie combination of such probability distribution functions over G. We apply the neural tree to semi-supervised node classification in 3D scene graphs, and show that these theoretical properties translate into significant gains in prediction accuracy, over the more traditional GNN architectures. We also show the applicability of the neural tree architecture to citation networks with large treewidth, by using a graph sub-sampling technique.
function can be approximated by nonlinear
Introduction
Graph-structured learning problems arise in several disciplines, including biology (e.g.. molecule classification [15] computer vision (e.g., action recognition [19], image classification [48), shape and pose estimation (30), computer graphics (e.g., mesh and point cloud classification and segmen- tation (20 35 41). and social networks (e.g., fake news detection 42],, among others [9. this
landscape, Graph Neural Networks (GNN) have gained popularity as flexible and effective approach for regression and classification over graphs.
Despite this growing research interest, recent work has pointed out several limitations of existing GNN architectures [56] 43 38 g) Local message passing GNNs are no more expressive than the Weisfeiler- Lehman (WL) graph isomorphism test (56), neither can they serve as universal approximators to all G-invariant (equivariant) functions, i.e., functions defined over graph & that remain unchanged by (or commute with) node permutation. The work [12] proves an equivalence between the ability to do graph isomorphism testing and the ability to approximate any G-invariant function.
Various GNN architectures have been proposed, that go beyond local message passing or use tensor representations, in order to improve expressivity. Graph isomorphism testing. S--nvarianteeqiivarinn function approximation, and the generalized k-order WL (L-WL) tests have served as end objectives and guided recent progress of this inquiry. For example, k-order linear GNN [39 and k-order folklore GNN (38] have expressive powers equivalent to k-WL and (k + 1) test, respectively [3] While
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

these architectures can theoretically approximate any G-invariant function (as & - oo), they use k-order tensors for representations, rendering them impractical for any k >> 3.
There is a need for a new way to look at constructing GNN architectures. With better end objectives to guide theoretical progress. Such attempt can result in new and expressive GNNs that are provably tractable - if not in general, at least in reasonably constrained settings.
A GNN, by its very definition, operates on graph structured data. The graph structure of the data determines inter-dependency between nodes and their features. Probabilistic graphical models present reasonable and well selllestablished way of articulating and working with such dependeennssss in the data. Prior to the advent of neural networks, inference algorithms on such graphical models were successfully applied to many real- world problems. Therefore, operating on a graph should have at least the expressive power of a probabilistic graphical model, i.e. it should be able to approximate any distribution defined by probabilistic graphical model.
pose that a GNN architecture
This is not trivial requirement as exact inference (akin to learning the distribution or its marginals) on a probabilistic graphical model, without any structural constraints the input graph, is known to be an NP-hard problem [13. Even approximate inference on a probabilistic graphical model is known to be NP-hard in general 46). A common trick to perform exact inference, consists in constructing a junction tree for an input graph and performing message passing on the junction tree instead. In the junction tree, each node corresponds to subset of nodes of the input graph. The junction tree algorithm remains tractable for graphs with bounded treewidth, while [T]] shows that treewidth is the only structural parameter, bounding which, allows for tractable inference on graphical models.
Contribution. We first define the notion of G-compatible function and argue that approximating G G-compatible functions is equivalent to approximating any probability distribution on a probabilistic graphical model (Section[4) 4 we also show that -invariant/equivariant functions considered in related work can be approximated using nonlinear combination of G-compatible functions.
We then propose novel GNN architecture the Neural Tree that can approximate any G-compatible function (Section 5). Neural trees do not perform message passing on the input graph, but on a tree-structured graph, called the H-tree, that is constructed from the input graph. Each node in the H-tree corresponds to a subgraph of the input graph. These subgraphs are arranged hierarchically in the H-tree such that the parent of a node in the H-tree always corresponds to a larger subgraph in the input graph. The leaf nodes in the H-tree correspond to singleton subsets (i.e., individual nodes) of the input graph. The H-tree is constructed by recursively computing tree decompositions of the input graph and its subgraphs, and attaching them to one another to form hierarchy. Neural message passing on the H-tree generates representations for all the nodes and important subgraphs of the input graph.
We next prove that the neural tree architecture can approximate any smooth G-compatible function defined over given undirected graph (Section(6). We also bound the number of parameters required by neural tree architecture to obtain an e-approximation of an arbitrary (smooth) G-compatible function. We show that the number of parameters increases exponentially in the treewidth of the input graph, but only linearly in the input graphs size. Thus, for graphs with bounded treewidth, the neural tree can tractably approximate any smooth distribution function.
We apply the neural tree architecture for semi-supervised node classification in 3D scene graphs and citation networks (Section 7 Our experiments on 3D scene graphs demonstrate that neural trees outperform standard, local message passing GNNs, by a large margin. Citation networks on the other hand, typically have large treewidth: therefore we make use of recently proposed bounded treewidth graph bub-sampling algorithm (62). that sub- samples the input graph (i.e.. removes edges) to reduce its treewidth to a specified number. We show that applying the neural tree architecture in conjunction with such sub-sampling algorithm makes our architecture scalable to large graphs while still preserving its advantage over traditional architectures. Our code is publically available at https://// //gi thub. com/MIT SP ARK /wtk//eeral... /
2 Related Work
Expressive Power of Graph Neural Networks. Since the seminal works 18 architectures have been proposed including Graph Convolutional Networks (GCN)
49
various GNN
29
14 29 9)
Message Passing Neural Networks (MPNN) [7.. GraphSAGE [3], Graph Attention Networks

---

10,, message passing GNN [17]. Limited expressive power of these standard GNNs has been major concern. For instance. is known that local message passing GNNs can neither distinguish between non-isomorphic graphs (provably worse than the 1- -eiiseeiler--Lehman (WI.)
(GAT) 53 34
test) 156 4
nor can they compute even simple graph properties [66]
Many GNN architectures have been proposed to overcome this expressivity bottleneck. Graph substructure network is proposed in S and is shown to be more powerful than the I-WL test. k-order GNNs, in which message passing is performed among a subset of nodes in the input graph, is shown have expressive power equivalent to the generalized k-WL test 45
It generally understood that to improve the expressivity of GNNs one has to extract features corresponding to important subgraphs, and operate on them. A hierarchical architecture that pools a representation vector from a subset of nodes, at each layer, is proposed in [6 A junction-trey based message passing GNN is proposed for molecular graph generation in 23
38
Graph neural networks have been investigated as function approximators since the beginning. (50) introduces the notion of unfolding equivalence and derives a universal approximation result for graph neural networks. Recent research in developing expressive GNN architectures has been towards
approximating graph invariant/equivariatt functions 40 39 cquivariance are desirable properties, the problem of designing GNNs that are universal approximators of G-invariant/equiiarrian functions has been difficult. For instance, the k-order GNNs 39 38
38
27
47 While, invariance and
can provably approximate any graph invariant function, but only as k + 30, rendering them impractical [3]. An equivalence between designing GNN architectures to approximate graph invariant functions and graph isomorphism testing is shown in [12. The generalization power of GNNs has
also been investigated in (51 16 57 58
Scene Graphs. Scene graphs are popular model to abstract information in images or model 3D environments. 2D scene graphs have been used image retrieval [24], caption generation 226 M.
visual question answering [44] (31] and relationship detection (37). GNNs are popular tool for joint
object labels and/or relationship inference on scene graphs (55 36 59 63 Recently, there has been
a growing interest towards 3D scene graphs, which are constructed from 3D data, such as meshes (2].
point clouds [54], or raw sensor data (28 45). GNNs have been very recently applied to 3D scene
graphs for scene layout prediction [54] or object search [32].
3 Problem Statement and Preliminaries
In this section, we state the node classification problem and review standard graph neural networks. Problem. We focus on the standard problem of semi-supervised node classification (9]. We are given graph G (V, along with node features X = (œv)vev; where E. denotes the node feature of node e E V. The graph is not necessarily connected. A subset of nodes A C V in are labeled, i.e., Zz, E C v A} is given; here denotes the label for node and L the finite set of label classes. We need to design a model to predict the labels of all the unlabeled nodes u E VA,AA
Graph Neural Networks (GNN). Various GNN architectures have been successfully applied to solve the node classification problem [33 29
53 56 23). Standard GNN architectures construct representation vectors for each node in G by iteratively aggregating representation vectors of its neighboring nodes. At iteration i, the representation vector of node is generated as follows:
ht = AGG, (N--) ((h))) (u,r) E No (o))),
with No A Z.. Ve E V; where NV (v) denotes the set of neighbors of node e in graph G and the aggregation function AGG, can depend on the trainable edge parameters Ku,v- This process of sharing and aggregating representation vectors among neighboring nodes in G is often called message passing. This procedure runs for a fixed number of iterations T. The node labels are then generated from the representation vectors at the final iteration T'. Node labels are extracted as
y = READ(A)),
(2)
for all U E V. The functions AGG, and READ are modeled as single or multi- perceptrons.
3

---

4 Graph Compatible Functions
We start by defining class of G-compatible functions. G-compatible functions allow us to establish connections with probabilistic graphical models and the G-invarain//equivariant functions.
Definition (G-compatible functions) We say that a function f (XvEVXur 9) - R is compatible with graph G or G-compatible if it can be factorized as
f(x) = Ecec(a) Oc(xc),
(3)
where C (g) denotes the collection of all maximal cliques in & and 0g is some function that maps Xvec%y (the set of node features in the clique C') to real number.
Compatible functions arise in probabilistic graphical models; for instance, the logarithm of a joint probability distribution is compatible function (see supplementary material for more examples on how such functions arise in inference on graphical models).
Functions. A graph invariant function requires that the function output remains invariant to node permutation, whereas a graph equivariant function outputs vector (or a tensor in general) which is required to commute with any permutation applied the input graph nodes. While graph invariance a desirable property for graph classification problems, graph equivariance is desirable in node classification problems.
Relation with Invariant/Equivarian
now show that any continuous G-invariant or G-equivariant function can be written as a finite sum of G-compatible functions, each composed with specific nonlinear function. The precise definitions of G- G-invariant and Gequivarrinn functions and the proof is given in the supplementary material.
Theorem (InvarianceEQuivvriineee For any continuous G-invariant function h X R and an 6 >> 0 there exists an integer M 2 1 and a collection of M continuous G-compatible functions ( J==1 such that
supxex [(X) ( <.
where o :R- -RR is a nonlinear function. For any continuous G-equivariant h. X - R and 0, holds for each of its component hi( (x)
The result shows that a GNN architecture that can approximate any G-compatible function will also be able approximate any graph invariant and equivariant functions. In the next section, we describe the neural tree architecture, which can approximate any (smooth) G-compatible function.
5 Neural Tree Architecture
The key idea behind the neural trees architecture is to construct tree-structured graph from the input graph and perform message passing on the resulting tree instead of the input graph.
In the following, we first review the notion of tree decomposition (Section 5.1). We then show how construct H-tree for graph, by successively applying tree decomposition on given graph G and its subgraphs (Section 5.2). Finally, we discuss the proposed neural tree architecture for node classification, which performs neural message passing the H-tree (Section 5.3).
In Section 6 we show that the tree structure enables the derivation of strong approximation results by which neural tree can approximate any (smooth) G-compatible function.
5.1 Tree Decomposition
For a graph G, tree decomposition is a tuple (T, B) where T is a tree graph and B = (Brrrev a family of bags, where B, C V()) for every tree node T E V(T), such that the tuple (T, B) satisfies the following two properties:
(1) Connectedness: for every graph node E V(9), the subgraph of T induced by tree nodes whose bag contains node v, is connected, i.e., T, A [[r E V(T) E B,}] a connected subgraph of T for every V()).

---

(2) Covering: for every edge {u, v} in G there exists node 7 E V(T) such that E Br-
The simplest tree decomposition of any graph 9 is the nodes G. However, in practical applications, it is desirable to obtain decompositions where the size of the largest bag is small. This is captured by the notion of treewidth. The treewidth of tree decomposition (T, B) is defined as the size of the largest bag minus one:
with single node, whose bag contains all
tw (T, B)] max+ev(T) [Br] 1.
(5)
The treewidth of graph 9 is defined the minimum treewidth that can be achieved among all tree decompositions of G. While finding tree decomposition with minimum treewidth is NP-hard, many algorithms exist that generate tree decompositions with small enough treewidth 4 52 7
We use (T, .) tree- sereeddecoposiitionn
to denote a generic tree decomposition of a graph G. One of the most popular tree decompositions is the junction tree decomposition, which was introduced in [22]. We denote it by (T, B) = junction (re and describe it's construction in the supplementary material for completeness.
5.2 The H-free
Troe Sub-grophts
Junction Graphs
We first define H-tree for a complete graph. Let S,, denote star graph with n leaf nodes and one root.
14
Definition 3 (Complete graph)
For a complete graph with n nodes, the H-tree is slar graph, i.e.,
Horee
Ig = -nn, where the root node (in Jg) represents the single maximal clique in 9 and each of the leaf nodes in S,, corresponds to node in G.
The H-tree for a complete graph of Figure 1: Generating H-trees for graph and its subgraphs.
three nodes is shown in Fig. rightmost column. In it, the unique clique in the graph, which contains nodes {3, 4, 5]. is labeled as = (345). For the sake of clarity, we always enlist the set of root nodes when defining an H-tree. Therefore, an H-tree of graph g is given by a tuple (Jg. R), where Tg is a tree graph and R is the set of root nodes.
The H-tree is computed by recursively applying tree de- composition on the input graph and the subgraphs obtained in tree decomposition. For instance, if (T, B) is tree de- composition of the input graph G, then we recursively apply tree decomposition to each subgraph G (of G) for each E B. The final H-tree Tg is computed by con- necting all the obtained tree decomposition as hierarchy. The set of root nodes R are the nodes in Tg correspond- ing to the original tree decomposition (T, B) of the graph. This process is illustrated in Figure and the algorithm described in Algorithm [
Algorithm 1: H- tree
input :Graph output:H-tree (Jg, R)
(T,B) sree-decomposttion(()
J < T
R < V(T)
for each bag in B do
5
g is complete graph then
Update J:
V(J) + UB
E(J)
E (U((T(B).b))e
else
We now describe the algorithm more detail. Algorithm I takes an undirected graph G and outputs H-tree Ig with set of root nodes R. Let (T, B)) denote a tree decompo- sition of graph G (line Tp. The H-tree J is initialized to J == T (line 2 and the set of root nodes equals the root nodes of this tree, namely It = V(T) (line 3). For B E B, let T(B) denote the node corresponding to bag in J. Then for each bag B E B construct H-tree of the induced subgraph [[B] (lines 41
(J', R²){ H- (B)
Update J:
E(J") + E(T')EE13(())
13
JUJ E(J) E(J) (((B))))
Ja J return (Ja.
If G B is not complete, we attach its root nodes to r (BB) (lines 15). Specifically, if (J', R') denotes the H-tree for the induced subgraph G[B), then we attach the graph J' to J by linking all root nodes of J'.
5

---

namely R', to the node TBB) (lines 13 14). To avoid eycles, we also remove edges between the root
nodes R' in J'(ine 12
If the induced subgraph [ is complete, then from Definition 3 we know that its H-tree is a star graph with a single clique node, call it C. In this case, we attach the star graph to 7 (B) by merging two nodes - C' and TBB) - into one. This avoids an unnecessary edge (T(B), C)) in the H-tree.
Figure shows the construction of a H-tree for graph with 5 nodes and 6 edges. Here, we have used the juncti onnction-ae tree algorithm to perform tree decomposition, The first column shows the graph G and its junction trees, which has three nodes corresponding to the three cliques in the chordal graph G. (which in this case consists in adding the dashed blue line in Figure [T] see supplementary material for details). The remaining columns show the three subgraphs of G corresponding to each of the three maximal cliques in Ge. along with their junction trees and H-trees. The H-tree of each of these subgraphs is then attached to the junction tree of & to get the required H-tree for G. The H-tree for graph G is shown in the last row of the first column in Figure Also illustrated are the two edges deleted (in red) when merging the two H-trees of the subgraphs to the junction tree of G.
Example.
Remark 4 (Leaves and features) Each node in the H-tree (of graph G) corresponds to subset of nodes in graph G. Every leaf node I in Ig corresponds to exactly one node v in G. We denote this node by k(l) for every leaf node of Ig. In the construction of the H-tree, we also assign the node input feature Te to every node in for which r(l)) = U. Note that multiple leaf nodes may correspond to single node in the graph G, ie., can have k(l) for many leaf nodes in Jg. Fig. D illlustrates the input node features by node coloring.
5.3 Message Passing on the H-tree
Given a graph G with input node features, we construct a H-tree (Jg, R) and perform message passing on Jg. We call this the neural tree architecture. Representation vectors are generated for each node in the H-tree Ig by aggregating representation vectors of neighboring nodes in Tg. The
message passing starts with hi = (1) for all leaf nodes I Tg and hy for non-leaf nodes u in Tg. These representation vectors are then updated as
h AGG, (h-- ((tt ( k.,..)) w E No (u))).
(6)
for each iteration E {1, T}. The aggregation function AGG, can be modeled in numerous ways. Many of the message passing GNN architectures in the literature, such as GCN (2).. Graph- SAGE 33 GIN (56), GAT [53 34, can be used to perform message passing on Jg. The message passing in (6) using edge weights can also be made to distinguish between edges connecting to roots and children in the H-tree. After T iterations of message passing, we extract the label yo for node E G by combining the representation vectors of leaf nodes I of Jg. which correspond to node in G, i.e., e = x()::
yv COMB ((hT) | leaf node in Ig s.t. x(I) = v))
for every U E V. where h." denotes the representation vector generated at leaf node in Tg after T iterations. COMB can be modeled by using any of the standard neural network models. In our experiments, we model COMB with a mean pooling function followed by a softmax.
Remark (Mutatis mutandis) The neural tree architecture is partly inspired by the junction tree algorithm (25). The junction free message passing algorithm can be described in three steps. First, the clique potentials are computed for all nodes in the junction tree (T,B) of G. This is followed by message passing between nodes on T, which updates the clique potentials, until convergence. Third, the marginals are computed for each node from the clique potentials. The proposed neural tree can emulate these three steps by message passing from leaf nodes to the root nodes in H-tree, message passing between the root nodes, and message passing back from the root nodes to the leaf nodes, respectively. [57] suggests that such algorithmic alignment of the neural architecture leads to better generalizability. We leave the question of generalization power to future work.
Remark (Scalability and trade-offs) The proposed architecture requires constructing the H-tree for the graph G, which involves computing a tree decomposition of G. The time and spuce complexity of computing a tree decomposition of a graph G scales exponentially in the treewidth of G. In many semi-supervie node classification problems, the treewidth of the input graph is too large to compute

---

tree decomposition (eg. graphs arising in citation networks (60)). In such cases, to regain computational tractability, one can sub-sample the input graph (i..., remove some edges in G) to ger graph 9. with smaller treewidth, and then apply the neural tree architecture to this sub-sampled graph 9x- 162] proposes one such graph sampling algorithm, which for any given graph 9 and treewidth bound k, efficiently generates the sub-sampled graph Go and its tree decomposition. The complexity of this algorithm is ((EE()) + (V))))). This addition to the neural tree architecture
makes it scalable to large graphs (see Section 7.2
6 Expressive Power of Neural Trees
We now show that neural trees can learn any graph-compatible function provided it is smooth enough. All proofs are given in the supplementary material.
For simplicity, let the input node features and the representation vectors be real numbers, ie., 2. E IR and ht E IR for all E V(G) and nodes Jg. Let us implement the aggregation function AGG, in (6) as a shallow network:
h = AGG (n" 1 ((h' "Km))) w E NN (u))) = ReLU (Exn k= (,,,
h N(u)) + b
where N(u) = {u} U J (u) denotes the set containing node u and its neighbors in the H-tree Tg. and a by w and Nu, are parameters IT The representation vectors h' are initialized as discussed in Section 5.3
We fix a node Up in graph G and extract our output from up:
yuo COMB ((hT) leaf node in Ig s.t. x(I) vo))
where T is the number of iterations. We also assume the COMB function to be shallow network.
Let N denote the total number of parameters used the neural tree architecture. Consider the space of functions that map the input node features X to the output y/o in (9):
For some T where
F)G,N) 9: 19 9(x)
yvo
you is given by (8-(9)
We now show that any graph-compatible function - that is smooth enough - can be approximated by a function in F(G.N) to an arbitrary precision.
Theorem 7 Lei J 1] + 10. 1] be function compatible with graph G with nodes. Let each clique function Oz in f (see Definition 7 be 1 1-Lipschitz and be bounded to [0, 1). Then, for any > O, there exists a E FG, N) such that [T glloo <,C, while the number of parameters N is bounded by
N (EuEEEn (dh 11) (T.-T)
(duu-1)
(10)
where du denotes the degree of node in Tg, and the summation is over all the non-leaf nodes in Tg.
Theorem 7 assummss the domain and range of the compatible function f and the clique functions Og be bounded between [0. 1]. We remark here that the result, and the proof, can be extended to any bounded f and fz, over bounded domains.
We next develop the bound in Theorem 77 expose the dependence of the number of parameters N on the treewidth of the tree decomposition of the graph.
Corollary The number of parameters N in Theorem is upper-bounded by
N N (n x (nw [Tl + +1) 162433 c- -(mw(3ol+1)
where tw [Je] denotes the treewidth of the tree-decomposttion of G. formed by the root nodes of Jg-
We assume a different AGG, function for each node u at iteration t. This choice is more general than our architecture in Section [533 However, our results extend to the case where the AGG, function is the same across nodes each iteration
7

---

Remark 9 (Efficient approximations) Corollary 8 shows that the number of parameters needed to obtain an e-approximation with neural trees increases exponentially in only the treewidth of the tre-deccompoiiion, and is linear in the number of nodes in the graph. Thus, for graphs with bounded treewidth, neural trees are able to approximate any graph-compatible function efficiently.
Remark 10 (Data efficiency) The value of N also affects the data required to train the model: the larger the N, the more samples are required for training. In particular, Corollary 8 provides the reassuring result that if the training dataset contains graphs of small treewidth, then the amount of data required for training scales only linearty in the number of nodes n.
7
Experiments
7.1 Node Classification in 3D Scene Graphs
We use the neural tree architecture for node classification on 3D scene graphs and show it outperforms the standard GNNs.
Dataset. We run semi-supervised node classification experi- ments on Stanford's 3D scene graph dataset [2]. The dataset includes 35 3D scene graphs with verified semantic labels, each containing building, room, and object nodes in a residential unit. Since there is only a single class of building nodes (residen- tial), we remove the building node and obtain 482 room-object graphs where each graph contains a room and at least one object in that room shown in Fig. [ The resulting dataset has 482 room nodes with 15 semantic labels, and 2338 objects with 35 labels. Each object node is connected the room node belongs to. In addition we add 4920 edges to connect adjacent objects in the same room. We use the centroid and bounding box dimensions features for each node.
Figure 2: A room-object graph in 3D scene graph.
Approaches and Setup. We implement the neural tree architecture with four different aggregation functions AGG, specified in: GCN (29), GraphSAGE [33), GAT [53), GIN [56]. We randomly select 10% of the nodes for validation and 20% for testing. The hyper-parameters of the two approaches are
separately tuned based the best validation accuracy, while using all 70% of the remaining nodes for training; see supplementary material for details.
Results. Table [ compares the test accuracies (averaged over T00 runs) for the standard GNN architectures and the corresponding neural tree architecture, while using the same type of ag- gregation function. We see that the neural tree architecture always yields a better predic- tion model than the standard GNN, for given aggregation function.
Table I: Test Accuracy
Model
Input graph
Neural Tree
GCN GraphSAGE
40.88 + 2.28 %
50.63 + 2.25 %
59.54 + 1.35 %
63.57 + 1.54 %
GAT
46.56 + 2.21 %
62.16
2.03
GIN
49.25 + 1.15 %
63.53 + 1.38 %
To further analyze the proposed architecture, we carry out series of experiments to see how the test
accuracy varies as a function of the amount of training data and the number of message passing iterations T. For simplicity, we only show the neural tree that uses the GCN aggregation func- tion in comparison with the stan- dard GCN.
0.6
SCV
L-GGMM
Vi 10CH
0.5
Averoge sccrssy (5)
10
80
0.
Tequerryy
10
8
Figures and plot the test ac- curacy (averaged over 10 runs) as a function the training data used and the number of iterations T. The test accuracy -for both the neural tree (NT+GCN) and
23
30
60
30
00
75
Number of oifitertions, diameter
Nodes used for tainng
Figure 4: Accuracy vs. number of iterations and weighted diam- eter distribution.
Figure 3: Accuracy vs. training data (% of labeled nodes).
8

---

GCN- increases with increasing training data, however, the increase is sharper for the neural tree architecture, eventually outperforming GCN.
This shows the higher expressive power of the proposed neural tree architecture. As with the number an optimal T at which the test accuracy is maximized. This optimal T is
of iterations T, empirically close to the average diameter of the constructed H-trees, of all (room-object) scene graphs in the dataset. This is intuitive, as for the messages to propagate across the entire H-tree, " would have to equal the diameter of the H-tree, See supplementary material for more details, where we also report the compute, train, and test time requirements for neural trees.
7.2 Node Classification in Citation Networks
90
Here show that the neural tree architecture scale to large citation network datasets by using the bounded treewidth graph sub-sampling proposed in [62] We use the popular citation network datasets (60), where nodes documents and undirected edges citations. Each
Beeaago accuracy (96
80
Average
node has a class label representing the subject of the docu- ment. These graphs have high treewidth, and therefore, are first sub-sampled using the bounded treewidth graph sub- sampling algorithm in [2]]. The neural tree constructed on the sub-sampled graph.
-3
GON
--NT-GON, k-1 NT-GON, ko4
70
1000
2000
3000
4000
Nodes used for training, per class
In Figure 5 we plot test accuracy (averaged over 10 runs) as a function of training data, for GCN and NT+GCN, on the Pubmed dataset [60] As in the scene graph case, we again see that the test accuracy improves with increasing training data, and eventually the neural tree architecture performs better than the standard GNN (GCN in this case). We also observe no significant change in performance of the NT+GCN, with increasing treewidth bound & used for graph sub-sampling. This indicates that it is possible retain the best possible performance, even after sub-sampling the input graph with very low treewidth bound. We report the details and more results in the supplementary material.
Figure 5: Accuracy vs. training data (per class).
8 Conclusion
We propose a novel graph neural network architecture - the neural tree. The neural tree performs message passing, not the input graph, but over constructed H-tree, which provides a tree- structured description of the original graph and its subgraphs. We show that the neural tree architecture approximate any graph-compatible function, and that the number of parameters required obtain a desired approximation grows linearly with the number of nodes and exponentially in the treewidth of the input graph. This renders the proposed architecture more parsimonious for large graphs with small treewidth.
Graph-compatible functions arise in probabilistic graphical models, hence the proposed architecture can approximate any probability distribution function defined on graph. Furthermore, we show that graph compatile function can be used to approximate any smooth graph- int-aniaaat/equuiariann functions studied in the literature. This suggests that the goal of approximating functions is a worthwhile pursuit towards the design of novel GNN architectures.
We use neural trees for node classification on 3D scene graph and citation network datasets, showing that the proposed architecture leads to more accurate predictions with increasing training data and is applicable even for large networks with high treewidth.
Neural Tree is a general purpose architecture and remains to be applied to other learning tasks such as graph representation learning and classification.
Societal Impact
Research Community. Many problems have been sought to solved using graph neural networks. However, the relation between complexity of the underlying problem and parameter complexity of

---

the neural architecture used to solve it is not generally well investigated. Moreover, the expressivity of the graph neural network architecture, i.e., ability to solve any instance of the problem is also not fully understood.
This work, believe, is step towards understanding these fundamental questions. In obtaining approximation guarantees for the proposed Neural Tree architecture, we bring out an interesting tangle between approximating graph compatible functions (which can be thought of as approximating exact inference over probabilistic graphical models), graph treewidth, and the parameter complexity of the Neural Tree. The parameter complexity obtained in Theorem X matches the problem complexity of exact inference on probabilistic graphical models [
We hope that this work will inspire other researchers to consider similar questions for other problems and neural architectures and investigate the relation between the problem complexity, parameter complexity, and the underlying graph properties such as the graph treewidth.
Community at Large. The main thrust of this work to develop new graph neural network architecture that can approximate any graph compatible function. We show that the parameter complexity increases exponentially in the graph treewidth, and of the same order as the complexity of exact inference on graphical models. This implies that when applying Neural Trees, graph treewidth not only an important parameter, but the most important aspect in controlling the required memory and computation time.
This can be limiting factor in deploying the Neural Tree architecture in cases where either the energy consumption or large graph treewidth is an issue. In the paper, however, we observe that using the Neural Tree architecture in conjunction with bounded treewidth subgraph sampling 62 provides good approximation in such cases.
Acknowledgement
This work was partially funded by the Office of Naval Research under the ONR RAIDER program (N00014-18-) 14441-1111 18-1-8888..
10

---

References
[1] P. Anderson, B. Fernando, M. Johnson, and S. Gould. Spice: Semantic propositional image caption evaluation. In European Conf. on Computer Vision (ECCV), pages 382-398, 2016.
[2] I. Armeni, Z. He, J. Gwak, A. Zamir, M. Fischer, Malik, and S. Savarese. 3D scene graph:
A structure for unified semanties, 3D space, and camera. In Intl. Conf. Computer Vision (ICCV), pages 5664-5673, 2019.
[3] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. Intl. Conf. on Learning Representations (ICLR), May 2021.
[4] Ann Becker and Dan Geiger. A sufficiently fast algorithm for finding close to optimal junction trees. In Conf. on Uncertainty in Artificial Intelligence (UAI), pages 81-89, Feb. 1996.
[5] Hans L. Bodlaender. Treewidth: Characterizations, applications, and computations. In Graph- Theoretic Concepts Computer Science, pages 1-14. Springer Berlin Heidelherg, 2006.
[6] Hans L. Bodlaender and Arie M.C.A. Koster. Treewidth computations I: Upper bounds. Information and Computation, 208(3):259 275, 2010.
[7] Hans I.. Bodlaender and Arie M.C.A. Koster. Treewidth computations II: Lower bounds. Information and Computation, 209(7):1 103 1119, 2011.
[8] G. Bouritsas, F. Frasca, S. Zafeiriou, and M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.000 09252, Jan. 2021.
[9] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Process. Mag., 34(4): 18- 42, 2017.
[10] Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y. Hammerla. Relational graph attention networks. arXiv preprint arXiv: NKKKv/99040000 1904.0581/ Apr. 2019.
[11] Venkat Chandrasekaran. Nathan Srebro, and Prahladh Harsha. Complexity of inference in graphical models. In Conf. on Uncertainty in Artificial Intelligence (UAI), page 70-78, 2008
[12] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in Neural Information Processing Systems (NIPS), volume 32, Dec. 2019.
[13] G.F. Cooper. The computational complexity of probabilistic inference using Bayesian belief networks. Artificial Intelligence, 42(2-3):393-405 1990.
[14] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NIPS), volume 29, pages 3844-3852, Dec. 2016.
[15] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molec- ular fingerprints. In Advances in Neural Information Processing Systems (NIPS), volume 28, pages 2224 2224-2232, 2232, 2015.
[16] V. Garg. S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In Intl. Conf. on Machine Learning (ICML), volume 119, pages 3419-3430. Jul. 2020.
[17] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Intl. Conf. on Machine Learning (ICML), volume 70, pages 1263-1272, 2017.
[18] M. Gori, G. Monfardini, and F. Scarselli. new model for learning in graph domains. IEEE Intl. J. Conf. Neural Netw,, volume 2, pages 729-734, 2005.

---

[19] M. Guo, E. Chou, D.-A, Huang, S. Song, S. Yeung, and L. Fei-Fei. Neural graph matching networks for fewshot 3D action recognition. In European Conf. on Computer Vision (ECCV). pages 673-689, 2018.
[20] Rana Hanocka, Amir Hertz, Noa Fish, Raja Giryes, Shachar Fleishman, and Daniel Cohen-Or: MeshCNN: network with an edge. ACM Trans. Graph., 38(4):1-12, 2019.
[21] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph- structured data, arXiv preprint PrrXiv:5506... 163, Jun. 2015.
[22] Finn V. Jensen and Frank Jensen. Optimal junction trees. In Conf. on Uncertainty in Artificial Intelligence (UAI), page 360-366, Jul. 1994.
[23] W. Jin, R. Barzilay, and T. Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Intl. Conf. on Machine Learning (ICML), volume 80, pages 2323-2332, Jul. 2018.
[24] Johnson, R. Krishna, M. Stark, L. D.A. Shamma, M.S. Bernstein, and L. Fei-Fei. Image retrieval using scene graphs. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pages
2015.
[25] M.I. Jordan. An introduction to probabilistic graphical models. Unpublished Lecture Notes, November 2002.
[26] Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descriptions. In IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2015.
[27] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NIPS), volume 32, Dec. 2019.
[28] U. Kim, Park, T. Song, and J. Kim. 3-D scene graph: A sparse and semantic representation of physical environments for intelligent agents. IEEE Trans. Cybern., PP:1-13, Aug. 2019.
[29] T.N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Intl. Conf. on Learning Representations (ICLR), Apr. 2017.
[30] Nikos Kolotouros, Georgios Pavlakos, and Kostas Daniilidis. Convolutional mesh regression for single-image human shape reconstruction. In JEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2019.
[31] R. Krishna, Y. Zhu, O. Groth, J. Johnson, K. Hata, Kravitz, S. Chen, Y. Kalantidis, L. Li, D. Shamma, M. Bernstein, and L. Fei-Fei. Visual Genome: Connecting language and vision using crowdsourced dense image annotations. arXiv preprints arXiv: 10XX::/602.07332.. 2016.
[32] Andrey Kurenkov, Roberto Martín- Jeff Ichnowski, Ken Goldberg, and Silvio Savarese. Semantic and geometric modeling with neural message passing in 3D scene graphs for hierar- chical mechanical search. arXiv preprint arXiv:2012. 201::0002.040000 04060, 2020.
[33] W. Hamilton L., R. Ying. and Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS), page 1025-1035, Dec. 2017.
[34] J. Lee, R. Rossi, Kim, N. Ahmed, and E. Koh. Attention models in graphs: survey, ACM Trans. Knowl. Discov. Data, 13(6), Nov. 2019.
[35] Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs Go as Deep as CNNs? In Inil Conf. on Computer Vision (ICCV), 2019.
[36] Yikang Li, Wanli Ouyang, Bolei Zhou, Kun Wang, and Xiaogang Wang. Scene graph generation from objects, phrases and region captions. In International Conference on Computer Vision (ICCV), 2017.
[37] Cewu Lu, Ranjay Krishna, Michael Bernstein, and Fei-Fei Li. Visual relationship detection with language priors. In European Conference Computer Vision, pages 852-869, 2016.
12

---

[38] H. Maron, H. Ben-Hamu H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NIPS), volume 32, pages 2156-2167, Dec. 2019.
[39] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. Intl. Conf. on Learning Representations (ICLR), 2019.
[40] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Intl. Conf. on Machine Learning (ICML), volume 97, pages 4363-4377 Jun. 2019,
[41] F. Milano. A. Loquercio, A. Rosinol, D. Scaramuzza, and L. Carlone. Primal-dual mesh convolutional neural networks. In Conference on Neural Information Processing Systems (NeurlPS), 2020.
[42] Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael Bronstein. Fake news detection on social media using geometric deep learning. arXiv 990706673, 2019.
[43] C. Morris, M. Ritzert, Fey, W. Hamilton, J. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. Nat. Conf. on Artificial Intelligence (AAAI), (3(01)):402-4465 Jul. 2019.
[44] Mengye Ren, Ryan Kiros, and Richard Zemel. Image question answering: A visual semantic embedding model and new dataset. arXiv preprints 1505.00505.02274. 2015.
[45] A. Rosinol, A. Gupta, M. Abate, J. Shi, and L. Carlone. 3D dynamic scene graphs: Actionable spatial perception with places, objects, and humans. In Robotics: Science and Systems (RSS), 2020.
[46] Dan Roth. On the hardness of approximate reasoning. Artificial Intelligence, 82(1):273-302, Apr. 1996.
[47] Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permuta- tion invariant/equivarian functions by deep neural networks. arXiv preprint arXiv:1903.0199 Sep. 2019.
[48] Victor Gareia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. In Intl. Conf. on Learning Representations (ICLR), 2018.
[49] F. Scarselli, M. Gori, A. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Trans. Neural Netw., 20(1):61-80, 2008.
[50] Scarselli, M. Gori, A. Tsoi, M. Hagenbuchner, and G. Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20(1):81-102 2009.
[51] Scarsellia, Tsoi, and M. Hagenbuchner. The Sepnik-Chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-253 2018.
[52] Alun Thomas and Peter J. Green. Enumerating the junction trees of decomposable graph. J. Comput Graph Stat., 18(4)99309940 Dec. 2009.
[53] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lió, and Yoshua Bengio. Graph attention networks. In Inil. Conf. on Learning Representations (ICLR), May 2018.
[54] Johanna Wald, Helisa Dhamo, Nassir Navab, and Federico Tombari. Learning 3D semantic scene graphs from 3D indoor reconstructions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3961-3970, 2020.
[55] Danfei Xu, Yuke Zhu, Christopher B. Choy, and Li Fei-Fei. Scene graph generation by iterative message passing. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pages 3097-3106, 2017.
[56] K. Xu, W. Hu, J. Leskovec, and Jegelka. How powerful are graph neural networks? Intl. Conf. on Learning Representations (ICLR), May 2019.
13

---

[57] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanic Jegelka. What can neural networks reason about? Intl. Conf. on Learning Representations (ICLR), 2020.
[58] Keyulu Xu, Mozhi Zhang. Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. Intl. Conf. on Machine Learning (ICML), 2021.
[59] Jianwei Yang, Jiasen Lu, Stefan Lee, Dhruv Batra, and Devi Parikh. Graph R-CNN for scene graph generation. In European Conf. on Computer Vision (ECCV), 2018.
[60] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Intl. Conf. Machine Learning (ICML), page 40-48, Jun. 2016.
[61] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and Leskovee. Hierarchical graph repre- sentation learning with differentiable pooling. In Advances in Neural Information Processing Systems (NIPS), pages 4800-4811 2018.
[62] Jaemin Yoo, Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon. Sampling subgraphs with guaranteed treewidth for accurate and efficient graphical inference. In Int. Conf. on Web Search and Data Mining, page 708-716, Jan. 2020.
[63] Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi. Neural motifs: Scene graph parsing with global context. In IEEE Conf. Computer Vision and Putlern Recognition (CVPR), 2017.
14


Reviews:
[{"review_id": "mqLC0LC87Ut", "reviewer": "Reviewer_pckR", "summary": "The paper proposes a modification to GNN by first computing an H-tree and then running a GNN on it.\n\nIn 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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n- 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).\n\nBecause of this later in assertion 1 and 2 you assume you can send information from a specific edge, but that in itself contradicts invariance.\n- 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.\n\nOther remarks:\n- k-WL can be used efficiently for k=3, see \"Provably Powerful Graph Networks\".\n- I found the 5.2 section very unclear and hard to follow.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly state the limitations of their method - graphs with  large tree width", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "kVvhkhwW803", "reviewer": "Reviewer_Xe3h", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality: 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.\n\nClarity: The paper is clearly written and well organized.\n\nSignificance: 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.\n\nConsidering 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "gWjbozZVuMa", "reviewer": "Reviewer_zPgP", "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. ", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\n\nThe 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. \n\nAlthough 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. \n\n## Quality\n\nThe 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. \n\n**Scalability and generalization**\n\nFrom 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. \n\nAs 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). \n\nIn 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. \n\n**Questions on the proof**\n\nFor 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?\n\nFor 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?\n\n**Questions on the experiments**\n\nPlease 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. \n\nThe scalability and generalization concerns are similarly posed to the experiments. The evaluated datasets are both very small, indicating the challenge in scalability. \n\nAs 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. \n\n**Other questions on the model design**\n\nI 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. \n\nWhat 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. \n\n\n## Clarity\n\nThe 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. \n\n\n## Significance\n\nOn the positive side, the design connects probabilistic graphical models with GNNs, and can possibly lead to future exploration. \n\nThe 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. \n\nIn 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does not discuss potential negative societal impact. \n\nIt 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_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "J9W0wyHx09t", "reviewer": "Reviewer_o8Qn", "summary": "\nThe 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.\n\nNode 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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Overview\n\nTo 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.\n\n\n## What I like about this paper\n\n- The proposed architecture is based on theory from probabilistic graphical models.\n- The paper is clearly written and well-paced. The different concepts/definitions are introduced as you need them.\n\n\n## Comments\n- The paper focuses on undirected graphs, what about directed ones?\n- 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?\n\n\n-----\n## Typos\n- p.4, line 137: G-invaraint -> G-invariant", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nRegarding 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)