ATD: Collaborative Research: Spectral Interpretations of Essential Subgraphs for Threat Discoveries

在过去的十年里，图论发生了显著的转变——一场深刻的变革。图论不再局限于几个顶点和边缘（如著名的“柯尼斯堡七座桥”之谜）。今天，图论通常是关于理解我们这个连接越来越紧密的世界，这个世界可能包含数百万甚至数十亿个节点。这种变化在很大程度上是由于当今社会中存在的海量信息。例如，成功的Web搜索算法基于WWW图，它将所有网页作为顶点，将超链接作为边。在其他情况下，例如社交网络，用户的数量会导致特定社交媒体的图表的巨大尺寸。为了应对ATD公告中提出的挑战，这项工作旨在开发一个框架，使用随机和谱图理论的先进工具，对大型图或网络的结构和动态进行定量分析。在这里，重点是寻找可能隐藏在其中的模式，这些模式可能潜在地指示各种新出现的威胁（互联网，关键基础设施网络，金融网络，社交网络等）。本研究计划使用随机图论，微分几何和信息论的工具对可观察的网络结构进行分析计算，并捕获现实世界网络中最相关和最精细的数量。该方法基于Szemeredi规则引理，该引理提供了给定图的规则划分。如果可以有效地找到这些，那么将实现快速（通常是并行和分布的）方法来计算感兴趣的无数图属性，包括图合并和子图检测。不幸的是，正则性引理只是一个存在性证明；然而，正是在这里，利用谱图理论的思想，将开发出计算效率高且可扩展的方法来近似这些分区。此外，为了进一步提高效率，将开发一种新的模型（基于随机块模型）来表示图上的信息。这种方法背后的动机是双重的。首先，最有意义的图操作类型（图合并等）倾向于保留这样的分区。其次，这些块（或社区）可以进一步降低在给定图中查找特定子图（通常表示新出现的威胁）的复杂性。

In the past decade, graph theory has undertaken a remarkable shift --- a profound transformation. Graph theory is no longer limited to a few vertices and edges (as in the famous riddle of "The Seven Bridges of Konigsberg"). Today, graph theory is often about understanding our ever-more connected world, which may contain millions and billions of nodes. Such a change is in large part due to the humongous amount of information present in today's society. For example, successful Web search algorithms are based on WWW graphs, which contain all web pages as vertices and hyperlinks as edges. In other cases, such as social networks, the sheer number of users contribute to the huge size of the graphs representing a particular social medium. In response to challenges set forth in the ATD announcement, this work seeks to develop a framework using advanced tools from random and spectral graph theory to carry out quantitative analyses of the structure and dynamics of large graphs or networks. Here, the focus is on finding patterns that may be hidden in them that could potentially be indicative of emerging threats of various kinds (internets, critical infrastructure networks, financial networks, social networks, etc.)This research plans to use tools from random graph theory, differential geometry, and information theory to carry out analytic computations of observable network structures and capture the most relevant and refined quantities of real-world networks. The approach is based on the Szemeredi regularity lemma, which provides regular partitions of a given graph. If these can be found efficiently, then rapid (and often parallel- and distributed- among partitions) methods to compute a myriad of graph properties of interest, including graph merging and subgraph detection, will be achieved. Unfortunately, the regularity Lemma is only an existence proof; however, it is here, using ideas from spectral graph theory, where computationally efficient and scalable methods to approximate these partitions will be developed. Moreover, to further achieve efficiency, a new model will be developed (based on a stochastic block model) representing information on graphs. The motivation behind this approach is two-fold. First, the most meaningful types of graph operations (graph merging, etc.) tend to preserve such partitions. Second, these blocks (or communities) can further reduce the complexity of finding a particular subgraph (often indicative of emerging threats) in a given graph.