betaFeedback

WorksMathematics

Maximum edge overlap between independent random regular graphs

Abstract

Optimising the vertex correspondence can substantially increase the number of edges shared by two independent realisations of the same random graph. We quantify this phenomenon for uniformly random dd-regular graphs and derive corresponding results for their edge-based graph edit distance. For every fixed d≥3d\geq 3, we show that the maximum overlap is n+ΘP(n/log⁡n)n+Θ_{\mathbb P}(n/\log n), where the leading term nn arises from Hamiltonicity, while the surplus captures the optimal order of the excess beyond it. We establish explicit upper and lower bounds on the surplus. The upper bound is obtained by counting common cores of minimum degree at least two, while the lower bound is established using spanning factors consisting of cycles of the same logarithmic length. For the special case d=2d=2, we show that the maximum overlap is n−(1+oP(1))log⁡nn-(1+o_{\mathbb P}(1))\log n. The additional overlap achievable is also studied by rotating aligned Hamilton cycles, using a contiguity argument. As a by-product, we determine the asymptotic maximum overlap between unions of independent random perfect matchings under cyclic shifts.

Introduction

Graph-structured representations offer a flexible way to model complex relationships and are therefore central to a broad spectrum of applications, ranging from semantic knowledge representation and molecular analysis to computer vision. In many of these settings, graphs rarely coincide exactly: they may differ in size, labelling, connectivity, or local structure while still encoding related information. This motivates the study of graph similarity, which replaces the yes-or-no notion of graph isomorphism with a graded measure of structural resemblance. By enabling meaningful comparisons between imperfect or partially aligned graphs, similarity measures provide a foundation for important learning tasks over graph data, including graph classification, clustering, pattern discovery, and anomaly detection.

Among the various approaches to quantify similarity, graph overlap is a widely used and intuitive measure. Rather than requiring an exact structural correspondence, graph overlap measures the extent to which the two graphs share common structural elements, such as vertices, edges, or substructures. This makes graph overlap particularly suitable for applications in which graphs may be only partially similar or may contain noise, missing information, or additional structures.

We quantify the similarity between two graphs by the number of shared edges they have. More precisely, we consider two graphs defined on the same vertex set.

Definition 1.1 (Graph overlap). Let G1G_1 and G2G_2 be two graphs with a common vertex set VV, where n=∣V∣n = |V|. For a permutation π∈Sn\pi\in\mathfrak{S}_n of [n]={1,…,n}[n] = \{1,\ldots,n\}, the graph overlap of G1G_1 and G2G_2 under π\pi is defined by

Ov⁡π(G1,G2)=∣π(E(G1))∩E(G2)∣.\operatorname{Ov}_{\pi}(G_1,G_2) = \left|\pi(E(G_1)) \cap E(G_2)\right|.

The maximum overlap is then given by

Mn=max⁡π∈SnOv⁡π(G1,G2).(1)M_n = \max_{\pi\in\mathfrak{S}_n} \operatorname{Ov}_{\pi}(G_1,G_2). \tag*{(1)}

The quantity MnM_n is closely related to the graph edit distance (GED) [16]. In general, the GED between two graphs, possibly equipped with vertex and edge labels, is defined as the minimum cost of an edit sequence that transforms one graph into a graph isomorphic to the other. The allowed edit operations may include inserting, deleting, or substituting vertices and edges, with each operation assigned a non-negative cost [8].

For unlabelled graphs on the same vertex set, when only edge insertions and deletions are permitted, and every operation has unit cost, the edge-based GED is given by

GED⁡E(G1,G2)=min⁡π∈Sn∣π(E(G1))△E(G2)∣=∣E(G1)∣+∣E(G2)∣−2Mn.(2)\operatorname{GED}_{E}(G_1,G_2) = \min_{\pi\in\mathfrak{S}_n} \left|\pi(E(G_1)) \triangle E(G_2)\right| = |E(G_1)| + |E(G_2)| - 2M_n. \tag*{(2)}

In this paper, we assume that G1G_1 and G2G_2 are independent copies of the same graph distribution, so that MnM_n represents a notion of self-similarity within the same graph ensemble. Both graph overlap and edit distance have been investigated in the setting of independent Erdős–Rényi random graphs.

Related work Comparisons of independent realisations of the same random graph model have been investigated from several perspectives. Hartle et al. [9] introduced the notion of within-ensemble graph distance, studying the typical distance between two independent samples from a common graph ensemble. Their analysis covers several random graph models, including Erdős–Rényi graphs, random geometric graphs, Watts–Strogatz networks, configuration models, and preferential attachment networks, using a variety of graph distance measures. This provides a general framework for understanding how structural variability within an ensemble is reflected by different notions of graph similarity.

