**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Graph signal processing tailored for subgraph focus and community structure

Abstract

Community structure in graph-modeled data appears in a range of disciplines that comprise network science. Its importance relies on the influence it bears on other properties of graphs such as resilience, or prediction of missing connections. Nevertheless, research to date seems to overlook its effect on the properties of signals defined in the domain of graphs' vertices. Indeed, the framework of graph signal processing mainly focuses on local connectivity patterns reflected by the graph Laplacian, and the Laplacian's effect on signals as the graph equivalent of a differential operator. This dissertation investigates the aforementioned interplay between graph signals and the underlying community structure. We make an effort to answer questions like -- do signal's values align and in what way with the communities?; does localization of signal's energy favors a community as the vertex support? Answers to these questions should provide a clearer perspective on the relation between graph signals and networks at the level of subgraphs.This dissertation consists of two main parts. First, we investigate a particular approach -- based on modularity matrix -- of informing the graph Fourier transform about the communities without explicitly detecting them. Thereof, we show that the derived community-aware operators on signals, such as filtering or subsampling, provide a complementary view on the framework to the conventional one based on the Laplacian. Indeed, reduced signal variability within a community seems to be a valuable metric of important signal behavior, aside from its smoothness. Secondly, we explore the intricacies of a broader definition of a community -- a subgraph of any special interest, possibly identified through metadata on vertices instead of the underlying edge connectivity. Within this context, the goal is to understand the benefits of processing signals in a subgraph-restricted way. We design a new, more computationally stable type of Slepians -- bandlimited signals with energy concentrated on a subgraph. Consequently, we show that such bandlimited vectors can be successfully employed to identify a signal's oscillatory pattern localized in a subgraph of interest, by means of a modified filtering procedure. Findings from both lines of research confirm the need and benefits of a better understanding of the interaction between communities and graph signals.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (50)

Related concepts (38)

Related MOOCs (23)

Digital Signal Processing [retired]

The course provides a comprehensive overview of digital signal processing theory, covering discrete time, Fourier analysis, filter design, sampling, interpolation and quantization; it also includes a

Digital Signal Processing

Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By rewo

Digital Signal Processing I

Basic signal processing concepts, Fourier analysis and filters. This module can
be used as a starting point or a basic refresher in elementary DSP

Signal

In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The IEEE Transactions on Signal Processing includes audio, video, speech, , sonar, and radar as examples of signals. A signal may also be defined as observable change in a quantity over space or time (a time series), even if it does not carry information.

Graph homomorphism

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. In formal terms, a directed graph is an ordered pair where V is a set whose elements are called vertices, nodes, or points; A is a set of ordered pairs of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using ...

Communities are shared areas on the Zenodo platform where projects, institutions, domains, and conferences can curate and manage their research outputs. An EPFL community https://zenodo.org/communities/epfl was created in 2013, mainly as a light-weight sol ...

2024