GraphFLEx: Structure Learning $\underline{\text{F}}$ramework for $\underline{\text{L}}$arge $\underline{\text{Ex}}$panding $\underline{\text{Graph}}$s

We sincerely thank the reviewer for their thoughtful feedback and for recognizing the potential of our work. We appreciate the reviewer’s positive response and for highlighting areas where the manuscript can be further improved.

W1 and Q1) We would like to clarify that along with K-means and spectral clustering, GraphFLEx also employs some very recent and advanced methods for both clustering and coarsening. For clustering, we employ DMoN (JMLR 2023); for coarsening, we integrate FACH (2023), FGC (JMLR 2023), and UGC (NeurIPS 2024), all of which are recent and well-established techniques, ensuring GraphFLEx aligns with the latest advancements in graph learning.

There are 3 different modules in GraphFLEx : clustering, coarsening, and the learning module. All 3 controls distinct properties. Altering any of these modules results in a new graph learning method. This flexibility allows seamless integration of newer methods, ensuring that GraphFLEx remains scalable and adaptable.

W2 and Q2) We appreciate the reviewer’s concern and have included the link prediction experiments in the table below. As shown, the structure learned by GraphFLEx performs well on link prediction, sometimes even surpassing the results on the base structure, demonstrating its effectiveness. The table below follows the same configuration as presented in Table 4 in the main manuscript.

For graph classification, its applicability depends on the nature of the dataset. This task often involves multiple small subgraphs, as seen in applications like molecule or drug discovery, where subgraphs are inherently small. Since GraphFLEx integrates clustering, coarsening, and learning, the first two steps become redundant in such scenarios. Applying clustering and coarsening to small subgraphs may lead to unnecessary computational overhead without adding value.

However, GraphFLEx can still be effectively applied to graph classification tasks by bypassing the clustering and coarsening steps and directly using its learning module to train models for classification. This flexibility ensures that GraphFLEx can adapt to different types of downstream tasks while maintaining its efficiency.

Appeal to Reviewer: We again thank you for the insightful comments on our work. We will incorporate your suggestions into the revised manuscript. Please let us know if there are any remaining concerns or clarifications needed. As we approach the final stage, we would greatly value your positive support.

Best regards,

Authors

We thank the reviewer for the thoughtful feedback and for recognizing the potential of our work. We appreciate the detailed insights and suggestions for improvement.

Missing references: Thankyou for pointing this out. We have added Table1 comparing vanilla SUBLINE[2] vs. GFLEx, where GFLEx significantly outperforms SUBLINE. We assure that pointed references will be added in the revised paper.

Table1: Time(sec) and acc(%).

Also, any other SOTA methods can be easily integrated into GFLEx, as it scales structure learning using existing techniques. In terms of computational time, GFLEx remains the preferred choice since it learns the structure using only a concise set of potential nodes.

A1: We acknowledge that GFLEx builds on existing methods to scale GSL. However, while much research has focused on improving graph model architectures, GSL itself remains underexplored. GFLEx addresses this gap by introducing a novel combination of clustering and coarsening to reduce the number of potential nodes for structure learning.

Beyond efficiency GFLEx offers 48 structure learning options integrating clustering, coarsening, & learning into a single pipeline. This unified framework enables diverse structure learning strategies without multiple tools. We believe these contributions significantly advance structure learning especially for large, expanding graphs.

A2: Thankyou for your thoughtful comment. Currently, GFLEx supports K-means, Spectral & Deep Learning-based clustering methods, each with unique strengths suited to different scenarios:

• K-means is computationally efficient & works well when clusters have a well-defined spherical structure. It is useful for large-scale datasets where speed is a priority.
• Spectral Clustering leverages eigenvalue decomposition making it effective for capturing complex graph structures, especially when communities are not clearly separable using simple distance metrics. However, it can be computationally expensive for large graphs.
• Deep Learning-based Clustering adapts well to non-linear & high-dimensional patterns, making it a good choice for complex & feature-rich graph data, though it requires more computational resources.

We will incorporate this discussion in Appendix

A3: Thankyou for highlighting this. In response, we have included experiments on larger datasets: ogbn-arxiv (169K nodes), ogbn-products (2.45M), Flickr (89K), and Reddit (233K). Please note that given the large node count these experiments were conducted on a different machine distinct from the one used for earlier experiments. Spec.: Intel Xeon Platinum 8360Y CPU, 1.0 TiB RAM, & NVIDIA RTX A6000 (48 GiB VRAM).

Table2: Time(sec)

Table3: Node classification acc

Table2 shows that GFLEx scales effectively to larger datasets & is the fastest among all baselines. Notably, methods like log, L2 & large models fail even on Flickr dataset, where GFLEx successfully scales them on Flickr, arxiv & Reddit. However, due to high computational cost of these methods GFLEx is unable to scale structure learning for them on ogbn-products dataset. We aim to further improve GFLEx's scalability in future work.

Table 3 highlights the quality of learned structure on these large datasets through node classification acc. GFLEx maintains acc comparable to base structure (shown in parentheses with dataset).

