Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data

Antonino Freno, Mikaela Keller, Gemma C. Garriga, Marc Tommasi
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:263-272, 2012.

Abstract

Generative models for graphs have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are either only suitable for characterizing some particular network properties (such as degree distribution or clustering coefficient), or they are aimed at estimating joint probability distributions, which is often intractable in large-scale networks. In this paper, we first propose a novel network statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random graph model, switching the focus from the estimation of joint probability distributions to a more tractable conditional estimation setting. After analyzing the dependence structure characterizing Fiedler random graphs, we evaluate them experimentally in edge prediction over several real-world networks, showing that they allow to reach a much higher prediction accuracy than various alternative statistical models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-freno12a, title = {Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data}, author = {Freno, Antonino and Keller, Mikaela and Garriga, Gemma C. and Tommasi, Marc}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {263--272}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/freno12a/freno12a.pdf}, url = {https://proceedings.mlr.press/r10/freno12a.html}, abstract = {Generative models for graphs have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are either only suitable for characterizing some particular network properties (such as degree distribution or clustering coefficient), or they are aimed at estimating joint probability distributions, which is often intractable in large-scale networks. In this paper, we first propose a novel network statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random graph model, switching the focus from the estimation of joint probability distributions to a more tractable conditional estimation setting. After analyzing the dependence structure characterizing Fiedler random graphs, we evaluate them experimentally in edge prediction over several real-world networks, showing that they allow to reach a much higher prediction accuracy than various alternative statistical models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data %A Antonino Freno %A Mikaela Keller %A Gemma C. Garriga %A Marc Tommasi %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-freno12a %I PMLR %P 263--272 %U https://proceedings.mlr.press/r10/freno12a.html %V R10 %X Generative models for graphs have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are either only suitable for characterizing some particular network properties (such as degree distribution or clustering coefficient), or they are aimed at estimating joint probability distributions, which is often intractable in large-scale networks. In this paper, we first propose a novel network statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random graph model, switching the focus from the estimation of joint probability distributions to a more tractable conditional estimation setting. After analyzing the dependence structure characterizing Fiedler random graphs, we evaluate them experimentally in edge prediction over several real-world networks, showing that they allow to reach a much higher prediction accuracy than various alternative statistical models. %Z Reissued by PMLR on 04 October 2026.
APA
Freno, A., Keller, M., Garriga, G.C. & Tommasi, M.. (2012). Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:263-272 Available from https://proceedings.mlr.press/r10/freno12a.html. Reissued by PMLR on 04 October 2026.

Related Material