Large Structures Seminar: Franz Király & Tiago Peixoto

There will be two 30-minute talks:
Franz Király (University College London) “Local Low-Rank Matrix Completion”
Tiago P. Peixoto (Universität Bremen) “Large-scale structure in networks: From modules to hierarchies, and their evolution”

Abstract of Franz Király’s talk:

In recent years, the low-rank matrix completion model has enjoyed quite some success for recommendation and prediction learning. Many standard algorithms in the field are designed for completing the whole matrix (or derivates) - which also means that achieving scalability on huge data sets is a challenging task.

A question which has only been more recently considered is prediction of single entries or only a few.

The novel approach based on algebra and combinatorics allows, for the first time, a systematic treatment of single-entry estimates including single-entry error bounds, and it yields, for the first time, a closed approach to the low-rank model that is intrinsically local.

In the talk, I will give a brief introduction to the matrix completion problem, and its algebraic combinatorial formulation; I will demonstrate how this allows to derive simple reconstruction algorithms, and review some recent empirical results.

This talk is the first in a series of self-contained talks related to the topic of local matrix completion which are optimally enjoyed together, including:

Matrices, matroids and marginals - a tutorial to the algebra, combinatorics, and statistics of local low-rank matrix completion (and similar problems) Speaker: Franz Király Apr 22, 15:15-17:00, ANTA seminar

Prediction and quantification of individual athletic performance (with local matrix completion) Speaker: Duncan Blythe May 11, 12:15-13:15, Large Structures Monday

References: Király FJ, Theran L, Tomioka R. The algebraic combinatorial approach for low-rank matrix completion. Preprint, 42 pages, arXiv 1211.4116. Accepted for publication in the Journal of Machine Learning Research, 2015. http://arxiv.org/abs/1211.4116

Abstract of Tiago P. Peixoto’s talk:

Networks form the backbones of a wide variety of complex systems, ranging from food webs, gene regulation and social networks to transportation networks and the internet. Due to the sheer size and complexity of many of theses systems, it remains an open challenge to formulate general descriptions of their large-scale structures, as well as to connect their structural properties with their function and dynamics, and finally to identify plausible reasons for their evolution. I will describe how generative models of network structure can be used as a tractable way to connect all these points. In particular, I will show how a general class of models that encapsulates the multilevel structure of network systems can be constructed, which allows for the principled and efficient high-resolution identification of modules and hierarchies from empirical systems. I will then show how such generative models can be used to investigate the structural and dynamical robustness of networks — i.e. the ability to sustain function despite damage, attacks or stochastic fluctuations — and propose a general mechanism for the emergence of large-scale structural patterns resulting from the optimization towards robustness.

Throughout the talk I will illustrate the application of the methods with many empirical networks such as the internet at the autonomous systems level, the global airport network, the network of actors and films, social networks, citations among websites, co-occurrence of disease-causing genes and others.