UGC: UNIVERSAL GRAPH COARSENING

Thank you for reviewing the paper and providing feedback! We have responded below to individual quotes from your review.

Ques 1) Some of the formal derivations were a bit difficult to parse, e.g. in equation (1) on page 2, what is the <C_l, C_l> term? I also mistook the \forall i \neq j before it to be for this term too because it included a d_i.

Ans 1) We thank the reviewer for bringing this to our attention. We have utilized the condition $C_l, C_l = d_l$ to denote the degree of super-nodes. We appreciate the reviewer's feedback and have addressed the concern by removing the comma before $\forall i \neq j$ to enhance clarity and avoid any potential confusion in the main manuscript.

Ques 2) In theorem 4.2, it's not clear what the role of x is. After equation (5), it's not clear what the 'proof in Appendix A.7' is for (is it missing a theorem statement here?). I had difficulties finding a concise summary of the theoretical guarantees (in terms of the graph Laplacian) proven by this coarsening scheme. Would it be possible to point to a 'main theorem' that's proven?

Ans 2)

In theorem 4.2 $x \in R^d$ represents the feature vector of the node, while $X \in R^{N * d}$ represents a node features matrix of all the nodes.

Theorem 4.2 :($\epsilon-similarity$) Given a Graph $G(L,X)$ and a coarsened graph $G_c(L_c,X_c)$, they are said to be $\epsilon$ similar if there exists some $\epsilon \geq 0$ such that:

$(1-\epsilon)\lVert X\rVert_{L}\leq\lVert X_c\rVert_{L_c} \leq (1 + \epsilon) \lVert X\rVert_L$

where $L$ and $L_c$ are the Laplacian matrices of $G$ and $G_c$ respectively. The coarsened graph$G_c({L_c,X_c}$) and features learned as an outcome of UGC satisfy this $\epsilon$ similarity.

In the section Bounded $\epsilon$-similarity, we have further improved this $\epsilon$ similarity result by relearning the coarsened features via imposing the smoothness condition mentioned in Equation 5. As a consequence of it we are able to obtain a better bound on $\epsilon$, i.e., $\epsilon\sim(0,1]$ which is summarized in the below Theorem

Updated Theorem: Given a Graph $G(L,X)$ we learn a coarsened Graph via UGC $G_c(L_c, X_c)$, and then we relearn enhanced features as, $\tilde{X}$ by enforcing the smoothness condition. The original graph $G(L,X)$ and coarsened graph $G_c(L_c,\tilde{X})$ are $\epsilon$ similar with $0 < \epsilon \leq 1$

$(1-\epsilon)\lVert X\rVert_L\leq \lVert\tilde{X}\rVert_{L_c}\leq (1+\epsilon)\lVert X\rVert_L$

The proof regarding this Theorem is deferred in Appendix A.7.

If the reviewer deems it beneficial, we are open to putting this discussion in the main paper or Appendix.

For theoretical guarantees(in terms of the graph Laplacian) we refer reviewers to this updated version of Theorem 4.2.

Thank you for reviewing the paper and providing feedback! We have responded below to individual quotes from your review.

Ques 1) Problem formulation -- what precisely is the mathematical objective that UGC tries to achieve? This is not clearly stated. The set S does not define the set of indicator matrices the authors seem to have in mind (there are matrices that fulfill those constraints that are not indicator matrices). Why introduce it this way? Also C is supposed to be N times n, yet the example given is n times N.

Ans 1) We have tried to elucidate the notation. To clarify, S is not a set of indicator matrices. It is the set of coarsening matrices. A coarsening matrix maps each node of the original graph to a node in the coarsened graph. Each node in the coarsened graph may be thought of as a supernode, that subsumes many nodes of the original graph. Hence, entries in a coarsening matrix are {1,0} indicating node numbers; each entry ($C_{ij}$) indicates the $i^{th}$ node number in the original graph paired with the $j^{th}$ node number in the coarsened graph.

Problem formulation This manuscript presents a novel approach to coarsening all types of graphs, including those that largely follow a homophily assumption, and others that depart substantially. The coarsening task attempts to to reduce a given graph $G(V,E,A,X)$ with N nodes, into a new graph $G_c(\tilde{V},\tilde{E},\tilde{A}, \tilde{X})$, with $n$-nodes and $\tilde{X} \in \mathbb{R}^{n \times d}$ where $n<< N$ nodes. The coarsened graph $G_c$ is summarized from the original graph $G$ by using a coarsening matrix, i.e. the Graph Coarsening problem is that of learning a coarsening matrix $C \in R^{N\times n}$. Every non-zero entry $C_{ij}$ in $C$ denotes the merger of the $i^{th}$ node of $G$ to the $j^{th}$ supernode. This $C$ matrix belongs to the following set S:

$S = \{ C \in \mathbb{R}^{N \times n}, \langle C_i,C_j \rangle = 0 \quad \forall i \neq j, \langle C_l,C_l \rangle = d_i, \|C_i\|_0 \geq 1 \}$ This equation becomes important to impose the next two discussed properties on the “C” matrix; the condition $\langle C_i, C_j \rangle = 0$ ensures that each node of $G$ is mapped to a unique super-node. The constraint $\|C_i\|_0 \geq 1$ requires that each super-node in $G_c$ contains at least one node of $G$.

We thank reviewer for pointing out we have modified $C$ to $C^T$ in the example.

Ques 2) The discussion on heterophily appears out of the blue -- it is not clear what relevance it has to the paper and the technique used.

Ans 2) We clarify the point. One novelty of our work is its applicability to a wide range of datasets; this includes those satisfying homophily assumptions, as well as those that violate it, such as graphs characterized by heterophily. Since the literature on graph coarsening largely assumes homophily, this point is relevant and important in the context of our work. Hence, the concept of heterophily is mentioned in the abstract, introduction, and explicitly discussed in Section 2.2.

Ques 3) The discussion on related work is pretty mixed, but it is not always clear on what these relations are build. There is a whole literature on network summarization, which appears to be largely ignored that is much closer to the type of problems discussed in this paper.

Ans 3) The manuscript cites recent literature on Graph Coarsening [1,2,3]. References were chosen from S-O-T-A methods to provide a baseline for UGC on two criteria. These include speed, and the ability to handle datasets that do not exhibit homophily. We might have missed some relevant references, it would be great if reviewers can point out those network summarization references relevant to this work. Certainly, more references could be included. However, with regard to speed, UGC is compared with the fastest methods published.

[1] Loukas, Andreas. "Graph Reduction with Spectral and Cut Guarantees." J. Mach. Learn. Res. 20.116 (2019): 1-42.

[2] Huang, Zengfeng, et al. "Scaling up graph neural networks via graph coarsening." Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2021.

[3] Kumar, Manoj, Anurag Sharma, and Sandeep Kumar. "A Unified Framework for Optimization-Based Graph Coarsening." Journal of Machine Learning Research 24.118 (2023): 1-50.

Ques 4) The notation and description in section 3.1 is unclear to me. What are the asterisks as opposed to \cdot denote? Figure 3 does not really help much either as it is rather cryptic.

Ans 4) We thank the reviewer for pointing out the confusion, we have modified the equation in section 3.1 to $F_i = \{(1 - \alpha) \cdot X_i\oplus \alpha \cdot A_i \}$ where $\oplus$ represents the concatenation. And $\cdot$ is the multiplication. Figure 3 is used to visualize this augmented feature.

re A1) This is exactly what I would have referred to as indicator matrices. To say it once more in different terms: It appears the authors have a set of 0/1 matrices in mind; however, the characterization of the set is such that it contains many matrices that are not 0/1 -- for instance we may simply multiply the matrix C in the example by -1 and it would still be in the set... I believe the correct definition of the matrices C could be given much more succinctly in other terms.

The current problem formulation the authors point out just states what the approach does (coarsen a graph) but it does not say what it aims to do in quantitative terms; e.g., is the spectrum supposed to be (approximately) conserved? some cut metric? the eigenvectors? There is still no mathematical problem statement here, in my opinion.

re A2) homophily is not a property of a graph, but of a generative process that creates a graph (it is a causal model for the formation of links and it cannot be inferred from observational data alone -- see [1,2]) it is thus still not clear to me what the authors really mean. My guess is that they want to say that prior methods for graph coarsening do not show good performance according to some measure (but which one?) if the graph considered is created according to a process that is not homophilic.

[1] McPherson, Miller, Lynn Smith-Lovin, and James M. Cook. "Birds of a feather: Homophily in social networks." Annual review of sociology 27.1 (2001): 415-444. [2] Shalizi, Cosma Rohilla, and Andrew C. Thomas. "Homophily and contagion are generically confounded in observational social network studies." Sociological methods & research 40.2 (2011): 211-239.

There are also no citations given in this paragraph, so it is unclear what methods the author refer to when they say, those do not work for non-homophilic graphs.

