Title: HAARPOOLING: GRAPH POOLING WITH COMPRES-SIVE HAAR BASIS

Abstract: Deep Graph Neural Networks (GNNs) are instrumental in graph classification and graph-based regression tasks. In these tasks, graph pooling is a critical ingredient by which GNNs adapt to input graphs of varying size and structure. We propose a new graph pooling operation based on compressive Haar transforms, called Haar-Pooling. HaarPooling is computed by following a chain of sequential clusterings of the input graph. The input of each pooling layer is transformed by the compressive Haar basis of the corresponding clustering. HaarPooling operates in the frequency domain by the synthesis of nodes in the same cluster and filters out fine detail information by compressive Haar transforms. Such transforms provide an effective characterization of the data and preserve the structure information of the input graph. By the sparsity of the Haar basis, the computation of HaarPooling is of linear complexity. The GNN with HaarPooling and existing graph convolution layers achieves state-of-the-art performance on diverse graph classification problems.

1. INTRODUCTION:

Graph Neural Networks (GNNs) have demonstrated excellent performance in node classification tasks and are very promising in graph classification and regression (Bronstein et al., 2017; Battaglia et al., 2018; Zhang et al., 2018b; Zhou et al., 2018; Wu et al., 2019) . In node classification, the input is a single graph with missing node labels that are to be predicted from the known node labels. In this problem, GNNs with appropriate graph convolutions can be trained based on the single graph that is provided, and achieve state-of-the-art performance (Defferrard et al., 2016; Kipf & Welling, 2017; Ma et al., 2019b) . Different from node classification, graph classification is a task where the label of any given graph-structured sample is to be predicted based on a training set of labeled graph-structured samples. This is similar to the image classification task tackled by traditional deep convolutional neural networks. The major difference is that here each input sample may have an arbitrary adjacency structure, instead of the fixed regular grids that are used in images. An example of graph-structured data are the molecules of different sizes shown in Figure 1 . This raises two important challenges: 1) How can GNNs exploit the graph structure information of the input data? 2) How can GNNs handle input graphs with varying number of nodes and connectivity structures?

Figure 1 : Graph-structured data: two molecules with atoms as nodes and bonds as edges. Each molecule has a different number of nodes and molecular structure. In graph classification (and regression), each input datum is an individual graph with features defined on the graph nodes (e.g., indicating the chemical element).

These problems have motivated the design of proper graph convolution and graph pooling to allow GNNs to capture the geometric information of each data sample (Zhang et al., 2018a; Ying et al., 2018; Cangea et al., 2018; Gao & Ji, 2019; Knyazev et al., 2019; Ma et al., 2019a; Lee et al., 2019) . Graph convolution plays an important role especially in question 1).

Figure 2 : Computational flow of a Graph Neural Network consisting of three blocks of GCN graph convolutional and HaarPooling layers, followed by an MLP. In this example, the output feature of the last pooling layer has dimension 4, which is the number of input units of the MLP.

The following graph convolution, as proposed by Kipf & Welling (2017) , is a widely accepted example:

X out = AX in W.

(1)

Here A = D -1/2 (A + I) D -1/2 ∈ R N ×N is a normalized version of the adjacency matrix A of the input graph, where I is the identity matrix and D is the degree diagonal matrix for A + I. Further, X in ∈ R N ×d is the array of d-dimensional features on the N nodes of the graph, and W ∈ R d×m is the filter parameter matrix. The graph convolution in equation 1 captures the structural information of the input in terms of A (or A), and W transforms the feature dimension from d to m. The filter size d × m does not depend on the graph size, which allows a fixed network architecture to process input graphs of varying size. However, the GCN convolution preserves the number of nodes and hence the output dimension of the network is not unique. Graph pooling provides an effective way to overcome this obstacle. Among several approaches that have been proposed, only EigenPooling (Ma et al., 2019a) incorporates both features and graph structure. However, this is based on eigenpairs of graph Laplacian and suffers from a high computational cost. We provide an overview of this and other graph pooling methods in Section 2.

In this paper, we propose a new graph pooling strategy based on a sparse Haar representation of the data, which we call HaarPooling. This is based on the Haar basis (Li et al., 2019) , which incorporates graph structure and features, and is computationally efficient. Suppose we have an input X in ∈ R N ×d . HaarPooling is then defined as

EQUATION

where This paper is organized as follows. Section 2 gives an overview of existing work on graph pooling. Section 3 details the components and computational flow for HaarPooling. Section 4 provides the mathematical details on HaarPooling, including the compressive Haar basis, compressive Haar transforms, and efficient implementations. Section 5 reports our experimental results on benchmark graph classification tasks compared with existing graph pooling methods. Section 6 concludes the paper. Proofs and implementation details are deferred to the appendix.

Φ ∈ R N ×N1 , N 1 < N . Each column of Φ is a compressive

2. RELATED WORK:

