HaarPooling: Graph Pooling with Compressive Haar Basis
Authors: Yu Guang Wang
Ming Li
Zheng Ma
Guido Montufar
Xiaosheng Zhuang
Yanan Fan
Venue:  (2020)
Keywords: graph pooling
graph neural networks
tree
graph classification
graph regression
deep learning
Haar wavelet basis
fast Haar transforms

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 HaarPooling. HaarPooling is computed 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.

HAARPOOLING: GRAPH POOLING WITH COMPRES- SIVE HAAR BASIS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep Graph Neural Networks (GNNs) are instrumental in graph classification and graph-based regression tasks. In these tasks, graph pooling is 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 com- pressive Haar basis of the corresponding clustering. HaarPooling operates 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 convo- lution layers achieves state-of- of-the-art performance on diverse graph classification problems.
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. [017 Battaglia al., 2018 Zhang al. 2018b 8b Zhou al. 2018 Wu 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-an performance (Defferrard et al.) [016]] Kipf & Welling, 2017 Ma 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 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, instcad 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 [ 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 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 proper graph comvolution and graph pooling to allow GNNs to capture the geometric information of each data sample (Zhang et al.) 2018a Ying al.
2018 Cangea et al. 2018 Gao & Ji] 2019; Knyazev et al. 2019:) Ma et al. 2019a A Lee et al. 2019) Graph convolution plays important role especially in question 1).

---

