PaperlayerView exact revision on arXiv

Source-linked AI summary

A statistical interpretation of spectral embedding: the generalised random dot product graph

Patrick Rubin-Delanchy, Joshua Cape, Minh Tang, Carey E. Priebe

arXiv:1709.05506v5stat.MLcs.LG

TL;DR

The paper addresses the inability of the random dot product graph to represent heterophilic connectivity and negative eigenvalues. It introduces the generalised random dot product graph and proves that adjacency or normalised-Laplacian spectral embeddings consistently estimate latent positions with asymptotically Gaussian error, while supporting community-analysis recommendations and a cyber-security application.

  • Problem

    The random dot product graph cannot model heterophilic connectivity patterns or graph structures with significant negative eigenvalues.

  • Method

    The paper introduces the GRDPG, an indefinite latent-position model, and analyzes adjacency and normalised-Laplacian spectral embeddings under this framework.

  • Results

    Spectral embeddings provide uniformly consistent latent-position estimates with asymptotically Gaussian error up to identifiability.

  • Takeaways & Limitations

    The theory supports Gaussian mixture modeling for stochastic-block-model spectral clustering and simplex-fitting under mixed membership, with practical application to cyber-security data.

  • Takeaways & Limitations

    The model’s alternative spectral estimand is constrained by identifiability choices, including indefinite orthogonal transformations and distribution-dependent community representatives.

Abstract

from arXiv · show

