---
title: "A Deterministic Partition Function Approximation for Exponential Random Graph Models"
authors:
  - "Wen Pu"
  - "Jaesik Choi"
  - "Yunseong Hwang"
  - "Eyal Amir"
doi: ""
url: "https://ijcai.org/proceedings/2015/34"
pdf: "https://ijcai.org/proceedings/2015/0034.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "192-199"
track: "Main Track"
keywords:
---

# A Deterministic Partition Function Approximation for Exponential Random Graph Models

Wen Pu, Jaesik Choi, Yunseong Hwang, Eyal Amir

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, 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.