summaries: 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. 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.  	This 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.
abstractText: 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.
authors.name: EXPRESSIVE BOTTLENECKS
references.authors: Michael M Bronstein Joan Bruna Yann LeCun Arthur Szlam Pierre Vandergheynst
references.title: Geometric deep learning: going beyond euclidean data
references.venue: IEEE Signal Processing Magazine,
references.authors: Zhengdao Chen Soledad Villar Lei Chen Joan Bruna
references.title: On the equivalence between graph isomorphism testing and function approximation with gnns
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Gabriele Corso Luca Cavalleri Dominique Beaini Pietro Liò Petar
references.title: Veličković. Principal neighbourhood aggregation for graph nets
references.venue: arXiv preprint arXiv:2004.05718,
references.authors: Nima Dehmamy Albert-László Barabási Rose Yu
references.title: Understanding the representation power of graph neural networks in learning graph topology
references.venue: In Advances in Neural Information Processing Systems,
references.authors: David K Duvenaud Dougal Maclaurin Jorge Iparraguirre Rafael Bombarell Timothy Hirzel Alán Aspuru-Guzik Ryan P Adams
references.title: Convolutional networks on graphs for learning molecular fingerprints
references.venue: In Advances in neural information processing systems,
references.authors: Vijay Prakash Dwivedi Chaitanya K Joshi Thomas Laurent Yoshua Bengio Xavier Bresson
references.title: Benchmarking graph neural networks
references.venue: arXiv preprint arXiv:2003.00982,
references.authors: M. Fey J.G. Yuen F. Weichert
references.title: Hierarchical inter-message passing for learning on molecular graphs
references.venue: In ICML Graph Representation Learning and Beyond (GRL+) Workhop,
references.authors: Matthias Fey Jan E. Lenssen
references.title: Fast graph representation learning with PyTorch Geometric
references.venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,
references.authors: Justin Gilmer Samuel S Schoenholz Patrick F Riley Oriol Vinyals George E Dahl
references.title: Neural message passing for quantum chemistry
references.venue: In Proceedings of the 34th International Conference on Machine Learning-Volume
references.authors: Marco Gori Gabriele Monfardini Franco Scarselli
references.title: A new model for learning in graph domains
references.venue: In Proceedings
references.authors: Will Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Sergey Ioffe Christian Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: arXiv preprint arXiv:1502.03167,
references.authors: Sergey Ivanov Evgeny Burnaev
references.title: Anonymous walk embeddings
references.venue: In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning,
references.authors: Kristian Kersting Nils M. Kriege Christopher Morris Petra Mutzel Marion Neumann
references.title: Benchmark data sets for graph kernels, 2016
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: arXiv preprint arXiv:1609.02907,
references.authors: Soheil Kolouri Navid Naderializadeh Gustavo K Rohde Heiko Hoffmann
references.title: Wasserstein embedding for graph learning
references.venue: arXiv preprint arXiv:2006.09430,
references.authors: Guohao Li Chenxin Xiong Ali Thabet Bernard Ghanem
references.title: Deepergcn: All you need to train deeper gcns
references.venue: arXiv preprint arXiv:2006.07739,
references.authors: Pan Li Yanbang Wang Hongwei Wang Jure Leskovec
references.title: Distance encoding–design provably more powerful gnns for structural representation learning
references.venue: arXiv preprint arXiv:2009.00142,
references.authors: Yaw-Ling Lin Steven S Skiena
references.title: Algorithms for square roots of graphs
references.venue: SIAM Journal on Discrete Mathematics,
references.authors: Sitao Luan Mingde Zhao Xiao-Wen Chang Doina Precup
references.title: Break the ceiling: Stronger multiscale deep graph convolutional networks
references.venue: In Advances in neural information processing systems,
references.authors: Haggai Maron Heli Ben-Hamu Hadar Serviansky Yaron Lipman
references.title: Provably powerful graph networks
references.venue: arXiv preprint arXiv:1905.11136,
references.authors: Pushkar Mishra Aleksandra Piktus Gerard Goossen Fabrizio Silvestri
references.title: Node masking: Making graph neural networks generalize and scale better
references.venue: arXiv preprint arXiv:2001.07524,
references.authors: Christopher Morris Martin Ritzert Matthias Fey William L Hamilton Jan Eric Lenssen Gaurav Rattan Martin Grohe
references.title: Weisfeiler and leman go neural: Higher-order graph neural networks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Ryan L Murphy Balasubramaniam Srinivasan Vinayak Rao Bruno Ribeiro
references.title: Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs
references.authors: Ryan L Murphy Balasubramaniam Srinivasan Vinayak Rao Bruno Ribeiro
references.title: Relational pooling for graph representations
references.venue: arXiv preprint arXiv:1903.02541,
references.authors: Mathias Niepert Mohamed Ahmed Konstantin Kutzkov
references.title: Learning convolutional neural networks for graphs
references.venue: In International Conference on Machine Learning,
references.authors: Raghunathan Ramakrishnan Pavlo O Dral Matthias Rupp O Anatole Von Lilienfeld
references.title: Quantum chemistry structures and properties of 134 kilo molecules
references.venue: Scientific data,
references.authors: Yu Rong Wenbing Huang Tingyang Xu Junzhou Huang
references.title: Dropedge: Towards deep graph convolutional networks on node classification
references.venue: In International Conference on Learning Representations,
references.authors: Lars Ruddigkeit Ruud Van Deursen Lorenz C Blum Jean-Louis Reymond
references.title: Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17
references.venue: Journal of chemical information and modeling,
references.authors: Ryoma Sato
references.title: A survey on the expressive power of graph neural networks
references.venue: arXiv preprint arXiv:2003.04078,
references.authors: Franco Scarselli Marco Gori Ah Chung Tsoi Markus Hagenbuchner Gabriele Monfardini
references.title: The graph neural network model
references.venue: IEEE Transactions on Neural Networks,
references.authors: Gunther Schmidt
references.title: Relational mathematics, volume 132
references.authors: Clement Vignac Andreas Loukas Pascal Frossard
references.title: Building powerful and equivariant graph neural networks with message-passing
references.venue: arXiv preprint arXiv:2006.15107,
references.authors: Matthias Fey
references.title: Open graph benchmark: Datasets for machine learning on graphs
references.authors: B. Yu. Weisfeiler A.A. Leman
references.title: Reduction of a graph to a canonical form and an algebra arising during this reduction
references.authors: Zhenqin Wu Bharath Ramsundar Evan N Feinberg Joseph Gomes Caleb Geniesse Aneesh S Pappu Karl Leswing Vijay Pande
references.title: Moleculenet: a benchmark for molecular machine learning
references.venue: Chemical science,
references.authors: Zhang Xinyi Lihui Chen
references.title: Capsule graph neural network
references.venue: In International Conference on Learning Representations,
references.authors: Keyulu Xu Chengtao Li Yonglong Tian Tomohiro Sonobe Ken-ichi Kawarabayashi Stefanie Jegelka
references.title: Representation learning on graphs with jumping knowledge networks
references.venue: arXiv preprint arXiv:1806.03536,
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Pinar Yanardag SVN Vishwanathan
references.title: Deep graph kernels
references.venue: In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
references.authors: Zhitao Ying Jiaxuan You Christopher Morris Xiang Ren Will Hamilton Jure Leskovec
references.title: Hierarchical graph representation learning with differentiable pooling
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Muhan Zhang Zhicheng Cui Marion Neumann Yixin Chen
references.title: An end-to-end deep learning architecture for graph classification
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
sections.heading: 1 INTRODUCTION
sections.text: 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 et 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, 2020). It 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-lehman (WL) graph isomorphism test (Weisfeiler & Leman, 1968) to 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. Unfortunately, general GNNs are at most as powerful as 1-order WL test (Morris et al., 2019; Xu et al., 2019). There is also work trying to improve the expressiveness that are beyond 1-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 is the fundamental limitation. The expressiveness analysis measured by the WL test assumes that aggregators are injective, which is usually unreachable. Therefore, this motivates us to 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 provided a family of functions to which any permutation invariant function must belong. (Xu et al., 2019) extended it on multisets but only for countable space. (Corso et al., 2020) further extended it to uncountable space. (Murphy et al., 2018) and (Murphy et al., 2019) expressed a permutation invariant function by approximating an average over permutation-sensitive functions with tractability
  strategies. (Dehmamy et al., 2019) showed that a single propagation rule applied in general GNNs is 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 a 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: ExpandingConv 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 as a partial order, and theoretically show that the choice of aggregators can be bottlenecks of expressiveness. We also propose to 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 a theoretical point of view on building powerful aggregators and even injective aggregators.
  • We propose ExpandingConv and CombConv layers which achieve state-of-the-art performance on a variety of graph tasks. We also show that multi-head GAT is one of the ExpandingConv implementations, which brings a theoretical explanation for its effectiveness.
