Graph Sparsification via Mixture of Graphs

We sincerely thank you for your insightful comments and thorough understanding of our paper! Here we give point-by-point responses to your comments and describe the revisions we made to address them.

Weaknesses 1: Making Contributions Clear

Following your suggestion, we have added a dedicated section in Appendix H.1 to present our key contributions in clear and concise bullet points:

• Node-Granular Customization: We propose a new paradigm of graph sparsification by introducing, for the first time, a method that customizes both sparsity levels and criteria for individual node modeling based on their local context.
• MoE for Graph Sparsification: We design an innovative and highly pluggable graph sparsifier, dubbed Mixture of Graphs (MoG), which pioneers the application of Mixture-of-Experts (MoE) in graph sparsification, supported by a robust theoretical foundation rooted in the Grassmann manifold.
• Empirical Evidence: Our extensive experiments on seven datasets and six backbones demonstrate that MoG is (1) a superior graph sparsifier, maintaining GNN performance losslessly at 8.67% - 50.85% sparsity levels; (2) a computational accelerator, achieving a tangible 1.47 - 2.62× inference speedup; (3) a performance booster, whichs boost ROC-AUC by 1.81% on OGBG-Molhiv and 1.02% on OGBN-Proteins;

We hope that this addition can provide a clearer overview and emphasizes the novelty of our work.

Weaknesses 2: Some Missing Background in Graph Sparsification

We appreciate the importance of situating our work within the broader context, including graph structure learning (GSL). In response, we have appropriately cited the references you provided and incorporated a discussion of the relevant works and their aspects in the revised manuscript under Appendix H.2. The key advantages of our approach over existing methods are as follows:

1. Seamless Integration: Unlike GSL methods, which often operate dependently of the backbone, MoG can be seamlessly embedded into various downstream graph tasks and GNN models. It functions as an effective sparsifier, inference accelerator, and performance enhancer without disrupting existing workflows.
2. Dynamic Local Adaptation: GSL methods typically rely on coarse-grained global metrics to evaluate topology importance and perform structure optimization. In contrast, MoG dynamically constructs sparse ego-graphs based on unique local contexts, thereby enhancing the quality and performance of the sparsified graph.
3. High Customizability: GSL methods often utilize a single metric for structural refinement, whereas MoG offers extensive customizability. It allows practitioners to tailor both sparsity criteria and levels to meet specific application needs. For example, in financial fraud detection, heterophilic pruning criteria can be applied, while in recommendation systems, PageRank-based pruning can be employed.

Weaknesses 3: Missing Experiment/Ablation Study

Thank you for suggesting an insightful baseline. We respectfully note that the idea you proposed closely resembles Local Degree [1], which we have already compared in our paper. The essence of Local Degree is to remove edges based on the node degrees of different nodes. To provide a clearer comparison between MoG and Local Degree, we have extracted the relevant experimental results from Table 1 in Section 4 and presented them as Table A. The results demonstrate that MoG consistently outperforms Local Degree across all datasets. We attribute this to MoG's consideration of a broader range of local context beyond just node degree, including node features, spectral information, gradients, and more.

Table A: Comparison of MoG and Local Degree on OGBN-ARXIV and OGBN-PROTEINS datasets using GraphSAGE backbone.

Dear Reviewer aseP,

We deeply appreciate your dedication to engaging in author-reviewer discussions. Here, we have outlined your key concerns and our responses for enhanced communication:

1. Making Contributions Clear Weakness 1 In response to your suggestion, we have included a dedicated section in Appendix H.1 that highlights our key contributions in clear and concise bullet points.
2. Some Missing Background in Graph Sparsification Weakness 2 We have respectfully cited the references you provided and included relevant discussions and comparisons. We sincerely thank you for helping us strengthen the presentation of our work!
3. Missing Experiment/Ablation Study Weakness 3 We are amazed by your keen academic intuition! Your suggestion aligns precisely with a classic graph sparsification baseline, Local Degree. We have included the relevant experiments accordingly.

We deeply and truly admire your academic intuition, and thank you immensely for your dedication to the reviewing process! We sincerely hope this addresses your concerns and look forward to further discussions.

Warm regards,

Authors

Question 2: What is the difference between observed average sparsity just after ensembling in eq. 13 and after the post-sparsification step of eq. 14? Curious to understand how much more the graph density changes after the optimization in eq 11.

