Summary
The main idea of this paper is to break a graph into communities and approximate the graph with a limited number of these communities. The main idea of the work is rooted in the cut metric, which is defined for signals on the graphs and includes both graph structure and node features. They approximate the cut metric with a Frobenius norm version of the problem and prove a constructive version of the Weak Regularity lemma. Their reformulation allows the problem to be solved with a gradient descent algorithm. They also provide a version of subgraph gradient descent for larger graphs. They also theoretically analyze the approximation power of their subgraph gradient descent for finding the gradient on the whole graph. They introduce two models to be used after finding the communities and signals for these communities. The first model uses a Transformer architecture on the community signals, but the second one learns the community signals along the layers of their network. They provide time analysis on their work using random Erdős-Rényi graphs and show that their method is much more efficient than Graph Convolutional Network (GCN) in a forward pass of their model (used after finding the communities). They also get competitive results on node classification tasks for a few datasets and apply their work for a spatio-temporal task for traffic forecasting.
Strengths
1. The paper has deep roots in the theory and does not neglect to provide theoretical analysis for any decision made in their process.
2. I am not an expert in the domain of signal processing for graphs, and I do not know to what extent the proofs in this paper are novel. However, they seem to present interesting results, and introducing them to the modern graph learning community is valuable in itself.
3. Their initial algorithm for finding the communities does not appear to be any simpler than learning on the graph by a Message Passing Neural Network (MPNN). However, it has the advantage of not requiring any hyperparameter tuning and only needing to be done once.
4. They have done a good job of finding spatiotemporal tasks where the graph structure is fixed, but the signals are changing. The initial community finding process load can be better justified in this setup.
Weaknesses
1. Their analysis on the time complexity and efficiency of their method seems to be incorrect. Namely, in line 257, they mention that the message passing networks need $O(ED^2)$ operations. This is not correct. Message passing networks usually have a node-level processing which is $O(ND^2)$ and then a message aggregation process which is $O(ED)$, as there is no matrix multiplication along the edges and it is just adding the vectors of size D. Thus, the total complexity is $O(ND^2 + ED)$.
This is a significant problem as they mention their method is efficient if $K = O(Dd)$, where $D$ is the size of the features and $d$ is the average degree of the graph. By correct complexity of the message passing networks, we can see that their method only works comparably efficiently if $K = O(d)$, which is very small for most of the graphs. While Figure 2 suggests that their method is much faster than the GCN, the reason is that the graphs they sample are very dense, with $d = O(N)$ and $E = O(N^2)$. This is evident from Figure 6 in their appendix, where they use a more sparse graph with $d = 50$. We can see that when $K=100$, the time required by their method is similar to that of the GCN.
2. The paper gets unnecessarily complex and hard to understand, especially with the notations, which are excessive and sometimes inconsistent. For example, starting from Definition 2.1. the definition of the matrix norm is just used for the adjacency matrix A and feature matrix S in this paper, defining new matrices B and Z here just makes it confusing. At any point, if you require to define a formula that is general on all matrices, like when you describe the Frobenius norm, you can use names like X which does not feel to be a special matrix that might next definitions depend on it.
Starting in Section 3.1, the use of C and P for finding the ICG on (A, S) using b vectors, and continuing with F at another point, makes it very confusing. One reason for this can be that B seems to be defined earlier in Definition 2.1, but it is not really connected to the b vectors used here.
Definition 3.1 defines $\mathcal{Q}$ as a set of functions. However, starting with Definition 3.2, it uses the term "soft affiliation model" for $\mathcal{Q}$. I am not sure what is meant by "model" here and whether we are still referring to the same $\mathcal{Q}$. This is particularly confusing because, as I understand it, each member of $\mathcal{Q}$ is a function from $[N]$ to $\mathbb{R}$. Therefore, $\mathcal{Q}$ is a subset of $\mathbb{R}^N$, and the space defined for $[\mathcal{Q}]$ in Definition 3.2 is not clear to me.
3. While the main point is the efficiency of the method, the results for node classification are very limited, both in the number of datasets and the size of the datasets, and do not quite reflect the effectiveness of the method.
4. Their theory (Theorem 3.1) only works for very large K values for reasonably sparse graphs that can be seen in most datasets.
Questions
1. Is there any time measured for fitting an ICG for a graph with the gradient descent? It seems to be at least as complex as learning the main task. However, I admit that it has the advantage of requiring no hyperparameter tuning and can be done once, with the condition that it can be done on large graphs with a reasonable calculation budget.
2. What is the relation of your work to graph coarsening methods? Methods such as DiffPool [1] seem to be learning a similar thing as a layer in the neural network, and thus their pooling is task-dependent. What are the advantages of your method over these techniques?
[1] Ying, Zhitao, et al. "Hierarchical graph representation learning with differentiable pooling." Advances in neural information processing systems 31 (2018).
Limitations
The method seems to be more efficient for very dense graphs, which is discussed to some extent in the paper. However, there also seem to be some mistakes in their argument (discussed in the Weaknesses section).