archives@tulane.edu / 1 / Junqi Wang

A massive amount of data is being generated at an unprecedented level from a diversity of sources, including social media, internet services, biological studies, physical infrastructure monitoring and many others. The necessity of analyzing such complex data has led to the birth of an emerging framework, graph signal processing. This framework offers an unified and mathematically rigorous paradigm for the analysis of high-dimensional data with complex and irregular structure. It extends fundamental signal processing concepts such as signals, Fourier transform, frequency response and filtering, from signals residing on regular lattices, which have been studied by the classical signal processing theory, to data residing on general graphs, which are called graph signals. In this thesis, we consider five fundamental tasks on graphs from the perspective of graph signal processing: representation, sampling, recovery, detection and localization. Representation, aiming to concisely model shapes of graph signals, is at the heart of the proposed techniques. Sampling followed by recovery, aiming to reconstruct an original graph signal from a few selected samples, is applicable in semi-supervised learning and user profiling in online social networks. Detection followed by localization, aiming to identify and localize targeted patterns in noisy graph signals, is related to many real-world applications, such as localizing virus attacks in cyber-physical systems, localizing stimuli in brain connectivity networks, and mining traffic events in city street networks, to name just a few. We illustrate the power of the proposed tools on two real-world problems: fast resampling of 3D point clouds and mining of urban traffic data.

Large-scale networks are becoming more prevalent, with applications in healthcare systems, financial networks, social networks, and traffic systems. The detection of normal and abnormal behaviors (signals) in these systems presents a challenging problem. State-of-the-art approaches such as principal component analysis and graph signal processing address this problem using signal projections onto a space determined by an eigendecomposition or singular value decomposition. When a graph is directed, however, applying methods based on the graph Laplacian or singular value decomposition causes information from unidirectional edges to be lost. Here we present a novel formulation and graph signal processing framework that addresses this issue and that is well suited for application to extremely large, directed, sparse networks. In this thesis, we develop and demonstrate a graph Fourier transform for which the spectral components are the Jordan subspaces of the adjacency matrix. In addition to admitting a generalized Parseval’s identity, this transform yields graph equivalence classes that can simplify the computation of the graph Fourier transform over certain networks. Exploration of these equivalence classes provides the intuition for an inexact graph Fourier transform method that dramatically reduces computation time over real-world networks with nontrivial Jordan subspaces. We apply our inexact method to four years of New York City taxi trajectories (61 GB after preprocessing) over the NYC road network (6,400 nodes, 14,000 directed edges). We discuss optimization strategies that reduce the computation time of taxi trajectories from raw data by orders of magnitude: from 3,000 days to less than one day. Our method yields a fine-grained analysis that pinpoints the same locations as the original method while reducing computation time and decreasing energy dispersal among spectral components. This capability to rapidly reduce raw traffic data to meaningful features has important ramifications for city planning and emergency vehicle routing.

