面向大规模网络分析的贝叶斯随机块模型与算法研究

Stochastic blockmodeling (SBM) is an important statistical network representation model, with good representing ability, generalization ability, interpretability and flexibility, and has become an important study of network theory. However，learning the optimal SBM for a given network is a NP-hard problem. Too much computational overhead makes the existing SBM models and their learning methods can only deal effectively with small-scale networks, which results in great limitations of applications. How to significantly reduce the cost of SBM learning and making it scalable for handling large-scale networks while maintaining the good theoretical properties of SBM remains an unresolved problem. In this project, we will address this challenging task from a novel perspective of model re-parameterization, and comprehensively study related theories, models, and algorithms, by posing and investigating some fundamental research questions that to date have not been addressed in the literature. First, how to construct a re-parameterized SBM with good theoretical properties and develop its efficient learning algorithm. Second, how to analyze the two important theoretical properties, resolution limit and detectability, of the re-parameterized SBM. Third, how to extend the re-parameterized SBM to deal with complicated real-world networks, e.g., the networks with heterogeneous degree distributions and overlapped block structures and the multiplex networks containing multiple layers. Fourth, how to construct distributed and parallel learning algorithm for the re-parameterized SBM. Based on the above, a theoretical and algorithmic framework of Bayesian stochastic blockmodelling for large-scale network analysis will be established. The implementation of this project will deepen, promote and expand the studies and applications of related areas including mining and learning from large-scale network data.

随机块模型是一类重要的统计网络表示模型，具有良好的表达能力、泛化能力、可解释性和灵活性，成为网络理论的重要研究对象。为给定的网络学习到最优的随机块模型是一个NP难问题，过高的计算开销使得现有的模型和方法仅能有效处理小规模网络，具有很大的局限性。如何在保持良好理论性质的前提下，显著降低随机块模型的学习开销，使其具有处理大规模网络的可伸缩性，仍是一个未被解决的难题。针对该问题，本项目拟从模型重参化这一新的角度入手，深入开展相关理论、模型及算法的研究，解决如下关键问题：如何构造出具有良好理论性质的重参化随机块模型及高效学习算法，如何分析重参化随机块模型的分辨率限制和识别性，如何扩展重参化随机块模型以处理形式多样的网络，如何构造出重参化随机块模型的分布并行学习算法，进而建立一个面向大规模网络分析的贝叶斯随机块理论和算法框架。本项目的实施将深化拓展大规模网络数据挖掘与学习等相关领域的研究与应用。

复杂网络广泛存在于现实世界中。随机块模型（SBM）因具有良好的理论性质（表达能力、可解释性、泛化能力和灵活性），成为网络理论的重要研究对象。为给定的网络学习到最优的随机块模型（SBM学习）是一个NP难问题，过高的计算开销使得SBM无法处理大规模网络，限制了SBM的应用范围。如何在保持良好理论性质的前提下，显著降低SBM的学习开销，使其具有处理大规模网络的可伸缩性，仍是一个未被解决的难题。为此，本项目从模型重参化这一角度入手，从模型、算法、理论以及并行化等方面开展研究，提出了面向大规模分析的贝叶斯SBM理论和算法框架。本项目的主要创新点是：.（1）提出了重参化SBM和高效学习机制。与现有模型相比，该模型不仅保持了良好的理论性质，还具有处理大规模网络的可伸缩性，大规模提高了在普通PC上有效处理的网络的规模；.（2）提出了具有层次贝叶斯结构的无信息先验构造方法和识别性分析新方法，研究了分辨率限制和网络噪声问题；.（3）提出了度校正、属性和符号重参化SBM，以有效处理异构网络、属性网络和符号网络；.（4）提出了面向重参化随机块模型的两阶段分布并行学习算法，借助并行计算平台，进一步提升了有效处理的网络规模。.这些工作系统解决了SBM学习开销过高的问题，深化拓展大规模网络数据挖掘与学习等相关领域的研究与应用。项目组在IEEE TPAMI、IEEE TKDE、NeurIPS、AAAI、WWW、ICLR等人工智能和数据挖掘领域著名期刊和会议上发表署名论文35篇。其中包括：SCI论文16篇，CCF A类论文6篇，CCF B类论文9篇，CCF C类论文11篇，中科院一区论文7篇、二区3篇。获得2021年吉林省自然科学一等奖1项、2020年中国商业联合会科学技术奖一等奖1项。这些工作引起了国内外同行的广泛关注，相关工作多次被国内外著名科研机构、著名学者以及人工智能、深度学习、数据挖掘等领域的顶级期刊和会议论文介绍、评价和对比。