COLLOQUIUM: Payam Delgosha, "A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression"

Due to technical difficulties, captions are unavailable but are forthcoming soon.

Abstract:

Many modern data sources arising from social networks, biological data, etc. are best viewed as being represented by combinatorial structures such as graphs, rather than time series. The local weak limit theory for sparse graphs, also known as the objective method, provides a framework which enables one to make sense of a stationary stochastic process for sparse graphs. The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes for combinatorial structures, in particular graphs, would eventually have a similarly wide-ranging impact.

Employing the above framework, we introduce a notion of entropy for probability distributions on rooted graphs. This is a generalization of the notion of entropy introduced by Bordenave and Caputo to graphs which carry marks on their vertices and edges. Such marks can represent information on real-world data. For instance, in a social network graph where each node represents an individual and edges represent friendships, a vertex mark represents the type of an individual, while edge marks represent shared data between friends. The above notion of entropy can be considered as a natural counterpart for the Shannon entropy rate in the world of graphical data. We illustrate this by introducing a universal compression scheme for marked graphical data. We also discuss a low complexity universal compression algorithm for marked graphical data. Furthermore, we study distributed compression of graphical data. In particular, we introduce a version of the Slepian-Wolf theorem for sparse marked graphs.

Bio:

Payam Delgosha received his B.Sc. in Electrical Engineering and Pure Mathematics in 2012, and his M.Sc. in Electrical Engineering in 2014, both from Sharif University of Technology, Tehran, Iran. He received his Ph.D. in Electrical Engineering and Computer Sciences from the University of California at Berkeley in 2020. He joined the computer science department at the University of Illinois at Urbana Champaign in 2020. He received the 2020 IEEE Jack Keil Wolf ISIT best student paper award for the paper "A universal low complexity compression algorithm for sparse marked graphs".

Faculty Host: Mahesh Viswanathan