Graph pooling is a necessary step when building a GNN model for graph classification, as one needs a unified graph-level rather than node-level representation for graph inputs for which size and topology are changing. The most direct pooling method takes the global mean and sum of node representations obtained by the graph convolutional layer (Duvenaud et al., 2015) as a simple graph-level representation. However, this pooling operation treats all the nodes equally and ignores the global geometry of the graph. ChebNet (Defferrard et al., 2016) uses a graph coarsening procedure to build the pooling module, which requires graph clustering algorithms to obtain subgraphs. One drawback of this topology-based strategy is that it does not incorporate the node features in the pooling. Global pooling methods consider the information of node embeddings to obtain the entire graph representation. As a general framework for graph classification problems, MPNN (Gilmer et al., 2017) uses the Set2Set method (Vinyals et al., 2015) to obtain graph-level representations. Zhang et al. (2018a) proposed a SortPool method that sorts feature representation of nodes before feeding them into traditional 1-D convolutional and dense layers. But these global pooling techniques cannot guarantee hierarchical graph representations that may contain useful information in the graph structure. A prominent recent idea is to build a differentiable and data-dependent pooling layer with learnable operations/parameters, which has brought substantial improvements on graph classification tasks. Ying et al. (2018) proposed a differentiable pooling layer (DiffPool) that learns a cluster assignment matrix over the nodes using the output of a GNN model. One common problem with DiffPool is its huge storage complexity, which results from the computation of the soft clustering assignments. Cangea et al. (2018) ; Gao & Ji (2019) ; Knyazev et al. (2019) used a Top-K pooling method that samples a subset of important nodes by employing a trainable projection vector. Lee et al. (2019) introduced Self-Attention Graph Pooling (SAGPool) by replacing the way node scores are computed in Top-K pooling by a GCN module. These hierarchical pooling methods technically still employ mean/max pooling procedures to aggregate the feature representation of super-nodes, which would lead to information loss. Diehl et al. (2019) proposed EdgePool which is a scheme which considers edge contraction and thus takes into account of graph structure in pooling.

There are also spectral-based pooling methods that take account of both the graph structure and its node features. Noutahi et al. (2019) proposed the Laplacian Pooling (LaPool) method that dynamically selects centroid nodes and their corresponding follower nodes by an attention mechanism that uses the graph Laplacian. Ma et al. (2019a) introduced EigenPool which uses local graph Fourier transform to extract subgraph information utilizing both node features and structure of the subgraph. Its potential drawback lies in the inherent bottleneck of computing Laplacian-based graph Fourier transform, given the huge cost in the eigendecomposition of the graph Laplacian. This shortcoming partially motivates our present work.

3. HAARPOOLING:

In this section we give an overview of the proposed HaarPooling framework. First we define the pooling architecture in terms of a chain, i.e., a sequence of graphs (G 0 , G 1 , . . . , G K ), where the nodes of each G j+1 correspond to clusters of nodes of G j+1 , j = 0, . . . , K -1. Each layer in the chain determines which sets of nodes are pooled together. Then we construct the compressive Haar transform, which compresses the dimension of the features.

Chain of coarse-grained graphs for pooling Graph pooling amounts to defining a sequence of coarse-grained graphs. In our chain, each graph is an induced graph that arises from grouping (clustering) certain subsets of nodes from the previous graph. We use clustering algorithms to generate the groupings of nodes. There are many good candidates, such as spectral clustering (Shi & Malik, 2000) , k-means clustering (Pakhira, 2014) , DBSCAN (Ester et al., 1996) , OPTICS (Ankerst et al., 1999) and METIS (Karypis & Kumar, 1998) . Any of these will work with HaarPooling.

Figure 3 shows an example of a chain with 3 levels, for an input graph G 0 .

Compressive Haar transforms on chain For each layer of the chain, we will have a feature representation. We define these in terms of the Haar basis. Haar basis represents graph-structured data by low and high frequency Haar coefficients in frequency domain. The low frequency coefficients con-

a b c d e f g h G 0 a b c d e f g h G 1 a b c d e f g h G 2

Figure 3 : A coarse-grained chain of graphs, where the input has 8 nodes, the second level has 3 nodes, and the top level has single node.

tain the coarse information of the original data while the high frequency coefficients contain the fine details. In the HaarPooing, the data is pooled (or compressed) by discarding fine detail information.

The Haar basis can be compressed in each layer. Consider a chain where at level j the two subsequent graphs have N j+1 and N j nodes, N j+1 < N j . For each of these graphs, we can create a Haar basis with N j+1 and N j elements, respectively. The elements of the smaller layer are obtained by compressing a subset of the elements from the other layer. These new vectors form the matrix Φ j of size N j+1 × N j . We call Φ j compressive Haar basis matrix for this particular jth layer. This then defines the compressive Haar transform Φ T j X in for feature X in with size N j × d.

Computational strategy of HaarPooling:

The HaarPooling is then defined as follows.

Definition 1 (HaarPooling). The HaarPooling for a graph neural network with K pooling layers is defined as

X out j = Φ T j X in j , j = 0, 1, . . . , K -1, where N j > N j+1 and N K = 1, Φ j or Φ (j)

Nj ×Nj+1 is the N j × N j+1 compressive Haar basis matrix for the jth layer, X in j ∈ R Nj ×dj is the input feature array, and X out j ∈ R Nj+1×dj is the output feature array. The corresponding layer is called HaarPooling layer.

HaarPooling has following key properties.

• The HaarPooling reduces layer by layer the first dimension of input feature. In the last pooling layer, the output feature is compressed as a vector with length d K-1 and each original input sample would generate such a vector with the same length. This then makes it possible to deal with input graph-structured data with different size and structure. • The HaarPooling uses the sparse Haar representation on chain structure. In each HaarPooling layer, the representation then combines the features of input X in j with the geometric information of the graphs of the jth and (j + 1)th layers of the chain.

• By the property of Haar basis, the HaarPooling only drops the high frequency (or detailed) information of the input data. The X out j has good approximation to X in j . Thus, the major data information (i.e. the low frequency coefficients) is preserved in the pooling, and the loss of the information is small. • Since the Haar basis matrix is very sparse, HaarPooling can be computed very fast, with near linear computational complexity.

Example Figure 4 shows the computational details of the HaarPooling associated with the chain from Figure 3 . There are two HaarPooling layers. In the first layer, the input X in 1 with size 8 × d 1 is transformed by the compressive Haar basis matrix Φ 8×3 has only up to three different values. This bound is exactly the number of nodes of G 1 . For each column φ (0) , all nodes with the same parent take the same value. Similarly, the 3 × 1 vector φ

(1)

1 is constant. This means that the HaarPooling 

8×3 with size 8 × 3 formed by the first three column vectors, and the output is a feature array with size 3 × d 1 ; in the second layer X in 2 = (y i,j ) ∈ R 3×d2 is transformed by the first column vector Φ

