‘Deep Graphs’: A New Framework for Network Analysis

New Method Appears Promising for Machine Learning, Feature Generation

An exciting new network analysis framework was published today. The paper, Deep Graphs – A General Framework to Represent and Analyze Heterogeneous Complex Systems Across Scales, presents the background information and derivation of methods applied to this new approach for analyzing networks [1]. The authors of the paper, Dominik Traxl, Niklas Boers and Jürgen Kurths, also released the open source DeepGraph network analysis package, written in Python, for undertaking and conducting the analysis. Detailed online documentation accompanies the entire package.

The basic idea behind Deep Graphs is to segregate graph nodes and edges into types, which form supernodes and superedges, respectively. These grouped types then allow the graph to be partitioned into lattices, which can be intersected (combinations of nodes and edges) into representing deeper graph structures embedded in the initial graph. The method can be applied to a graph representation of anything, since the approach is grounded in the graph primitives of nodes and edges using a multi-layer network (MLN) representation.

These deeper graph structures can themselves be used as new features for machine learning or other applications. A deep graph, which the authors formally define as a geometric partition lattice of the source graph, conserves the original information in the graph and allows it to be redistributed to the supernodes and superedges. Intersections of these may surface potentially interesting partitions of the graph that deserve their own analysis.

The examples the authors present show the suitability of the method for time-series data, using precipitation patterns in South America. However, as noted, the method applies to virtually any data that can be representated as a graph.

Though weighted graphs and other techniques have been used, in part, for portions of this kind of analysis in the past, this appears to be the first generalized method applicable to the broadest ways to aggregate and represent graph information. The properties associated with a given node may similarly be representated and aggregated. The aggregation of attributes may provide an additional means for mapping and relating external datasets to one another.

There are many aspects of this approach that intrigue us here at Structured Dynamics. First, we are always interested in network and graph analytical techniques, since all of our source schema are represented as knowledge graphs. Second, our specific approach to knowledge-based artificial intelligence places a strong emphasis on types and typologies for organizing entities (nodes and event relations) and we also separately segregate attribute property information [2]. And, last, finding embedded superstructures within the source graphs should also work to enhance the feature sets available for supervised machine learning.

We will later post our experiences in working with this promising framework.