Structured Graph Reduction for Efficient GNN

We thank the reviewer for valuable feedback and insightful comments.

Q1: The paper has mentioned a more recent work in Sec. 2.2, Kumar et al. 2023. Why Kumar et al. 2023 is not compared against in the experiments?

A1: We thank the reviewer for the question. Regarding the paper by Kumar et al. (2023) mentioned in Section 2.2, it is essential to note that they did not perform a downstream task such as node classification. Instead, they compared the eigenerror between the original and coarsened graphs. In response to the query, we conducted node classification using the FGC method proposed by Kumar et al. (2023) and compared it against our proposed algorithms. The comparison table is illustrated below:

It is evident from the above table that the proposed algorithms outperform all the state-of-the-art graph coarsening algorithms.

Q2: In Sec. 2, why should we use (1)? Why are structural properties such as multi-component and scale-free important in structured graph coarsening?

A2: We thank the reviewer for the question. Equation (1) in section 2 serves as a condition on the mapping matrix (C) to ensure a valid coarsening. This mapping matrix (C) maps nodes in the original graph to the supernodes in the coarsened graph. Each column of C represents a supernode, and every non-zero value in that column corresponds to nodes in the original graph mapped to that specific supernode. Additionally, each row's norm is always equal to 1, signifying that each node is mapped to a single supernode, and columns should be orthogonal such that a node of the original graph should not mapped to two supernodes. The mapping matrix $C$ learned by our algorithms satisfies equation(1). To perform the downstream task using the coarsened graph, we need to learn an informative coarsened graph, ensuring that the performance in downstream tasks using the coarsened graph is comparable to that achieved with the original graph. Ghoroghcgian et al. (2021) proposed the $\phi$ matrix, defined in Definition 2.1, suggesting that for optimal training of graph neural networks, $\phi$ should be sparse. Our investigation revealed that the $\phi$ matrix calculated from state-of-the-art methods is often not sparse, making it unsuitable for downstream tasks. Empirically, we observed that introducing various structural constraints, such as multicomponent and bipartite structures, and enforcing sparsity in the coarsened graph results in a sparser $\phi$ matrix and, consequently, improved performance. When prior knowledge about the original graph structure is available, imposing the same structure on the coarsened graph enhances downstream task performance. However, in the absence of prior knowledge, empirically, we found that multicomponent structure is a favourable choice for learning a coarsened graph with a sparse $\phi$ matrix, leading to improved performance in node classification tasks.

Q3: Which structural property is preferred in what scenarios? Also, why not impose all constraints?

A3: We thank the reviewer for the question. Prior knowledge about a graph's structure can benefit coarsening based on that specific structure. However, without such prior knowledge, the Multi-component structure has proven to be a robust approach, as highlighted in the last paragraph of Section 1, to perform node classification tasks. This observation is further supported by the findings in Table 2, where Multi-component Graph Coarsening (MGC) demonstrates superior or comparable performance compared to other structured coarsening methods. In response to the suggestion of imposing all constraints, we thank the reviewer for the suggestion. Since our framework is optimization-based, all the constraints can be easily imposed, and the overall problem is easily solvable if there is motivation for imposing all the constraints to learn a sparse multicomponent Bipartite coarsened graph. However, it is important to note that imposing all the structures might increase the per-iteration time complexity of the algorithm.

We thank the reviewer for valuable feedback and insightful comments.

Q1: What data splits are used in the experiments?

A1: We thank the reviewer for this question. We trained the GNN using the coarsened graph, where the label of the coarsened graph is determined by argmax$(C^TY)$, with Y representing the one-hot matrix of labels from the original graph. In the training process, 20% of the labels in Y are masked. Subsequently, testing is conducted on the entire original graph to evaluate the model's performance.

Q2: The authors present the sparsity of $\phi$ in the experiments. I am also interested in the sparsity of the results graph. The original graph is sparse and if the reduced graph is dense, then the training cost could be higher than training on the original (sparse) graph.