From a mathematical perspective, Bollobás and Riordan [2, 1] investigated metrics on sparse graphs, including edit and cut distances, with particular attention to random graphs having a linear number of edges. In the Erdős–Rényi model G(n,p)\mathcal{G}(n,p) with p=c/np = c/n, their results show that, for fixed c>1c > 1, two independent realisations have an edit distance bounded below by a positive constant times nn with high probability. Their framework also addresses more general inhomogeneous sparse random graph models. More recently, Ding, Du, and Gong [6] studied the maximum overlap between two independent Erdős–Rényi graphs in denser regimes. For p=n−αp = n^{-\alpha} with α∈(1/2,1)\alpha\in(1/2,1), they established that

Mn∼n2α−1M_n \sim\frac{n}{2\alpha- 1}

with high probability, and provided a polynomial-time approximation scheme achieving an arbitrarily close multiplicative approximation to the optimum. This shows that optimising the vertex correspondence can produce a linear overlap even when the two graphs are independently generated. The algorithmic aspects of this problem were further investigated by Du, Gong, and Huang [7], who identified a phase transition around

pc=log⁡nn.p_c = \sqrt{\frac{\log n}{n}}.

They established polynomial-time approximation schemes in the sparse regime and identified algorithmic limitations in the dense regime, including hardness results for online and greedy local iterative algorithms. Their overlap analysis also provides evidence of a broader statistical-computational gap, although the hardness of arbitrary polynomial-time algorithms remains open.

In this paper, we investigate the maximum overlap within the ensemble of uniform random dd-regular graphs. Unlike Erdős–Rényi graphs, these graphs satisfy a hard degree constraint, which introduces dependencies between their edges. Moreover, for fixed d≥3d \ge3, the presence of Hamilton cycles provides a natural linear baseline for the overlap. Our aim is to determine not only this leading-order behaviour, but also the order of the additional overlap achievable by optimising over vertex permutations.

Labelled versus unlabelled overlap

We focus on the set Gn,d\mathcal{G}_{n,d} of simple dd-regular graphs on [n][n], where dd is fixed and ndnd is even. We denote by Un,d\mathcal{U}_{n,d} the uniform probability measure on Gn,d\mathcal{G}_{n,d}. Throughout the paper, G1G_1 and G2G_2 are independent samples from Un,d\mathcal{U}_{n,d}, and all asymptotic statements are understood along admissible values of nn.

To illustrate the effect of optimising over vertex permutations, we first consider the overlap under a fixed labelling. Let

Xn:=∣E(G1)∩E(G2)∣X_n := |E(G_1) \cap E(G_2)|

be the number of common edges. Since each unordered pair of vertices is an edge of a uniform dd-regular graph with probability d/(n−1)d/(n-1), independence gives

E[Xn]=(n2)(dn−1)2=nd22(n−1)=d22+o(1).\mathbb{E}[X_n] = \binom{n}{2}\left(\frac{d}{n-1}\right)^2 = \frac{nd^2}{2(n-1)} = \frac{d^2}{2} + o(1).

In fact, using standard estimates for random regular graphs (see, e.g., [12 Chapter 9]), a factorial-moment argument shows that, for every fixed dd, XnX_n converges in distribution to a Poisson random variable with mean d2/2d^2/2. Thus, the overlap under a fixed labelling remains of constant order as nn grows, and in particular vanishes with a probability bounded away from zero.

Allowing vertex relabelings changes the picture. For any two graphs G1G_1 and G2G_2 on the same vertex set, consider a uniformly random permutation π∈Sn\pi\in S_n. Since the image of each fixed edge is uniformly distributed over the (n2)\binom{n}{2} unordered vertex pairs, we have

Eπ[Ov⁡π(G1,G2)]=∣E(G1)∣∣E(G2)∣(n2).\mathbb{E}_{\pi}[\operatorname{Ov}_{\pi}(G_1,G_2)] = \frac{|E(G_1)||E(G_2)|}{\binom{n}{2}}.

Consequently, at least one permutation achieves an overlap no smaller than this average. Since every dd-regular graph has exactly nd/2nd/2 edges, we obtain the deterministic bound

Mn≥⌈nd22(n−1)⌉.M_n \ge\left\lceil\frac{nd^2}{2(n-1)} \right\rceil.

Although this elementary argument only yields a constant lower bound, optimising over vertex permutations has a much stronger effect: as we show below, the maximum overlap between two independent random dd-regular graphs is typically of linear order in nn.

Main results

Our objective is to characterise the maximum overlap between two independent uniform random dd-regular graphs, for each fixed d≥1d \ge1. We will show that the behaviour changes significantly between the regimes d=1d = 1, d=2d = 2, and d≥3d \ge3 as summarised in the following table:

DegreeMaximum overlap MnM_nGEDE(G1,G2)\mathrm{GED}_E(G_1,G_2)
d=1d = 1n/2n/200
d=2d = 2n−(1+oP(1))log⁡nn - (1 + o_{\mathbb{P}}(1))\log n(2+oP(1))log⁡n(2 + o_{\mathbb{P}}(1))\log n
d≥3d \ge3n+ΘP(n/log⁡n)n + \Theta_{\mathbb{P}}(n/\log n)(d−2)n−ΘP(n/log⁡n)(d - 2)n - \Theta_{\mathbb{P}}(n/\log n)

Table 1.

When d=1d = 1, both graphs are perfect matchings, and any two perfect matchings on the same vertex set are isomorphic. Consequently, all n/2n/2 edges can be aligned, yielding Mn=n/2M_n = n/2 and GEDE(G1,G2)=0\mathrm{GED}_E(G_1,G_2) = 0 deterministically.

The case d=2d = 2 is more interesting. Here, each graph is a disjoint union of cycles, and although two independent realisations are typically not isomorphic, their cycle decompositions can be aligned so that only a logarithmic number of edges remain unmatched.

Theorem 1.2 (Overlap in degree two). Let d=2d = 2. Then

n−Mnlog⁡n→P1.\frac{n - M_n}{\log n} \xrightarrow{\mathbb{P}} 1.

More precisely, with c(G)c(G) denoting the number of cycles of GG,

Mn=n−c(G1)−c(G2)+OP(1).M_n = n - c(G_1) - c(G_2) + O_{\mathbb{P}}(1).

Since both graphs have exactly nn edges, this also implies that GEDE(G1,G2)=(2+oP(1))log⁡n\mathrm{GED}_E(G_1,G_2) = (2 + o_{\mathbb{P}}(1))\log n. Thus, unlike the case d=1d = 1, two independent random 2-regular graphs are typically not isomorphic, but they can be made almost identical by an appropriate relabelling, with only a logarithmic number of edge modifications.

For every fixed d≥3d \ge3, the behaviour is fundamentally different. A classical result of Robinson and Wormald [15] guarantees that a uniform random dd-regular graph is Hamiltonian with high probability. Consequently, two independent realisations contain Hamilton cycles that can be perfectly aligned through a suitable vertex permutation, yielding Mn≥nM_n \ge n with high probability. On the other hand, a first-moment argument shows that the maximum overlap cannot exceed (1+ε)n(1 + \varepsilon)n with high probability for any fixed ε>0\varepsilon> 0.

Theorem 1.3 (First-order overlap). For every fixed d≥3d \ge3 and every ε>0\varepsilon> 0,

lim⁡n→∞P(∣Mnn−1∣≤ε)=1.\lim_{n \to\infty} \mathbb{P}\left(\left|\frac{M_n}{n} - 1\right| \le\varepsilon\right) = 1.

This determines the leading-order behaviour of the maximum overlap. The next question is whether an appropriate relabelling can systematically improve upon the overlap of nn edges provided by aligning two Hamilton cycles. To quantify this improvement, we introduce the surplus overlap

Sn:=Mn−n.S_n := M_n - n.

Our main results identify the correct asymptotic order of this surplus and give explicit degree-dependent constants. Set

ad:=log⁡(d−1)+d−22log⁡(d−2d),bd:=dlog⁡(d−1)−(d−2)log⁡(d+1).a_d := \log(d-1) + \frac{d-2}{2}\log\left(\frac{d-2}{d}\right), \qquad b_d := d\log(d-1) - (d-2)\log(d+1).

We first establish an upper bound showing that, for any fixed d≥3d \ge3, the surplus cannot exceed order n/log⁡nn/\log n with high probability.

Theorem 1.4 (Second-order upper bound). For every fixed d≥3d \ge3 and every ε>0\varepsilon> 0,

lim⁡n→∞P(Sn≤(bd+ε)nlog⁡n)=1.\lim_{n\to\infty} \mathbb{P}\left(S_n \le(b_d+\varepsilon)\frac{n}{\log n}\right)=1.

The proof again uses a first-moment argument, but now after a structural reduction. Any overlap of size n+sn+s contains a common subgraph (a core) of minimum degree at least two and graph excess exactly ss. Counting these common cores and optimising over their number of vertices gives the constant bdb_d; the first moment is maximised by cores occupying asymptotically d/(d+1)d/(d+1) of the vertices.

