# BA 990.03 Spring
2020

## Statistical Inference on Graphs

**Overview and Objectives **

An emerging research thread in statistics and machine learning deals with finding latent structures from data represented by graphs or matrices.

This course will provide an introduction to mathematical and algorithmic tools for studying such problems.

We will discuss information-theoretic methods for determining the fundamental limits, as well as methodologies for attaining these limits,

including spectral methods, semidefinite programming relaxations,
Linear/quadratic programming relaxations, message passing (belief propagation) algorithms, etc.

Specific topics will include spectral clustering, planted clique and partition problem, community detection on stochastic block models, hidden Hamiltonian cycle problem,

planted bipartite graph matching problem, noisy graph isomorphism, and statistical-computational tradeoffs.

**Prerequisites**: Maturity with probability theory and linear algebra.

Familiarity with statistical theory, optimization, and algorithms.

**Instructor****:** Prof. Jiaming Xu, Fuqua W313, jiaming.xu868@duke.edu , Office Hours: By appointment

**Credit: **3
hours

**Meeting times:**
Wed and Fri, 3:05PM - 4:20PM

**Meeting location:**
Seminar Room G, Fuqua

**Syllabus**

**Lecture Notes (updated March 15)**

**
Introduction slides
**

**
Lecture 1
**

**
Lecture 2
**

**
Lecture 3
**

**
Lecture 4
**

**
Lecture 5
**

**
Lecture 6
**

**
Lecture 7
**

**
Lecture 8
**

**
Lecture 9
**

**
Lecture 10
**

**
Lecture 11
**

**
Lecture 12
**

**
Lecture 13
**

**Homework:**

**References:**

**
**