Dimensionality Reduction And Reconstruction For Graph Signals

With the advent of the era of dig data, the large amount, high dimensional and irregular features that lie in data bring new challenge to information processing methods.Signal processing on graphs is an emerging field in information science, where theory and methods for signal and information processing in discrete irregular domain are studied. It can provide new insights and new solutions for the information processing in the new era. Dimensionality reduction is a key component for solving problems in high dimension, and reconstruction methods are essential tools for solving inverse problems.Both of them find important applications in the field of signal processing on graphs. Currently, this field is still in its infancy. In this thesis, we focus on three problems in this field: graph signal coarsening(GSC), sampling and reconstruction for bandlimited graph signals, and the reconstruction of Boolean signals on graphs. The main contributions are as follows.1. For GSC, a metric for evaluating GSC algorithms is proposed, which is called Spectral Diversity. It is able to measure the spectral domain similarity between any graph signals. In order to obtain the coarsened signal when the coarsened graphs is known, Spectral Bin method is proposed and is proved to be the optimal method when measured by spectral diversity. A successive GSC algorithm is designed based on spectral bin method. Current GSC methods suffer from the isolation of graph coarsening and signal coarsening. In order to solve the problem, a joint GSC method with the object of minimizing spectral diversity between the original and coarsened graph signals is proposed. In the design process, it is proved that the spectrum of the coarsened graph should be a subset of that of the original graph,and we propose to use ADMM and optimization methods on manifolds to get a graph signal from the spectra. Experiment results show that the proposed methods are able to achieve both vertex domain similarity and spectral domain similarity.Comparisons demonstrate that the proposed methods overwhelm existing ones for the object of achieving spectral domain similarity.2. For the problem of sampling and reconstruction for bandlimited graph signals,we point out its similarity with irregular sampling problem in the time domain.Based on such similarity, two reconstruction methods for bandlimited graph signals, called IPR and IWR, are proposed. Experiments show that our methods converge significantly faster with both exact and approximate algorithm implementations, for both random graphs and real-world graphs.3. A special case for the reconstruction of Boolean signals on graphs is studied, which has its roots in the Sybil detection problem for directed social networks. A class of metric for evaluating graph partitions are proposed, which can degenerate to Modularity with appropriate parameters; the method for optimizing the metric is designed; based on the selection of measuring functions, the Sybil detection method for directed social network is proposed. Experiments demonstrate the effectiveness of the proposed method, suffering from no false positive rate and low false alarm rate. Comparisons with Sybil Defender, best Sybil detection method in undirected networks show that the performance of the proposed method is much better than Sybil Defender. Our research is the first one aiming for solving the Sybil detection problem in directed social networks, and can find applications in the defense against spammers in social networks.