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.

summaries: 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.

summaries: 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:
Michael M Bronstein
Joan Bruna
Yann LeCun
Arthur Szlam
Pierre Vandergheynst

title: Geometric deep learning: going beyond euclidean data

venue: IEEE Signal Processing Magazine,

authors:
Zhengdao Chen
Soledad Villar
Lei Chen
Joan Bruna

title: On the equivalence between graph isomorphism testing and function approximation with gnns

venue: In Advances in Neural Information Processing Systems,

authors:
Gabriele Corso
Luca Cavalleri
Dominique Beaini
Pietro Liò
Petar

title: Veličković. Principal neighbourhood aggregation for graph nets

venue: arXiv preprint arXiv:2004.05718,

authors:
Nima Dehmamy
Albert-László Barabási
Rose Yu

title: Understanding the representation power of graph neural networks in learning graph topology

authors:
David K Duvenaud
Dougal Maclaurin
Jorge Iparraguirre
Rafael Bombarell
Timothy Hirzel
Alán Aspuru-Guzik
Ryan P Adams

title: Convolutional networks on graphs for learning molecular fingerprints

authors:
Vijay Prakash Dwivedi
Chaitanya K Joshi
Thomas Laurent
Yoshua Bengio
Xavier Bresson

title: Benchmarking graph neural networks

venue: arXiv preprint arXiv:2003.00982,

authors:
M. Fey
J.G. Yuen
F. Weichert

title: Hierarchical inter-message passing for learning on molecular graphs

venue: In ICML Graph Representation Learning and Beyond (GRL+) Workhop,

authors:
Matthias Fey
Jan E. Lenssen

title: Fast graph representation learning with PyTorch Geometric

venue: In ICLR Workshop on Representation Learning on Graphs and Manifolds,

authors:
Justin Gilmer
Samuel S Schoenholz
Patrick F Riley
Oriol Vinyals
George E Dahl

title: Neural message passing for quantum chemistry

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Marco Gori
Gabriele Monfardini
Franco Scarselli

title: A new model for learning in graph domains

venue: In Proceedings

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: arXiv preprint arXiv:1502.03167,

authors:
Sergey Ivanov
Evgeny Burnaev

title: Anonymous walk embeddings

venue: In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning,

authors:
Kristian Kersting
Nils M. Kriege
Christopher Morris
Petra Mutzel
Marion Neumann

title: Benchmark data sets for graph kernels, 2016

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

venue: arXiv preprint arXiv:1609.02907,

authors:
Soheil Kolouri
Navid Naderializadeh
Gustavo K Rohde
Heiko Hoffmann

title: Wasserstein embedding for graph learning

venue: arXiv preprint arXiv:2006.09430,

authors:
Guohao Li
Chenxin Xiong
Ali Thabet
Bernard Ghanem

title: Deepergcn: All you need to train deeper gcns

venue: arXiv preprint arXiv:2006.07739,

authors:
Pan Li
Yanbang Wang
Hongwei Wang
Jure Leskovec

title: Distance encoding–design provably more powerful gnns for structural representation learning

venue: arXiv preprint arXiv:2009.00142,

authors:
Yaw-Ling Lin
Steven S Skiena

title: Algorithms for square roots of graphs

venue: SIAM Journal on Discrete Mathematics,

authors:
Sitao Luan
Mingde Zhao
Xiao-Wen Chang
Doina Precup

title: Break the ceiling: Stronger multiscale deep graph convolutional networks

authors:
Haggai Maron
Heli Ben-Hamu
Hadar Serviansky
Yaron Lipman

title: Provably powerful graph networks

venue: arXiv preprint arXiv:1905.11136,

authors:
Pushkar Mishra
Aleksandra Piktus
Gerard Goossen
Fabrizio Silvestri

title: Node masking: Making graph neural networks generalize and scale better

venue: arXiv preprint arXiv:2001.07524,

authors:
Christopher Morris
Martin Ritzert
Matthias Fey
William L Hamilton
Jan Eric Lenssen
Gaurav Rattan
Martin Grohe

title: Weisfeiler and leman go neural: Higher-order graph neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Ryan L Murphy
Balasubramaniam Srinivasan
Vinayak Rao
Bruno Ribeiro

title: Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs

title: Relational pooling for graph representations

venue: arXiv preprint arXiv:1903.02541,

authors:
Mathias Niepert
Mohamed Ahmed
Konstantin Kutzkov

title: Learning convolutional neural networks for graphs

venue: In International Conference on Machine Learning,

authors:
Raghunathan Ramakrishnan
Pavlo O Dral
Matthias Rupp
O Anatole Von Lilienfeld

title: Quantum chemistry structures and properties of 134 kilo molecules

venue: Scientific data,

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: Dropedge: Towards deep graph convolutional networks on node classification

venue: In International Conference on Learning Representations,

authors:
Lars Ruddigkeit
Ruud Van Deursen
Lorenz C Blum
Jean-Louis Reymond

title: Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17

venue: Journal of chemical information and modeling,

title: A survey on the expressive power of graph neural networks

venue: arXiv preprint arXiv:2003.04078,

authors:
Franco Scarselli
Marco Gori
Ah Chung Tsoi
Markus Hagenbuchner
Gabriele Monfardini

title: The graph neural network model

venue: IEEE Transactions on Neural Networks,

title: Relational mathematics, volume 132

authors:
Clement Vignac
Andreas Loukas
Pascal Frossard

title: Building powerful and equivariant graph neural networks with message-passing

venue: arXiv preprint arXiv:2006.15107,

title: Open graph benchmark: Datasets for machine learning on graphs

authors:
B. Yu. Weisfeiler
A.A. Leman

title: Reduction of a graph to a canonical form and an algebra arising during this reduction

