UC Davis

Learning and signal processing methods over graphs have recently attracted significant attentions in dealing with structured data. Normal (traditional) graphs, however, only capture pairwise relationships among nodes and are not effective in representing and capturing some high-order relationships of data samples. Such high order data interactions are often important in many applications such as Internet of Things (IoT), multimedia processing and network analysis, thereby motivating the exploration of learning and signal processing through high-dimensional graphs. In this dissertation, we investigate theoretical foundations and practical applications of two different high-dimensional graphs: 1) multilayer networks, and 2) hypergraphs. Inspired by the properties of high-dimensional graphs, we also revisit certain aspects of signal processing and learning under normal graphs.

First, we study the behavior analysis of propagation over multilayer networks. Specifically, we focus on the cascading failure over multilayer complex systems. We first propose a scalable tensor-based framework to represent interdependent multilayer networks, before applying this framework to analyze the failure propagation based on a susceptible-infectious-susceptible (SIS) epidemic model. We derive the transition equations and failure threshold to characterize the failure propagation. To make the failure indicator analytically tractable and computationally efficient, we derive its upper and lower bounds, as well as its approximated expressions in special cases.

Second, we investigate signal processing over hypergraphs. Representing hypergraphs as tensors, we proposed a novel framework of hypergraph signal processing (HGSP). Defining a specific form of hypergraph signals and hypergraph signal shifting, we provide an alternative definition of hypergraph Fourier space based on the tensor decomposition, together with the corresponding hypergraph Fourier transform. To better interpret the hypergraph Fourier space, we analyze the resulting hypergraph frequency properties, including the concepts of frequency and bandlimited signals. We also establish theoretical foundation for the HGSP sampling theory and filter designs. Furthermore, we examine its applications in multimedia processing, including three-dimensional (3D) point clouds, images and videos.

Lastly, revisiting the traditional graphs, we investigate the development of graph convolutional networks from the perspective of graph signal processing (GSP). We reexamine the graph spectral convolution in GSP and define conditions for approximating spectrum wavelet via propagation in the vertex domain. We then propose alternative propagation models for the GCN layers and develop a Taylor-series based graph convolutional networks (TGCN) based on the aforementioned approximation conditions. Our experimental results in citation networks and point clouds validate the effectiveness of the proposed TGCN.