Thank you for your insightful question! Pleasde allow us to clarify how the ego-graph of each node evolves throughout the process. Following Eq. (13), $k$ sparse ego-graphs $\{\widehat{\mathcal{G}}^{(i)}\_{m}\}_{m=1}^k$ are aggregated into a single representation $\widehat{\mathcal{G}^{(i)}} = \\{\widehat{\mathbf{A}^{(i)}}, \mathbf{X}^{(i)}\\}$. At this stage, $\widehat{\mathbf{A}^{(i)}}$ is derived from the ensembled Laplacian $\widehat{\mathbf{L}^{(i)}}$, which is inherently dense, i.e., it satisfies $||\widehat{\mathbf{A}^{(i)}}||_0 = \mathcal{E}^{(i)}$. We wish to emphasize that although $\widehat{\mathbf{A}}^{(i)}$ is dense at this stage, it is weighted—the weights are optimized on the Grassmann manifold, serving as critical guidance for the following post-sparsification process.

Subsequently, as described in Eq. (14), $\widehat{\mathcal{G}^{(i)}}$ undergoes further post-sparsification, adjusting to a sparsity level of $s^{(i)}\%$ based on the learned node connectivity strengths optimized on the Grassmann manifold.

[1] Edge sparsification for graphs via meta-learning

[2] Rigging the Lottery: Making All Tickets Winners

Weakness 3: What does $D$ in eq. 13 correspond to? Would it not introduce some approximation error since it doesn’t correspond exactly to the learned laplacian?

We are sorry for causing confusion! The reference to $D$ in Equation (13) was indeed a typo, and we have corrected it to $D^{(i)}$, which represents the degree matrix of the ego-graph for node $i$. Thank you immensely for your kind attention, and we sincerely hope this can address your concerns.

Weakness 4: The method seems entirely local. How does the proposed approach tackle the tasks which need global info?

Thank you for your insightful question, which has greatly helped us improve our work! We would like to clarify an important point: while MoG prunes edges based on the node’s local context, the edge importance evaluation function in Equation (9), $C^m(e_{ij}) = \operatorname{FFN}\left( x_i, x_j, c^m(e_{ij}) \right)$, can incorporate multi-hop or even global information. Specifically, we explored two easy-to-implement extensions and conducted supplementary experiments accordingly:

1. Expanding $x_v$ to $x_v^{(K)}$ with aggregated K-hop features:
   To integrate multi-hop information, we expanded $x_v$ into $x_v^{(K)} = \text{CONCAT}(h_v^{(1)}, h_v^{(2)}, \dots, h_v^{(K)})$, where $h_v^{(k)} = \frac{1}{|N_k(v)|} \sum_{u \in N_k(v)} x_u$ represents the K-hop features for node $v$, with $N_k(v)$ denoting the K-hop neighbors of $v$.

2. Incorporating $c^m(e_{ij})$ with prior global edge significance: For the $c^m(e_{ij})$ function in Eq. (9), we can consider global edge significance as prior guidance. This involved computing edge importance metrics such as PageRank, Betweenness Centrality, or Eigenvector Centrality across the entire graph and passing them to each ego graph to improve edge evaluation.

Table B: Performance of MoG-Khop with Multi-hop Features and MoG-m Incorporating Global Edge Significance as prior guidance on OGBN-Arxiv+GraphSAGE (node classification, 50% sparsity) and OGBN-PPA+DeeperGCN (graph classification, 50% sparsity).

As observed, the performance gain from integrating global information varies across different tasks: in tasks such as graph classification, which rely more heavily on global information, MoG-3hop results in a notable 1.15% accuracy improvement compared to MoG-1hop. However, in node classification tasks, the gains from both hop expansion and global priors are relatively limited. Nevertheless, we hope this addresses your concern, demonstrating that MoG can perform effectively even in scenarios where global information is crucial.

Question 1: Did we perform this qualitative analysis on an actual sparsified graph, or is it an imagined example to represent our hypothesis?

The example in Figure 1 (Middle) is hypothetical and designed to illustrate the motivation behind our method. Nevertheless, we are happy to introduce a qualitative analysis based on experiments conducted on real datasets, as shown in Table B.

Table B: Importance Scores of Different Criteria on Various Datasets.Experiments were conducted using the GraphSAGE with a sparsity level of 30%. $I_D$, $I_{JS}$, $I_{ER}$, and $I_{GM}$ denote the aggregated expert score proportions for Degree, Jaccard Similarity, ER, and Gradient Magnitude, respectively.