authors:
Zhenqin Wu
Bharath Ramsundar
Evan N Feinberg
Joseph Gomes
Caleb Geniesse
Aneesh S Pappu
Karl Leswing
Vijay Pande

title: Moleculenet: a benchmark for molecular machine learning

venue: Chemical science,

authors:
Zhang Xinyi
Lihui Chen

title: Capsule graph neural network

authors:
Keyulu Xu
Chengtao Li
Yonglong Tian
Tomohiro Sonobe
Ken-ichi Kawarabayashi
Stefanie Jegelka

title: Representation learning on graphs with jumping knowledge networks

venue: arXiv preprint arXiv:1806.03536,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

authors:
Pinar Yanardag
SVN Vishwanathan

title: Deep graph kernels

venue: In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Zhitao Ying
Jiaxuan You
Christopher Morris
Xiang Ren
Will Hamilton
Jure Leskovec

title: Hierarchical graph representation learning with differentiable pooling

authors:
Muhan Zhang
Zhicheng Cui
Marion Neumann
Yixin Chen

title: An end-to-end deep learning architecture for graph classification

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

heading: 1 INTRODUCTION

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.

heading: 2 PRELIMINARIES

heading: 2.1 NOTATIONS

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 .

heading: 2.2 GRAPH NEURAL NETWORKS

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.

heading: 3 PROPOSED MODEL

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.

heading: 3.1 DISTINGUISHING STRENGTH OF AGGREGATORS

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.

heading: 3.2 BUILDING POWERFUL AGGREGATORS

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.

heading: 3.3 EXPANDINGCONV

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.

heading: 3.4 COMBCONV

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.

heading: 4 EXPERIMENTS

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.

heading: 4.1 ABLATION STUDIES

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.

heading: 4.2 COMPARISONS WITH BASELINES

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.

heading: 5 CONCLUSION

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.

heading: A GCN, GAT AND GIN

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)

heading: B PROOF OF LEMMA 1

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.

heading: C PROOF OF PROPOSITION 1

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.

heading: D PROOF OF PROPOSITION 2

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.

heading: E PROOF OF PROPOSITION 3

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.

heading: F PROOF OF PROPOSITION 4

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
¯
.

heading: G COMPARISONS WITH MULTI-AGGREGATOR IMPLEMENTATIONS

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.

heading: H DETAILS OF EXPERIMENTAL SETUP

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.

heading: I MORE EXPERIMENTAL RESULTS

text: We present more results of ablation studies on OGB and QM9, which demonstrate the effectiveness of ExpandingConv, CombConv and Re-SUM.


summaries: The paper presents a disentanglement metric to measure the intrinsic properties of a generative model with respect to the factor of variation in the dataset. Toward this, the paper first assumes disentangled factors reside in different manifolds. These different manifolds are the sub-manifolds of some manifold M for a given disentangled generative model. The paper considers the fact that in an entangled model the sub-manifolds are not homeomorphic and thus similarity across submanifolds can be measured to evaluate a model’s disentanglement. As such, disentanglement is related to the topological similarity.  For measuring topological similarity, the paper then introduces Wasserstein Relative Living Times. The proposed metric is used to evaluate standard disentanglement methods and datasets demonstrating the importance.

summaries: Introduces unsupervised disentangling metric that measures homeomorphic similarity between submanifolds conditioned on a given factor, and homeomorphic dissimilarity on submanifolds conditioned on different factors. The paper also includes a supervised variant which can directly assess topological similarity of submanifolds with label-spaces. The paper also introduces a novel variation of RLTs that  employs wasserstein distance instead of euclidean distance.

summaries: The paper proposes a novel metric for evaluating disentanglement by taking a manifold-topological perspective on the representations learnt. The key insight is that for a disentangled representation, when we fix a certain factor of variation at different values the topology of the conditional sub-manifolds should be similar. Using this insight the paper proposes a metric for disentangling which does not require annotations of the factors of variation and is more general than previous such tests.

abstractText: Learning disentangled representations is regarded as a fundamental task for improving the generalization, robustness, and interpretability of generative models. However, measuring disentanglement has been challenging and inconsistent, often dependent on an ad-hoc external model or specific to a certain dataset. To address this, we present a method for quantifying disentanglement that only uses the generative model, by measuring the topological similarity of conditional submanifolds in the learned representation. This method showcases both unsupervised and supervised variants. To illustrate the effectiveness and applicability of our method, we empirically evaluate several state-of-the-art models across multiple datasets. We find that our method ranks models similarly to existing methods. We make our code publicly available at https://github.com/stanfordmlgroup/disentanglement.

authors:
A. Adcock
E. Carlsson
G. Carlsson

title: The ring of algebraic functions on persistence bar codes. Homology

venue: Homotopy and Applications,

authors:
M. Agueh
G. Carlier

title: Barycenters in the wasserstein space

venue: SIAM Journal on Mathematical Analysis,

authors:
A. Alemi
I. Fischer
J. Dillon
K. Murphy

title: Deep variational information bottleneck

venue: In ICLR,

authors:
Y. Bengio
A. Courville
P. Vincent

title: Representation learning: A review and new perspectives

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
D. Berthelot
T. Schumm
L. Metz

title: Began: boundary equilibrium generative adversarial networks

venue: arXiv preprint arXiv:1703.10717,

title: Statistical topological data analysis using persistence landscapes

venue: The Journal of Machine Learning Research,

authors:
C.P. Burgess
I. Higgins
A. Pal
L. Matthey
N. Watters
G. Desjardins
A. Lerchner

title: Understanding disentangling in beta-vae

venue: arXiv preprint arXiv:1804.03599,

title: Persistent homology and applied homotopy theory

venue: Handbook of Homotopy Theory,

title: Algorithms for manifold learning

venue: Univ. of California at San Diego Tech. Rep,