sections.heading: 2 PRELIMINARIES
sections.heading: 2.1 NOTATIONS
sections.text: For a graph GpV,Eq, we denote the set of edges, nodes and node feature vectors respectively by EG, VG and XG. N pvq represents the set of neighbors of v including itself, i.e., N pvq “ tu P VG|pu, vq P EGuY tvu. We use rns to denote the set t1, 2, ..., nu. tt...uu represents a multi-set, i.e., a set with possibly repeating elements. Πn represents the set of all permutations of the integers 1 to n. hπ , where π P Π|h|, is a reordering of the elements of a sequence h according to π. Given a matrix X P Raˆb, XT represents the transpose of X , and vecpXq P Rabˆ1 represents the column stack ofX .
sections.heading: 2.2 GRAPH NEURAL NETWORKS
sections.text: Most GNNs adopt the neighborhood aggregation scheme (Gilmer et al., 2017) to learn the node representations, which utilizes both node features and graph structures. In the k-th layer, the representation of node v
  hpkqv “ Updatephpk´1qv ,Aggregateptthpk´1qu |u P N pvquuqq. (1)
  Aggregators in GNNs. An aggregator is a permutation invariant function (Zaheer et al., 2017) with bounded size inputs. It satisfies: (i) size insensitive: an aggregator can take an arbitrary but finite size of inputs; (ii) permutation invariant: an aggregator is invariant to the permutation of input. There are a limited number of basic aggregators such as SUM, MEAN, NORMALIZED MEAN, MAX/MIN, STD, etc. Most proposed GNNs apply one of these aggregators. Sum-of-power mapping (Zaheer et al., 2017) and normalized moments (Corso et al., 2020) can also be used as aggregators and they allow for a variable number of aggregators.
