UGC: Universal Graph Coarsening

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Ques 1) Regarding .. *Line 4. vital insights’ *

Ans 1) We thank the reviewer for the suggestion. By vital insights and vital information, we mean retaining the basic statistics of the graphs, such as spectral properties and $\epsilon$-similarity in the coarsened graph. This ensures that downstream processes are more efficient and effective. Given the opportunity, we can integrate these clarifications into the manuscript.

Ques 2) Regarding Line 67-68. The Graph Coarsening(GC) problem ..

Ans 2) The Graph Coarsening (GC) problem is indeed about learning a coarsening matrix. This definition is well-established in the literature [1, Section 2], [2, Section 2.2]. The objective and problem formulation are also discussed in Section 2.

[1] Hashemi, Mohammad, et al. "A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation." arXiv preprint arXiv:2402.03358 (2024).

[2] Kumar, Manoj, et al. "Featured graph coarsening with similarity guarantees." International Conference on Machine Learning. PMLR, 2023.

Ques 3) Regarding Line 128-129. Due to this, these methods ....

Ans 3) We thank the reviewer for the suggestion. The main reason behind this statement was the following results, where we compared the coarsening time using GCond with the whole graph training time. As it can be seen from the table, the time it takes to coarsen the graph is multiple times higher than the training time. However, the above-mentioned statement can be rephrased as :

...these methods are extremely computationally demanding and may not be suitable for the scalability of GNN models. However, these methods can be beneficial for other tasks, like solving storage and visualization issues.

GCond accuracy and time

Ques 4) Regarding Line 143-144.The concepts of homophily and heterophily .....

Ans 4) We understand the statement mentioned can be misleading and therefore we have corrected the line to the following:

The concepts of homophily and heterophily in graphs are primarily concerned with whether the edges between two nodes align with their respective labels.

Ques 5) Regarding.. Line 155-160. The current formulation hash function ... Consider this example that a graph has 1 node whose degree is 999 and......

Ans 5) We appreciate your concern. To clarify, in the example cited by the reviewer, the node with a degree of 999 will indeed produce a higher hash value and will be collapsed into a super-node. This is reasonable because it is an important node and should be assigned to a different super-node. It is important to note that we ensure no super-node is empty during the formulation of the super-nodes. If there is no hash value between the range of 11-89, we will not create a super-node for this range. For the other nodes with a degree of 1, as these nodes are connected to the same high-degree node, the distinction between the hash values will be governed by their node feature vectors. The super-node index is determined by setting the appropriate bin-width value "r".

Ques 6) Regarding.. Again, concat the adj with node feature is ambiguous...

Ans 6) We appreciate your concern. To clarify, the order of the nodes is fixed and consistent across all l projectors at the start of the coarsening and does not change during the process. Once the node order is established, the LSH framework's locality-preserving property ensures that the hashing process remains stable.

Ques 7) Regarding. What is ‘|||’ in the proof of Theorem 3.1 in l......

Ans 7) We thank the reviewer for pointing out the typo. $||.||_p$ denotes $p^{th}$ norm. We have corrected the Proof of Theorem 3.1 here is the revised version:

Proof: Let S be defined such that L = $S^TS$, by Cholesky’s decomposition:

$| \lVert x\rVert_{L} - \lVert x_c\rVert_{L_c} | = | \lVert Sx\rVert_{2} - \lVert SP^+Px\rVert_{2}|$

From Modulus inequality property,

$

\leq ||Sx - SP^+Px||_2 = ||x - \widetilde{x}||_L \leq ||x||_L

$

The conversion from $L-norm$ to $2^{nd}-norm$ or vice-versa is as follows:

$\lVert x\lVert_L = \sqrt{x^T L x} = \sqrt{x^T S^T S x} = \lVert Sx\lVert_2$

Ques 8) Regarding. Line 180-181. "It means that the adjacency matrix A~ has a substantially smaller number of non-zero elements .....

Ans 8) As mentioned in the Line 177 coarsened graph, adjacency ($A_c$) is directly calculated from $C^T A C$. In general, $A_c$ has a substantially smaller number of non-zero elements than A. However, such extreme cases may exist where the number of edges remains the same and we will make a mention of such cases in the text if given an opportunity.

Ques 9) Regarding Where is the introduction of baselines .....

Ans 9) Section 2 includes the introduction to baseline(line 111-122)

• UGC: Universal Graph Coarsening, our proposed method
• VAN: Variation Neighborhood
• VAE: Variation Edge
• VC: Variation Clique
• HE: Heavy Edge
• aJC: Algebraic Distance
• aGS: Affinity
• Kron: Kron