Our findings reveal significant differences in the distribution of expert scores across datasets. Notably, in OGBN-Arxiv, which has a low average node degree, the Degree criterion exhibits higher expert scores. Conversely, in highly connected datasets like OGBN-Products and OGBN-Proteins, the Gradient Magnitude criterion shows the highest expert scores.

This suggests that in graphs with low node connectivity, preserving important edges often relies more heavily on degree-based criterion to maintain graph connectivity. In contrast, in highly connected graphs, retaining important edges depends more on semantic information, such as gradient magnitude, which is learned during the training process. These observations align with the design principles of most state-of-the-art graph pruning methods, which prioritize node weights and gradients in their frameworks [1,2].

Thank you for your insightful comments and questions on our manuscript! We have carefully considered each point and have made the necessary revisions and clarifications to address your concerns:

Weakness 1: How are post-sparsified ego-graphs assembled? Is it possible that for two nodes and $i$ and $j$, the post-sparsified ego graph of $i$ and $j$ connects to $j$ but the post-sparsified ego graph of $j$ doesn’t connect to $i$? If yes, how is this handled?

How are post-sparsified ego-graphs assembled? We provide a detailed explanation of how post-sparsified ego-graphs are assembled as follows:

Dear Reviewer D6Ca,

We humbly appreciate your recognition and thoughtful feedback on our work! For a better understanding of our rebuttal and revision, we have summarized your key concerns and our responses as follows:

1. Ensembling Post-Sparsified Ego-Graphs Weakness 1
   We have provided a detailed explanation of how multiple ego-graphs are merged back into a single large graph, which inherently addresses the conflicts you mentioned.
2. Details on Parameter $k$ Weakness 2
   We elaborated on how $p$ is determined and reported its sensitivity analysis.
3. Can MoG Tackle Tasks Requiring Global Information? Weakness 4 We proposed two straightforward methods to incorporate global information into MoG and evaluated their performance.

For other issues not mentioned here, please refer to our detailed rebuttal response. We sincerely hope this addresses your concerns! We respectfully look forward to further discussion with you.

Warm regards,

Authors

Thank you for your valuable feedback on our manuscript! We have taken your comments seriously and have made the necessary revisions and additions to address the concerns raised. Below is our point-by-point rebuttal:

Weakness 1: Eq.11 is heuristic. Does the final ensembled sparse Laplacian truly integrate the eigenvectors of multiple sparsified ego-net Laplacians as the authors hope? Regardless of the degree achieved, it would be helpful to see experimental evidence here.

Thank you for your valuable suggestion! In response, we provide an illustrative case study in Appendix C.1 of the updated manuscript. Specifically, we examine how the Grassmann manifold enhances graph sparsification for the ego-graph (of node 2458) from the Ogbn-Arxiv dataset. We compare the original ego-graph, the sparse ego-graphs generated by three different sparsifiers, and the ensembled and post-sparsified ego-graphs derived through simple averaging and Grassmann optimization, as depicted in Figure 5. Our results demonstrate that simple averaging followed by sparsification leads to eigenvalue distributions that significantly deviate from the original graph. Conversely, the Grassmann ensembling method preserves the spectral properties of each graph view, producing a sparse ego-graph with an eigenvalue distribution that closely resembles that of the original graph. We believe this is because the post-sparsification is computed based on $\widehat{\mathbf{A}}^{(i)}$, which is optimized on the Grassmann manifold and better preserves the spectral information of multiple graph candidates.

Weakness 2: There are only two node classification and two graph classification datasets, which is relatively few.

Thank you for your insightful comment, which greatly enhances the quality of our paper! In response, we have included additional experiments on link prediction tasks, specifically using DeeperGCN with OGBN-COLLAB and GIN with Pubmed, as shown in Table A and Table B, respectively. The link prediction experimental settings follow [1].

These additions allow us to thoroughly evaluate our method across three major graph tasks—graph classification, node classification, and link prediction. The experiments now cover four sparsity levels, six backbones, and eight datasets, offering a comprehensive assessment of our approach under various conditions.

Table A: Additional Experiments on DeeperGCN + OGBL-COLLAB. The reported metrics represent the average of Five runs. (Metric = Hits@50, Baseline = 53.53%)

Table B: Additional Experiments on GIN + Pubmed. The reported metrics represent the average of Five runs. (Metric = ROC-AUC, Baseline = 0.895)