sections.heading: 3 PROPOSED MODEL
sections.text: 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, we analyze the requirements for building powerful aggregators and even injective aggregators. Finally, we introduce two GNN layers based on our theoretical analysis.
sections.heading: 3.1 DISTINGUISHING STRENGTH OF AGGREGATORS
sections.text: To ensure generality, our analysis of aggregators is always considered in multisets and uncountable case, where the inputs are 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 aggregator faggr1 is stronger than faggr2, denoted by faggr1 ľ faggr2, if and only if for any two multisets x1 and x2 where the number of elements can be different, faggr2px1q ‰ faggr2px2q ñ faggr1px1q ‰ faggr1px2q. Meanwhile, if there exist x11 and x 1 2 such that faggr1px11q ‰ faggr1px12q but faggr2px11q “ faggr2px12q, faggr1 is strictly stronger than faggr2, denoted by faggr1 ą faggr2. If faggr1 ľ faggr2 ľ faggr1, we say these two aggregators have the same distinguishing strength, denoted by faggr1 “ faggr2. If there exist multisets x1 and x2 such that faggr1px1q ‰ faggr1px2q, faggr2px1q “ faggr2px2q, and there also exist x11 and x 1 2 such that faggr1px11q “ faggr1px12q, faggr2px11q ‰ faggr2px12q, we say faggr1 and faggr2 are incomparable.
  Distinguishing strength is a 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 as showed in (Corso et al., 2020).
  Equivariant aggregator. faggr : ttRduu Ñ Rd is an equivariant aggregator if and only if faggrpttT ¨ x1,T ¨ x2, ¨ ¨ ¨ ,T ¨ xnuuq “ T ¨ faggrpttx1,x2, ¨ ¨ ¨ ,xnuuq for any T P Rmˆd and ttxi P Rd|i P rnsuu. Widely used SUM and MEAN are equivariant aggregators but MAX/MIN is not. We denote faggr1 b faggr2 a new aggregator by combing faggr1 and faggr2 with faggr1 b faggr2pXq “ rfaggr1pXq||faggr2pXqs, where || denotes concatenation.
  Lemma 1. (i) For any continuous function g, we have g ˝ faggr ĺ faggr, and when g is injective, faggr “ g ˝ faggr; (ii) faggr1 b faggr2 ľ faggr1 and faggr1 b faggr2 ľ faggr2. If faggr1 and faggr2 are incomparable, faggr1 b faggr2 ą faggr1 and faggr1 b faggr2 ą faggr2; (iii) If faggr is an equivariant aggregator, then faggrpT ¨ x1,T ¨ x2, ¨ ¨ ¨ ,T ¨ xnq ĺ faggrpx1,x2, ¨ ¨ ¨ ,xnq for any T P Rmˆd and ttxi P Rd|i P rnsuu.
  We prove Lemma 1 in Appendix B. Lemma 1 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 gpSUMpT ¨ x1,T ¨ x2, ¨ ¨ ¨ ,T ¨ xnqq ĺ SUMpx1,x2, ¨ ¨ ¨ ,xnq and gpMEANpT ¨ x1,T ¨ x2, ¨ ¨ ¨ ,T ¨ xnqq ĺ MEANpx1,x2, ¨ ¨ ¨ ,xnq, where T P Rmˆd, and g can be any continuous function. Based on Lemma 1, 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 to a 2-layer MLP. Therefore, when considering in a continuous input features space, the distinguishing strength of GIN-0 is at most as powerful as the SUM aggregator. GCN uses a NORMALIZED MEAN (denoted by nMEAN) aggregator. Given a node v and its neighbors, nMEANpv, u1, ¨ ¨ ¨ , unq “ 1?|N pvq| ¨p hv? |N pvq| ` hu1? |N pu1q| `¨ ¨ ¨` hun? |N punq|´1
  q. nMEAN is also an equivariant aggregator, and the distinguishing strength of aggregation in GCN is at most as powerful as nMEAN. 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 on inputs before aggregation.
sections.heading: 3.2 BUILDING POWERFUL AGGREGATORS
sections.text: 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 a node v and its neighbors N pvq, our new formulation represents the
  GNN operation as follows: $
  ’ &
  ’ % mv “ flocalpvq /* aggregation coefficients generation */ r ptq v “mvπh̄pt´1qTvπ /* neighborhood aggregation */ h ptq v “ fNNprptqv q /* feature/structure extraction */.
  (2)
  Here, mv P R|N pvq| is the aggregation coefficients vector of node v. Note that mv should be the mapping of local structures such as node degrees, node or edge features of the k-hop neighbors assigned on node v to ensure the same encoding of isomorphic graphs. h̄pt´1qTvπ “ phpt´1qv ,hpt´1qu1 , ¨ ¨ ¨ ,h pt´1q u|N pvq|q
  T P R|N pvq|ˆd is the matrix representation of v’s neighbors according to a permutation π. fNN : Rd Ñ Rd 1 is a neural network that extracts task-relevant information from the aggregated representation rptqv , and is used to update hidden feature h ptq v of node v.
  According to Equation 2, the aggregation should be with high distinguishing strength to avoid indistinguishability among neighbors. Meanwhile, the extraction should be powerful enough to efficiently extract task-relevant structural patterns from the aggregated representation of neighbors. Based on these observations, we reformulate GCN, GIN0 and GAT with their corresponding threestage representations as follows:
  GCN :
  $
  ’ ’ &
  ’ ’ %
  mv “ 1?|N pvq| p 1? |N pvq| , 1? |N pu1q| , ¨ ¨ ¨ , 1?|N pu|Npvq|´1q| q r ptq v “mvπh̄pt´1qTvπ h ptq v “ σpWrptqv ` bq, GIN0 : $ ’ & ’ % mv “ 11ˆ|N pvq| r ptq v “mvπh̄pt´1qTvπ h ptq v “ MLPprptqv q,
  GAT :
  $
  ’ &
  ’ %
  m ptq v “ pattphpt´1qv ,hpt´1qv q, attphpt´1qv ,hpt´1qu1 q, ¨ ¨ ¨ , attph pt´1q v ,h pt´1q u|Npvq´1|qq r ptq v “mptqvπh̄pt´1qTvπ h ptq v “ σpWrptqv ` bq.
  Their default formulations are given in Appendix A. In the aggregation step, GCN’s mv is the mapping of neighbors’ degrees; GIN0’s mv is the mapping of node v’s degree which is equivalent to SUM aggregator; GAT’smv is the mapping of neighbors’ features. All of them are the mappings of local structures as given in Equation 2.
  In this three-stage representation, the aggregation is reformulated as the multiplication of the aggregation 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 invariance in this formulation. Let M P Rsˆn denote an aggregation coefficient matrix where s ě 1. Note that in GCN, GIN and GAT, s is restricted to be 1. hπ P Rnˆd is the matrix representation of n input elements according to π. The aggregation computation in the second step of Equation 2 is faggrpM ,hπq “ MPπhπ “ Mπhπ , where Pπ is the permutation matrix according to π. Pπhπ ensures the same output for all hπ , π P Π|h|. Mπ “ MPπ is the reordering of columns of M according to π. For any π1, π2 P Πn, faggrpM ,hπ1q “ faggrpM ,hπ2q, thus permutation invariance holds. Once M is decided, we obtain a unique aggregator denoted by fM . For any sequence of input elements h, fM phq “ faggrpM ,hπq, where π P Πn can be any ordering of neighbors. Next, we analyze the distinguishing strength of fM . Proposition 1. For any two matrices M P Rsˆn and M 1 P Rs1ˆn with s, s1 ď n, we have (i) f` M
  M 1
  ˘ ľ fM , where ` M M 1 ˘
  means stacking these two matrices; (ii) f` M M 1 ˘ ą fM if and only
  if rankp ` M M 1 ˘ q ą rankpMq; (iii) Any multiset of size n is distinguishable with fM if and only if rankpMq “ n.
  We prove Proposition 1 in Appendix C. Proposition 1 shows that the distinguishing strength of fM is decided by the rank of the correspondingM . Yet, the distinguishing strength analysis in Proposition 1 is only suitable for multisets aggregated with shared fM . Next, we extend the analysis for the case of different aggregators.
  Let RespfM q 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 fM1 and fM2 , RespfM1qXRespfM2q “ H. This is because to fully distinguish different local structures, we should ensure their aggregated
  representations are different. SinceM is restricted to be the mapping of local structures (such as khop 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 a detailed analysis of it.
  Proposition 2. For any M1,M2 P Rsˆn1 and M 11,M 12 P Rs 1ˆn2 , (i) Respf`M1
  M 11
  ˘q X
  Respf`M2 M 12 ˘q Ď RespfM1q X RespfM2q; (ii) If Respf`M1 M 11 ˘q X Respf`M2 M 12 ˘q Ă RespfM1q X RespfM2q, then rankp `M1 M2 M 11 M 1 2 ˘ q ą rankp ` M1 M2 ˘ q;
  We prove Proposition 2 in Appendix D. Proposition 2 shows the necessity of preserving the rank of aggregation coefficient matrix when considering the distinguishing strength among different aggregators. Next, we provide a sufficient condition for building desired multiple injective aggregators with the outputs having no intersections.
  Proposition 3. For any two aggregators fM1 and fM2 with M1 P Rsˆn1 and M2 P Rsˆn2 , if rankp ` M1 M2 ˘
  q “ n1 ` n2, then fM1 and fM2 are injective and RespfM1q X RespfM2q “ H.
  We prove Proposition 3 in Appendix E. Proposition 1, 2 and 3 provide a new perspective for building powerful aggregators and even injective aggregators. Compared with the distinguishing strength studies in (Xu et al., 2019) and (Corso et al., 2020), as well as existing strategies for building injective aggregators, e.g., sum-of-power mapping (Zaheer et al., 2017) and normalized moments (Corso et al., 2020), we reformulate the aggregation with aggregation coefficients matrix and show the relations of the distinguishing strength of aggregators and the rank of the corresponding aggregation coefficients matrices. Besides, the aggregation of this method is controlled by aggregation coefficients 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 to more sophisticated aggregators with the overall framework unchanged
  In the perspective of preserving the rank of hidden features among neighbors, r “ Mh indicates that rankprq ď minprankpMq, rankphqq. To preserve the rank of hidden features in aggregations such that rankprq “ rankphq, we need rankpMq ě rankphq. 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 ofM . General aggregators such as ones in GCN, GIN-0 and GAT have rankpMq “ 1. Thus, rankprq is always fixed to 1 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 a representation regularization step, which unifies different multisets of neighbors into the same representation style while holding permutation invariance. Then, the model can extract structural information on this regulated data with a shared trainable matrix as the third step in Equation 2. Based on this observation, we propose two novel GNN layers: ExpandingConv and CombConv.
sections.heading: 3.3 EXPANDINGCONV
sections.text: In this section, we first present ExpandingConv framework. Then we provide one of its implementations and analyze how ExpandingConv achieves more powerful aggregations. The ExpandingConv framework is
  #
  m ptq uv “ flocalpu, vq|uPN pvq h ptq v “ faggrpttvecpmptquvhpt´1qTu q|u P N pvquuq,
  where mptquv P Rsˆ1 with s ą 1 and flocalpu, vq is the mapping of local structures between nodes u and v. The implementation of flocalpu, vq is very flexible with the only restriction of ensuring the same encoding of isomorphic graphs. vecpmptquvhpt´1qTu q P Rsdˆ1 is the expanded representation of hidden features hpt´1qu P Rdˆ1. Then a GNN layer faggr learns structural information on this
  expanded representations. We introduce an implelentation as follows: #
  m ptq uv “ TanhpW rhpt´1qv ||hpt´1qu s ` bq h ptq v “ ř uPN pvq MLPpvecpm ptq uvh pt´1qT u qq.
  (3)
  In Equation 3, we implement flocalpu, vq as the function of hidden features of nodes u and v. There can be other implementations, and we leave them for future work. W P Rsˆ2d and b P Rsˆ1 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 in the computation ofmptquv to better preserve the rank of aggregation coefficient matrices. MLP denotes a 2-layer perceptron.
  Next, we represent Equation 3 with the corresponding three-stage representation as 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 withW 1 P Rdˆsd and b1 P Rdˆ1. hptqv “ ÿ
  uPN pvq ReLUpW 1vecpmptquvhpt´1qTu q ` b1q “
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  ř uPN pvq ReLUpW 1 r1,:svecpm ptq uvh pt´1qT u q ` b1r1sq ř
  uPN pvq ReLUpW 1 r2,:svecpm ptq uvh pt´1qT u q ` b1r2sq
  ... ř
  uPN pvq ReLUpW 1 rd,:svecpm ptq uvh pt´1qT u q ` b1rdsq
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚ “
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  ř uPN1pvqpW 1 r1,:svecpm ptq uvh pt´1qT u q ` b1r1sq ř
  uPN2pvqpW 1 r2,:svecpm ptq uvh pt´1qT u q ` b1r2sq
  ... ř
  uPNdpvqpW 1 rd,:svecpm ptq uvh pt´1qT u q ` b1rdsq
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚
  “
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  W 1r1,:s
  W 1r2,:s . . .
  W 1rd,:s
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  vecp ř uPN1pvqm ptq uvh pt´1qT u q vecp ř
  uPN2pvqm ptq uvh pt´1qT u q
  ...
  vecp ř uPNdpvqm ptq uvh pt´1qT u q
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚ `
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  |N1pvq| ¨ b1r1s |N2pvq| ¨ b1r2s
  ...
  |Ndpvq| ¨ b1rds
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚
  “
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  W 1r1,:s
  W 1r2,:s . . .
  W 1rd,:s
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  vecpM ptqv1π1 h̄ pt´1qT v1π1 q vecpM ptqv2π2 h̄ pt´1qT v2π2 q
  ...
  vecpM ptqvdπd h̄ pt´1qT vdπd q
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚ `
  ¨
  ˚ ˚ ˚ ˚ ˚ ˚ ˝
  |N1pvq| ¨ b1r1s |N2pvq| ¨ b1r2s
  ...
  |Ndpvq| ¨ b1rds
  ˛
  ‹ ‹ ‹ ‹ ‹ ‹ ‚ ,
  (4) where Nipvq Ď N pvq|i P rds are sampled subsets of neighbors in each di-
  mension. M ptqvi “ pm ptq u1v,m ptq u2v, ¨ ¨ ¨ ,m ptq u|Nipvq|v q P Rsˆ|Nipvq| and h̄pt´1qvi “ phpt´1qu1 ,h pt´1q u2 , ¨ ¨ ¨ ,h pt´1q u|Nipvq|
  q P Rdˆ|Nipvq| are aggregation coefficients matrix and hidden feature matrix corresponding to the subset of neighbors Nipvq Ď N pvq according to πi. We denote rhpt´1qv ||h̄pt´1qvi s “ ph pt´1q v ||hpt´1qu1 ,h pt´1q v ||hpt´1qu2 , ¨ ¨ ¨ ,h pt´1q v ||hpt´1qu|Nipvq|q P R 2dˆ|Nipvq|, then M ptq vi “ TanhpW rh pt´1q v ||h̄pt´1qvi s ` bq P Rsˆ|Nipvq|. According to Equation 4, we finally obtain the three-stage representation equivalent to Equation 3. $
  ’ ’ ’ ’ &
  ’ ’ ’ ’ %
  M ptq vi “ TanhpW rh pt´1q v ||h̄pt´1qvi s ` bq r̄ ptq vi “M ptq viπi h̄ pt´1qT viπi , i P rds h ptq v “ diagpW 1r1,:s,W 1r2,:s, ¨ ¨ ¨ ,W 1rd,:sqpvecpr̄ ptq v1 q, vecpr̄ ptq v2 q, ¨ ¨ ¨ , vecpr̄ ptq vd qqT
  `p|N1pvq| ¨ b1r1s, |N2pvq| ¨ b1r2s, ¨ ¨ ¨ , |Ndpvq| ¨ b1rdsqT .
  (5)
  According to the computation of r̄ptqvi , rankpr̄ ptq vi q ď minps, d, |Nipvq|q. By configuring a larger s,
  we have rankpr̄ptqvi q ą 1 with a high probability, which is different from general GNNs with a rank of 1. As analyzed in Section 3.2, this achieves more powerful aggregators as well as preserves the rank of hidden features among neighbors. The obtained r̄ptqvi after aggregation is the unified representations of neighbors. We then use the trainable matrix W 1 P Rsdˆd to extracts feature/structure information. Unlike the aggregation step, the dimensions reduction here (from sd to d) would not cause information loss. This can be explained by the fact that only task-relevant structural information needs to be preserved and passed to the next layer, and it can be embedded in lower dimensions.
  Comparisons with multi-head GAT. Proposition 4. Multi-head GAT is an implementation of ExpandingConv as follows:
  $
  ’ &
  ’ %
  αvu “ softmaxpLeakyReLUprdiagpã1T , ã2T , ¨ ¨ ¨ , ãKT q ||diagpã11T , ã12T , ¨ ¨ ¨ , ã1KT qsrWhpt´1qv ||Whpt´1qu sqq
  h ptq v “ σ
  ´
  1 KW
  ř jPNv vecpαvuh pt´1qT u q
  ¯
  ,
  (6)
  whereW “ ||Kk“1W k P Rkdˆd is the concatenation of the trainable matrix in all K heads.
  We prove Proposition 4 in Appendix F. Although multi-head GAT is based on attention mechanism, ExpandingConv provides a new perspective to explain its effectiveness. Applying multi-head attention mechanism helps to preserve the rank of hidden features as well as achieve more powerful aggregators. However, the usage of LeakyReLU may be harmful to preserving the rank of the aggregation coefficient matrix (Luan et 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 to the analysis in Section 3.1, Equation 3 applies MLP on vecpmptquvhpt´1qTu q before SUM to break the distinguishing strength limitation of SUM. It also produces other interesting results. By reformulating Equation 3 with its three-stage representation as Equation 5, each dimension of hidden features aggregates on a subset of neighbors independently, which corresponds to a kind of dimension-wise neighbor sampling mechanism. We call the modification 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 on 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 as unbiased data augmentation technique for training. Compared with dropedge and node masking, Re-SUM realizes a dimension-wise neighbor sampling, and it does not need to manually set the sampling ratio 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 modifying the network architecture. Our experimental results verified the effectiveness of the Re-SUM on a variety of graph tasks.
sections.heading: 3.4 COMBCONV
sections.text: The CombConv framework is #
  m ptq uv “ flocalpu, vq|uPN pvq h ptq v “ faggrpttvecpmptquv d hpt´1qu q|u P N pvquuq,
  where mptquv P Rdˆ1 and d denotes element-wise product. An implementation of CombConv is given as follows:
  # m ptq uv “ TanhpW rhpt´1qv ||hpt´1qu s ` bq
  h ptq v “ ř uPN pvq MLPpm ptq uv d hpt´1qu q,
  (7)
  where W P Rdˆ2d and b P Rdˆ1. Similar to ExpandingConv, CombConv also applies Re-SUM aggregation. The difference is that each dimension of hidden features is aggregated with an independent weighted aggregator. ExpandingConv with s “ 1 corresponds to a special case of CombConv where all dimensions share the same aggregator. Therefore, the distinguishing strength of CombConv is stronger than ExpandingConv with s “ 1. Meanwhile, CombConv does not expand the hidden features of nodes in aggregation. Hence, it requires fewer parameters.
sections.heading: 4 EXPERIMENTS
sections.text: In this section, we evaluate ExpandingConv and CombConv 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://github.com/qslim/epcb-gnns.
  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 et al., 2018) and report our results following the protocol described 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 (Ioffe & 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 aggregators andRe-SUM mechanism on OGB and QM9 as given in Table 1 and Table 2. Then, we compare the performance of ExpandingConv and CombConv with competitive baselines on all three datasets as given in Table 3 and Table 4 to show their improvements. ExpC-s denotes ExpandingConv with W P Rsˆ‹. We use ExpC* and CombC* to denote the ExpandingConv and CombConv without Re-SUM.
sections.heading: 4.1 ABLATION STUDIES
sections.text: Effect 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 to leverage large receptive fields. This is validated on both QM9 and OGB. We configure s “ 1, 4, 8, 16, 32 of ExpC-s for all 12 targets of QM9. As we apply a larger s, the model continuously achieves better performance on most targets. We randomly select s “ 1, 4 for ogbg-ppa, ogbgmolhiv and s “ 1, 5 for ogbg-code. The results show that applying larger s gains performance improvements, especially on ogbg-ppa which involves large graphs with dense connections.
  Effect of Re-SUM mechanism. In Table 1 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% improvements). On most targets of QM9, this mechanism also gains improvements. For small graphs with sparse connections such as ogbg-hiv and ogbg-molpcba, the improvements are not very significant.
