summaries: In this work the authors point out an issue related to graph neural networks. Specifically, if two nodes, that may be far apart in the graph, may be represented as (almost) the same vector. This is simply because when no features/labels are associated with nodes, and the local structure around those two nodes is very similar then the local aggregation of information will result in a similar representation.  Therefore the authors introduce an embedding first of the graph in the Euclidean space using DeepWalk and then use this embedding in combination with the design of a CNN. The authors propose a pooling method that outperforms several state-of-the-art pooling techniques on real data. Overall, the empirical results are supportive of the fact that the proposed method can help improve the performance of GNNs.

summaries: The authors propose in this paper to complement the node attributes in a graph with vectors obtained using a graph embedding algorithm. More precisely, they propose a graph neural network that apply several layers of graph convolution in parallel to the node attributes and to the embedding, then takes an average of the result, which is fed to another series of graph convolution. This is combined with some form of sampling which strongly resembles median based quantization but is solved with some basic heuristics and without acknowledging the resemblance (I might be missing something).

abstractText: The spatial convolution layer which is widely used in the Graph Neural Networks (GNNs) aggregates the feature vector of each node with the feature vectors of its neighboring nodes. The GNN is not aware of the locations of the nodes in the global structure of the graph and when the local structures corresponding to different nodes are similar to each other, the convolution layer maps all those nodes to similar or same feature vectors in the continuous feature space. Therefore, the GNN cannot distinguish two graphs if their difference is not in their local structures. In addition, when the nodes are not labeled/attributed the convolution layers can fail to distinguish even different local structures. In this paper, we propose an effective solution to address this problem of the GNNs. The proposed approach leverages a spatial representation of the graph which makes the neural network aware of the differences between the nodes and also their locations in the graph. The spatial representation which is equivalent to a point-cloud representation of the graph is obtained by a graph embedding method. Using the proposed approach, the local feature extractor of the GNN distinguishes similar local structures in different locations of the graph and the GNN infers the topological structure of the graph from the spatial distribution of the locally extracted feature vectors. Moreover, the spatial representation is utilized to simplify the graph down-sampling problem. A new graph pooling method is proposed and it is shown that the proposed pooling method achieves competitive or better results in comparison with the state-of-the-art methods.

authors:
Amr Ahmed
Nino Shervashidze
Shravan Narayanamurthy
Vanja Josifovski
Alexander J Smola

title: Distributed large-scale natural graph factorization

venue: In International Conference on World Wide Web (WWW), pp

authors:
James Atwood
Don Towsley

title: Diffusion-convolutional neural networks

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Mikhail Belkin
Partha Niyogi

title: Laplacian eigenmaps and spectral techniques for embedding and clustering

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:
Joan Bruna
Wojciech Zaremba
Arthur Szlam
Yann LeCun

title: Spectral networks and locally connected networks on graphs

venue: In International Conference on Learning Representations (ICLR),

authors:
Shaosheng Cao
Wei Lu
Qiongkai Xu

title: Grarep: Learning graph representations with global structural information

venue: In ACM International on Conference on Information and Knowledge Management (CIKM),

authors:
Diane J Cook
Lawrence B Holder

title: Mining graph data

authors:
Siamak Zamani Dadaneh
Xiaoning Qian

title: Bayesian module identification from multiple noisy networks

venue: EURASIP Journal on Bioinformatics and Systems Biology,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

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:
Matthias Fey
Jan Eric Lenssen
Frank Weichert
Heinrich Müller

title: Splinecnn: Fast geometric deep learning with continuous b-spline kernels

venue: In IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Alex Fout
Jonathon Byrd
Basir Shariat
Asa Ben-Hur

title: Protein interface prediction using graph convolutional networks

authors:
Hongyang Gao
Shuiwang Ji

title: Graph u-nets

venue: In International conference on machine learning (ICML),

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

title: Neural message passing for quantum chemistry

venue: In International Conference on Machine Learning (ICML),

authors:
Aditya Grover
Jure Leskovec

title: node2vec: Scalable feature learning for networks

venue: In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD),

authors:
Nathan Halko
Per-Gunnar Martinsson
Joel A Tropp

title: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

venue: SIAM Review,

authors:
William L Hamilton
Rex Ying
Jure Leskovec

title: Representation learning on graphs: Methods and applications

venue: IEEE Data Engineering Bulletin,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Mikael Henaff
Joan Bruna
Yann LeCun

title: Deep convolutional networks on graph-structured data

authors:
Keith Henderson
Brian Gallagher
Tina Eliassi-Rad
Hanghang Tong
Sugato Basu
Leman Akoglu
Danai Koutra
Christos Faloutsos
Lei Li

title: Rolx: structural role extraction & mining in large graphs

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

authors:
Sergey Ioffe
Christian Szegedy

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

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

title: Benchmark data sets for graph kernels, 2016

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Thomas Kipf
Ethan Fetaya
Kuan-Chieh Wang
Max Welling
Richard Zemel

title: Neural relational inference for interacting systems

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems (NIPS)

authors:
Junhyun Lee
Inyeop Lee
Jaewoo Kang

title: Self-attention graph pooling

authors:
Ron Levie
Federico Monti
Xavier Bresson
Michael M Bronstein

title: Cayleynets: Graph convolutional neural networks with complex rational spectral filters

venue: IEEE Transactions on Signal Processing,

authors:
Yujia Li
Daniel Tarlow
Marc Brockschmidt
Richard Zemel

title: Gated graph sequence neural networks

authors:
Enxhell Luzhnica
Ben Day
Pietro Lio

title: Clique pooling for graph classification

venue: arXiv preprint arXiv:1904.00374,

authors:
Dang Nguyen
Wei Luo
Tu Dinh Nguyen
Svetha Venkatesh
Dinh Phung

title: Learning graph representation via frequent subgraphs

venue: In SIAM International Conference on Data Mining,

authors:
Mathias Niepert
Mohamed Ahmed
Konstantin Kutzkov

title: Learning convolutional neural networks for graphs

authors:
Mingdong Ou
Peng Cui
Jian Pei
Ziwei Zhang
Wenwu Zhu

title: Asymmetric transitivity preserving graph embedding

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

authors:
Charles R Qi
Hao Su
Kaichun Mo
Leonidas J Guibas

title: Pointnet: Deep learning on point sets for 3d classification and segmentation

authors:
Charles Ruizhongtai Qi
Li Yi
Hao Su
Leonidas J Guibas

title: Pointnet++: Deep hierarchical feature learning on point sets in a metric space

authors:
Mostafa Rahmani
George K Atia

title: Spatial random sampling: A structure-preserving data sketching tool

venue: IEEE signal processing letters,

authors:
Sam T Roweis
Lawrence K Saul

title: Nonlinear dimensionality reduction by locally linear embedding

authors:
Michael Schlichtkrull
Thomas N Kipf
Peter Bloem
Rianne Van Den Berg
Ivan Titov
Max Welling

title: Modeling relational data with graph convolutional networks

venue: In European Semantic Web Conference,

authors:
Martin Simonovsky
Nikos Komodakis

title: Dynamic edgeconditioned filters in convolutional neural networks on graphs

venue: In Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Nitish Srivastava
Geoffrey Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting

venue: The journal of machine learning research,

authors:
Antoine J-P Tixier
Giannis Nikolentzos
Polykarpos Meladianos
Michalis Vazirgiannis

title: Graph classification with 2d convolutional neural networks

venue: In International Conference on Artificial Neural Networks (ICANN),

authors:
Daixin Wang
Peng Cui
Wenwu Zhu

title: Structural deep network embedding

authors:
Kelvin Xu
Jimmy Ba
Ryan Kiros
Kyunghyun Cho
Aaron Courville
Ruslan Salakhudinov
Rich Zemel
Yoshua Bengio

title: Show, attend and tell: Neural image caption generation with visual attention

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

authors:
Rex Ying
Jiaxuan You
Christopher Morris
Xiang Ren
William L Hamilton
Jure Leskovec
Joseph M Antognini
Jascha Sohl-Dickstein
Nima Roohi
Ramneet Kaur

