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 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.
Summary
This 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.
Decision
Although 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.
Suggestions
- 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).
- 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.
- 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.
Minor Comments
- Introduction
	- Haar Pooling is computed following a chain... → Haar Pooling is computed by following ...
- page 1, section 1, paragraph 1
	- Graph classification and regression are a very different kind of task
	- → At first sight, I have thought that this sentence discusses the difference between classification and regression tasks. Could you reconsider the sentence?
- page 3, section 2, paragraph 1
	- 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?
- page 5, section 3, Chain of graph by clustering
	- Write what $w$ is in the definition of a graph $\mathcal{G}=(V, E, w)$.
- page 5, section 3.1, Orthogonality
	- Define $l_2(\mathcal{G}_j)$ (I can imagine its definition, though).
- page 5, section 3.1, Haar basis
	- For two consective layers $j$, $j+1$ ...
	- → I had a little difficulty in understanding this sentence. Could you reconsider the wording?
-  page 13, Appendix B, (10)
	-  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.
-  page 5, section 3.1 and page 7, (8)
	-  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.
- page 13, Appendix B
	- 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$)?
Questions
- 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?)
- 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$.
- 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.