More Like this

1. Graphon mean field systems

   https://doi.org/10.1214/22-AAP1901  

   Bayraktar, Erhan; Chakraborty, Suman; Wu, Ruoyu (October 2023, The Annals of Applied Probability)

   We consider heterogeneously interacting diffusive particle systems and their large population limit. The interaction is of mean field type with weights characterized by an underlying graphon. A law of large numbers result is established as the system size increases and the underlying graphons converge. The limit is given by a graphon mean field system consisting of independent but heterogeneous nonlinear diffusions whose probability distributions are fully coupled. Well-posedness, continuity and stability of such systems are provided. We also consider a not-so-dense analogue of the finite particle system, obtained by percolation with vanishing rates and suitable scaling of interactions. A law of large numbers result is proved for the convergence of such systems to the corresponding graphon mean field system. 

   more » « less
2. A Label-State Formulation of Stochastic Graphon Games and Approximate Equilibria on Large Networks

   Lacker, Daniel; Soret, Agathe (November 2022, Mathematics of Operations Research)

   This paper studies stochastic games on large graphs and their graphon limits. We propose a new formulation of graphon games based on a single typical player’s label-state distribution. In contrast, other recently proposed models of graphon games work directly with a continuum of players, which involves serious measure-theoretic technicalities. In fact, by viewing the label as a component of the state process, we show in our formulation that graphon games are a special case of mean field games, albeit with certain inevitable degeneracies and discontinuities that make most existing results on mean field games inapplicable. Nonetheless, we prove the existence of Markovian graphon equilibria under fairly general assumptions as well as uniqueness under a monotonicity condition. Most importantly, we show how our notion of graphon equilibrium can be used to construct approximate equilibria for large finite games set on any (weighted, directed) graph that converges in cut norm. The lack of players’ exchangeability necessitates a careful definition of approximate equilibrium, allowing heterogeneity among the players’ approximation errors, and we show how various regularity properties of the model inputs and underlying graphon lead naturally to different strengths of approximation. Funding: D. Lacker was partially supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0291] and the National Science Foundation [Award DMS-2045328]. 

   more » « less
3. Robust Recovery of Robinson Property in $L^p$-Graphons: A Cut-Norm Approach

   https://doi.org/10.37236/12435  

   Ghandehari, Mahya; Mishura, Teddy (October 2024, The Electronic Journal of Combinatorics)

   This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $$5 5$, any $L^p$-graphon $$w$$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of $$\Lambda(w)$$. When viewing $$w$$ as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless $$w$$. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of $$L^\infty$$-graphons was answered. 

   more » « less
4. Weak Randomness in Graphons and Theons

   https://doi.org/10.1002/rsa.21261  

   Coregliano, Leonardo N; Malliaris, Maryanthe (January 2025, Random Structures & Algorithms)

   Call a hereditary family F of graphs strongly persistent if there exists a graphon W such that in all subgraphons W0 of W , F is precisely the class of finite graphs that have positive density in W0. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. We call graphons with the self-similarity property above weakly random. A hereditary family F is said to have the weakly random Erdos–Hajnal property (WR) if every graphon that is a limit of graphs in F has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with “few” prime graphs. We also extend some of the results above to structures in finite relational languages by using the theory of theons. 

   more » « less
5. A Poincare Inequality and Consistency Results for Signal Sampling on Large Graphs

   Le, T; Ruiz, Luana; Jegelka, Stefanie (May 2024, International Conference on Learning Representations (ICLR))

   Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this pa- per, we introduce a signal sampling theory for a type of graph limit—the graphon. We prove a Poincare ́ inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks. 

   more » « less