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

Graph structure learning is a core problem in graph-based machine learning, essential for uncovering latent relationships and ensuring model interpretability. However, most existing approaches are ill-suited for large-scale and dynamically evolving graphs, as they often require complete re-learning of the structure upon the arrival of new nodes and incur substantial computational and memory costs. In this work, we propose GraphFLEx—a unified and scalable framework for Graph Structure Learning in Large and Expanding Graphs. GraphFLEx mitigates the scalability bottlenecks by restricting edge formation to structurally relevant subsets of nodes identified through a combination of clustering and coarsening techniques. This dramatically reduces the search space and enables efficient, incremental graph updates. The framework supports 48 flexible configurations by integrating diverse choices of learning paradigms, coarsening strategies, and clustering methods, making it adaptable to a wide range of graph settings and learning objectives. Extensive experiments across 26 diverse datasets and graph neural network architectures demonstrate that GraphFLEx achieves state-of-the-art performance with significantly improved scalability. Our implementation is publicly available here: https://anonymous.4open.science/r/ScalingGraphLearning-CB67/README.md.

Many important datasets are networks: people connected in social platforms, papers connected by citations, products connected by user behavior, or molecules connected through interactions. Often, these connections are missing, noisy, or keep changing as new items arrive. This makes it difficult to use machine learning methods that rely on having a good network structure. We introduce GraphFLEx, a method for building and updating such networks efficiently. Instead of comparing every item with every other item, GraphFLEx first finds smaller relevant groups and then searches for connections only within the most promising parts of the data. This greatly reduces the time and memory needed to build the network. GraphFLEx can work when the original network is completely missing, and it can also update an existing network as new items arrive, without rebuilding everything from scratch. Across many datasets, it scales to networks with millions of items where several existing methods are too slow or run out of memory. The networks learned by GraphFLEx remain useful for tasks such as predicting categories, missing links, and properties of small graphs. Overall, GraphFLEx makes network-based machine learning more practical for large and continuously growing real-world data.