Some new results in graph representation learning

图表示学习的一些新成果

• 批准号: 2592879
• 金额: --
• 依托单位: University of Bristol
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2592879
• 关键词: Some; new; results; graph; representation

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.

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