The paper derives Cramer-Rao bounds for Laplacian matrix estimation under various constraints.
problem Estimating Laplacian matrices with structural constraints and sparsity.
method Linear reparametrization and closed-form expressions for Cramer-Rao bounds tailored to Laplacian matrix estimation.
result The derived CRBs provide performance limits for Laplacian matrix estimation and are validated in various applications.
Transformers interpreted as probabilistic Laplacian Eigenmaps steps.
problem Improving transformer performance through probabilistic interpretation.
method Probabilistic Laplacian Eigenmaps model derivation and graph diffusion step.
result Subtracting identity from attention matrix improves transformer performance.
Extends spectral number variance convergence to random matrix ensembles for twisted Laplacians.
problem Spectral number variance convergence for twisted Laplacians and Dirac operators.
method Extends Rudnick's approach to Gaussian ensembles for twisted Laplacians and Dirac operators.
result Convergence to Gaussian ensembles for twisted Laplacians and Dirac operators.
Enhances clustering performance with a novel high-order Laplacian matrix.
problem Limited representation capability and insufficient information exploitation in multi-view spectral clustering.
method Proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix.
result Improves clustering performance through enhanced representation capacity of the learned optimal Laplacian matrix.
Survey of Laplacian-based methods for data dimensionality reduction and embedding.
problem Efficiently reducing high-dimensional data to lower dimensions while preserving important features and structures.
method Laplacian-based methods including spectral clustering, Laplacian eigenmap, locality preserving projection, graph embedding, and diffusion map.
result Comprehensive overview of various optimization variants and applications of Laplacian-based techniques.
The paper tackles sparse graph learning under Laplacian-related constraints, improving upon existing methods.
problem Learning a sparse undirected graph from multivariate data under Laplacian-related constraints.
method Modifications to penalized log-likelihood approaches to enforce total positivity and lasso/adaptive lasso penalties using ADMM.
result The proposed constrained adaptive lasso approach significantly outperforms existing Laplacian-based approaches.
A checkerboard graph of a special diagram of an oriented link is made a directed, edge-weighted graph in a natural way so that a principal minor of its Laplacian matrix is a Seifert matrix of the link. Doubling and weighting the edges of the graph produces a second Laplacian matrix such that a principal minor is an Ale…
New outlier detection method using graph Laplacian spectrum boosts performance.
problem Detecting outliers in large datasets efficiently.
method Boosted outlier detection based on graph Laplacian spectrum.
result Outperforms existing methods on synthetic datasets.
Paper proves conditions for estimating precision matrices with Laplacian constraints.
problem Estimating high-dimensional precision matrices with Laplacian constraints.
method Minimizing Stein's loss with conditions on graph connectivity and Laplacian constraints.
result High-dimensional consistency achieved with Laplacian constraints, independent of graph structure.
The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used in spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, K) is generally unknown a-priori. Consequently, the majority of t…
New theory for eigenvectors of generalized Laplacian matrices, addressing dependency issues.
problem Dependency in random matrix theory hinders eigenvector analysis for latent embeddings.
method Introduces generalized Laplacian matrices and a new asymptotic theory framework.
result Established asymptotic normalities for spiked eigenvectors and eigenvalues.
The smallest eigenvalues and the associated eigenvectors (i.e., eigenpairs) of a graph Laplacian matrix have been widely used for spectral clustering and community detection. However, in real-life applications the number of clusters or communities (say, K) is generally unknown a-priori. Consequently, the majority of …
New method for mixed memberships using symmetrized Laplacian inverse matrix.
problem Mixed memberships in community detection.
method Spectral clustering on symmetrized Laplacian inverse matrix.
result Mixed-SLIM methods outperform state-of-the-art methods.
Unified spectral clustering for sparse networks with heterogeneous degrees.
problem Efficiently detecting communities in sparse networks with varying degrees.
method Developed a parametrized regularized Laplacian matrix for spectral clustering.
result Improved parametrization accounts for network heterogeneity and community hardness.
Novel Haar-Laplacian for directed graphs enhances spectral graph applications.
problem Lack of suitable Laplacian for directed graphs in spectral graph theory.
method Inspired by Haar-like transformation, introduces a Hermitian matrix preserving direction and weight.
result HaarNet outperforms in weight prediction and denoising on directed graphs.
Dual regularized graph Laplacian improves spectral clustering for community detection.
problem Detecting clusters in networks with improved spectral clustering methods.
method Proposes dual regularized graph Laplacian for three spectral clustering approaches.
result Theoretical analysis shows DRSC and DRSLIM yield stable consistent community detection.
New invariant for special alternating links based on graph Laplacian.
problem Developing an invariant for special alternating links.
method Using the Laplacian matrix of the Tait graph, invariant is defined.
result A specific quadratic trace expression is invariant under flype moves.
Spectral sparsification improves Laplacian-constrained graph learning.
problem Improving accuracy of Laplacian-constrained graph learning.
method Spectral graph sparsification as a post-estimation operation.
result Improved accuracy of Laplacian-constrained graph learning.
Many problems in machine learning can be expressed by means of a graph with nodes representing training samples and edges representing the relationship between samples in terms of similarity, temporal proximity, or label information. Graphs can in turn be represented by matrices. A special example is the Laplacian matr…
The graph Laplacian is a standard tool in data science, machine learning, and image processing. The corresponding matrix inherits the complex structure of the underlying network and is in certain applications densely populated. This makes computations, in particular matrix-vector products, with the graph Laplacian a ha…
Study conic Laplacian on \(\mb P^1\) with explicit model and boundary data.
problem Modeling conic Laplacian on \(\mb P^1\) with specific boundary conditions.
method Fourier decomposition, Legendre equations, gluing map, Friedrichs spectrum, Weyl function.
result Explicit computation of eigenfunctions and \(S\)-matrix.
Using Roelcke formula for the Green function, we explicitly construct a basis in the kernel of the adjoint Laplacian on a compact polyhedral surface X and compute the S-matrix of X at the zero value of the spectral parameter. We apply these results to study various self-adjoint extensions of a symmetric Laplacian…
We prove a central limit theorem for the components of the eigenvectors corresponding to the d largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized La…
Manifold learning and dimensionality reduction techniques are ubiquitous in science and engineering, but can be computationally expensive procedures when applied to large data sets or when similarities are expensive to compute. To date, little work has been done to investigate the tradeoff between computational resourc…
The paper proves spectral convergence rates for graph Laplacian to manifold Laplace-Beltrami operator.
problem Spectral convergence of graph Laplacian to manifold Laplace-Beltrami operator.
method Analysis of Dirichlet form convergence and construction of approximate eigenfunctions via manifold heat kernel.
result Proves spectral convergence rates for Gaussian kernelized graph Laplacian.
We study the heat kernel asymptotics for the Laplace type differential operators on vector bundles over Riemannian manifolds. In particular this includes the case of the Laplacians acting on differential p-forms. We extend our results obtained earlier for the scalar Laplacian and present closed formulas for all heat in…
LAD detects anomalies in dynamic graphs using Laplacian matrix.
problem Anomaly detection in temporal graphs for real-world applications.
method LAD uses the spectrum of the Laplacian matrix to model graph snapshots and temporal dependencies.
result LAD outperforms state-of-the-art methods in synthetic and real-world datasets.
A new method for community detection in networks is presented.
problem Community detection in network analysis.
method Mixed regularized spectral clustering (Mixed-RSC) based on the regularized Laplacian matrix.
result The method is asymptotically consistent under mild conditions.
Novel GNN for signed and directed networks using magnetic signed Laplacian.
problem Efficiently modeling signed and directed networks for tasks like clustering and link prediction.
method Introduced a magnetic signed Laplacian for directed signed graphs, used it to construct a spectral GNN.
result Demonstrated effective performance on tasks involving signed and directional information.
Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We pro…
DeepVir uses deep matrix factorization to predict antivirals for COVID-19.
problem Predicting effective antivirals for COVID-19 using known drug-virus associations.
method Graphical deep matrix factorization with HyPALM optimization.
result DeepVir outperforms state-of-the-art techniques in predicting antivirals for COVID-19.
Complexity of signed graphs linked to Alexander polynomials and Lehmer's question.
problem Complexity of signed graphs and its relation to Alexander polynomials.
method Definition of graph complexity using Laplacian matrix and Mahler measure, linking to Alexander polynomials and Lehmer's question.
result Complexity growth of signed graphs is related to the growth rate of Alexander polynomials.
New algorithms detect and estimate rank-one signals with prior directional information.
problem Detecting and estimating rank-one signals with directional prior information.
method Construct nonlinear Laplacians and examine top eigenvalues and eigenvectors.
result Nonlinear Laplacian algorithms outperform direct spectral methods for biased signals.
S2MAM improves semi-supervised learning by selecting relevant variables and updating similarity metrics.
problem Joint learning from labeled and unlabeled data with geometric structure.
method Bilevel optimization scheme for automatic variable selection and similarity matrix update.
result The proposed S2MAM achieves robust and interpretable predictions.
This paper speeds up spectral clustering for large graphs by dilating their eigenspectrum.
problem Slow convergence in spectral clustering due to small eigengaps in graph Laplacians.
method Polynomial approximations to matrix operations that dilate the spectrum without changing eigenvectors.
result Significant acceleration of convergence in spectral clustering.
Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factoriza…
Grid security and open markets are two major smart grid goals. Transparency of market data facilitates a competitive and efficient energy environment, yet it may also reveal critical physical system information. Recovering the grid topology based solely on publicly available market data is explored here. Real-time ener…
Study on signed graphs with random signs, focusing on community detection.
problem Community detection in signed stochastic block models.
method Strong concentration inequalities for adjacency and Laplacian matrices, applied to signed Laplacian matrix.
result The sign of the first eigenvector of the Laplacian matrix defines a weakly consistent estimator for balanced community detection.
We provide a theoretical analysis of the representation learning problem aimed at learning the latent variables (design matrix) Θ of observations Y with the knowledge of the coefficient matrix X. The design matrix is learned under the assumption that the latent variables Θ are smooth with respect to a (known) t…
The spectral geometry of mesh matrices of graphs is explored, leading to new formulas and eigenvalue estimates.
problem Understanding the spectral properties of mesh matrices of graphs.
method Definition and study of mesh matrices, introduction of mesh Laplacian, derivation of characteristic polynomial formulas.
result Mesh Laplacian eigenvalues are all real and greater than or equal to 1, with a smallest positive eigenvalue estimated.
The paper develops a method to sparsify magnetic Laplacians using multi-type spanning forests.
problem Sparsifying magnetic Laplacians for large and dense graphs.
method Sampling multi-type spanning forests using a determinantal point process.
result The method provides statistical guarantees for estimating the connection Laplacian.
The paper explores learning graphs in financial markets using Laplacian constraints.
problem Learning undirected graphical models for financial assets.
method Alternating Direction Method of Multipliers for graph learning.
result Laplacian matrix as a model for financial assets' precision matrix.
Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. It is well known that structured graph learning from observed samples is an NP-hard combinatorial problem. In this paper, we first show that for a set of important graph families it is possib…
Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacia…
New method learns high-quality Laplacian representations for reinforcement learning.
problem Lack of accurate Laplacian representations in large or continuous state spaces.
method Reformulated spectral graph drawing objective to have eigenvectors as unique global minimizer.
result Learned Laplacian representations more faithfully approximate the ground truth.
Method estimates multiple related Gaussian distributions using Laplacian regularization.
problem Jointly estimate multiple related zero-mean Gaussian distributions.
method Laplacian regularized stratified model fitting with hyper-parameters to encourage covariance closeness.
result The method performs well, especially in low data regimes, as demonstrated in finance, radar, and weather.
We present a method based on the orthogonal symmetric non-negative matrix tri-factorization of the normalized Laplacian matrix for community detection in complex networks. While the exact factorization of a given order may not exist and is NP hard to compute, we obtain an approximate factorization by solving an optimiz…
New method clusters hypergraphs using weighted random walks and Laplacians.
problem Clustering hypergraph data with edge-dependent weights.
method Random walks with edge-dependent vertex weights, constructing hypergraph Laplacians for clustering.
result Proposed methods outperform existing hypergraph clustering algorithms.