(1)

3×1 and the output is a feature vector with size 1 × d 2 . In the plots of Haar basis matrix, the colors indicate the value of the entries of the Haar basis matrix.

synthesizes the node feature by adding the same weight to the nodes that are in the same cluster of the coarser layer, and in this way, pools the feature using the graph clustering information.

4. MATHEMATICS AND COMPUTATION FOR HAARPOOLING:

Chain of graphs by clustering For a graph G = (V, E, w), where V, E, w are the vertices, edges, and weights on edges, a graph

G cg := (V cg , E cg , w cg ) is a coarse-grained graph of G if |V cg | ≤ |V | and each node of G has only one parent node in G cg associated with it. Each node of G cg is called a cluster of G. For integers J > 0, a coarse-grained chain for G is a sequence of graphs G 0→J := (G 0 , G 1 , . . . , G J ) with G 0 = G and such that G j+1 is a coarse-grained graph of G j = (V j , E j , w j )

for each j = 0, 1, . . . , J -1, and G J has only one node. Here, we call the graph G J the top level or the coarsest level and G 0 the bottom level or the finest level. The chain G 0→J hierarchically coarsens graph G. We use the notation J + 1 for the number of layers of the chain to distinguish the number K of layers for pooling. The chain for graph G can be created by any clustering method. For details about graphs and chains, we refer the reader to the examples by Chung & Graham (1997); Hammond et al. (2011) ; Chui et al. (2015; 2018) ; Wang & Zhuang (2018; 2019) .

4.1. COMPRESSIVE HAAR TRANSFORMS:



Haar basis:

The construction of Haar basis is rooted in the theory of Haar wavelet basis which was first introduced by Haar (1910) . It is a special example of the more general Daubechies wavelets (Daubechies, 1992) . Haar basis is later constructed on graph by Belkin et al. (2006) , and also Chui et al. (2015) ; Wang & Zhuang (2018; 2019) . The construction of the Haar basis is based on a chain of the graph. If the topology of the graph is well reflected by the clustering of the chain, then the Haar basis contains the crucial geometric information of the graph. For a chain G 0→J , on the jth-layer graph G j , j = 0, . . . , J, there is a Haar orthogonal basis {φ (j) } Nj =0 defined on G j , where N j is the size of G j and N j+1 < N j for j = 0, . . . , J -1. Suppose two consecutive layers j, j + 1. The first N j+1 members of φ (j) , = 1, . . . , N j+1 , are defined on the finer layer j + 1, and can be reduced into the φ (j+1) , = 1, . . . , N j+1 , as follows. For first = 1, . . . , N j+1 ,

φ (j) (v) = φ (j+1) (P a G (v))/ |P a G (v)|, i.e. the value of the φ (j) (v) is equal to the scaled φ (j+1)

at the parent P a G (v) of v and the scaled factor is one on square root of the number of nodes in the cluster which v lies in. It means that φ (j) (v) for v sharing the parent have the same value. This property is critical to pooling as φ (j) (v) can then be treated as weights for the graph G j on which the input feature defined, and the nodes gain the same weight if they are in the same cluster. On the other hand, the remaining Haar basis vectors φ (j) for = N j+1 +1, . . . , N j are constructed to reflect the high-frequency information in the Haar wavelet decomposition. This property is exploited by the compressive Haar basis which then pools the input feature into a lower (first) dimension output feature. The construction and its pseudo-codes for algorithmic implementation of the full Haar basis is detailed in Li et al. (2019) ; Wang & Zhuang ( 2019), which we also attach in the appendix. Let {φ (j) } Nj =1 , j = 0, . . . , J, be the sequence of Haar bases associated with the layers of chain G 0→J of a graph G. For j = 0, . . . , J, we let the matrix Φ j = (φ

(j) 1 , . . . , φ (j)

Nj ) ∈ R Nj ×Nj and call the matrix Φ j Haar transform matrix for layer j.

Orthogonality For each level j = 0, . . . , J, the sequence {φ (j) } Nj =1 , with N j := |V j |, is an orthonormal basis for the space l 2 (G j ) of square-summable sequences on the graph G j , so that (φ

(j) ) T φ (j) = δ , . For each j, {φ (j) } Nj =1

is the Haar basis system for the chain G j→J .

Locality Let G 0→J be a coarse-grained chain for G. If each parent of level G j , j = 1, . . . , J, contains at least two children, the number of different scalar values of the components of a Haar basis vector φ (j) , = 1, . . . , N j , is bounded by a constant independent of j.

In Figure 4 , the Haar basis is created based on the coarse-grained chain

G 0→2 := (G 0 , G 1 , G 2 ),

where G 0 , G 1 , G 2 are graphs with 8, 3, 1 nodes. The two colorful matrices show two Haar bases for the layers 0 and 1 in the chain G 0→2 . There are in total 8 vectors of the Haar basis for G 0 each with length 8, and 3 vectors of the Haar basis for G 1 each with length 3. Haar basis matrix for each level of the chain has up to 3 different values in each column as indicated by colors in each matrix. For j = 0, 1, each node of G j is a cluster of nodes in G j+1 . Each column of the matrix is a member of the Haar basis on the individual layer of the chain. The first three column vectors of Φ 1 can be reduced as an orthonormal basis of G 1 and the first column vector of G 1 can be compressed to the constant basis for G 2 . This connection ensures that the compressive Haar transform for HaarPooling is feasible and would allow fast algorithms of HaarPooling (see Section 4.2 below).

Adjoint and forward Haar transforms:

We use adjoint Haar transforms for HaarPooling, which as the sparsity of the Haar basis matrix, the transform is fast implementable. The adjoint Haar transform for the signal f on G j is defined as

EQUATION

and the forward Haar transform for (coefficients) vector c := (c 1 , . . . , c Nj ) ∈ R Nj .

