University of Oxford

Novel machine learning techniques based on deep learning, i.e., the data-driven manipulation of neural networks, have reported remarkable results in many areas such as image classification, game intelligence, or speech recognition. Driven by these successes, many scholars have started using them in areas which do not focus on traditional machine learning tasks. For instance, more and more researchers are employing neural networks to develop tools for the discretisation and solution of partial differential equations. Two reasons can be identified to be the driving forces behind the increased interest in neural networks in the area of the numerical analysis of PDEs. On the one hand, powerful approximation theoretical results have been established which demonstrate that neural networks can represent functions from the most relevant function classes with a minimal number of parameters. On the other hand, highly efficient machine learning techniques for the training of these networks are now available and can be used as a black box. In this talk, we will give an overview of some approaches towards the numerical treatment of PDEs with neural networks and study the two aspects above. We will recall some classical and some novel approximation theoretical results and tie these results to PDE discretisation. Afterwards, providing a counterpoint, we analyse the structure of network spaces and deduce considerable problems for the black box solver. In particular, we will identify a number of structural properties of the set of neural networks that render optimisation over this set especially challenging and sometimes impossible. The talk is based on joint work with Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, Felix Voigtlaender, and Mones Raslan

Matrix completion is an area of great mathematical interest and has numerous applications, including recommender systems for e-commerce. The recommender problem can be viewed as follows: given a database where rows are users and and columns are products, with entries indicating user preferences, fill in the entries so as to be able to recommend new products based on the preferences of other users. Viewing the interactions between user and product as links in a bipartite graph, the problem is equivalent to approximating a partially observed graph using clusters. We propose a divide and conquer algorithm inspired by the work of [1], who use recursive rank-1 approximation. We make the case for using an LP rank-1 approximation, similar to that of [2] by a showing that it guarantees a 2-approximation to the optimal, even in the case of missing data. We explore our algorithm's performance for different test cases.

[1]  Shen, B.H., Ji, S. and Ye, J., 2009, June. Mining discrete patterns via binary matrix factorization. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 757-766). ACM.

[2] Koyutürk, M. and Grama, A., 2003, August. PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 147-156). ACM.
 

Many protein interaction databases provide confidence scores based on the experimental evidence underpinning each in- teraction. The databases recommend that protein interac- tion networks (PINs) are built by thresholding on these scores. We demonstrate that varying the score threshold can re- sult in PINs with significantly different topologies. We ar- gue that if a node metric is to be useful for extracting bio- logical signal, it should induce similar node rankings across PINs obtained at different thresholds. We propose three measures—rank continuity, identifiability, and instability— to test for threshold robustness. We apply these to a set of twenty-five metrics of which we identify four: number of edges in the step-1 ego network, the leave-one-out dif- ference in average redundancy, average number of edges in the step-1 ego network, and natural connectivity, as robust across medium-high confidence thresholds. Our measures show good agreement across PINs from different species and data sources. However, analysis of synthetically gen- erated scored networks shows that robustness results are context-specific, and depend both on network topology and on how scores are placed across network edges. 

In this work, study the mean first saturation time (MFST), a generalization to the mean first passage time, on networks and show an application to the 2015 Burundi refugee crisis. The MFST between a sink node j, with capacity s, and source node i, with n random walkers, is the average number of time steps that it takes for at least s of the random walkers to reach a sink node j. The same concept, under the name of extreme events, has been studied in previous work for degree biased-random walks [2]. We expand the literature by exploring the behaviour of the MFST for node-biased random walks [1] in Erdős–Rényi random graph and geographical networks. Furthermore, we apply MFST framework to study the distribution of refugees in camps for the 2015 Burundi refugee crisis. For this last application, we use the geographical network of the Burundi conflict zone in 2015 [3]. In this network, nodes are cities or refugee camps, and edges denote the distance between them. We model refugees as random walkers who are biased towards the refugee camps which can hold s_j people. To determine the source nodes (i) and the initial number of random walkers (n), we use data on where the conflicts happened and the number of refugees that arrive at any camp under a two-month period after the start of the conflict [3]. With such information, we divide the early stage of the Burundi 2015 conflict into two waves of refugees. Using the first wave of refugees we calibrate the biased parameter β of the random walk to best match the distribution of refugees on the camps. Then, we test the prediction of the distribution of refugees in camps for the second wave using the same biased parameters. Our results show that the biased random walk can capture, to some extent, the distribution of refugees in different camps. Finally, we test the probability of saturation for various camps. Our model suggests the saturation of one or two camps (Nakivale and Nyarugusu) when in reality only Nyarugusu camp saturated.

