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.