EQUATION

We call the components of ( Φ j ) T f the Haar (wavelet) coefficients for f . The adjoint Haar transform represents the signal in Haar wavelet domain by computing the Haar coefficients for graph signal.

Here the adjoint and forward Haar transforms can be extended to a feature data with size N j × d j by replacing the column vector f by the feature array. Proposition 2. The adjoint and forward Haar Transforms are invertible in that for j = 0, . . . , J and vector f on graph G j , f = Φ j ( Φ j ) T f.

Proposition 2 shows that the forward Haar transform can recover the graph signal f from the adjoint Haar transform ( Φ j ) T f . This means that adjoint and forward Haar transforms have zero-loss in graph signal transmission.

Compressive Haar transforms Now for a graph neural network, suppose we want to use K pooling layers. We associate the chain G 0→K of an input graph with the pooling by linking the jth layer of pooling with the jth layer of the chain. Then, we can use the Haar basis system on the chain to define the pooling operation. By the property of Haar basis, in the Haar transforms for layer j, 0 ≤ j ≤ K -1, of the N j Haar coefficients, the first N j+1 coefficients are low-frequency coefficients, which reflect the approximation to the original data, and the other (N j -N j+1 ) coefficients are in high frequency, which contain fine details of the Haar wavelet decomposition. To define pooling, we remove the high-frequency coefficients in Haar wavelet representation and obtain the compressive Haar transforms for the feature X in j at layers j = 0, . . . , K -1, which then gives the HaarPooling in Definition 1.

As shown in the following formula, the compressive Haar transform synthesizes the neighbourhood information of the signal f as compared to the full Haar transform. Thus, HaarPooling takes the average information of the data f over nodes in the same cluster. 

EQUATION

4.2. FAST COMPUTATION OF HAARPOOLING:

For the HaarPooling introduced in Definition 1, we can develop a fast computational strategy by virtue of fast adjoint Haar transforms. Let G 0→K be a coarse-grained chain of the graph G 0 . For convenience, we label the vertices of the level-j graph G j by V j := v

EQUATION

Nj .

Fast algorithm for HaarPooling The HaarPooling in equation 3 can be computed fast by using the hierarchical structure of the chain, as we introduce as follows. For j = 1, . . . , K, let c

(j)

k be the number of children of v (j) k , i.e. the number of vertices of G j-1 which belongs to the cluster v (j) k , for k = 1, . . . , N j . For j = 0, we let c (0) k ≡ 1 for k = 1, . . . , N 0 . Now, for j = 0, . . . , K and k = 1, . . . , N j , define the weight for the node v k | j = 0, . . . , K, k = 1, . . . , N j }. Then, for j = 0, . . . , K, the weighted chain (G j→K , W j→K ) becomes a filtration if each parent of the chain G j→K has at least two children. See e.g. (Chui et al., 2015, Definition 2.3) .

Let j = 0, . . . , K. For the jth HaarPooling layer, let {φ (j) } Nj =1 be the Haar basis for the jth layer, which we also call the Haar basis for the filtration (G j→K , W j→K ) of a graph G. For k = 1, . . . , N j , we let X(v

(j) k ) = X(v (j) k , •) ∈ R dj the feature vector at node v (j)

k . We define the weighted sum for feature X ∈ R Nj ×dj for d j ≥ 1 by

EQUATION

Algorithm 1: Fast HaarPooling for One Layer

Input: Input feature X in j for the jth pooling layer given j = 0, . . . , K -1 in a GNN with total K HaarPooling layers; the chain G j→K associated with the HaarPooling; numbers N i of nodes for layers i = j, . . . , K. Output: Φ T j X in j from Definition 1.

Step 1: Evaluate the sums for i = j, . . . , K recursively, using equation 7 and equation 8:

S (i) X in j , v (i) k ∀v (i) k ∈ V i . Step 2: for = 1 to N j+1 do Set N K = 0. Compute i such that N i+1 + 1 ≤ ≤ N i . Evaluate Ni k=1 S (i) (X in j , v (i) k )w (i) k φ (i) (v (i)

k ) in equation 9 by the two steps: (a) Compute the product for all v

EQUATION

k ). end for and recursively, for i = j + 1, . . . , K and v

EQUATION

For each vertex v

(i) k of G i , the S (i) X, v (i) k

is the weighted sum of the S (i-1) X, v

(i-1) k at the level i -1 for those vertices v (i-1) k of G i-1 whose parent is v (i) k . Theorem 3. For 0 ≤ j ≤ K -1, let {φ (i) } Ni

=1 for i = j + 1, . . . , K be the Haar bases for the filtration (G j→K , W j→K ) at layer i. Then, the compressive Haar transform for the jth HaarPooling layer can be computed by, for the feature X ∈ R Nj ×dj and = 1, . . . , N j ,

EQUATION

)