[1] Sood, Vishal, and Peter Grassberger. ”Localization transition of biased random walks on random
networks.” Physical review letters 99.9 (2007): 098701.
[2] Kishore, Vimal, M. S. Santhanam, and R. E. Amritkar. ”Extreme event-size fluctuations in biased
random walks on networks.” arXiv preprint arXiv:1112.2112 (2011).
[3] Suleimenova, Diana, David Bell, and Derek Groen. ”A generalized simulation development approach
for predicting refugee destinations.” Scientific reports 7.1 (2017): 13377.

The physics literature has for a long time posited a connection between the geometry of continuous random fields and discrete percolation models. Specifically the excursion sets of continuous fields are considered to be analogous to the open connected clusters of discrete models. Recent work has begun to formalise this relationship; many of the classic results of percolation (phase transition, RSW estimates etc) have been proven in the setting of smooth Gaussian fields. In the first part of this talk I will summarise these results. In the second I will focus on the number of excursion set components of Gaussian fields in large domains and discuss new results on the mean and variance of this quantity.

TBC

We study several important fine properties for the family of fractional Brownian motions with Hurst parameter H under the (p,r)-capacity on classical Wiener space introduced by Malliavin. We regard fractional Brownian motions as Wiener functionals via the integral representation discovered by Decreusefond and \"{U}st\"{u}nel, and show non differentiability, modulus of continuity, law of iterated Logarithm(LIL) and self-avoiding properties of fractional Brownian motion sample paths using Malliavin calculus as well as the tools developed in the previous work by Fukushima, Takeda and etc. for Brownian motion case.

The analysis and characterization of human mobility using population-level mobility models is important for numerous applications, ranging from the estimation of commuter flows to modeling trade flows. However, almost all of these applications have focused on large spatial scales, typically from intra-city level to inter-country level. In this paper, we investigate population-level human mobility models on a much smaller spatial scale by using them to estimate customer mobility flow between supermarket zones. We use anonymized mobility data of customers in supermarkets to calibrate our models and apply variants of the gravity and intervening-opportunities models to fit this mobility flow and estimate the flow on unseen data. We find that a doubly-constrained gravity model can successfully estimate 65-70% of the flow inside supermarkets. We then investigate how to reduce congestion in supermarkets by combining mobility models with queueing networks. We use a simulated-annealing algorithm to find store layouts with lower congestion than the original layout. Our research gives insight both into how customers move in supermarkets and into how retailers can arrange stores to reduce congestion. It also provides a case study of human mobility on small spatial scales.

George Soules [1] introduced a set of vectors $r_1,...,r_N$ with the remarkable property that for any set of ordered numbers $\lambda_1\geq\dots\geq\lambda_N$, the matrix $\sum_n \lambda_nr_nr_n^T$ has nonnegative off-diagonal entries. Later, it was found [2] that there exists a whole class of such vectors - Soules vectors - which are intimately connected to binary rooted trees. In this talk I will describe the construction of Soules vectors starting from a binary rooted tree, and introduce some basic properties. I will also cover a number of applications: the inverse eigenvalue problem, equitable partitions in Laplacian matrices and the eigendecomposition of the Clauset-Moore-Newman hierarchical random graph model.

[1] Soules (1983), Constructing Symmetric Nonnegative Matrices
[2] Elsner, Nabben and Neumann (1998), Orthogonal bases that lead to symmetric nonnegative matrices

Mechanical percolation is a phenomenon in materials processing wherein ‘filler’ rod-like particles are incorporated into polymeric materials to enhance the composite’s mechanical properties. Experiments have well-characterized a nonlinear phase transition from floppy to rigid behavior at a threshold filler concentration, but the underlying mechanism is not well understood. We develop and utilize an iterative graph compression algorithm to demonstrate that this experimental phenomenon coincides with the formation of a spatially extending set of mutually rigid rods (‘rigidity percolation’). First, we verify the efficacy of this method in two-dimensional fiber systems (intersecting line segments), then moving to the more interesting and mechanically representative problem of three-dimensional fiber systems (cylinders). We show that, when the fibers are uniformly distributed both spatially and orientationally, the onset of rigidity percolation appears to co-occur with a mean field prediction that is applicable across a wide range of aspect ratios.