authors:
N. Chen
A. Klushyn
R. Kurle
X. Jiang
J. Bayer
P. van der Smagt

title: Metrics for deep generative models. PMLR, 2018a

authors:
T.Q. Chen
X. Li
R.B. Grosse
D.K. Duvenaud

title: Isolating sources of disentanglement in variational autoencoders

venue: In Advances in Neural Information Processing Systems,

authors:
X. Chen
Y. Duan
R. Houthooft
J. Schulman
I. Sutskever
P. Abbeel

title: Infogan: Interpretable representation learning by information maximizing generative adversarial nets

venue: In Advances in neural information processing systems,

authors:
L. Chizat
G. Peyré
B. Schmitzer
F.-X. Vialard

title: Scaling algorithms for unbalanced optimal transport problems

venue: Mathematics of Computation,

title: Co-clustering documents and words using bipartite spectral graph partitioning

venue: In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining,

authors:
P. Dognin
I. Melnyk
Y. Mroueh
J. Ross
C.D. Santos
T. Sercu

title: Wasserstein barycenter model ensembling

authors:
S. Duan
L. Matthey
A. Saraiva
N. Watters
C.P. Burgess
A. Lerchner
I. Higgins

title: Unsupervised model selection for variational disentangled representation learning

authors:
C. Eastwood
C.K. Williams

title: A framework for the quantitative evaluation of disentangled representations

title: Challenging common assumptions in the unsupervised learning of disentangled representations

authors:
C. Frogner
C. Zhang
H. Mobahi
M. Araya
T.A. Poggio

title: Learning with a wasserstein loss

title: Barcodes: the persistent topology of data

venue: Bulletin of the American Mathematical Society,

authors:
X. Glorot
A. Bordes
Y. Bengio

title: Domain adaptation for large-scale sentiment classification: A deep learning approach

authors:
W. Grathwohl
A. Wilson

title: Disentangling space and time in video with hierarchical variational auto-encoders

venue: arXiv preprint arXiv:1612.04440,

authors:
I. Gulrajani
F. Ahmed
M. Arjovsky
V. Dumoulin
A.C. Courville

title: Improved training of wasserstein gans

title: A construction for computer visualization of certain complex curves

venue: Notices of the Amer. Math. Soc,

title: Algebraic topology

authors:
I. Higgins
L. Matthey
A. Pal
C. Burgess
X. Glorot
M. Botvinick
S. Mohamed
A. Lerchner

title: beta-vae: Learning basic visual concepts with a constrained variational framework

authors:
I. Higgins
D. Amos
D. Pfau
S. Racaniere
L. Matthey
D. Rezende
A. Lerchner

title: Towards a definition of disentangled representations

venue: arXiv preprint arXiv:1812.02230,

authors:
D. Horak
S. Yu
G. Salimi-Khorshidi

title: Topology distance: A topology-based approach for evaluating generative adversarial networks

venue: arXiv preprint arXiv:2002.12054,

authors:
T. Karaletsos
S. Belongie
G. Rätsch

title: Bayesian representation learning with oracle constraints

venue: ICLR,

authors:
T. Karras
T. Aila
S. Laine
J. Lehtinen

title: Progressive growing of gans for improved quality, stability, and variation

authors:
T. Karras
S. Laine
T. Aila

title: A style-based generator architecture for generative adversarial networks

authors:
V. Khrulkov
I. Oseledets

title: Geometry score: A method for comparing generative adversarial networks

authors:
H. Kim
A. Mnih

title: Disentangling by factorising

venue: PMLR,

authors:
Z. Li
J.V. Murkute
P.K. Gyawali
L. Wang

title: Progressive learning and disentanglement of hierarchical representations

venue: arXiv preprint arXiv:2002.10549,

authors:
S. Lim
F. Memoli
O.B. Okutan

title: Vietoris-rips persistent homology, injective metric spaces, and the filling radius

venue: arXiv preprint arXiv:2001.07588,

authors:
Z. Lin
K.K. Thekumparampil
G. Fanti
S. Oh

title: Infogan-cr: Disentangling generative adversarial networks with contrastive regularizers

authors:
Z. Liu
P. Luo
X. Wang
X. Tang

title: Deep learning face attributes in the wild

venue: In Proceedings of International Conference on Computer Vision (ICCV),

title: Improving co-cluster quality with application to product recommendations

authors:
L. Matthey
I. Higgins
D. Hassabis
A. Lerchner

title: dsprites: Disentanglement testing sprites dataset

authors:
H. Narayanan
S. Mitter

title: Sample complexity of testing the manifold hypothesis

authors:
F. Pedregosa
G. Varoquaux
A. Gramfort
V. Michel
B. Thirion
O. Grisel
M. Blondel
P. Prettenhofer
R. Weiss
V. Dubourg
J. Vanderplas
A. Passos
D. Cournapeau
M. Brucher
M. Perrot
E. Duchesnay

title: Scikit-learn: Machine learning in Python

venue: Journal of Machine Learning Research,

authors:
D. Pfau
I. Higgins
A. Botev
S. Racanière

title: Disentangling by subspace diffusion

venue: Advances in Neural Information Processing Systems,

title: Probabilistic topological maps

venue: PhD thesis, Georgia Institute of Technology,

title: A survey of inductive biases for factorial representation-learning

authors:
B. Rieck
M. Togninalli
C. Bock
M. Moor
M. Horn
T. Gumbsch
K. Borgwardt

title: Neural persistence: A complexity measure for deep neural networks using algebraic topology

authors:
H. Shao
A. Kumar
P. Thomas Fletcher

title: The riemannian geometry of deep generative models

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
R. Shu
Y. Chen
A. Kumar
S. Ermon
B. Poole

title: Weakly supervised disentanglement with guarantees

authors:
A. Shukla
S. Uppal
S. Bhagat
S. Anand
P. Turaga

