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.