A2: We thank the reviewer for this question. The coarsened graph learned from the proposed SCG algorithm is sparse and is demonstrated by the below table:

In this table, $(x,y)$, where x represents the number of nodes and y represents the number of edges. The table above illustrates a clear correlation: reducing the original graph by a factor of k corresponds to almost same amount of reduction in the number of edges which implies that the sparsity level of the original graph and the coarsened graph is almost the same.

Next, here are the responses to the weaknesses pointed out by the reviewer:

W1: The novelty is limited. First, using a graph reduction techniques to speedup GNN training is not new. Second, all the components involved in the coarsening objectives are quite standard, which are widely used for controlling the structures of the solution. Third, the heuristics used to solve the optimization problems are also standard optimization techniques.

A1: We thank the reviewer for the question and for giving us a chance to highlight the novelty of our work. Sandeep Kumar (JMLR, 2020) is an optimization-based framework that learns a graph with various structures by taking the data $X$ as input only. Manoj Kumar (JMLR, 2023) is also an optimization-based framework that learns a smooth coarsened graph by taking the Laplacian matrix and feature matrix of the original graph as input. Our algorithm development lies in the intersection of both Sandeep Kumar (JMLR, 2020) and Manoj Kumar (JMLR, 2023). However, the crucial aspect is that different structure plays a different role in performing the downstream task using graph neural network, which has not been investigated yet. Furthermore, this is the first work that enforces specific structures in the coarsened graph and investigates that structure plays an important role while performing downstream tasks using the graph neural network. Moreover, imposing a specific structure into the coarsened graph is a combinatorial hard problem and difficult to solve. We have utilized the spectral constraints to impose the structure defined in Sandeep Kumar (JMLR, 2020) and developed a framework that can enforce four different structures in the coarsened graph. Our framework is simple and adaptable also other than these four structures, structures like Bipartite multicomponent, sparse Bipartite, and tree structure can be easily learned. In this work, we have investigated the role of structure in the coarsened graph for improving the performance of node classification task using the coarsened graph.

W2: The datasets used in the experiments are all small: the largest contains 30k nodes. These datasets can be easily trained using full-batch training.

A2: We thank the reviewer for the question. As per the question by the reviewer, the below table shows the node classification performance on large datasets e.g. NELL(65755 nodes) and OBGN ARXIV(169343 nodes) for a coarsening ratio of 0.1.

Where OOM stands for out of Memory. The above table demonstrates that the proposed method outperforms the state-of-the-art graph coarsening method.

W3: For the testing accuracy, there is a notable gap between the proposed methods and whole graph training.

A3: We thank the reviewer for the question. We agree with the reviewer that there is a gap between the proposed methods and whole graph training. However, this gap is significantly less as compared to other state-of-the-art methods.

W4: In the experiments, the proposed method is compared only against 2 reduction methods. There are numerous coarsening/sparsification/condensation methods, I suggest the authors add more baselines.

A4: We thank the reviewer for the question. we have also compared our proposed algorithms with the most recent graph coarsening method FGC(Manoj Kumar (JMLR, 2023)) as illustrated in below table:

It is evident in the above table that our proposed algorithms outperform the state-of-the-art methods.

W5: There is no analyses on the correlation between downstream task performance and the coarsening objectives values, i.e., whether a better coarsening matrix (in terms of the coarsening objectives) results in better classification accuracy.

A5 We thank the reviewer for this question. We have analysed that the downstream task performance depends on the sparsity of $\phi$ matrix. The more sparser the $\phi$ matrix, the more the node classification accuracy will be, which is supported by Figure 3 in the paper. More detail about $\phi$ matrix is in section 2 of the manuscript.

We respectfully ask the reviewers to consider increasing our score if our justification addresses your concerns. We would appreciate further feedback if our changes do not address your concerns.

We thank the reviewer for valuable feedback and insightful comments.

Q1: The reviewer notes that the submission lacks a clear exposition of its novel contributions, especially when contrasted with prior works such as those by Manoj Kumar (JMLR, 2023) and Sandeep Kumar (JMLR, 2020). Could the authors specifically articulate the unique and novel aspects of their approach that advance the state-of-the-art in graph coarsening?

