Quantifying randomness in complex graph sets using pairwise graph distances

On Graph-Informed Distance Metrics for Comparing Graph Partitions

Comparing graph partitions is fundamental to the analysis of network-structured data, yet existing measures for comparing graph partitions typically rely on graph-agnostic indices that treat vertices as exchangeable, ignoring the underlying graph topology that encodes essential information about community cohesion and separation. We propose a general construction of graph-informed distances that compares vertex partitions through induced edge partitions and yields valid metrics on the space of contiguous graph partitions. As special cases, we develop graph-informed versions of variation of information and the van Dongen distance together with a binary cut-based companion distance, and show that these distances satisfy a natural local graph-aware refinement criterion. Under stochastic block models, we prove that stronger topological disruptions incur asymptotically larger distances almost surely in both inter-community and intra-community split settings. These results provide a simple and principled framework to compare graph partitions while respecting the underlying graph structure.

Average Distance Approximation for Static Large Graphs

The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.

Comparing Geometric Embeddings of Graphs

Distributed Symmetry Breaking on Hyperbolic Random Graphs

Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of $\Delta+1$ colouring, where $\Delta$ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA'26]. In stark contrast to this 2-round algorithm for $\Delta+1$ colouring, we prove that the related symmetry-breaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of $\Omega\left(\frac{\log\log n}{\log\log\log n}\right)$ for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain $d$-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to HRGs that solve MIS and MM in $\tilde{\mathcal{O}}(\log^{5/3}\log n)$ rounds with high probability in the LOCAL model, improving over the general worst-case lower bound of $\Omega\left(\min\left\{\log \Delta, \sqrt{\log n}\right\}\right)$ rounds [Khoury and Schild; FOCS'25].

On the Complexity of Graph Edit Distance in Restricted Graph Classes

The graph edit distance generalizes several well-known NP-hard problems and is therefore NP-hard itself. However, the relationship between the considered graph class, the edit cost function, and the resulting computational complexity is not well understood. We investigate this interplay by revisiting polynomial-time reductions from the literature, which reduce subgraph isomorphism and maximum common induced subgraph to the graph edit distance. For these classical problems, a sharp distinction between NP-hard and polynomial-time solvable cases is known, and we make the implications for the complexity of the graph edit distance explicit. We establish a graph-class-preserving correspondence between the maximum common edge subgraph and graph edit distance under a specific cost function, both in labeled and unlabeled graphs. In the unlabeled setting, the maximum common edge subgraph problem is polynomial-time solvable when one graph is a path and the other is a tree. In contrast, for labeled graphs, we prove that both the maximum common edge subgraph and the graph edit distance remain NP-hard, even when both graphs are paths.

Higher-order graphon theory: Fluctuations, degeneracies and inference

The joint asymptotic distribution of any finite collection of network moments in random graphs sampled from a graphon, which includes both the nondegenerate case as well as the degenerate case, provides the higher-order fluctuation theory for subgraph counts in the graphon model.