title: Geometry of deep generative models for disentangled representations

venue: In Proceedings of the 11th Indian Conference on Computer Vision, Graphics and Image Processing,

authors:
K. Simonyan
A. Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: 3rd International Conference on Learning Representations,

authors:
D. Stutz
M. Hein
B. Schiele

title: Disentangling adversarial robustness and generalization

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

title: On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms

authors:
A. Zomorodian
G. Carlsson

title: Computing persistent homology

venue: Discrete & Computational Geometry,

heading: 1 INTRODUCTION

text:
Learning disentangled representations is important for a variety of tasks, including adversarial robustness, generalization to novel tasks, and interpretability (Stutz et al., 2019; Alemi et al., 2017; Ridgeway, 2016; Bengio et al., 2013). Recently, deep generative models have shown marked improvement in disentanglement across an increasing number of datasets and a variety of training objectives (Chen et al., 2016; Lin et al., 2020; Higgins et al., 2017; Kim and Mnih, 2018; Chen et al., 2018b; Burgess et al., 2018; Karras et al., 2019). Nevertheless, quantifying the extent of this disentanglement has remained challenging and inconsistent. As a result, evaluation has often resorted to qualitative inspection for comparisons between models.
Existing evaluation metrics are rigid: while some rely on training additional ad-hoc models that depend on the generative model, such as a classifier, regressor, or an encoder (Eastwood and Williams, 2018; Kim and Mnih, 2018; Higgins et al., 2017; Chen et al., 2018b; Glorot et al., 2011; Grathwohl and Wilson, 2016; Karaletsos et al., 2015; Duan et al., 2020), others are tuned for a particular dataset (Karras et al., 2019). These both pose problems to the evaluation metric’s reliability, its relevance to different models and tasks, and consequently, its applicable scope. Specifically, reliance
on training and tuning external models presents a tendency to be sensitive to additional hyperparameters and introduces partiality for models with particular training objectives, e.g. variational methods (Chen et al., 2018b; Kim and Mnih, 2018; Higgins et al., 2017; Burgess et al., 2018) or adversarial methods with an encoder head on the discriminator (Chen et al., 2016; Lin et al., 2020). In fact, this reliance may provide an explanation for the frequent fluctuation in model rankings when new evaluation metrics are introduced (Kim and Mnih, 2018; Lin et al., 2020; Chen et al., 2016). Meanwhile, dataset-specific preprocessing, such as automatically removing background portions from generated portrait images (Karras et al., 2019), generally limits the scope of the evaluation metric’s applicability because it depends on the preprocessing procedure and may otherwise be unreliable.
To address this, we introduce an unsupervised disentanglement evaluation metric that can be applied across different model architectures and datasets without training an ad-hoc model for evaluation or introducing a dataset-specific preprocessing step. We achieve this by using topology, the mathematical discipline which differentiates between shapes based on gross features such as holes, loops, etc., alongside density analysis of samples. The combination of these two ideas are the basis for functional persistence, which is one of the areas of application of persistent homology (Cayton, 2005; Narayanan and Mitter, 2010; Goodfellow et al., 2016). In discussing topology, we walk a fine line between perfect mathematical rigor on the one hand and concreteness for a more general audience on the other. We hope we have found the right level for the machine learning community.
Our method investigates the topology of these low-density regions (holes) by estimating homology, a topological invariant that characterizes the distribution of holes on a manifold. We first condition the manifold on each latent dimension and subsequently measure the persistent homology of these conditional submanifolds. By comparing persistent homology, we examine the degree to which conditional submanifolds continuously deform into each other. This provides a notion of topological similarity that is higher across submanifolds conditioned on disentangled dimensions than those conditioned on entangled ones. From this, we construct our evaluation metric using the aggregate topological similarity across data submanifolds conditioned on every latent dimension in the generative model.
In this paper, we make several key contributions:
• We present an unsupervised metric for evaluating disentanglement that only requires the generative model (decoder) and is dataset-agnostic. In order to achieve this, we propose measuring the topology of the learned data manifold with respect to its latent dimensions. Our approach measures the topological dissimilarity measure across latent dimensions, and permits the clustering of submanifolds based on topological similarity.
• We also introduce a supervised variant that compares the generated topology to a real reference. • For both variants, we develop a topological similarity criterion based on Wasserstein distance,
which defines a metric on barcode space in persistent homology (Carlsson, 2019).
• Empirically, we perform an extensive set of experiments to demonstrate the applicability of our method across 10 models and three datasets using both the supervised and unsupervised variants. We find that our results are consistent with several existing methods.

heading: 2 BACKGROUND