Graph Signal Processing (GSP) has been used in the analysis of functional Magnetic Resonance Imaging(fMRI). As a holistic view of brain function and the connections between and within brain regions, by structuring data as node points within the brain and modelling the edge connections between nodes. Many studies have used GSP with Blood Oxygenation Level Dependent (BOLD) imaging of the brain and brain activation. Meanwhile, the methodology has seen little use in muscle imaging. Similar to brain BOLD, muscle BOLD (mBOLD) also aims to demonstrate muscle activation. Muscle BOLD depends on oxygenation, vascularization, fibre type, blood flow, and haemoglobin count. Nevertheless the mBOLD signal still follows muscle activation closely. Electromyography (EMG) is another modality for measuring muscle activation. Both mBOLD and EMG can be represented and analyzed with GSP. In order to better understand muscle activation during contraction the proposed method focused on using GSP to model mBOLD data both alone and jointly with EMG. Simultaneous mBOLD imaging and EMG recording of the calf muscles was performed, creating a multimodal dataset. A generalized filtering methodology was developed for the removal of the MRI gradient artifact in EMG sensors within the MR bore. The filtered data was then used to generate a GSP model of the muscle, focusing on gastrocnemius, soleus, and tibialis anterior muscles. The graph signals were constructed along two edge connection dimensions; coherence and fractility. For the standalone mBOLD graph signal models, the models’ goodness of fits were 1.3245 × 10-05 and 0.06466 for coherence and fractility respectively. The multimodal models showed values of 2.3109 × -06 and 0.0014799. These results demonstrate the promise of modelling muscle activation with GSP and its ability to incorporate multimodal data into a singular model. These results set the stage for future investigations into using GSP to represent muscle with mBOLD, EMG, and other biosignal modalities. / Thesis / Master of Applied Science (MASc) / Magnetic Resonance Imaging(MRI) and electromyography (EMG) are techniques used in the analysis of muscle, for detecting injury or deepening the understanding of muscle function. Graph Signal Processing (GSP) is a methodology used to represent data and the information flow between positions. While GSP has been used in modelling the brain, applications to muscle are scarce. This work aimed to model muscle activation using GSP methods, using both MRI and EMG data. To do so, a method for being able to simultaneously record MRI and EMG data was developed through hardware construction and the software implementation of EMG signal filtering. The collected data were then used to construct multiple GSP models based on the coherence and complexity of the signals, the goodness of fit for each of the constructed models were then compared. In conclusion, it is feasible to use GSP to model muscle activity with multimodal MRI and EMG data. This shows promise for future investigations into the applications of GSP to muscle research.

Graph signal processing analyzes signals supported on the nodes of a network with respect to a shift operator matrix that conforms to the graph structure. For shift-invariant graph filters, which are polynomial functions of the shift matrix, the filter response is defined by the value of the filter polynomial at the shift matrix eigenvalues. Thus, information regarding the spectral decomposition of the shift matrix plays an important role in filter design. However, under stochastic conditions leading to uncertain network structure, the eigenvalues of the shift matrix become random, complicating the filter design task. In such case, empirical distribution functions built from the random matrix eigenvalues may exhibit deterministic limiting behavior that can be exploited for problems on large-scale random networks. Acceleration filters for distributed average consensus dynamics on random networks provide the application covered in this thesis work. The thesis discusses methods from random matrix theory appropriate for analyzing adjacency matrix spectral asymptotics for both directed and undirected random networks, introducing relevant theorems. Network distribution properties that allow computational simplification of these methods are developed, and the methods are applied to important classes of random network distributions. Subsequently, the thesis presents the main contributions, which consist of optimization problems for consensus acceleration filters based on the obtained asymptotic spectral density information. The presented methods cover several cases for the random network distribution, including both undirected and directed networks as well as both constant and switching random networks. These methods also cover two related optimization objectives, asymptotic convergence rate and graph total variation.

abstract: The availability of data for monitoring and controlling the electrical grid has increased exponentially over the years in both resolution and quantity leaving a large data footprint. This dissertation is motivated by the need for equivalent representations of grid data in lower-dimensional feature spaces so that machine learning algorithms can be employed for a variety of purposes. To achieve that, without sacrificing the interpretation of the results, the dissertation leverages the physics behind power systems, well-known laws that underlie this man-made infrastructure, and the nature of the underlying stochastic phenomena that define the system operating conditions as the backbone for modeling data from the grid. The first part of the dissertation introduces a new framework of graph signal processing (GSP) for the power grid, Grid-GSP, and applies it to voltage phasor measurements that characterize the overall system state of the power grid. Concepts from GSP are used in conjunction with known power system models in order to highlight the low-dimensional structure in data and present generative models for voltage phasors measurements. Applications such as identification of graphical communities, network inference, interpolation of missing data, detection of false data injection attacks and data compression are explored wherein Grid-GSP based generative models are used. The second part of the dissertation develops a model for a joint statistical description of solar photo-voltaic (PV) power and the outdoor temperature which can lead to better management of power generation resources so that electricity demand such as air conditioning and supply from solar power are always matched in the face of stochasticity. The low-rank structure inherent in solar PV power data is used for forecasting and to detect partial-shading type of faults in solar panels. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2020

