Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs

• URL: http://arxiv.org/abs/2608.10845v1
• Date: Tue, 11 Aug 2026 12:16:29 GMT
• Title: Spectral Embeddings of Degree-$α$ Laplacians in Random Dot Product Graphs
• Abstract summary: We show how degree normalization affects both population geometry and the local uncertainty of embedded nodes.<n>The favored normalization depends on network density, community imbalance, and block-probability structure.<n>These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.
• Score: 3.133932152358817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.

Related papers

• Muon Dynamics as a Spectral Wasserstein Flow [21.689846521201588]
  We introduce a family of Wasserstein norms on positive semidefinite matrices.<n>We prove the equivalence between the static and dynamic Benamou-Brenier formulations.<n>We identify exact gradientity associated with flow models.
  arXiv  Detail & Related papers  (2026-04-06T17:41:12Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Rethinking Diffusion Models with Symmetries through Canonicalization with Applications to Molecular Graph Generation [56.361076943802594]
  CanonFlow achieves state-of-the-art performance on the challenging GEOM-DRUG dataset, and the advantage remains large in few-step generation.
  arXiv  Detail & Related papers  (2026-02-16T18:58:55Z)
• On the Normalization of Confusion Matrices: Methods and Geometric Interpretations [2.4097006540200434]
  We introduce bistochastic normalization using Iterative Proportional Fitting.<n>Unlike standard normalizations, this method recovers the underlying structure of class similarity.<n>We show a correspondence between confusion matrix normalizations and the model's internal class representations.
  arXiv  Detail & Related papers  (2025-09-05T09:36:51Z)
• Alleviating Structural Distribution Shift in Graph Anomaly Detection [70.1022676681496]
  Graph anomaly detection (GAD) is a challenging binary classification problem. Gallon neural networks (GNNs) benefit the classification of normals from aggregating homophilous neighbors. We propose a framework to mitigate the effect of heterophilous neighbors and make them invariant.
  arXiv  Detail & Related papers  (2024-01-25T13:07:34Z)
• The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks [117.93273337740442]
  We show that gradient descent converges to a uniform margin classifier on the training data with an $exp(-Omega(log2 t))$ convergence rate. We also show that batch normalization has an implicit bias towards a patch-wise uniform margin.
  arXiv  Detail & Related papers  (2023-06-20T16:58:00Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model [1.2891210250935143]
  We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the block model. We prove that spectral clustering is able to achieve exact recovery of the planted community structure under conditions that match the information-theoretic limits.
  arXiv  Detail & Related papers  (2020-04-21T07:16:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.