sections.heading: 4.2 COMPARISONS WITH BASELINES
sections.text: 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 evaluations. For TU, we use 3 widely used datasets: COLLAB includes graphs with dense connections;
  REDDIT-BINARY (RDT-B) and REDDIT-MULTI-12K (RDT-M12) include large and sparse graphs with one center node having dense connections with other nodes. All results of baselines are taken from the original papers except for the results of GraphSAGE on TU, multi-head GAT on OGB and GIN0* on QM9 which were not reported by the original papers. We report the results of GraphSAGE provided by (Ying et al., 2018) and evaluate multi-head GAT and GIN0* by ourselves. To ensure a 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 t3, 4, 5u. For QM9, the number of heads is 8 and s P t4, 8, 16, 32u. GIN0* in QM9 denotes GIN0 without batch normalization. Compared with baselines, our models achieve the best performance on 7 out of all 12 targets of QM9, 3 out of all 4 graph-level prediction datasets of OGB and all 3 selected TU datasets. Our models get 1.9% improvements on COLLAB and 2.83% improvements on REDDIT-MULTI-12K compared with SOTA baselines. On ogbg-ppa, our models achieve 2.6% higher classification accuracies compared with SOTA baselines. On ogbg-code, they achieve 1.5% improvements. Multi-head GAT can also be considered as an implementation of ExpandingConv. However, its performance on graph-level predictions is not competitive. According to its three-stage representation, the usage of LeakyReLU 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 1-layer MLP may have a limited representation power to represent the desired extraction functions.
