  A known failing of many popular random graph models is that the Aldous-Hoover
Theorem guarantees these graphs are dense with probability one; that is, the
number of edges grows quadratically with the number of nodes. This behavior is
considered unrealistic in observed graphs. We define a notion of edge
exchangeability for random graphs in contrast to the established notion of
infinite exchangeability for random graphs --- which has traditionally relied
on exchangeability of nodes (rather than edges) in a graph. We show that,
unlike node exchangeability, edge exchangeability encompasses models that are
known to provide a projective sequence of random graphs that circumvent the
Aldous-Hoover Theorem and exhibit sparsity, i.e., sub-quadratic growth of the
number of edges with the number of nodes. We show how edge-exchangeability of
graphs relates naturally to existing notions of exchangeability from clustering
(a.k.a. partitions) and other familiar combinatorial structures.