MLP
GCNComv HearPPollin
GCNConu + HaarPooling
GCNConv HaarPooling
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 the number of input units of the MLP.
The following graph convolution, as proposed by Kipt & Welling (2017), is a widely accepted example:
Xout Axi"W.
(1)
Here À 2-D-1:2(++1)--12 N is normalized version of the adjacency matrix A of the input graph, where the identity matrix and 7) is the degree diagonal matrix for T. Further, X Rxxx is the array of d-dimensional features the N nodes of the graph, and W Rdxm is the filter parameter matrix. The graph convolution equation I 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 x does 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 al., 2019a) incorporates both features and graph structure. However, this is based eigenpairs of graph Laplacian and suffers from a high computational cost. We provide an overview this and other graph pooling methods Section
In this paper, we propose new graph pooling strategy based sparse Haar representation of the data, which we call HaarPooling. This is based on the Haar basis (Li et al., (019),, which incorporates graph structure and features, and is computationally efficient. Suppose we have input X e TR Nxxe xd HaarPooling is then defined as
you Xin
where NNN, N1 < N. Each column of compressive Haar basis vector. By applying
HaarPooling in equation 2 the number of nodes is compressed from N to N₁. The Haar basis provides 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 computational cost O(N) (up to log term of N) for input graphs with N nodes. Experiments Section 5 demonstrate that GNNs with HaarPooling achieve statc-of-the-ar performance various graph classification tasks.
This paper organized as follows. Section 2 gives an overview of existing work on graph pool- ing. Section 3 details the components and computational flow for HaarPooling. Section provides the mathematical details on HaarPooling, including the compressive Haar basis, compressive Haar transforms, and efficient implementations. Section Srrpporss experimental results on benchmark graph classification tasks compared with existing graph pooling methods. Section concludes the paper. Proofs and implementation details are deferred the appendix.
2

---

2
RELATED WORK
Graph pooling is a necessary step when building GNN model for graph classification, 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 graph coarsening proce- dure 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) ct al. (017)) uses the Ser2Set method (Vinyals et al., 2015) to obtain graph-level representations. Zhang et al. (2018a) proposed SortPool method that sorts feature representation of nodes before feeding them into traditional 1-D convolutional and dense layers. But these global pooling tech- niques 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/parameete classification tasks. Ying et al. (2018) proposed a differentiable pooling layer (DittPool) 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 cluster- ing assignments. Cangea al. ) Gao Ji (2019): (nyyaeev et al. (2019) used a Top-K pooling method that samples a subset of important nodes by employing trainable projection vector. [Lee] et al. (2019) introduced Self-Attention Graph Pooling (SAGPool) by replacing the way node scores computed in Top-K pooling by 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. (2199) proposed EdgePool which is a scheme which considers edge contraction and thus takes into account of graph structure in pooling.
which has brought substantial improvements on graph
There are also spectral-based 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 dynami- cally selects centroid nodes and their corresponding follower nodes by attention mechanism that uses the graph Laplacian. Ma et al. (2019) introduced HigenPool 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-basee 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 detine the pooling architecture in terms of a chain, i.e., a sequence of graphs (Go. ....... 9k), where the nodes of each Gj+1 correspond clusters of nodes of 9y+1. j 0, O..... 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 searse-rraieed graphs. In our chain, each graph is an induced graph that arises from grouping (clus- tering) certain subsets of nodes from the previous graph. We use clustering algorithms to generate the groupings of nodes. There are many good candidates, such spectral clustering (Shi & Malik 2000), k-means clustering (Pakhira 2014), DBSCAN (Ester et al., 1996). OPTICS (Ankerst et al. and METIS (Karypis & Kumar 1998). Any of these will work with HaarPooling.
1999
Figure
shows an example of a chain with 3 levels, for an input graph Go-
Compressive Haar transforms on chain For each layer of the chain, we will have feature repre- sentation. 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-
3

---

5
$1 Figure A coarse- soanse-rained chain of graphs, where the input has 8 nodes, the second level has 3 nodes, and the top level has single node.
b d
d
9
tain the coarse information of the original data while the high frequency coefficients contain the fine details. In the HaarPooing, the data pooled (or compressed) by discarding fine detail information.
The Haar basis can be compressed in each layer. Consider chain where at level j the two subse- quent graphs have N,+1 and N, nodes, Ny+1 < Ny.. For each of these graphs, basis with N1 and N, elements, respectively. The elements of the smaller layer are obtained by compressing subset of the elements from the other layer. These new vectors form the matrix & of size Nj+1 N,. We call 3 compressive Haar basis matrix for this particular jth layer. This then defines the compressive Haar transform T Xin for feature Xin with size N, x d.
create Haar
Computational strategy HaarPooling The HaarPooling is then defined as follows.
Definition (HaarPooling), The HaarPooling for graph neural network with K pooling layers is defined as
XTut D5 x == 0, 1..,,..,
where N₃ > N841 and NK = 1, 3 or ()) N is the N₂ x Njt1 compressive Haar basis matrix for the jth layer, X E N,d,, is the input feature array, and X E IR IR- Xdz, 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 vector with length dx-1 and each original input sample would generate such vector with the same length. This then makes it possible to deal with input graph-structured data with different size and structure.
The HaarPooling
the sparse Haar representation layer, the representation then combines the features of input X with the geometric information the graphs of the jth and (j + 1)th layers of the chain.
chain structure. In each HaarPooling
By the property of Haar basis, the HaarPooling only drops the high frequency (or detailed) in- formation of the input data. The X has good approximation to XJ". Thus, the major data information (i.e. the low frequency coefficients) is preserved 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 There are two HaarPooling layers. In the first layer, the input X]" with size 8 x di
transformed by the compressive Haar basis matrix & 8x3 which consists of the first three column vectors of the full Haar basis (0)
8x8 in (a), and output is 3 x d1 matrix Xput, In the second layer, the input Xin with size 3 x d2 (usually X followed by convolution) is transformed by the (1)
compressive Haar matrix Ø3x which is the first column vector of the full Haar basis matrix & 3xx in (b). By the construction of the Haar basis in relation the chain (details in Appendix B). each of
(0) and Øi of (0) has only up to three different values. This the first three column vectors ( 02
bound exactly the number nodes S1. For each column (((0) all nodes with the same parent take the same value. Similarly, the 3 x vector ( is constant. This means that the HaarPooling

---

X
(0)
8x3
21.1
21.4
22.4
23,1
x3
24.1
24.d
X1"
3x1
44.41
16,1
D1.1
27.1
27.41
3/2.1
.2
4
V1
Vile
2/21
...
22
X
(b) Second HaarPooling Layer G1 - G2
Xg
(a) First HaarPooling Layer for Gu + G1
Figure 4: Computational strategy of HaarPooling. We the chain in Figure and then there are two HaarPooling layers the network from Go + 9i and 9, + G2 respectively. The input of each layer is pooled by the compressive Haar transform for each layer: in the first layer input X = (xi,) E 8xdi transformed by the compressive Haar basis matrix &8x3 with size 8 x formed by the first three column vectors, and the output is feature array with size 3 x dj; in the second layer X (yt,)) E R 3xxd2 is transformed by the first column vector ( and the output a feature vector with size 1 d2. 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.
MATHEMATICS AND COMPUTATION FOR HAARPOOLING
Chain of graphs by clustering For graph G - (V, E, w.) where V, E, the vertices, edges, and weights on edges, a graph G = (Ve5 E w²8) is coarse- grriinee graph of G if [V<s] S [ and each node of G has only one parent node in gov associated with it. Each node of g is called a cluster of G. For integers J > 0. coarse- coarse-grained chain for G is a sequence of graphs Go+JJ == (Gn, 91, .. GT) with Go G and such that 9j+1 is coarse-gras garsenggaaiee graph of Gj = -V, Egj my for each the coarsest level and Go the bottom level or the finest level. The chain G0-+J hierarchically coarsens graph G. We use the notation J + 1 for the number of layers of the chain to distinguish the number K layers for pooling. The chain for graph can be created by any clustering method. For details
0.,...., J 1, and G. has only one node. Here, we call the graph G3 the top level or
about graphs and chains, refer the reader to the examples Chung & Graham (197]; 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 special example of the more general Daubechies wavelets (Daubechies) 1992). Haar basis is later constructed on graph by Belkin et al. (206)), and also (Cui al. (2015): Wang & Zhuang 2018 2019). The construction of the Haar basis based 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 Go-... on the jtherayer graph G,, j O, O....,J, there is a Haar orthogonal basis { 1 defined on Gj. where N, is the size of Gj and N,+1 N2 for j 0 O....,J 1. Suppose two consecutive
5

---

layers j 1. The first N3+1 members of 56 l _ ..... N3+1, are defined the finer layer
j + 1, and can be reduced into the of o()+1) - , NN51, as follows. For first = 1,... N4+1,
(v) is equal to the scaled of ( at the parent (e) of v and the scaled factor is one square root of the number of nodes in the cluster which v lies in. means that 266" (v) for v sharing the parent have the same value. This property is critical pooling as (v) can then be treated as weights for the graph 9j on which the input feature defined, and the nodes gain the same weight if they are in the same cluster. On the
(v) = of o (Pag (ong(())///eeel (V) i.c. the value of the (v)
other hand, the remaining Haar basis vectors o6 for E N 1,.... N2, are constructed reflect the
information in the Haar wavelet decomposition. This property is exploited by the compressive Haar basis which then pools the input feature into lower (first) dimension output feature. The construction and its pseudo-codes for algorithmic implementation of the full Haar basis detailed in [i et al. (2019); Wang & Zhuang (019)) which we also attach in the appendix. Let {or
(o()) It-1- j = O.....J. J. be the sequence of Haar bases associated with the layers of chain Go-.J of graph G. For j O, .,,,,,,......................... J, we let the matrix $ (of)
X,N, and call the matrix
T Haar transform matrix for layer j.
For each level j O,.....,, the sequence ( J with N, [V is an orthonormal basis for the space (2()) of square-summable sequences on the graph Gj. so that ( 0 =dg, For each j. (06)) N₂ is the Haar basis system for the chain 9j-J-
Orthogonality
)==1
Locality Let Go-L be a coarse-grained chain for G. If each parent of level 9j. I,...,J, contains at least two children, the number of different scalar values of the components of Haar basis vector (b 1= N,. is bounded by a constant independent of j.
In Figure 4 the Haar basis is created based on the coarse- guannee chain Go-2 == (Go. 9r, 92), where Go. 91. G2 are graphs with 8, 3, nodes. The two colorful matrices show two Haar bases for the layers and in the chain Go-2. There are total 8 vectors of the Haar basis for Go each with length 8, and 3 vectors of the Haar basis for Gi each with length 3. Haar basis matrix for each level of the chain has up to different values in each column as indicated by colors each matrix. For j 0, 1. each node of Gj is cluster of nodes in Gy-1- Each column of the matrix is member of the Haar basis on the individual layer of the chain. The first three column vectors of Φ can be reduced as an orthonormal basis of Gi and the first column vector of GI can be compressed to the constant basis for G2. 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 9j is defined as
E E ERN, BEV
(3)
V
and the forward Haar transform for (coefficients) vector c:= (cI, CN2) E RRN.
N, (t) = Σ 1 (1)c,, VEV.
(4)
t=1
We call the components of )T f the Haar (wavelett 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, x d, by replacing the column vector f by the feature array.
Proposition 2. and vector f on graph Gz.
The adjoint and forward Haar Transforms are invertible in that for O....,J
f = グ

---

Proposition shows that the forward Haar transform recover the graph signal f from the adjoint Haar transform (f,)² This means that adjoint and forward Haar transforms have zero-loss in graph signal transmission.
Compressive Haar transforms Now for graph neural network, suppose want use K pooling layers. We associate the chain Go-sx 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 s j S K 1, of the Nj Haar coefficients, the first Nj+1 coefficients are frequency coefficients, which reflect the approximation to the original data, and the other (N₃ N5+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 at layers j O,..., , K 1, which then gives the HaarPooling
in Definition II
As shown in the following formula, the compressive Haar transform synthesizes the neighbourhood information of the signal f compared to the full Haar transform. Thus, HaarPooling takes the average information of the data f over nodes in the same cluster.
x
Σ PE9,+1
Σ ()))
x
Σ
Σ
X (5)
Pa(u)]
p=Pa(e)
PEG,+1 Pa(u)
where $ is the full Haar basis matrix at the jth layer and [Pag(t) means the number of nodes in the cluster which v lies in. Here, in the first equation, 1/ A/V[Pag()) (v)] can be taken out of summation as Pa(v) is in fact a set of nodes. We show the derivation of formula in equation in Appendix D
In HaarPooling, the compression or pooling occurs in the Haar waveler domain. HaarPooling trans- forms the features on the nodes to the Haar wavelet domain and discards the sigh-frequency coeffi- cients in the sparse Haar wavelet representation. Figure 4 shows two-layer HaarPooling strategy. The first layer pools the input X by the compressive Haar basis matrix $ 88x to the output Xg
with lower first dimension. The second layer pools the input X by the $ (1) which first dimension drops to one.
the output X
4.2 FAST COMPUTATION OF HAARPOOLING
For the HaarPooling introduced in Definition I we can develop a fast computational strategy by virtue of fast adjoint Haar transforms. Let Go- be coarse-grained chain of the graph Go- For convenience, we label the vertices of the level-j graph Gy by V3 := (of" ... JN
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 ck be the number of children of o i.c. the number of vertices of Gy-1 which belongs the cluster u for is 1, I,..., N₁. For j = 0, we let (0) = for k = 1,..., No. Now, for j O,... K and I.....Ny Nj. define the weight for the node of layer j by
w
(
(6)
Let Wo == (w( (
Then, for j O...., K, the weighted chain (9)- K. W j+ becomes a filtration if each parent of the chain 9-- K has least two children. See e.g. (Chui et al. 2015) Definition 2.3).
O...., K, k= 1....,,,, N2).
Let j 0, 0,..., K. For the jth HaarPooling layer, let (6 N₂ be the Haar basis for the jth layer, which we also call the Haar basis for the filtration (Gj-k, W of graph G. For k = 1,....N; (f).
we let X (()(())
x(o()), :)) E RRd the feature vector at node u We define the weighted sum for feature X E N2 xd, for d, 2 1 by
8 (x, ((1)) X(o2)),
( ok
E Gy.
7

---

Algorithm 1: Fast HaarPooling for One Layer
Input: Input feature X for the jth pooling layer given j = O...., 1 in GNN with total K HaarPooling layers; the chain 9--K associated with the HaarPooling: numbers N; of nodes for layers J...... K.
Output: 0 X from Definition !
Step 1: Evaluate the sums for J..... K recursively, using equation and equation (()) Vul E V,.
((0) (x)" 1
Step 2:
for L = 1 to Nj+1 do
Set NK 0.
Compute i such that Noa1 +IsESN; N₁
Evaluate Σ st (X)o o
)u) 0f (v)
(1) (0) (0) in equation by the two steps:
(a) Compute the product for all o/ VV:
(x (b)) (X3",, ju Pt (ek
(8) (1)
(b) Evaluate sum Ex T ok).
end for
and recursively, for = j+ + 1,..., K and (00 g (ti) (x, xx
Σ S E
w (t-1)
g( ((=))(())((X,, (X, ((
(8)
For each vertex (0) of Gi the St0) (X, 2 is the weighted sum of the S(i-1) (x, oh =1 at the level i 1 for those vertices Uk (i-1) of G: whose parent is u
( Theorem 3. For 0 J ijs K 1, 1, let (0) J for = j l,..,, K be the Haar bases for the filtration (Gj-k, w layer i. Then, the compressive Haar transform for the jth HaarPooling layer can be computed by. for the feature E xd,, and I.....N...
(0 x) = Σ S (X, uk
W
WE OF (o
where the largest possible number in {j + I,...,,K K} such that oe the tth member of the orthonormal basis ( No 12())), Uk are the vertices of Gs and the weights woy are given by
(3)
equation 72
We give the algorithmic implementation of Theorem Algorithm rithm for HaarPooling at each layer.
I which provides fast algo-
Computational complexity With increasing graph size, the sparsity of the Haar basis matrix T6 becomes more pronounced et al 2019). This sparsity implies fast computation for HaarPooling. The computational complexity of HaarPooling determined by the adjoint Haar transforms. In the first step of Algorithm|] D the total number of summations for all elements of Step is no more than E N;+1; In the second step, by the locality of the Haar basis, the total number of multiplication and summation operations is at most 2 D C (N₂)). Here the constant which bounds the number of different values of the Haar basis vector. Thus, the computational cost of Algorithm is ON₁)). We run an experiment to evaluate the CPU computational time of HaarPooling by Algorithm against the direct matrix product. We use randomly generated graphs and features with size ranging from 2 to 5000. As shown in Figure [] the fast HaarPooling has computational cost nearly pro- portional to the number of nodes N, while the ordinary matrix product incurs a cost close to order O(22). These results consistent with the computational complexity analysis given above.
8

---

100
HaarPool
1.6 x 10 N0
10.1
Matrix Product
6.2 10 22
Figure 5: Comparison for fast putation and direct matrix product for HaarPooling for input feature ar- ray with up to 5000 nodes. The cost of HaarPooling has near lin- car computational complexity. The cost of direct matrix product grows at ((N2.1).
10² 2
You
10 3
1100
10
10.5
102
10
N
EXPERIMENTS
To verify whether the proposed framework can hierarchically learn good graph repre- sentations for classification, evaluate HaarPooling five widely used benchmark data sets for graph classification (Kersting et al. 2016), including one protein graph data set PROTEINS (Borg-
Data sets
wardt et al., 2005 Dobson & Doig 2003); two mutagen data sets MUTAG (Debnath et al. 1991
Kriege & Mutzel 2012) and MUTAGEN (Riesen & Bunke (0088 Kazius et al. 2005) (full name
Mutagenicity): ) and data sets that consist of chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines, NCI1 and NCT109 (Wale et al.) 2008). We include data sets from different domains, sample and graph sizes to give a comprehensive under- standing of how HaarPooling performs with data sets in various scenarios. A summary information of the data sets given Table 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 from 17.93 to 39.06 and the average number of edges is from 19.79 to 72.82.
Table 1: Summary statistics of the data sets used in experiments
Data Set
MUTAG
PROTEINS
NCII
NC1109
MUTAGEN
max #nodes
28
620
111
111
417
min #nodes
10
4
3
4
4
avg #nodes
17.93
39.06
29.87
29.68
30.32
avg #edges
19.79
72.82
32.30
32.13
30.77
#graphs
188
1,113
4,110
4,127
4,337
#classes 2
2
Baselines and running environment We compare HaarPool with SortPool (Zhang et al.) 201 Sa),
DiffPool (Ying et al. 2018), gPool (Gao Ji 2019). SAGPool (Lee et al. 2019). EigenPool (Ma et al. 2019a), CSM (Kriege &
and GIN (Xu et al. 2019) on the above data sets. The
experiments use PyTorch Geometrid (Fey & Lenssen 2019) and were run in Google Cloud using
Nvidia Telsa T4 with 2560 CUDA cores, compute 7.5, 16GB GDDR6 VRAM.
Training procedures In experiments, we use GNN with most 3 GCN (Kipf & Welling 2017 convolutional layers plus one HaarPooling layer, followed by three fully connected layers. The hyperparameters of the network the eigenvalues of the graph Laplacian, to generate a chain with the number of layers given. Spectral clustering has shown good performance in coarsening variety of data patterns and handle isolated nodes.
adjusted case by case. We use spectral clustering, which exploits

---

We use random shuffling of the data set, which split into training, validation, and test sets with proportions 80%. 10% and 10% respectively. We use the Adam optimizer (Kingma & Bal (015), 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 [Shhhur et al. (2018).
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, achieved top accuracy. This shows that HaarPooling with appropriate graph convolution, graph classification tasks, and in some cases improve state of the art by few percent points.
Results
achieve top performance
variety of
Table 2: Performance comparison for graph classification tasks (test accuracy in percent, showing the standard deviation over 10 repetitions of the experiment).
Method
MUTAG
PROTEINS
NCI1
NC1109
MUTAGEN
CSM
85.4
GIN
89.4
76.2
82.7
SortPool
85.8
75.5
74.4
72.3*
78.8*
DiffPool
76.3
76.0
74.1
80.6
gPool
77.7
SAGPool
72.1
74.2
74.1
EigenPool
76.6
77.0
74.9
79.5
HaarPool
90.0++3.6
80.4+:1.8
78.6:+0.5
75.6+
10.9+
** that the records retrieved from EigenPool (Ma et al. 2019a), "-" means that there is
public records for the corresponding method on data set, and the bold number indicates the best performance in the list.
CONCLUSION
introduced new graph pooling method called HaarPooling. HaarPooling has a mathemati- cal 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 coarsened representation. As 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 very fast pooling method.
REFERENCES
Mihael Ankerst, Markus Breunig, Hans-Peter Kriegel, and Jörg Sander. Optics: ordering points to identify the clustering structure. In ACM Sigmod Record, volume 28, pp. 49-60. ACM, 1999.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez. Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:
2018.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7(Nov):2399-22 2006.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1): 147-i56, 2005.
10

---

Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Cätálina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò. Towards sparse hierarchical graph classifiers. In Workshop Relational Representation Learning, NeurIPS, 2018.
C. K. Chui, H.N. Mhaskar, and X. Zhuang. Representation of functions on big data associated with directed graphs. Applied and Compulational Harmonic Analysis, 44(1):165 188, 2018. ISSN 1063-5203. doi: http:///diiorg/10000110 6/j.aca.....166666.. 2016.12.06....
C.K. Chui, Filbir, and H.N. Mhaskar. Representation of functions on big data: graphs and trees. Applied and Computational Harmonic Analysis, 38(3):489 509, 2015.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical Society, 1997.
Ingrid Daubechies. Ten lectures wavelets. SIAM, 1992.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2):786-797, 1991. doi: 10. 1021/jm00010600444
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, pp. 3844-3852, 2016
Frederik Dichl, Thomas Brunner, Michael Truong Le, and Alois Knoll. Towards graph pooling by edge contraction. In ICML 2019 Workshop on Learning and Reasoning with Graph-Structured Data, 2019.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4))771-783, 2003.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzin and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In NIPS, pp. 2224 2232, 2015.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. KDD, volume 96, pp. 226-231, 1996.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In Workshop on Representation Learning on Graphs and Manifolds, ICLR, 2019.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. ICML, pp. 2083-2092, 2019.
Matan Gavish, Boaz Nadler, and Ronald Coifman. Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning. In ICML, pp. 367-374, 2010.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, pp. 1263-1272. 2017.
Alfred Haar. Zur theorie der orthogonalen funktionensysteme. Mathematische Annalen, 69(3): 331-371, 1910.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal Scientific Computing, 20(1):359-392 1998.

---

Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of Medicinal Chemistry, 48(1):312-320) 2005.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL BKKLLttpp:/ggrapkeeteet
cs bu-dortmund,
de
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and general- ization in graph neural networks. In NewrlPS, 2019.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In ICML,, pp- 291-298, 2012.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In ICMLL pp. 3734-3743, 2019.
Ming Li, Zheng Ma, Yu Guang Wang, and Xiaosheng Zhuang. Fast Haar transforms for graph neural networks. arXiv preprint arXiv: (el::::907.4488888 2019.
Yao Ma. Suhang Wang, Charu C. Aggarwal, and Jiliang Tang. Graph convolutional networks with EigenPooling, KDD, pp. 723-731, 2019a.
Zheng Ma, Ming Li, and Yu Guang Wang. PAN: Path integral based convolution for deep graph
neural networks. In Workshop on Learning and Reasoning with Sraph-Structured Representation. ICML, 2019b.
Emmanuel Noutahi, Dominique Beani. Julien Horwood, and Prudencio Tossou. Towards in- terpretable sparse graph representation learning with Laplacian pooling. arXiv preprint arXiv: 1905. 1577, 2019.
M. K. Pakhira. A linear time- complexity k-means algorithm using cluster shifting. In 2014 Interna- tional Conference on Computational Intelligence and Communication Networks, pp. 1047-1051, 2014. doi: 10. 10.1109/CICN.2014222
Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Pat- tern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 287-297. Springer, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pit- falls of graph neural network evaluation. Workshop on Relational Representation Learning, NeurIPS, 2018.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. Departmental Papers (CIS), pp. 107, 2000.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. In ICLR, 2015.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3)3347-375, 2008.
Yu Guang Wang and Xiaosheng Zhuang. Tight framelets and fast framelet filter bank transforms manifolds. Applied and Computational Harmonic Analysis, 2018. doi: 10.1016/J ac0.6//.cch..011..0 001.
Yu Guang Wang and Xiaosheng Zhuang. Tight framelets on graphs for multiscale analysis. In Wavelets and Sparsity XVIII, SPIE Proc., pp. 11138-11, 2019.
12

---

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.005900 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In NeurlPS, pp. 4800 4810, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018a.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. arXiv preprint arXiv: 1Ef2:4/8//.0402,, 2018b.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. arXiv preprint arXiv:/812.0000 2018.
A GRAPH CLASSIFICATION
Graph classification This task is to categorize graph structrrd data into several classes. The training set consists of M pairs of samples (( G.). yi), ,,..., M. For the ith sample, G. = (V,, Ex, W₂) is graph with vertex set Vi of size [V; N, (also called nodes), and edge set E; with weights W, The feature v; E R. g.x is an array of d features per vertex, i.c., an Idd -valudd function over V, The label y; an integer from a finite set indicating which class the input sample (x,, 9i) lies in. The number of nodes N, and the graph structure E;, W, usually vary over the different input samples.
Graph neural networks Deep graph neural networks (GNNs) are designed to work with graph- structured inputs of the form (z,, 9:) described above. GNN 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. changes the dimension d of the fea- ture array but does not change the number of nodes N;. Since the number of nodes of different inputs is variable, the number of nodes 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 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 cascade of convolutional and pooling layers. Fig- ure 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 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 chain of the graph, one can generate a Haar basis for (2() 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 = (VOR, E w* be a coarse cearse-grained graph of g = (V, E, w) with N = V Each vertex w E Ves is cluster e = {u E V has parent o88) G. Order Ves, e.g., by degrees of vertices weights of vertices, as Veg = {uj8 ..... Nox We define Nes vectors o on g by
1
(2
o E Vog
(10)
Neg
13

---

and for l = ......;Ne
NeR 8+1
Ej=e Xj
C5 0
Xt-1
(11)
No
1+2
Ncg 1+1
where Xj is the indicator function for the jth vertex oi E V on & given by
() = (1. v u5. 8 E Vo {ug8).
=
Then, one can show that {
N i==1 forms orthonormal basis for (g
Note that each E V belongs to exactly one cluster usk E Vox In view of this, for each a88 1,..., Nox, we can extend the vector of on G to a vector Φε,1 on G by
CB (1,1 == Of (DRR)
E v88
here | := ky is the size of the cluster R i... the number vertices 9 whose common parent 08 We order the cluster uz e.g., by degrees of vertices,
(ve.1.... ve S.V.
For = 2,... ......, similar to equation
define
ki le +
Σ/E Xt.j Xt,k-
ΦLR =
V
ke k +
Ki - k +
where for I,..., ke Xe, is given by
11 = veji
xe.(u)= = 10. v VWeeiit
One can show that the resulting {de, i I,..., No8, k I..... ke) is orthonormal basis for (g).
(J) No Step 2. Let Go-J be coarse-grained chain for the graph G. An orthonormal basis {0r Jē=1 for (g() is generated using equation 10 and equation II We then repeatedly use Step 1: for UT N; j O.....J J 1, generate orthonormal basis {Ø? Jt=1 for (2(9,) from the orthonormal basis (o) ( Ni+1 Je-1 for the coarse-grained graph Gj+1 that was derived in the previous steps. We
m of vectors the finest level, the Haar global orthonormal basis simply the Haar basis for G associated with the chain GD-VJ. The orthonormal basis {0()) Je=1 / for j JJ is called the associated (orthonormal) basis for the Haar basis {0r 1.v }
call the sequence ( = {
Besides the orthogonality, the Haar basis has the locality which is critical to the fast computation of HaarPooling.
Compressive Haar basis Suppose we have constructed the (full) Haar basis {o) (0)() N,
Je=0 for each
layer Gj of the chain Ga- The compressive Haar basis for layer is (66)) Ng
1t=0
C FAST COMPUTATION FOR HAARPOOLING
Let Go--K be a coarse-grained chain of the graph Go. For convenience, we label the vertices of the level-j graph Gj by V, {v(5) ,N.., (5)]
,,,
14

---

Fast algorithm for HaarPooling The HaarPooling in equation 3 can be computed fast by using the hierarchical structure of the chain, we introduce as follows. For j I....: K, let ()) be the number of children of o i.c. the number of vertices of Gy-1 which belongs to the cluster (t) for k = 1,..., Nj- For j = O, we let & = 1 for k = 1,..., No. Now, for j 0,..., K and k ...... Nj. define the weight for the node of
(i) of layer by
(
(12)
G
C
Let Wo- {wg (1) (9)- K, W j->k
O...., K, k l...., N2). Then, for ....., K, the weighted chain becomes a filtration each parent of the chain 9--, has least two children. See e.g. CCuui et al. 2015 Definition 2.3).
D PROOFS
Proof for equation S
We only need to prove the first formula. The second is obtained by definition. To simplify notation, we let f = Xj". By construction of Haar basis, for some layer j, the first Ns+1 basis vectors
(P)a( (v)= +6+t)) (p)/V/PPs/())))
for p Pag(v)-
Then, the Fourier coefficient of for the /th basis vector is the inner product
(1.07T) = E (p)
rEGy
= E
Σ
f(u)0
(1)) (p)/ V (P)
Σ
PED,11
= (Frolth)
where we have let
F(p) = [Pao(v)
f(v).
p=Pao(e)
This then gives
N1+1
Ns+1
( Σ
(T. olott))
(13)
Since {oe)e=t forms orthonormal basis Eg (2(G)+
N
Ns+1
10 f|] =
( ( 1 Σ
F())2
t=1
pE0,+1
Σ
Σ f(u)
(Pg((v)
PEg
p=Pag(v)
This proves the left formula in equation 5
15

---

Proof of Theorem 1y... N1+h.
By the relation between of (7) and of for j 1.... K and &
N
(o)X)= x) =
(0f
(
(1)
(ok)
N,+1
Σ
Σ
x(vb))
(1+1)
(uk (1 (1(tt))
Wk
W=1
Pag 1o0
Ny11
E
s (1-1) (
uK yokk oi
(++1)
((+
N512
Σ
s (X,
00 (
(+1)
w
(++2) +((+2) (1(tt))
N112
s6+2) (X, Uk
yu ( 0f
(f+2) (i+2)
(()+2) (1(
Σ
5O (X,
(4) 0 (v))) Uk Dul
(f+1) is the parent of og and Up" is the parent of (i+1). and we recursively compute the eg
(
(++))
where Up" 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 XGC25--HP-2FC256-FCC
to represent a GNN architecture with 3 GCNConv layers each with 256 hidden nodes plus one HaarPooling layer followed by fully connected layers each with 256 hidden nodes and 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 optimiza- tion); maximum number of epochs; patience for early stopping. The choice of hyperparameters in each data set is shown in Table
Table 3: Network architecture
Data Set
Layers and #Hidden Nodes
MUTAG
GCG0-HP-FCGO-FCI8OFFC
PROTEINS
NCII
280266HIFFF25--4CI222-2222 30C256-H1--FF226--FF122 30C256-HP-2F225-FFC22
NC1109
MUTAGEN
F GNN WITH HAARPOOLING ON TRIANGLES
We 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
16

---

Table 4: Hyperparameter setting
Data Set
MUTAG
PROTEINS
NCI1
NCI109
MUTAGEN
batch size
60
50
100
100
100
max #epochs
30
20
150
150
50
early stopping
15
20
50
50
50
learning rate
0.01
0.001
0.001
0.01
0.01
weight decay 0.0005
0.0005
0.0005
0.0001
0.0005
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 GIN convolution and global max pooling, denoted by CIN-SP-GIN-SP--INE where SP means the SAGPooling and MP means global max pooling. With HaarPooling, we test with two architectures: HaarPooling, The data for training, validation and test are 35000, 5000 and 10000 respectively. The hidden nodes convoluational layers is 64, batch size is 60 and learning rate is 0.001.
GIN-HP-GIN--AA
and
where HP means
Table 5 shows the test accuracy of the three networks. It illustrates that both networks with Haar- Pooling outperform that with the SAGPooling.
Table 5: Training, validation and test accuracies on Triangles
Accuracy (%)
Architecture
Training
Validation
Test
LIN-SP-GIN- -IN-SP-GIN-MP
45.6
45.3
44.0
-IN-HP-GIN-MP
47.5
46.3
46.1
47.3
45.8
45.5
G PROPERTY COMPARISON OF POOLING METHODS
Here 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-baseed node feature or graph structure and sparse representation. We compare HaarPooling (denoted by HaarPool in the ta- ble) to other methods (SortPool, DifiPool, gPool, SAGPool and EigenPool). The SortPool (i.e. Sort- Pooling) is global pooling which uses node signature (i.e. Meisfeiler-ehhmal color of vertex) sorts all vertices by the values of the channels the input data. Thus, the time complexity (worst case) of SortPool is ((V and space complexity is ((V])) Other pooling methods 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 (K)(V 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( + |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(EE) and the space complexity O(VI+ [F)) due to the sparsity of the pooling matrix. EigenPool, which considers both the node feature and graph structure, uses the eigedecomposition the input data by Fourier transforms of the assembled basis matrix. Due to eigendecomposition, the time complexity of EigenPool ((V)2) and space complexity is O(V HaarPool which uses the sparse representation of data by compressive Haar basis has linear time complexity O(VV) (up to log [V] term), and the space complexity is O(V]?e), where e is the sparsity the compressive Haar transform matrix and is usually very small. From the table,
subgraphs (from clustering) of the input graph, and pools
observe the HaarPool is the
17

---

Table 6: Property comparison for pooling methods.
Method
Time Complexity
Space Complexity
Clustering- based
Spectral- based
Hicrarchical Pooling
Use Node
Use
Sparse
Feature
Graph
Repre-
Structure
sentation
SortPool
O((V))
O(VD)
DiftPool
O(VV))
O V
gPool
O(VV*)
O(N) + E
SAGPool
O(EE)
O(V) + E
V
V V
EigenPool
O(VV)
O(V))
HaarPool
O(IV)
O(IV)')
V[V'' is the number of vertices of the imput graph: "["" is the number of edges of the input graph; 'c' in HaarPooling is the sparsity of the compressive Haar transform matrix; 'k" in the DiffPool is the pooling
ratio.
only pooling method which has time complexity proportional to the number of nodes, and thus has faster implementation.
18


Reviews:
[{"review_id": "Syg7UrsD5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates the problem of graph classification using neural networks and suggests a hierarchical approach for constructing a feature vector describing a whole graph via the use of the compressed Haar transform. The general method utilizes a hierarchical chain of coarsened versions of the graph (group multiple nodes into a parent 'node')  where the coarsening is achieved via spectral clustering. After obtaining the graph chain, at each level the authors apply a GCN followed by a HaarPooling, namely applying a lossy Haar Transform compression to get a representation for each cluster. \n\nOverall graph classification and regression tasks are quite important and this work provides a new way of transitioning from node based learning methods to full graph representations via hierarchical compression. Nonetheless, I find that the organization of the paper needs additional work and the experimental investigation is not sufficient and compelling enough. So I do not think the current paper is ready for publication in a top-tier venue like ICLR yet.\n\nIn particular I find the discussion of the HaarPooling step's computational performance not particularly appealing since other parts of the hierarchical approach are computationally expensive for example, the spectral clustering or GCN steps are costly. It also seems that the discussion of the paper is more on the computation and viability of the compressive Haar transform than it is about using it as a compressor as part of a larger hierarchical system. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SkxciEMt9B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new graph pooling method, called HaarPooling. HaarPooling has a mathematically formalism derived from compressive Haar transforms. HaarPooling takes into account both graph the structure and features of the graph-structured input data to compute a coarsened representation. HaarPooling can be applied in conjunction with any type of graph convolution in GNNs. Experimental results verified the efficacy of the proposed method.\n\nThe writing, organization and presentation are satisfactory. \n\nMy comments regarding this paper are as below.\n1) More experiments on real tasks (e.g., multi-human parsing or pose estimation, etc.), both quantitatively and qualitatively, should be supplemented to further verify the superiority claimed in this paper.\n2) The main contributions of this paper are not clear to me, compared with other SOTAs.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "ByxuAn3TKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper proposed a new graph pooling method based on the Haar basis on graphs. The authors argued that existing graph pooling methods have drawbacks (ignored node features, ignored the hierarchical structure of a graph or, computationally expensive in terms of space or time) and that the proposed method overcame these drawbacks. The proposed method extracts the low-frequency components of signals in terms of Haar decomposition on a chain of graphs. By the property of the Haar basis, we can compute the pooling matrix with the complexity proportional to the graph size. The paper empirically compared the proposed method with state-of-the-art pooling methods and graph NNs using well-known datasets.\n\n\nDecision\n\nAlthough this paper gave a novel pooling method by incorporating the Wavelet theory, I still have questions for the effectiveness of the proposed method in the real datasets and whether the proposed method solved the problems of existing methods the authors mentioned in the introduction (see the Suggestion section). Besides, I think the authors can improve the organization of the paper to maximize the value of the paper. Therefore, I judge the paper as a border, tending to reject for now.\n\n\nSuggestions\n\n- The main part of the paper is 10 pages long. I think the authors can polish the organization of the paper to fit the recommended page size (i.e., 8 pages).\n- I want to know how many times the authors ran experiments for each configuration.  I think the variance of test accuracies are critical since the difference in performance between methods is not significant. Adding error bars to the experiment results are preferrable if authors ran experiments multiple times.\n- The authors claimed in the introduction that the drawback of existing methods is their time or space complexity and that the proposed method is computationally inexpensive. I think it is better to emphasize that HaarPooling does solve the questions. Although the authors demonstrated that the proposed algorithm is fast compared to the naive implementation, the comparison with other pooling methods are missing. For example, adding a comparison table in terms of time and space complexity of pooling methods is one idea. Another idea is to demonstrate it empirically by providing time and memory consumption to the experiment results.\n\n\nMinor Comments\n\n- Introduction\n\t- Haar Pooling is computed following a chain... → Haar Pooling is computed by following ...\n- page 1, section 1, paragraph 1\n\t- Graph classification and regression are a very different kind of task\n\t- → At first sight, I have thought that this sentence discusses the difference between classification and regression tasks. Could you reconsider the sentence?\n- page 3, section 2, paragraph 1\n\t- The authors used the term \"chain,\" whose definition is available in the later section (Sec. 3). I think this terminology is not common in the literature of graph NNs (at least I did not come up with the definition from this term). Could you consider to add the definition (or brief explanation) of the term when you use it for the first time?\n- page 5, section 3, Chain of graph by clustering\n\t- Write what $w$ is in the definition of a graph $\\mathcal{G}=(V, E, w)$.\n- page 5, section 3.1, Orthogonality\n\t- Define $l_2(\\mathcal{G}_j)$ (I can imagine its definition, though).\n- page 5, section 3.1, Haar basis\n\t- For two consective layers $j$, $j+1$ ...\n\t- → I had a little difficulty in understanding this sentence. Could you reconsider the wording?\n-  page 13, Appendix B, (10)\n\t-  I think \"1\" in this equation is an all-one vector. It is better to write differently the all-one vector and the scalar one.\n-  page 5, section 3.1 and page 7, (8)\n\t-  For the node $v$ in the $j$-th graph and $v'$ in the $(j+1)$-th graph, the authors use both of $v\\in v'$ (section 3.1) and $v'\\in Pa_{\\mathcal{G}}(v)$ (equation (8)) to denote the parent-child relationship. It is better to align the notation.\n- page 13, Appendix B\n\t- Could you write in the appendix how to construct the compressed Haar from the full counterpart (I suppose we should choose bases corresponding to $k=1$)?\n\n\nQuestions\n\n- In the paragraph starting with Locality on page 5, the paper says that the number of different values of the Haar basis is bounded by constant. I want the authors to make this sentence more precise. To be more specific, what \"the different values\" means (I imagine that it means the number of scalar values appearing as a component of some basis) and what \"constant\" means (with respect to which variable the \"constant\" is constant?)\n- I think that the complexity of the direct matrix product is $O(N^2C)$, where $N$ is the graph size and $C$ is the channel size (correct me if I am wrong). Therefore the result of Figure 5 was surprising to me because the direct matrix product takes approximately $O(N^3)$ time.  These look inconsistent to me unless the channel size $C$ is proportional to the node size $N$.\n- Equation (5) claimed that the compressive Haar basis approximately keeps the length of an input signal. I want to know how we can justify it (theoretically or empirically).  I think that it is empirically correct for the Fourier basis that signal carries \"information\" in the low-frequency domains and that high-frequency areas are noisy (e.g., NT and Maehara (2019); Ma et al., 2019). If this is the case for Haar transform, too, I understand that equation (5) holds and gives the justification that the proposed method can extract the information from lower frequencies.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlDfpXqcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The 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.\n\nThe 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.\n\nMinor Comments:\n- In Figure 3 it seems counter-intuitive that the Graphs are arranged down-top (0-->2), whilst the equations above are arranged top-down.\n- 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.\n- 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.\n- 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. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new graph pooling method, called HaarPooling. Based on the hierarchical HaarPooling, the graph classification problems can be solved under the graph neural network framework.

One major concern of reviewers is the experiment design. Authors add a new real world dataset in revision. Another concern is computational performance. The main text did not give a comprehensive analysis and the rebuttal did not fully address these problems.

Overall, this paper presents an interesting graph pooling approach for graph classification while the presentation needs further polish. Based on the reviewers’ comments, I choose to reject the paper.

Decision: Reject