sections.heading: 5 CONCLUSION
sections.text: We show how basic aggregators used in general GNNs become expressive bottlenecks. To address this limitation, we develop theoretical foundations of building powerful aggregators. We also propose the Re-SUM mechanism which achieves dimension-wise sampling. To evaluate their effectiveness, we develop two novel GNN layers, and conduct extensive experiments on public graph benchmarks. The results are consistent with our analysis, and our proposed models achieve SOTA performance on a variety of graph-level prediction benchmarks.
sections.heading: A GCN, GAT AND GIN
sections.text: Here, we present implementations of GCN, GAT and GIN for the usage of our analysis.
  Graph Convolution Networks (GCN) (Kipf & Welling, 2016).
  Hptq “ σpD̂´ 12 ÂD̂´ 12Hpt´1qW ` bq (8)
  Graph Attention Networks (GAT) (Veličković et al., 2017).
  hptqv “ σ
  ¨
  ˝
  ÿ
  uPN pvq att
  ´
  hpt´1qv ,h pt´1q u
  ¯
  Whpt´1qu
  ˛
  ‚ (9)
  Graph Isomorphism Networks (GIN-0) (Xu et al., 2019).
  hptqv “ MLPp ÿ uPN pvq hpt´1qu q. (10)
sections.heading: B PROOF OF LEMMA 1
sections.text: Proof. (i) For any two multisets x1 and x2, if gpfaggrpx1qq ‰ gpfaggrpx2qq, then faggrpx1q ‰ faggrpx2q. Therefore, we have faggr ľ g ˝ faggr. If g is injective, then faggrpx1q ‰ faggrpx2q ñ gpfaggrpx1qq ‰ gpfaggrpx2qq. We have faggr ľ g ˝ faggr ľ faggr, therefore faggr “ g ˝ faggr. (ii) For any two multisets x1 and x2, faggr1px1q ‰ faggr1px2q ñ rfaggr1px1q||faggr2px1qs ‰ rfaggr1px2q||faggr2px2qs. Therefore, faggr1 b faggr2 ľ faggr1. If faggr1 and faggr2 are incomparable, there exist x3 and x4 such that faggr2px3q ‰ faggr2px4q but faggr1px3q “ faggr1px4q. Therefore, there exist x3 and x4 such that rfaggr1px3q||faggr2px3qs ‰ rfaggr1px4q||faggr2px4qs but faggr1px3q “ faggr1px4q. faggr1 b faggr2 ą faggr1. (iii) Since faggr is an equivariant aggregator, then faggrpT ¨ x1,T ¨ x2, ¨ ¨ ¨ ,T ¨ xnq “ T ¨ faggrpx1,x2, ¨ ¨ ¨ ,xnq ĺ faggrpx1,x2, ¨ ¨ ¨ ,xnq.
sections.heading: C PROOF OF PROPOSITION 1
sections.text: Proof. (i)
  f` M M 1
  ˘pxq “ ` M M 1 ˘ π xπ “
  ˆ
  mπxπ m1πxπ
  ˙ “ ˆ fM pxq fM 1pxq ˙ ,
  then for any x1 and x2, we have
  fM px1q ‰ fM px2q ñ f` M M 1 ˘px1q ‰ f` M M 1 ˘px2q,
  and therefore we conclude that f` M M 1 ˘ ľ fM .
  (ii) “f` M M 1
  ˘ ą fM ð rankp ` M M 1 ˘ q ą rankpMq”
  We prove the claim by contradiction. Assume that rankp ` M M 1 ˘ q ą rankpMq and f` M M 1 ˘ “ fM . f` M M 1 ˘ “ fM means that for any x1 and x2, mπx1π “ mπx2π ô ` M M 1 ˘ π x1π “ ` M M 1 ˘ π x2π , where π is the ordering of input elements. Let s “ x1π ´ x2π . For any i P rns, sris “ x1πris ´ x2πris P R. Then for any s P Rn, mπs “ 0 ô ` M M 1 ˘ π s “ 0. The system of linear equations mπx “ 0 and ` M M 1 ˘ π x “ 0 share the same solution space. Let RS denote the rank of this solution space, then rankpmπq ` RS “ rankp ` M M 1 ˘ π q ` RS “ n. Therefore, rankpmπq “ rankp ` M M 1 ˘ π q, then we have rankpMq “ rankp `
  M M 1
  ˘ q. Since we assumed that rankp ` M M 1 ˘ q ą rankpMq, we reach a contradiction.
  “f` M M 1
  ˘ ą fM ñ rankp ` M M 1 ˘ q ą rankpMq”
  We prove an equivalent proposition “rankp ` M M 1 ˘ q ď rankpMq ñ f` M M 1 ˘ ĺ fM”. Note that rankp `
  M M 1
  ˘
  q ě rankpMq and f` M M 1 ˘ ľ fM as given in Proposition 1(i). We only need to prove
  “rankp ` M M 1 ˘ q “ rankpMq ñ f` M M 1 ˘ “ fM”. rankp ` M M 1 ˘ q “ rankpMq means that any row in M 1 is linearly dependent to rows inM . Therefore, there existsL P Rs1ˆs so that `
  M M 1
  ˘ “ `
  I L
  ˘
  M . For any x1 and x2 with MPπx1π “ MPπx2π , ` I L ˘ MPπx1π “ ` I L ˘ MPπx2π , and therefore `
  M M 1
  ˘ Pπx1π “ ` M M 1 ˘
  Pπx2π , where π is the ordering of input elements. That is, for any x1 and x2, fM px1q “ fM px2q ñ f` M
  M 1 ˘px1q “ f` M M 1 ˘px2q, thus f` M M 1 ˘ ĺ fM . Finally, we have
  f` M M 1
  ˘ “ fM .
  (iii) “Any multiset of size n is distinguishable with fM ñ rankpMq “ n” Since rankpMq ď n, we prove an equivalent proposition “rankpMq ă nñ there exists at least two multisets which are indistinguishable”. Considering the system of linear equations y “Mx where x P Rn, if rankpMq ă n, then there exists y1 such that rankpMq “ rankpM ,y1q ă n. According to the Rouché–Capelli theorem, there are infinite solutions x1i such that y
  1 “ Mx11 “ Mx12 “ ¨ ¨ ¨ “ Mx18, Each x1i comes from a multiset with a particular order. Next, we need to prove that all these x1i come from more than one multiset. As a multiset with bounded size n constitutes at most n! different orders, the infinite number of x1i corresponds to y
  1 must come from more than one multisets, making these multisets indistinguishable.
  “Any multiset of size n is distinguishable with fM ð rankpMq “ n” Since rankpMq “ n and s “ n, for any x P Rn, y “Mx P Rn is unique. Correspondingly, for any Pπxπ ,MpPπxπq is unique.
