Learning Laplacian Matrix in Smooth Graph Signal Representations

The construction of a meaningful graph plays a crucial role in the success of many graph-based representations and algorithms for handling structured data, especially in the emerging field of graph signal processing. However, a meaningful graph is not always readily available from the data, nor easy to define depending on the application domain. In particular, it is often desirable in graph signal processing applications that a graph is chosen such that the data admit certain regularity or smoothness on the graph. In this paper, we address the problem of learning graph Laplacians, which is equivalent to learning graph topologies, such that the input data form graph signals with smooth variations on the resulting topology. To this end, we adopt a factor analysis model for the graph signals and impose a Gaussian probabilistic prior on the latent variables that control these signals. We show that the Gaussian prior leads to an efficient representation that favors the smoothness property of the graph signals. We then propose an algorithm for learning graphs that enforces such property and is based on minimizing the variations of the signals on the learned graph. Experiments on both synthetic and real world data demonstrate that the proposed graph learning framework can efficiently infer meaningful graph topologies from signal observations under the smoothness prior.

I. Introduction

Modern data processing tasks often manipulate structured data, where signal values are defined on the vertex set of a weighted and undirected graph. We refer to such data as graph signals, where the vertices of the graph represent the entities and the edge weights reflect the pairwise relationships between these entities. The signal values associated with the vertices carry the information of interest in observations or physical measurements. Numerous examples can be found in real world applications, such as temperatures within a geographical area, transportation capacities at hubs in a transportation network, or human behaviors in a social network. Such data representations have led to the emerging field of graph signal processing [1], [2], which studies the representation, approximation and processing of such structured signals. Currently, most of the research effort in this field has been devoted to the analysis and processing of the signals, which are defined on a graph that is a priori known or naturally chosen from the application domain, e.g., geographical or social friendship graphs. However, these natural choices of graphs may not necessarily describe well the intrinsic relationships between the entities in the data. Furthermore, a natural graph might not be easy to define at all in some applications. When a good graph is not readily available, it is desirable to learn the graph topology from the observed data such that it captures well the intrinsic relationships between the entities, and permits effective data processing and analysis. This is exactly the main objective of the present paper.