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

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

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.