sections.heading: D PROOF OF PROPOSITION 2
sections.text: Proof. (i) According to the proof of Proposition 1(i), f` M M 1
  ˘pxq “ ˆ fM pxq fM 1pxq ˙ . For any x1 and
  x2 with f`M1 M 11 ˘px1q “ f`M2 M 12 ˘px2q, fM1px1q “ fM2px2q holds. Meanwhile, f`M1 M 11 ˘px1q “ f`M2 M 12 ˘px2q P Respf`M1 M 11 ˘qXRespf`M2 M 12 ˘q, and fM1px1q “ fM2px2q P RespfM1qXRespfM2q. Therefore, for any e P Respf`M1 M 11 ˘q X Respf`M2 M 12 ˘q, we have e P RespfM1q X RespfM2q. That is Respf`M1 M 11 ˘q X Respf`M2 M 12 ˘q Ď RespfM1q X RespfM2q.
  (ii) We prove an equivalent proposition “Respf`M1 M 11 ˘qXRespf`M2 M 12 ˘q “ RespfM1qXRespfM2q ð rankp `M1 M2 M 11 M 1 2 ˘ q “ rankp ` M1 M2 ˘ q”. rankp `M1 M2 M 11 M 1 2 ˘ q “ rankp ` M1 M2 ˘ q means that any row in `
  M 11 M 1 2
  ˘ is linearly dependent to ` M1 M2 ˘ . Therefore, there existsL P Rs1ˆs so that `M1 M2 M 11 M 1 2 ˘ “ `
  I L
  ˘` M1 M2 ˘ . Correspondingly, `M1 M 11 ˘ “ ` I L ˘ M1 and `M2 M 12 ˘ “ ` I L ˘ M2. For any x1 and x2 with M1Pπx1π “ M2Pπx2π , ` I L ˘ M1Pπx1π “ ` I L ˘ M2Pπx2π , and therefore `M1 M 11 ˘
  Pπx1π “ `M2 M 12 ˘
  Pπx2π , where π is the ordering of input elements. Thus for any x1 and x2, fM1px1q “ fM2px2q P RespfM1qXRespfM2q ñ f`M1
  M 11 ˘px1q “ f`M2 M 12 ˘px2q P Respf`M1 M 11 ˘qXRespf`M2 M 12 ˘q.
  Hence, RespfM1q X RespfM2q Ď Respf`M1 M 11 ˘q X Respf`M2 M 12 ˘q. According to Proposition 2(i), RespfM1q X RespfM2q “ Respf`M1 M 11 ˘q X Respf`M2 M 12 ˘q.
