Structured Graph Learning Via Laplacian Spectral Constraints
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 possible to convert the structural constraints of structure into eigenvalue constraints of the graph Laplacian matrix. Then we introduce a unified graph learning framework, lying at the integration of the spectral properties of the Laplacian matrix with Gaussian graphical modeling that is capable of learning structures of a large class of graph families. The proposed algorithms are provably convergent and practically amenable for large-scale semi-supervised and unsupervised graph-based learning tasks. Extensive numerical experiments with both synthetic and real data sets demonstrate the effectiveness of the proposed methods. An R package containing code for all the experimental results is available at https://cran.r-project.org/package=spectralGraphTopology.
Code (2)
Tasks
Graph LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Graph Laplacian Wavelet Transformer via Learnable Spectral Decomposition
Existing sequence to sequence models for structured language tasks rely heavily on the dot product self attention mechanism, which incurs quadratic complexity in both computation and memory for input length N. We introdu…
On spectral partitioning of signed graphs
We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the lead…
Spectral Convergence Rate of Graph Laplacian
Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a $…
ClusteringDenoisingLarge sample spectral analysis of graph-based multi-manifold clustering
In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one …
ClusteringRoot Laplacian Eigenmaps with their application in spectral embedding
The root laplacian operator or the square root of Laplacian which can be obtained in complete Riemannian manifolds in the Gromov sense has an analog in graph theory as a square root of graph-Laplacian. Some potential app…
Clustering