A1: We thank the reviewer for the question and for giving us a chance to highlight the novelty of our work. Sandeep Kumar (JMLR, 2020) is an optimization-based framework that learns a graph with various structures by taking the data $X$ as input only. Manoj Kumar (JMLR, 2023) is also an optimization-based framework that learns a smooth coarsened graph by taking the Laplacian matrix and feature matrix of the original graph as input. We agree that based on the methodology, our algorithm development lies in the intersection of both Sandeep Kumar (JMLR, 2020) and Manoj Kumar (JMLR, 2023). However, the crucial aspect is that different structure plays a different role in performing the downstream task using graph neural network, which has not been investigated yet. Furthermore, this is the first work that enforces specific structures in the coarsened graph and investigates that structure plays an important role while performing downstream tasks using the graph neural network. Moreover, imposing a specific structure into the coarsened graph is a combinatorial hard problem and difficult to solve. We have utilized the spectral constraints to impose the structure defined in Sandeep Kumar (JMLR, 2020) and developed a framework that can enforce four different structures in the coarsened graph. Our framework is simple and adaptable also other than these four structures, structures like Bipartite multicomponent, sparse Bipartite, and tree structure can be easily learned. In this work, we have investigated the role of structure in the coarsened graph for improving the performance of node classification task using coarsened graph.

Q2: While applying convex optimization methods to graph coarsening is theoretically appealing, concerns arise regarding scalability, as time complexity may increase quadratically with the number of nodes. This appears to conflict with the primary objective of graph coarsening, which is to reduce computational load. Can the authors address the apparent contradiction and clarify how their algorithms maintain or improve upon the time complexity compared to existing graph coarsening methods?

A2: We thank the reviewer for the question regarding the per iteration complexity of our algorithm, which is $\mathcal{O}(p^2k)$ due to matrix multiplications. It is crucial to note that the mapping matrix $C$ exhibits high sparsity, containing only $p$ non-zero elements. In the broader context, graphs often demonstrate sparsity, resulting in a sparser Laplacian matrix. To enhance computational efficiency, by leveraging sparse matrix multiplication instead of the conventional matrix multiplication, the per iteration complexity can be significantly reduced to $\mathcal{O}(ab)$, where $'a'$ represents the number of non-zero entries in matrix $A$, and $'b'$ signifies the number of non-zero entries in matrix $B$. For example, SciPy sparse module in Python can be directly used for sparse matrix multiplication.

Next, we will compare the time complexity of our proposed algorithms and state-of-the-art techniques as suggested by the reviewer. For instance, the deep learning-based method GCOND exhibits a time complexity of $\mathcal{O}(Lk^2d + Lkd)$, where $L$ is the number of GCN layers, and $d$ represents the number of hidden units. In contrast, the most recent optimization-based graph coarsening technique, FGC (Manoj Kumar, JMLR, 2023), has a per-iteration time complexity of $\mathcal{O}(7p^2k+5k^2p+5kpn+k^3)$. Similarly, SCG has a per-iteration time complexity of $\mathcal{O}(3p^2k+2k^2p+3kpn+k^3)$, while BI-GC and MGC have $\mathcal{O}(4p^2k+2k^2p+3kpn+k^3)$ which demonstrate that our proposed algorithms are faster than state of the art graph coarsening techniques.

Furthermore, consider the input graph with $p$ nodes, $E_1$ edges and a feature vector of size $n$ for each node. If the GCN has $L$ layers, the total time complexity to perform node classification is $\mathcal{O}(Lp^2n+LpE_1n)$. However, the time complexity to perform coarsening as well as node classification is $\mathcal{O}(p^2k+Lk^2n+LkE_2n)$ where k is the number of nodes of the coarsened graph and $E_2$ is the number of edges of the coarsened graph. Since $(p>>k)$ and $(E_1>>E_2)$ and if $(k<n)$, then the time complexity to perform coarsening and node classification is less as compared to performing classification using the original graph.