sections.heading: E PROOF OF PROPOSITION 3
sections.text: Proof. SinceM1 P Rsˆn1 ,M2 P Rsˆn2 and rankp ` M1 M2 ˘ q “ n1`n2, we have rankpM1q “ n1 and rankpM2q “ n2. According to Proposition 1, fM1 and fM2 are injective. We build the system of linear equations y “ Ax, where x P Rn1`n2 , and A “ `
  M1 M2 ˘` In1 0 0 ´In2 ˘ P Rsˆpn1`n2q. Then, rankpAq “ rankp ` M1 M2 ˘` In1 0 0 ´In2 ˘ q “ rankp ` M1 M2 ˘
  q “ n1 ` n2, which means Ax “ 0 has no non-zero solutions. Let x1 “ pxr1s,xr2s, ¨ ¨ ¨ ,xrn1sq and x2 “ pxrn1 ` 1s,xrn1 ` 2s, ¨ ¨ ¨ ,xrn1 ` n2sq such that x “ ` x1
  x2
  ˘
  . For any x ‰ 0,
  Ax “ pM1 M2q ˆ In1 0 0 ´In2 ˙ˆ x1 x2 ˙ “M1x1 ´M2x2 ‰ 0.
  Therefore, for any x1 P Rn1 , x2 P Rn2 and x1,x2 ‰ 0, M1x1 ‰ M2x2, hence M1pPπx1πq ‰ M2pPπx2πq for any Pπx1π and Pπx2π . As a result, RespfM1q X RespfM2q “ H.
