Nonparametric estimation and testing of exchangeable graph models

Justin Yang, Christina Han, Edoardo Airoldi
; Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:1060-1067, 2014.

Abstract

Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data.

Cite this Paper


BibTeX
@InProceedings{pmlr-v33-yang14c, title = {{Nonparametric estimation and testing of exchangeable graph models}}, author = {Justin Yang and Christina Han and Edoardo Airoldi}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {1060--1067}, year = {2014}, editor = {Samuel Kaski and Jukka Corander}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/yang14c.pdf}, url = {http://proceedings.mlr.press/v33/yang14c.html}, abstract = {Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data.} }
Endnote
%0 Conference Paper %T Nonparametric estimation and testing of exchangeable graph models %A Justin Yang %A Christina Han %A Edoardo Airoldi %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-yang14c %I PMLR %J Proceedings of Machine Learning Research %P 1060--1067 %U http://proceedings.mlr.press %V 33 %W PMLR %X Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data.
RIS
TY - CPAPER TI - Nonparametric estimation and testing of exchangeable graph models AU - Justin Yang AU - Christina Han AU - Edoardo Airoldi BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics PY - 2014/04/02 DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-yang14c PB - PMLR SP - 1060 DP - PMLR EP - 1067 L1 - http://proceedings.mlr.press/v33/yang14c.pdf UR - http://proceedings.mlr.press/v33/yang14c.html AB - Exchangeable graph models (ExGM) are a nonparametric approach to modeling network data that subsumes a number of popular models. The key object that defines an ExGM is often referred to as a graphon, or graph kernel. Here, we make three contributions to advance the theory of estimation of graphons. We determine conditions under which a unique canonical representation for a graphon exists and it is identifiable. We propose a 3-step procedure to estimate the canonical graphon of any ExGM that satisfies these conditions. We then focus on a specific estimator, built using the proposed 3-step procedure, which combines probability matrix estimation by Universal Singular Value Thresholding (USVT) and empirical degree sorting of the observed adjacency matrix. We prove that this estimator is consistent. We illustrate how the proposed theory and methods can be used to develop hypothesis testing procedures for models of network data. ER -
APA
Yang, J., Han, C. & Airoldi, E.. (2014). Nonparametric estimation and testing of exchangeable graph models. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in PMLR 33:1060-1067

Related Material