Some new results in graph representation learning

To be able to perform machine learning and statistical inference on networks, similarity matrices, or other relational information is an important task with societal, humanitarian and scientific implications. For example, uncovering malicious activity on the dark web, performing intrusion detection on a corporate enterprise network, or stopping DDOS/BGP hijacks at global internet scales, all require sophisticated network analysis of internet traffic data. The DARPA Memex programme, running since 2014, indexes the deep web for human-trafficking activity, generating graphs on tens of millions of ads connecting images,

phone numbers, locations, working names, and more, for which statistical inference questions include identifying advertisements likely to describe trafficked individuals or helping law enforcement locate victims.

For such problems, the practice of embedding, that is, the representation of each node as a point in R^D, has become a common first step to statistical inference. Embedding techniques typically look to reproduce probabilistic or semantic relationships between nodes as vector operations. For example, spectral embedding can be interpreted as seeking to position the nodes in such a way that a node sitting between nodes x and y acts as the corresponding probabilistic mixture of the two.

Embedding techniques allow us to find a representation of an observed graph and explain its structure in terms of a statistical model. Going beyond this task, in some situations one may be presented with a graph or collection of graphs, and have a need to generate

further graphs which are not identical to the given graphs but somehow share their salient statistical characteristics. This endeavour is referred to generative modelling of graphs, or graph simulation. Graph simulation is of interest, for example, in protein and molecule discovery, where one is given examples of proteins or molecules with desirable biological and chemical properties and whose structure is encoded as a graph, and one seeks novel structures which are "close" but not identical to the given examples.

Recent work has shown that sparse graphs containing many triangles cannot be reproduced using a finite-dimensional representation of the nodes, in which link probabilities are inner products. We show that such graphs can be reproduced using an infinite-dimensional inner product model, where the node representations lie on a low-dimensional manifold. Recovering a global representation of the manifold is impossible in a sparse regime. However, we can zoom in on local neighbourhoods, where a lower-dimensional representation is possible. As our constructions allow the points to be uniformly distributed on the manifold, we find evidence against the common perception that triangles imply community structure.

The COMPASS Centre for Doctoral Training will have the following impact.

Doctoral Students Impact.

I1. Recruit and train over 55 students and provide them with a broad and comprehensive education in contemporary Computational Statistics & Data Science, leading to the award of a PhD. The training environment will be built around a set of multilevel cohorts: a variety of group sizes, within and across year cohort activities, within and across disciplinary boundaries with internal and external partners, where statistics and computation are the common focus, but remaining sensitive to disciplinary needs. Our novel doctoral training environment will powerfully impact on students, opening their eyes to not only a range of modern technical benefits and opportunities, but on the power of team-working with people from a range of backgrounds to solve the most important problems of the day. They will learn to apply their skills to achieve impact by collaborative working with internal and external partners, such as via our Rapid Response Teams, Policy Workshops & Statistical Clinics.

I2. As well as advanced training in computational statistics and data science, our students will be impacted by exposure to, and training in, important cognate topics such as ethics, responsible innovation, equality, diversity and inclusion, policy, effective communication and dissemination, enterprise, impact and consultancy skills. It is vital for our students to understand that their training will enable them to have a powerful impact on the wider world, so, e.g., AI algorithms they develop should not be discriminatory, and statistical methodologies should be reproducible, and statistical results accurately and comprehensibly communicated to the general public and policymakers.

I3. The students will gain experience via collaborations with academic partners within the University in cognate disciplines, and a wide range of external industrial & government partners. The students will be impacted by the structured training programmes of the UK Academy of Postgraduate Training in Statistics, the Bristol Doctoral College, the Jean Golding Institute, the Alan Turing Institute and the Heilbronn Institute for Mathematical Sciences, which will be integrated into our programme.

I4. Having received an excellent training, the students will then impact powerfully on the world in their future fruitful careers, spreading excellence.

Impact on our Partners & ourselves.

I5. Direct impacts will be achieved by students engaging with, and working on projects with, our academic partners, with discipline-specific problems arising in engineering, education, medicine, economics, earth sciences, life sciences and geographical sciences, and our external partners Adarga, the Atomic Weapons Establishment, CheckRisk, EDF, GCHQ, GSK, the Office for National Statistics, Sciex, Shell UK, Trainline and the UK Space Agency. The students will demonstrate a wide range of innovation with these partners, will attract engagement from new partners, and often provide attractive future employment matches for students and partners alike.

Wider Societal Impact

I6. COMPASS will greatly benefit the UK by providing over 55 highly trained PhD graduates in an area that is known to be suffering from extreme, well-known, shortages in the people pipeline nationally. COMPASS CDT graduates will be equipped for jobs in sectors of high economic value and national priority, including data science, analytics, pharmaceuticals, security, energy, communications, government, and indeed all research labs that deal with data. Through their training, they will enable these organisations to make well-informed and statistically principled decisions that will allow them to maximise their international competitiveness and contribution to societal well-being. COMPASS will also impact positively on the wider student community, both now and sustainably into the future.