Graph signal processing is a field concerning theprocessing of graphs with data associated to their vertices, oftenin the purpose of modeling networks. One area of this fieldthat has been under research in recent years is the developmentof frameworks for learning graph topologies from such data.This may be useful in situations where one wants to representa phenomenon with a graph, but where an obvious topologyis not available. The aim of this project was to evaluate theusefulness of one such proposed learning framework in thecontext of image segmentation. The method used for achievingthis consisted in constructing graph representations of imagesfrom said framework, and clustering their vertices with anestablished graph-based segmentation algorithm. The resultsdemonstrate that this approach may well be useful, although theimplementation used in the project carried out segmentationssignificantly slower than state of the art methods. A numberof possible improvements to be made regarding this aspect arehowever pointed out and may be subject for future work. / Grafsignalbehandling är ett ämnesområde vars syfte är att behandla grafer med data associerat till deras noder, ofta inom nätverksmodelleringen. Inom detta område pågår aktiv forskning med att utveckla tekniker för att konstruera graftopologier från sådana data. Dessa tekniker kan vara användbara när man vill representera ett fenomen med grafer, men då uppenbara grafstrukturer inte finns tillgängliga. Syftet med detta projekt var att utvärdera användbarheten hos en sådan teknik när den appliceras inom bildsegmentering. Metoden som användes bestod i att konstruera grafrepresentationer av bilder med hjälp av denna teknik, för att sedan behandla dessa med en etablerad, grafbaserad segmenteringsalgoritm. Resultaten påvisar att detta tillvägagångssätt under rätt förutsättningar kan producera tillfredsställande bildsegmenteringar. Dock är implementeringen som nyttjats i projektet betydligt långsammare än de metoder som vanligen används inom området. Ett antal förslag till prestandaförbättring utpekas, och kan vara föremål för framtida studier. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

Pour l’apprentissage automatisé de données régulières comme des images ou des signaux sonores, les réseaux convolutifs profonds s’imposent comme le modèle de deep learning le plus performant. En revanche, lorsque les jeux de données sont irréguliers (par example : réseaux de capteurs, de citations, IRMs), ces réseaux ne peuvent pas être utilisés. Dans cette thèse, nous développons une théorie algébrique permettant de définir des convolutions sur des domaines irréguliers, à l’aide d’actions de groupe (ou, plus généralement, de groupoïde) agissant sur les sommets d’un graphe, et possédant des propriétés liées aux arrêtes. A l’aide de ces convolutions, nous proposons des extensions des réseaux convolutifs à des structures de graphes. Nos recherches nous conduisent à proposer une formulation générique de la propagation entre deux couches de neurones que nous appelons la contraction neurale. De cette formule, nous dérivons plusieurs nouveaux modèles de réseaux de neurones, applicables sur des domaines irréguliers, et qui font preuve de résultats au même niveau que l’état de l’art voire meilleurs pour certains. / Convolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases.

