Edge-exchangeable graphs and sparsity
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. However, 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 a general framework for graph generative models; by contrast to the pioneering work of Caron and Fox [12], models within our framework are stationary across steps of the graph sequence. In particular, our model grows the graph by instantiating more latent atoms of a single random measure as the dataset size increases, rather than adding new atoms to the measure.
This paper introduces an alternative notion of exchangeability for random graphs, called edge exchangeability, by viewing a graph as a sequence of edges. In contrast to the classical Aldous-Hoover representation where the number of edges increases in proportional to the square of the number of vertices (a.s. dense or empty), the proposed graph representation is not only exchangeable in terms of edges but also leads to sparsity, i.e., the number of edges is asymptotically upper bounded by constant*#_vertex^2. The authors also propose the graph frequency model and simulate its generative process to validate the sparsity property.  
[Technical quality] In Section 2.2, the authors have elaborated the step-augmented graph representation for edge-exchangeable graph sequences and try to define the edge exchangeability on the permutation of steps. But to me it still looks like directly applying the de Finetti's theorem to an exchangeable sequence conditioned on W Eq.(1), where the elements are pairs of vertices. Although W is two-dimensional and \theta has two indices, it actually is treated as a sequence (1-array), so the de Finetti's theorem can be directly applied. Is my understanding right? Or it is indeed a new notion of exchangeability?   The biggest flaw of this work may be that: According to the measure defined in Eq.(1), the generative process only generates a multi-set, whose elements are i.i.d. generated edges given W. However, a graph, if represented in edges, is a binary set. In Line 164, an additional operation is required to obtain the final graph by binarizing the multigraph. Thus the resulting binary graph is no longer edge-exchangeable and the measure define in Eq.(1) is not applicable to random binary graphs.  Can the rate w_{I,j} only be defined in the form of w_i w_j in Eq.(3)? All the discussions in the reminder of the paper are based on this definition. Any other form?  First mentioned in the introduction (Line 46) and some places later, the notion of “stationary” is not described or defined. Is it the same meaning defined in Section 7.8 [19]? And this “stationary” property is not further discussed or proved in the rest of the paper.  [Novelty] On one hand, the proposed edge-exchangeability is an application of the de Finetti's theorem to an exchangeable sequence conditioned on W, which is not novel.  On the other hand, the proposed graph frequency model tries to grow the number of vertices in the graph through increasing the number of steps; and tries to make connection to the well known Bayesian nonparametric model such as CRP by viewing Eq.(1) as DP and the posterior graph after n steps as CRP. Such interpretation and connection may be interesting.   [Impact] Graph representation for sparse graphs are very important and can be impactful.   [Presentation] The presentation and clarity of the paper is good. The running examples and connection to other forms of exchangeability in the supplementary material are helpful to understand the idea. Example 4.1 is not clearly described, and in Line 192, should it be Section 3?