A fast structured regression for large networks

Structured regression has been successfully used in many applications where explanatory and response variables are inter-correlated, such as in weighted attributed networks. One of structured models, Gaussian Conditional Random Fields (GCRF), utilizing multiple unstructured models to learn the non-linear relationships between node attributes and the structured response variable, achieves high prediction accuracy. However, it does not scale well with large networks. We propose a novel model, called Scalable Approximate GCRF (SA-GCRF), which integrates weighted attributed network compression with GCRF, with the aim of making GCRF applicable to large networks. The model consists of three steps: first, it compresses a network into a smaller one by generalizing nodes into supernodes and edges into superedges; then, it applies GCRF to the reduced network; and finally, it unfolds the predicted response variables into the original nodes. Our hypothesis is that the reduced network maintains most information of the original network such that the loss in prediction accuracy obtained by GCRF on the reduced network is minor. The comprehensive experimental results indicate that SA-GCRF was 150-520 times faster than standard GCRF and 11-29 times faster than state-of-the-art UmGCRF on large networks, and provided regression results where GCRF and UmGCRF were not applicable. Furthermore, SA-GCRF achieved a similar regression accuracy, 0.76, to the one obtained from the original real-world weighted attributed citation network, even after compressing the network to 10% of its size.