Graph coarsening aims to reduce the size of a large graph while preserving some of its key properties, which has been used in many applications to reduce computational load and memory footprint. For instance, in graph machine learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to drastic savings in time and memory. However, GNNs rely on the Message-Passing (MP) paradigm, and classical spectral preservation guarantees for graph coarsening do not directly lead to theoretical guarantees when performing naive message-passing on the coarsened graph. In this work, we propose a new message-passing operation specific to coarsened graphs, which exhibit theoretical guarantees on the preservation of the propagated signal. Interestingly, and in a sharp departure from previous proposals, this operation on coarsened graphs is oriented, even when the original graph is undirected. We conduct node classification tasks on synthetic and real data and observe improved results compared to performing naive message-passing on the coarsened graph.
Paper
Similar papers
Peer review
Summary
This paper studies the theoretical guarantees of graph coarsening for GNNs. The authors propose a new and directed message-passing operation specific to coarsened graphs, which makes many theoretical results possible.
Strengths
S1: The results are very useful for the field of graph coarsening. Theorem 2 shows the gap of loss between the coarsened graph and the original graph, which is applicable for many tasks. S2: The new message-passing looks natural and novel to me. S3: The literature review is comprehensive.
Weaknesses
W1: The overall structure is somewhat loose. W2: It would be nice to see more intuitive explanation of $S^{MP}_c$, e.g., when $S$ is symmetrically normalized adjacency matrix from GCN. W3: The experiments are conducted only on small datasets, which I understand since the authors put more effort on the theoretical analysis.
Questions
Q1: Can the authors give some intuitive explanation on $\overline{C}_{\Pi}$, e.g., what kind of coarsening method will make this term smaller? Q2: It would be nice to see more experiments on larger datasets, e.g., ogbn-arxiv. Typo: Line 212, $\hat{A}=A+I$.
Rating
6
Confidence
2
Soundness
3
Presentation
2
Contribution
4
Limitations
N/A
Summary
This paper proposes a new message-passing matrix for a graph coarsening algorithm. The goal is to have some message-passing guarantees for the new message-passing matrix, which is not the case with the previous message-passing matrices based on this coarsening. They provide theoretical proofs for linear variants of GNNs (SGC). They examine their theoretical guarantees on synthetic datasets and do experiments on two real-world graphs for comparing different selections of the message-passing matrices. Their approach in most of the experiments varying in the coarsening ratio, works better than alternative approaches.
Strengths
Graph coarsening can be indeed very beneficial if it can be done efficiently. Pooling approaches in some domains such as computer vision have been very helpful, but they are not as prominent in the learning on graphs community. Having well-studied approaches for this end can be of great importance because of the memory limitations of the GNNs. Also, their work has a deep root in the theory and provides theoretical guarantees for their approach.
Weaknesses
While the theoretical analysis is interesting it is limited to the linear networks. Extending this analysis to more complex GNNs might not be an easy task, however, this does not mean that they could not try their approach for other types of GNNs and see if it works in practice or not. Maybe they could try more common message-passing architecture such as Graph Attention Networks (GAT) or Graph Isomorphism Networks too. Also, the datasets used are fairly old and outdated in the current state of learning on graph works. I would suggest trying some recent datasets, maybe varying from homophilous datasets to heterophyllous ones.
Questions
1. The theory is based on signal processing on graphs that work on a single value for each node. Most datasets have a vector of initial features for each node, how this can be addressed in the theory? 2. How much does the coarsening algorithm help with the memory? GNNs usually scale by the number of nodes + the number of edges, the coarsening ratio r talks about how much you can reduce the number of nodes, but edges seem to be a more important factor in the memory and time complexity. Is there any theoretical or experimental analysis on the edges or memory in general?
Rating
5
Confidence
1
Soundness
3
Presentation
3
Contribution
2
Limitations
The theoretical analysis is limited to the linear networks and the experiments are limited to two small datasets.
I thank the authors for their rebuttal and new experiments. In general, I think the practical applicability of this work is limited at present. The computational cost seems to be expensive and this class of graph coarsening idea seems to be mostly applicable to homogeneous datasets (usually less challenging datasets), and as nodes inside a supernode can only be assigned to the same class, the performance would be poor on more heterogeneous datasets. However, I also think that we need more theory to understand the coarsening and pooling algorithms. I am not an expert in this area and cannot evaluate the significance of the theoretical results provided in this work or their applicability to other works or for future theoretical analysis. Relying on Reviewer 7C68's review, I would like to increase my score to 5; however, I want to decrease my confidence level in my assessment to 1, since I am making a decision in an area where my knowledge is very limited.
Thank you for your answer. Indeed, your are correct in pointing out that the *coarsening* process in itself is still an active area of research and that classical spectral-based coarsening must be improved for certain datasets. Our work, however, studies message-passing on coarsened graphs, which is downstream from the coarsening process. But we hope that it might serve as pointers to improve the coarsening itself in future work.
Summary
This work presents a novel computation method for the message-passing matrix on coarsened graphs. This method does not require recalculating degree matrices and other information on the coarsened graph and has comprehensive theoretical guarantees. Overall, it addresses a significant problem in graph coarsening field.
Strengths
1. The theoretical analysis is sufficient and reasonable. 2. The proposed method is very simple. 3. The model performs very well on Cora and Citeseer.
Weaknesses
The experimental section is insufficient. Testing only on Cora and Citeseer is not enough to demonstrate the effectiveness of the method. More GNN models should also be tried. I believe this work is a valuable contribution to the field of graph coarsening, and if the authors further increase the experiments, I will raise my score.
Questions
How effective is this work on datasets such as Arxiv and Products?
Rating
7
Confidence
4
Soundness
3
Presentation
2
Contribution
3
Limitations
The authors adequately addressed the limitation and potential negative societal impact of their work.
Summary
The authors describe an alternative way to obtain the connectivity matrix of a coarsened graphs and provide some bounds on operations performed on such a matrix.
Strengths
Theoretical work on how to optimally compute the connectivity matrix of a coarsened graph is an interesting and potentially useful research direction.
Weaknesses
- The main contribution is very small, as it simply consists in replacing the coarsened matrix QSQ^T, commonly used in graph pooling, with QSQ^+. This seems more of a detail in practice and it seems too much to have a whole paper on it. I seriously doubt it would make a significant difference in practice and the limited experimental evaluation (more on this later) does not help to address my concern. - I don't see the usefulness of Theorems 1 and 2, which is the second contribution of the paper. They provide bounds which I don't find useful, as they do not compare against other existing bounds and they are not computed for other coarsening schemes, such as the more common QSQ^T. For example, it would be useful to see that the proposed coarsened matrix yields narrower bounds than the latter. - I believe that there are too many simplifications and assumptions for the theoretical results to be relevant in practice. For example, the RSA constant is defined only for 1-D node features, which is something not commonly found in many graph data processed by graph neural networks. Similarly, it seems that Theorem 2 relies on the assumption that each column of the node features X belongs to R, which seems too strong and unrealistic as assumption. Finally, the whole paper assumes GNNs without nonlinearities. I believe that a GNN without nonlinearity is not a GNN and a paper completely centered around the analysis of such models should rather be published in a (graph) signal processing or linear algebra venue, not a machine learning one. - The experimental evaluation is too limited and not convincing. First of all, it only considers relatively small graphs, as the coarsening algorithm used does not scale well. This defies the whole premise of using coarsened graphs to handle large graphs that cannot be processed due to high computational complexity. - Only one coarsening algorithm is considered to obtain Q, while there is a large pletora of existing graph pooling algorithms that can be used to compute Q. To convince about the effectiveness of the proposed method, the author(s) should show that it works with different coarsening schemes. Remarkably, the coarsening algorithm used in the experimental evaluation does not even account for node features. This, again, set the work apart from the GNN and machine learning community. - Besides the synthetic data, the only two datasets considered are Cora and Citeseer. These datasets are rather similar (both of them are citation networks) and they have very homophilic node features\labels, which might biases the experimental evaluation. In addition, the experiment considers only the largest connected component of these networks, which further simplify the task on datasets that are already simplicistic. The need for such an unusual experimental setting casts further doubts on the effectiveness of the proposed method. - The authors largely overlook relevant related work on graph pooling. See for example the CONNECT operation from the paper entitled "Understanding Pooling in Graph Neural networks". - (minor) Ker(L) is not defined I think.
Questions
I do not have questions besides the concerns above.
Rating
6
Confidence
5
Soundness
2
Presentation
3
Contribution
2
Limitations
See what I wrote in weaknesses.
Thank you for your careful review and for raising your score. A few comments on the points you mention. **On pooling**: we agree that the vocabulary in the community might overlap a bit at this point. We'll try to clarify as much as we can our meaning in the final version (that is, our focus on spectral-based unsupervised coarsening), and add the references you mention. Thank you for providing them. **On propagation matrix**: it is true that the ``more orthogonal'' $Q$ is, the less the difference between $Q^+$ and $Q^T$. More generally, the difference between the two is more pronounced when supernodes are of very different sizes, which may happen for highly irregular graphs (eg, for uniform coarsenings, when all the supernodes are exactly of the same size, there is only a multiplicative constant between $Q^+$ and $Q^T$). We will explain this better in the final version, as well as outline the datasets where this happens more frequently.
The point you made in your answer about the propagation matrix, i.e., that $Q^{+}$ and $Q^\top$ become more similar as $Q$ induces a balanced partition makes sense but it is something I missed when reviewing the paper. Indeed, I strongly encourage the authors to stress this point. There is a class of graph pooling methods that encourage the size of the supernodes to be balanced (see for example the dense pooling methods from this recent survey paper [1]). In this case, it would make less sense to use $Q^{+}$. Again, this seems an important point worth commenting on. [1] Wang, Pengyun, et al. "A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability." arXiv preprint arXiv:2406.09031 (2024).
Thank you for the pointers and reference, that is indeed an important point that we will emphasize in the final version.
I further improved my score, trusting the authors to implement all the modifications they promised to me and the other reviewers.
Summary
This paper proposes a novel message-passing guarantee for graph coarsening and a new message-passing operation with the message-passing guarantee. Experiments demonstrate that the prediction performance of the proposed method outperforms some baselines.
Strengths
1. The proposed message-passing guarantee is novel. 2. The authors provide the theoretical analysis
Weaknesses
1. How to select the hyperparameters in experiments (e.g. the number of the SGC layers)? The selected coarsening ratio is significantly larger than existing works. 2. Do linear GNNs [3] satisfy Assumption 4? 3. I am not sure whether the analysis under the linearity assumption is enough. Assume the processed features of SGC is $H=A^TX \in \mathbb{R}^{n \times r}$, where the feature dimension $r$ is significantly smaller than the number of nodes $n$. By noticing that the rank of $H$ is lower than $r$, we can compress the node features into sizes $(r,r)$ without errors. So, what is the motivation for graph coarsening under the linearity assumption? 4. The authors may want to compare the spectral guarantee and the proposed message-passing guarantee in details. Moreover, I suggest summarizing these theoretical properties of existing methods and the proposed method. 5. The formulation of message passing is different from [5]. The message passing framework considers the graphs with edge features while Equation (1) does not consider them. Therefore, the concept of message passing guarantees may mislead readers. In my opinion, the proposed concept in this paper is close to convolution matching [6]. 6. How to effectively compute $Q^+$ in practice? The complexity analysis is missing. [1] Featured Graph Coarsening with Similarity Guarantees. [2] Graph Distillation with Eigenbasis Matching. [3] How Powerful are Spectral Graph Neural Networks? [4] Graph Reduction with Spectral and Cut Guarantees. [5] eural Message Passing for Quantum Chemistry. [6] Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
Questions
See Weaknesses.
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
The authors have adequately addressed the limitations.
Thank you for your answer. We attempt to answer your remaining questions below. 1. *Why is the selected coarsening ratio significantly larger than existing works? How to select the coarsening ratio in experiments?* We select three coarsening ratios that are used in Loukas work [1] to illustrate our theoretical results. Following your suggestion, the final version of the paper will include more coarsening ratios (please note that in the Dickens [4] work mentioned earlier in your questions, the coarsening ratio is defined as $1-r$ compared to Loukas and ours). In practice, selecting the ratio really depends on the use-case, whether the aim of the user is to save storage memory, train a GNN, and so on. For instance, compared to smaller datasets, we had to select a very high coarsening ratio for Reddit in order to train a GNN for it on a laptop. Of course, the higher the ratio, the ``worse'' the results compared to the original graph. 2. *What is the motivation for graph coarsening under the linearity assumption?* We agree that for now the assumption on non-linearities is strong. However SGC is indeed used in many theoretical works to analyse the inner workings of GNNs (see eg [2,3] and references therein), and we still believe that it opens a path for interesting future works on the interaction between low-frequencies and non-linearities, in order to treat more general GNNs on coarsened graphs. 3. *The answer for Concern 4 is confusing. If spectral guarantees lead to message-passing guarantees, then what is the contribution of this paper? A method with spectral guarantees is enough in practice, as the method also ensures message-passing guarantees.* Spectral guarantees and message-passing are of different nature, and concern different objects. Spectral guarantees are inherent to a graph coarsening, and refer to the fact that low-frequencies of the graphs are preserved by coarsening (aka a low $\epsilon$ constant). Most algorithms, such as Loukas' that we employ in the experiments, aim at producing such spectral guarantees. Message-passing guarantees concerns the choice of a *propagation matrix*. Our work consist in showing that, even assuming that the coarsening exhibit spectral guarantees, message-passing guarantees are *not* automatic, and generally not satisfied for naive choices of propagation matrices. We then propose a new propagation matrix that yields such message-passing guarantees, when the coarsening has spectral guarantees (that is, we bound the message-passing error of this propagation matrix by $\epsilon$, hence the fact that spectral guarantees ``lead to'' message-passing guarantees *for this new propagation matrix only*). We will clarify this in the final version. 4. *The concept of message-passing guarantees is still confusing. Given your answer, convolution guarantees may be more accurate than message-passing guarantees, as the convolution operation usually does not consider the edge features.* Thank you for your suggestion. We will not change the title at this point, but will make this point of vocabulary clear in the final version. [1] Graph Reduction with Spectral and Cut Guarantees, Andreas Loukas, JMLR 2019 [2] Zhu et al. Graph Neural Networks with Heterophily. AAAI. [3] Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing. NeurIPS. [4] Dickens et al. Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
Thanks for the detailed response and most of my concerns have been addressed. Therefore, I raise my score to support the acceptance of this paper.
Thanks for the response. All my concerns are addressed.
Thank you for the detailed answers. I do not completely agree with the distinction proposed by the authors between graph pooling and graph coarsening. Graph pooling can also be a pre-processing step that reduces the size of the graph and, thus, the memory consumption. See for example Graclus [1], originally introduced by [2] as a pooling scheme, and other non-trainable pooling operators described in [3]. In addition, there are some recent work that showed some guarantees of pooling operators in terms of their capability of keeping two non-homomorphic graphs distinguishable after pooling [4]. I suggest the authors to clarify this connection... or to find a stronger argument for why pooling and coarsening should be different things. I still believe that the practical contribution seems a rather small detail that would arguably make a small difference using $QSQ^+$ rather than $QSQ^T$ in most practical settings. At least, that's the experience I had myself when I replaced $S^T$ with a pseudo-inverse on some problems I am currently working with. Nevertheless, I see that the value of this work is to be a starting point for a theoretical study on pooling/coarsening in GNNs that will hopefully be developed further in the future. Even if most of my concerns still remain after the rebuttal, I do appreciate the effort of the authors in answering in detail to every author and adding additional experiments. Therefore, I'll raise my scores conditional on the fact that the authors will modify the paper as asked. [1] I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors a multilevel approach. IEEE transactions on pattern analysis and machine intelligence, 29(11):1944–1957, 2007. [2] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3844–3852, 2016. [3] Grattarola, D., Zambon, D., Bianchi, F. M., & Alippi, C. (2022). Understanding pooling in graph neural networks. IEEE transactions on neural networks and learning systems, 35(2), 2708-2718. [4] Bianchi, F. M., & Lachi, V. (2024). The expressive power of pooling in graph neural networks. Advances in neural information processing systems, 36.
Thanks for the response. I believe that the volume of experiments in this paper still has not reached my expectations. However, considering that the paper addresses a very important issue in graph coarsening, I have raised the score to 7 and encourage the authors to continue adding more experiments.
Thank you for your answer. We are confident at this point that it will be possible for us to extend the experimental section with other large datasets beyond Reddit.
Thanks for your rebuttal. The rebuttal has addressed Concerns 2 and 6. Unfortunately, my concerns about Concerns 1,3,4,5 remain unaddressed. The suggestions and questions are as follows. 1. **Why is the selected coarsening ratio significantly larger than existing works?** How to select the coarsening ratio in experiments? 2. **What is the motivation** for graph coarsening under the linearity assumption? 3. The answer for Concern 4 is confusing. If spectral guarantees lead to message-passing guarantees, then what is the contribution of this paper? A method with spectral guarantees is enough in practice, as the method also ensures message-passing guarantees. 4. The concept of message-passing guarantees is still confusing. Given your answer, convolution guarantees may be more accurate than message-passing guarantees, as the convolution operation usually does not consider the edge features.
Decision
Accept (poster)