Ques 10) Regarding Figure 7 is confusing. Present actual time saved’.....

Ans 10) The reason this figure is being presented is because the downstream tasks take substantially longer time as compared to the coarsening time in our case, whereas it is not true for the other methods. Adding a large number (downstream time) to a smaller one (coarsening time) could diminish the emphasis on coarsening, which is the focus of this work.

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Ques 1) Although the LSH strategy is much faster than other methods, the memory space overhead is non-negligible. Could you please measure the space complexity and provide a further empirical evaluation of the method? Additionally, how is the number of hash functions (𝑙) configured?

Ans 1) The memory space overhead by UGC arises from two steps

a) Random sampling of $l \in R^d$ different projectors,

b) Storing the hash values of each of 'n' nodes across these l projectors.

Hence, the additional space complexity is bounded by O(l*d + n*l). l is a hyperparameter, for all our experiments, and all datasets, we have used 3000 different projectors(l). It is worth noting that for some datasets, the value of l can be as low as 1000.

Additionally, due to its construction, UGC is suitable for online or streaming data as it does not require the entire feature matrix to be present simultaneously. In scenarios with limited memory space, the feature matrix can be split into different chunks, and UGC can be applied to each chunk separately, ensuring that the same memory is reused for all chunks. In this case, the required additional space complexity is bounded by O(l*d + n'*l) where n' is the size of the chunk and it can vary from 1 to n.

Ques 2) The paper lacks a detailed description of the experimental setup, including software and hardware environments, as well as the parameters used for different algorithms.

Ans 2) The details are included in the Appendix due to limited space in the main manuscript. For convenience, we also provide the details here:

Appendix H contains a detailed discussion about the experimental setup as mentioned in Line 301. Figure 9 provides an overview of the GCN training pipeline, while Table 7 includes information on the hyper-parameters used for training.

Appendix F contains details about the hardware specifications.

"All experiments conducted for this work were performed on a desktop with an Intel Xeon W-295 CPU and 64GB of RAM using the Python environment."

Ques 3) and Ques4)

• From Figure 5, we can see that UGC does not exhibit lower errors (RRE and HE) at lower Coarsening Ratios. I think it questions the claimed advantage of preserving spectral properties. Can the authors give a detail explanation?

• Figure 5 illustrates that the methods (e.g., VAE, VC) do not maintain a monotonic relationship between the Coarsening Ratio and RRE/HE Error. Additionally, UGC does not exhibit a clear advantage across the overall Coarsening Ratio. Can the authors make a further clarify?

Ans 3) and Ans4) In Figure 5, lower coarsening ratios indicate that the graph is significantly reduced. We observe that the RRE error for UGC is optimal when the graph is reduced by approximately 0-65%. For HE error, we acknowledge that UGC is not the best-performing algorithm, but it is comparable to existing methods. However, for the node classification task, we can see that UGC gives the best results. How these properties are related to downstream tasks is not well understood yet and warrants further investigation.

We have noticed the monotonic relationship that the reviewer mentioned but at the moment we are trying to analyze the data from additional experiments so that we can make an objective statement after a thorough assessment.

Ques 5) Table 3 does not prove the claim of “UGC (features) method achieves substantial accuracy enhancements” over GCN, GraphSAGE, GIN and GAT. Can the authors utilize UGC to more recent models, e.g., 3WL-GNNs, heterogeneous graph neural networks?

Ans 5)

We have added the results of 3WL-GNN methods. It is to be noted that originally 3WL-GNN was a graph classification method, we have made the necessary changes to adapt it to node classification task.

In 5 out of 7 datasets UGC gives the best results for 3WL-GNN.

Ques 6) In Figure 2, the specific meanings of a, b, and c are not labeled in the diagram.

Ans 6) We thank the reviewer for pointing it out, Given the opportunity, we will improve the diagram to avoid any confusion.

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Ques 1) For ScalableTrainingof Graph Neural Networks section, there are no detailed discussion on GNN models except GCN.

Ans 1) Due to the limited space of the manuscript, we have only added a discussion about GCN to the manuscript. If the reviewer suggests, the following detailed discussion can be added to the paper:

GraphSAGE [1] is a scalable inductive framework for generating node embeddings in graphs. It leverages a neighborhood sampling and aggregation approach, allowing it to generalize to unseen nodes. This makes GraphSAGE particularly effective for large-scale graphs where retraining the model for new nodes would be computationally prohibitive. The Graph Isomorphism Network (GIN) [2] takes a different approach, designed to be as powerful as the Weisfeiler-Lehman graph isomorphism test. GIN uses a sum aggregation function, ensuring that different graph structures produce distinct embeddings. This ability to distinguish graph structures makes GIN a robust choice for tasks requiring high discriminative power. Graph Attention Networks (GAT) [3], on the other hand, introduce attention mechanisms to graph neural networks. GATs assign different importance to nodes in a neighborhood, which enhances the model's capability to focus on the most relevant parts of the graph. This attention mechanism allows GATs to achieve state-of-the-art performance on various node classification tasks by effectively capturing the underlying structure of the graph.

[1] Hamilton, Will, Zhitao Ying, and Jure Leskovec. "Inductive representation learning on large graphs." Advances in neural information processing systems 30 (2017).

[2] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018). How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826.

[3] Veličković, Petar, et al. "Graph attention networks." arXiv preprint arXiv:1710.10903 (2017).

Ques 2) For Table 4, why only GCN results are shown? I also expected results for GIN GAT and GraphSage.

Ans 2) Due to space limitations in the manuscript, we included only GCN results in the main manuscript. However, we had already conducted experiments with GraphSage, GIN, and GAT for two homophilic and two heterophilic datasets, as shown in Table 3, to demonstrate the model-agnostic behavior of UGC.

As suggested by the reviewer, we have now conducted experiments using GIN, GAT, and GraphSage models for Table 4. These results further demonstrate that UGC is not restricted to any specific model.

If the reviewer suggests, we can include these additional results in the Appendix and refer to them in the caption of Table 4 as follows:

Table 4: This table illustrates the accuracy of the GCN model when trained with a 50% coarsened graph. UGC demonstrated superior performance compared to existing methods in 7 out of the 9 datasets. Please refer to Appendix H for results with GraphSage, GIN, and GAT models.

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Ques 1) it claims that the augmented feature vector is calculated by dot product and concatenation, it is not very clear that how to concate A with node features X

Ans 1) We thank the reviewer for bringing this typo to our attention. The augmented feature vector is calculated by scaling and concatenation operation instead of dot product and concatenation.

The augmented feature vector of node $v_i$ is calculated by scaling the adjacency vector $A_i$ by ($\alpha$) and feature vector $X_i$ by (1 - $\alpha$), followed by the concatenation operations of the two vectors as (1 - $\alpha$)*$X_i$ || ($\alpha$) * $A_i$, where $\alpha$ is the heterophily factor.

A detailed illustration of this process is given in Figure 11 in Appendix K. This figure provides a toy example demonstrating how the augmentation matrix is formulated. It is also mentioned in the main manuscript, specifically on lines 150-151.

Ques 2) Some figures, e.g., figure 1 and figure 4, is not very clear for visualization.

Ans 2) Thank you for bringing this to our attention. We will address this issue by increasing the size of the axis labels in Figure 1 and Figure 4 to enhance their clarity. We appreciate your feedback and will make these adjustments in the updated manuscript.

Ques 3) In table 4, for comparisons in GNN classification accuracy, it would be better to involve some other graph size reduction methods, like GCOND, SFGC to show the performance.

Ans 3) We thank the reviewer for the suggestion. We have added the accuracy of GCond in the following table.

GCond accuracy and time

As mentioned in the paper, these methods are computationally demanding, which is also evident from the table above. Specifically, the time required to coarsen the graph exceeds the time needed to train the GNN on the original graphs.

These results can be included in Table 1 and Table 4 if suggested by the reviewer.

Ques 4) Is there any ablation study to show the effectiveness of the proposed augmented feature vector?

Ans 4) Yes, the ablation study to demonstrate the effectiveness of the proposed augmented feature vector is included in Table 4. In this table, "UGC feat." denotes the scenario where $\alpha$ is set to zero, meaning only the feature matrix is considered, while "UGC-feat. + adj." denotes the case where $\alpha$ is set to heterophily factor, thereby incorporating the adjacency vector.

For heterophilic datasets, node classification accuracy improves significantly when using the augmented feature vector. This highlights the importance of the adjacency vector in the augmented feature vector.

Ques 5) More detailed explanations and analysis of whether the proposed method could adapt heterophilic graph well are expected. Is there any specific design targeting for heterophily?

Ans 5) We thank the reviewer for bringing this up. We have observed that the heterophily factor can be directly utilized as the $\alpha$ value. When we extrapolated the results for different $\alpha$ values, it was observed that setting $\alpha$ around the heterophily factor yielded the best results.

The results are shown in the table below for two heterophilic datasets, Squirrel and Chameleon. For both datasets, the heterophily factor is approximately 0.78. We observed that the best results for these datasets are obtained when $\alpha$ is set around heterophily factor.