Infrastructure to Support Analytics on Massive-Scale Dynamic Graphs

在几个应用领域中出现的一个具有挑战性的问题是使用时态事件数据准确地识别正在协调大规模活动的特定信息流的主要来源(例如，假新闻、垃圾邮件或社交机器人攻击的来源)。这对今天的分析系统来说具有挑战性的是，事件通常是：(I)仅在参与实体(例如，网络设备、电子邮件收件箱、社交网络帐户)的级别上观察，以及(Ii)从众多独立来源聚集而不保证接收事件的及时性。 该问题可以通过将系统建模为动态图来解决，其中：(I)节点(即，顶点)是参与系统的实体；(Ii)链接(即，边)是这些实体之间的交互；以及(Iii)当观察到新事件时，节点和链接都可以动态地添加到演化图中。鉴于该系统的动态性，这一模型不仅在概念上符合得很好，而且还使其有可能“跨越时间”，同时保持对系统整体状态的准确看法--这是审计和法证调查的关键推动因素。当前的系统远远没有提供在现实世界中支持这种场景所需的规模、反应时间和查询语义。 为了支持这一场景和许多其他可以建模为时间演变图的场景，我们的项目旨在探索四个相互交织的研究方向。首先，设计能够有效支持大规模动态图处理的抽象、数据结构和并行算法。其次，揭示特定于域的图结构以及频繁的数据访问模式支持的优化，并通过专门的运行时透明地利用它们。第三，探索通过特定领域的语言简化图形分析开发的方法。最后，探讨利用两项最新技术进步的可行性：存储级存储器(例如，Intel的Optane DC)和软件定义的网络，以提高性能并减少图形分析的能源消耗。 虽然受益于支持动态图分析的高效框架的潜在领域集是巨大的，但我们计划将重点放在两个影响较大的领域：社交网络和网络安全。这些领域在问题规模、数据多样性、数据速度和解决时间方面提出了具有挑战性的要求，同时见证了一组日益多样化的复杂分析的快速发展，这证明我们有理由将重点放在应用程序开发的友好性上。 。

A challenging problem emerging in several application domains is to accurately identify the main source of a particular information flow (e.g., a source of fake news, spam, or social-bot attack) that is coordinating a large-scale campaign, using temporal event data. What makes this challenging for today's analytics systems is that events are typically: (i) only observed at the level of the participating entities (e.g., network devices, email inboxes, social network accounts), and (ii) aggregated from numerous independent sources with no guarantees for the timeliness of receiving the events. This problem can be solved by modelling the system as a dynamic graph where: (i) the nodes (i.e., vertices) are the entities participating in the system; (ii) the links (i.e., edges) are the interactions between those entities; and (iii) both nodes and links can be dynamically added to the evolving graph as new events are observed. Given the dynamicity of the system, this model is not only a good conceptual fit but it also makes it possible to “jump through time” while maintaining an accurate view of the overall state of the system - a key enabler for audits and forensic investigations. Current systems are far from offering the scale, the reaction time, and the querying semantics required to support this scenario in the real world. To offer support for this scenario and for the many others that can be modelled as time-evolving graphs, our project aims to explore four intertwined research directions. Firstly, designing the abstractions, data-structures, and parallel algorithms able to effectively support processing large-scale dynamic graphs. Secondly, uncovering the optimizations enabled by domain-specific graph-structures as well as frequent data access patterns, and harnessing them transparently through specialized runtimes. Thirdly, exploring avenues to simplify the development of graph analytics through domain-specific languages. Finally, exploring the feasibility of harnessing two recent technological advances: storage-class memories (e.g., Intel's Optane DC) and software-defined networks, to both increase performance and reduce the energy footprint for graph analytics. While the set of potential domains that benefit from an efficient framework that supports analytics on dynamic graphs is huge, we plan to focus on two high-impact areas: social-networks and cyber-security. These domains offer challenging requirements in terms of problem scale, data diversity, data velocity, and time-to-solution, and, at the same time, witness the rapid development of an increasingly diverse set of complex analytics which justifies our focus on application-development friendliness. .