High-Order Pooling for Graph Neural Networks with Tensor Decomposition
Authors: Chenqing Hua
Guillaume Rabusseau
Jian Tang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Tensor
Graph Neural Networks
Node Classification
Graph Classification
CP decomposition

Abstract: Graph Neural Networks (GNNs) are attracting growing attention due to their effectiveness and flexibility in modeling a variety of graph-structured data. Exiting GNN architectures usually adopt simple pooling operations~(\eg{} sum, average, max) when aggregating messages from a local neighborhood for updating node representation or pooling node representations from the entire graph to compute the graph representation. Though simple and effective, these linear operations do not model high-order non-linear interactions among nodes. We propose the Tensorized Graph Neural Network (tGNN), a highly expressive GNN architecture relying on tensor decomposition to model high-order non-linear node interactions. tGNN leverages the symmetric CP decomposition to efficiently parameterize permutation-invariant multilinear maps for modeling node interactions. Theoretical and empirical analysis on both node and graph classification tasks show the superiority of tGNN over competitive baselines. In particular, tGNN achieves the most solid results on two OGB node classification datasets and one OGB graph classification dataset.

High-Order Pooling for Graph Neural Networks with Tensor Decomposition
Chenging Hual.4-
Guillaume Rabusseau 2,4,5,6 Jian Tang3.4.0
McGill University; Université de Montréal; HEEC Montréal; Mila; DIRO; CIIAR Al Chair
Abstract
Graph Neural Networks (GNNs) are attracting growing attention due to their effec- tiveness and flexibility in modeling variety of graph-structured data. Exiting GNN architectures usually adopt simple pooling operations (e.g., sum, average, max) when aggregating messages from local neighborhood for updating node represen- tation or pooling node representations from the entire graph to compute the graph representation. Though simple and effective, these linear operations do not model high-order non-linear interactions among nodes. We propose the Tensorized Graph Neural Network (IGNN), a highly expressive GNN architecture relying on tensor decomposition to model high-order non-linear node interactions. tGNN leverages the symmetric CP decomposition efficiently parameterize cermutation-ivvaiian multilinear maps for modeling node interactions. Theoretical and empirical analysis on both node and graph classification tasks show the superiority of (GNN over competitive baselines. In particular, (GNN achieves the most solid results on two OGB node classification datasets and one OGB graph classification dataset.
1 Introduction
Graph neural networks (GNNs) generalize traditional neural network architectures for data in the Euclidean domain data in non- non-Euclidean domains [26, 45, 34, 35]. As graphs are very general and flexible data structures and are ubiquitous in the real world, GNNs are now widely used in a variety of domains and applications such as social network analysis [20]. recommender systems [49], graph reasoning [55], and drug discovery [42].
Indeed, many GNN architectures (e.g., GCN [26], GAT [45], MPNN [16]) have been proposed. The essential idea of all these architectures to iteratively update node representations by aggregating the information from their neighbors through multiple rounds of neural message passing. The final node representations can be used for downstream tasks such as node classification or link prediction. For graph classification, an additional readout layer is used to combine all the node representations calculate the entire graph representation. In general. an effective aggregation (or pooling) function is required to aggregate the information the level of both local neighborhoods and the entire graph. In practice, some simple aggregation functions are usually used such as sum, mean, and max. Though simple and effective in some applications, the expressiveness of these functions is limited they only model linear combinations of node features, which can limit their effectiveness in some cases.
A recent work, principled neighborhood aggregation (PNA) [13], aims design more flexible aggregation function by combining multiple simple aggregation functions, each of which is associated with learnable weight. However, the practical capacity of PNA is still limited by simply combining multiple simple aggregation functions. A more expressive solution would be to model high-order non-linear interactions when aggregating node features. However, explicitly modeling high-order
"Corresonndncce to: Chenqing Hua <chenqing hww.haal.aaaaacmaammmm..a..aaeaa mammmail.mmmglll...
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

non-linear interactions among nodes is very expensive, with both the time and memory complexity being exponential in the size of the neighborhood. This raises the question of whether there exists an aggregation function which can model high-order non-linear interactions among nodes while remaining computationally efficient.
In this paper, we propose such an approach based on symmetric tensor decomposition. We design an aggregation function over a set of node representations for graph neural networks, which is permutation-invariaat and is capable of modeling non-linear high-order multiplicatiiv interactions among nodes. We leverage the symmetric CANDECOMP/PARAPHI to design an efficient parameterization of permutation innmutttiooninvariann multilinear maps over set of node representations. Theoretically, we show that the CP layer can compute any permutation crrmutation-ivaariant multilinear polynomial, including the classical sum and mean aggregation functions. We also show that the CP layer universally strietly more expressive than sum and mean pooling: with probability one, any function computed by random CP layer cannot be computed using sum and mean pooling.
decomposition (CP) [22. 29]
We propose the CP-layer as an expressive mean of performing the aggregation and update functions in GNN. We call the resulting model a tensorized GNN (IGNN). We evaluate (GNN on both node and graph classification tasks. Experimental results on real-world large-scale datasets show that our proposed architecture outperforms or can compete with existing state-of-the-ar approaches and traditional pooling techniques. Notably, our proposed method is more effective and expressive than existing GNN architectures and pooling methods on two citation networks, two OGB node datasets, and one OGB graph dataset.
Summary of Contributions We propose new aggregation layer, the CP layer, for pooling and readout functions in GNNs. This new layer leverages the symmetric CP decomposition efficiently parameterize polynomial maps, thus taking into account high-order multiplicative interactions be- tween node features. We theoretically show that the CP layer can compute any permutation -nnvarationnnvariaant multilinear polynomial including sum and mean pooling. Using the CP layer as drop-in in replacement for sum pooling in classical GNN architectures, our approach achieves more effective and expressive results than existing GNN architectures and pooling methods on several benchmark graph datasets.
2 Preliminaries
2.1 Notation
We use bold font letters for vectors (e.g., v), capital letters (e.g. M, T) for matrices and tensors respectively, and regular letters for nodes (e.g., v). Let G = (V, be a graph, where V is the node set and E is the edge set with self-loop. We use (v)) to denote the neighborhood set of node v, i.e. NNv) = {u: Evu E}. node feature is vector x IR . defined on V, where x, defined on the node v. We use & to denote the Kronecker product, o to denote the outer product, and @ to denote the Hadamard (i.e., component-wise) product between vectors, matrices, and tensors. For any integer k, we use the notation [k] = (1, k).
2.2 Tensors
We introduce basic notions of tensor algebra, more details can be found in [29]. A k-th order tensor T E x can simply be seen as a multidimensional array. The mode-i fibers of T R The i-th mode matricization of a tensor is the matrix having its mode-i fibers as columns and is denoted by T (1) e.g., T(1) IR N. NN...NN We use TX,V R xxxx...NN............ xN.41x...X to denote
the vectors obtained by fixing all indices except the i-th one: T "n.."...... ".0....:....
the mode-i product between a tensor T E E NIX X and vector v E NN,, which defined
by (T (x pi.........111 11t-1.1P44410 Ml
Σn==1 T Tn Vn, The following useful identity relates the mode-i product with the Kronecker product:
T x vi X2
Xx-1 VA-1 (v- 1 vi).
(I)
2.3 CANDECOMPPPARAFAC Decomposition
We refer to CANDECOMP/PARAFAAT decomposition of a tensor as CP decomposition [24, 22]. A Rank R. CP decomposition factorizes k-th order tensor T E Nix...N. Nr into the sum of R

---

Figure 1: Example of rank symmetric CP decomposition symmetric 3-order tensor T R NXNNN such that T = ER o v, Vr.
rank one tensors T = > Vir o V2r o ..... Var, where denotes the vector outer- outer-product and E RRN, E RRN, y..., E RR Nu for every 1,2, 2..,... R.
The decomposition vectors, V.r for into factor matrices M1 = [VII:... VIRl E IR x .... M = [Vai,... V&Rl s E RN Using the factor matrices, we denote the CP decomposition of as
R, equal in length, thus can be naturally gathered
T =
Σ
Vir o V2r ..... Ver [M, M M&].
The k--th order tensor T is cubical if all its modes have the same size, i.e., Ni =.. No tensor is symmetric it cubical and is invariant under permutation of indices:
N.
T (e(t))r-PRald
T m1 Th1,
E [N]
for any permutation Φ [k] + [k]. A rank R symmetric CP decomposition of a symmetric tensor T is a decomposition of the form T [M.... M] with M e &* It is well known that any symmetric tensor admits a symmetric CP decomposition [12], we illustrate a rank I symmetric CP decomposition in Fig.
We say that tensor T is partially symmetric if it is symmetric in subset of its modes [28]. For example, 3-rd order tensor T E RR is partially symmetric w.r.t. modes and 2 if it has symmetric frontal slices; i.e., T...k is a symmetric matrix for all [Na]. We prove the fact that any partially symmetric tensor admits partially symmetric CP decomposition in Lemma in Appendix A, e.g., T x,N,xN,xX is partially symmetric w.r.t. modes and 2, there exist M E x x and W E R Nt such that T [M, W].
2.4 Graph Neural Networks and Pooling Functions
Given graph G E), graph neural network always aggregates information neighborhood to give node-level representations. During each message passaggepassing iteration, the embedding he corresponding to node V is generated by aggregating features from N(v) [18]. Formally, the 1-th layer of graph neural network,
( [w)) AGGREGATE(") (bb-")) Nu E N(o))), UPDATE (b1-11) ..mm (N())
(2)
where AGGREGATE( and UPDATE(" are differentiable functions, the former being permutation-invariant In words, AGGREGATE(// (.) first aggregates information from N(u), then (PDATE(())) (.) combines the aggregated message and previous node embedding (t-1)) to give a new embedding.
The node representation h! of node from the last GNN layer L can be used for predicting relevant properties of the node. For graph classification, an additional READOUT(-) function aggregates node representations from the final layer obtain graph representation he of graph G as,
h READOUT((b()) E V)),
(3)
where READOUT(.) be simple permutation innvaraaiooninvaiiantt function (e.g., sum, mean, etc.) more sophisticated graph pooling function [50, 48).
In the general design of GNNs, it is important to have effective pooling function to aggregate messages from local neighborhoods and update node representations (see Eq. equation 2), and to combine node representations to compute representation at the graph level (see Eq. equation 3).

---

3 Meaning of High-Order of 1GNN
In our paper, high-order refers to multi-dimensional feature products between nodes in a neighborhood. [38, 43] previous works high-dimensionas feature products, and introduce how to tensor methods to achieve those products. They have stated the importance of having high-order products in physics and geometries. For example, if we have 21 and 22,, simple GNN layer result in a vector of [2, 22, 21 + X22. but our high-order layer result in a vector of [2) 22; 21 + 22, 2 222 with another term 21 And if we have have 31, 22, and 2g, simple low-order GNN layer will result in [4i, 22, 23, 21 + 22, 01 + I3, D2 + L3, F1 + 22 + val while the high-order layer will result in vector of [21 F2, T3, J1 + 22 + 23, + T3, 21 Ti + 33, 22 T2 22222 with extra 4 terms at a higher feature dimension. In general content of GNNs, high-order will normally refer the ability of capturing long-range dependencies, the interactions between long-range nodes [48, 2, 46], but ours refers to the multi-dimensional node feature products. However, the CP layer is able to capture stacking long-range dependencies by stacking layers like other simple GNNs [26, 45].
One may raise a question on why we need to compute dimei--dimesiooall feature products. The idea is fairly easy if one thinks the multi-dimenssonall feature space. Take a molecular graph dataset as an example, and blood pressure could be one feature. Many studies analyze the impact of blood pressure one's health. Blood pressure is the feature in this case. So, one could try to predict life expectancy using blood pressure as a feature, but you can imagine that this might not be sufficient. You really need more information. So you could add age, exercise frequency, and body fat see if you can predict person's 's life expectancy. Those additional measurements are also features and now feature vector consisting of these measurements. However, every individual has a tne-dimensional feature interactions may not capture the correlation between simple GNN with one- age, exereise frequency, and body fat. There could be some correlation between the three factors to predict life expectancy. A simple GNN that does age+exerciis frequency+bodyy fat is not able to capture the correlation between those factors. Still, our multi-dimenssonal feature product can capture age exercise frequency, age body fat, exercise frequency x body fat, agex agexexercise exercise frequency x body fat, all the correlations to predict life expectancy. So in molecular graph case, high- high-dimensional feature products are importantly needed to make a prediction as most features are correlated (like in atom graphs, atom charge, and atom mass), and our model shows some significant improvements on molecular datasets in Sec.6. And the high-dimensional feature products might also be important for other networks and applications [38, 43].
4 Tensorized Graph Neural Network
In this section, we introduce the CP-layer and tensorized GNNs (IGNN). For convenience, we let {x1, X2, } denote features of node and its 1-hop neighbors ((v) such that (())U(()) = k.
4.1 Motivation and Method
We leverage the symmetric CP decomposition to design an efficient parameterization of permutation- invariant multilinear maps for aggregation operations in graph neural networks, Tensorized Graph Neural Network (IGNN), resulting in a more expressive high-order node interaction scheme. We visualize the CP pooling layer and compare it with sum pooling in Fig. 2.
Let T E IR N X..NXX........... N M of order i + 1 be tensor which is partially symmetric w.r.t. its first modes. We can parameterize T using a rank R partially symmetric CP decomposition (see Section 2.3): T = [W, ...., W. MJ where W N and M E MxR Such a tensor naturally defines map from (R N to IR M using contractions over the first k modes:
f(x1,'' xx) T X1 X1 X2
Xx Xx
W
W. M] X1 X2... X Xt.
(4)
1: times
This map satisfies two very important properties for GNNs:
commutatiooninvariian (due to the partial symmetry of 'T) and its number of parameters is independent of k (due to the partially symmetric CP parameterization). Thus, using only two parameter matrices of fixed size, the map in Eq. equation 4 can be applied to sets of N-dimensional vectors of arbitrary cardinality. In particular, we will show that it can be leveraged to replace both the AGGREGATE and UPDATE functions in GNNs.

---

CP Layer
Input Features
Lineet
W
W. W.
Product Pooling Layer
w,
No W
W
Output Representation 27 Elements
Transbenation
Ng. Fo
M
fCP y,
Tio
3.Y12,, N.y. X,. S,7 MPsk 9.
Lincar Activation
Figure 2: (Left) Sum pooling followed by a FC layer: the output takes individual components input into account. (Right) The CP layer can be interpreted combination of product pooling with linear layers (with weight matrices W and M) and non-linearities. The weight matrices a CP layer corresponds partially symmetric CP decomposition of weight tensor T [W, W, W. M]. shows that the output of a CP layer takes high-order multiplicative interactions of the inputs' components into account (in contrast with sum pooling that only considers 1st order terms).
There are several way to interpret the map in Eq. equation 4. First, from Eq. equation we have
"x Xx) T X X2 X Xx T (k+1) (X Xx- @ x1),
where T (1+1) A the mode-(k: 1) matricization of T. This shows that each element of the output ... .xx) ) is linear combinations of terms of the form (x1) )a (xe):z (xx) ) (k-th order multiplicative interactions between the components of the vectors X1 ... .x)). That is, f is multivariate polynomial map of order k involving only k-th order interactions. By using homogeneous coordinates, i.e., appending an entry equal to one to each of the input tensors x,, the map f becomes more general polynomial map taking into account all multiplicative interactions between the x; up to the k-th order:
X
X 1 T (k+1)
X [
f(xI, xx) T
where T is now of size (N +1+ (N+1)xx....... (N +1) 1)x M and can still be parameterized using the partially symmetric CP decomposition T [ .., W, M] with W R(N+1)xR and M MrR With
[W....
this parameterization, one can check that
xx)= - M ( W X
f(x) .x)
W
X
where O denotes the component-wise product between vectors. The map f can thus be seen as composition of linear layer with weight W, multiplicative pooling layer, and another linear map M. Since is permutation invariann and can be applied to any number of input vectors, this map can be used as both the aggregation, update, and readout functions of a GNN using non-linear activation functions, which leads us to introduce the novel CP layer for GNN.
Definition 1. (CP layer) Given parameter matrices M Ra R and W F and activation functions o', rank R CP layer computes the function fcr Ulz1 (RF)
8 + Rd defined by
fCP(XI, xx)= =o' (M
W
X
WT
xx 1
for any and any X1. X F.
The rank R of a CP layer is a hyperparameter controlling the trade-off between parameter efficiency and expressiveness. Note that the layer computes AGGREGATE and UPDATE (see Eq. in one step. One can think of the womeonent-wise product of the W Xx 1]T AGGREGATE, while
5

---

the UPDATE corresponds to the two non-linear activation functions and linear transformation M. We observed in our experiments that the non-linearity a is crucial to avoid numerical instabilities during training caused by repeated products of W. In practice, we use Tanh for a and ReLU for a'. Fig. graphically explains the computational process of a CP layer, comparing with a classical sum pooling operation. We intuitively see in this figure that the CP layer is able to capture high order multiplicative interactions that are not modeled by simple aggregation functions such as the sum or the mean. In the next section, we theoretically formalize this intuition.
The sum, mean and max poolings result in O(F Fout)) time complex- ity, while CP pooling is O (R((NFis F where N denotes the number of nodes, Fin is the input Fout)),
Complexity Analysis
feature dimension, Fout is out feature dimension, and R is the CP decomposition rank. In Sec. 6.3, we experimentally compare tGNN and CP pooling with various GNNs and pooling techniques to show the model efficiency with limited computation and time budgets.
4.2 Theoretical Analysis
We now analyze the expressive power of CP layers. In order to characterize the set of functions that can be computed by CP layers, first introduce the notion of multilinear polynomial. A multilinear polynomial is special kind of veluer- multivariate polynomial in which no variables appears with power of 2 or higher. More formally, we have the following definition.
Definition function g R >> called a univariate multilinear polynomial if it can be written as
g(a 02
.xk
Σ
Σ
T2 01 a ..
where each Tiysg--ii E R. The degree of a univariate multilinear polynomial is the maximum number of distinct variables occurring in any of the non-zero monomials Ti,ig--.,, 31 .....
A function (R2))* + R" called a multilinear polynomial map if there exist univariate multilinear polynomials Iiare" Sn for J1,".., "i [d] and i 'p] such that
f(x1,".-,,x
Σ
Iisir di ((x))s>"" (xx)
21, j===
for all "1. .xx E Idd and all E [p]. The degree of f is the highest degree of the multilinear polynomials 9i.fi."
The following theorem shows that CP layers can compute any crrmutation-inaaiian multilinear polynomial map. We also visually rep- resent the expressive power of CP layers in Fig. 3, showing that the class of functions computed by CP layer subsumes multilinear polynomials (including sum and mean aggregation functions).
Aperopiiis brsccioss
Theorem 1. The function computed by a CP layer (Eq. equation 1) is cnniunattioo-ivariannn In addition, any permutation-invarian multilinear polynomial f (RFF* + IRd can be computed by a CP layer (with a linear activation function).
Figure 3: Visualization of relations of [permutation-invarian
Note also that in Fig. 3 the CP layer is strietly permutation invariant multilinear polynomials due to the non-linear ac- tivation functions Def. 1. Since the classical sum and mean pooling aggregation functions are degree 1 multilinear polynomial maps, it readily follows from the previous theorem that the CP layer is more expressive than these standards aggregation functions. However, it is natural to ask how many parameters a CP layer needs compute sums and means. We answer this question in the following theorem.
expressive than
function space) 2 (CP function space] 2 (permutation-invaaraat
multilinear polynomial space) 2 (sum and mean aggregation functions).
Theorem 2. A CP layer of rank F k can compute the sum and mean aggregation functions over k vectors in I...
Consequenll,, for any k 2 and any GNN N using mean sum pooling with feature and embedding dimensions bounded by F, there exists a GNN with CP layers of rank F & computing the same function as N over all graphs of uniform degree k.

---

It follows from this theorem that a CP layer with 2 can compute sum and mean aggregation over sets of vectors. While Theorem shows that any function using sum and mean aggregation can be computed by CP layer, the next theorem shows that the converse is not true, i.e., the CP layer is strictly more expressive aggregator than using the mean or sum.
Theorem 3. With probability one, any function fCP (BR)* - BRd computed by CP layer (of any rank) whose parameters are drawn randomly (from a distribution which continuous w.r.t. the Lebesgue measure) cannot be computed by function of the form
9sm X1,
Xx. H
M
Σ WT
where M E RdxR W WER" F and o, a' are component-wise activation function.
This theorem not only shows that there exist functions computed by CP layers that cannot be computed using sum pooling, but that this is the case for almost all functions that can be computed by (even rank-one) CP layers.
From an expressive power viewpoint, we showed that a CP layer is able to leverage both low and high- order multiplicative interactions. However, from learning perspective, is clear that the CP layer has a natural inductive bias towards capturing high-order interactions. We are not enforcing any sparsity in the tensor parameterizing the polynomial, thus the number and magnitude of weights corresponding to high-order terms will dominate the result (intuitively, learning a low order polynomial would imply setting most of these weights to zero). In order to counterbalance this bias, complement the CP layer with simple but efficient linear low-orde interactions (reminiscent of the idea behind residual networks (21]) when using it in IGNN:
f(x1. ;,)))) = o' M (M(
W
x
w
Xx
1)) +o"
XI + W xx) (5)
where the first term corresponds to the CP layer and the second one to standard sum pooling layer (with a, o' and o" being activation functions).
Related Work and Discussion
We now discuss relevant work on the parameterization of tensors graph neural networks. In general, our work relates to three areas of deep learning: (1) aggregation functions, (2) universal approximator for set aggregation, (3) high-order pooling, and (4) tensor methods for deep learning.
GNN & Aggregation Scheme [26] successfully define convolutions on graph-structured data by averaging node information in neighborhood. [48] prove the incomplete expressivity of mean aggregation to distinguish nodes, and further propose use sum aggregation to differentiate nodes [13] further generalize this idea and show that mean aggregation can be a particular case of sum aggregation with a linear multiplier, and further propose an architecture with multiple aggregation channels to adaptively learn low-order information. Most GNNs use low-order aggregation schemes for learning node representations. To the best of our knowledge, tGNN the first GNN architecture that adopts high-order multiplicative interactions in aggregation.
with similar properties.
Universal Approximator & Permutation-invarian NN Universal approximators for set aggre- gation functions have been previously proposed and studied. [51] show that sum pooling is enough provided that it combined with two universal approximators. [48] further discuss the limitations of non-injective set function. [25] propose a generalization of transformers to permutation innuuttaioonnivriian invariant sets. Most universal approximation results for GNN relies on combining simple aggregation functions (e.g. sum, mean) with universal approximators for the feature and output maps. In contrast, the CP layer achieves the same goal of being an universal approximator but using a different mean: explicit computation of multilinear polynomials (in an effective manner using the CP parameterization) While the approaches might be expressively similar, they may differ from a learning aspect, i.e., how easy it is for these models to learn a function from data.
High-order Pooling [2] formulate the pooling problem as multiset encoding problem with auxiliary information about the graph structure, and propose an attention-based pooling layer that captures the interaction between nodes according to their structural dependencies. [46] apply second- order statistic methods because the use of second-order statistics takes advantage of the Riemannian
7

---

geometry of the space of symmetric positive definite matrices. However, high-order in CP pooling refers to high- high-dimensional multiplicative feature products, which is different than previous literature.
Tensor Methods Tensor methods allow one to define meaningful geometries to build more expres- sive models. Authors in [52, 30] define geometries of tensor networks on complex or hypercomplex manifolds, their models encompass greater freedom in the choice of the product between the algebra elements. [7] develop a general framework for both probabilistic and neural models for tree- structured data with a tensor-based aggregation function. [6] leverages
CP-based aggre- gation function to capture high-order interactions NL.P tasks. Using multiplicative interactions as powerful source of non-linearities in neural network models have been studied previously for convolutional [11, 10, 32] and recurrent networks [41, 44, 47J. The connection between such multi- plicative interactions with tensor networks have been leveraged both from theoretical and practical perspectives. The CP layer can be seen as a graph generalization of the convolutional and recurrent arithmetic circuits considered in [10] and [31], respectively.
cormuuatiooninvvriii
6 Experiments on
Datasets
In this section, we evaluate Tensorized Graph Neural Net on real-world node- and graph-level datasets. We introduce experiment setup in 6.1, compare IGNN with the state-of-the- arts models in 6.2, and conduct ablation study on model performance and efficiency in 6.3. The hyperparameter and computing resources are attached in Appendix K. Dataset information can be found in Appendix J.
6.1 Experiment Setup In this work, we conduct experiments on three citation networks (Cora, Citeseer, Pubmed) and three OGB datasets (PRODUCTS, ARXIV, PROTEINS) [23] for node-level tasks, one OGB dataset (MolH/V) [23] and three benchmarking datasets (ZINC, CIFARIO, MNIST) [14] for graph-level tasks.
Training Procedure For three citation networks (Cora, Cileseer, Pubmed), we run experiments 10 times on each dataset with 60%/20%/20%% random splits used in [9], and report results in Tab. 1. For data splits of OGB node and graph datasets, we follow [23], run experiments times on each dataset (due to training cost), and report results in Tab. 1, 2. For benchmarking datasets, we run experiments 5 times on each dataset with data split used in [14], and report results in Tab. 2. To avoid numerical instability and floating point exception in (GNN training, we sample 5 neighbors for each node. For graph datasets, we do not sample because the training is already in batch thus numerical instability can be avoided, and we apply the CP pooling at both node-level aggregation and graph-level readout.
Model Comparison IGNN has two hyperparameters, hidden unit and decomposition rank, we fix hidden unit and explore decomposition rank. For citation networks, we compare 2-layer GNNs with 32 hidden units. And for OGB and benchmarking datasets, we use 32 hidden units for IGNN, and the results for all other methods are reported from the leaderboards and corresponding references.
Particularly, IGNN and CP pooling are more effective and expressive than existing pooling techniques for GNNs on two citation networks, two OGB node datasets, and one OGB graph dataset in Tab. 1, 2.
6.2 Real-world Datasets
In this section, we present IGNN performance on node- and graph-level tasks. We compare (GNN with several classic baseline models under the same training setting. For three citation networks, we compare tGNN with several baselines including GCN [26]. GAT [45], GraphSAGE [19], H₂GCN [54], GPRGNN [9], APPNP [27] and MixHop [1]; for three OGB node datasets, we compare 1GNN with MLP, Node2vec [17], GCN [26), GraphS AGE [19] and DeeperGCN [33]. And for graph-level tasks, we compare iGNN with several baselines including MLP, GCN [26], GIN [48), DiffPool [50],
GAT [45], MoNet [37], GatedGCN [4], PNA [13], PHMGNN [30] and DGN [3]. The model choice is because we propose a new pooling method and want to mainly compare IGNN with other poolings in standard GNN architectures. Current leading models on OGB leaderboards [23] adopt transformer, cquivariant, fingerprint, C&S, or others, which are more complex than standard GNNs. We visualize the performance boost and comparisons with GNNs and pooling techniques in Tab. 1,2.
From Tab. 1, we can observe that tGNN outperforms all classic baselines on Cora, Pubmed, PROD- UCTS and ARXIV, and have slight improvements on the other datasets but underperforms GCN on Citeseer and DeeperGCN on PROTEINS. On the citation networks, iGNN outperforms others on out of 3 datasets. Moreover, on the OGB node datasets, even when tGNN is not ranked first, it is still very competitive (top 3 for all datasets). We believe is reasonable and expected that 1GNN does not outperform all methods on all datasets. But overall (GNN shows very competitive performance and
8

---

Table I: Results of node-level tasks. Left Table: tGNN in comparison with GNN architectures on citation networks. Right Table: 1GNN in comparison with GNN architectures on OGB datasets.
DATASET MODEL
Cars
Cheeseer
Pubmee
DATASET
PRODUCTS
ARXIV
PROTFINS
Asc
Aec
Ace
GCN
08876+00.006
0.00-
MODEL
Acc
Asc
AUC
GAT
0.886
0.028 06620000.0066
ML.P
0.6006+0.0088
0.5550++0.023
0.7204++0.0048
GriphSAGE
0.865810. 0026
0,762410,0000
0,865810.000 0.0001
Node2vec
0.7249+0.0010 0.7007=+0.001
0.6881 +000006
HyGEN
08752+000065
0.7992+000009
0.777800.0025
GCN
0.7564+0.002 0.7174+0.0029
0.7251+000035
GPRUNN
000000
0.676310.0038
0.8507
GraphSAGE
0:7850+0.0016 0.7149:000002
0,7768++0.000
APPNP
0,7941:10.00 0018
0.60590000000
0.5022000000 0,0009
DeeperGCN
0.8008:0000000 0.7192=000006
0.8580=00.00
MixHop
0.6565=0.1131
0.405240.1335
0.8704=0.0400
IGNN
0.8808.10.0131
0.80.5110..119
0.900010.0018
IGNN
0.8179:000054
0.7538=000005
0.8255:+0.0049
deliver significant improvement on challenging graph benchmarks compared to popular commonly used pooling methods (with comparable computational cost).
Table 2: Results of tGNN on graph-level tasks in comparison with GNN architectures.
Table 3: Results of the tGNN ablation study on two node- and one graph-level tasks. tGNN in comparison with high-order CP pooling and low- order linear sum pooling.
Nacelge
elgg Icaaro
Nooege
Anc
AUC
MLP
1000010001
B 5000
0.04500 MBB
Divivd
GEN
0099110032
0306 IIC
Dilhvl
GXT
0490200036
0363:6002
96255-0003
0.000e0
8.906a0 (01
DATASET
MODEL
Lam
Aue
Pobaeod
Ace
MAF
Macl
0,87220007
0.504400000 100
Non Linear CP Pooting
0,8655 1003/5
0,809_0,0103
0,40710:025
6422260005
0.594e0
Lincar Sum Pooling
0.0027
0.8511 0,0009
0.480100010
Non-l incar CP Cinear Sum
03700800188
09018-000015
0:301=0008
Ta
HIM-GN
DuX
020920000
8727950005
00397:30 809
01756:00
In Tab. 2, we present (GNN performance on graph property prediction tasks. (GNN achieves state- of-the-arts results on MolIIVV, and have slight improvements on other three Benchmarking graph datasets. Overall tGNN achieves more effective and accurate results on 5 out of 10 datasets comparing with existing pooling techniques, which suggests that high-order CP pooling can leverage a GNN to generalize better node embeddings and graph representations.
6.3 Ablation and Efficiency Study
In the ablation study, we first investigate the effectiveness of having the high-order non-linear CP pooling and adding the linear low-order transformation in Tab. 3, then investigate the relations of the model performance, efficiency, and tensor decomposition rank in Fig. 4. Moreover, we compare IGNN with different GNN architectures and aggregation functions to show the efficiency in Tab. 5, 7 by showing the number of model parameters, computation time, and accuracy.
In Tab. 3, we test each component, high-order non-linear CP pooling, low-order linear sum pooling, and two pooling techniques combined, separately. We fix 2-layer GNNs with 32 hidden unit and 64 decomposition rank, and run experiments 10 times on Cora and Pubmed with 60%/20%6222% random splits used in [9], run ZINC times with 10,000//,,00/1, 1,000 graph split used in [14].
From the results, we can see that adding the linear low-order interactions helps put essential weights on them. Ablation results show that high-order CP pooling has the advantage over low-order linear pooling for generating expressive node and graph representations, moreover, tGNN is more expressive with the combination of high-order pooling and low-order aggregation. This illustrates the necessity of learning high-order components and low-order interactions simultaneously in IGNN.
Computational Aspect In Fig. 4, we compare model performance with computation costs. We fix a 2-layer tGNN with 32 hidden channels with 8,16,..,,0048, 4099 rank, and 2-layer baselines with 8, 204.8,,0048,, 4096 hidden dim. We run 10 times on each citation network with the same 60%/20%//05f random splits for train/validation/eest and draw the relations of average test accuracy, rank/hidden dim, and computation costs. From the figure, we can see that the model performance can be improved with higher ranks (i.e., Tensor T more accurately computed as the rank R gets larger), but training time is also increased, thus it is trade-off between classification accuracy and

---

Con
Suared tge
1pth l01e
patrec gin
12gin
toge
5000
200
18-
Epoch per www.seeeeaaa ot
Accuroo995
Esoch pCY SCOEII
04-
300
classn
sutenod
puteoed Nooe ecc
303
Cora Apored Acc
300
2009
11030
7006
2700
1000
2005
2008
2000
Bank Dim for ICMMutadden Cam Beran Staees
Figure 4: Results of node classification with increasing rank dimension three citation datasets. Left Figure: Left axis shows accuracy, right axis shows #training epochs second, and horizontal axis indicates rank dim of IGNN hidden dim of baselines. Right Figure: Left axis shows accuracy, right axis shows #training epochs second, and horizontal axis indicates rank dim of IGNN.
computation efficiency. And in comparison with baselines, (GNN still has marginal improvements with higher ranks while the baselines stop improving with larger hidden dimensions.
In Sec. 4.1, we theoretically discuss the time complexity of tGNN. In Appendix H, we experimentally assess model efficiency by comparing 1GNN with GCN [26], GAT [45], GCN2 [8], and mean, max poolings Cora on CPU over 10 runtimes, and compare the number of model parameters, training epochs per second, and accuracy. The experiments show that IGNN is more competitive terms of running time and better accuracy with fixed number of parameters and the same time budget.
7 Conclusion and Future Work
In this paper, we theoretically develop a high-order permutation-invarian invariant multilinear map for node aggregation and graph pooling via tensor parameterization. We show its powerful ability compute multilinear polynomial including sum and mean pooling functions. Experi- ments demonstrate that &GNN is more effective and accurate on 5 out of 10 datasets, showcasing the relevance of tensor methods for high-order graph neural network models.
any pernutation-invarte
For future work, one interesting direction is to augment various GNN architectures with non-line non-linear high-order CP layers. Most the existing GNN models adopt low-order aggregation and pooling functions, it would be interesting to equip current state-of-the. of-the-art models with high-order pooling functions for potential performance boost. Another interesting direction is to enhance tGNN with adaptive channel mixing mechanism. In (GNN with high-order and low-order pooling functions, one node receives two channels of information combined in a linear way. The linear combination may not be sufficient balance and extract high-order components and low-order components, would be interesting to design an adaptive channel mixing tGNN model for learning from different node-wise components.
Acknowledgements
This research was supported by the Canadian Institute for Advanced Research (CIFAR Al chair program), the Natural Sciences and Engineering Research Council of Canada (Discovery program, 2117N-2019-059499 This research was enabled in part by support provided by Calcul Québec (www.caleulquchec.o and the Digital Research Alliance of Canada (alliance.can can.ca). The authors acknowledge the material support of NVIDIA in the form of computational resources.
10

---

References
[1] S. Abu-EI-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan. G. Ver Steeg, and A. Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[2] J. Back, M. Kang, and S. J. Hwang. Accurate learning of graph representations with graph multiset pooling. arXiv preprint arXiv:2102.11533 2021.
[3] D. Beani, S. Passaro, V. Létourneau, W. Hamilton, G. Corso, and P. Liò. Directional graph networks. International Conference on Machine Learning, pages 748-758. PMLR, 2021.
[4] X. Bresson and T. Laurent. Residual gated graph convnets. arXiv preprint
2017.
[5] X. Cao and G. Rabusseau. Tensor regression networks with various low-rank tensor approxima- tions. arXiv preprint arXi:: 2017.
[6] D. Castellana and D. Bacciu. Learning from non-binary constituency trees via tensor decompo- sition. arXiv preprint arXiv:201 J. 1.00600, 2020.
[7] D. Castellana and D. Bacciu. tensor framework for learning in structured domains. Neuro- computing, 470:405-422 2022.
[8] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
[9] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations. hutp://openneviiw. netiforrum, 2021.
[10] N. Cohen, O. Sharir, and A. Shashua. Deep simnets. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4782-4791, 2016.
[11] N. Cohen, O. Sharir, and A. Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory, pages 698-728. PMLR, 2016.
[12] Comon, G. Golub, L.-H. Lim, and B. Mourrain. Symmetric tensors and symmetric tensor rank. SIAM Journal Matrix Analysis and Applications, 30(3): 2008
[13] G. Corso, L. Cavalleri, D. Beaini, P. Lio, and P. Velickovic. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1327,, 2020.
[14] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural
networks. arXiv preprini AxXiv:2003000983 2020.
[15] Errica, M. Podda, D. Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint 1:X1v:1912.09893, 2019.
[16] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals. and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume -oolmme 70, pages 1263-1272. JMLR. org, 2017.
[17) A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pages 855-864. ACM, 2016.
[18] W. L. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 1459) 2020.
[19] W. L.. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. 2017.
arXiv, abs/1706.002)
[20] W. L. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint
2017.
[21] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[22] L.. Hitchcock. The expression of a tensor or a polyadic as a sum of products. Journal of Mathematics and Physics, 6(1 6(1-4):164-18, 1927.

---

[23] W. Hu, M. Fey, M. Zitnik. Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph
benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
[24] H. A. Kiers. Towards standardized notation and terminology in multiway analysis. Journal of Chemometrics: A Journal of the Chemometries Society, 14(3):105-122. 2000.
[25] J. Kim, S. Oh, and S. Hong. Transformers generalize deepsets and can be extended to graphs & hypergraphs. Advances in Neural Information Processing Systems, 34, 2021.
[26] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv, http:/6090000000 2016.
[27] Kliepera, A. Bojehevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 2018.
(28) T. G. Kolda. Numerical optimization for symmetric tensor decomposition. Mathematical Programming, 151(1):225-24) 248, 2015.
[29] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM review, 51(3):455- 500, 2009.
[30] T. Le, M. Bertolini, F. Noé, and D.-A. Clevert. Parameterized hypercomplex graph neural networks for graph classification, arXiv preprint vrXiv:2103.16588 2021.
[31] Y. Levine, O. Sharir, and A. Shashua. Benefits of depth for long-term memory of recurrent networks. 2018.
[32] Y. Levine, D. Yakira, N. Cohen, and A. Shashua. Deep learning and quantum entanglement: Fundamental connections with implications to network design. In International Conference on Learning Representations, 2018.
[33] G. Li, C. Xiong, A. Thabet, and B. Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint wxXiv:20060077399 2020.
[34] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Is het- erophily a real nightmare for graph neural networks to do node classification? arXiv preprint Sifi:22009006444 2021.
[35] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Revisiting heterophily for graph neural networks. arXiv preprint arXiv:2210.07606 2022.
[36] S. Luan, M. Zhao, C. Hua, X.WW Chang, and D. Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint wrXiv:2008.08444 2020.
[37] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5124, 2017.
[38] A. Novikov, M. Trofimov, and I. Oseledets. Exponential machines. arXiv preprint arXiv:1605.0379. 2016.
[39] Y. Peng. A. Ganesh, J. Wright, W. Xu, and Y. Ma. Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE transactions pattern analysis and machine intelligence,
2012.
[40] G. Rabusseau and H. Kadri. Low-rank regression with tensor responses. Advances in Neural Information Processing Systems, 29, 2016.
[41] O Sharir and A. Shashua. On the expressive power of overlapping architectures of deep learning. arXiv preprint arXiv: 1tth::1700000555 2017.
[42] C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang. Graphaf: flow-based autoregressive model for molecular graph generation. arXiv preprint ArXiv:2001.09388 2020.
[43] E. M. Stoudenmire and D. J. Schwab. Supervised learning with quantum-inspired tensor networks. arxiv 2016. arXiv preprint arXiv: 1600: 05775.
[44] I. Sutskever, J. Martens, and G. E. Hinton. Generating text with recurrent neural networks. In ICML, 2011.
[45] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv, 0ts/11700.1003, 2017.
12

---

[46] Z. Wang and S. Ji. Second-ore order pooling for graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[47] Y. Wu, S. Zhang, Y. Zhang, Y. Bengio, and R. R. Salakhutdinov. On multiplicative integration with recurrent neural networks. Advances in nearal information processing systems, 29, 2016.
[48] K. Xu, W. Hu. J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1010:08810000822 00866, 2018.
[49] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983, 2018.
[50] R. Ying. J. You, C. Morris, X. Ren, W. L. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling, arXiv preprint arXiv:1806. 08804, 2018.
[51] M. Zaheer, S. Kottur, Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. Smola. Deep
sets. Advances in neural information processing systems, 30, 2017.
[52] S. Zhang. Y. Tay. I.. Yao, and Q. Liu. Quaternion knowledge graph embeddings. arXiv preprint arXiv: 1904. 10281, 2019.
[53] X. Zhang, Z.-H. Huang, and Qi. Comon's 's conjecture, rank decomposition, and symmetric rank decomposition of symmetric tensors. SIAM Journal on Matrix Analysis and Applications, 37(4):119-11728 2016.
[54] J. Zhu, Y. Yan, L. Zhao, M. Heimann. L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
[55] 7. Zhu, 7. Zhang, I..P. Xhonneux, and J. Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. arXiv preprint (rXiv:2106006935, 2021.
13


Reviews:
[{"review_id": "y2StMIjbJLB", "reviewer": "Reviewer_974s", "summary": "The paper proposes a novel aggregation (pooling) layer for GNNs, called CP layer. The main idea consists of leveraging multilinear tensor decomposition to model high-order polynomial interaction between the components of node embeddings (the final design also employs non-linear activation functions). The authors show that the proposed layer is strictly more expressive than typical neighborhood aggregation functions, e.g., sum or mean. Experiments on many benchmarks (including OGB) assess the effectiveness of CP layers. ", "questions": "- In the experiments, tGNN applies sampling \"to avoid numerical instability and floating point exception in tGNN training\". What is the source of this numerical instability? Is it a strong limitation?\n- Table 1 reports numbers for GPRGNN and APPNP from [1]. However, I wonder if there are differences in the evaluation setup between this paper and [1] as [1] reports, e.g., 0.7521 for GCN as opposed to 0.8778 here. Also, there is a big gap between GAT and GCN which is not often observed on Cora, Citeseer, and Pubmed. What is the source of these differences?\n- In the node-level experiments, tGNN samples 5 neighbors. It is possible that performance gains come from this regularization. Can you provide evidence that this is not the case?\n- Classical GNNs model high-order node interactions by stacking simple low-order layers, possibly interleaved with MLPs. Can you elaborate more about the possible gains of using CP instead? \n\n[1] https://openreview.net/pdf?id=n6jl7fLxrP", "limitations": "The limitations are briefly mentioned throughout the paper, but no dedicated section/paragraph is provided.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper reads well and tackles a relevant issue in GNNs: neighborhood aggregation. The evaluation setup is comprehensive. The empirical results are promising but not outstanding. The paper also lacks a stronger motivation to support the novel GNN design, either in terms of GNN's expressiveness or by characterizing relevant inductive biases for certain tasks.  \n\nStrengths\n- The evaluation setup considers a number of relevant benchmarks\n- The proposed model is simple and easy to grasp\n- The contribution is novel in the sense that is the first paper to leverage multilinear tensor decomposition for improved neighborhood aggregation\n\nWeaknesses\n- Despite showing positive results for CP layers, tGNN is not provably more expressive than classic 1-WL GNNs (e.g., GIN). Since inductive biases are not universal, the paper does not discuss when (and why) the proposed design is desirable.\n- It seems the method suffers from numerical instability. This issue is not properly discussed in the paper.\n- Some numbers reported in the paper are inconsistent with the literature.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "t5WOZyb8qPI", "reviewer": "Reviewer_1gCd", "summary": "This paper proposes to consider non-linear high-order multiplicative interactions among nodes with symmetric tensor decomposition, for node aggregations in graph neural networks (GNNs). In particular,\n* The authors motivate that existing GNNs rely on naive pooling operations, such as sum or mean, which are insufficient for aggregating nodes for obtaining node- and graph-level representations.\n* The authors then propose to consider high-order interactions among nodes with the existing symmetric CP decomposition scheme, and the authors show that the proposed one can approximate permutation-invariant multilinear polynomial including sum and mean aggregations.\n* The authors verify their model on node and graph classification benchmark datasets, on which the proposed method named tGNN outperforms existing baselines on most datasets.", "questions": "### Major Questions and Suggestions\n* Regarding analyses on the model complexity, I suggest authors increase the number of sampled nodes (currently, they are too small, for example, 3 or 5) and then compare the complexity across different models in this setting of increased sample sizes. \n* Also, regarding analyses on the model complexity, I suggest the authors include the complexities of baselines in Figure 4 of the main paper, and then discuss the complexity by comparing the proposed tGNN and baselines.\n* There are two related works: 1) There is a relevant work that considers interactions among nodes on graph pooling, which is also a universal approximator for set aggregation [1]. 2) There is a relevant work that proposes second-order pooling for graph neural networks [2]. Those works should be discussed and compared on the graph classification task.\n* In Table 1, why the most basic GCN outperforms all the other recent GNNs, which is quite weird?\n* Also, it is quite weird that the performance results in Table 1 and Table 4 are different.\n* I suggest authors empirically verify that the CP layer can approximate sum and mean pooling functions. While the authors theoretically analyze that the proposed CP layer can compute them, I am not certain this is empirically possible, as the CP layer tends to capture high-order interactions as in Line 202 while ignoring low-order interactions.\n* Also, similarly to the above question, the evidence of tenting to capture high-order interactions and why not exist. I would like to see how much and why the CP layer prefers high-order interactions. \n* In Figure 2, which part is the illustration of sum pooling? It seems there is only the illustration of the proposed CP layer, and the sum pooling is not illustrated but mentioned in the caption.\n\n### Minor Questions and Suggestions\n* This is a simple question that is the linear sum pooling in Table 3 the model of equation (5) without using the left (first) term?\n* The number of sampled nodes is not consistent across different tables: in Line 263, the authors sample 5 neighbors, however, in Table 4, the authors sample 3 neighbors. Why does there exists inconsistency?\n* In Line 288, the description is not matched to the results in Table 1: there are no datasets that the proposed tGNN is ranked at four.\n* I cannot see the text in Figure 3 clearly, due to its background color.\n\n### Typos\n* In line 154, such at -> such as.\n\n---\n\n[1] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR 2021.\n\n[2] Second-Order Pooling for Graph Neural Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020\n\n---\n\n**Update after the author-reviewer interaction phase**: thanks authors for additionally revising the manuscript. Since I cannot write public comments that the authors can see anymore, I leave my update here. The revision looks good and I am further satisfied with it. Thus, I increase my score from borderline accept to weak accept, and hope the authors move some of the revision in Appendix to the main page, if additional one page is allowed.", "limitations": "The authors do not describe the limitations and potential negative societal impact of their work, and simply mark the checklist for this category as N/A. However, I think authors can describe the limitations and", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* The authors propose to consider multiplicative interactions among nodes from the lowest-order to k-order polynomials, rather than only considering k-order polynomials, which is reasonable and interesting. \n* The authors theoretically show that the proposed CP layer can approximate any permutation-invariant multilinear polynomial, which is necessary and valuable.\n* The authors analyze the complexity of the proposed CP layer against the most naive graph neural network with big-O notation, which I appreciate. Also, it seems if we control the decomposition rank carefully, then the complexity of the proposed CP layer becomes reasonable (i.e., complexity is not much high).\n* This paper is well structured and well written.\n\n### Weaknesses\n* This work is not well-positioned against existing works. The authors focus on capturing high-order interactions among nodes, and there are various works that consider such interactions, for example, graph attention network and Graphormer that reflect how each node is related to every other node, which are but not mentioned in the introduction section for motivating authors' work. In this vein, which points are different between those previous works and the proposed work, regarding node-level interactions? It should be discussed.\n* Further, similarly to the above weak point, while the authors propose to consider high-order node interactions, the related work and discussion section (Section 4) barely describes such a point, but rather describing generic aggregation functions, universal approximators, and tensor methods for deep learning.\n* The authors argue that the proposed tGNN achieves state-of-the-art results in Line 13, however, the performance improvements against baselines are marginal. Specifically, in Table 1, it seems the results of the proposed tGNN are not statistically significant compared to the most basic model, namely graph convolutional network (GCN), and further the proposed tGNN underperforms GCN on the Citeseer dataset. \n* The analyses on model complexities are not enough (see suggestions in the Major Questions and Suggestions section below). In particular, the model complexity is not analyzed in terms of the number of sampled nodes, which is currently too small (i.e., 3 or 5) to confirm the proposed tGNN's efficiencies. Also, the computational complexity in Figure 4 is not compared against baselines, but only compared within the proposed models, thus I cannot see how much the proposed tGNN is efficient compared to the previous models, for example, five times slower than the GCN model.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qein0P5NsXr", "reviewer": "Reviewer_2WJs", "summary": "The paper targets at developing a more expressive pooling layer for GNNs, which allows neighboring nodes to perform high-order multiplicative interactions. The authors leverage a rank R symmetric CANDECOMP/PARAFAC (CP) decomposition to design an efficient parameterization of multilinear maps over a set of node representations. The number of parameters is controlled by the rank R. With appropriate non-linear activation function, the paper proposes the CP layer as a high-order graph pooling layer. Theoretical analysis shows that the CP layer can achieve permutation-invariance and is is universally strictly more expressive than sum and mean pooling. With the CP layer, the authors propose tGNN, which uses both the CP layer and the sum/mean pooling layer. Experimental studies on graph and node classification tasks indicate that tGNN can achieve better performances on multiple benchmark datasets.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical derivation of the CP layer is technically sound and novel.\n2. The proposed method shows improved performance across tasks and datasets, along with complete ablation studies.\n3. The paper is overall well-written. \n\nWeaknesses:\n1. There is a missing related work like \"Wang, Zhengyang, and Shuiwang Ji. \"Second-order pooling for graph neural networks.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2020).\" which also explore higher-order pooling. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AVJFNWGeXh_", "reviewer": "Reviewer_vNWo", "summary": "This paper proposes a novel Tensorized Graph Neural Network (tGNN) based on symmetric CP decomposition, which can model high-order non-linear interactions among nodes. It theoretically shows that the CP layer can compute any permutation-invariant multilinear polynomial including sum and mean pooling. Experiments on several benchmark graph datasets demonstrate that the proposed method achieves more effective and expressive results than existing GNN architectures and pooling methods.", "questions": "It would be great if the authors could address the following questions.\n\n1. Why Tanh is chosen for \\sigma and ReLu chosen for \\sigma’?\n2. Which equation is used in the CP layer? the one was given in Definition 1 or Eq. (5)? It is interesting to see how effective is Eq. (5) against the inductive bias towards capturing high-order interactions, which terms, high-order interactions or lower-order interactions, dominate the model performance?\n3. In Lines 262-263, it was mentioned that \"To avoid numerical instability and floating point exception in tGNN training, we sample 5 neighbors for each node.\" How 5 neighbors are sampled for each node? The 5 nearest ones or others?\n4. More discussions about hyperparameter settings should be given based on the results, especially how to set the CP decomposition rank R in practice?\n5. What do the different background colors mean in Tables 1 and 2?\n6. Is there any reason why different evaluation metrics (e.g., Acc and AUC) are used for different datasets?\n\nMinors:\n1. In Figure 1, the three Ns should have the same font size.\n2. In Line 94, \"mode 1 and 2\" --> modes 1 and 2.\n3. In Line 147, \"see Eq.2\" --> see Eq. 2.\n4. In Line 151, \"RelU\" --> ReLU.\n5. In Line 321, \"asses\" --> assess.\n", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is very well motivated and a good application of tensor methods on GNNs.\n- Good problem formulation and insight\n- Works well on the evaluated datasets\n\nWeaknesses:\n\n- Some important results are given without justification, e.g., why Tanh is chosen for \\sigma and ReLu chosen for \\sigma’? How effective is Eq. (5) against the inductive bias towards capturing high-order interactions?\n- There is no discussion about hyperparameter choices and stability, except for simply listing the hyperparameter values in Tables 8 and 9.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept