Research On Graph Learning Methods Under Laplacian Constraints

With the rapid development of information technology,the trend of the interconnection of everything and the ubiquity of data is obvious,and data are characterized by massive,structured,high-dimensional,and low-rank.If we can capture the structural characteristics of data and take advantage of them,it will help people to better collect,store,transmit and exploit data.Graph is a crucial tool to represent abstractly the topological structure of data entities.Once a meaningful graph has been established for the data entities,the data can be systematically analyzed and processed using spectral graph theory and signal processing methods.However,because not all graphs are known beforehand,graph learning research has been developed in an effort to infer potential graph structure information from observations.Graph Laplacian matrix is a matrix representation of graphs,which reflects the structure information of the graph and has special spectral characteristics,making it one of the core contents of spectral graph theory research and widely used in machine learning,graph signal processing,and other fields.Especially in graph signal processing,graph Fourier transform,graph filtering,and other concepts are defined based on the graph Laplacian matrix.In the Gaussian graphical models,the precision matrix of the attractive DC-intrinsic Gaussian Markov random field is a Laplacian matrix,the associated random variables follow a degenerate multivariate Gaussian distribution and have non-negative partial correlations,making the graph Laplacian matrix statistically significant as well.Based on the theories of graph signal processing and the Gaussian graphical models,this dissertation focuses on investigating the methods of inferring graph Laplacian matrices from observations,in order to obtain graph structure information,reveal the correlation between data entities,and provide technical support for signal analysis and processing within the framework of Laplacian theory,and its primary contents are as follows:1.Graph Laplacian matrix learning from the spatiotemporal smooth signal is proposed for the signals which change smoothly in time and space.Firstly,the Cartesian product is used to construct the joint time-vertex graph,and the observed signal is represented as a linear combination of low-frequency components in the joint time-vertex graph frequency domain,and the spatiotemporal smooth graph signal representation model is established.Secondly,by maximum a posteriori estimation,the graph learning problem with the joint graph Laplacian matrix and the reconstructed graph signal as the optimization variables is formulated.Finally,the graph learning problem is decomposed according to the properties of the Cartesian product graph,and the subproblems are solved alternately by using the primal-dual and conjugate gradient descent algorithms.The Laplacian matrix of the time graph and vertex graph is obtained by constraining the spatiotemporal smoothness of the reconstructed graph signal.The proposed method uses the graph Laplacian matrices to reconstruct the graph signals in time and space domains while learning the graphs.In the noise and missing data scenarios,the accuracy of the graph signal reconstruction is good,thus guaranteeing the graph learning performance.The results of the experiments demonstrate that even with a signal sampling rate of 0.5,the proposed method can still obtain accurate results and is superior to the comparative graph learning method.2.The observations of the physical system may be affected by potential factors.The latent variable Gaussian graphical model under Laplacian constraints can be used to characterize the influence of potential factors if the observations follow a degenerate multivariate Gaussian distribution and have non-negative partial correlations.Given the latent variables,the conditional precision matrix of the observed variables is sparse.However,the latent variables are unknown,the general graph learning method under Laplacian constraints can only estimate the marginal precision matrix of the observed variables,which has a non-sparse structure of “sparse + low-rank”.The sparsity of a graph plays a crucial role both statistically and computationally,therefore,the proposed method to separate the “sparse term” and “low-rank term” while estimating the marginal precision matrix,where the “sparse term” is the conditional precision matrix of observed variables,whose sparse pattern can show the pairwise conditional independence between the observed variables.First,the optimization problem is formulated by maximizing the marginal likelihood function of the observed variables,whose optimal variables are the marginal precision matrix,conditional precision matrix,and low-rank matrix,respectively.Then,the graph learning problem is further constrained to a convex optimization problem with specific matrix variables by proving that the three optimal variables have special matrix properties,namely,combinatorial Laplacian,diagonally dominant Laplacian,and non-negativity.Finally,three objective matrices are obtained by the multi-block alternating direction multipliers algorithm.Experimental results show that the proposed method can effectively infer the sparse pattern of the conditional precision matrix in the presence of latent variables,and provide sparse graphs for subsequent signal analysis and processing tasks.3.In large-scale networks,centralized graph learning is difficult due to the limitations of data samples,communication bandwidth,and computational resources.To address this issue,we propose a distributed graph learning method under Laplacian and structural constraints.A low-dimensional local optimization problem under Laplacian and structural constraints is first formulated by defining the local neighborhood of each vertex and maximizing the marginal likelihood function of the local variables.The local problem is then solved by the block coordinate descent algorithm.The global Laplacian matrix is then formed by single information transfer,merging,and symmetrization after parameters are extracted from the solution of each local problem.The proposed distributed graph learning method has low computational complexity,can be parallelized,and can achieve the statistical accuracy of global estimation without sampling error.The experimental results support the aforementioned theoretical results.