text:
Our method draws inspiration from the Manifold Hypothesis (Cayton, 2005; Narayanan and Mitter, 2010; Goodfellow et al., 2016), which posits that there exists a low-dimensional manifoldMdata on which real data lie and pdata(x) is supported, and that generative models g : Z → X learn an approximation of that manifold Mmodel. As a result, the true data manifold Mdata contains high-density regions, separated by large expanses of low-density regions.Mmodel approximates the topology ofMdata, and superlevel sets of density withinMdata, through the learning process. A k-manifold is a space X , for example a subset of Rn for some n, which locally looks like an open set in Rk (formally, for every point x ∈ X , there is a subset can be reparametrized to an open disc in Rk). A coordinate chart for the manifold X is an open subset U of Rk together with a continuous parametrization g : U → X of a subset of X . An atlas for X is a collection of coordinate charts that cover X . For example, any open hemisphere in a sphere is a coordinate chart, and the collection of all open hemispheres form an atlas. We say two manifolds are homeomorphic if there is a continuous map from X to Y that has a continuous inverse. Intuitively, two manifolds are homeomorphic if one can be viewed as a continuous reparametrization of the other. If we have a continuous map f from a
manifold X to Rn, and are given two nearby points ~x and ~y in Rn, it is often useful to compare the subsets f−1(~x) and f−1(~y), which are manifolds (where the Jacobian matrix of f is maximal rank). They are frequently homeomorphic, and we will be using topological invariants that can distinguish between two non-homeomorphic manifolds.
Among the easiest topological invariants to numerically estimate is homology (Hatcher, 2005), which characterizes the number of k-dimensional holes in a topological space such as a manifold. Intuitively, these holes correspond to low-density regions on the manifold. The field of persistent homology offers several methods for estimating the homology of a topological space from data samples (Carlsson, 2019). Recent work on Relative Living Times (RLTs) (Khrulkov and Oseledets, 2018) has applied persistent homology to generative model data manifolds, also enabling direct comparison of generated data manifolds to real ones. For low-dimensional data (and images), points correspond to their vector representation (flattened matrices of pixels); for high-dimensional data, particularly images, points correspond to vectorized embeddings from a pretrained VGG16 (Simonyan and Zisserman, 2015).
To obtain RLTs, we first construct a family of simplicial complexes–graph-like structures–from data samples, each starting with a set of vertices representing the data points and no edges (Figure 2). These are witness complexes that characterize the topology of a set of points, a common method for statistically estimating topological invariants in persistent homology (Carlsson, 2019; Lim et al., 2020). These simplicial complexes approximate the persistent homology of the data manifold by identifying k-dimensional holes present in the simplices at varying levels of proximity. Proximity is defined with a dissimilarity metric (Euclidean distance) between points. It is used to build a simplicial complex in which a collection of points spans a simplex if all points have proximity measure less than some threshold, as shown in Figure 2d. Varying the threshold gives persistent homology. As proximity increases, simplices are added, creating varying numbers of k-dimensional holes, which gives rise to persistence barcodes (Carlsson, 2019; Zomorodian and Carlsson, 2005; Ghrist, 2008).
RLTs are vectorizations of these persistence barcodes, specifically the discrete distributions over the duration of each k-dimensional hole as it appears and disappears, or their lifetime relative to other holes. This is merely one method to (partially) vectorize persistence barcodes efficiently, and we leave it to future work to explore alternate methods (Adcock et al., 2013; Bubenik, 2015). To measure the topological similarity between data samples representing two generative model manifolds, Khrulkov and Oseledets (2018) then take the Euclidean mean of several RLTs to produce a discrete probability distribution, called a Mean Relative Living Time; they propose employing the Euclidean distance between two Mean Relative Living Times as the measure of topological similarity between two sets of data samples, known as the Geometry Score. Additional background is in Appendix B.

heading: 3 MANIFOLD INTERPRETATION OF DISENTANGLEMENT

text:
We use prevailing definitions of disentanglement where a disentangled model has a factorized latent space corresponding bijectively to factors of variation (Shu et al., 2019; Higgins et al., 2018; Duan
et al., 2020). We frame our approach primarily on the definition in Shu et al. (2019), with a more formal connection between their approach and our method in Appendix A.
From the manifold perspective, disentanglement is an extrinsic property that is dependent on the generative model’s atlas. Consider a disentangled generative model g with manifoldM that assumes topology τ . We can define another generative model g′ with the same underlying manifoldM and τ , but it is entangled and has a different atlas. In fact, we can define several alternate disentangled and entangled atlases, provided there are multiple valid factorizations of the space. As a result, we need a method that can detect whether an atlas is disentangled.
In this paper, we sliceM into submanifolds Usi=v ⊂M that are conditioned on a factor si at value v. These conditional submanifolds may have different homology from their supermanifoldM. If we observe samples from one factor, e.g. Xs1=v ∼ Us1=v at varying values of v, we find that all samples Xs1=v appear identical, except with respect to that single factor of variation si set to a different value of v. For a generative model, the correspondence between latent dimensions zj and factors si is not known upfront. As a result, we perform this procedure by conditioning on each latent dimension zj .
Conditional submanifold topology. For two submanifolds to have the same topology, there needs to be a continuous and invertible mapping between them. First, assume that there exists an invertible mapping, or encoder e : X → Z, and a generative model g : Z → X , where both functions are continuous. Then, for a given z and x = g(z), we can recover z by the composition z = e(g(z)). We can also construct a simple linear mapping l : z→ z’, which adapts a factor’s value, such that z’ = l(e(g(z))) remains continuously deformable. This holds across factors, where the manifold is topologically symmetric with respect to different factors, i.e. its conditional submanifolds are homeomorphic. As an example, consider a disentangled generative model g(z0, z1, z2) that traces a tri-axial ellipsoid x 2
z20 + y
2
z21 + z
2
z22 = 1. If we condition the model on varying values of each factor, the
resulting submanifolds are ellipses and have the same topology.
Most complex manifolds have submanifolds that have non-homeomorphic factors of variation. For example, consider a generative model g(z0, z1) that traces a cylindrical shell with angle z0, height z1, and for simplicity, no thickness. The submanifolds conditioned on angle z0 form lines (no holes), while the submanifolds conditioned on height z1 form circles (a 1D hole). However, the topology remains the same for a given factor. A visualization of this principle on a cone is shown in Figure 3. Taken together, this means that submanifolds within a factor (intra-factor) are homeomorphic, while submanifolds between factors (extra-factor) can be either homeomorphic or non-homeomorphic.
Topological asymmetry. Because topologically asymmetric submanifolds are non-homeomorphic, using a single e that continuously deforms across submanifolds no longer holds under disentanglement. To address this, assume that for each factor j, there exists a continuous invertible encoder ej : X → Zj that exclusively encodes information on j from a generated sample. In the cylindrical shell example, this means continuously deforming across submanifolds conditioned on varying values of z0 using e0 (deforming between lines) and likewise for z1 using an e1 (deforming between circles). Note that this formulation prevents continuous deformations between lines and circles. More generally, we cannot continuously deform across submanifolds conditioned by arbitrary factors and expect the topology to be preserved. This procedure now amounts to performing latent traversals along an axis and observing the topology of the resulting submanifolds. In a disentangled model, the j-conditional
Algorithm 1: Procedure for producing W. RLTs on generated images: For generator g with latent prior P and N samples, Dz latent dimensions, and nd samples per latent dimension, returns a W. RLT for each dimension. RLT is the RLT procedure from Khrulkov and Oseledets (2018).
for i in 1 : N do Sample z(i) ∼ P {note: z ∈ RN×Dz} end for for latent dimension d in 1 : Dz do
for k in 1 : nd do z′ ← copy(z) Set z′d ← k ∼ Pd Compute ez ← embedding(g(z′d)) {e.g. using VGG16} Compute rlt[d, k]← RLT (ez, γ = 1/128, L0 = 64, n = 100) end for Compute WB[d]←W.Barycenter(rlt[d, k])
end for return WB
submanifolds exhibit the same topology by continuous composition of z = ej(g(z)), using a linear mapping that only adapts factor j across the traversal, i.e. z′ = lj(ej(g(z))).
In an entangled model by contrast, more than one factor—such as both the angle and height in the cylindrical shell example—exhibit variation along a dimension zj . Put another way, the topology on submanifolds conditioned on zj changes when multiple factors contribute to variation along this dimension. Concretely, following the cylindrical shell example, a dimension that encodes height and, after a certain height threshold, also begins to adapt the angle will result in a topology that changes to include a 2D hole. Consequently, submanifolds conditioned on the same latent dimension zj have the same topology in a disentangled model, yet different topology in an entangled one.
Because we cannot assume that the data manifold of a generative model is completely symmetric, we only consider submanifolds to be homeomorphic along the same factor in a disentangled model. By contrast, since these submanifolds are not homeomorphic in an entangled model, we can measure the similarity across submanifolds to evaluate a model’s disentanglement. Using this notion of intra-factor topological similarity, we may sufficiently measure disentanglement in most cases, but it does not shield us from the scenario where a generative model learns a single trivial factor along all dimensions, i.e. a factorization of one. If we assume that there exists assymmetries in the data manifold, then ensuring that the manifold exhibits topological dissimilarity between certain factors would disarm that case. We operationalize this by identifying homeomorphic clusters of factors, whereby each cluster has a distinct topology to ensure there is not a factorization of one. Within clusters, we measure topological similarity, but between clusters, we calculate topological dissimilarity. Consequently, topological similarity and dissimilarity form the basis of our evaluation metric. A more principled treatment of how manifold topology measures disentanglement is in Appendix A.