Spectral embedding is a procedure which can be used to obtain vector representations of the nodes of a graph. This paper proposes a generalisation of the latent position network model known as the random dot product graph, to allow interpretation of those vector representations as latent position estimates. The generalisation is needed to model heterophilic connectivity (e.g., `opposites attract') and to cope with negative eigenvalues more generally. We show that, whether the adjacency or normalised Laplacian matrix is used, spectral embedding produces uniformly consistent latent position estimates with asymptotically Gaussian error (up to identifiability). The standard and mixed membership stochastic block models are special cases in which the latent positions take only $K$ distinct vector values, representing communities, or live in the $(K-1)$-simplex with those vertices, respectively. Under the stochastic block model, our theory suggests spectral clustering using a Gaussian mixture model (rather than $K$-means) and, under mixed membership, fitting the minimum volume enclosing simplex, existing recommendations previously only supported under non-negative-definite assumptions. Empirical improvements in link prediction (over the random dot product graph), and the potential to uncover richer latent structure (than posited under the standard or mixed membership stochastic block models) are demonstrated in a cyber-security example.

1 Introduction

Spectral embedding offers statistical node representations, but the random dot product graph cannot model many graphs with negative eigenvalues or heterophilic connectivity. The paper introduces the GRDPG, which extends the model to indefinite structure and establishes consistency and asymptotic normality for spectral latent-position estimates.

  • Motivation: The random dot product graph interprets spectral embeddings as latent positions but assumes positive-definite connectivity structure.This excludes important graph patterns represented by negative eigenvalues.
  • Motivation: Negative eigenvalues arise in heterophilic, core-periphery, and some higher-community stochastic block models.For two communities, heterophily occurs when between-community connectivity exceeds both within-community connectivities.
  • Examples: Under stochastic block models, negative eigenvalues determine embedding geometry that can reveal communities through rays rather than standard positive-eigenvalue representations.The Harry Potter enmity graph uses one positive and one negative leading eigenvalue, producing two rays associated with inferred communities.
  • Model: The GRDPG uses the indefinite inner product x⊤I_p,qy, reducing to the standard random dot product graph when q = 0.The model retains latent positions while allowing negative directions in the connectivity kernel.
  • Theory: The paper reports that adjacency and normalised-Laplacian spectral embeddings yield uniformly consistent, asymptotically Gaussian latent-position estimates up to identifiability.These results extend the statistical interpretation of spectral embedding beyond positive-definite settings.
  • Implications: The framework motivates Gaussian-mixture spectral clustering and simplex-fitting recommendations while accommodating richer network connectivity than the random dot product graph.Real-world graph surveys and computer-network analysis motivate the need for this generalisation.

2 The data, spectral embedding, and model

The paper seeks a model-based rationale for spectral embedding by treating node vectors as latent-position estimates, including graphs with negative eigenvalues. It proposes an indefinite-inner-product model and relates standard, mixed-membership, and degree-corrected block models to that framework.

  • The data and spectral embedding: Spectral embedding represents graph nodes as vectors, using scaled eigenvectors of the adjacency or normalised Laplacian matrix.The adjacency embedding selects largest-magnitude signed eigenvalues; the Laplacian embedding analogously uses the normalised Laplacian.
  • The problem: The paper seeks latent positions whose spectral estimates have quantifiable error, with a suitable transformation serving as the Laplacian embedding’s estimand.
  • Why generalise the model: The random dot product graph cannot explain significant negative eigenvalues because its edge-probability matrix is positive semidefinite.Negative eigenvalues arise in settings such as heterophilic and core-periphery connectivity.
  • The generalised model: The GRDPG assigns edge probabilities through the indefinite inner product x⊤I_p,qy, allowing p positive and q negative dimensions.Here I_p,q has p ones followed by q minus ones on its diagonal.
  • Block-model special cases: Under the stochastic block model, communities correspond to K latent vectors, with d = rank(B) ≤ K and Xi = v_Zi.
  • Block-model special cases: Under mixed membership, Xi is a convex combination of community vectors and lies in their convex hull, a (K − 1)-simplex when B has full rank.Degree correction instead places Xi = w_i v_Zi on one of K rays from the origin.
  • Identifiability and parameterisations: Latent positions are identifiable only up to the indefinite orthogonal group O(p,q), which can change inter-point distances when q > 0.The paper therefore also introduces a spectral estimand, but its rows depend on the observed latent-position configuration and may not be i.i.d.

3 Asymptotics

The paper establishes consistency and asymptotic Gaussian error for GRDPG latent-position estimates from adjacency and Laplacian spectral embeddings, under stated sparsity conditions and up to identifiability. It also explains the transformations required for indefinite geometry and the implications for downstream inference.

  • Identifiability: The transformations align estimated, spectral, and latent positions because GRDPG parameters are identifiable only up to indefinite orthogonal transformations.When relevant eigenvalues are distinct, the transformations can reduce to sign reversals of eigenvectors.
  • Uniform consistency: Spectral estimates converge uniformly to GRDPG latent positions up to an indefinite orthogonal transformation when nρ_n grows faster than a polylogarithmic rate.The adjacency result requires nρ_n = ω(log^{4c} n) for a universal constant c > 1.
  • Asymptotic normality: For any fixed finite set of nodes, scaled adjacency-embedding errors converge to independent zero-mean Gaussian vectors conditional on their latent positions.The covariance is Σ(ξ_i), and the central limit theorem is obtained after applying the appropriate transformation.
  • Scope and limitations: A direct Gaussian interpretation relative to the original latent positions can fail because the alignment matrix may converge no faster than n^-1/2 and depends on F.This matters particularly when comparing graphs under a null hypothesis involving different latent-position distributions.
  • Downstream inference: Indefinite transformations can be immaterial for invariant procedures such as Gaussian mixture fitting and do not contradict consistency of K-means or simplex-fitting in supported settings.The paper specifically notes consistency of spectral clustering with K-means and simplex-fitting under the mixed membership stochastic block model.
  • Laplacian embedding: Laplacian spectral embedding has analogous uniform-consistency and central-limit results under the same sparsity conditions.The Laplacian results are stated in Theorems 6 and 7, with Gaussian limits described by the corresponding covariance matrix.

4 Implications for stochastic block model estimation

The asymptotic theory supports model-based spectral estimation for standard and mixed membership stochastic block models, including graphs with negative eigenvalues. It recommends Gaussian mixture modeling for spectral clustering and minimum volume simplex fitting for mixed membership estimation.

  • Supported algorithms: The proposed algorithms extend stochastic block model estimation to settings with negative eigenvalues, previously supported formally only under non-negative-definite block matrices.The mixed membership algorithm is unchanged, but its consistency with negative eigenvalues requires the paper’s asymptotic results.
  • Standard stochastic block model: Spectral clustering computes an adjacency or Laplacian embedding, then fits a Gaussian mixture model with K components to estimate communities.The mixture model allows varying volume, shape, and orientation, unlike the spherical solutions favored by K-means.
  • Standard stochastic block model: The theory recommends Gaussian mixture modeling rather than K-means because embedded community clusters are elliptical in theory and practice.K-means can produce inaccurate community separation, and numerical studies report higher misclassification rates for it.
  • Mixed membership stochastic block model: For mixed membership estimation, spectral embedding is projected onto a principal hyperplane and enclosed by a minimum volume K−1-simplex.Barycentric coordinates relative to the fitted simplex provide estimated community membership probability vectors.
  • Examples: In simulation, a two-community embedding is modeled with empirical and theoretically predicted Gaussian components, while a three-community embedding forms a noisy simplex whose enclosing simplex converges to the theoretical one.The examples use n = 2000 nodes for the two-community graph and n = 5000 nodes for the three-community graph.
  • Identifiability: Fitting the Gaussian mixture model directly to the observed embedding effectively accounts for the unobserved indefinite orthogonal transformation.The Gaussian mixture likelihood is unchanged under the corresponding transformation of data, means, and covariances.

5 Real data

The real-data analysis finds that negative spectral components are common and informative, motivating GRDPG-based embeddings for heterophilic networks. In the Los Alamos network, these embeddings support link prediction and reveal structure richer than standard block-model assumptions.

  • Survey of real-world graphs: Half of 24 surveyed real-world graphs had at least one estimated negative eigenvalue among their leading components.The smallest negative eigenvalue often ranked among the largest in magnitude.
  • Los Alamos network: The Los Alamos network contains no triangles, consistent with heterophilic connectivity arising from server/client structure and router locations.Its five-minute adjacency spectrum also contains abundant negative eigenvalues, outside the random dot product graph’s usual scope.
  • Link prediction: Negative eigenvalue components can contain important signal that the GRDPG models but the random dot product graph discards.The GRDPG retains the largest eigenvalues by magnitude, whereas the comparator retains only the largest positive eigenvalues.
  • Link prediction: GRDPG and random dot product graph embeddings are compared by predicting new edges in the subsequent five-minute window.The comparison uses adjacency spectral embeddings into dimension 10 and evaluates predictions with ROC curves.
  • Latent structure: The full Los Alamos graph contains roughly 12 thousand nodes and one hundred thousand edges, with structure richer than standard or mixed membership stochastic block models.Gaussian mixture modelling and t-SNE provide complementary visualisations of the spectral embedding, whose clusters associate with commonly used ports.

6 Conclusion

The paper introduces GRDPG as a latent position model that extends random dot product graphs to nonhomophilic connectivity while retaining standard network models as special cases. Its theory justifies spectral embedding as statistically interpretable latent-position estimation and supports improved community-analysis methods and cyber-security applications.

  • Contribution: GRDPG includes the stochastic block model, its extensions, and the random dot product graph as special cases.Its distinguishing capability is modelling nonhomophilic connectivity, including cases where opposites attract.
  • Theory: Spectral embedding yields uniformly consistent latent position estimates with asymptotically Gaussian error, up to identifiability.The result applies when using either the adjacency or normalised Laplacian matrix.
  • Implications: The paper uses this framework to motivate methodological improvements for community-structure estimation and demonstrate practical cyber-security applications.The conclusion presents these as consequences of the theoretical treatment of spectral embedding.

A.1 Distortion under the stochastic block model

The stochastic block model analysis shows that indefinite orthogonal transformations can distort Euclidean geometry across embeddings, making K-means unstable. Gaussian mixture modelling avoids this dependence because it is invariant to the transformation.

  • Indefinite transformations: Spectral embeddings from stochastic block models with different community proportions cannot be geometrically related without an indefinite orthogonal transformation.The experiment uses two graphs with the same block matrix but different community proportions.
  • Clustering consequences: Applying an indefinite orthogonal transformation before Euclidean K-means changes the resulting partition of the points.This means there is no obvious statistical reason to prefer the raw spectral configuration for K-means clustering.
  • Clustering consequences: Gaussian mixture modelling avoids these concerns because it is invariant to the indefinite transformation.The argument extends earlier evidence that Gaussian mixture modelling can outperform K-means under non-negative-definite stochastic block models.

A.2 Distortion under the degree-corrected stochastic block model

Under the degree-corrected stochastic block model, spectral embeddings form noisy rays whose Euclidean angles vary with degree weights. Hyperbolic angles remain invariant and provide a degree-heterogeneity-aware geometric measure.

  • Spectral geometry: With one positive and one negative eigenvalue, each embedded point cloud lies near two rays through the origin, up to an indefinite orthogonal transformation.The simulated graphs differ in their degree distributions while sharing the block matrix and community proportions.
  • Hyperbolic geometry: The hyperbolic angle between the rays is a consistently estimable population quantity that does not depend on node weights.It provides a natural measure of distance between communities under the stated regularity conditions.
  • Hyperbolic geometry: Hyperbolic angles remain equal across the two degree-weight configurations, whereas ordinary Euclidean angles visibly differ.The hyperbolic metric accounts for degree heterogeneity in the embedding.

B Uniqueness

The GRDPG is motivated as a latent-position model that faithfully represents connectivity-profile mixtures, including mixed-membership structure and settings beyond positive-definite dot products.

  • The GRDPG provides essentially the only faithful representation of connectivity-profile mixtures as convex combinations in latent space.
  • Mixture reproduction means convex combinations of latent positions preserve the corresponding convex combinations of connectivity probabilities.
  • This property lets a mixed latent position be interpreted either directly or as a randomized mixture of community-specific positions.
  • The mixed membership stochastic block model naturally uses this simplex interpretation, with simplex vertices representing communities and interior positions representing membership preferences.
  • Any finite-dimensional model with mixture-reproducing connectivity profiles can be represented as a GRDPG in at most one additional dimension.
  • For mixed membership, the additional dimension is necessary: the GRDPG uses d = 3 dimensions while latent positions lie on a 2-dimensional subset.

B.1 Proof of Theorem 9

Theorem 9 is proved by extending mixture-preserving connectivity functions to symmetric bi-affine forms, homogenising them, and expressing the result through an indefinite inner product.

  • The proof of Theorem 9 follows directly from the extension lemma and the homogenisation lemma.
  • A mixture-reproducing function extends exactly to a symmetric bi-affine form on the affine hull of the latent space.
  • Homogenisation embeds the affine representation into one extra coordinate and converts the bi-affine form into a bilinear form.
  • Diagonalising the symmetric matrix of the bilinear form separates positive and negative eigenvalues, yielding an indefinite inner-product representation.
  • The resulting representation has dimension d = p + q and uses the signature matrix I_p,q; nonnegative self-connectivity requires p > 0 unless the function is uniformly zero.

C Proof of Theorems 3 and 4

The proofs extend adjacency spectral-embedding theory from random dot product graphs to GRDPGs with positive and negative eigenspaces, using concentration and eigenvector perturbation tools.

  • Extending adjacency spectral-embedding results to GRDPGs requires new analytical methods and constitutes the paper’s main technical contribution.
  • The proof combines GRDPG concentration results with an eigenvector matrix series decomposition, rather than following trivially from earlier theorems.
  • The model assumes independent latent-position replicates and conditionally independent Bernoulli edges with means X_i^T I_p,q X_j.
  • The population eigenspace is partitioned into p positive and q negative components, while the empirical embedding selects the d largest-magnitude eigenvalues accordingly.
  • The proof first aligns empirical and population eigenspaces using an orthogonal matrix with block structure compatible with the indefinite inner product.
  • Canonical angles and the Davis–Kahan theorem control within-sign eigenspace alignment and cross-sign interactions.

C.2 Proof details

The proof derives a matrix-series expansion for empirical eigenvectors and then rescales it to obtain the decomposition used in the GRDPG embedding analysis.

  • The eigenvector equation is rewritten using the population matrix plus the adjacency fluctuation, enabling a matrix-series expansion for the empirical eigenvectors.
  • Rescaling empirical eigenvectors by the square root of the absolute empirical eigenvalues incorporates the indefinite sign structure through I_p,q.
  • The resulting expansion decomposes the rescaled embedding into three terms, V1 + V2 + V3.

C.2.1 The matrix V1

This section develops bounds for the matrix V1 and related terms using approximate commutativity, spectral perturbation, concentration, and asymptotic limit arguments. These steps support Theorems 3 and 4, including the limiting covariance expression obtained via the Cramér–Wold device.

  • The matrix V1: Approximate commutativity of U⊤Û and I_p,q enables further decomposition and bounding of the matrices M_k.The difference is controlled in spectral norm using Eq. (7).
  • The matrix V1: Hoeffding’s inequality and the Davis–Kahan theorem bound U⊤ÛŜ−SU⊤Û, supporting subsequent bounds on M_k.The argument decomposes U⊤(A−P)Û through UU⊤ and I−UU⊤.
  • The matrix V1: The proof controls successive matrix terms under the growth condition (nρ_n) = ω(d(log n)^4c), which implies (nρ_n) = ω(d(log n)^2).This condition is used to establish the stated asymptotic bounds.
  • The matrix V1: The law of large numbers and continuous mapping theorem yield convergence of the normalized Gram matrix to Δ−1, while the multivariate central limit theorem gives conditional convergence in distribution.These limits are combined with residual-matrix control and Slutsky’s theorem.
Loading 1709.05506v5…