Q3: The datasets employed in validating the proposed technique are relatively small-scale. For a comprehensive evaluation of the proposed method's efficacy, would the authors consider applying their approach to larger-scale graphs where the benefits of coarsening could be more pronounced and the technique's scalability and effectiveness more rigorously assessed?

A3 We thank the reviewer for the question. As per the suggestion by the reviewer, the below table shows the node classification performance on large datasets e.g. NELL(65755 nodes) and OBGN ARXIV(169343 nodes) for a coarsening ratio of 0.1.

Where OOM stands for out of Memory. The above table demonstrates that the proposed method outperforms the state-of-the-art graph coarsening method.

We respectfully ask the reviewers to consider increasing our score if our justification addresses your concerns. We would appreciate further feedback if our changes do not address your concerns.

We thank the reviewer for valuable feedback and insightful comments.

W1: The benchmark datasets are all relatively small. Considering that the primary aim of graph coarsening techniques is to downsize large-scale graphs, validating the model's performance on larger datasets would lend more credibility to the results.

A1: We thank the reviewer for the question. As per the suggestion by the reviewer, below table shows the node classification performance on large datasets e.g. NELL(65755 nodes) and OBGN ARXIV(169343 nodes) for a coarsening ratio of 0.1.

Where OOM stands for out of Memory. The above table demonstrates that the proposed method outperforms the state-of-the-art graph coarsening method.

W2: Some experimental results require further clarification. For instance:

<i> In Table 7, the time required for coarsening and node classification using the proposed methods is not significantly less than that needed for node classification using the original graph. In the worst case (e.g., the BI-GC model on the CORA dataset), the time cost for the former even exceeds the latter. However, graph coarsening techniques are designed to reduce large-scale original graphs and enhance the scalability of existing GNN models. These empirical results seem to contradict the core motivations behind graph coarsening, necessitating further clarification.

<ii> In Tables 1, 2, and 3 provided in the supplementary material, it would be beneficial to include node classification results using the original graph for comparison.

A2 <i>: We thank the reviewer for the question. Consider the input graph with $p$ nodes, $E_1$ edges and a feature vector of size $n$ for each node. If the GCN has $L$ layers, the total time complexity for node classification is $\mathcal{O}(Lp^2n+LpE_1n)$. However, the time complexity to perform coarsening as well as node classification is $\mathcal{O}(p^2k+Lk^2n+LkE_2n)$ where $k$ is the number of nodes of the coarsened graph and $E_2$ is the number of edges of the coarsened graph. Since $(p>>k)$ and $(E_1>>E_2)$ and if $(k<n)$, then the time complexity to perform coarsening and node classification is less as compared to performing classification using the original graph.

For smaller datasets, the time needed for coarsening and subsequent node classification using our proposed methods may not exhibit a substantial reduction compared to node classification on the original graph. However, as the dataset size scales up, a noteworthy reduction in time becomes apparent, as exemplified by the CO-CS dataset. Moreover, it is crucial to note that the benefits extend beyond time efficiency. The space complexity is also considerably reduced during the GNN training on the coarsened graph.

A2 <ii>: We thank the reviewer for the suggestion. We have updated the supplementary as per the suggestion.

W3. The paper's presentation needs improvements.

A3: We thank the reviewer for the suggestion. We have updated the manuscript as per the reviewer's suggestion.

Next, here is the answer to the question asked by the reviewer:

Q1. It is noteworthy that most scale-free graphs also fall into the category of sparse graphs. Could the authors elaborate on the rationale behind discussing these two types of graphs separately?

A1: We thank the reviewer for the question. We agree with the reviewer that most of the scale-free graphs fall into the category of sparse graphs. However, sparse graph is the broader class of graph. It is important to note that sparsity alone does not guarantee the scale-free characteristic. Additional regularization, as defined in equations (6) and (7), is necessary to ensure the scale-free property.

We respectfully ask the reviewers to consider increasing our score if our justification addresses your concerns. We would appreciate further feedback if our changes do not address your concerns.