heading: 3.1 TOPOLOGICAL SIMILARITY USING WASSERSTEIN RELATIVE LIVING TIMES

text:
To estimate the topological similarity between conditional submanifolds, we build on Relative Living Times (Khrulkov and Oseledets, 2018) and introduce Wasserstein (W.) Relative Living Times. Wasserstein distance, unlike Euclidean distance, defines a metric on barcode space (Carlsson, 2019); recall that barcodes are the discrete distributions representing the presence and absence of different k-dimensional holes (more formally known as Betti numbers, or kth homology groups), vectorized to form RLTs (Carlsson, 2019). This strongly motivates us to consider Wasserstein over Euclidean distance, which we find empirically to improve separation between distinct factors of variation (on a real disentangling dataset), detailed in Appendix C. Thus, in lieu of the Euclidean mean across RLTs,
we equivalently employ the W. barycenter (Agueh and Carlier, 2011). For distances between W. barycenters, we employ standard W. distance.
The W. barycenter p̄w of the distributions p1...pN corresponds to finding the minimum cost for transporting p̄W to each pi, where cost is defined in W-2 distance: p̄W = arg minq ∑N j=1 λjW 2 2 (q, pj),
where λ ≥ 0 and ∑N j=1 λj = 1. This is a weighted Fréchet mean, p̄ = arg minq ∑N j=1 λjd(q, pj), where d = W 22 . In contrast, Euclidean distance, or the l2 norm, is defined using d = ‖ · ‖22. Because our distributions represent discrete unnormalized counts of k-dimensional holes, we leverage recent work in unbalanced optimal transport (Chizat et al., 2018; Frogner et al., 2015) that assumes that pi are not normalized probabilities containing varying cumulative mass. The unbalanced W. barycenter modifies the W. distance to penalize the marginal distributions based on the extended KL divergence (Chizat et al., 2018; Dognin et al., 2019). Unlike Euclidean, Hellinger, or total variation distance, W. distance defines a valid metric on barcode space in persistent homology (Carlsson, 2019).
We provide the procedure for W. RLTs for the generated data manifold in Algorithm 1 and the real data manifold in Algorithm 2 of Appendix I. We also show in Appendix C that the use of both W. RLTs and W. distance result in a distance metric on sets of RLTs that best separates similar and dissimilar topological features, as measured using persistent homology.

heading: 3.2 EVALUATION METRIC

