MIA: Tamara Broderick, Edge-exchangeable Graphs, Clustering, and Sparsity - 2017

Details

Title : MIA: Tamara Broderick, Edge-exchangeable Graphs, Clustering, and Sparsity Author(s): Broad Institute Link(s) : https://www.youtube.com/watch?v=jRO_OU7S9yQ

Rough Notes

There is a model misspecification problem with many probabilistic models for graphs when learning growing graphs, as they assume projectivity (adding more data doesn't change the distribution of earlier data) (#DOUBT I guess this leads to dense graphs?). This talk introduces a new framework for sparse graphs.

Consider sequences of graphs where we add nodes. If \(|V(G_n)|\to \infty\), (i.e. number of nodes goes to infinity), then a dense graph sequence will have \(|E(G_n)|\geq c |V(G_n)|^2\). Instead we want a sequence of sparse graphs - a sensible definition is that \(|E(G_n)|\) grows sub-quadratically, i.e. \(|E(G_n)|\in o(|V(G_n)|^2\). Old approaches go like this - as nodes are added, if an edge connected to this node is not added, it will stay that way.

Exchangeability is a key assumption for graphs - changing the labels of the nodes of a graph should not change the probability density for it.

Consider the following procedure that generates node exchangeable graphs:

On the unit square, apply a function \(W(x,y)\in [0,1]\) above the line \(y=x\).
Draw iid \(u_i\sim U(0,1)\) for each node \(i\), and draw both lines \(y=u_i,x=u_i\) on the unit square.
Each intersection between pairs \(u_i,u_j\) represents a potential edge. The probability of that edge existing is given by \(W(u_i,u_j)\).
The distribution for the (undirected) edge \((i,j)\in E\) is \(\text{Bernoulli}(W(u_i,u_j))\).

The Aldous-Hoover Representation Theorem says that every node-exchangeable graph is generated in such a manner.

By the construction above, \(\mathbb{ E }[|E(G_n)|] = \mathbb{ E }[{n\choose 2}\frac{1}{2}\int_{0}^{1}\int_{0}^1W(x,y)dxdy] \sim cn^2\) (\(\sim\) means asymptotic equivalence). This implies, every node-exchangeable graph sequence is dense (or empty) a.s.

A new way: Add edges as we increase the sequence, and an edge-exchangeability assumption. This means the probability density of a given graph with the same number of nodes is the same if they have the same edges but they arrived in the sequence in a different order. A wide class of edge-exchangeable graphs give sparse graph sequences. They are introduced starting from clustering models to feature allocation models (i.e. a sample could belong to multiple clusters) to feature allocation models restricted to 2 features so that each sample represents an edge as they belong to only 2 clusters (nodes). Sparse graph model sequences are introduced from there (#TODO Fill in the gap here).