text: We study an extention of total variation denoising over images to over Cartesian power graphs and its applications to estimating non-parametric network models. The power graph fused lasso (PGFL) segments a matrix by exploiting a known graphical structure, @math , over the rows and columns. Our main results shows that for any connected graph, under subGaussian noise, the PGFL achieves the same mean-square error rate as 2D total variation denoising for signals of bounded variation. We study the use of the PGFL for denoising an observed network @math , where we learn the graph @math as the @math -nearest neighborhood graph of an estimated metric over the vertices. We provide theoretical and empirical results for estimating graphons, a non-parametric exchangeable network model, and compare to the state of the art graphon estimation methods.
  @cite_13: We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized first-order approximation of spectral graph convolutions. Our model scales linearly in the number of graph edges and learns hidden layer representations that encode both local graph structure and features of nodes. In a number of experiments on citation networks and on a knowledge graph dataset we demonstrate that our approach outperforms related methods by a significant margin.
  @cite_30: Matrix factorization techniques have been frequently applied in information retrieval, computer vision, and pattern recognition. Among them, Nonnegative Matrix Factorization (NMF) has received considerable attention due to its psychological and physiological interpretation of naturally occurring data whose representation may be parts based in the human brain. On the other hand, from the geometric perspective, the data is usually sampled from a low-dimensional manifold embedded in a high-dimensional ambient space. One then hopes to find a compact representation,which uncovers the hidden semantics and simultaneously respects the intrinsic geometric structure. In this paper, we propose a novel algorithm, called Graph Regularized Nonnegative Matrix Factorization (GNMF), for this purpose. In GNMF, an affinity graph is constructed to encode the geometrical information and we seek a matrix factorization, which respects the graph structure. Our empirical study shows encouraging results of the proposed algorithm in comparison to the state-of-the-art algorithms on real-world problems.
  @cite_4: 
  @cite_8: 
  @cite_32: We introduce a family of kernels on graphs based on the notion of regularization operators. This generalizes in a natural way the notion of regularization and Greens functions, as commonly used for real valued functions, to graphs. It turns out that diffusion kernels can be found as a special case of our reasoning. We show that the class of positive, monotonically decreasing functions on the unit interval leads to kernels and corresponding regularization operators.
  @cite_3: Piecewise smooth (PWS) images (e.g., depth maps or animation images) contain unique signal characteristics such as sharp object boundaries and slowly varying interior surfaces. Leveraging on recent advances in graph signal processing, in this paper, we propose to compress the PWS images using suitable graph Fourier transforms (GFTs) to minimize the total signal representation cost of each pixel block, considering both the sparsity of the signal’s transform coefficients and the compactness of transform description. Unlike fixed transforms, such as the discrete cosine transform, we can adapt GFT to a particular class of pixel blocks. In particular, we select one among a defined search space of GFTs to minimize total representation cost via our proposed algorithms, leveraging on graph optimization techniques, such as spectral clustering and minimum graph cuts. Furthermore, for practical implementation of GFT, we introduce two techniques to reduce computation complexity. First, at the encoder, we low-pass filter and downsample a high-resolution (HR) pixel block to obtain a low-resolution (LR) one, so that a LR-GFT can be employed. At the decoder, upsampling and interpolation are performed adaptively along HR boundaries coded using arithmetic edge coding, so that sharp object boundaries can be well preserved. Second, instead of computing GFT from a graph in real-time via eigen-decomposition, the most popular LR-GFTs are pre-computed and stored in a table for lookup during encoding and decoding. Using depth maps and computer-graphics images as examples of the PWS images, experimental results show that our proposed multiresolution-GFT scheme outperforms H.264 intra by 6.8 dB on average in peak signal-to-noise ratio at the same bit rate.
  @cite_19: 
  @cite_5: 
  @cite_34: 
  @cite_10: 
  @cite_12: 
  @cite_17: We propose a novel discrete signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional discrete signal processing theory to structured datasets by viewing them as signals represented by graphs, so that signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph signals in the frequency domain.
summary: Graph signal processing refers to methods that denoise, localize, detect, and predict signals over graphs. For example, each vertex corresponds to a low-powered sensor, and we would like to denoise sensor measurements, and we use the graph structure is based on communication between the sensors or spatial proximity. The driving assumption is that there is some underlying signal that in some way respects' the graph topology, and specifies the distribution of the observations. Many of the tools in signal processing and supervised learning can be extended to the graph case, such as Fourier analysis @cite_17 @cite_3 , wavelets @cite_10 @cite_34 @cite_8 , graph kernels @cite_32 , and convolutional networks @cite_13 @cite_19 . Graph structure has previously been used in matrix completion and network denoising problems (see for example, @cite_30 @cite_4 @cite_12 @cite_5 ), but these methods require some predetermined graph structure, such as knowledge graphs, so are not well suited to estimating graphons, and they do not perform segmentation, which is the focus of this work.