The classical wavelet transform has been widely used in image and signal processing, where a signal is decomposed into a combination of basis signals. By analyzing the individual contribution of the basis signals, one can infer properties of the original signal. This dissertation presents an overview of the extension of the classical signal processing theory to graph domains. Specifically, we review the graph Fourier transform and graph wavelet transforms both of which based on the spectral graph theory, and explore their properties through illustrative examples. The main features of the spectral graph wavelet transforms are presented using synthetic and real-world data. Furthermore, we introduce in this dissertation a novel method for visual analysis of dynamic networks, which relies on the graph wavelet theory. Dynamic networks naturally appear in a multitude of applications from different domains. Analyzing and exploring dynamic networks in order to understand and detect patterns and phenomena is challenging, fostering the development of new methodologies, particularly in the field of visual analytics. Our method enables the automatic analysis of a signal defined on the nodes of a network, making viable the detection of network properties. Specifically, we use a fast approximation of the graph wavelet transform to derive a set of wavelet coefficients, which are then used to identify activity patterns on large networks, including their temporal recurrence. The wavelet coefficients naturally encode spatial and temporal variations of the signal, leading to an efficient and meaningful representation. This method allows for the exploration of the structural evolution of the network and their patterns over time. The effectiveness of our approach is demonstrated using different scenarios and comparisons involving real dynamic networks. / A transformada wavelet clássica tem sido amplamente usada no processamento de imagens e sinais, onde um sinal é decomposto em uma combinação de sinais de base. Analisando a contribuição individual dos sinais de base, pode-se inferir propriedades do sinal original. Esta tese apresenta uma visão geral da extensão da teoria clássica de processamento de sinais para grafos. Especificamente, revisamos a transformada de Fourier em grafo e as transformadas wavelet em grafo ambas fundamentadas na teoria espectral de grafos, e exploramos suas propriedades através de exemplos ilustrativos. As principais características das transformadas wavelet espectrais em grafo são apresentadas usando dados sintéticos e reais. Além disso, introduzimos nesta tese um método inovador para análise visual de redes dinâmicas, que utiliza a teoria de wavelets em grafo. Redes dinâmicas aparecem naturalmente em uma infinidade de aplicações de diferentes domínios. Analisar e explorar redes dinâmicas a fim de entender e detectar padrões e fenômenos é desafiador, fomentando o desenvolvimento de novas metodologias, particularmente no campo de análise visual. Nosso método permite a análise automática de um sinal definido nos vértices de uma rede, tornando possível a detecção de propriedades da rede. Especificamente, usamos uma aproximação da transformada wavelet em grafo para obter um conjunto de coeficientes wavelet, que são então usados para identificar padrões de atividade em redes de grande porte, incluindo a sua recorrência temporal. Os coeficientes wavelet naturalmente codificam variações espaciais e temporais do sinal, criando uma representação eficiente e com significado expressivo. Esse método permite explorar a evolução estrutural da rede e seus padrões ao longo do tempo. A eficácia da nossa abordagem é demonstrada usando diferentes cenários e comparações envolvendo redes dinâmicas reais.

Ce manuscrit introduit dans une première partie le domaine du traitement du signal sur graphe en commençant par poser les bases d'algèbre linéaire et de théorie spectrale des graphes. Nous définissons ensuite le traitement du signal sur graphe et donnons des intuitions sur ses forces et faiblesses actuelles comparativement au traitement du signal classique. En seconde partie, nous introduisons nos contributions au domaine. Le chapitre 4 cible plus particulièrement l'étude de la structure d'un graphe par l'analyse des signaux temporels via une transformation graphe vers série temporelle. Ce faisant, nous exploitons une approche unifiée d'apprentissage semi-supervisé sur graphe dédiée à la classification pour obtenir une série temporelle lisse. Enfin, nous montrons que cette approche s'apparente à du lissage de signaux sur graphe. Le chapitre 5 de cette partie introduit un nouvel opérateur de translation sur graphe définit par analogie avec l'opérateur classique de translation en temps et vérifiant la propriété clé d'isométrie. Cet opérateur est comparé aux deux opérateurs de la littérature et son action est décrite empiriquement sur quelques graphes clés. Le chapitre 6 décrit l'utilisation de l'opérateur ci-dessus pour définir la notion de signal stationnaire sur graphe. Après avoir étudié la caractérisation spectrale de tels signaux, nous donnons plusieurs outils essentiels pour étudier et tester cette propriété sur des signaux réels. Le dernier chapitre s'attache à décrire la boite à outils \matlab développée et utilisée tout au long de cette thèse. / This dissertation introduces in its first part the field of signal processing on graphs. We start by reminding the required elements from linear algebra and spectral graph theory. Then, we define signal processing on graphs and give intuitions on its strengths and weaknesses compared to classical signal processing. In the second part, we introduce our contributions to the field. Chapter 4 aims at the study of structural properties of graphs using classical signal processing through a transformation from graphs to time series. Doing so, we take advantage of a unified method of semi-supervised learning on graphs dedicated to classification to obtain a smooth time series. Finally, we show that we can recognize in our method a smoothing operator on graph signals. Chapter 5 introduces a new translation operator on graphs defined by analogy to the classical time shift operator and verifying the key property of isometry. Our operator is compared to the two operators of the literature and its action is empirically described on several graphs. Chapter 6 describes the use of the operator above to define stationary graph signals. After giving a spectral characterization of these graph signals, we give a method to study and test stationarity on real graph signals. The closing chapter shows the strength of the matlab toolbox developed and used during the course of this PhD.