where i is the largest possible number in {j + 1, . . . , K} such that φ (i) is the th member of the orthonormal basis {φ

EQUATION

k are the vertices of G i and the weights w

(i)

k are given by equation 12.

We give the algorithmic implementation of Theorem 3 in Algorithm 1, which provides a fast algorithm for HaarPooling at each layer.

Computational complexity With increasing graph size, the sparsity of the Haar basis matrix Φ j becomes more pronounced (Li et al., 2019) . This sparsity implies fast computation for HaarPooling. The computational complexity of HaarPooling is determined by the adjoint Haar transforms. In the first step of Algorithm 1, the total number of summations for all elements of Step 1 is no more than j-1 i=0 N i+1 ; In the second step, by the locality of the Haar basis, the total number of multiplication and summation operations is at most 2

Nj =1 C = O(N j ).

Here C is the constant which bounds the number of different values of the Haar basis vector. Thus, the computational cost of Algorithm 1 is O(N j ).

We run an experiment to evaluate the CPU computational time of HaarPooling by Algorithm 1 against the direct matrix product. We use randomly generated graphs and features with size ranging from 2 to 5000. As shown in Figure 5 , the fast HaarPooling has computational cost nearly proportional to the number of nodes N , while the ordinary matrix product incurs a cost close to order O(N 2 ). These results are consistent with the computational complexity analysis given above. 

5. EXPERIMENTS:

Data sets To verify whether the proposed framework can hierarchically learn good graph representations for classification, we evaluate HaarPooling on five widely used benchmark data sets for graph classification (Kersting et al., 2016) , including one protein graph data set PROTEINS (Borgwardt et al., 2005; Dobson & Doig, 2003) ; two mutagen data sets MUTAG (Debnath et al., 1991; Kriege & Mutzel, 2012) and MUTAGEN (Riesen & Bunke, 2008; Kazius et al., 2005) (full name Mutagenicity); and two data sets that consist of chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines, NCI1 and NCI109 (Wale et al., 2008) . We include data sets from different domains, sample and graph sizes to give a comprehensive understanding of how HaarPooling performs with data sets in various scenarios. A summary information of the data sets is given in Table 1 , which shows the data sets containing graphs with different sizes and structures: the number of data samples ranges from 188 to 4,337, the average number of nodes is from 17.93 to 39.06 and the average number of edges is from 19.79 to 72.82. Baselines and running environment We compare HaarPool with SortPool (Zhang et al., 2018a) , DiffPool (Ying et al., 2018) , gPool (Gao & Ji, 2019) , SAGPool (Lee et al., 2019) , EigenPool (Ma et al., 2019a) , CSM (Kriege & Mutzel, 2012) and GIN (Xu et al., 2019) on the above data sets. The experiments use PyTorch Geometric1 (Fey & Lenssen, 2019) and were run in Google Cloud using 4 Nvidia Telsa T4 with 2560 CUDA cores, compute 7.5, 16GB GDDR6 VRAM.

Training procedures:

In experiments, we use a GNN with at most 3 GCN (Kipf & Welling, 2017) convolutional layers plus one HaarPooling layer, followed by three fully connected layers. The hyperparameters of the network are adjusted case by case. We use spectral clustering, which exploits the eigenvalues of the graph Laplacian, to generate a chain with the number of layers given. Spectral clustering has shown good performance in coarsening a variety of data patterns and can handle isolated nodes.

We use random shuffling of the data set, which we split into training, validation, and test sets with proportions 80%, 10% and 10% respectively. We use the Adam optimizer (Kingma & Ba, 2015) , early stopping criterion, patience. The specific values are provided in the appendix. The early stopping criterion was that the validation loss does not improve for 50 epochs, with a maximum of 150 epochs, as suggested by Shchur et al. (2018) .

Results:

The classification test accuracy is reported in Table 6 . GNNs with HaarPooling have excellent performance on all data sets. In 4 out of 5 datasets, it achieved top accuracy. This shows that HaarPooling with appropriate graph convolution, can achieve top performance on a variety of graph classification tasks, and in some cases improve state of the art by a few percent points. '*' means that the records are retrieved from EigenPool (Ma et al., 2019a) , '-' means that there is no public records for the corresponding method on the data set, and the bold number indicates the best performance in the list.

6. CONCLUSION:

We introduced a new graph pooling method called HaarPooling. HaarPooling has a mathematical formalism derived from compressive Haar transforms. Unlike existing graph pooling methods, HaarPooling takes into account both the graph structure and also the features over the nodes of the graph-structured input data, to compute a coarsened representation. As an individual unit, Haar-Pooling can be applied in conjunction with any type of graph convolution in GNNs. We show in experiments that HaarPooling reaches state of the art in several benchmark graph classification tasks. Moreover, having only linear computational complexity in the size of the inputs, HaarPooling is a very fast pooling method.

A GRAPH CLASSIFICATION:

Graph classification This task is to categorize graph-structured data into several classes. The training set consists of M pairs of samples

(x i , G i ), y i , i = 1, . . . , M . For the ith sample, G i = (V i , E i , W i ) is a graph with vertex set V i of size |V i | = N i (

also called nodes), and edge set E i with weights W i . The feature x i ∈ R Ni×d is an array of d features per vertex, i.e., an R d -valued function over V i . The label y i is an integer from a finite set indicating which class the input sample (x i , G i ) lies in. The number of nodes N i and the graph structure E i , W i usually vary over the different input samples.

Graph neural networks Deep graph neural networks (GNNs) are designed to work with graphstructured inputs of the form (x i , G i ) described above. A GNN is typically composed of multiple graph convolution layers, graph pooling layers, and fully connected layers. A (graph) convolutional layer extracts an array of features from the previous array. It changes the dimension d of the feature array but does not change the number of nodes N i . Since the number of nodes of different inputs is variable, the number of nodes of the corresponding outputs is also variable. This raises new challenges in comparison with traditional image classification tasks, where the local structure connecting pixels is always fixed (even if the number of pixels might be variable).

Graph pooling:

In GNNs, one uses graph pooling to reduce the first dimension N of the feature arrays, and more importantly, to obtain outputs of uniform dimension (commonly followed by fully connected layers). A general architecture uses a cascade of convolutional and pooling layers. Figure 2 illustrates such an architecture with three blocks of graph convolutional and pooling layers, followed by a multi-layer perceptron (MLP) with three fully connected layers. In practice, each block can include several convolutional layers but use only one pooling layer at most. The exact architecture of GNNs with combined convolutional and pooling layers is mainly dependent upon the particular problem and the data set and is designed case by case.

B CONSTRUCTION OF HAAR BASIS:

Construction of Haar basis. With a chain of the graph, one can generate a Haar basis for l 2 (G) following Chui et al. (2015) , see also Gavish et al. (2010) . We show the construction of Haar basis on G, as follows.

Step 1. Let G cg = (V cg , E cg , w cg ) be a coarse-grained graph of G = (V, E, w) with

N cg := |V cg |. Each vertex v cg ∈ V cg is a cluster v cg = {v ∈ V | v has parent v cg } of G.

Order V cg , e.g., by degrees of vertices or weights of vertices, as V cg = {v cg 1 , . . . , v cg N cg }. We define N cg vectors φ cg on G cg by

EQUATION

and for = 2, . . . , N cg ,

EQUATION

where χ cg j is the indicator function for the jth vertex v cg j ∈ V cg on G given by

χ cg j (v cg ) := 1, v cg = v cg j , 0, v cg ∈ V cg \{v cg j }.

Then, one can show that {φ cg } N cg =1 forms an orthonormal basis for l 2 (G cg ). Note that each v ∈ V belongs to exactly one cluster v cg ∈ V cg . In view of this, for each = 1, . . . , N cg , we can extend the vector φ cg on G cg to a vector φ ,1 on G by

φ ,1 (v) := φ cg (v cg ) |v cg | , v ∈ v cg ,

here |v cg | := k is the size of the cluster v cg , i.e., the number of vertices in G whose common parent is v cg . We order the cluster v cg , e.g., by degrees of vertices, as

v cg = {v ,1 , . . . , v ,k } ⊆ V.

For k = 2, . . . , k , similar to equation 11, define

φ ,k = k -k + 1 k -k + 2 χ ,k-1 - k j=k χ ,j k -k + 1

.

where for j = 1, . . . , k , χ ,j is given by

χ ,j (v) := 1, v = v ,j , 0, v ∈ V \{v ,j }.

One can show that the resulting {φ ,k : = 1, . . . , N cg , k = 1, . . . , k } is an orthonormal basis for l 2 (G).

Step 2. Let G 0→J be a coarse-grained chain for the graph G. An orthonormal basis {φ (J) } N J

=1:

for l 2 (G J ) is generated using equation 10 and equation 11. We then repeatedly use Step 1: for j = 0, . . . , J -1, we generate an orthonormal basis {φ (j) } Nj =1 for l 2 (G j ) from the orthonormal basis {φ (j+1) } Nj+1 =1 for the coarse-grained graph G j+1 that was derived in the previous steps. We call the sequence {φ := φ (0) } N0 =1 of vectors at the finest level, the Haar global orthonormal basis or simply the Haar basis for G associated with the chain G 0→J . The orthonormal basis {φ

(j) } Nj =1

for l 2 (G j ), j = 1, . . . , J is called the associated (orthonormal) basis for the Haar basis {φ } N =1 . Besides the orthogonality, the Haar basis has the locality which is critical to the fast computation of HaarPooling. 

Compressive Haar basis:



C FAST COMPUTATION FOR HAARPOOLING:

Let G 0→K be a coarse-grained chain of the graph G 0 . For convenience, we label the vertices of the level-j graph G j by V

EQUATION

Nj .

Fast algorithm for HaarPooling The HaarPooling in equation 3 can be computed fast by using the hierarchical structure of the chain, as we introduce as follows. For j = 1, . . . , K, let c (j) k be the number of children of v (j) k , i.e. the number of vertices of G j-1 which belongs to the cluster v (j) k , for k = 1, . . . , N j . For j = 0, we let c (0) k ≡ 1 for k = 1, . . . , N 0 . Now, for j = 0, . . . , K and k = 1, . . . , N j , define the weight for the node v k | j = 0, . . . , K, k = 1, . . . , N j }. Then, for j = 0, . . . , K, the weighted chain (G j→K , W j→K ) becomes a filtration if each parent of the chain G j→K has at least two children. See e.g. (Chui et al., 2015, Definition 2.3 ).