text:
Equipped with a procedure for measuring topological similarity, we develop a disentanglement evaluation metric from intra-cluster topological similarity and extra-cluster topological dissimilarity. Beginning with intra-factor topological similarity, we are concerned with the degree to which the topology of pmodel(x|si = v) varies with respect to a factor si at different values of v. Specifically, we condition the manifold on a particular factor si at value v, while allowing other factors s\i to vary. We then measure the topology of this conditional submanifold. For each factor si, we find the topology of conditional submanifolds at varying values of v. A disentangled model would exhibit topological similarity within the set of submanifolds conditioned on the same si. We visualize similar and dissimilar W. RLTs on factors of the CelebA dataset in Figure 4.
For a generative model, the correspondence between latent dimensions zj and factors si is not known upfront. As a result, we perform this procedure by conditioning on each latent dimension zj . We then assess pairwise topological similarity across latent dimensions ∀j,kd(zj , zk), where d is the W. distance between W. RLTs. This operation constructs a j-dimensional similarity matrix M . We use spectral coclustering (Dhillon, 2001) on M to cocluster zj into c biclusters, which represent different clusters of likely homeomorphic submanifolds conditioned on a shared factor. Spectral coclustering uses SVD to identify, in our case, the c ≤ j most likely biclusters, or the subsets of rows that are most similar to columns in M . The resulting biclusters create a correspondence from latent dimensions zi to a cluster of homeomorphic submanifolds conditioned on a factor hc. We then minimize the total variance of intra-cluster variance and extra-cluster variance on the biclusters in M to find the value for c. Aggregating biclusters in M , we obtain a c-dimensional matrix M ′c (see examples in
Figure 5). Using M ′c, we compute a score µ that rewards high intra-cluster similarity ρc = tr(M ′) and low extra-cluster similarity ρ\c = ∑ aM ′ a\a− tr(M
′) where a indexes the bicluster rows of M ′. This score is based on the normalized cut objective in spectral coclustering to measure the strength of associations within a bicluster (Dhillon, 2001). As a result, the unsupervised evaluation metric
µ = ρc − ρ\c.
Supervised variant. In order to capture the correspondence between the learned and real data topology, we present a supervised variant that uses labels of relevant factors on the real dataset to represent the real data topology. This is motivated in large part by F. Locatello et al. (2019), who importantly show that learning a fully disentangled a model requires supervision; further discussion is in Appendix B. While this supervised variant requires labeled data, there are no external ad-hoc classifiers or encoders that might favor one training criterion over another. Persistent homology is computed in the same way for the real data submanifolds as the generated data submanifolds, except that we have desired clusters of factors si upfront. See Figure 1 for a comparison between real and generated Wasserstein RLTs of two dSprites factors. The major difference is that the generated data manifold is no longer compared to itself, but to the real data manifold, where topological similarity is now computed between the two manifolds: ∀i,jd(zj , si), where d = W2. Note that the relevant factors in the real topology form a specific factorization, so a model that finds an alternate factorization and scores well on the unsupervised evaluation metric may not fare well on the supervised variant.
We use the same spectral coclustering procedure, though this time on a j× imatrix. Note that because it is not a square matrix, ρc = ∑c a=0M ′ aa and ρ\c = ∑c a=0 ∑c b=0M ′ ab−ρc, where c = min(c, i) so we only consider the real factors if c > i. Finally, we normalize the final score by number of factors
µSUP = µ/i,
to penalize methods that do not find any correspondence to some factors. Ultimately, the supervised evaluation metric favors submanifolds, conditioned on clusters of latent dimensions, which are similar to the conditional submanifolds of the ground truth dataset.
Limitations. In Figure 6, we highlight cases where our evaluation metric may face limitations, delineated from scenarios where it would behave as expected. The first limitation is that it is theoretically possible for two factors to be disentangled and, under cases of complete symmetry, still have the same topology. This is more likely in datasets with trivial topologies that are significantly simpler than dSprites. While partial symmetry is handled in the evaluation metric with spectral coclustering of homeomorphic factors, complete symmetry is not.
Because we assume the manifold is not exactly symmetric, we do not account for all factors to present symmetry. In order to safeguard against this case, we would need to consider the covariance of topological similarities across pairwise conditional manifolds. This requires selecting fixed points from v that hold two dimensions constant, and subsequently verifying that the topologies do not covary. However, this approach comes with a high computational cost for a benefit only to, for the most part, simple toy datasets. If we assign a Dirichlet process prior over all possible topologies (Ranganathan, 2008) and treat the number of factors as the number of samples, we find the probability of having only a single set of all homeomorphic factors decreases factorially with the number of dimensions n.
An additional limitation of our method is that RLTs do not compute a full topology of the data manifold, but instead efficiently approximate one topological invariant, homology, so that we can comparatively rank generative models on disentanglement. Our overall approach of measuring disentanglement is general enough to incorporate measurements of other topological invariants.

heading: 4 EXPERIMENTS