Through the experiments in Tables A and B, we further verified that MoG is also effective in the link prediction task, demonstrating strong generalization across diverse datasets and backbones.

We hope that these revisions properly address your concerns, and we are more than glad to respond to any further questions!

[1] A Unified Lottery Ticket Hypothesis for Graph Neural Networks. ICML 2021

Dear Reviewer XfnA,

We sincerely appreciate your high commendation and thorough feedback on our work! To aid in better understanding our rebuttal and revision, we have summarized your key concerns and our responses as follows:

1. How is the Final Ensembled Sparse Laplacian useful? Weakness 1
   As visualized in Appendix C.1 of the updated manuscript, compared to simply averaging $K$ sparse ego-graphs, the use of $\widehat{\mathbf{A}^{(i)}}$, optimized on the Grassmann manifold, better approximates the eigenvalue distribution of the original ego-graph.
2. Insufficient Experiments Weakness 2
   Respectfully following your suggestion, we have added two additional link prediction tasks. Notably, MoG has now been extensively validated across four sparsity levels, six backbones, and eight datasets, and we are deeply grateful for your valuable feedback.

Thank you very much for your dedication to the reviewing process. We sincerely hope this addresses your concerns and look forward to further discussions.

Warm regards,

Authors

Weakness 1.3: Different sparsity combinations are applied in different datasets without an explanation of the selection rationale.

In the manuscript, we selected specific combinations of sparsity levels for different datasets to achieve the target sparsities of \\{10\\%, 30\\%, 50\\%, 70\\%\\}, which allows for a fair comparison with other graph sparsification methods under the same sparsity conditions. This is because, even with the same sparsity combination, MoG optimizes a distinct global sparsity for each dataset due to its high customizability. Therefore, we adjusted the sparsity combinations for different datasets to closely match the desired sparsity levels, which also guarantees the reproducibility of our paper.

We would like to emphasize, however, that these configurations are fully customizable, allowing users to adjust them according to their specific requirements and data scenarios.

Weakness 2: The process of integrating sparse subgraphs on the Grassmann manifold is mathematically dense and lacks intuitive explanation. While the theoretical basis is strong, the connection between the Grassmann manifold’s properties and its benefits for graph sparsification may not be immediately clear to all readers.

Thank you for your thoughtful question! We aim to address your concerns from both theoretical and practical perspectives.

From a theoretical standpoint, the Grassmann manifold is fundamentally tied to the construction of the first $p$ eigenvectors, ensuring the orthogonality of eigenvectors corresponding to distinct eigenvalues and the normalized norm property of each eigenvector. By incorporating these constraints into the optimization problem, the solution is guided towards a matrix that exhibits "eigenvector-like" characteristics, aligning naturally with the graph Laplacian structure used in our framework. While it is true, as you noted, that the ego-graph integrated by the Grassmann manifold is mathematically dense, its adjacency matrix $\widehat{\mathbf{A}}^{(i)}$ is weighted. These weights are optimized on the Grassmann manifold, serving as a solid foundation for subsequent post-sparsification. A straightforward way to test the necessity and effectiveness of the Grassmann manifold is to directly apply expert scores to perform a weighted average of the sparse ego-graphs, followed by post-sparsification, rather than employing Eq. (11). To validate the necessity of the Grassmann manifold, we provide an experimental comparison in the next paragraph.

From a practical standpoint, we provide an illustrative case study in Appendix C.1 of the updated manuscript. Specifically, we examine how the Grassmann manifold enhances graph sparsification for the ego-graph of a node (node 2458) from the Ogbn-Arxiv dataset. We compare the original ego-graph, the sparse ego-graphs generated by three different sparsifiers, and the ensembled ego-graphs derived through simple averaging and Grassmann optimization, as depicted in Figure 5. Our results demonstrate that simple averaging followed by sparsification leads to eigenvalue distributions that significantly deviate from the original graph. Conversely, the Grassmann ensembling method preserves the spectral properties of each graph view, producing a sparse ego-graph with an eigenvalue distribution that closely resembles that of the original graph.

In summary, we respectfully argue that employing the Grassmann manifold for sparse graph construction provides both theoretical and practical advantages by preserving the spectral properties of the graph, enabling more informed and effective graph sparsification.

Weakness 3: The terminology for sparsifiers and experts appears inconsistent across sections.

Thank you for wisely pointing this out! In MoG, the term "expert" is equivalent to "sparsifier expert", as illustrated in the third subfigure of Figure 2. In some instances, to emphasize the functionality of the "expert", we also refer to it as the "sparsifier expert".

