Sparse Exchangeable Graphs and Their Limits via Graphon Processes
Authors: Christian Borgs, Jennifer T. Chayes, Henry Cohn, Nina Holden
JMLR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a σ-finite measure space (S, S, µ) and the connection probabilities by an integrable function W : S S [0, 1], we construct a random family (Gt)t 0 of growing graphs such that the vertices of Gt are given by a Poisson point process on S with intensity tµ, with two points x, y of the point process connected with probability W(x, y). We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on R+ equipped with Lebesgue measure. |
| Researcher Affiliation | Collaboration | Christian Borgs EMAIL Microsoft Research One Memorial Drive Cambridge, MA 02142, USA. Jennifer T. Chayes EMAIL Microsoft Research One Memorial Drive Cambridge, MA 02142, USA. Henry Cohn EMAIL Microsoft Research One Memorial Drive Cambridge, MA 02142, USA. Nina Holden EMAIL Department of Mathematics Massachusetts Institute of Technology Cambridge, MA 02139, USA. |
| Pseudocode | No | The paper describes mathematical concepts and proofs but does not contain any structured pseudocode or algorithm blocks. It focuses on theoretical derivations and properties of sparse exchangeable graphs. |
| Open Source Code | No | The paper mentions that a 'sampling method we will use in our forthcoming paper (Borgs, Chayes, Cohn, and Holden, 2017) generalizes both of these methods' but does not provide any specific code for the methodology described within this paper. No links to code repositories or explicit statements about code availability for this work are present. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with specific datasets. While it mentions the application of graphons to 'real-world networks, such as Facebook and Linked In' as reported by others (E. M. Airoldi, private communication, 2015), it does not use or provide access to any datasets for its own methodology. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets; therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on mathematical proofs and definitions; it does not describe any computational experiments or hardware specifications. |
| Software Dependencies | No | The paper is theoretical and presents mathematical concepts and proofs, thus it does not list any specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical and presents mathematical concepts and proofs; it does not describe any experimental setup details or hyperparameters. |