D PROOFS:

Proof for equation 5. We only need to prove the first formula. The second is obtained by definition. To simplify notation, we let f = X in j . By construction of Haar basis, for some layer j, the first N j+1 basis vectors

φ (j) (v) = φ (j+1) (p)/ |P a G (v)|, for p = P a G (v).

Then, the Fourier coefficient of f for the th basis vector is the inner product f, φ

EQUATION

where we have let

f (p) := 1 |P a G (v)| p=P a G (v) f (v).

This then gives:

EQUATION

)

Since {φ }

Nj+1:

=1 forms an orthonormal basis on 2 (G j+1 ),

EQUATION

j+1) 2 = f 2 = p∈Gj+1 f (p) 2 = p∈Gj+1 1 |P a G (v)| p=P a G (v) f (v) 2 .

This proves the left formula in equation 5.

Proof of Theorem 3. By the relation between φ (i) and φ (j) , for i = j + 1, . . . , K and = 1, . . . , N j+1 ,

Φ T j X = Nj k=1 X(v (j) k )φ (j) (v (j) k ) = Nj+1 k =1    P a G (v (j) k )=v (j+1) k X(v (j) k )    w (j+1) k φ (j+1) (v (j+1) k ) = Nj+1 k =1 S (j+1) (X, v (j+1) k )w (j+1) k φ (j+1) (v (j+1) k ) = Nj+2 k =1    P a G (v (j+1) k )=v (j+2) k S (j+1) (X, v (j+1) k )w (j+1) k    w (j+2) k φ (j+2) (v (j+2) k ) = Nj+2 k =1 S (j+2) (X, v (j+2) k )w (j+2) k φ (j+2) (v (j+2) k ) • • • • • • = Ni k=1 S (i) (X, v (i) k )w (i) k φ (i) (v (i) k ), where v (j+1) k is the parent of v (j) k and v (j+2) k is the parent of v (j+1) k

, and we recursively compute the summation to obtain the last equality, thus completing the proof.

E EXPERIMENTAL SETTING:

The architecture of GNN is identified by the layer type and the number of hidden nodes at each layer. For example, we denote 3GC256-HP-2FC256-FC128 to represent a GNN architecture with 3 GCNConv layers each with 256 hidden nodes plus one HaarPooling layer followed by 2 fully connected layers each with 256 hidden nodes and 1 fully connected layer with 128 hidden nodes. The architecture for each data set is shown by Table 3 .

The hyperparameters include batch size; learning rate, weight decay rate (these two for optimization); maximum number of epochs; patience for early stopping. The choice of hyperparameters in each data set is shown in Table 4 . 

:

https://pytorch-geometric.readthedocs.io/en/latest.

Figures and Tables:

Haar basis vector. By applyingHaarPooling in equation 2, the number of nodes is compressed from N to N 1 . The Haar basis provides a sparse representation which distills graph structural information. Cascading pooling layers we can obtain an output of a fixed dimension, regardless of the size of the inputs. The sparsity of the Haar basis matrix ensures that the computation of HaarPooling is efficient. Generating the Haar basis and computing the Haar transform has a computational cost O(N ) (up to a log term of N ) for input graphs with N nodes. Experiments in Section 5 demonstrate that GNNs with HaarPooling achieve state-of-the-art performance on various graph classification tasks.

of the first three column vectors of the full Haar basis Φ (0) 8×8 in (a), and output is a 3 × d 1 matrix X out 1 . In the second layer, the input X in 2 with size 3 × d 2 (usually X out 1 followed by convolution) is transformed by the compressive Haar matrix Φ (1) 3×1 which is the first column vector of the full Haar basis matrix Φ (1) 3×3 in (b). By the construction of the Haar basis in relation to the chain (details in Appendix B), each of the first three column vectors φ

Figure 4: Computational strategy of HaarPooling. We use the chain in Figure 3 and then there are two HaarPooling layers in the network from G 0 → G 1 and G 1 → G 2 respectively. The input of each layer is pooled by the compressive Haar transform for each layer: in the first layer input X in 1 = (x i,j ) ∈ R 8×d1 is transformed by the compressive Haar basis matrix Φ

)where Φ j is the full Haar basis matrix at the jth layer and |P a G (v)| means the number of nodes in the cluster which v lies in. Here, in the first equation, 1/ |P a G (v)| can be taken out of summation as P a(v) is in fact a set of nodes. We show the derivation of formula in equation 5 in Appendix D.In HaarPooling, the compression or pooling occurs in the Haar wavelet domain. HaarPooling transforms the features on the nodes to the Haar wavelet domain and discards the high-frequency coefficients in the sparse Haar wavelet representation. Figure4shows a two-layer HaarPooling strategy. The first layer pools the input X in 0 by the compressive Haar basis matrix Φ

Figure 5: Comparison for fast computation and direct matrix product for HaarPooling for input feature array with up to 5000 nodes. The cost of HaarPooling has near linear computational complexity. The cost of direct matrix product grows at O(N 2.1 ).

Suppose we have constructed the (full) Haar basis {φ (j) } Nj =0 for each layer G j of the chain G 0→K . The compressive Haar basis for layer j is {φ (j) } Nj+1 =0 .

Summary statistics of the data sets used in our experiments

Table content: <table><tr><td>Data Set</td><td>MUTAG</td><td>PROTEINS</td><td>NCI1</td><td>NCI109</td><td>MUTAGEN</td></tr><tr><td>max #nodes</td><td>28</td><td>620</td><td>111</td><td>111</td><td>417</td></tr><tr><td>min #nodes</td><td>10</td><td>4</td><td>3</td><td>4</td><td>4</td></tr><tr><td>avg #nodes</td><td>17.93</td><td>39.06</td><td>29.87</td><td>29.68</td><td>30.32</td></tr><tr><td>avg #edges</td><td>19.79</td><td>72.82</td><td>32.30</td><td>32.13</td><td>30.77</td></tr><tr><td>#graphs</td><td>188</td><td>1,113</td><td>4,110</td><td>4,127</td><td>4,337</td></tr><tr><td>#classes</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr></table>

Performance comparison for graph classification tasks (test accuracy in percent, showing the standard deviation over 10 repetitions of the experiment).

Table content: <table><tr><td>Method</td><td>MUTAG</td><td>PROTEINS</td><td>NCI1</td><td>NCI109</td><td>MUTAGEN</td></tr><tr><td>CSM</td><td>85.4</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>GIN</td><td>89.4</td><td>76.2</td><td>82.7</td><td>-</td><td>-</td></tr><tr><td>SortPool</td><td>85.8</td><td>75.5</td><td>74.4</td><td>72.3*</td><td>78.8*</td></tr><tr><td>DiffPool</td><td>-</td><td>76.3</td><td>76.0*</td><td>74.1*</td><td>80.6*</td></tr><tr><td>gPool</td><td>-</td><td>77.7</td><td>-</td><td>-</td><td>-</td></tr><tr><td>SAGPool</td><td>-</td><td>72.1</td><td>74.2</td><td>74.1</td><td>-</td></tr><tr><td>EigenPool</td><td>-</td><td>76.6</td><td>77.0</td><td>74.9</td><td>79.5</td></tr><tr><td>HaarPool</td><td>90.0±3.6</td><td>80.4±1.8</td><td>78.6±0.5</td><td>75.6±1.2</td><td>80.9±1.5</td></tr></table>

Network architecture GNN WITH HAARPOOLING ON TRIANGLESWe test GNN with HaarPooling on graph data set Triangles(Knyazev et al., 2019). Triangles is a 10 classification problem with 45000 graphs. The average numbers of nodes and edges of graphs are