re A3) the mentioned papers all have a clear problem formulation and objective, which the current paper is still lacking in my opinion. Again graph coarsening is an ill-defined term and as long as the authors do not clearly specify what properties the coarsened graph is supposed to preserve precisely There are even surveys on graph summarization available already like Liu, Yike, et al. "Graph summarization methods and applications: A survey." ACM computing surveys (CSUR) 51.3 (2018): 1-34

re A4) Thanks for the clarification

re A5) What is not fully clear here is why the authors believe that their method would perform well in terms of these metrics (in terms of the algorithm design). That these are possibly quality criteria is quite clear, but how do they relate to the proposed approach?

re A6) What does "resemble" and "quality" mean precisely here -- this is the question. In mathematical, quantifyable terms. Loukas work has a clear objective, already stated in the title of his work!

Let me iterate my point here from my initial review: I think the problem area and potentially the algorithm the authors propose is interesting; however, the exposition and the discussion of the idea, motivation and algorithmic guarantees appears too vague to me to recommend acceptance here.

Thank you for reviewing the paper and providing feedback! We have responded below to individual quotes from your review.

Ques 1) Section 3.4 is not a time complexity analysis, and no appropriate appendix is present. Crucially, it is unclear how the hidden loop on Line 14 in Algorithm 1 is maintained as O(N) rather than O(N^2). A time complexity analysis section should not leave finding all hidden loops in mixed pseudo-code and mathematical notation algorithms as an exercise for the reader. The empirical results indeed hint that the time cost benefits exist, but as the linear time claim is made in the abstract and introduction, this section requires considerable improvement

Ans 1) We have three phases for our framework. In the first phase(Algo 1 Line 1-7), we can see Line 7 is driving the complexity of the algorithm where we multiply two $F \in \mathbb{R}^{N \times d}$ and $W \in \mathbb{R}^{L \times d}$ matrices which results to $O(NLd)$. In the second pass, the supernodes for the coarsened graphs are constructed with the help of the accumulation of nodes in the bins. The main contribution of UGC is up to these two phases i.e., Line 1-10. Till now, time-complexity is $O(NLd) \equiv O(NC)$ where $C$ is a constant. Hence, the time complexity for getting the partition matrix is $O(N)$.

In the third phase, Line 14-15, we calculate the adjacency and features of the supernodes of the coarsened graph $G_{c}$. For this we iterate over the edges of the original graph and use the edge nodes along with the surjective mapping $\pi : V \rightarrow V_c$ to increment the weight of the corresponding edge between the supernodes in $G_{c}$. The computational cost of this operation is $O(m)$, where $m$ is the number of edges in the original graph, and this is a one time step. Indeed, the overall time complexity of all three phases combined is O(N+m) where m is the number of edges. However, it's important to note that the primary contribution of UGC lies in the process of finding the partition matrix whose time complexity is O(N). We have compared the partition matrix computational of all other methods with ours.

We have added this Detailed Time-complexity analysis in Appendix also.

Ques 2) The choice of downstream GNN architecture feels unjustified. Why specifically convolution instead of GIN, or GAT? More concretely, how should a reader know that the coarsening benefits are not specific to GCN but rather more universally exploitable?

Ans 2) We thank the reviewer for their constructive suggestions. While we initially employed GCN for validating the quality of our coarsened graph, it's essential to note that our model is not constrained to any specific architecture. Responding to the suggestion, we have tested our framework on additional models and results from three models (GraphSage, GIN, and GAT) are incorporated here. These results validate that our framework is not model dependent. If the reviewer deems it beneficial, we are open to add these results into Appendix.

Models are trained on 50% coarsened graph and accuracies are quoted on original data.

Ques 3)

Additionally, low Eigen error is shown as a benefit, but no investigation was made to show if, for example, the coarsening maps to community detection when performed using spectral methods.

Ans 3) We thank the reviewer for their feedback. To elucidate the correlation between Eigen Error(REE) and the quality of the coarsened graph, we draw the reviewer's attention to Figure 5(a). In this figure, it is evident that the Relative Eigen Error (REE) increases as we reduce the graph. This observed trend is consistent with the relationship observed in node classification accuracy using GNNs, where the accuracy decreases as the graph gets reduced. These findings are corroborated in Table 6, presented in Appendix A.5. The presented results collectively illustrate the intrinsic connection between Relative Eigen Error, GNNs accuracy, and the quality of the coarsened graphs.