GPU-Accelerated Kronecker Graph Fitting and a General Framework for Graph Structure Descriptor Language Models

Abstract

Understanding the complex behaviors of large-scale graphs is an important task. It helps us comprehend phenomena like the spread of viruses across online networks, the spread of diseases, and the spread of tumors in the brain, etc. Using graph models as surrogates for real data allows domain experts to analyze the behavior of these networks from compact representations. This requires fitting model parameters for the given graph data. For dense graphs, these can be processed with relative ease due to the performance improvements made over time; however, problems arise when the graphs are sparse, as most existing methods for dense graphs are not designed for graphs where the computation performed is affected by their structure. For hyper-sparse graphs, KronFit addresses this challenge by fitting the parameters to a Kronecker graph model. These parameters can be used to recreate a synthetic graph with similar properties to the original graph to understand their underlying workings. However, these tools are limited to singular models, like KronFit for Kronecker graphs and MAGfit for multiplicative Attribute graphs. They are sequential, meaning that for large enough graphs, the computation time to run these tools is too high to be usable. We present MFit, a heterogeneous CPU--GPU pipeline for Kronecker graph fitting that runs Metropolis--Hastings MCMC permutation sampling on the CPU and offloads likelihood and gradient computations to thousands of GPU cores in parallel. MFit frames graph model fitting as a modern machine learning optimization task, leveraging PyTorch automatic differentiation and the Adam optimizer in place of hand-derived gradient calculations. Evaluated across 20 benchmark graphs, MFit achieves speedups exceeding $10\times$ over KronFit while producing equal or better parameter recovery quality, making it a practical choice at scales where single-core fitting becomes intractable. We also extend MFit into GSDLFit, a more general fitting framework that can fit any graph model expressible in the Graph Structure Descriptor Language, not just Kronecker graphs.