A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference

1 Introduction

• The central challenge is to estimate shared graph parameters accurately while retaining power to detect differences across multiple graphs, including weighted, directed, or corrupted settings.The introduction also asks whether such procedures can scale and compare favorably with existing methods.Source: §1 · pp. 1–2
• Multiscale inference remains open: beyond comparing whole graphs, researchers seek to identify which subgraphs or vertices account for population-level differences.The motivation includes community classification and graph-level analysis analogous to ANOVA and post-hoc comparisons.Source: §1 · pp. 1–2
• The omnibus embedding jointly represents vertex-matched graphs and has a central limit theorem, enabling Euclidean inference while avoiding pairwise alignment.The introduction presents it as a way to address estimation, testing, and multiscale comparison in one procedure.Source: §1 · pp. 2–3
• The paper contributes consistency and central limit results for the embedding, addressing a literature with few distributional results for spectral decompositions of random graphs.The introduction compares these results with prior work on consistency and spectral central limit theorems.Source: §1 · p. 2
• Simulations show competitive latent-position estimates that retain graph-specific information, while the omnibus-derived test improves on a state-of-the-art two-graph procedure.The comparison concerns testing whether two random dot product graphs have the same latent positions.Source: §1 · p. 3

2 Summary of main results and applications to real data

• The embedding gives each vertex one point per graph, enabling graph-equality testing without further Procrustes alignment and vertex-level inference with meaningful simulated testing power.The authors report improved power over state-of-the-art methods in simulated two-graph testing and extend the approach to multisample inference.Source: §2 · pp. 5–6
• Under equal latent positions, omnibus rows consistently estimate shared positions and are near-optimal; scaled rows are asymptotically Gaussian mixtures under mild assumptions.The consistency result bounds error simultaneously across latent positions, while the limiting-distribution result assumes i.i.d. latent positions and conditionally independent graph realizations.Source: §2 · pp. 5–6

2.1 Discerning vertex-level difference in paired brain scans of human subjects

• In BNU dMRI, omnibus dissimilarities clustered 114 graphs into three groups, and vertex-wise MANOVA highlighted Vertex 98 as a contributor to between-graph differences.The analysis is exploratory: clusters are post-hoc, so embedded vectors are not independent samples, and asymptotic normality applies to a finitely fixed collection of rows.Source: §2.1 · pp. 8–9

2.2 Identifying brain regions associated with schizophrenia

• For COBRE, the authors apply omnibus embedding to 123 scans from 54 schizophrenic patients and 69 healthy controls to test population differences at each of 264 brain-region vertices.The supplied passage describes the testing setup, not its resulting significant vertices.Source: §2.2 · pp. 9, 12
• A three-dimensional omnibus embedding jointly represents 123 weighted brain graphs from 54 schizophrenic and 69 healthy patients, enabling Hotelling’s t2 tests for each of 264 regions.Each region receives a p-value measuring whether its estimated latent positions differ in distribution between the two patient groups; permutation tests yield broadly similar results.Source: §2.2 · pp. 12–13
• Figure 8 shows left-skewed p-value histograms suggesting differences in the default mode, sensory/somatomotor hand, and uncertain parcels.The histograms summarize region-level p-values within each of the 14 Power parcels; largely similar populations are expected to produce roughly flat histograms.Source: §2.2 · p. 13
• Alignment across all 123 graphs makes it possible to summarize vertex-level population differences with little processing in a display interpretable to domain specialists.The results can be aggregated into Power parcels to indicate which subnetworks may be involved in schizophrenia.Source: §2.2 · p. 13

3.1 Notation and Definitions

• In a random dot product graph, vertices have latent positions whose inner products determine edge probabilities, and edges are conditionally independent given those positions.The model is defined for hollow, undirected graphs and is identifiable only up to orthogonal transformation.Source: §3.1 · pp. 13, 15
• A joint random dot product graph comprises conditionally independent graphs sharing the same latent positions, with each graph's edges generated from those positions.The latent positions are i.i.d. from a common inner-product distribution; the paper holds its dimension and second-moment matrix constant in n while allowing the number of graphs to grow.Source: §3.1 · p. 15
• Adjacency spectral embedding estimates latent positions from the top d eigenvalues and corresponding eigenvectors of a graph's adjacency matrix.The adjacency matrix is treated as a noisy version of the unobserved probability matrix.Source: §3.1 · p. 15
• The sample-mean adjacency embedding estimates shared positions but collapses the graphs, making it unsuitable for comparing their positions graph by graph.The omnibus approach instead retains a distinct d-dimensional representation for each graph while using a single spectral decomposition.Source: §3.1 · p. 16
• The omnibus embedding applies adjacency spectral embedding to a block matrix whose diagonal blocks are the input graphs and whose off-diagonal blocks are pairwise averages.Under the joint model, its rows estimate the repeated latent positions across graphs, up to an orthogonal rotation.Source: §3.1 · p. 16

Consistency

• The omnibus embedding provides uniformly consistent estimates of all latent positions, up to an orthogonal transformation.The consistency result is in the 2 → ∞ norm.Source: §4 · pp. 16–17

Central limit theorem