Table content: <table><tr><td>Data Set</td><td>Layers and #Hidden Nodes</td></tr><tr><td>MUTAG</td><td>GC60-HP-FC60-FC180-FC60</td></tr><tr><td>PROTEINS</td><td>2GC128-HP-2GC128-HP-2GC128-HP-GC128-2FC128-FC64</td></tr><tr><td>NCI1</td><td>2GC256-HP-FC256-FC1024-FC2048</td></tr><tr><td>NCI109</td><td>3GC256-HP-2FC256-FC128</td></tr><tr><td>MUTAGEN</td><td>3GC256-HP-2FC256-FC128</td></tr></table>

Hyperparameter setting 20.85 and 32.74 respectively. In the experiments, the network uses GIN convolution(Xu et al., 2019) as graph convolution and with HaarPooling or SAGPooling(Lee et al., 2019). With SAGPooling, the network architecture uses two combined layers of GIN convolution and SAGPooling followed by combined layers of GIN convolution and global max pooling, denoted by GIN-SP-GIN-SP-GIN-MP, where SP means the SAGPooling and MP means global max pooling. With HaarPooling, we test with two architectures: GIN-HP-GIN-HP-GIN-MP and GIN-HP-GIN-GIN-MP, where HP means HaarPooling. The data for training, validation and test are 35000, 5000 and 10000 respectively. The hidden nodes in convoluational layers is 64, batch size is 60 and learning rate is 0.001.Table5shows the test accuracy of the three networks. It illustrates that both networks with Haar-Pooling outperform that with the SAGPooling.

Table content: <table><tr><td>Data Set</td><td>MUTAG</td><td>PROTEINS</td><td>NCI1</td><td>NCI109</td><td>MUTAGEN</td></tr><tr><td>batch size</td><td>60</td><td>50</td><td>100</td><td>100</td><td>100</td></tr><tr><td>max #epochs</td><td>30</td><td>20</td><td>150</td><td>150</td><td>50</td></tr><tr><td>early stopping</td><td>15</td><td>20</td><td>50</td><td>50</td><td>50</td></tr><tr><td>learning rate</td><td>0.01</td><td>0.001</td><td>0.001</td><td>0.01</td><td>0.01</td></tr><tr><td>weight decay</td><td>0.0005</td><td>0.0005</td><td>0.0005</td><td>0.0001</td><td>0.0005</td></tr></table>

Training, validation and test accuracies on TrianglesHere we provide a comparison of the properties of HaarPooling with existing pooling methods. The properties in comparison includes time complexity and space complexity, and whether involving the clustering, hierarchical pooling (which is then not a global pooling), spectral-based, node feature or graph structure and sparse representation. We compare HaarPooling (denoted by HaarPool in the table) to other methods (SortPool, DiffPool, gPool, SAGPool and EigenPool). The SortPool (i.e. Sort-Pooling) is a global pooling which uses node signature (i.e. Weisfeiler-Lehman color of vertex) sorts all vertices by the values of the channels of the input data. Thus, the time complexity (worst case) of SortPool is O(|V | 2 ) and space complexity is O(|V |). Other pooling methods are all hierarchical pooling. DiffPool and gPool both use the node feature and have time complexity O(|V | 2 ) The Diff-Pool learns the assignment matrices in end-to-end manner and has space complexity O(k|V | 2 ) for pooling ratio k. The gPool projects all nodes to a learnable vector to generate scores for nodes, and then sorts the nodes by the projection scores; the space complexity is O(|V | + |E|). SAGPool uses the graph convolution to calculate the attention scores of nodes and then selects top ranked nodes for pooling. The time complexity of SAGPool is O(|E|) and the space complexity is O(|V | + |E|) due to the sparsity of the pooling matrix. EigenPool, which considers both the node feature and graph structure, uses the eigedecomposition of subgraphs (from clustering) of the input graph, and pools the input data by Fourier transforms of the assembled basis matrix. Due to eigendecomposition, the time complexity of EigenPool is O(|V | 2 ) and space complexity is O(|V | 2 ). HaarPool which uses the sparse representation of data by compressive Haar basis has linear time complexity O(|V |) (up to a log |V | term), and the space complexity is O(|V | 2 ), where is the sparsity of the compressive Haar transform matrix and is usually very small. From the table, we can observe the HaarPool is the

Table content: <table><tr><td>Architecture</td><td>Training</td><td>Accuracy (%) Validation</td><td>Test</td></tr><tr><td>GIN-SP-GIN-SP-GIN-MP</td><td>45.6</td><td>45.3</td><td>44.0</td></tr><tr><td>GIN-HP-GIN-HP-GIN-MP</td><td>47.5</td><td>46.3</td><td>46.1</td></tr><tr><td>GIN-HP-GIN-GIN-MP</td><td>47.3</td><td>45.8</td><td>45.5</td></tr><tr><td colspan="3">G PROPERTY COMPARISON OF POOLING METHODS</td><td/></tr></table>

Peer review (iclr2020):
The paper presents a new approach called HaarPooling in the context of Deep Graph Neural Networks. The approach solves dmiensional problems of applying the same model on graphs of different size and shows how to contribute to high performance in a set of graph classification tasks, while having low computational complexity. The paper is very well written. The authors describe the concept of HaarPooling in a very detailed way and show the mathematical foundation of their approach. They further provide detailed mathematical explanations and proofs for the claimed advantages of their method, whilst using descriptive examples to ease understanding. The use of HaarPooling is then tested on five different datasets, showing a very good performance on each of them. The description of the machine learning experiments is very detailed, i.e., the methodology seems reproducable. Minor Comments: - In Figure 3 it seems counter-intuitive that the Graphs are arranged down-top (0-->2), whilst the equations above are arranged top-down. - The Related Work section could be placed earlier in the paper to get a better overview of the context and the problems that HaarPooling tries to solve. - All the experiments use exactly one HaarPool layer. Would it be possible to use multiple HaarPool layers, or is this not sensible or even possible (e.g. due to the dimensionality reduction). An explanation on this could be beneficial. - In Appendix A, weights are described with a capital *W*, which seems inconsistent with the lower case *w* used in the rest of the paper.