Wasserstein gradient flows on probability measures have found a host of applications in various optimization problems. They typically arise as the continuum limit of exchangeable particle systems evolving by some mean-field interaction involving a gradient-type potential. However, in many problems, such as in multi-layer neural networks, the so-called particles are edge weights on large graphs whose nodes are exchangeable. Such large graphs are known to converge to continuum limits called graphons as their size grows to infinity. We show that the Euclidean gradient flow of a suitable function of the edge weights converges to a novel continuum limit given by a curve on the space of graphons that can be appropriately described as a gradient flow or, more technically, a curve of maximal slope. Several natural functions on graphons, such as homomorphism functions and the scalar entropy, are covered by our setup, and the examples have been worked out in detail.
more »
« less
The devil's staircase for chip‐firing on random graphs and on graphons
We study the behavior of the activity of the parallel chip‐firing upon increasing the number of chips on an Erdős–Rényi random graph. We show that in various situations the resulting activity diagrams converge to a devil's staircase as we increase the number of vertices. Such a phenomenon was proved in an earlier paper by Levine for complete graphs, by relating the activity to the rotation number of a cycle map. Our method in this article is to generalize the parallel chip‐firing to graphons. Then we show that the earlier results on complete graphs generalize to constant graphons. Moreover, we prove a continuity result for the activity on graphons. These statements enable us to prove results on the activity of the parallel chip‐firing on large random graphs. We also address several problems concerning chip‐firing on graphons, and pose open problems. In particular, we show that the activity of a chip configuration on a graphon does not necessarily exist, but it does exist for every chip configuration on a large class of graphons.
more » « less- NSF-PAR ID:
- 10532182
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract A convex geometric graph is said to be packable if there exist edge‐disjoint copies of in the complete convex geometric graph covering all but edges. We prove that every convex geometric graph with cyclic chromatic number at most 4 is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most 3 is packable. Arguments based on the average length of edges imply these results are the best possible. We also identify a class of convex geometric graphs that are packable due to having many “long” edges.
-
We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-complete with 1× 1 particles even when only allowed to move in 2 or 3 directions.more » « less
-
more » « less
Abstract We present a refinement of the classical alteration method for constructing ‐free graphs for suitable edge‐probabilities , we show that removing all edges in ‐copies of the binomial random graph does not significantly change the independence number. This differs from earlier alteration approaches of Erdős and Krivelevich, who obtained similar guarantees by removing one edge from each ‐copy (instead of all of them). We demonstrate the usefulness of our refined alternation method via two applications to online graph Ramsey games, where it enables easier analysis.
-
more » « less
Computing strongly connected components (SCC) is among the most fundamental problems in graph analytics. Given the large size of today's real-world graphs, parallel SCC implementation is increasingly important. SCC is challenging in the parallel setting and is particularly hard on large-diameter graphs. Many existing parallel SCC implementations can be even slower than Tarjan's sequential algorithm on large-diameter graphs.
To tackle this challenge, we propose an efficient parallel SCC implementation using a new parallel reachability approach. Our solution is based on a novel idea referred to as vertical granularity control (VGC). It breaks the synchronization barriers to increase parallelism and hide scheduling overhead. To use VGC in our SCC algorithm, we also design an efficient data structure called the parallel hash bag. It uses parallel dynamic resizing to avoid redundant work in maintaining frontiers (vertices processed in a round).
We implement the parallel SCC algorithm by Blelloch et al. (J. ACM, 2020) using our new parallel reachability approach. We compare our implementation to the state-of-the-art systems, including GBBS, iSpan, Multi-step, and our highly optimized Tarjan's (sequential) algorithm, on 18 graphs, including social, web, k-NN, and lattice graphs. On a machine with 96 cores, our implementation is the fastest on 16 out of 18 graphs. On average (geometric means) over all graphs, our SCC is 6.0× faster than the best previous parallel code (GBBS), 12.8× faster than Tarjan's sequential algorithms, and 2.7× faster than the best existing implementation on each graph.
We believe that our techniques are of independent interest. We also apply our parallel hash bag and VGC scheme to other graph problems, including connectivity and least-element lists (LE-lists). Our implementations improve the performance of the state-of-the-art parallel implementations for these two problems.
