A Deterministic Partition Function Approximation for Exponential Random Graph Models

Pu, Wen; Choi, Jaesik; Hwang, Yunseong; Amir, Eyal

A Deterministic Partition Function Approximation for Exponential Random Graph Models

Wen Pu, Jaesik Choi, Yunseong Hwang, Eyal Amir

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 192-199.

Abstract

Exponential Random Graphs Models (ERGM) are common, simple statistical models for social network and other network structures. Unfortunately, inference and learning with them is hard even for small networks because their partition functions are intractable for precise computation. In this paper, we introduce a new quadratic time deterministic approximation to these partition functions. Our main insight enabling this advance is that subgraph statistics is sufficient to derive a lower bound for partition functions given that the model is not dominated by a few graphs. The proposed method differs from existing methods in its ways of exploiting asymptotic properties of subgraph statistics. Compared to the current Monte Carlo simulation based methods, the new method is scalable, stable, and precise enough for inference tasks.

Wen Pu, Jaesik Choi, Yunseong Hwang, and Eyal Amir. 2015. A Deterministic Partition Function Approximation for Exponential Random Graph Models. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 192–199. https://ijcai.org/proceedings/2015/34

@inproceedings{ijcai2015p34,
  title     = {A Deterministic Partition Function Approximation for Exponential Random Graph Models},
  author    = {Pu, Wen and Choi, Jaesik and Hwang, Yunseong and Amir, Eyal},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {192--199},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/34},
}

TY  - CPAPER
TI  - A Deterministic Partition Function Approximation for Exponential Random Graph Models
AU  - Pu, Wen
AU  - Choi, Jaesik
AU  - Hwang, Yunseong
AU  - Amir, Eyal
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 192
EP  - 199
UR  - https://ijcai.org/proceedings/2015/34
ER  -