Graphon
In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function formula_1, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs. Statistical formulation. A graphon  is a symmetric measurable function formula_2. Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme: A random graph model is an exchangeable random graph model if and only if it can be defined in terms of a (possibly random) graphon in this way. The model based on a fixed graphon formula_7 is sometimes denoted formula_8, by analogy with the Erdős–Rényi model of random graphs. A graph generated from a graphon formula_7 in this way is called a formula_7-random graph. It follows from this definition and the law of large numbers  that, if formula_11, exchangeable random graph models are dense almost surely. Examples. The simplest example of a graphon is formula_12 for some constant formula_13. In this case the associated exchangeable random graph model is the Erdős–Rényi model formula_14 that includes each edge independently with probability formula_15. If we instead start with a graphon that is piecewise constant by: the resulting exchangeable random graph model is the formula_20 community stochastic block model, a generalization of the Erdős–Rényi model. We can interpret this as a random graph model consisting of formula_20 distinct Erdős–Rényi graphs with parameters formula_22 respectively, with  bigraphs between them where each possible edge between blocks formula_23 and formula_24 is included independently with probability formula_18. Many other popular random graph models can be understood as exchangeable random graph models defined by some graphon, a detailed survey is included in Orbanz and Roy. Jointly exchangeable adjacency matrices. A random graph of size formula_26 can be represented as a random formula_27 adjacency matrix. In order to impose consistency (in the sense of projectivity) between random graphs of different sizes it is natural to study the sequence of adjacency matrices arising as the upper-left formula_27 sub-matrices of some  infinite array of random variables; this allows us to generate formula_29 by adding a node to formula_30 and sampling the edges formula_31 for formula_32. With this perspective, random graphs are defined as random infinite symmetric arrays formula_33. Following the fundamental importance of exchangeable sequences in classical probability, it is natural to look for an analogous notion in the random graph setting. One such notion is given by jointly exchangeable matrices; i.e. random matrices satisfying for all permutations formula_35 of the natural numbers, where formula_36 means equal in distribution. Intuitively, this condition means that the distribution of the random graph is  unchanged by a relabeling of its vertices: that is, the labels of the vertices carry no information. There is a representation theorem for jointly exchangeable random adjacency matrices, analogous to de Finetti’s representation theorem for exchangeable sequences. This is a special case of the Aldous–Hoover theorem for jointly exchangeable arrays and, in this setting, asserts that the random matrix formula_33 is generated by: where formula_1 is a (possibly random) graphon. That is, a random graph model has a jointly exchangeable adjacency matrix if and only if it is a jointly exchangeable random graph model defined in terms of  some graphon. Graphon estimation. Due to identifiability issues, it is impossible to estimate either the graphon function formula_7 or the node latent positions formula_43 and there are two main directions of graphon estimation. One direction aims at estimating formula_7up to an equivalence class, or estimate the probability matrix induced by formula_7. Analytic formulation. Any graph on formula_26 vertices formula_47 can be identified with its adjacency matrix formula_48. This matrix corresponds to a stepfunction formula_49, defined by partitioning formula_50 into intervals formula_51 such that formula_52 has interior formula_53 and for each formula_54, setting formula_55 equal to the formula_56 entry of formula_48 . This function formula_58 is the associated graphon of the graph formula_59. In general, if we have a sequence of graphs formula_60 where the number of vertices of formula_29 goes to infinity, we can analyze the limiting behavior of the sequence by considering the limiting behavior of the functions formula_62. If these graphs converge (according to some suitable definition of convergence), then we expect the limit of these graphs to correspond to the limit of these associated functions. This motivates the definition of a graphon (short for "graph function") as a symmetric measurable function formula_2 which captures the notion of a  limit of a sequence of graphs. It turns out that for sequences of dense graphs, several apparently distinct notions of convergence are equivalent and under all of them the natural limit object is a graphon. Examples. Constant graphon. Take a sequence of formula_60 Erdős–Rényi random graphs formula_65 with some fixed parameter formula_15. Intuitively, as formula_26 tends to infinity, the limit of this sequence of graphs is determined solely by edge density of these graphs. In the space of graphons, it turns out that such a sequence converges almost surely to the constant formula_12, which captures the above intuition. Half  graphon. Take the sequence formula_69 of half-graphs, defined by taking formula_70 to be the bipartite graph on formula_71 vertices formula_72 and formula_73 such that formula_74 is adjacent to formula_75 precisely when formula_76. If the vertices are listed in the presented order, then the adjacency matrix formula_77 has two corners of "half square" block matrices filled with ones, with the rest of the entries equal to zero. For example, the adjacency matrix of formula_78 is given by formula_79 As formula_26 gets large, these corners of ones "smooth" out. Matching this intuition, the sequence formula_69 converges to the half-graphon formula_7  defined by formula_83 when formula_84 and formula_85 otherwise. Complete bipartite graphon. Take the sequence formula_86 of complete bipartite graphs with equal sized parts. If we order the vertices by placing all vertices in one part at the beginning and placing the vertices of the other part at the end, the adjacency matrix of formula_86 looks like a block off-diagonal matrix, with two blocks of ones and two blocks of zeros. For example, the adjacency matrix of formula_88 is given by formula_89 As formula_26 gets larger, this block structure of the adjacency matrix remains constant, so that this sequence of  graphs converges to a "complete bipartite" graphon formula_7 defined by formula_83 whenever formula_93 and formula_94, and setting formula_85 otherwise. If we instead order the vertices of formula_96 by alternating between parts, the adjacency matrix has a chessboard structure of zeros and ones. For example, under this ordering, the adjacency matrix of formula_88 is given by formula_98 As formula_26 gets larger, the adjacency matrices become a finer and finer chessboard. Despite this behavior, we still want the limit of formula_86 to be unique and result in the graphon from example 3. This means that when we formally define convergence for a  sequence of graphs, the definition of a limit should be agnostic to relabelings of the vertices. Limit of W-random graphs. Take a random sequence formula_60 of formula_7-random graphs by drawing formula_103 for some fixed graphon formula_7. Then just like in the first example from this section, it turns out that formula_60 converges to formula_7 almost surely. Recovering graph parameters from graphons. Given graph formula_59 with associated graphon formula_108, we can recover graph theoretic properties and parameters of formula_59 by integrating transformations of formula_7. For example, the edge density (i.e. average degree divided by number of vertices) of formula_59  is given by the integral formula_112 This is because formula_7 is formula_114-valued, and each edge formula_115 in formula_59 corresponds to a region formula_117 of area formula_118 where formula_7 equals formula_120. Similar reasoning shows that the number of triangles in formula_59 is equal to formula_122 Notions of convergence. There are many different ways to measure the distance between two graphs. If we are interested in metrics that "preserve" extremal properties of graphs, then we should restrict our attention to metrics that identify random graphs as similar. For example, if we randomly draw two graphs independently from an Erdős–Rényi model  formula_14 for some fixed formula_15, the distance between these two graphs under a "reasonable" metric should be close to zero with high probability for large formula_26. Naively, given two graphs on the same vertex set, one might define their distance as the number of edges that must be added or removed to get from one graph to the other, i.e. their edit distance. However, the edit distance does not identify random graphs as similar; in fact, two graphs drawn independently from formula_126 have an expected (normalized) edit distance of formula_127. There are two natural metrics that behave well on dense  random graphs in the sense that we want. The first is a sampling metric, which says that two graphs are close if their distributions of subgraphs are close. The second is an edge discrepancy metric, which says two graphs are close when their edge densities are close on all their corresponding subsets of vertices. Miraculously, a sequence of graphs converges with respect to one metric precisely when it converges with respect to the other. Moreover, the limit objects under both metrics turn out to be graphons. The equivalence of these two notions of convergence mirrors how various notions of quasirandom  graphs are equivalent. Homomorphism densities. One way to measure the distance between two graphs formula_59 and formula_129 is to compare their relative subgraph counts. That is, for each graph formula_130 we can compare the number of copies of formula_130 in formula_59 and formula_130 in formula_129. If these numbers are close for every graph formula_130, then intuitively formula_59 and formula_129 are similar looking graphs. Rather than dealing directly with subgraphs, however, it turns out to be easier to work with graph homomorphisms. This is fine when dealing with large, dense graphs, since in this scenario the number of subgraphs and the  number of graph homomorphisms from a fixed graph are asymptotically equal. Given two graphs formula_130 and formula_59, the homomorphism density formula_140 of formula_130 in formula_59 is defined to be the number of graph homomorphisms from formula_130 to formula_59. In other words, formula_145 is the probability a randomly chosen map from the vertices of formula_130 to the vertices of formula_59 sends adjacent vertices in formula_130 to adjacent vertices in formula_59. Graphons offer a simple way to compute homomorphism densities. Indeed, given a graph formula_59 with associated graphon formula_58 and another formula_130, we have formula_153 where the integral is multidimensional, taken over  the unit hypercube formula_154. This follows from the definition of an associated graphon, by considering when the above integrand is equal to formula_120. We can then extend the definition of homomorphism density to arbitrary graphons formula_7, by using the same integral and defining formula_157 for any graph formula_130. Given this setup, we say a sequence of graphs formula_60 is left-convergent if for every fixed graph formula_130, the sequence of homomorphism densities formula_161 converges. Although not evident from the definition alone, if formula_60 converges in this sense, then there always exists a graphon formula_7 such that for every graph formula_130 , we have formula_165 simultaneously. Cut distance. Take two graphs formula_59 and formula_129 on the same vertex set. Because these graphs share the same vertices, one way to measure their distance is to restrict to subsets formula_168 of the vertex set, and for each such pair subsets compare the number of edges formula_169 from formula_170 to formula_171 in formula_59 to the number of edges formula_173 between formula_170 and formula_171 in formula_129. If these numbers are similar for every pair of subsets (relative to the total number of vertices), then that suggests formula_59 and formula_129 are similar graphs. As a preliminary formalization  of this notion of distance, for any pair of graphs formula_59 and formula_129 on the same vertex set formula_181 of size formula_182, define the labeled cut distance between formula_59 and formula_129 to be formula_185 In other words, the labeled cut distance encodes the maximum discrepancy of the edge densities between formula_59 and formula_129. We can generalize this concept to graphons by expressing the edge density formula_188 in terms of the associated graphon formula_58, giving the equality formula_190 where formula_191 are unions of intervals corresponding to the vertices in formula_170 and formula_171. Note that this definition can still be used even  when the graphs being compared do not share a vertex set. This motivates the following more general definition. Definition 1. For any symmetric, measurable function formula_194, define the cut norm of formula_195 to be the quantity formula_196 taken over all measurable subsets formula_197 of the unit interval. This captures our earlier notion of labeled cut distance, as we have the equality formula_198. This distance measure still has one major limitation: it can assign nonzero distance to two isomorphic graphs. To make sure isomorphic graphs have distance zero, we should compute the minimum cut norm over all possible "relabellings" of the  vertices. This motivates the following definition of the cut distance. Definition 2. For any pair of graphons formula_199 and formula_7, define their cut distance to be formula_201 where formula_202 is the composition of formula_7 with the map formula_204, and the infimum is taken over all measure-preserving bijections from the unit interval to itself. The cut distance between two graphs is defined to be the cut distance between their associated graphons. We now say that a sequence of graphs formula_60 is convergent under the cut distance if it is a Cauchy sequence under the cut distance formula_206. Although not a  direct consequence of the definition, if such a sequence of graphs is Cauchy, then it always converges to some graphon formula_7. Equivalence of convergence. As it turns out, for any sequence of graphs formula_60, left-convergence is equivalent to convergence under the cut distance, and furthermore, the limit graphon formula_7 is the same. We can also consider convergence of graphons themselves using the same definitions, and the same equivalence is true. In fact, both notions of convergence are related more strongly through what are called counting lemmas. Counting Lemma. For any pair of graphons formula_199 and formula_7, we have formula_212  for all graphs formula_130. The name "counting lemma" comes from the bounds that this lemma gives on homomorphism densities formula_214, which are analogous to subgraph counts of graphs. This lemma is a generalization of the graph counting lemma that appears in the field of regularity partitions, and it immediately shows that convergence under the cut distance implies left-convergence. Inverse Counting Lemma. For every real number formula_215, there exist a real number formula_216 and a positive integer formula_20 such that for any pair of graphons formula_199 and formula_7 with formula_220 for all graphs formula_130 satisfying formula_222, we must have formula_223 . This lemma shows that left-convergence implies convergence under the cut distance. The space of graphons. We can make the cut-distance into a metric by taking the set of all graphons and identifying two graphons formula_224 whenever formula_225. The resulting space of graphons is denoted formula_226, and together with formula_206 forms a metric space. This space turns out to be compact. Moreover, it contains the set of all finite graphs, represented by their associated graphons, as a dense subset. These observations show that the space of graphons is a completion of the space of graphs with respect to the  cut distance. One immediate consequence of this is the following. Corollary 1. For every real number formula_215, there is an integer formula_229 such that for every graphon formula_7, there is a graph formula_59 with at most formula_229 vertices such that formula_233. To see why, let formula_234 be the set of graphs. Consider for each graph formula_235 the open ball formula_236 containing all graphons formula_7 such that formula_233. The set of open balls for all graphs covers formula_226, so compactness implies that there is a finite subcover formula_240 for some finite subset formula_241. We can now take formula_229 to be the  largest number of vertices among the graphs in formula_243. Applications. Regularity lemma. Compactness of the space of graphons formula_244 can be thought of as an analytic formulation of Szemerédi's regularity lemma; in fact, a stronger result than the original lemma. Szemeredi's regularity lemma can be translated into the language of graphons as follows. Define a stepfunction to be a graphon formula_7 that is piecewise constant, i.e. for some partition formula_246 of formula_50, formula_7 is constant on formula_249 for all formula_250. The statement that a graph formula_59 has a regularity partition is equivalent to saying that its associated graphon  formula_58 is close to a stepfunction. The proof of compactness requires only the weak regularity lemma: Weak Regularity Lemma for Graphons. For every graphon formula_7 and formula_215, there is a stepfunction formula_255 with at most formula_256 steps such that formula_257. but it can be used to prove stronger regularity results, such as the strong regularity lemma: Strong Regularity Lemma for Graphons. For every sequence formula_258 of positive real numbers, there is a positive integer formula_259 such that for every graphon formula_7, there is a graphon formula_255 and a stepfunction formula_199 with formula_263 steps such that formula_264 and formula_265 The proof  of the strong regularity lemma is similar in concept to Corollary 1 above. It turns out that every graphon formula_7 can be approximated with a stepfunction formula_199 in the formula_268 norm, showing that the set of balls formula_269 cover formula_226. These sets are not open in the formula_206 metric, but they can be enlarged slightly to be open. Now, we can take a finite subcover, and one can show that the desired condition follows. Sidorenko's conjecture. The analytic nature of graphons allows greater flexibility in attacking inequalities related to homomorphisms. For example, Sidorenko's conjecture is a major open  problem in extremal graph theory, which asserts that for any graph formula_59 on formula_26 vertices with average degree formula_274 (for some formula_275) and bipartite graph formula_129 on formula_277 vertices and formula_278 edges, the number of homomorphisms from formula_129 to formula_59 is at least formula_281. Since this is quantity is the expected number of labeled subgraphs of formula_129 in a random graph formula_14, the conjecture can be interpreted as the claim that for any bipartite graph formula_129, the random graph achieves (in expectation) the minimum number of copies of formula_129 over all graphs with some fixed edge density. Many approaches to  Sidorenko's conjecture formulate the problem as an integral inequality on graphons, which then allows the problem to be attacked using other analytical approaches. Generalizations. Graphons are naturally associated with dense simple graphs. There are extensions of this model to dense directed weighted graphs, often referred to as decorated graphons. There are also recent extensions to the sparse graph regime, from both the perspective of random graph models and graph limit theory.