Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. While this leads to tractable inference algorithms, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We present an alternative notion of exchangeability for random graphs, which we call edge exchangeability, in which the distribution of a graph sequence is invariant to the order of the edges. We demonstrate that edge-exchangeable models, unlike models that are traditionally vertex-exchangeable, can exhibit sparsity. To do so, we outline the class of graph frequency models, which grow the graph by sequentially sampling edges to instantiate based on latent vertex weights. We also provide a paintbox representation for edge-exchangeable graphs, which we call the graph paintbox, and show that it characterizes the distribution of all edge-exchangeable graphs. The paintbox representation thus provides a way to study desirable properties such as sparsity and power laws. Finally, we provide a characterization for all graph frequency models via a function called the exchangeable vertex probability function (EVPF), which is useful when developing practical posterior inference procedures.