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

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.