Some new results in graph representation learning

能够对网络、相似矩阵或其他关系信息进行机器学习和统计推理是一项具有社会、人道主义和科学意义的重要任务。例如，发现暗网上的恶意活动，在企业企业网络上执行入侵检测，或者在全球互联网规模上阻止DDOS/BGP劫持，所有这些都需要对互联网流量数据进行复杂的网络分析。DARPA Memex项目自2014年开始运行，为人口贩运活动的深层网络建立索引，在数千万个广告上生成图表，连接图像、电话号码、地点、工作人员姓名等，统计推断问题包括识别可能描述人口贩运个人的广告或帮助执法部门定位受害者。对于这样的问题，嵌入的做法，也就是将每个节点表示为R^D中的一个点，已经成为统计推断的常见第一步。嵌入技术通常寻求将节点之间的概率或语义关系复制为向量运算。例如，谱嵌入可以被解释为寻求以这样一种方式定位节点，即位于节点x和y之间的节点充当这两个节点的相应概率混合。嵌入技术使我们能够找到观察到的图的表示，并根据统计模型解释其结构。除了这项任务之外，在某些情况下，可能会向用户呈现一个图或一组图，并且需要生成与给定图不相同但以某种方式共享其显著统计特征的其他图。这一努力指的是图形的生成性建模，或图形模拟。例如，图形模拟在蛋白质和分子发现中很有意义，其中给出具有期望的生物和化学性质的蛋白质或分子的例子，其结构被编码为图形，并且人们寻找与所给例子“接近”但不完全相同的新结构。最近的工作表明，包含许多三角形的稀疏图不能使用节点的有限维表示来复制，在有限维表示中，链接概率是内积。我们证明了这样的图可以使用无限维内积模型来复制，其中节点表示位于低维流形上。在稀疏的体制下，恢复流形的全球表示是不可能的。然而，我们可以放大局部社区，在那里低维表示是可能的。由于我们的构造允许点在流形上均匀分布，我们找到了反对通常认为三角形意味着社区结构的证据。

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.