Learning heat diffusion graphs

Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined sensing arrangements, like in road transportation networks for example. In general though, the data structure is not readily available and becomes pretty difficult to define. In particular, the global smoothness assumptions, that most of the existing works adopt, are often too general and unable to properly capture localized properties of data. In this paper, we go beyond this classical data model and rather propose to represent information as a sparse combination of localized functions that live on a data structure represented by a graph. Based on this model, we focus on the problem of inferring the connectivity that best explains the data samples at different vertices of a graph that is a priori unknown. We concentrate on the case where the observed data is actually the sum of heat diffusion processes, which is a quite common model for data on networks or other irregular structures. We cast a new graph learning problem and solve it with an efficient nonconvex optimization algorithm. Experiments on both synthetic and real world data finally illustrate the benefits of the proposed graph learning framework and confirm that the data structure can be efficiently learned from data observations only. We believe that our algorithm will help solving key questions in diverse application domains such as social and biological network analysis where it is crucial to unveil proper geometry for data understanding and inference.

Graph Signal Processing

Ntorina Thanou

Over the past few decades we have been experiencing an explosion of information generated by large networks of sensors and other data sources. Much of this data is intrinsically structured, such as traffic evolution in a transportation network, temperature values in different geographical locations, information diffusion in social networks, functional activities in the brain, or 3D meshes in computer graphics. The representation, analysis, and compression of such data is a challenging task and requires the development of new tools that can identify and properly exploit the data structure. In this thesis, we formulate the processing and analysis of structured data using the emerging framework of graph signal processing. Graphs are generic data representation forms, suitable for modeling the geometric structure of signals that live on topologically complicated domains. The vertices of the graph represent the discrete data domain, and the edge weights capture the pairwise relationships between the vertices. A graph signal is then defined as a function that assigns a real value to each vertex. Graph signal processing is a useful framework for handling efficiently such data as it takes into consideration both the signal and the graph structure. In this work, we develop new methods and study several important problems related to the representation and structure-aware processing of graph signals in both centralized and distributed settings. We focus in particular in the theory of sparse graph signal representation and its applications and we bring some insights towards better understanding the interplay between graphs and signals on graphs. First, we study a novel yet natural application of the graph signal processing framework for the representation of 3D point cloud sequences. We exploit graph-based transform signal representations for addressing the challenging problem of compression of data that is characterized by dynamic 3D positions and color attributes. Next, we depart from graph-based transform signal representations to design new overcomplete representations, or dictionaries, which are adapted to specific classes of graph signals. In particular, we address the problem of sparse representation of graph signals residing on weighted graphs by learning graph structured dictionaries that incorporate the intrinsic geometric structure of the irregular data domain and are adapted to the characteristics of the signals. Then, we move to the efficient processing of graph signals in distributed scenarios, such as sensor or camera networks, which brings important constraints in terms of communication and computation in realistic settings. In particular, we study the effect of quantization in the distributed processing of graph signals that are represented by graph spectral dictionaries and we show that the impact of the quantization depends on the graph geometry and on the structure of the spectral dictionaries. Finally, we focus on a widely used graph process, the problem of distributed average consensus in a sensor network where sensors exchange quantized information with their neighbors. We propose a novel quantization scheme that depends on the graph topology and exploits the increasing correlation between the values exchanged by the sensors throughout the iterations of the consensus algorithm.

EPFL2016

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs.However, research on relational representation learning has so far mostly focused on the problems arising in simple, homogeneous graphs. Integrating the structural priors provided by multi-relational data may further empower the generalization capacity of representation learning models, yet it still remains an open challenge.Although there is a strong line of works on relational machine learning on knowledge graphs, it is quite concentrated on the task ofcompleting missing edges, which is known as link prediction. In this thesis, we shift the focus away from the well-addressed node and graph classification problems on simple graphs or the link prediction problem on knowledge graphs, and prompt new research questions targeting the representation learning problems that are overlooked in multi-relational data.First, we focus on the problem of node regression on multi-relational graphs, noting that inference of continuous node features across a graph is rather under-studied in the current relational learning research.We propose a novel propagation method which aims to complete missing features at the nodes of a multi-relational and directed graph.Our multi-relational propagation algorithm is composed of iterative neighborhood aggregations which originate from a relational local generative model. Our findings show the benefit of exploiting the inductive bias led by the multi-relational structure of the data.Next, we consider the node attribute completion problem in knowledge graphs, which is relatively unexplored by the knowledge graph reasoning literature.We propose a novel multi-relational attribute propagation method where we harness not only the relational structure of the knowledge graph, but also the dependencies between various types of numerical node attributes relying on a heterogeneous feature space.Our algorithm is framed within a message-passing scheme where the propagation parameters are estimated in advance. We also propose an alternative semi-supervised learning framework where the parameters and the missing node attributes are inferred in an end-to-end fashion.Experimental results on well-known knowledge graph datasets relay the effectiveness of our message-passing approach, which specifies the computational graph by the heterogeneity of the data.Finally, we study graph learning in multi-relational data domain.Unlike the existing structure inference methods, we aim at exploiting and combining each source of relational information provided by the data domain to learn the underlying graph of a set of observations.For this purpose, we employ a multi-layer graph representation which encodes multiple types of relationships between data entities. Then, we propose a mask learning method to infer a specific combination of the layers which reveals the structure of observations.Experiments conducted both on simulated and real-world data suggest that incorporating multi-relational domain knowledge enhances structure inference by boosting its adaptability to a variety of input data conditions.

EPFL2021

Semantic coding by supervised dimensionality reduction

Pascal Frossard, Effrosyni Kokiopoulou

This paper addresses the problem of representing multimedia information under a compressed form that permits efficient classification. The semantic coding problem starts from a subspace method where dimensionality reduction is formulated as a matrix factorization problem. Data samples are jointly represented in a common subspace extracted from a redundant dictionary of basis functions. We first build on greedy pursuit algorithms for simultaneous sparse approximations to solve the dimensionality reduction problem. The method is extended into a supervised algorithm, which further encourages the class separability in the extraction of the most relevant features. The resulting supervised dimensionality reduction scheme provides an interesting trade-off between approximation (or compression) and discriminant feature extraction (or classification). The algorithm provides a compressed signal representation that can directly be used for multimedia data mining. The application of the proposed algorithm to image recognition problems further demonstrates classification performances that are competitive with state-of-the-art solutions in handwritten digit or face recognition. Semantic coding certainly represents an interesting solution to the challenging problem of processing huge volumes of multidimensional data in modern multimedia systems, where compressed data have to be processed and analyzed with limited computational complexity.