• As the number of embedded graphs increases, the omnibus estimator’s variance decreases.The paper derives the explicit variance of the omnibus matrix as part of establishing the limiting result.Source: §4 · p. 17
• The omnibus embedding’s row-wise estimation error is asymptotically Gaussian, without requiring distinct eigenvalues of the second-moment matrix.The proof separates a classical-CLT summand from residual terms that converge to zero; handling the residuals requires different bounds than Athreya et al. (2016).Source: §4 · p. 17

5.1 Recovery of Latent Positions

• OMNIbar performs nearly identically to mean-graph ASE, while Procrustes alignment is notably inferior at graph sizes of 80–200 vertices.The mean-graph embedding is described as a low-variance estimate; the omnibus embedding also outperforms Procrustes for some graph sizes, including 80–100 vertices.Source: Figure 9 · p. 18, §5.1 · pp. 18–19

5.2 Two-graph Hypothesis Testing

• The testing experiments use known latent positions for the first graph to sample the true null distribution; without this, estimation noise may overwhelm signals from a few changed positions.The authors note that without the known expected matrix, tens of thousands of vertices would be required for latent-position estimation variance not to overwhelm that signal.Source: §5.2 · p. 20
• For k = 5 and k = 10 altered latent positions, the omnibus test has higher power than the Procrustes test, especially for graphs with 30–250 vertices.When only one position changes, neither method has power much above 0.25; both improve as graph size increases. Figure 10 reports power over 1000 trials.Source: §5.2 · p. 20, Figure 10 · p. 21
• At n = 50 vertices, omnibus-test performance clearly improves as drift parameter λ increases, while Procrustes-test performance stays more or less flat; omnibus performance climbs well above Procrustes for λ > 0.8.At n = 200 vertices, both methods perform approximately equally, though omnibus appears to consistently outperform Procrustes testing.Source: §5.2 · p. 21

6 Discussion and Conclusion

• The omnibus embedding yields competitive latent-position estimates and asymptotic normality results that support classical Euclidean inference for comparing graph populations.The paper describes its estimation accuracy as competitive with state-of-the-art spectral approaches.Source: §6 · p. 21
• Analyses of two collections of noisy, weighted brain scans identify brain regions and vertices responsible for graph-level differences.The analyses are presented as illustrations of multiscale inference on real data.Source: §6 · p. 22
• As the number of graphs m grows, the omnibus embedding can substantially reduce row variance, with its asymptotic variance conjectured to match embedding the mean adjacency matrix.Figure 9 provides weak evidence that the mean-squared errors of omnibus- and Procrustes-based estimates are close to those from the mean-adjacency estimate.Source: §6 · pp. 22–23
• For multiple-graph testing, the omnibus structure incorporates alignment a priori, avoiding separate Procrustes alignments that may introduce variance and harm inference.The authors report that simulations show better performance than a Procrustes-based equality test, especially for moderately sized graphs.Source: §6 · p. 23
• In the BNU1 analysis, centering the graphs is reported to improve difference detection, though the authors offer conjectures rather than an established explanation.Proposed explanations include better assessment of covariance structure, mitigation of degree heterogeneity, and dampening noisy common-subgraph effects.Source: §6 · p. 24
• The impact of centering remains an open problem, alongside extensions to correlated, weighted, or occluded graphs and tests that identify which graphs differ.The discussion also identifies comparative estimator efficiency and behavior under unequal graph distributions as open questions.Source: §6 · p. 24

• Theorem 1 follows by showing that the h-th row of √nH converges in probability to 0 and that of √nN converges in distribution to a mixture of normals, then applying Slutsky’s theorem.The consistency result and supporting lemmas provide the groundwork for the first convergence.Source: SUPPLEMENTARY MATERIAL · p. 27
• With high probability, the omnibus matrix satisfies ∥M − EM∥ ≤ Cmn^1/2 log^1/2(mn), yielding eigenvalue closeness to those of EM via Weyl’s inequality.The proof applies a matrix Bernstein inequality to the omnibus matrix.Source: SUPPLEMENTARY MATERIAL · p. 27
• The population omnibus matrix ˜P has eigenvalues mλ1 through mλd and zeros thereafter; the eigenvalues of P concentrate around nλi(EYYT) within 2d√n log n with probability at least 1 − d²/n².The supplement also states that λi(˜P) ≤ Cnmδ with high probability.Source: SUPPLEMENTARY MATERIAL · p. 28
• The supplement establishes consistency of the omnibus embedding up to an orthogonal transformation, with a high-probability rowwise error bound.The stated bound scales with m^1/2 log(mn)/√n.Source: SUPPLEMENTARY MATERIAL · p. 33

Supplementary Material

• Conditional on latent position X_i = x_i, the aligned estimate has an asymptotic normal limit with covariance Σ(x_i).The covariance depends on x_i; integrating over its distribution yields the unconditional mixture.Source: SUPPLEMENTARY MATERIAL · pp. 34, 36
• Theorem 1 follows by showing the row-wise embedding error is negligible and applying Slutsky’s theorem to the mixture-of-normals limit.The proof decomposes the scaled row into terms N and H; √nH converges in probability to zero, while √nN converges in distribution to a mixture of normals.Source: SUPPLEMENTARY MATERIAL · p. 37