title: Hierarchical graph representation learning with differentiable pooling

venue: In Advances in Neural Information Processing Systems (NeurIPS),

authors:
Muhan Zhang
Zhicheng Cui
Marion Neumann
Yixin Chen

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

venue: In AAAI Conference on Artificial Inteligence (AAAI),

heading: 1 INTRODUCTION

text:
Many of the modern data are naturally represented by graphs (Bronstein et al., 2017; Cook & Holder, 2006; Dadaneh & Qian, 2016; Qi et al., 2017b) and it is an important research problem to design neural network architectures which can work with graphs. The adjacency matrix of a graph exhibits the local connectivity of the nodes. Thus, it is straightforward to extend the local feature aggregation used in the Convolutional Neural Networks (CNNs) to the Graph Neural Networks (GNNs) (Atwood & Towsley, 2016; Bruna et al., 2014; Fey et al., 2018; Gilmer et al., 2017; Niepert et al., 2016; Simonovsky & Komodakis, 2017; Zhang et al., 2018). However, when the nodes of the graphs are not labeled/attributed or the labels/attributes of the nodes do not carry information about the differences between the nodes or any information about their locations in the graph, the GNN can fail to extract discriminative features. The GNN maps nodes whose corresponding local structures are similar to same/close feature vectors in the continuous feature space. Although mapping nodes with similar local structures to similar feature vectors might be desirable in some applications (Henderson et al., 2012), this feature can make the GNN unable to distinguish graphs whose difference is not in their local structures. In addition, when the nodes are not labeled/attributed, the spatial graph convolution only propagates information about the degree of the nodes which might not lead to extracting informative features about the topological structure of the graph. Another limitation of the current GNN architectures is that they are mostly unable to do the hierarchical feature learning employed in the CNNs (He et al., 2016; Krizhevsky et al., 2012). The main reason is that graphs lack the tensor representation and it is difficult to measure how accurate a subset of nodes represent the topological structure of the given graph.
Summary of Contributions. In this paper, we focus on the graph classification problem. The main contributions of this paper can be summarized as follows.
• A shortcoming of the GNNs is discussed and it is shown that the existing GNNs can fail to learn to perform even simple graph analysis tasks. It is shown that the proposed approach which leverages a spatial representation of the graph effectively addresses the shortcoming of the GNN. Several new experiments are presented to demonstrate the shortcoming of the GNNs and they show that providing the geometrical representation of the graph to the neural network substantially improves the capability of the GNN in inferring the structure of the graph.
• The geometrical representation of the graph is leveraged to design a novel graph pooling method. The proposed approach simplifies the graph down sampling problem into a column/row sampling problem. The proposed approach samples a subset of the nodes such that they preserve the structure of the graph. It is shown that the proposed approach achieves competitive or better performance in comparison with the existing methods.
Notation. Given a vector x, ‖x‖p denotes its `p Euclidean norm, and x(i) denotes its ith element. Given a matrix X, xi denotes the ith row of X. A graph with n nodes is represented by two matrices A ∈ Rn×n and F ∈ Rn×df , where A is the adjacency matrix, F is the matrix of node labels/attributes, and df is the dimension of the attributes/labels of the nodes. The operation A⇐ B means that the content of A is set equal to the content of B. If I is a set of indices, XI is the matrix of the rows of X whose indexes are in I. Vector y = softmax(x) is defined as y(i) = exp(x(i))∑
k exp(x(k)) .
The local structure corresponding to a node is the structure of the graph in the close neighbourhood of the node.

heading: 2 RELATED WORK

text:
This paper mainly focuses on the graph classification problem. In the proposed approach, the geometrical representation of the graph provided by a graph embedding algorithm is utilized to make the neural network aware of the topological structure of the graph. In this section, some of the related research works in GNN and graph embedding are briefly reviewed.
Graph Embedding: A graph embedding method aims at finding a continuous embedding vector for each node of the graph such that the topological structure of the graph is encoded in the spatial distribution of the embedding vectors. The nodes which are close on the graph or they share similar structural role are mapped to nearby points in the embedding space and vice versa. In general, the graph embedding methods fall into three broad categories: matrix factorization based methods (Ahmed et al., 2013; Belkin & Niyogi, 2002; Cao et al., 2015; Ou et al., 2016; Roweis & Saul, 2000), random-walk based approaches (Grover & Leskovec, 2016; Perozzi et al., 2014), and deep learning based methods (Wang et al., 2016). In this paper, we use the DeepWalk graph embedding method (Perozzi et al., 2014) which is a random walked based method.
Graph Neural Networks: In recent years, there has been a surge of interest in developing deep network architectures which can work with graphs (Bronstein et al., 2017; Bruna et al., 2014; Duvenaud et al., 2015; Fout et al., 2017; Gilmer et al., 2017; Hamilton et al., 2017; Kipf et al., 2018; Kipf & Welling, 2017; Li et al., 2016; Niepert et al., 2016; Simonovsky & Komodakis, 2017; Tixier et al., 2019). Local connectivity, weight sharing, and shift invariance of the convolution layer in the CNNs have led to remarkable achievements in computer vision and natural language processing (Goodfellow et al., 2016). Accordingly, there are remarkable works focusing on the design of graph convolution layers encoding the traditional properties. Most of the existing graph convolution layers can be loosely divided into two main subsets: the spatial convolution layers and the spectral convolution layers. The spectral methods are based on the generalization of spectral filtering in graph signal processing (Bruna et al., 2014; Defferrard et al., 2016; Henaff et al., 2015; Levie et al., 2017). The major drawback of the spectral based methods is the non-generalizability to data residing over multiple graphs which is due to the dependency on the basis of the graph Laplacian. In contrast to spectral graph convolution, the spatial graph convolution performs the convolution directly in the nodal domain and can be generalized across graphs (Nguyen et al., 2018; Niepert et al., 2016; Schlichtkrull et al., 2018; Simonovsky & Komodakis, 2017; Veličković et al., 2017; Verma & Zhang, 2018; Zhang et al., 2018). If the sum function is used to aggregate the local feature vectors, a simple spatial convolution layer can be written as
X⇐ A f (XΦ1) + f (XΦ2) , (1) where f(·) is the element-wise non-linear function. Some papers use a normalized version of (1) via multiplying (1) with the inverse of the degree matrix (Ying et al., 2018). The weight matrix
Φ2 transforms the feature vector of the given node and Φ1 transforms the feature vectors of the neighbouring nodes. A drawback of the spatial convolution is that the aggregation function might not be an injective function, i.e., two nodes with different local structures can be mapped to the same feature vector by the convolution layer. The authors of (Xu et al., 2019) showed that with a minor modification, the sum aggregation function can become an injective function. However, when the nodes are not labeled/attributed or the labels/attributes do not inform the GNN about the location of the nodes, the GNN is not able to distinguish graphs whose local structures are similar but their global structures are different. The approach proposed in our paper not only addresses the problem raised in (Xu et al., 2019), it also helps the GNN to distinguish the similar local structures in different locations of the graph.
In order to obtain a global representation of the graph, the local feature vectors obtained by the convolution layers should be aggregated into a final feature vector. The element-wise max/mean functions are used widely to aggregate all the local feature vectors. Inspired by the hierarchical feature extraction in the CNNs, tools have been developed to perform nonlocal feature aggregation (Duvenaud et al., 2015; Luzhnica et al., 2019). In (Zhang et al., 2018), the nodes are ranked and the ranking is used to build a sequence of nodes using a subset of the nodes. Subsequently, a 1- dimensional CNN is applied to the sequence of the nodes to perform non-local feature aggregation. However, the way that (Zhang et al., 2018) builds the sequence of the nodes is not data driven. In addition, a 1-dimensional array might not have the capacity to preserve the topological structure of the graph. In (Ying et al., 2018), a soft graph pooling method was proposed which learns a set of cluster centers that are used to down-sample the extracted local feature vectors. The graph pooling methods proposed in (Gao & Ji, 2019; Lee et al., 2019) are similar to the soft graph pooling method presented in (Ying et al., 2018) but they learn one cluster center which is used to rank the nodes and they sample the nodes which are closer to the learned cluster center. In (Defferrard et al., 2016; Fey et al., 2018), the graph clustering algorithms were used to perform graph down-sizing.

heading: 3 THE SHORTCOMING OF THE GNNS

text:
Suppose the nodes of the given graphs are not labeled/attributed or assume that the labels/attributes do not contain any information about the role/location of the nodes in the global structure of the graph. Therefore, if two different nodes are not labeled or they are labeled similarly, they appear the same to the GNN. Accordingly, if the local structures corresponding to two nodes are similar, the convolution layer of the GNN maps them to the same feature vector in the continuous feature space. This means that if the local structures of two different graphs are similar, the GNN cannot extract discriminative features to distinguish them. In the followings, we study an example to clarify this feature of the GNN.
Illustrative example: Suppose we have a dataset of clustered unlabeled graphs (nodes and edges are not labeled/attributed) and assume that the clusters are not topologically different (a common generator created all the clusters). Every node is connected to small a set of the other nodes in its corresponding cluster. One class of the graphs consist of two clusters and the other class of graphs consist of three clusters. Therefore, the task is to infer if a graph is made of two clusters or three clusters. Consider the simplest case in which there is no connection between the clusters. Assume that we use a typical GNN which is composed of multiple spatial convolution layers and a global element-wise max/mean pooling layer. Suppose that a given graph belongs to the first class, i.e., it consists of two clusters. Define v1 and v2 as the aggregation of the local feature vectors corresponding to the first and the second clusters, respectively. The global feature vector of this graph is equal to the element-wise mean/max of v1 and v2. Clearly, v2 can be indistinguishable from v1 since the clusters are generated using the same generator and the GNN is not aware of the location of the nodes. Therefore, the feature vector of the whole graph can also be indistinguishable from v1. The same argument is also true for a graph with three clusters. Accordingly, the representation obtained by the GNN is unable to distinguish this two classes of graphs. If one trains a GNN on this task, the test accuracy is around 50 % which is not better than random guess. The main reason is that the local structures corresponding to all the nodes in a graph are similar. In addition, the local structures in a graph with two clusters is not different from the local structures in a graph with three clusters. Since the GNN is not aware of the location of the nodes, all the nodes are mapped to similar
feature vectors in the feature space. Accordingly, the spatial distribution of the local feature vectors of the two classes of the graphs are indistinguishable. 1

heading: 4 PROPOSED APPROACH

text:
In section 3, it was shown that the GNN can fail to infer the topological structure of the graph when the local structures in the graph are similar. The GNN is not aware of the location of each node in the global structure of the graph and it maps all the nodes whose corresponding local structures are similar to same/close points in the feature space. This was the main reason that the GNN failed to learn to perform the task described in Section 3. Ideally, if the extracted feature vector for each node is a function of its location in the graph, the nodes are mapped to different points (corresponding to their locations) in the feature space and the GNN can distinguish the graphs via analyzing the spatial distribution of the extracted local feature vectors. Accordingly, we propose an approach using which the extracted feature vectors depend on the location/role of the nodes in the global structure of graph. Another motivation for the proposed approach is the remarkable success of the neural networks in analysing point-clod data (Qi et al., 2017a). In point-cloud data, each data point is corresponding to a point on the surface of the object and the location of each point in the 3D space is included in the feature vector which represents each point of the surface. The neural networks which process the point-cloud representation yielded the state-of-the-art performance in the 3D vision tasks (Qi et al., 2017b).
1 As another example, note the last three columns of Table 1 which are corresponding to three classification tasks described in Section 5. The second row shows the accuracy of a GNN on these tasks. In all the three tasks, the performance of the GNN is comparable to random guess.
In order to include the locations of the nodes in the extracted local feature vectors, first we have to define a representation for the location of each node. Suppose that vector ei ∈ Rde in the dedimensional Euclidean space contains the information about the location of the ith node. Evidently, if the ith node and the jth node are close to each other on the graph, ei and ej should be close to each other in the continuous space and vice versa. Interestingly, a graph embedding method can perfectly provide the location representation vectors {ei}ni=1. Graph embedding maps each node to a vector in the embedding space such that the distance between two points in the embedding space is proportional to the distance of the corresponding nodes on the graph. Accordingly, in order to make the extracted local feature vectors a function of the role of the nodes in the structure of the graph, we propose the approach depicted by the red box in Figure 1. The matrix F ∈ Rn×df represents the node labels/attributes and E ∈ Rn×de denotes the matrix of the embedding vectors obtained by a graph embedding method (e.g., DeepWalk). The red box represents a GNN Equipped with the Spatial Representation (GNN-ESR). The GNN-ESR leverages both the node labels/attributes and the node embedding vectors to extract the local features. Accordingly, the GNN-ESR is aware of the locations of the nodes and the distance between different nodes and it does not map nodes whose corresponding local structures are similar to the same feature vector. The convolution layers of the GNN-ESR provides a spatial distribution of the local feature vectors which the next layers use to infer the structure of the graph. For instance, in the example discussed in Section 3, the spatial distribution of the local feature vectors corresponding to two graphs in two different classes were indistinguishable. In sharp contrast, if the local feature vectors are extracted using the GNN-ESR, they can build two/three clusters in the feature space if the graph is composed of two/three clusters. Accordingly, the distribution of the feature vectors makes the two classes distinguishable.
Algorithm 1 Node Sampling Using the Geometrical Description of the Graph Input. The matrix of embedding vectors E ∈ Rn×de and m as the number of sampled nodes. 0. Initialization. Sample index k from set {i}ni=1 randomly and initialize set Is = {k}. 1. Repeat m times: Sample the next embedding vector such that it has the maximum distance to the sampled embedding vectors, i.e., append k to set Is such that
k = argmax t (min ({‖et − ej‖2}j∈Is)) . (2)
2. Output: Is contains indexes of the sampled nodes.

heading: 4.1 GRAPH POOLING VIA DATA POINT SAMPLING

text:
One of the main challenges of extending the architecture of the CNNs to graphs is to define a pooling function which is applicable to graphs. In this section, the proposed graph pooling method is presented which utilizes the geometrical representation of the graph. The proposed method is composed of two main steps: node sampling and graph down-sampling.
Node Sampling: It is not straightforward to measure how accurate a sub-sampled graph represents the topological structure of the given graph. Graph embedding encodes the topological structures of the graph in the spatial distribution of the embedding vectors. Accordingly, the node sampling problem can be simplified into a data point sampling problem. Since the distribution of the embedding vectors represents the topological structure of the graph, we define the primary aim of the proposed pooling function to preserve the spatial distribution of the embedding vectors.
Data point sampling is a well-know problem in big data analysis (Halko et al., 2011) known as column/row sampling problem. A simple method is to perform random data point sampling. However, if the distribution of the data points is sparse in some region of the space, random sampling might not be able to capture the spatial distribution of the data points. Most of the existing sampling methods aim at finding a small set of informative data points whose span is equal to the row-space of the data. However, preserving the row-space of the data is not necessarily equivalent to preserving the spatial distribution of the rows (Rahmani & Atia, 2017). Define {ei}i∈Is as the set of sampled embedding vectors where Is is the set of the indexes of the sampled embedding vectors. We define the objective of the sampling method as
min Is n∑ k=1 (min{‖ek − ei‖p}i∈Is) subject to |Is| = m , (3)
where |Is| is the cardinality of Is. The minimization problem (3) samples m embedding vectors such that the summation of the distances between the embedding vectors and their nearest sampled embedding vector is minimum. This minimization problem is non-convex and it is hard to solve. We propose Algorithm 1 which uses the farthest data point sampling and provides a greedy method to find the sampled data points. Algorithm 1 samples the first embedding vector randomly. In the subsequent steps, the next embedding vector is sampled such that it has the maximum distance to the previously sampled embedding vectors. Accordingly, in each step the embedding vectors which are not close to sampled ones are targeted and gradually the sampled embedding vectors cover the distribution of all the embedding vectors. The computation complexity of Algorithm 1 isO(mn de). Although Algorithm 1 starts from a randomly chosen embedding vector, this random choice does not cause variance at test time. Algorithm 1 uses farthest data point sampling and the sampled embedding vectors finally cover the spatial distribution of all the embedding vectors (independent from the starting point). Moreover, one can choose the first embedding vector in a deterministic way. For instance, one candidate could be the embedding vector which is the closest vector to the mean of all the embedding vectors.
Graph Down Sampling: Define X ∈ Rn×d as the matrix of feature vectors (Figure 1) and define Xs and As as the matrix of feature vectors and the adjacency matrix of the sub-sampled graph. The sub-sampled adjacency matrix is obtained via sampling the columns and rows of A corresponding to the indexes in Is. We present two methods to obtain Xs. Method 1: Sample the rows of X corresponding to the indexes in Is. In other word,
Xs = XIs . (4) Method 2: In (4), the feature vectors of the unsampled nodes are discarded. Thus, some useful information could be lost during the down-sampling step. In the second method, we utilize the rows of X corresponding to the sampled indexes as pivotal feature vectors and all the feature vectors are aggregated around them using the attention technique (Xu et al., 2015). Define P ∈ Rm×d as the matrix of pivotal feature vectors equal to P = XIs which is equivalent to the matrix of the subsampled feature vectors in Method 1. Using the pivotal feature vectors, we define m assignment vectors {qi ∈ Rn}mi=1 as follows qi = softmax(X pTi ) , (5) where pi is the ith row of P. The vector qi is an attention vector which represents the resemblance between all the feature vectors and the ith pivotal vector. The attention vector qi is used to aggregate the feature vectors of X and obtain the ith feature vector of the sub-sampled graph as follows
xsi = q T i X , (6)
where xsi is the ith row of Xs. Remark 1. If the nodes of the given graph are sparsely connected, the down-sampled graph can be a disconnected graph. Define Ar = ∑r i=1 A
i . If the distance between the jth node and the kth node is less than r + 1, Ar(j, k) is non-zero. Therefore, if we down-sample Ar to obtain the adjacency matrix of the sub-sampled graph, two sampled nodes are connected if their distance is less than r+1. In the presented experiments, we down-sized A3 to obtain As. In most of the graph classification applications, the size of the graphs is not large. However, if in a specific application the size of the graphs is large, the computation of Ak (for k ≥ 2) could require large volume of memory. In this scenario, one can simply down sample the adjacency matrix A and find the disconnected nodes and subsequently connect each disconnected node to its nearest sampled node (nearest according to the original graph). In addition, if we use Ak to obtain the down sampled adjacency matrix and the obtained adjacency matrix is dense, one can sparsify the matrix by applying a proper threshold to the values of the down sampled adjacency matrix. In the presented experiments, we did not face this problem and we used the exact down sampled version of A3. Remark 2. We presented two methods to obtain Xs. In the presented experiments, we used both of them to obtain Xs. The final Xs was obtained as a convex combination of them.

heading: 5 NUMERICAL EXPERIMENTS

text:
First we focus on demonstrating the significance of equipping the GNN with the spatial representation. Subsequently, the proposed pooling method (Spatial Pooling) is compared with the existing graph pooling methods.
The structure of the basis neural network: In the presented experiments, GNN-ESR indicates the neural network depicted by the red box in Figure 1 with k1 = 1 and k2 = 2. The dimensionality of the output of all the convolution layers is equal to 64. The functionality of each convolution layer can be written as (1) where f(·) is the Relu function followed by Batch-normalization (Ioffe & Szegedy, 2015). The output of all the convolution layers are concatenated (Xu et al., 2018) to obtain the global representation of the graph and the element-wise max function is used as the global aggregator. The fully connected classifier is composed of three fully connected layers. The first two layers of the fully connected classifier are equipped with dropout (Srivastava et al., 2014) ( dropout probability equal to = 0.5) and batch-normalization. In the presented tables, GNN indicates a graph neural network similar to the GNN-ESR while E is not provided as an input.
The input and the optimizer: The Deep-Walk graph embedding method (Perozzi et al., 2014) was used to embed the graphs and the dimension of the embedding vectors is equal to 12. The length of the random walks is determined as max (4,min(n/10, 10)) where n is the number of the nodes. All the neural networks were similarly trained using the Adam optimizer (Kingma & Ba, 2015). The learning rate was initialized at 0.005 and was reduced to 0.0005 during the training process. Following the conventional settings, we perform 10-fold cross validation (Zhang et al., 2018). We refer the reader to (Kersting et al., 2016) for a complete description of the used real-world datasets. The size of each synthetic dataset is equal to 1000.

heading: 5.1 ANALYZING UNLABELED/NON-ATTRIBUTED GRAPHS

text:
In this section, we consider graphs whose nodes are not labeled/attributed. In some of the utilized real datasets, the nodes are labeled/attributed which are discarded in this experiment to examine the ability of the neural networks in inferring the topological features of the graphs in the absence of the labels/attributes. First we describe the designed synthetic graph classification tasks.
High Level Loop Detection (HLLD): In this task, the generated graphs are composed of 3 to 6 clusters (the number of clusters are chosen randomly per graph). Each cluster is composed of 20 to 45 nodes (the number of nodes are chosen randomly per cluster). Each node in a cluster is connected to 5 other nodes in the same cluster. In addition, if two clusters are connected, 3 nodes of one cluster are densely connected to 3 nodes of the other cluster. In the generated graphs, the consecutive clusters are connected. The classifiers are trained to detect if the clusters in a graph form a loop. Obviously, there are many small loops inside each cluster. The task is to detect if the clusters form a high level loop. Accordingly, this task is equivalent to a binary classification problem. Part (a) of Figure 2 shows an example of the HLLD task.
Count Number of Clusters (CNC): In this task, the graphs are similar to the graphs in the HLLD task. However, the objective of the CNC task is to count the number of clusters. The generated graphs are composed of 3 to 6 clusters. This task is equivalent to a classification task with four classes.
Count the Number of the Loops of Clusters (CNLC): In this task, the generated graphs contain several clusters and the clusters form multiple loops. For instance, the graph depicted in Part (b) of Figure 2 consists of 11 clusters and the clusters form form 3 loops. In this experiment, the clusters can form 2 to 4 loops and each loop is formed with 3 to 5 clusters. The number of clusters in each loop is chosen randomly per loop. The objective of this task is to count the number of the loops. Thus, this task is equivalent to a graph classification task with three classes.
Table 1 shows the classification accuracy of a simple GNN and the GNN-ESR. The last three columns show the performance with the synthetic datasets. One can observe that the GNN failed to learn to perform the synthetic tasks. The main reason is that in the synthetic tasks, the local structure corresponding to all the nodes are similar and the convolution layers map all the nodes to similar vectors in the feature space. Thus, the GNN cannot extract discriminative features from the distribution of the local feature vectors. In sharp contrast, the GNN-ESR is aware of the differences/similarities between the nodes and it does not necessarily map them to similar feature vectors when the nodes are not close to each other on the graph. The results show that the GNN-ESR successfully extracts discriminative features from the distribution of the extracted local feature vectors. Moreover, the results with real datasets demonstrate that the proposed approach significantly (up to 23 %) improves the classification accuracy. The spatial representation makes the GNN-ESR aware of the difference between the nodes (although they are not labeled) and it paves the way for the GNN-ESR to extract discriminative features from the distribution of the embedding vectors.

heading: 5.2 ANALYZING LABELED GRAPHS

text:
This experiment is similar to the previous experiment but the node labels are included. We use the real datasets and the following synthetic tasks.
Number of Labeled Clusters (NLC): The graphs in this task are similar to the graphs in the CNC task. Each graph is composed of 6, 7, or 8 clusters. The consecutive clusters are connected and they form a loop. The labels of the nodes are binary (0 or 1) and all the nodes in the same cluster are labeled similarly. The task is to count the number of clusters whose nodes are labeled 1. There are 4 classes of graphs, i.e., the number of clusters which are labeled 1 are equal to 2, 3, 4, or 5. Figure 3 shows an example of this task.
Match the Diagonal Clusters MDC: In this task, each graph is composed of 6, 8, or 10 clusters and the clusters form a loop. The labels of the nodes are binary and all the nodes in a cluster are labeled similarly. The task is to check if all the pairs of diagonal clusters are labeled similarly. A pair of clusters are called a pair of diagonal clusters if they are in the maximum distance from each other. Therefore, the MDC task is equivalent to a binary classification task. Figure 3 shows an example of this graph classification task.
Table 2 shows classification accuracy with different datasets. One can observe that even when the nodes are labeled, the difference between the performances is significant for most of the datasets. The main reason is that the spatial representation makes the neural network aware of the differences between the nodes and the neural network leverages both the node labels and the node embedding vectors to extract discriminative features.

heading: 5.3 GRAPH POOLING

text:
In this experiment, the proposed graph pooling method (Spatial Pooling) is compared with some of the recently published pooling algorithms. In all the neural networks, the described GNN-ESR is used to extract the local feature vectors. Similar to the architecture depicted in Figure 1, the pooling layer is placed next to last convolution layer of the GNN-ESR. Since the graphs in the datasets are not large graphs (mostly less than 100 nodes), one down-sampling layer was used.
• Spatial Pooling: Two spatial convolution layers were implemented after the down-sampling step. Define Y ∈ Rn×192 as the concatenation of the outputs of all the convolution layers before the pooling layer (three convolution layers) and define y ∈ R192 as the aggregation of these n feature vectors (by the element-wise max function). Similarly, define Ys ∈ Rm×128 as the concatenation of the outputs of all the convolution layers after the pooling layer and define ys ∈ R128 similar to y. The final representation of the graph is defined as the concatenation of y and ys and it is used as the input of the final classifier. We chose m = min(30,max(5, n/4)).
• Diff-Pool (Ying et al., 2018): This method was implemented according to the instructions in (Ying et al., 2018). Two spatial convolution layers were placed after the down-sizing step. The final representation of the graph was obtained similar to the procedure used in Spatial-Pooling. • Rank-PooL (Gao & Ji, 2019; Lee et al., 2019): Similar to the other pooling methods, one down-sampling layer was used and two spatial convolution layers were implemented after the down-sizing step. The number of sampled nodes was chosen similar to the proposed method. • Sort-Node (Zhang et al., 2018): Similar to the implementation described in (Zhang et al., 2018) and its corresponding code, 30 nodes were sampled to construct the ordered sequence of the nodes.
Table 3 shows the accuracy of the GNN-ESR with different pooling methods. One can observe that Spatial-Pooling achieves higher or comparable results on all the datasets. On the MDC dataset, Spatial-Pooling outperforms the other methods and on ENZYM and SYNTHIE datasets, it slightly outperforms Diff-Pool. The Diff-Pool method also achieves notable performance on most of the datasets. The feature vectors which Diff-Pool uses to down-size the graph are fixed. In contrast, the way the proposed approach down-sizes the graph depends on the topology of the graph not a set of fixed cluster centers. One can observe that the accuracy of Sort-Pool is significantly less than the accuracy of Spatial-Pooling and Diff-Pool with the MDC dataset. The main reason is that SortPool sorts the nodes in a 1-dimensional array. The placement of the nodes in a 1-dimensional array leads to loosing important information about the structure of the graph. An observation one can make by studying the results is that the performance of the GNN-ESR is close to the performance of the GNN-ESR with the pooling layers. In contrast, the performance of a simple GNN with the pooling layers can be notably higher than the performance of the GNN (Yanardag & Vishwanathan, 2015). For instance, Table 4 shows the performance of the neural networks with and without the pooling layers. One can observe that the performance of the GNN equipped with the pooling layer is notably higher than the performance of the GNN on the MDC and the ENZYM datasets. In contrast, the difference between the performances reported in the third and the forth rows is lower. Another predictable point that Tables 4 makes is that the pooling layer cannot make the GNN able to learn
to perform the CNC task or the HLLD task (and also the CNLC task). In these tasks, the neural network should be able to distinguish the nodes to be able to infer the structure of the graph.

heading: 6 CONCLUSION

text: An important shortcoming of the GNN was discussed . It was shown that if the nodes/edges of the given graph are not labeled/attributed or the labels/attributes do not make the GNN aware of the role of the nodes in the structure of the graph, the GNN can fail to infer the topological structure of the graph. Motivated by the success of the deep networks in analyzing point-cloud data, we proposed an approach in which a geometrical representation of the graph is provided to the GNN. The geometrical representation is computed by a graph embedding method which encodes the topological structure of the graph into the spatial distribution of the embedding vectors. We showed that the proposed approach significantly empowers the GNN via analyzing its performance on a diverse set of real and synthetic datasets. Moreover, the spatial representation was utilized to simplify the graph down-sampling problem and a novel graph pooling method was proposed.


summaries: This paper proposed "F pooling" for Frequency Pooling, which is a pooling operation satisfying shift equivalence and anti-aliasing properties. The method is very simple: first, transform the input 1D/2D signal into the spectrum domain based on discrete Fourier transform (DFT), then cut the high-frequencies, then transform back to the time domain using the inverse DFT. The method can be implemented using FFT and auto differentiation frameworks. The method is tested on Resnet/Desnet on CIFAR-100 and subsets of ImageNet, showing better performance than the original models.

summaries: This paper researches the pooling operation, which is an important component in convolutional neural networks (CNN) for image classification. Taking the perspective from signal processing, this paper proposes a pooling operation called frequency pooling (F-pooling). The key motivation is to make the pooling operation shift-equivalent and anti-aliasing. This paper gives an improved definition on shift-equivalent functions and shows that the proposed F-pooling is optimal in the sense of reconstructing the orignal signal. The F-pooling is then implemented with matrix multiplications and tested with recent convolutional neural networks for image classifiation on CIFAR-100 and a subset of ImageNet dataset.

abstractText: Convolutional layer utilizes the shift-equivalent prior of images which makes it a great success for image processing. However, commonly used down sampling methods in convolutional neural networks (CNNs), such as max-pooling, averagepooling, and stride convolution, are not shift-equivalent. This destroys the shiftequivalent property of CNNs and degrades their performance. In this paper, we provide a formal definition of shift-equivalent when down sampling involved. We propose a strict shift equivalent and anti-aliasing pooling method. This is achieved by (inverse) Discrete Fourier Transform and we call our method frequency pooling. Experiments on image classifications show that frequency pooling improves accuracy and robustness w.r.t shifts of CNNs.

authors:
Md Faijul Amin
Kazuyuki Murase

title: Single-layered complex-valued neural network for realvalued classification

venue: problems. Neurocomputing,

authors:
Aharon Azulay
Yair Weiss

title: Why do deep convolutional networks generalize so poorly to small image transformations

venue: arXiv preprint arXiv:1805.12177,

authors:
Taco S. Cohen
Mario Geiger
Jonas Khler
Max Welling

title: Spherical CNNs

venue: In International Conference on Learning Representations,

authors:
Logan Engstrom
Brandon Tran
Dimitris Tsipras
Ludwig Schmidt
Aleksander Madry

title: A rotation and a translation suffice: Fooling cnns with simple transformations

venue: arXiv preprint arXiv:1712.02779,

title: Fractional max-pooling

venue: arXiv preprint arXiv:1412.6071,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Spatial pyramid pooling in deep convolutional networks for visual recognition

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

authors:
Yann Lecun
Bernhard E Boser
John S Denker
D Henderson
R E Howard
W Hubbard
L D Jackel

title: Handwritten digit recognition with a back-propagation network

authors:
Chenyu Lee
Patrick W Gallagher
Zhuowen Tu

title: Generalizing pooling functions in convolutional neural networks: Mixed

venue: gated, and tree

authors:
Jonathan Long
Evan Shelhamer
Trevor Darrell

title: Fully convolutional networks for semantic segmentation

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: Computer Science,

title: Certain topics in telegraph transmission theory

venue: Transactions of The American Institute of Electrical Engineers,

authors:
Adam Paszke
Sam Gross
Soumith Chintala
Gregory Chanan
Edward Yang
Zachary DeVito
Zeming Lin
Alban Desmaison
Luca Antiga
Adam Lerer

title: Automatic differentiation in pytorch

authors:
Antti Rasmus
Harri Valpola
Mikko Honkala
Mathias Berglund
Tapani Raiko

title: Semisupervised learning with ladder networks

authors:
Jongbin Ryu
Minghsuan Yang
Jongwoo Lim

title: Dft-based transformation invariant pooling layer for visual classification

authors:
Mark Sandler
Andrew Howard
Menglong Zhu
Andrey Zhmoginov
Liang-Chieh Chen

title: Mobilenetv2: Inverted residuals and linear bottlenecks

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

authors:
Dominik Scherer
Andreas Muller
Sven Behnke

title: Evaluation of pooling operations in convolutional architectures for object recognition

authors:
Chiheb Trabelsi
Olexa Bilaniuk
Ying Zhang
Dmitriy Serdyuk
Sandeep Subramanian
Joao Felipe Santos
Soroush Mehri
Negar Rostamzadeh
Yoshua Bengio
Christopher J Pal

title: Deep complex networks

authors:
Travis Williams
Robert Li

title: Wavelet pooling for convolutional neural networks

authors:
Wenpeng Yin
Katharina Kann
Mo Yu
Hinrich Schutze

title: Comparative study of cnn and rnn for natural language processing

venue: arXiv: Computation and Language,

title: Making convolutional networks shift-invariant again

venue: arXiv preprint arXiv:1904.11486,

heading: 1 INTRODUCTION

text:
Convolutional neural networks (CNNs) have achieved great success on image processing Goodfellow et al. (2016), natural language processing Yin et al. (2017), game playing Mnih et al. (2013) and so on. One of the reasons is that convolutions utilize the shift-equivalent prior of signals. Modern CNNs include not only convolutional layers but also down sampling or pooling layers. As an important part of CNNs, pooling layers are used to reduce spatial resolution of feature maps, aggregate spatial information, and reduce computational and memory cost.
Based on classical Nyquist sampling theorem Nyquist (1928), the sampling rate must be at least as twice as the highest frequency of a signal. Otherwise, frequency aliasing will appear, i.e. highfrequencies of the signal alias into low-frequencies. This leads sub-optimal when reconstruction the signals and misleads the following processing because orthogonal components are mixed again. To anti-alias, a traditional solution is that applying low-pass filter to the signal before down sampling it. Following the spirit of blurred down sampling, early CNNs use average pooling to achieve down sampling Lecun et al. (1989). Later, empirical evidence suggests max-pooling Scherer et al. (2010) and stride convolutions Long et al. (2015) provide better performance. They are widely used in CNNs but they don’t consider about anti-aliasing.
Shift-equivalent is another expected property of pooling. Otherwise it will destroy the shiftequivalent of CNNs and thus the shift-equivalent prior of signals is not fully utilized. Unfortunately, most commonly used poolings are not shift-equivalent. Worse, small shifts in the input can drastically change the output when stacking multiple max-pooling or stride convolutions Engstrom et al. (2017); Azulay & Weiss (2018); Zhang (2019).
Shift-equivalent is believed to be a fundamental property of CNNs. However, the fact that CNNs with poolings are not shift-equivalent has been ignored by the community. Until recently, Zhang (2019) propose anti-aliasing pooling (AA-pooling) by low-pass filtering before down sampling. They observe increased accuracy and better generalization on image classification when low-pass filtering is integrated correctly. Specifically, they decompose a pooling operator with down sampling factor s into two parts: a pooling operator with factor 1 and a blur filter with factor s. Although AApooling reduces the aliasing effects and makes the outputs more stable w.r.t input shifts, it is neither strict shift-equivalent nor anti-aliasing in theory.
In this paper, we propose a strict shift equivalent and anti-aliasing pooling in theory. We first transform a signal or image into frequency domain via Discrete Fourier Transform (DFT). Then we only retain its low frequencies, i.e. the frequencies which are smaller than Nyquist sampling
rate. Finally, we transform the low frequencies back into time domain via inverse DFT. We call our method frequency pooling (F-pooling). Note that a similar method is proposed in Ryu et al. (2018). However, they only focus on classification accuracy. Shift equivalent of their method is not evaluated in both theory and practice. Compared with previous works, the novelties and contributions of Fpooling are summarized as follows:
• We formally define shift-equivalent of functions which contain down sampling operations. A suitable up sampling operation U must be involved in the definition. Without it, the definition for discrete signal is ill-posed. We believe a formal mathematical treatment has great value for further research.
• We prove that F-pooling is the optimal anti-aliasing down sampling operation from the perspective of reconstruction. We also prove that F-pooling is shift equivalent. The up sampling operation U plays an important rule in our proofs. To best of our knowledge, F-pooling is the first pooling method which has those properties.
• Experiments on CIFAR-100 and a subset of ImageNet demonstrate that F-pooling remarkably increases accuracy and robustness w.r.t shifts of commonly-used network architectures. Moreover, the shift consistency of F-pooling is improved more when we replace zero padding of convolutions with circular padding.

heading: 2 METHOD

text: In this section, we first define shift-equivalent for CNNs formally. Then we describe F-pooling in detail and prove its properties. Finally we discuss our implementation and some practical issues.

heading: 2.1 DEFINITION OF SHIFT-EQUIVALENT

text:
Denote X as an h0 × w0 × c tensor where h0, w0, and c are the height, width, and number of channels of X respectively. Denote Y as an h1×w1× c tensor. We suppose h0 > h1 and w0 > w1. M : X → Y is a pooling operation and U : Y → X is a up sampling operation. We say M is shift-equivalent if and only if
Shift4h,4w(UMX) =UMShift4h,4w(X) (1) ∀(4h,4w), ∃U
That is, if there is a suitable up sampling operation U which makes UM and Shift4h,4w commutable, thenM is shift-equivalent. The shift operation is required to be circular or periodic. When a shifted element hits the edge, it rolls to other side.
Shift4h,4w(Xa,b) = X(a+4h)%h0,(b+4w)%w0 (2)
where % is the modulus function. Our definition of shift-equivalent is similar with the one in Zhang (2019). The difference is that we introduce an up sampling U to make this definition strict. Without
introducing U , the definition of shift-equivalent for pooling is ill-posed. SupposeM down samples signals by a factor s. Without introducing U , one may define shift-equivalent as follows:
Shift4h/s,4w/s · M(X) =M · Shift4h,4w(X), ∀(4h,4w) (3) However, Shift4h/s,4w/s is not operable for discrete signals when 4h%s 6= 0 or 4h%s 6= 0. To make the shifted element which is not on lattice operable, one must interpolate or up sample the down sampled signals. This leads to the definition in equation 1.
As in equation 1, to makeM shift-equivalent, one must find the corresponding up sampling operation U . For a givenM, the first line in equation 1 may hold for some up sampling operations. But it may not hold for other up sampling operations.

heading: 2.2 F-POOLING

text:
The basic idea of F-pooling is removing the high frequencies of signals and reconstructing the signals only using the low frequencies. In this paper, high frequencies mean the frequencies which are beyond Nyquist frequency, i.e. half of signal resolution. And low frequencies mean the frequencies which are not higher than Nyquist frequency. To remove high frequencies, we first transform signals into frequency domain via DFT. Then only the low frequencies are retained. Finally, we transform the low frequencies back to time domain via inverse DFT (IDFT). Figure 2 gives an illustration of the forward process of F-pooling.
Since 2D (inverse) DFT can be decomposed into two 1D (inverse) DFT, we provide the formal representation of F-pooling in 1D case. Denote x ∈ RN as time domain signal and y ∈ CM as frequency domain signal. Without loss of generality, we suppose M is even. FN ∈ CN×N is the so-called DFT-matrix:
FN =  ω0·0N ω 0·1 N . . . ω 0·(N−1) N ω1·0N ω 1·1 N . . . ω 1·(N−1) N ... ... . . . ...
ω (N−1)·0 N ω (N−1)·1 N . . . ω (N−1)·(N−1) N  (4) where ωN = e−2πi/N . F∗N is the inverse DFT-matrix. By definition, 1 NFNF ∗ N = I where I is identity matrix. We denote Tµ as a operation which selects the first µ rows and the last µ rows of a matrix. Tµ(x) = [x1:µ;xN−µ+1:N ] (5) That is we select the basis of frequencies ranged in [−µ, µ), due to periodicity of DFT. When applying Tµ to a signal, we obtain its lowest µ frequencies. Then the function of F-pooling for 1D signals is represented as:
y = 1
N F∗MTM 2 FNx def = Px (6)
where P ∈ CM×N is the transform matrix of F-pooling. Now we formalize F-pooling for CNNs. Recall that X is an h0×w0×c tensor and Y is an h1×w1×c tensor. We apply F-pooling to each channel of X.
Y:,:,i = PhX:,:,iP ∗ w, i ∈ [1, c] (7)
where Ph ∈ Ch1×h0 and Pw ∈ Cw1×w0 are the transform matrices of F-pooling along vertical direction and horizontal direction respectively. Since F-pooling can be represented as two times matrix-matrix multiplications, its back propagation rule is easily derived.
As mentioned in section 2.1, the choice of up sampling operation U is important. In this paper, U is set to the inverse process of F-pooling. Specifically, we transform a signal into frequency domain. Then we zero pad the transformed signal to match the resolution of output. Finally, we transform it back to time domain. This process can also be represented by matrix multiplications. For 1D signals, we have:
x = 1
M F∗NZM 2 FMy (8)
where is Z is the zero padding operation.
Zµ = [x1:µ;0;xM−µ+1:M ] (9)
The formulations of F-pooling and U are easily extended to 2D case.

heading: 2.3 OPTIMAL ANTI-ALIASING DOWN SAMPLING

text:
In this section, we prove that F-pooling is the optimal anti-aliasing down sampling operation from the perspective of reconstruction given U . We focus on 1D case here. Given U , the optimal antialiasing down sampling is obtained by solving the following problem:
min M ||UMx− x||22, s.t. M∈ A (10)
where A is a set of all possible anti-aliasing down sampling operations. That is, we hope to find an anti-aliasing down sampling which minimizes the reconstruction error. Based on Nyquist sampling theory,M must remove high frequencies of signals and this holds for F-pooling. We focus on the optimality of F-pooling. We decompose x into low frequencies part xl and high frequencies part xh, i.e. xl = 1NF ∗ NDM2
FNx and xh = x − xl. Dµ is a diagonal matrix whose the first µ and the last µ diagonal elements equal to 1 while others equal to 0.
||UMx− x||22 = ||UMx− xl − xh||22 (11) = ||UMx− xl||22 + ||xh||22 + 〈UMx,xh〉 − 〈xl,xh〉 (12) = ||UMx− xl||22 + ||xh||22 (13)
equation 13 holds because the third term and the forth term of equation 12 equal to 0. M removes high frequencies and U doesn’t introduce new frequencies. Thus UMx only contains low frequencies. Due to the orthogonality of frequency spectrum, 〈UMx,xh〉 = 0. Similarly, 〈xl,xh〉 = 0. WhenM is F-pooling, we have
UMx = 1 MN F∗NZM 2 FMF ∗ MTM 2 FNx (14)
= 1
N F∗N
( ZM
2 TM 2
) FNx (15)
= 1
N F∗NDM 2 FNx def = xl (16)
equation 16 holds due to the definition of operations T, Z, and D. See appendix A for proof. Since the fist term of equation 13 equals to 0, equation 10 is minimized. Thus, we have proved that Fpooling is the optimal anti-aliasing down sampling operation from the perspective of reconstruction.
We choose reconstruction optimality because: 1) we believe reconstruction optimality relates to the final performance, e.g. classification optimality for image classification. If we accept that the feature extracted by previous convolution layers is useful, then it is best to keep it as much as possible for the current pooling layer. Prior works have shown that using self reconstruction loss as an auxiliary is helpful for classification Rasmus et al. (2015); 2) It is difficult to directly define classification optimality for an intermediate layer.

heading: 2.4 SHIFT-EQUIVALENT

text:
Based on shift theorem of Fourier transform, we have
FNShift4h(x) =FNx S4h (17) Shift4h(F ∗ Nx) =F ∗ Nx S4h (18)
where S4h ∈ CN whose kth element is e− 2πk N 4h and is element-wise multiplication. Combining with equation 16, we have
UMShift4h(x) = 1
N F∗NDM 2 FNShift4h(x) (19)
= 1
N F∗N
( DM
2 FNx
) S4h (20)
= Shift4h
( 1
N F∗NDM 2 FNx
) (21)
= Shift4h(UMx) (22)
We have proved that F-pooling is shift-equivalent. Note that equation 22 is not hold if other up sampling operations are used, such as linear interpolation.
The proofs in section 2.3 and 2.4 can be easily extended for 2D signals.

heading: 2.5 TRANSITIVITY OF SHIFT-EQUIVALENT

text:
We study the transitivity of shift-equivalent for F-pooling. Denote f as a shift-equivalent function without down sampling or up sampling. It is straightforward to shown
UMShift4h(f(x)) = Shift4h(UMf(x)) (23)
That is shift-equivalent of F-pooling is transitive for any shift-equivalent function f without down sampling or up sampling. And it is transitive for F-pooling itself. For example, a stack of two F-pooling layers is still a shift-equivalent function.
Unfortunately, this transitivity of F-pooling is not hold for a shift-equivalent function with down sampling. For example, a function of Fpooling → conv → relu → Fpooling is not shiftequivalent. This prevents us to obtain strict shift-equivalent deep CNNs.

heading: 2.6 PRACTICAL ISSUES

text:
Dealing with imaginary part: generally, the output of F-pooling, i.e. Mx contains both real part and imaginary part. However, for commonly used CNNs, the feature maps must be real. Thus one must ignore the imaginary part of F-pooling. On the other hand,Mx is treated as complex in the proofs in section 2.3 and 2.4. If we ignore the imaginary part, F-pooling is no longer the optimal anti-aliasing down sampling (but still anti-aliasing) and F-pooling is no longer strict shift-equivalent.
Fortunately, this issue is easy to overcome. When the resolution of down sampled signals is odd, the imaginary part ofMx is zero. Suppose the resolution is 2µ+ 1.
x̂−µ, . . . , x̂−1, x̂0, x̂1 . . . , x̂µ (24)
Due to its symmetry, it only contains real part when transforms back into time domain. If the resolution is µ+ 2
x̂−µ, . . . , x̂−1, x̂0, x̂1 . . . , x̂µ, x̂µ+1 (25)
In this case, it contains imaginary part. But we can recover the symmetry and eliminate the imaginary part by setting x̂µ+1 to zero. We call this trick odd padding. We show the effects of odd padding in appendix B. A drawback of odd padding is that more information is lost during down sampling which may reduces accuracy. We don’t use it in this paper.
Compared with equation 24 and equation 25, the imaginary part is introduced by x̂µ+1. Thus, the error of ignoring the imaginary part is smaller than ||x̂µ+1||22. In practice, we find this effect is small. Dealing with zero padding: F-pooling is designed to be circular shift equivalence. However, zero padding is commonly used in convolution layers. Convolutional layers with zero padding destroy circular shift-equivalence. Thus, one should expect that using circular padding in convolutional layers will greatly increase the shift consistency of F-pooling. In this paper, we evaluate the performance of F-pooling with both zero-padding and circular padding. We suggest one replaces zero padding with circular padding for better shift-equivalence.

heading: 2.7 IMPLEMENTATION

text:
We implement F-pooling in PyTorch Paszke et al. (2017). Theoretically, it is best to implement F-pooling with fast Fourier transform (FFT) and inverse FFT. Suppose F-pooling down samples an h0 × w0 × c tensor to a h1 × w1 × c tensor. Then its time complexity is ch0w0 log(w0h0)). Unfortunately, we find such a implementation in PyTorch is comparatively slow.
Instead, we implement F-pooling via 1 × 1 convolutions. As in equation 7, 2D F-pooling can be represented as two times matrix-matrix multiplications along vertical direction and horizontal direction respectively. This is equivalent to 1× 1 convolutions along vertical direction and direction horizontal. Its time complexity is O(h0w0(h1 + w1)) which is higher than the optimal complexity. F-pooling requires much more computational costs than average pooling or max-pooling. F-pooling is faster than a convolutional layer when the resolution of feature maps is smaller than the number of channels, as the situations of image classifications. Moreover, the number of pooling layers is limited compared with the number of convolutional layers. Thus, introducing F-pooling will not introduce too many computational costs into CNNs.
Zhang (2019) claims that it is important to integrate anti-aliasing pooling into CNNs in a correct way. In this paper, we follow their settings. Specifically, a max-pooling with stride s is replaced with a max-pooling with stride 1 and an F-pooling with stride s. A convolution with stride s is replaced with a convolution with stride 1 and an F-pooling with stride s. An average pooling with stride s is replaced with an F-pooling with stride s. See the illustration in figure 3.

heading: 3 EXPERIMENTS

heading: 3.1 1D SIGNALS

text: We test the shift-equivalent of F-pooling on 1D signals. In figure 1, the original signal is a randomly selected row of a 512 × 512 image. We apply max-pooling, average pooling, and F-pooling with stride 4 to those signals. As shown in figure 1, F-pooling is perfectly shift-equivalent. And average pooling is better than max-pooling from shift-equivalent perspective. odd padding is used here.

heading: 3.2 IMAGE CLASSIFICATION

text:
CIFAR-1001: we test classification of low-resolution 32 × 32 color images. This dataset contains 50k images for training and 10k images for test. Images are classified into one of 100 categories.
sub-ImageNet: we then test classification of high-resolution color images. Original ImageNet dataset Russakovsky et al. (2015) contains 1.28M training and 50k validation images, classified into one of 1,000 categories. To reduce the computational resources for training, we use a subset of ImageNet (sub-ImageNet) in this work. We randomly select 200 categories from 1,000 categories. For each category, we randomly select 500 images. Thus, we collect 100k images for training. And we select corresponding 10k validation images. All models are trained on a single GPU with batchsize 64 and 100 epochs. We decrease the initial learning rate by a factor 10 every 40 epochs. For other hyper-parameters, we follow PyTorch’s official training script.2
We train CIFAR-100 using resnet He et al. (2016) and densenet Huang et al. (2017). We train subImageNet using resnet, densenet, and mobilenet-v2 Sandler et al. (2018). Those models are widely used as benchmarks. Max-pooling, average pooling, and stride convolution are covered in those models. We also compare F-pooling with AA-pooling Zhang (2019). For a model trained on subImageNet, its first down sampling operation is kept to reduce computational costs. This setting is also used in Zhang (2019). The results on CIFAR-100 are averaged by 3 runs.
We study not only accuracy but also consistency. We follow the metric of consistency used in Zhang (2019): we check how often the network outputs the same classification, given the same image with two different shifts.
Eh0,h1,w0,w11 {argmax p(Shifth0,w0) = argmax p(Shifth1,w1)} (26) We only evaluate diagonal shifts in this paper. For CIFAR-100, the number of shifted pixels ranges from -7 to 7. For sub-ImageNet, it ranges from -63 to 63.
Zero padding: we keep the padding method of convolutions as zero padding. We measure accuracy and consistency of different pooling methods. Results on sub-ImageNet is shown in table 1 and results on CIFAR-100 are shown in table 2 respectively.
Circular padding: as mentioned earlier, circular padding may improve the consistency of Fpooling. Thus we replace the zero padding of convolutions with circular padding. To further evaluate the robustness w.r.t shifts, we use standard deviation (std) of probabilities of the correct label. Std and consistency on sub-ImageNet an CIFAR-100 are shown in table 3 and table 4 respectively.
Based on those results, we conclude that
• F-pooling is significantly and consistently better than original pooling methods in terms of accuracy and shift consistency.
• F-pooling is comparable with AA-pooling in term of accuracy and shift consistency with zero padding. With circular padding, F-pooling is significantly better than AA-pooling.
• Shift consistency of F-pooling is improved more when replacing zero padding with circular padding, especially on CIFAR-100.
1https://www.cs.toronto.edu/ kriz/cifar.html 2https://github.com/pytorch/examples/tree/master/imagenet

heading: 4 RELATED WORKS

text:
Pooling which reduces the resolution of feature maps is an important part of CNNs. Early CNNs Lecun et al. (1989) use average pooling which is good for anti-aliasing. Later empirical evidence suggests max-pooling Scherer et al. (2010) and strided-convolutions Long et al. (2015) provide better performance. However, small shifts in the input can drastically change the output when stacking multiple max-pooling or strided-convolutions Engstrom et al. (2017); Azulay & Weiss (2018). Other variants such as Graham (2014); He et al. (2015); Lee et al. (2016) (we just list a few of them), focus on extending the functionality of pooling Lee et al. (2016) or making pooling adjusted to variable input size Graham (2014); He et al. (2015).
Recently, Zhang (2019) shows that CNNs will have better shift-equivalent and anti-aliasing properties when low-pass filtering is integrated correctly. However, their method is not strict shiftequivalent and anti-aliasing in theory. Williams & Li (2018) propose Wavelet-pooling. They decompose a signal via wavelet transform and retain the lowest sub-band. This process is repeated until the designed down sampling factor is met. The spirit of Wavelet-pooling is similar to F-pooling. However, they claim that Wavelet-pooling is better than others because it is a global transform instead of a local transform. They neither focus on shift-equivalent nor prove Wavelet-pooling is shift-equivalent or not.
F-pooling is a complex transformation because DFT and IDFT are involved in it. Many works integrate complex transformations or complex values into neural networks. Amin & Murase (2009) study single-layered complex-valued neural networks for real-valued classification problems. Complex numbers represented in polar coordinates are more suitable to deal with rotations. Based on this, Cohen et al. (2018) propose spherical CNNs which are rotation-equivalent to deal with signals projected from spherical surface. Trabelsi et al. (2018) propose general deep complex CNNs. They adjust batch normalization and non-linear activations for complex CNNs. F-pooling can used in their method without worry about the imaginary part. F-pooling utilizes shift theorem of DFT and achieves shift-equivalent. This is a new success for the combination of complex transformations and neural networks.

heading: 5 CONCLUSIONS

text: In this paper, we have proposed frequency pooling (F-pooling) for CNNs. F-pooling reduces the dimension of signals in frequency domain. We have defined shift-equivalent of functions which contain down sampling operations by introducing an up sampling operation. Under this definition, we have proved that F-pooling is the optimal anti-aliasing down sampling operation and F-pooling is shift-equivalent. We have integrated F-pooling into modern CNNs. We have verified that Fpooling remarkably increases accuracy and robustness w.r.t shifts of modern CNNs. We believe that F-pooling plays a more important role in applications where shift-equivalent is more serious, such as object detection and semantic segmentation.

heading: A PROOF OF OPERATION

text:
We prove DM 2 = ZM 2 TM 2 . By definition, T can be represented as an M ×N matrix and Z can be represented as a N ×M matrix.
TM 2 =
[ IM
2 0M 2 0N 2 −M 0N 2 −M 0M 2 0M 2
0M 2 0M 2 0N 2 −M 0N 2 −M 0M 2 IM 2
] (27)
where IM is an M ×M identity matrix and 0M is an M ×M zero matrix. ZM 2 is equal to the transpose of TM
2 by definition. Then
ZM 2 TM 2 = IM2 · ·· 0N−M · · · IM
2  (28) which is the same as DM
2 by definition.
B EFFECT OF odd padding
C LOSS CURVES ON SUB-IMAGENET