Breaking the Expressive Bottlenecks of Graph Neural Networks
Authors: Mingqi Yang
Yanming Shen
Heng Qi
Baocai Yin
Venue:  (2021)
Keywords: graph representation learning
graph neural networks
expressive power

Abstract: Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressiveness of graph neural networks (GNNs), showing that the neighborhood aggregation GNNs were at most as powerful as 1-WL test in distinguishing graph structures. There were also improvements proposed in analogy to $k$-WL test ($k>1$). However, the aggregators in these GNNs are far from injective as required by the WL test, and suffer from weak distinguishing strength, making it become expressive bottlenecks. In this paper, we improve the expressiveness by exploring powerful aggregators. We reformulate aggregation with the corresponding aggregation coefficient matrix, and then systematically analyze the requirements of the aggregation coefficient matrix for building more powerful aggregators and even injective aggregators. It can also be viewed as the strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to a special case of low-rank transformations. We also show the necessity of applying nonlinear units ahead of aggregation, which is different from most aggregation-based GNNs. Based on our theoretical analysis, we develop two GNN layers, ExpandingConv and CombConv. Experimental results show that our models significantly boost performance, especially for large and densely connected graphs.

Under review as a conference paper at ICLR 2021
BREAKING THE EXPRESSIVE BOTTLENECKS OF GRAPH NEURAL NETWORKS
A Anonymous authors Paper under double-blind review
ABSTRACT
Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to mea- sure the expressiveness of graph neural networks (GNNs), showing that the neigh- borhood aggregation GNNs were at most as powerful as 1-WL test in distinguish- ing graph structures. There were also improvements proposed in analogy to k-W A-WI. test (k > 1). However, the aggregators in these GNNs are far from injective as re- quired by the WL test, and suffer from weak distinguishing strength, making it be- come expressive bottlenecks. In this paper, we improve the expressiveness by ex- ploring powerful aggregators. We reformulate aggregation with the corresponding aggregation coefficient matrix, and then systematically analyze the requirements of the aggregation coefficient matrix for building more powerful aggregators and even injective aggregators. It can also be viewed the strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to special case of low-rank transformations. We also show the necessity of applying non- linear units ahead of aggregation, which is different from most aggregation-base GNNs. Based on our theoretical analysis, we develop two GNN layers, Expand- ingConv and CombConv. Experimental results show that our models significantly boost performance, especially for large and densely connected graphs.
INTRODUCTION
Graphs are ubiquitous in the real world. Social networks, traffic networks, knowledge graphs, and molecular structures are typical graph-structured data. Graph Neural Networks (GNNs) (Scarselli al. 2008 Gori et al.) 2005), leveraging the power of neural networks to graph-structured data, have a rapid development recently (Kipf & Welling. 2016; Hamilton et al. 2017 Bronstein et al.)
2017 Gilmer et al. 2017; Duvenaud et al. 2015)).
Expressive power of GNNs measures their abilities to represent different graph structures (Sato) 2020j. decides the performance of GNNs where the awareness of graph structures is required, especially on large graphs with complex topologies. The neighborhood aggregation scheme (or message passing) follows the same pattern with weisfiler-lchman (WL) graph isomorphism test (Weisfeiler & Leman 1968) encode graph structures, where node representations are computed iteratively by aggregating transformed representations of its neighbors with structural information learned implicitly. Therefore, the WL test is used to measure the expressiveness of GNNs. Unfor- tunately, general GNNs are at most as powerful as --rrder WL test (Morris et al. 2019 Xu et al.)
2019). There is also work trying improve the expressiveness that are beyond -order WL test
Maron et al. 2019 Morris et al., 2019 Chen et al. 2019 Li et al. 2020b; Vignac et al. 2020). However, the weak distinguishing strength of aggregators
fundamental limitation. The expres- siveness analysis measured by the WI. test assumes that aggregators are injective, which is usually unreachable. Therefore, this motivates us investigate the following questions: What are the key factors to limit the expressiveness of GNN? and how to break these limitations?
Aggregators are permutation invariant functions that operate on sets while preserving permutation invariance. (Zaheer et al., 2017) first theoretically studied permutation invariant functions and pro- vided a family of functions to which any permutation invariant function must belong. (Xu et al, 2019) extended it multisets but only for countable space. (Corso al. 2020 further extended to uncountable space. (Murphy et al.) 2018) and (Murphy et al.] 2019) expressed a permutation in- variant function by approximating an average over permutation-sensiie functions with tractability

---

