Distributed Gaussian Conditional Random Fields Based Regression for Large Evolving Graphs

Dynamics of many real-world systems are naturally modeled by structured regression of representationally powerful Gaussian conditional random fields (GCRF) on evolving graphs. However, applications are limited to small and sparse evolving graphs due to high computational cost of the GCRF learning and inference. In this study, a new method is proposed to allow applying a GCRF model to large and extremely dense evolving graphs. Efficiency issues are addressed by graph partitioning and application of the GCRF model to each partition independently and in parallel. The hypothesis evaluated in this project is that the robustness of GCRF allows distributed learning of accurate regression models as long as most of the nodes after the graph partitioning are still linked to a subset of their heavily connected neighbors. To evaluate this hypothesis, GRCF-based distributed regression experiments were conducted on synthetic and two real-world evolving networks. The obtained results provide evidence that the proposed approach greatly speeds up time needed for modeling large graphs while obtaining accurate models. Finally, a simple graph characterization is proposed that, when satisfied allows application of distributed GCRF regression to extremely big graphs without construction of the entire graph