GraphFLEx: Structure Learning Framework for Large Expanding Graphs
This addresses scalability bottlenecks in graph-based machine learning for applications with expanding graphs, though it is incremental as it builds on existing techniques.
The paper tackles the problem of graph structure learning for large and dynamically evolving graphs, which often require costly re-learning, by proposing GraphFLEx, a framework that restricts edge formation to relevant subsets using clustering and coarsening, achieving state-of-the-art performance with improved scalability across 26 datasets.
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.