Under review as a conference paper at ICLR 2021
strategies. (Dehmamy et al. 2019) showed that single propagation rule applied in general GNNs rather restrictive in learning graph moments (Lin Skiena 1995). They and (Corso et al.) 2020 improved the distinguishing strength of aggregation by leveraging multiple basic aggregators (SUM,
MEAN, NORMALIZED MEAN, MAX/MIN, and STD). This strategy showed its effectiveness on tasks taken from classical graph theory.
In contrast to existing studies towards aggregators in GNNs, we provide a new GNN formulation, where the aggregation is represented as the multiplication of the corresponding hidden feature matrix of neighbors and the aggregation coefficient matrix. This new formulation enables us to answer the following questions: (i) when GNN will lose its expressive power; (ii) How to build aggregators with higher distinguishing strength, even injective aggregators. Based on our theoretical analysis, we propose two GNN layers: ExpandingCon and CombConv, and evaluate them on general graph classification and graph regression tasks. Our key contributions are summarized as follows:
We formalize the distinguishing strength of aggregators partial order, and theoretically show that the choice of aggregators can be bottlenecks of expressiveness. We also pro- pose apply nonlinear units ahead of aggregations to break the distinguishing strength limitations of aggregators as well as to achieve an implicit sampling mechanism.
We reformulate the neighborhood aggregation with the aggregation coefficient matrix and then provide theoretical point of view on building powerful aggregators and even injective aggregators.
We propose ExpandingCony and CombConv layers which achieve state-of-the-as perfor- mance on variety of graph tasks. We also show that multi-head GAT is one of the Ex- pandingConv implementations, which brings a theoretical explanation for its effectiveness.
2 PRELIMINARIES
2.1 NOTATIONS
For graph G(V, E). we denote the set of edges, nodes and node feature vectors respectively by Eg. VG and Xg. NNv) represents the set of neighbors v including itself, i.c., .N(v) = {u Val(u, v) Ea} U (u). We use [n] to denote the set 21,2, ..., nJ. {1...] represents multi-set, i.e., a set with possibly repeating clements. II, represents the set of all permutations of the integers to hr where matrix X Raxb X represents the transpose X, and vec(X) e Rabx represents the column stack of X.
IT Al, is reordering of the elements of sequence h according to Given
2.2 GRAPH NEURAL NETWORKS
Most GNNs adopt the neighborhood aggregation scheme (Gilmer al., 2017) to learn the node representations, which utilizes both node features and graph structures. In the k-th layer, the repre- sentation of node
(k) = Upddae(h!!--) (k-1), ((aregaat(((h((>- N()))))).
(1)
Aggregators in GNNs. An aggregator is permutation invariant function (Zaheer et al. 2017) with bounded size inputs. satisfies: (i) size insensitive: an aggregator can take an arbitrary finite size of inputs; (ii) permutation invariant: an aggregator is invariant to the permutation of input. There a limited number basic aggregators such as SUM, MEAN, NORMALIZED MEAN, MAX/MIN, STD, etc. Most proposed GNNs apply one of these aggregators. Sum-of-power -ffwoer-oower mapping (Zaheer ltt al. 2017) and normalized moments (Corso et al. 2020 can also be used as aggregators and they allow for variable number of aggregators.
3 PROPOSED MODEL
In this section, we first formalize the distinguishing strength of aggregators as a partial order, and show why basic aggregators used in popular GNNs become bottlenecks of expressiveness. Then, analyze the requirements for building powerful aggregators and even injective aggregators. Finally, introduce GNN layers based theoretical analysis.
2

---

Under review as a conference paper at ICLR 2021
3.1 DISTINGUISHING STRENGTH OF AGGREGATORS
To ensure generality, our analysis of aggregators is always considered in multisets and uncountable case, where the inputs continuous and with possibly repeating elements. We first introduce distinguishing strength under the concept of partial order (Schmidt) 2011).
Distinguishing strength. The distinguishing strength of aggregatorr foggrt is stronger than faggr2. denoted by Saggri 2 fagorz, if and only if for any two multisets #1 and 2/2 where the number of elements can be different, ( of faggra (x22) Saggri ) * faggri
Meanwhile, if there exist æ' and æ/2 such that f Foggri(es (2x{ * fuggri (xl) but f faggr2 (0grr(((() (x')) = Fagure(<<2. foggri is strictly stronger than fager2. denoted by faggri > feggr2. If fagori z fagor2 faggri. we say these two aggregators have the same distinguishing strength, denoted by faggr1 = Jaggr2. If there exist multisets 21 and 22 such that fagar1 (21) * Sageri (22)), faggrz (21) = -faggr2 (22), and there also exist æ' and æ/2 such that faggri (x') faggrt (2%)), (x))) # 2 we say foggrt and faggrz are incomparable.
Distinguishing strength is partial order, and the set of all aggregators form a poset. In this poset, the aggregators with the greatest distinguishing strength should be injective. With the definition of distinguishing strength, we can compare any two aggregators. The distinguishing strength of widely used aggregators SUM, MEAN, MAX/MIN is incomparable. One can easily give two multisets of elements that are distinguished by one aggregator but are not distinguished by the others showed in (Corso et al. 2020).
Equivariant aggregator. fager (RR2)) - Rd is an equivariant aggregator if and only if fager (( 21, T "22," "",""" T [x))) T fuggr( (1121, "2, " (n))) for any T Rmxd and ((2; E Rd [n]]]-
Widely used SUM and MEAN are equivariant aggregators but MAX/MIN is not. We denote Sagget & Saggr2 a new aggregator by combing faggr1 and Sagar2 with Sagart @ SXagr2(X) Saggr (aggraggr2()) where denotes concatenation.
Lemma 1. (i) For any continuous function g. we have g faygr faggr and when g is injective, Faggr 9 faggri (ii) fagyr1 @ faggr2 2 faggr1 and faggr1 8 faggr2 2 fagge2. If faggr1 and I Saggr2 are incomparable, faggrl @ saagr2 foggrt and faggri Saggrz > faggrz: 25 (iii) Saagr is an equivariant aggregator, then foger (T x1, T. Ø22 "2,...., xnn) 3 Saper (21 22, ... Gn) for any T E mxd and [124 E TRdlie [n]]].
We prove Lemma D in Appendix B Lemma T indicates that aggregators become bottlenecks of distinguishing strength. For the equivariant aggregator, any linear transformation before aggregation and any transformation after aggregation have no contribution to the distinguishing strength. For SUM and MEAN, we have g (T 2,, T DD2 T .T.))) I SUM [1, ... ..,) and I MEAN(#1, 22, ....... ,Tn), where T E R and g can be any continuous function. Based on Lemma [ we can now compare the distinguishing strength of aggregations in some popular GNNs. GIN-0 sums all hidden features of neighbors at first, and then pass them 2-layer MLP. Therefore, when considering in continuous input features space, the distinguishing strength of GIN-O is at most as powerful as the SUM aggregator. GCN uses a NORMALIZED MEAN (denoted by rMMAAN) aggregator. Given a node v and its neighbors, J..
(MEAN(T æ1, T T22 ... T
xx,)) "T....TTTT..
r.EEAN(,, u1, un)
VIV(o))
"ViVO ViV((a))
Auj
V(A((a))) -1 ). aMEAN is also an
hun
equivariant aggregator, and the distinguishing strength of aggregation in GCN is at most as powerful as rMEAN. GAT corresponds to the weighted SUM aggregation, where the weight coefficients
are the functions of hidden features. This makes the distinguishing strength of GAT and SUM incomparable. Based on these observations, a potential approach to breaking the distinguishing strength limitation is to apply a nonlinear processing inputs before aggregation.
3.2 BUILDING POWERFUL AGGREGATORS
In this section, we analyze the requirements for building more powerful aggregators and further injective aggregators. We first introduce a new representation of GNN layers which unifies several popular GNN layers. Given node and its neighbors (w),, our formulation represents the
3

---

Under review as a conference paper at ICLR 2021
GNN operation follows:
my = flocal (v)
1 aggregation coefficients generation */
rv m Foom (1-112
/* neighhorhood aggregation */
(2)
he fNN(r
/ feature/structure extraction */.
Here, m. E IR W(v) is the aggregation coefficients vector of node Note that my should be the mapping of local structures such as node degrees, node or edge features of the k-hop neighbors assigned node to ensure the same encoding of isomorphic graphs. (t-1)) (he (11-1) Ain 11111) h (un)(()) ([(())) the matrix representation of v's neighbors accord-
ing to permutation т. sNN : E - Rdd is neural network that extracts task-relevant information from the aggregated representation r(0, and is used to update hidden feature h!! of node
According to Equation 2 the aggregation should be with high distinguishing strength avoid in- distinguushabiiityy among neighbors. Mcanwhile, the extraction should powerful enough to ef- ficiently extract task-relevant structural patterns from the aggregated representation of neighbors. Based on these observations, we reformulate GCN, GINO and GAT with their corresponding three- stage representations follows:
my V(V() VINTO) ViM(a)))
Vituxio Di
m. = 1 [x]A((0]]
GCN:
(t) m.r hor ((t-1)T
GINO:
r!!)) miia h
h (Wr! + bb,,,
( MMP(r!!)),
m (att(h)' (t-)) h (((11) auths 11) ) auth (f-1), (t-1) (
GAT
re = mon htr (t-
h a (Wr! (+) b).
Their default formulations are given in Appendix A In the aggregation step, GCN's m. is the mapping of neighbors' degrees; GINO's m, the mapping of node v's degree which is equivalent to SUM aggregator; GAT's m,, is the mapping of neighbors' features. All of them are the mappings of local structures given in Equation
In this three-stage representation, the aggregation is reformulated as the multiplication of the aggre- gation coefficients vector and the feature matrix of neighbors. It provides insights on improving the distinguishing strength of aggregations. First, we show how to characterize the permutation invari- ance this formulation. Let M e R*** denote an aggregation coefficient matrix where $ > 1. Note that in GCN, GIN and GAT, is restricted to be 1. h Rnxd is the matrix representation of n input elements according to æ. The aggregation computation the second step of Equation 2 is Sager( M. ) MP
M,h,, where P= is the permutation matrix according to P P_h,, ensures the same output for all hg, π E [[pn-- M, = MP, is the reordering of columns of M according to π. For any æ1, n2 E In, f [M, hn,) = ( h,,), thus permutation invariance holds. Once M is decided, we obtain unique aggregator denoted by fM. For any sequence of input elements h. ( = Jagrr(M (M, hz), where π E II, can be any ordering of neighbors. Next, we analyze the distinguishing strength of fM-
Proposition For any two matrices M E Raxx and M' Re'xn xn with s, & n, we have (i) > fM if and only
f( M. z fM. where ( (M) means stacking these two matrices; (ii) f( M MMM)
if rank(( ( M rank(M) (iii) Any multiset of size is distinguishable with JM if and only if rank M) = n.
M'
Pnpposstionnshowee that the distinguishing strength of fM decided by the rank of the corresponding M. Yet, the distinguishing strength analysis in Proposition Tis only suitable for multisets aggregated with shared fM- Next, we extend the analysis for the case of different aggregators.
We prove Proposition
Tin in Appendix
Let Res(fM denote the set of all outputs of fM- Our proposed three-stage representation also provides useful insight on the constraints among different aggregators. That is, in order to fully distinguish different local structures, for any two different fM, and fM.. Res( fM, n Res(f (f,)) Ø. This is because fully distinguish different local structures, should ensure their aggregated
4

---

Under review as a conference paper at ICLR 2021
representations are different. Since M is restricted to be the mapping of local structures (such k- hop neighbors), different M means that the corresponding local structures are different. Therefore, the aggregation results of different fM must be different. However, it is not satisfied by existing GNNs, and there are few studies on distinguishing multisets aggregated by different aggregators. In Proposition
2
we present detailed analysis of it.
Proposition 2. For any M1, M2 E Raxm and Mi, M2 E Ro''ma, (i) Res(f dd)
(M:) Mi
Res(f M2 MM)
Res(fM,) Res(f (i) If Res(f M. (M,) ), then rank( Mi M2 Mi M; )) > rank(( M. M²)); ));
Res(f M Res(faa)
M;
We prove Proposition 2 in Appendix [ Proposition] 2 shows the necessity of preserving the rank of aggregation coefficient matrix when considering the distinguishing strength among different aggre- gators. Next, we provide a sufficient condition for building desired multiple injective aggregators with the outputs having no intersections.
Proposition For any two aggregators SM, and fM, with M1 E Raxm and M2 E R2x=2, if rank( (M, M² = n1 + n2, then fM, and fM, are injective and Res(f o Res(f Ø.
We prove Proposition 3 in Appendix Proposition 2 and provide a new perspective for build- ing powerful aggregators and even injective aggregators. Compared with the distinguishing strength studies in (Xu al. 2 and (Corso et al. 2020), as well as existing strategies for building injec- tive aggregators, c.g., sum-of-power mapping (Zaheer et al. 2017) and normalized moments (Corso) al. 2020), we reformulate the aggregation with aggregation coefficients matrix and show the re- lations of the distinguishing strength of aggregators and the rank of the corresponding aggregation coefficients matrices. Besides, the aggregation of this method controlled by aggregation coeffi cients which can be learned from graph data to better leverage structural information. In this paper, to simplify the analysis, we only consider the aggregations within one-hop neighbors. The results can be easily extended more sophisticated aggregators with the overall framework unchanged
In the perspective of preserving the rank of hidden features among neighbors, r = Mh indicates that rank(r) & min(rank(AV) rank(h)). To preserve the rank of hidden features in aggregations such that rank(r) = rank(h), we need rank(M) ž rank(h). This builds a connection between improving the distinguishing strength of aggregators and preserving the rank of hidden features among neighbors, both of which have the requirements on the rank of M. General aggregators such as ones in GCN, GIN-O and GAT have rank M) 1. Thus, rank(r) is always fixed no matter what the rank of the input features is. Correspondingly. they have a weak distinguishing strength.
Equation 2 splits the aggregation and feature/structure extraction into two independent steps, which helps to figure out that the expressive power loss happens in the aggregation step, and then the model extracts feature/structure information on the distorted encodings of neighbors. From Equation 2 the aggregation can be considered as representation regularization step, which unifies different mul- tisets of neighbors into the same representation style while holding permutation invariance. Then, the model can extract structural information on this regulated data with shared trainable matrix Based on this observation, we propose two novel GNN layers:
as the third step Equation 2 ExpandingConv and CombConv.
3.3 EXPANDINGCONY
In this section, we first present ExpandingConv framework. Then we provide one of its implementa- tions and analyze how ExpandingConv achieves more powerful aggregations. The ExpandingConv framework is
mae fioca (u, v) (ueN(()) (0) (1-1"") Ju ((())))
h fuger( (vec(m
where may Rex1 with s > and fweal (u, v) is the mapping of local structures between nodes u and v. The implementation of frocat v) is very flexible with the only restriction of ensuring the
same encoding of isomorphic graphs. vec( (1)
bocmmii hu ((-1)T) E Redx1 is the expanded representation
of hidden features 1i (t-1) E Rdx11 Then GNN layer faggr learns structural information on this
5

---

Under review as a conference paper at ICLR 2021
expanded representations. We introduce implelentation follows:
Mur Tanh [ w(h--1) ( I [| b)
he EvEN(w) MLP((ve((m.) (m) h (
In Equation 3 we implement flocal u, v) as the function of hidden features of nodes u and v. There can be other implementations, and we leave them for future work. W Rax2d and b E R are trainable matrices. (Luan et al., 2019) empirically showed that different nonlinear activatoin functions have different contributions in preserving the rank of matrices. We use the recommended
Tanh as the activation function the computation (t) to better preserve the rank of aggregation coefficient matrices. MLP denotes 2-layer perceptron.
Next, we represent Equation 3 with the corresponding three-stage representation given in Section 3.2 to obtain its aggregation coefficient matrix and analyze its distinguishing strength. To simplify this process, We only consider 1-layer MLP with W' Rdxed and b' e Rdx1
h
Σ
(c ( 8')
(E)(
[M)N()) ReLU 10 132
1)² b(1))
EmeNi roc vec 1o + 1/11)
EveN(,) ReLU [2.]] vec 1 (t- 1)) blm))
EmeNato) (W (W vec 12 + 1/4))
EueN(O) ReL.U( [d..] vec (e m 1 b(u))
EveNa(u) (W vec(m 22n D + b(m))
W(1.g
veel (ueNiit)) (-11))
(i(()) 1/11
[2.1]
veel (meeN))))()) m
[N((e)) 6/21
W(aa)
veel vee vec(EneNa(o)
(Vaa(D) 6/4))
W(1.)
vee vee (t) 1
[Wi(o)] b/u)
W
[NG(e)I 1/41
Wiaa)
vee M hoatd
[W(())] b/
(4) where Ni(v) S N(u)li e [d] are sampled subsets of neighbors each di- (0)
mension. M
(munn, Mugus muin
(8) (8)
[ and h
(t-1)
aggregation coefficients matrix and hidden fea- ture matrix corresponding to the subset of neighbors Mi(v) S N(()) according to my We de- note [ (1(t-")
(h (t-1) _
(t-1) .... (an [dx(()(
(t-1)
(h) (--1)) I (t-1) .n (t-1)) (t-)),.. ,..., " " (t-1)
xy(e)) 2dx (GG)), then
M Tanh W " ho (1-1 + b) e [x(())
According to Equation
we finally obtain
the three-stage representation equivalent to Equation
M (anh(W(h. (t-1) [| (e(;""'++b
rs = M ((-11) [
(5)
h diag (L.g We...... ... W(a (()( vec(F(() vec(F(()))
+(M((v)) (GG)) b/2 (Wa(v) )- B(a))"
According to the computation of 7!! rank(=!!)) & min(s, d, [M(())).. By configuring a larger s, have rank(r!!)) with high probability, which is different from general GNNs with a rank of As analyzed in Section 3.2 this achieves more powerful aggregators as well as preserves the rank of hidden features among neighbors. The obtained +(t) after aggregation is the unified repre- sentations neighbors. We then use the trainable matrix W e Radxd to extracts feature/structure information. Unlike the aggregation step, the dimensions reduction here (from sd d) would not cause information loss. This can be explained by the fact that only task-relevant structural informa- tion needs be preserved and passed to the next layer, and it can be embedded in lower dimensions.

---

Under review as a conference paper at ICLR 2021
Comparisons with multi-head GAT.
Proposition 4. Multi-heat GAT is implementation of ExpandingCom as follows:
softmax(LeakyRe 0 IT a aKT)
||diag(a") _² (kkT) ][Wh
h. whhh-111
(t-1)
(6)
h (1) = =o W vec(a )
where W
k- W Rkddd the concatenation the trainable matrix in all K heads.
We prove Proposition 4 in Appendix Although multi-head GAT is based attention mecha- nism, ExpandingCony provides a new perspective to explain its effectiveness. Applying multi-head attention mechanism helps preserve the rank of hidden features well as achieve more power- ful aggregators. However, the usage of LeakyReLU may be harmful to preserving the rank of the aggregation coefficient matrix (Luan al. 2019).
GAT as well as most other GNNs (such as GCN, GIN, etc) follows the same pattern that applies nonlinear units after aggregation. According the analysis in Section [.1] Equation Japplie applies MLP on vec(m ha (=1))) before SUM to break the distinguishing strength limitation of SUM. It also produces other interesting results. By reformulating Equation with its three-stage representation as Equation [] each dimension of hidden features aggregates on a subset of neighbors independently, kind of dimension-wise neighbor sampling mechanism. We call the modifi- cation of applying ReLU ahead of SUM aggregator as Re-SUM mechanism. (Mishra et al. 2020) and (Rong et al. 2019) studied dropedge and node masking mechanism node-level predictions, both of which can be considered as neighbor sampling strategies that have shown their effectiveness in improving the generalization ability of aggregation- -based GNNs and are also used unbiased data augmentation technique for training. Compared with dropedge and node masking, Re-SUM realizes a dimension neighbor sampling, and does not need to manually set the sampling ra- tio since this mechanism takes effects implicitly. Re-SUM shows that the neural network itself can perform sampling by properly combining nonlinear units and aggregators, without explicitly modi- fying the network architecture. Our experimental results verified the effectiveness of the Re-SUM on a variety of graph tasks.
which corresponds
3.4 COMBCONV
The CombConv framework is
mas ( faggr( ((vec(ml)) O h h ) N(o)))),
(t)
fieal (u, v))ueN(1)
where may E gdx1 and @ denotes element-wise product. An implementation of CombConv is given follows:
m Tanh [h (1-1) [ (1 (0) EuEN(y) MLP(m (1) O h (((1))).
where W E dddx2d and b E dx Similar to ExpandingConv, CombConv also applies Re-SUM aggregation. The difference is that each dimension of hidden features aggregated with an indepen- dent weighted aggregator. ExpandingConv with 8 = 1 corresponds to special case of CombConv where all dimensions share the same aggregator. Therefore, the distinguishing strength of Comb- Conv is stronger than ExpandingConv with 1. Meanwhile, CombConv does not expand the hidden features nodes in aggregation. Hence, it requires fewer parameters.
EXPERIMENTS
In this section, we evaluate ExpandingConv and CombCony on graph-level prediction tasks on OGB (Weihua Hu 2020), TU (Kersting et al. 2016; Yanardag & Vishwanathan 2015) and QM9 (Ramakrishnan et al. 2014, Wu et al.) 2018 Ruddigkeit et al., 2012). The code is available at https: //q thub. www...ooomoooooo qs
1 1 epcb -erecc--nnnss-- gnns

---

Under review as a conference paper at ICLR 2021
Configurations. We use the default dataset splits for OGB. The QM9 dataset is randomly split into
80% train, 10% validation and 10% test as given in (Morris et al. 2019 Maron et al. 2019). For TU dataset, we follow the standard 10-fold cross validation protocol and splits from (Zhang al. 2018)
and report our results following the protocol deseribed in (Xu et al. 2019 Ying et al. 2018). We
use the concatenation of hidden features from all layers to compute the entire graph representations
(Xu et al. 2018). In our tests, all models are equipped with batch normalization (loffe & Szegedy) 2015) on each hidden layer when evaluating on OGB and TU, and are not when evaluating on QM9. All datasets' descriptions and detailed hyperparameter settings are given in Appendix H
We first conduct comprehensive ablation studies to evaluate the effectiveness of powerful aggrega- tors and Re-SUM mechanism on OGB and QM9 as given in Table[]and Table Then, we compare the performance of ExpandingConv and CombConv with competitive baselines on all three datasets as given in Table Table 4 to show their improvements. ExpC-s denotes ExpandingCon with W e Rx We use ExpC* and CombC* to denote the ExpandingConv and CombConv without Re-SUM.
Table 1: Ablation studies OGB and QM9, Higher is better.
aghg--pe ppu
ogbg-molhil
ughg-molpcha
ogbe-code
ExpC*-1
70:65
77.63
22.65
32.2
ExpC-1
77.50
76.79
23.39
32.6
ExpC-3,4,5
80.11
77.89
23.44
33,2
CombC"
73.61
76.47
23.45
32,29
CombC
77.64
76.63
23.73
32.72
Table 2: Ablation studies on QM9. Lower better.
Chomo
Clumo
(IL²)
ZPVE
Up
ExpC*-1
0.467
0,288
0.00337
0.00340
0.00467
22.9
0.000205
0,0255
0.0263
0.0342
0.0261
0,1189
ExpC-1
0.00126
0.00329
0.00666
0.000186
0.0199
0.0202
0.0201
0,1039
ExpC-
0.255
0.00273
0.00300
0.0420
19.4
0,000168
0,0184
0.0133
0.8178
00182
0.1115
ExpC-8
0.100
0.257
0.00239
0.00286
0.00395
18.1
0.000112
0,0158
0.0170
0.0177
0.0144
0,1060
ExpC-16
0.382
0.255
0.00248
0,00268
0.00373
17.2
0.000170
0,0170
0.0174
0.0193
0.0165
0.1043
ExpC-32
0.00248
0,00257
0.00364
0.000174
0.0151
0.0167
0.0165
0.0198
0.0962
Combe*
0.4062
0,248
0,00259
0.00273
0.00387
17.1
0.000170
0,0185
0.0181
0.0161
0.0174
0.1022
CombC
0.00261
0,00278
0.00386
0.0147
0.0140
0.0658
4.1 ABLATION STUDIES
Effeet of powerful aggregators. For complex graph structures with dense connections or with abundant node/edge features, they would benefit from a higher expressive model to maximumly distinguish different structures and extract relevant structural patterns as the model goes deeper both QM9 and OGB. We configure
to leverage large receptive fields. This is validated 1,4, 8, 16, 32 of ExpC-8 for all 12 targets of QM9. As we apply a larger 8, the model continuously achieves better performance on most targets. We randomly select molhiv and s = 1,5 for ogbg-code. The results show that applying larger gains performance improvements, especially on ogbg-ppa which involves large graphs with dense connections.
1,4 for ogbg-ppa, ogbg-
Effect of Re-SUM mechanism. In Table I and Table 2 the performance differences between ExpC*-1 (CombC*) and ExpC-1 (CombC) show the effectiveness of Re-SUM. In our tests, the Re-SUM can be extremely powerful on graphs with dense connections such as ogbg-ppa, which is validated on both ExpandingConv (with 6.85% improvements) and CombConv (with 4% improve- ments). On most targets of QM9, this mechanism also gains improvements. For small graphs with sparse connections such as ogbg-hiv and gebg-molpcba. the improvements are not very significant.
4.2 COMPARISONS WITH BASELINES
Table 3 and Table 4 show the performance comparisons of our models with baselines on QM9, TU and OGB respectively. All datasets in QM9 and OGB graph-level predictions are used for evalua- tions. For TU, use 3 widely used datasets: COLLAB includes graphs with dense connections;
8

---

taken Under review as a conference paper at ICLR 2021
Table 3: Comparisons with baselines OGB and TU. Higher is better.
OGB
TU
ophgyppa
ophg-molliv
oghg-melpchs
oghg-code
COLLAR
ROTB
RDT-M2
DGK
& Vohverathan 2015
0.1
PSCN
NEC BI AV10
NA
NA
73.76
0.50
36,30 1.58
41.32
0.42
AWE
19009 Sumeey 2016
NA
NA
NA
NA
75.03 a: 1.94
$7.89
2.53
50.20
2.09
CCN
ANR Welmi 2710
68, 39
0.84
76.06 1. 0.9
20.20
0.24
31.63
0.18
NA
NA
KA
GIN
Aue. (1209122199
68,92 1.0
75,58 1.00
22,66 0.25
31.63 0.20
80.2 1,9
92.4
2.5
KA
GraphSar Hamilia
7
NA
NA
NA
NA
68.25
42.24
DefiPool
Vin Eellenin 2013
75.48
47.08
Cap+ON
PPGN Makggaeleee
DesperCUN Literar 21AM
0.72
[0MP cll (3200 (0/00)
NA
7880
NA
WBGG
K.o.on B
2020 2020
NA
77.57 1.11
NA
NA
NA
NA
NA
multi-h
Volleov 200 2017
NA
75.81
20,10
$1.10
NA
NA
NA
ExpC-x
79.76
77.09
1.75
77.81
Table Comparisons with baselines on QM9. Lower better.
2
(R²)
ZPVF
H
G
DENN
Wa al 5015
0.264
0.95
0.00388
0.05122
0.0122
0.00172
2.43
2.43
2.45
2.43
0.27
MPNN
L Banne Aal P0l
0.355
0.59
000541
B08625
0.0866
28.5
0.80216
2.05
2,02
1,02
0-22
L-GNN
Mounis meinireraal aany
0.476
0.27
000137
000351
010048
22.9
0.00019
0.0227
0.111
0.0119
0/469
0.Р44
PPON
0J934
0.318
BJ80174
RUM21
BJ8829
3.78
0.000800
0.022
0.0904
00294
0.03
0144
GEND
A0
2019
0.371
0.281
0000127
0.01400
0.00175
22.9
0.0002022
0.0244
0.0245
D0233
0,0255
0.1283
GAT-
Vole
2013
0.452
0.286
1100322
0103277
0104660
22.7
0.000228
0.0212
0.0225
0.0223
04219
0.1247
ExpC
0.000160
0.0147
0.0140
REDDIT-BINAL (RDT-B) and REDDIT-MULTI-IE (RDT-MI2) include large and sparse graphs with center node having dense connections with other nodes. All results of baselines from the original papers except for the results of GraphSAGE on TU, multi-head GAT on OGB and GINO* on QM9 which were not reported by the original papers. We report the results of Graph- SAGE provided by (Ying et al. 2018) and evaluate multi-head GAT and GINO* by ourselves, To ensure fair comparison, for OGB and TU, we configure the number of heads in multi-head GAT and s in ExpC-s to be the same which is selected in f3. 4, 5}. For QM9, the number of heads is 8 and s E {4. 16, 32). GINO* in QM9 denotes GINO without batch normalization.
Compared with baselines, our models achieve the best performance on 7 out of all 12 targets of QM9, 3 out of 4 graph-level prediction datasets of OGB and all selected TU datasets. Our models get 1.9% improvements on COLLAB and 2.83% improvements on REDDIT-MULTI-12 compared with SOTA baselines. On ogbg-ppa, our models achieve 2.6% higher classification aceu- racies compared with SOTA baselines. On ogbg-code, they achieve 1.5% improvements. Multi-head GAT can also be considered as an implementation of ExpandingCony However, its performance on graph-level predictions is not competitive. According to its shree-stage representation, the usage of LeakyRel.U in the aggregation step is harmful to preserving the rank, and the usage of softmax makes it harder to analyze the rank. In the extraction step, the l-layer MLP may have limited representation power to represent the desired extraction functions.
5 CONCLUSION
We show how basic aggregators used in general GNNs become expressive bottlenecks. To ad- dress this limitation, develop theoretical foundations of building powerful aggregators. We also propose the Re-SUM mechanism which achieves dimension-wir -iit sampling. To evaluate their ef- fectiveness, develop two novel GNN layers, and conduct extensive experiments public graph benchmarks. The results are consistent with our analysis, and our proposed models achieve SOTA performance variety of graph-level prediction benchmarks.
REFERENCES
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.

---

Under review as a conference paper at ICLR 2021
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pp. 19866-15876, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.057/ 2020.
Nima Dehmamy, Albert-Lászlo Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In Advances in Neural Information Processing Systems, pp. 15413-15423, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems. pp. 2224-2232 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
M. Fey, J. G. Yuen, and F. Weichert. Hierarchical inter-message passing for learning on molecular graphs. ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volunee 70, pp. 1263-1272. JMLR. org, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pp. 729-7349-47 734. IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances Neural Information Processing Systems, pp. 1024-10344 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In Jennifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2191-2200, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http::/pprocceeiggss.o.m press/ (VC/ivanovl8B. html
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http::/ cs. tu- wwwddodd..dd... de
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.00970 2016.
Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann. Wasserstein em- bedding for graph learning. arXiv preprint arXiv:2006.09453 2020.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07733 2020a.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding-destie provably more powerful gnns for structural representation learning. arXiv preprint crXiv:2009.00142, 2020b.
Yaw-Ling Lin and Steven S Skiena. Algorithms for square roots of graphs. SIAM Journal on Discrete Mathematics, 8(1):99-118. 1995.
10

---

Under review as a conference paper at ICLR 2021
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances in neural information processing systems, pp. 10945-10955, 2019.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprini 1905 2019.
Pushkar Mishra, Aleksandra Piktus, Gerard Goossen, and Fabrizio Silvestri. Node masking: Making graph neural networks generalize and scale better. arXiv preprint 2XXi:2001.075244 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602 -609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pool- ing: Learning deep permutation-invariaat functions for variable-size inputs. arXiv preprint 1rXiv:1811.01900 2018.
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. arXiv preprint arXiv:1903.02541 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net-
works for graphs. In International Conference on Machine Learning, pp. 2014-2023, 2016.
Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1:140022, 2014.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Lars Ruddigkeit, Ruud Van Deursen, Lorenz C Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. Journal of chemical information and modeling, 52(1 1):2864-2875, 2012.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Gunther Schmidt. Relational mathematics, volume 132. Cambridge University Press, 2011.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with pressage-passing arXiv preprint drXiv:2006.15107, 2020.
Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta Jure Leskovec Weihua Hu, Matthias Fey. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687. 2020.
B. Yu. Weisfeiler and A. A. Leman. Reduction graph to a canonical form and an algebra arising during this reduction. 1968.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9(2):1335330 2018.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. International Conference on Learn 18
ing Representations, 2019. hwt..nttpee///geeeeeeeee.eeeeeee

---

Under review as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv:1806.03530 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https:
//openreview. net/ 20tt//ormmm2.07ryG6623
Pinar Yanardag and SVN Vishwanathan. Deep graph kerness. Proceedings of the 21th ACM
SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810, 2018
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances neural information processing systems, pp. 3391- 1401,2017
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
12

---

Under review as a conference paper at ICLR 2021
A GCN, GAT AND GIN
Here, we present inplementations of GCN, GAT and GIN for the usage of our analysis.
Graph Convolution Networks (GCN) (Kipf & Welling 2016).
H o (DD H W b)
(8)
Graph Attention Networks (GAT) VVelicković et al., 2017).
h (0 =
Σ att (n!!11) ( Wh Wh (t-1)
(9)
(E)(
Graph Isomorphism Networks (GIN-0) (Xu et al., 2019).
h (
MLP Σ D)
(10)
wEA(e)
B PROOF OF LEMMA
Proof. (i) For any two multisets æi and æ2, if g( ((fnerr (())))(()))) # g(fngr((02)) then Sager # (a Therefore, we have Saggr 2 o Saggr- If g is injective, then Saga sage((()) (21) * fuger (222) Fagge (x1)) # g ((22))(222) We have fager 2 g fagg 2 fuggr. therefore fager = 9 fagar.
(ii) For any two multisets and fagor1( # faggri (x22 = [faggr fagor2 (x1)) # Therefore, fagar1 @ faggrz z Saggri. If faggri and faggr2 are incom- parable, there exist 33 and 24 such that Fagera(1:s) * faggra (xra) but faggr1 (ax3) faggr1 (x:a) Therefore, there exist my and æa such that [faggr (x33) faagr(aggr)2(3s)) but faggr (1rz) faggr1(44)) fogar1 @ fagar2 > Saggri.
[Faggr faggl
[Jaggr (r. (1))llfagrrr axa)]
(iii) Since Sarer is an equivariant aggregator, then Saner (T 21, .., T vn. = T
Sager (Ii, , an) I (nggr(()) (21, "2, Dn.)
C PROOF OF PROPOSITION
Proof. (i)
f (2) = 2g = (m=07) m' x.T fa):(x))
= (Mx(
M'
then for any 2i and 22, have
fm(a1) fM((2)) = F(MM MM (xI1) )x # fl M.
(222),
M.
and therefore we conclude that f( (M) 2 fM.
(ii) f M fM = rank( M )) rank "M)"
M/
M'
We prove the claim by contradiction. Assume that rank((
M/
rank(M and f( M
= fMM
M
f( M. fM means that for any Ti and E2, M2 m 22
M M
x 2in
M
M
I2n.
MM
where π is the ordering of input elements. Let s = Fix C25. For any i E [n]. s[i] = x [i]
M' ) s = O. The system of linear equations æ 0 and M' ) 0 share the same solution space. Let Rts denote the rank of this solution space, then rank(m.)) + Rss rank( MM )²) + Rs n. Therefore, (ank(m-) rank MM ),)) then we have rank( M) rank(( M )). Since we assumed that rank( (M )) > rank M), we reach a contradiction.
22n [ E R. Then for any 8 E R", m,8 = 0 <>
M
M
"f(MM (M) > fM = rank( ( M rank(M)" M'
13

---

Under review as a conference paper at ICLR 2021
We prove equivalent proposition "rank(( M M'
rank(M)
f(m fM" Note that
M'
rank(( M' )) > (M) and f( M fM given in Proposition
ii).
We only need to prove
M'
"rank(( (M-) rank(M { M'
fM" rank(( M. rank MM) means that any row in
M' is linearly dependent to rows in M. Therefore, there exists L E R so that (M) M..
For any 21 and 22 with M 11 M MP,aa 2. (1 ML)MPr = (1MMP= and therefore M PI = ( M D2n, where is the ordering of input elements. That is, for any æ1 and {( MM (22)), thus { ((M)
M
22 fM (x2) > {( M M
(an)
fM. Finally, we have
MM
MM))
f M
= fM.
(iii) "Any multiset of size is distinguishable with fM rank (M) n"
Since Ma) & n, we prove an equivalent proposition "rank(M) < = there exists at least two multisets which indistigguisaable... Considering the system of linear equations y M where a E R., if (Mn < n, then there exists y such that rank(M) rank( y') < n. According to the CapcélCCapelli theorem, there are infinite solutions æi such that y Mæ'
Mæ'
Mæ'., Each x comes from a multiset with particular order. Next, we need to prove that all these x come from more than one multiset. As a multiset with bounded size n constitutes at most n! different orders, the infinite number of æ² corresponds to y must come from more than one multisets, making these multisets indistinguishable.
"Any multiset of size is distinguishable with fM rank MM n
Since rank( M) and n, for any x E R", y Mæ IR" unique. Correspondingly, for any PT M (,. is unique.
D PROOF OF PROPOSITION
11), F( M (a:) fM f2)(())) faa((x))
Proof. (i) According to the proof of Proposition
For any an and
Mr
22 with f M,
f(M,)
(x1) = f( M:
(x2), faz (x1)
fML, (xx2) holds. Meanwhile, f M, (x1) =
Mi
MM
M
f (M:))
(122) E Res(f
) Res(F
M. and fM, (x1) (x2) Res(fM. ) Res(effa) Mr
M,
M;
Mr
Therefore, for any e E Res( (f
a Res(f (f, M. ). we have e Res(fM,) n Res(fM,, That is
M
My
Res(f
Mi Res(f
Ma M
S
Res( Res(fM,) ) Res( fMa.).
M
(ii) We prove an equivalent proposition "Res(f M ) Res(S (f (Ma)) ) Res( M
My
rank(( M, Ma )) = rank(( ( M, Mz))". rank(( Mi M²
M, M
)) = rank( ( (M, Mz)) means that any row in
M; M;
(Mr; M; is linearly dependent to [,, Ms Therefore, there exists L R so that M M²
M, M.
(E) M, Mz). Correspondingly. (M)
M, (L) and (M: M2 For any 21 and X2
with P.P. M2Pap22x (1. M4 M2P,P 11 = M M2P,Ta2. and therefore [M] PI
M,
( Ma P2 where æ is the ordering of input elements. Thus for any œ1 and 22, fM, (x1) (z1)==(())
M,
fM. (x2) Res(fM,) (effffa)RRRsse (oRe)(ffe))))))) = {(M M,
f( (MM
(x2) Res(f ( [M )o f Ma [M]]
M³
Mi
Hence, Res(SM)) o Res(sMa) S Res(s
)) Res(
f
Ma ) According to Proposition My
Res( (M(f Res(SM.) Res(s Mr ) Res(S
(M²)
(M))
Mi
14

---

Under review as a conference paper at ICLR 2021
E PROOF OF PROPOSITION 3
Proof. Since M1 E Rexm,, M2 E R and rank( ( M, M, )) = nI +12, we have rank(M), m1 and M2) f2. According Proposition SM. and JM, injective.
We build the system of linear equations (M, M2) m
Ax. where E Rutn, and A _1"2 E ( Then, rank(A)
0
-1-2 )) rank(( M, Ma (²)((0 mm
rank(( Mr M2) = ni + n2, which means Ax 0 has no non-zero solutions. Let x'
(a+ æ=]]].... æ[ni]) and x" (æln) a[1 2), æln1 n2]) such that For any a * 0,
1
0
x''
Ax = (Mr
M2)
= Mi Maæ" * 0.
n
x²
Therefore, for any x' R", x" E _ and x', x" * O, M2æ' * Maæ", hence M (2 # M2(P=2" for any o and Pa As result, Res(fMs) Res(fM,) = Ø.
F PROOF OF PROPOSITION
Proof. For Multi-head GAT, there are types of implementations aggregating each head, concatenation and average. Here, we only consider the average aggregation implementation.
K
h
Σ
W W (1-1)
vr
K
k-
JeN.
Wh (2!l-!1()
K
JEN
k=1
W (11 (e (((e1)))
JeN.
Σ jeN
W vecc(auu h ((-1TT
K
W
vec Sacaauhhl 1e ((-1)T)
JEN
where W E Raxd is the trainable matrix for the k-th head, and W concatenation of the trainable matrix in all heads;
|| W e kRdd is the
a h a 27 2
W h (1-1)
h (t-1)
2 (t- (1-1)]
a KT kkT 1 (1-1) w (wn((11) (1-1)
15

---

Under review as a conference paper at ICLR 2021
Let a' a2, akk and a' = "k+2 ,gg)) Then,
W hi -
2 h2
KT
KT
M
-
h!! 1
hm W
WlT (11) ब w (111)
w (1-1) a wht (1-1)
aKTW h2 (1-1) K ((-1))
à a'Tw'n ((-1)
a'Tw'' h (t-1)
a w2n (t-1)
w2T (1-1)
KT W ho (1-1) iT
WK WK luu (1-1)
W
W
2
W
à
W
h (t-1))
h (t-1)
KT
W
KTT
WK
diag(ā" IT à
KT
Whh Wh ((())))))))))))))()) + diag(ā" 2T
ā
KT
Wh (t-1)
[diag(ā "T arr
KT
diag
an 2r K [[W (t-)) (h(("))
Therefore, multi-head GAT an implementation of ExpandingConv as follows:
softmax (odtma((eayyRellU((ddaaa at à²T ā aKT)
Ouu
||diag(à' @"! _2 aKkT ][Wh (t-1) wh. WD)
h o W EjeN, vec(a (1 )
G COMPARISONS WITH MULTI-ACCREGATOR IMPLEMENTATIONS
ExpandingConv can also be considered as a kind multi-aggregaan scheme. In Equation 5 each row of M,, can be viewed as a weighted aggregator where the weight coefficients are learned from data. Proposition [ shows that obtain higher distinguishing strength by utilizing more aggrega- tors, the weight coefficients of newly added aggregators should be linearly independent all existing aggregators. The distinguishing strength weighted aggregators is incomparable with basic aggre- gators. However, since each row of My, is equivalent an independent aggregator, one simply modify the implementation freca [u, v) to obtain the variant whose distinguishing strength is strict stronger than basic aggregators follows:
ExpandingCony *g) (mm
SUM,
ExpandingCony 1m (oTo
SUM & MEAN.
Compared with lerveraging multiple basic aggregators in (Corso al. 2020) and (Dehmamy al. 2019), lerveraging weighted aggregator allows for variable numbers aggregators. Meanwhile, the weighted coefficients learned from data, which better capture relevant structural patterns.
16

---

Under review as a conference paper at ICLR 2021
H DETAILS OF EXPERIMENTAL SETUP
Datasets. Benchmark datasets for graph kernels provided by TU (Kersting et al. 2016) suffer from their small scales of data, making them sufficient to evaluate the performance of mod- els (Dwivedi et al. 2020). Our evaluations are conducted on graph property predictions datasets ogbg-ppa, oode-code, ogbg-molhiv in OGB (Weihua Hu 2020) and QM9 (Ramakrishnan et al.) 2014 Wu et al., 2018 Ruddigkeit et al. (0122) which are onge-scale graph datasets including graph classification and graph regression tasks. ogbg-ppa is extracted from the pootein-protetie association networks with large and densely connected graphs. ogbg-code is collection of Abstract Syntax Trees (AST') obtained from Python method definitions with large and sparse graphs. ogbg-molhiv molecular property prediction datasets with relative small graphs. QM9 consists 134K small ganic molecules with the task to predict 12 targets for each molecule. All data is obtained from pytorch-geometric library (Fey & Lenssen, 2019).
Table 5: Hyperparameter settings for OGB.
ngtg-motile
ePg-nelpeto
Expon-, BeyCs
Conter CorDC
EggCt), ExpCri
EapCCa
Coote't Cento
ExpC+)),EgCC
GontC: CoubC
E.ge%), ExpCCe
Conte" ComteC
betch size
12
128
128
64
layers
0.00K5
0.0001
0,0001
10
doder
0.8
0.7
0.7
0.7
065
0.6
0.5
0.5
0.5
8-
0.1
0.1
B.S.
DS
6.5
reedou:
SUM
SUM
MEAN
MEAN
MEAN
MEAN
MEAN
MEAN
Table 6: Hyperparameter settings for TU.
COLLAB
REDDIT BINARY
REDDIT MRDDIT-MULTI-I2K
ExpC-
CombC:
ExpC-a
CombC
ExpC-a
CombC
layers
3
3
3
hidden
180
256
0.001
0.001
0.001
0.001
0.001
0.001
step size
10
10
10
doeay
0.8
0.8
dropout
0.5
0.5
0.5
0.5
0.5
0.5
readout
The shared hyperparameter settings of ExpC*-1, ExpC-s, CombC and CombC all 12 targets of QM9: batch sizes = 64; Ir 0.0001; step size = 30; Ir decay = 0.85; readout = SUM. hidden 256 for ExpC*-1 and ExpC-s; hidden 512 for CombC* and CombC. Table gives the individual hyperparameter settings of each model on each target, including the number of layers.
Table 7: Number of layers for QM9.
<home
Elumo
(R²)
ZPVE
Un
H
G
C,
ExpC+-1.ExxC-e
5
4
4
5
Combt' CCome"' Commb"
5
4
5
4
4
5
4
4
4
4
I MORE EXPERIMENTAL RESULTS
We present more results of ablation studies on OGB and QM9, which demonstrate the effectiveness of ExpandingConv, CombConv and Re-SUM.
17

---

Under review as a conference paper at ICLR 2021
1/00
og02 P29
6.6
0.6
og0g 959
0.00
0.00
6.75
0.75
mm
0.m
0.00
0.00
0.00
Exp-33
Egc-3
Cambic
Centey
Caric
Carte
Cartec
330
molhiv
opby-moliv
1.00
6/96
6.00
6:00
TeC4
0:9
0.75
6.50
0.00
0.70
300
200
250
0.0
100
220
256
0.65
129
250
Oparn
Opec1
Opec1
oghggmnlpccb
spbppmopptbe
aghrpmmppphh
0.0
0.300
0.300
0.71
0.215
0.20
Fecch
Exede>
tpech
opbpccode
0..0
64
0.20
03
Faac1
PapC:
Fay
02
Ereer
Fivete
10
15
25
10
25
0.22
20
25
46
23
25
25
20
46
Figure 1: Learning curves ogbg-ppa, ogbg-molhiv, ogbg-molpcba and ogbg-code.
18

---

Under review as a conference paper at ICLR 2021
Q/9 -0
Q14--1
Q19-2
6.6
6660
0.55
0.044
0.50
0,0
CWV-3
640
0.09
0.00
0M9-5
E-c-33
Expo-3
Combic
Combi
CorbC
GU005
0.335
0.0000
0.330
0.040
300
6022
60005
11.
0.0200
200
230
500
0,0000
230
300
468
15.0
330
340
500
Ezoch
Opech
Opec1
QV9--
QM9-7
0.0005
CambiC-
2014
0.004
60000
taach
CH4-11
14
3.4
Expir-3
Expo-
122
Counti
Canic
0:30
6L15
0.10
2010
330
400
503
600
2.00
2000
300
420
500
620
300
200
200
403
200
600
Figure Effectiveness of Re-SUM QM9.
19

---

Under review as a conference paper at ICLR 2021
Q/4-- 0
Q14--1
Q19-2
646
666
Dxp033
0.55
CxpC35
0.044
Dxp
0.50
0,0
ExpC-1
640
0.00
0M9-5
Dxp032
DxpC32
Eap535
DpC4
Oyp4
G0005
0.335
0.0000
0.330
6.040
300-
6022
60005
11.5
0.0200
200
230
500
0,0000
230
300
468
15.0
330
340
500
Opech
Opec1
QV9--
QM9-7
Q019-8
0.0006
PapC/18
Eapco
Capco
2044
00004
Papc-1
Payic1
60000
CHP-11
14
Expti12
14
BxpC:32
12
12
Exp7-4
Exy
0:300
6115
0.10
200
330
403
503
600
200
200
300
920
500
620
300
200
200
903
200
600
Cyecc
Figure 3: Effectiveness of powerful aggregators QM9.
20


Reviews:
[{"review_id": "xlV3BjNp4go", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose two new layers for GNNs. CombConv and ExpandingConv are motivated by the insight that a GNN is only as expressive as the rank of the matrix that represents the coefficients of the aggregation function. To arrive at this statement, the authors formalize all GNNs as being composed of three steps: 1) generation of aggregation coefficients, 2) actual aggregation of the neighbourhood, and 3) feature extraction from the aggregation. Furthermore, it is shown that current approaches have very low distinguishing strength and that CombConv and ExpandingConv, by their construction, yield higher expressive power. \nThe effectiveness of different components of their layers (e.g. Re-SUM, applying a ReLU non-linearity before summing when features are computed form the aggregation) are investigated in an ablation study. Additionally, proposed layers are compared with current approaches on 4 data sets. \n\nThis paper constructs an interesting theoretical analysis of GNNs and finds the bottleneck of these networks to be in the coefficient matrix of the aggregation scheme. While I was not able to check all proofs, it seems like a solid mathematical analysis. What I find somewhat sobering is the experimental section. First, I am surprised that you only compare your method on four data sets and that you miss some reported by your comparison partners (such as IMDB, REDDIT, PROTEINS, etc.). I understand the Graph Kernel data sets are smaller, however, they’ve been used in comparable papers before. Second, while the title and the theoretical analysis promises much higher distinguishing strength, I am surprised that your performance gains are good but not outstanding. I wonder if you could construct a synthetic data set in which you can show how you break the expressive bottleneck in practice. Would it make sense to compute the rank of M for different networks (including yours ((it is not guaranteed it is $s$, right?)) and plot it as a function of predictive performance? \nIn Eq. 4 you start with summing over all neighbours of $v$ for each dimension of $W$, could you comment on how this relates to summing over the subset of the neighbours? I am not sure, I understand what you mean with the “subset of neighbours in each dimension”.\n\nMinor language hiccups:\n\n•\tP. 4 2nd sentence below equations: “is the function [that computes] node degrees” and same for the function “that computes” the hidden features?\n\n•\tP. 4 second to last paragraph: second sentence suiable -> suitable\n\n•\tFirst sentence in 3.3: Is that what you wanted to say?\n\n•\tSame page “We use […] aggregation coefficient matrices [as shown by?] Luan et al.”\n\n•\tPage 6: last sentence before “Comparisons with multi-head GAT“: “this can be explained [by the fact] that […]”.\n\n•\tPage 7: Paragraph “Effect of powerful aggregators”: Third sentence: “We config[ure]” \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "wyrzhkUc5Px", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\tThis paper explores the representation power of graph neural networks. Unlike recent work on choosing among simple aggregation functions or combinations thereof, the authors here recognize that these aggregators are the bottleneck in the representation power and generalize simple aggregator functions commonly used in literature to an aggregation coefficient matrix. The paper supports this construction theoretically and also proposes two aggregators that satisfy the rank-preservation requirement for more expressive (distinguishing) GNNs.\n\nStrengths:\n* The theoretical results are strong in proving the bottleneck of aggregators (Lemma 1) and clearly contextualize popular existing methods into this result.\n* Formulating aggregation in terms of a product with coefficients (indexed by a permutation) allows for framing existing methods and to connect the representation power with the rank of the matrix of coefficients.\n\nWeaknesses:\n* The study of the expressiveness of GNNs is a very popular topic right now and not enough context is provided about related work on this topic and other approaches, mainly focusing on GIN and GAT in the development and while a few other GNNs are considered in the experimental results, they are not discussed or explained enough.\n\nRecommendation:\nBy framing the aggregation in terms of coefficients, the paper provides interesting connections between the rank of these coefficient matrices and the distinguishing power of GNNs.  While analysis and explanation of experiments is extremely limited, the theoretical developments are interesting and novel enough to narrowly recommend publication. Meanwhile, I do think the paper should undergo a reorganization to add more details about related work in the study of expressiveness of GNNs and analyze experiments more thoroughly.\n\n\nOther comments and clarification needed:\n* It’s not quite clear what it means for aggregators to be incomparable (top of page 3), ie what does it mean for the relative strength to “not exist”? This point could be clarified with an additional sentence in this “Distinguishing strength” paragraph. \n* The text on page 4 before Proposition 2 states that “… different M corresponds to different local structures. Therefore, the aggregation results of different aggregators must be different. However, it is not satisfied by existing GNNs.” This statement should be explained more and supported. \n* The details of the ExpandingConv layer overwhelm the paper. The details fo equation 4 and related text can be moved to an Appendix and explained in the main text at a higher level. This would free up space to add context of the paper’s contribution and more properly address the experiments. In the end, the ExpandingConv formulation is a refinement on multi-head GAT.", "extra_scores": {}, "extra_text": {}}, {"review_id": "tgkKGCCTyR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper: The main objective of the paper is to improve the expressiveness of the GNN by exploring powerful aggregators. The requirements to build more powerful aggregators are analysed. It is closely related to finding strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to a special case of low-rank transformations.\n\nStrengths: The idea is promising. A new GNN formulation is proposed: the aggregation is represented as the multiplication of hidden feature matrix of neighbours and the aggregation coefficient matrix.\n\nWeaknesses: The strength mentioned above (multiplication of hidden features values and the aggregation) is also a weakness: I have an impression that already known results are presented in a much more complex way. The paper is not easy to follow in general ( e.g., the sentence \"The difference is that each dimension of hidden features is aggregated with an independent weighted aggregator which works like a comb\".)\n\nThe paper needs to be throughly read: use \\citep instead of \\cite where it is necessary. \n\nThe improvements reported in the experimental section seem to be not really significant.\n\nQuestions: Could you provide an intuition for the definition of the distinguishing strength? (Section 3.1). \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "sRrSDMkrnN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Post Rebuttal**\n\nI thank the authors for the extensive experiments and answers. Unfortunately, I still feel that the contribution is rather marginal. I keep my score unchanged.\n\n---\n\n**Summary of Contributions** \nThe paper points at the expressive bottleneck of GNNs as the weak distinguishing strength of learned aggregators. The authors then formulate the aggregator operation via a standalone matrix, and analyze the requirements for it to have a sufficient distinguishing strength. \nThen, based on the analysis, 2 aggregation schemes with enlarged strength are proposed. Also, the benefit of applying activation before aggregation is shown. \n\n**Strengths** \n- *Simplicity of analysis* - The paper presents a simple formulation to the aggregation operator via the matrix coefficients which provide an intuitive view of the requirements from the aggregator functions. \n- The paper presents a general formulation for GNNs under the suggested framework, and shows how other GNNs fall into this framework. \n-  *Thorough ablation study confirming theory* - the ablation study on s nicely shows the improvement in performance as s grows. \n- Achieving SOTA results on some benchmarks.\n\n**Weaknesses** \n- *Contribution and comparison to Corso et. al. (2020)* - Although the paper states results regarding the requirements from strong aggregators, as very similar result has already been introduced in Corso et. al.. In that case, I would have expected to see comparison in performance as both papers tackle the same problem. \n- *Comparison to GAT* - The paper shows how GAT can be formulated under the ExpandingConv formulation, raising the question, does it perform as well as the proposed methods?\n\n\n**Recommendation**\nThe paper posses an interesting and simple view of aggregators in GNNs however I have concerns regarding the significance of contribution. Therefore, I rate it as marginally bellow acceptance threshold. \n\n**Additional Comments**\n- Inaccuracies in GCN, GAT aggregation coefficients in p.4, missing the self coefficient. \n\n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "q6gXaHXeIy", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work presents a framework to categorize GNN aggregators based on their distinguishing strength. It connects the distinguishing strength to the rank of the aggregation coefficient matrices. Based on the findings, the authors present two GNN layers, ExpandingConv and CombConv, and evaluate them on some graph data sets.\n\nStrengths:\n- The paper is mostly well written.\n- The formalization of distinguishing strength for aggregators is interesting and novel.\n- The relation to the rank of coefficient matrices is a valuable insight and gives a new perspective to the effectivity of multi-head GAT.\n\nWeaknesses/Questions:\n- The paper lacks clarity in presentation / technical soundness, up to a point where I am not able to understand some details:\n\t- It is not clear what it means if f_aggr1 <= f_aggr2 \"does not exist\" (definition of incomparability)\n\t- In Lemma 1(ii), the formalization with \"or\" is confusing. It should probably be \"f_aggr1 ⊗ f_aggr2 >= f_aggr1 or f_aggr1 ⊗ f_aggr2 >= f_aggr2\".\n\t- I suggest to call the feature matrix for all nodes H, not h with specific indices, to avoid confusion. Currently, the index, or the lack of it, makes it either a matrix or a vector. Sometimes, h seems to be defined as the matrix containing features from all neighbors of u (as in the GCN definition). At other places, it seems to be just the vector of node u (Equation 3).\n\t- Page 5, rank(r) < min(rank(M), rank(h)) should probably be <=, otherwise rank(r) = rank(h) can't be achieved.\n\t- How can P be found? In order to construct it, a canonical order has to be defined and pi needs to be extracted from h. In fact, the permutation invariance does not seem to be relevant for the proposed approaches, since they both process all neighbors individually, have a sum in the end and do not impose an order by e.g. concatenation. Can the authors clarify, why this part is needed?\n\t- The set of results RES() is not clearly defined. The output of the aggregation is a matrix, not a set.\n\t- In general, Proposition 2 with the set formulations seems to be out of context and needs at least to be discussed.\n\n- The experiments are not sufficient and do not show significant improvements:\n\t- Some strong competitors are left out in comparions: E.g. GAT and multi-head GAT.\n\t- The approach is only validated on a small set of data sets. Since the authors already use OGB, I wonder why only three data sets have been chosen. To me this looks like those three were cherry-picked.\n\t- Even on the small number of data sets, the results are mediocre.\t\n\n- It is unclear why CombConv is proposed. It needs more discussion. In the case of CombConv, the aggregation coefficients have rank 1, similar to a lot of other existing GNN operators, isn't that right? This would mean that CombConv disgards the main argument of the work (having rank > 1) in trade for efficiency.\n\n\nAll in all, I recommend to reject the paper in its current state. While there seems to be some novel insight in this work, which might be of interest to the community, I think the paper needs to be improved in (1) clarity of presentation and (2) experiments. Issues with (1) can maybe be fixed within the rebuttal period. I am not sure about (2). It probably depends on the actual performance of the proposed operator.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores the representation power of GNNs, in particular, studying the bottleneck and improving expressiveness with new aggregators, which are analyzed theoretically. This issue was highlighted in previous works, but the merit of this paper is a constructive analysis. 

The reviewers were overall not enthusiastic and  raised a few concerns:
- Not enough context is provided about related work, in particular, the early work of Corso et. al. 
- Insufficiently convincing experiments

While the authors provided an elaborate rebuttal and extended the experimental section to address experiment concerns raised by most of the reviewers, the final evaluation was still lukewarm. Given that the conference has a very high bar and there have been many very good submissions on graphs, we find the paper not quite above the bar and hence have no choice but to recommend rejection with a heavy heart. The authors should be commended on their efforts and are encouraged to seek publication elsewhere. 


Decision: Reject