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.