sections.heading: F PROOF OF PROPOSITION 4
sections.text: Proof. For Multi-head GAT, there are two types of implementations on aggregating each head, concatenation and average. Here, we only consider the average aggregation implementation.
  hptqv “ σ ˜ 1
  K
  K ÿ
  k“1
  ÿ
  jPNv
  αkvuW khpt´1qu
  ¸
  “ σ ˜ 1
  K
  ÿ
  jPNv
  K ÿ k“1 W kpαkvuhpt´1qu q
  ¸
  “ σ ˜ 1
  K
  ÿ
  jPNv
  p||Kk“1W kqp||Kk“1αkvuhpt´1qu q ¸
  “ σ ˜ 1
  K
  ÿ
  jPNv
  W vecpαvuhpt´1qTu q ¸
  “ σ ˜ 1
  K W
  ÿ
  jPNv
  vecpαvuhpt´1qTu q ¸ ,
  where W k P Rdˆd is the trainable matrix for the k-th head, and W “ ||Kk“1W k P Rkdˆd is the concatenation of the trainable matrix in all K heads;
  αvu “softmaxpLeakyReLU
  ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  a1T rW 1hpt´1qv ||W 1hpt´1qu s a2T rW 2hpt´1qv ||W 2hpt´1qu s
  ... aKT rW 1hpt´1qv ||WKhpt´1qu s
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  q.
  Let ã‹ “ pa‹1,a‹2, ¨ ¨ ¨ ,a‹Kq and ã1‹ “ pa‹K`1,a‹K`2, ¨ ¨ ¨ ,a‹2Kq. Then, ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  a1T rW 1hpt´1qv ||W 1hpt´1qu s a2T rW 2hpt´1qv ||W 2hpt´1qu s
  ... aKT rW 1hpt´1qv ||WKhpt´1qu s
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  “
  ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  rã1||ã11sT rW 1hpt´1qv ||W 1hpt´1qu s rã2||ã12sT rW 2hpt´1qv ||W 2hpt´1qu s
  ... rãK ||ã1KsT rW 1hpt´1qv ||WKhpt´1qu s
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  “
  ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  ã1TW 1h pt´1q v ` ã11TW 1hpt´1qu ã2TW 2h pt´1q v ` ã12TW 2hpt´1qu
  ... ãKTWKh pt´1q v ` ã1KTWKhpt´1qu
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  “
  ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  ã1TW 1h pt´1q v ã2TW 2h pt´1q v
  ... ãKTWKh pt´1q v
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  `
  ¨
  ˚
  ˚
  ˚
  ˚
  ˝
  ã11TW 1h pt´1q u ã12TW 2h pt´1q u
  ... ã1KTWKh pt´1q u
  ˛
  ‹
  ‹
  ‹
  ‹
  ‚
  “
  ¨
  ˚
  ˚
  ˚
  ˝
  ã1T
  ã2T
  . . . ãKT
  ˛
  ‹
  ‹
  ‹
  ‚
  ¨
  ˚
  ˚
  ˝
  W 1 W 2
  ... WK
  ˛
  ‹
  ‹
  ‚
  hpt´1qv `
  ¨
  ˚
  ˚
  ˚
  ˝
  ã11T
  ã12T
  . . . ã1KT
  ˛
  ‹
  ‹
  ‹
  ‚
  ¨
  ˚
  ˚
  ˝
  W 1 W 2
  ... WK
  ˛
  ‹
  ‹
  ‚
  hpt´1qu
  “ diagpã1T , ã2T , ¨ ¨ ¨ , ãKT qWhpt´1qv ` diagpã11T , ã12T , ¨ ¨ ¨ , ã1KT qWhpt´1qu “ rdiagpã1T , ã2T , ¨ ¨ ¨ , ãKT q||diagpã11T , ã12T , ¨ ¨ ¨ , ã1KT qsrWhpt´1qv ||Whpt´1qu s.
  Therefore, multi-head GAT is an implementation of ExpandingConv as follows: $
  ’ &
  ’ %
  αvu “ softmaxpLeakyReLUprdiagpã1T , ã2T , ¨ ¨ ¨ , ãKT q ||diagpã11T , ã12T , ¨ ¨ ¨ , ã1KT qsrWhpt´1qv ||Whpt´1qu sqq
  h ptq v “ σ
  ´
  1 KW
  ř jPNv vecpαvuh pt´1qT u q
  ¯
  .
sections.heading: G COMPARISONS WITH MULTI-AGGREGATOR IMPLEMENTATIONS
sections.text: ExpandingConv can also be considered as a kind of multi-aggregator scheme. In Equation 5, each row ofMvi can be viewed as a weighted aggregator where the weight coefficients are learned from data. Proposition 1 shows that to obtain higher distinguishing strength by utilizing more aggregators, the weight coefficients of newly added aggregators should be linearly independent to all existing aggregators. The distinguishing strength of weighted aggregators is incomparable with basic aggregators. However, since each row ofMvi is equivalent to an independent aggregator, one can simply modify the implementation of flocalpu, vq to obtain the variant whose distinguishing strength is strict stronger than basic aggregators as follows:
  ExpandingConv| m 1ptq uv “rmptquv ||1s ą SUM, ExpandingConv| m 1ptq uv “rmptquv ||1|| 1|Npvq| s ą SUMbMEAN.
  Compared with lerveraging multiple basic aggregators in (Corso et al., 2020) and (Dehmamy et al., 2019), lerveraging weighted aggregator allows for variable numbers of aggregators. Meanwhile, the weighted coefficients are learned from data, which can better capture relevant structural patterns.
sections.heading: H DETAILS OF EXPERIMENTAL SETUP
sections.text: Datasets. Benchmark datasets for graph kernels provided by TU (Kersting et al., 2016) suffer from their small scales of data, making them not sufficient to evaluate the performance of models (Dwivedi et al., 2020). Our evaluations are conducted on graph property predictions datasets ogbg-ppa, ogbg-code, ogbg-molhiv in OGB (Weihua Hu, 2020) and QM9 (Ramakrishnan et al., 2014; Wu et al., 2018; Ruddigkeit et al., 2012) which are large-scale graph datasets including graph classification and graph regression tasks. ogbg-ppa is extracted from the protein-protein association networks with large and densely connected graphs. ogbg-code is a collection of Abstract Syntax Trees (ASTs) obtained from Python method definitions with large and sparse graphs. ogbg-molhiv is molecular property prediction datasets with relative small graphs. QM9 consists 134K small organic molecules with the task to predict 12 targets for each molecule. All data is obtained from pytorch-geometric library (Fey & Lenssen, 2019).
  The shared hyperparameter settings of ExpC*-1, ExpC-s, CombC* and CombC on all 12 targets of QM9: batch sizes = 64; lr = 0.0001; step size = 30; lr decay = 0.85; readout = SUM. hidden = 256 for ExpC*-1 and ExpC-s; hidden = 512 for CombC* and CombC. Table 7 gives the individual hyperparameter settings of each model on each target, including the number of layers.
sections.heading: I MORE EXPERIMENTAL RESULTS
sections.text: We present more results of ablation studies on OGB and QM9, which demonstrate the effectiveness of ExpandingConv, CombConv and Re-SUM.