More Like this

1. Parallel Vertex Color Update on Large Dynamic Networks

   https://doi.org/10.1109/HiPC56025.2022.00027  

   Khanda, Arindam; Bhowmick, Sanjukta; Liang, Xin; Das, Sajal K. (December 2022, HiPC)

   We present the first GPU-based parallel algorithm to efficiently update vertex coloring on large dynamic networks. For single GPU, we introduce the concept of loosely maintained vertex color update that reduces computation and memory requirements. For multiple GPUs, in distributed environments, we propose priority-based ordering of vertices to reduce the communication time. We prove the correctness of our algorithms and experimentally demonstrate that for graphs of over 16 million vertices and over 134 million edges on a single GPU, our dynamic algorithm is as much as 20x faster than state-of-the-art algorithm on static graphs. For larger graphs with over 130 million vertices and over 260 million edges, our distributed implementation with 8 GPUs produces updated color assignments within 160 milliseconds. In all cases, the proposed parallel algorithms produce comparable or fewer colors than state-of-the-art algorithms. 

   more » « less
2. Finding Small Dijoins in Transitive Closure Time

   https://doi.org/10.4230/lipics.fsttcs.2025.46  

   Nalam, Chaitanya; Saranurak, Thatchaphol (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aiswarya, C; Mehta, Ruta; Roy, Subhajit (Ed.)

   Abstract: We present a faster algorithm for finding a minimum dijoin, a smallest set of edges whose contraction makes a directed graph strongly connected. This problem has been studied since the 1960s [Seshu and Reed 1961] and is dual to finding a maximum sized family of disjoint dicuts [Lucchesi and Younger 1978]. Given a directed graph G with n vertices and m edges whose minimum dijoin has size d, our algorithm outputs both a minimum dijoin and a maximum sized family of disjoint dicuts in O(TC⋅ d) time, where TC = min(mn,n^ω) is the time to compute the transitive closure. This improves upon the state of the art of [Gabow 1993], which requires O(TC ⋅ min(m^{1/2},n^{2/3})) time when d = o(min(m^{1/2},n^{2/3})). Our result extends to finding a minimum weighted dijoin. We achieve this by observing that Frank’s algorithm [Frank 1981] can be sped up when warm-started with a 2-approximation solution, which we observed can be computed in near-linear time. 

   more » « less
3. Edge-transitive graphs and combinatorial designs

   Heather A. Newman, Hector Miranda (October 2019, Involve)

   A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. We present a complete classification of all connected edge-transitive graphs on less than or equal to 20 vertices. We investigate biregular bipartite edge-transitive graphs and present connections to combinatorial designs, and we show that the Cartesian products of complements of complete graphs give an additional family of edge-transitive graphs. 

   more » « less
4. Representing Joint Hierarchies with Box Embeddings

   Dhruvesh Patel, Shib Sankar (January 2020, Automated Knowledge Base Construction)

   Learning representations for hierarchical and multi-relational knowledge has emerged as an active area of research. Box Embeddings [Vilnis et al., 2018, Li et al., 2019] represent concepts with hyperrectangles in -dimensional space and are shown to be capable of modeling tree-like structures efficiently by training on a large subset of the transitive closure of the WordNet hypernym graph. In this work, we evaluate the capability of box embeddings to learn the transitive closure of a tree-like hierarchical relation graph with far fewer edges from the transitive closure. Box embeddings are not restricted to tree-like structures, however, and we demonstrate this by modeling the WordNet meronym graph, where nodes may have multiple parents. We further propose a method for modeling multiple relations jointly in a single embedding space using box embeddings. In all cases, our proposed method outperforms or is at par with all other embedding methods. 

   more » « less
5. A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes

   https://doi.org/10.1287/moor.2021.1179  

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

   We study a class of linear-quadratic stochastic differential games in which each player interacts directly only with its nearest neighbors in a given graph. We find a semiexplicit Markovian equilibrium for any transitive graph, in terms of the empirical eigenvalue distribution of the graph’s normalized Laplacian matrix. This facilitates large-population asymptotics for various graph sequences, with several sparse and dense examples discussed in detail. In particular, the mean field game is the correct limit only in the dense graph case, that is, when the degrees diverge in a suitable sense. Although equilibrium strategies are nonlocal, depending on the behavior of all players, we use a correlation decay estimate to prove a propagation of chaos result in both the dense and sparse regimes, with the sparse case owing to the large distances between typical vertices. Without assuming the graphs are transitive, we show also that the mean field game solution can be used to construct decentralized approximate equilibria on any sufficiently dense graph sequence. 

   more » « less