A4: To evaluate the effectiveness of these clustering methods we have conducted experiments (Table5) using NMI, Conductance & Modularity. Since clustering in GFLEx is applied only once on a randomly sampled small set of nodes selecting right method can be considered as part of hyperparameter tuning, where these clustering measures can guide the optimal choice based on dataset characteristics.

Appeal to Reviewer: Thankyou again for your insightful comments. Please let us know if any concerns remain. Otherwise, we would really appreciate it if you could support the paper by increasing the score.

Best regards,

Authors

We thank the reviewer for the thoughtful feedback and for recognizing the potential of our work. We appreciate the detailed insights and suggestions for improvement.

Complexity: We clarify that Sec3.6 and Table2 breaks down the complexity for both (a)best & (b)worst scenarios, highlighting each module. To improve, we explain each module's contribution and highlight GFLEx's linear & sub-linear time complexity. In clustering: kNN is the fastest $O(k^2)$, while spectral clustering is slowest $O(k^3)$. Since clustering is applied to randomly sampled, smaller subgraph with $k \ll N$ nodes, the cost is constant. For coarsening: FACH & UGC achieve best complexity: $O(\frac{k_\tau}{c})$, while FGC denotes the worst case with $O((\frac{k_\tau}{c})^2 |S_\tau^i|)$, where $c$ is number of communities, $|S_\tau^i|$ is number of coarsened nodes & $k_\tau$ is number of nodes at time $\tau$. For learning module, ANN is the most efficient with $O(N \log N)$, while GLasso is worst with $O(N^3)$. Therefore, GFLEx’s overall complexity is bounded between $O(k^3 + (\frac{k_\tau}{c})^2 |S_\tau^i| + \alpha^3)$ and $O(k^2 + \frac{k_\tau}{c} + \alpha \log \alpha)$, where $\alpha = |S_\tau^i| + |E^i_\tau|$. $M_{clust}$ is trained once keeping its runtime bounded, $M_{coar}$ also remains controlled as some methods have linear complexity. Thus, both of these contribute linearly to the overall time, denoted as $O(N)$. The total complexity of GFLEx is $O(N + M_{gl}(|S_i, X^i\tau|))$, scaling linearly or sub-linearly based on $\alpha$ & $M_{gl}$. For eg, ANN maintains linear complexity if $\alpha \log(\alpha) \approx N$, while GLasso exhibits linear behavior when $\alpha^3 \approx N$.

Motivation: The Intro is structured to gradually build motivation, first highlighting the ubiquity of graph data (Intro:para1) & the necessity of GSL (para2). Para3 states key challenges:scalability & adaptability before presenting GFLEx(para4). Sec2 formally defines these challenges (Goal1&2), & Sec3 details how GFLEx efficiently achieves these goals. To enhance we will refine Intro by adding:

"Real-world graphs continuously expand for eg, e-commerce networks accumulate new transactions daily, academic networks grow with new publications, financial & social graphs evolve with ongoing interactions. These dynamic changes require efficient methods that can incrementally learn graph structures rather than recomputing them from scratch. However, existing approaches struggle with expanding graphs."

This will provide a stronger motivation by first illustrating real-world scenarios where graph expansion is inevitable then naturally transitioning into limitations of SOTA.

Methodology, Figure & Theoritical Framework: Our intention was to introduce the methodology progressively across multiple sections to maintain a coherent narrative. To enhance understanding, we’ve updated Fig2 & refined caption summarizing the methodology, updated Fig2: https://t.ly/URWmZ.

Additionally Theorem1 states that with a constant probability of success the neighbor of incoming nodes $N_k(E_i)$ can be effectively recovered using GFLEx’s multi-step approach to establish the theoretical foundation.

Assumption1: It is grounded in the well-established homophily principle which forms the basis of most graph coarsening & learning methods. To formalize this we assume that the generated graphs follow the DCSBM, an extension of SBM that accounts for degree heterogeneity, making it a more flexible & realistic choice for real-world networks. We acknowledge that the justification for this assumption could be more explicit & we will enhance this explanation in the revised version to improve clarity.

Ans-Other Comments:

• We have revised it to: Vanilla KNN failed to construct graph structures for more than 10K nodes due to memory limitations.
• Specifications used for experiments (also in Sec4): Intel Xeon W-295 CPU & 64GB RAM using Python environment; OOM: Execution failure due to memory constraints; OOT: Execution exceeding 100k seconds (~28 hours).
• Yes results are in seconds.

Ans-Questions:

• Most graph research focuses on developing deep learning architectures, often overlooking the critical role of graph structure. Structure learning remains underexplored, with existing methods struggling to scale for large & expanding graphs. We aim to bridge this gap by using clustering & coarsening techniques to enable efficient structure learning at scale.

• Table4 shows results of various GNN models on base structure reflecting SOTA performance. These results show that GFLEx maintains good node classification acc while outperforming existing structure-learning methods.

Appeal to Reviewer: Thankyou again for your insightful comments. We will incorporate your suggestions into the revised manuscript. Please let us know if any concerns remain. Otherwise, we would really appreciate it if you could support the paper by increasing the score.

Best regards

Authors