In our manuscript, "sparsifier" may refer to the "sparsifier expert of MoG", "ego-graph sparsifier" or "full-graph sparsifier", which could lead to ambiguity. To avoid this confusion, we have consistently referred to the sparsifier expert of MoG as "sparsifier expert" or "expert" in the revised manuscript.

Weakness 4: Typos in the paper

Thank you for your detailed review and for kindly pointing out the spelling errors in our manuscript. We have addressed the issues you mentioned and conducted a thorough review of the entire document to identify and correct additional errors, such as changing "paramter" to "parameter" in Section 4.3 (obs5) and "NETWOR" to "NETWORK" in the title of G.3. These corrections have been incorporated into the revised manuscript.

Thank you for your thorough review and insightful comments on our manuscript! We have carefully considered your feedback and have made the following revisions and clarifications to address the raised concerns.

Weakness 1.1: Why select the specific 12 combinations of sparsity levels and criteria?

In the manuscript, we select these sparsity criteria because they are representative and easy to compute. However, we respectfully emphasize that the combinations of sparsity levels and criteria in MoG can be easily customized for practitioners.

Furthermore, we use twelve candidate experts because the MoG method achieves a better balance between computational load and performance in this setup. To illustrate this point, Table B illustrates the inference time and accuracy of MoG with varying candidate experts $K$. It can be observed that MoG achieves the highest performance at $K=12$ with acceptable additional per-epoch time.

Table B: Inference Time & Accuracy of MoG with varying candidate experts $K$ when applyng MoG to OGBN-PROTEINS+GraphSAGE with $k=2$.

Weakness 1.2: Additionally, the variance of each row across combinations in Table 8 is minimal, raising questions about the distinctiveness of each sparsifier.

Thank you for your detailed review and thoughtful comment! We selected the sparsity combinations presented in Table 8 as the final configuration in the paper to ensure reproducibility and enable a fair comparison with other baseline methods. However, we respectfully emphasize that this does not indicate any incompatibility of MoG with sparsity combinations exhibiting higher variance. To substantiate this, we conducted additional experiments:

We tested a broader range of sparsity configurations with greater variance on the GraphSAGE + OGBN-Arxiv dataset. As shown in Table C, while the sparsifiers in the third row demonstrate significantly higher variance compared to those in the first row, the resulting global sparsity remains largely consistent. This outcome arises from MoG's ability to dynamically adjust expert loads, allocating fewer resources to high-sparsity experts (e.g., $15\%$ for $(1 - s_3) = 0.2$), thereby balancing the overall sparsity. This observation leads us to conclude that, regardless of differing sparsity combinations, MoG is capable of adjusting the expert load dynamically to approximate a suitable sparsity level for the graph data.

We hope this additional experiment demonstrates MoG's customizability and broad adaptability.

Table C: Performance of different sparsity level combinations when applying MoG to OGBN-ARXIV with GraphSAGE. In the table, $s_i$ represents the sparsity of the $i$-th sparsifier, and $l_i$ denotes its load.

Dear Reviewer f3PB,

We would like to extend heartfelt thanks to you for your time and efforts in the engagement of the author-reviewer discussion. To facilitate better understanding of our rebuttal and revision, we hereby summarize your key concerns and our responses as follows:

1. Explanation of MoG's Sparsity Combination Weakness 1 We respectfully clarify that (1) $K=12$ represents the optimal trade-off between performance and computational efficiency for MoG, and (2) MoG is inherently adaptable to sparsity combinations with greater variance.
2. Variation of Sparsity Combination Across Datasets Weakness 1 This variation arises from the need to tune MoG to achieve the desired global sparsity, enabling fair comparisons with other graph sparsification methods under similar sparsity levels.
3. How the Grassmann Manifold Benefits Graph Sparsification Weakness 2 The weighted ego-net adjacency matrix $\widehat{\mathbf{A}^{(i)}}$ is optimized on the Grassmann manifold, efficiently preserving the spectral properties of each graph view and effectively informing the subsequent post-sparsification procedure.

For other issues not mentioned here, please refer to our detailed rebuttal response. We sincerely hope this addresses your concerns! We respectfully look forward to further discussion with you.

Warm regards,

Authors

We extend our heartfelt thanks to Reviewer f3PB for their increased support of our paper! We are pleased that our rebuttal have sufficiently addressed your concerns.