For the lower bound, we first fix a Hamilton cycle in each graph and consider a permutation that perfectly aligns the two cycles, yielding an overlap of at least nn edges. Cyclically rotating this permutation preserves the alignment of all nn Hamiltonian edges, while changing the correspondence between the remaining edges. We exploit these nn possible rotations to search for additional overlaps beyond the Hamiltonian baseline. Using contiguity arguments, the residual edges can be analysed through a suitable random matching model. We then identify local configurations witnessing additional overlaps and control the dependencies among different rotations by selecting witnesses with distinct cyclic lengths. This yields a surplus of order log⁡n/log⁡log⁡n\log n/\log\log n with high probability.

To reach the larger scale n/log⁡nn/\log n, we need to pass from a single Hamilton cycle to a spanning collection of cycles of the same logarithmic length kk.

References

  1. [1]Béla Bollobás and Oliver Riordan, Sparse graphs: Metrics and random models, Random Struct. Algorithms 39 (2011), no. 1, 1–38.arxiv.org/abs/0812.2656
  2. [2]B. Bollobás and O. Riordan, Metrics for sparse graphs, London Mathematical Society Lecture Note Series, vol. 365, p. 211–288, Cambridge University Press, 2009.arxiv.org/abs/0708.1919
  3. [3]Gerandy Brito, Christopher Fowler, Matthew Junge, and Avi Levy, Ewens sampling and invariable generation, Combinatorics, Probability and Computing 27 (2018), no. 6, 853–891.arxiv.org/abs/1610.04212
  4. [4]Colin Cooper, Alan Frieze, and Michael Krivelevich, Hamilton cycles in random graphs with a fixed degree sequence, SIAM Journal on Discrete Mathematics 24 (2010), no. 2, 558–569.DOI
  5. [5]Colin Cooper, Alan Frieze, and Bruce Reed, Random regular graphs of non-constant degree: Connectivity and hamiltonicity, Combinatorics, Probability and Computing 11 (2002), no. 3, 249–261.DOI
  6. [6]Jian Ding, Hang Du, and Shuyang Gong, A polynomial-time approximation scheme for the maximal overlap of two independent Erdős–Rényi graphs, Random Structures Algorithms 65 (2024), no. 1, 220–257.arxiv.org/abs/2210.07823
  7. [7]Hang Du, Shuyang Gong, and Rundong Huang, The algorithmic phase transition of random graph alignment problem, Probab. Theory Related Fields 191 (2025), 1233–1288.arxiv.org/abs/2307.06590
  8. [8]Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li, A survey of graph edit distance, Pattern Analysis and Applications 13 (2010), no. 1, 113–129.DOI
  9. [9]Harrison Hartle, Brennan Klein, Stefan McCabe, Alexander Daniels, Guillaume St-Onge, Charles Murphy, and Laurent Hébert-Dufresne, Network comparison and the within-ensemble graph distance, Proc. R. Soc. A 476 (2020), 20190744.DOI
  10. [10]Svante Janson, Random regular graphs: Asymptotic distributions and contiguity, Combinatorics, Probability and Computing 4 (1995), no. 4, 369–405.DOI
  11. [11]⟨blank⟩, The probability that a random multigraph is simple, Combinatorics, Probability and Computing 18 (2009), no. 1–2, 205–225.DOI
  12. [12]Svante Janson, Tomasz Łuczak, and Andrzej Ruciński, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 2000.
  13. [13]Jeff Kahn, Eyal Lubetzky, and Nicholas Wormald, Cycle factors and renewal theory, Comm. Pure Appl. Math. 70 (2017), no. 2, 289–339.
  14. [14]Colin McDiarmid, On the method of bounded differences, Surveys in Combinatorics, 1989 (J. Siemons, ed.), London Mathematical Society Lecture Note Series, vol. 141, Cambridge University Press, 1989, pp. 148–188.DOI
  15. [15]Robert W. Robinson and Nicholas C. Wormald, Almost all regular graphs are Hamiltonian, Random Structures Algorithms 5 (1994), no. 2, 363–374.DOI
  16. [16]Alberto Sanfeliu and King-Sun Fu, A distance measure between attributed relational graphs for pattern recognition, IEEE Trans. Syst. Man Cybern. 13 (1983), no. 3, 353–362.DOI
  17. [17]Simon Tavaré, The magical Ewens sampling formula, Bulletin of the London Mathematical Society 53 (2021), no. 6, 1563–1582.DOI
  18. [18]Nicholas C. Wormald, Models of random regular graphs, Surveys in Combinatorics, 1999 (J. D. Lamb and D. A. Preece, eds.), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge University Press, Cambridge, 1999, pp. 239–298.

Paper details

vlnc:W_d9vhmadw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT6, Grammarly

View statement
Looking for related papers…
Contents