Infrastructure to Support Analytics on Massive-Scale Dynamic Graphs

点击翻译按钮获取中文摘要

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. .