text:
Across an extensive set of experiments, our goal is to show the extent to which our metric is able to evaluate across different generative model architectures, training criteria, and datasets. We
Inf oG
AN
Inf oG
AN -CR
Inf oG
AN -CR
Inf oG
ANVA E VA E β-V AE β-V AE
β-T CV
AE
β-T CV
AE
Fac tor
VA E
Fac tor
VA E
μ (Ours)SUP Disentanglement (Kim & Mnih)
SupervisedUnsupervised
μ (Ours)
Inf oG
AN VA E
Fac tor
VA E β-V AE
Mutual Information Gap
β-T CV
AE
Inf oG
AN VA E
Fac tor
VA E β-V AE
β-T CV
AE
Figure 7: Comparisons of µ to MIG (Chen et al., 2018b) and µSUP to classifier-based disentanglement score (Kim and Mnih, 2018) on the dSprites dataset.
additionally show that our metric performs similarly to existing disentanglement metrics, without the same architectural or dataset-specific needs. We use pretrained model checkpoints where possible or else train with default hyperparameters. For each model and dataset combination we compute µ following Algorithms 1 and 3. To compute µSUP we also use Algorithm 2 to generate the W. RLTs of the real dataset. For the embedding function in Algorithms 1 and 2, we used a pretrained VGG16 (Simonyan and Zisserman, 2015) with the last 3 layers removed to embed image samples into 64 feature dimensions. Additional training details are in Appendix G.
Datasets. We present empirical results on three datasets: (1) dSprites (Matthey et al., 2017) is a canonical disentanglement dataset whose five generating factors {shape, scale, orientation, x-position, y-position} are complete and independent, i.e. they fully describe all combinations in the dataset; (2) CelebA is a popular dataset for disentanglement and image generation, and is comprised of over 202K human faces, which we align and crop to be 64× 64 px (Liu et al., 2015). There are also 40 attribute labels for each image; and (3) Celeba-HQ, a higher resolution subset of CelebA consisting of 30K images (Karras et al., 2018).
Generative models. We compare ten canonical generative models, including a standard VAE, βVAE (Higgins et al., 2017), β-VAEB (Burgess et al., 2018), FactorVAE (Kim and Mnih, 2018), β-TCVAE (Chen et al., 2018b), InfoGAN (Chen et al., 2016), InfoGAN-CR (Lin et al., 2020), BEGAN (Berthelot et al., 2017), WGAN-GP (Gulrajani et al., 2017), ProGAN (Karras et al., 2018), and StyleGAN (Karras et al., 2019). We evaluate VAE and InfoGAN variants on dSprites and CelebA, WGAN-GP and BEGAN on CelebA, and ProGAN and StyleGAN on CelebA-HQ. We match models to datasets, on which they have previously demonstrated strong performance and stable training.
Metric parity. We find that {µ, µSUP} rank models similarly to several other frequently cited metrics, including: (1) an information-theoric metric MIG that uses an encoder (Chen et al., 2018b), (2) a supervised metric from (Kim and Mnih, 2018) that uses a classifier, and (3) a dataset-specific metric PPL (Karras et al., 2019) that caters to face datasets such as CelebA-HQ. We use scores from their respective papers and prior work (Chen et al., 2018b; Kim and Mnih, 2018; Lin et al., 2020; Karras et al., 2019) to show that our method ranks most or all models the same across each metric (µ compared to MIG and PPL, µSUP to the supervised method). The source of deviation from MIG is the ranking of β-VAE; nevertheless, both of our scores exhibit exceptionally high variance across runs, suggesting that β-VAE has inconsistent disentanglement performance (see Figure 7). The classifier method ranks β-TCVAE and FactorVAE quite far apart, while ours ranks them similarly. We find that their nearly identical training objectives should rank them more closely and do not find this disparity particularly unexpected. Finally, our method agrees with PPL rankings on CelebA-HQ.
As shown in Table 1, these experiments highlight several key observations:
• Performance is not only architecture-dependent, but also dataset-dependent. This highlights the importance of having a metric that can cater to comparisons across these facets. Nevertheless, we note that β-VAEB shows especially strong results on both metrics and two dataset settings.
• As expected, the VAE and InfoGAN variants designed for disentanglement show greater performance on µ than their GAN counterparts. However, on µSUP, we find that BEGAN is able to perform inseparably close to β-VAEB , suggesting that the model learns dependent factors consistent with the attributes in CelebA.
• With similar training objectives, β-TCVAE and FactorVAE demonstrate comparable strong performances on µ across both dSprites and CelebA. β-TCVAE displays slight, yet consistent, improvements over FactorVAE, which may point to FactorVAE’s underestimation of total correlation (Chen et al., 2018b). Nevertheless, FactorVAE demonstrates higher µSUP on dSprites.
• StyleGAN demonstrates consistently higher disentanglement, compared to ProGAN, which supports architectural decisions made for StyleGAN (Karras et al., 2019).
Different datasets and requirements for evaluating disentanglement may favor an unsupervised variant over a supervised variant, and vice versa. Without known factors or without factors of interest, the unsupervised variant is clearly the more favorable or in some cases the only option.
One benefit of using the unsupervised variant even if the factors are known is when multiple combinations of factors are valid to disentangle the data. For example, one can imagine disentangling color into RGB {red, green, blue}, HSL {hue, saturation, lightness}, or HSV {hue, saturation, value}. The unsupervised evaluation metric would be satisfied with a model that disentangles into any of these. A supervised evaluation metric, for which the known factors are RGB, however, would not. RGB is a human (supervised) prior that dictates not only whether but how the factors disentangle. In effect, this leads to differences in rankings across the two variants. Nevertheless, in the case of a disentanglement dataset, such as dSprites, where the factors were created first and the data was created from those factors, we would expect that the known factors are reasonable ones, if not the best ones according to human judgment, to disentangle. That is, while there may be alternatives, this is a good, and quite possibly the most intuitive, human prior.
However, datasets in the wild, which CelebA veers closer to, differ in this respect. We do not know the complete set of factors of variation for CelebA’s human faces, and the attributes provided in the metadata are a subset at best. In this case, if one wishes to measure disentanglement generally, we suggest using unsupervised approaches to assess disentanglement of a learned model. If one wishes to measure disentanglement of specific factors, e.g. sunglasses and hair color, then the supervised variant would be more appropriate. Nevertheless, different variants suit different needs, and across datasets and variants, we may expect different models to emerge as superior in their ability to disentangle.

heading: 5 CONCLUSION

text: In this paper, we have introduced a disentanglement evaluation metric that measures intrinsic properties of a generative model with respect to its factors of variation. Our evaluation metric circumvents the typical requirements of existing evaluation metrics, such as requiring an ad-hoc model, a particular dataset, or a canonical factorization. This opens up the stage for broader comparisons across models and datasets. Our contributions also consider several cases of disentanglement, where labeled data is not available (unsupervised) or where direct comparisons to user-specified, semantically interpretable factors are desired (supervised). Ultimately, this work advances our ability to leverage the intrinsic properties of generative models to observe additional desirable facets and to apply these properties to important outstanding problems in the field.

heading: ACKNOWLEDGEMENTS

text: We would like to thank Torbjörn Lundh, Samuel Bengmark, and Rui Shu for their helpful feedback and encouragement in the preparation of our manuscript.