How can a hypergraph help to predict the dynamic behavior of complex networked systems?

The study proposes an efficient data-driven model to predict the dynamic behavior of various networked physical systems using a Hypergraph Convolutional Recurrent Neural Network (HGC-RNN). The hypergraph can model the mutual interactions among subcomponents of the target system.

Article | Fall 2020

Numerous sensors are attached to a variety of systems to acquire a wide range of data. Will just installing a large number of sensors and receiving a large amount of data help to understand the characteristics of the target system? Only by analyzing the data using a suitable model that reflects the characteristics of the target system is it possible to understand the system’s characteristics. When the target system is huge and complex, it is essential to consider the relative relationship of components constituting the target system and the dynamic characteristics of the target system.

Graphs have been used as effective ways to represent structured data, capturing relationships among data entities. Conventional graphs map individual data points to nodes and connections or correlations between two points to edges. However, such pairwise connections are not always appropriate in actual applications. In practical cases, more complicated relationships often exist among multiple nodes than pairwise connections between two nodes. Figure 1a shows an example of complicated relationships of a sensor network that are difficult to represent with a conventional graph. A hypergraph is a generalized concept that can express complex networks. Unlike a conventional graph that defines an edge between two nodes (Figure 1b), a hypergraph can define an edge among multiple nodes, modeling more complicated higher-order interactions among multiple nodes (Figure 1c).

 

This study proposes a data-driven model that predicts the spatiotemporal characteristics of a target system by using sensor data obtained from various sub-components that make up a complex system. Specifically, we propose a hyper-graph convolutional recurrent neural network (HGC-RNN), a deep neural network integrating the hypergraph convolution into RNN, which can infer the system’s dynamic characteristics by reflecting the mutual interaction of sub-components. The structure of the algorithm is shown in Figure 2. The hypergraph convolution extracts the structural feature of the data. The recurrent structure of the model extracts temporal dependencies between sequential time steps. Using the hypergraph concept, the proposed model can overcome the limitations of conventional graph time-series models that cannot express complicated structures.

 

The proposed method has been employed to predict the gas pressures of 195 gas regulators operated in Daejeon city, South Korea. The 195 gas regulators are operated to control gas flow in the gas distribution network (Figure 3a). By taking into account the mutual interaction through the connected gas pipelines, the proposed model accurately predicts the future gas pressures of the 195 gas regulators simultaneously. The constructed prediction model can be used to detect an abnormal pattern in a gas network or to control the gas regulators to optimize the gas distribution efficiency. The proposed model has also been used to predict the taxi demand in New York city (Figure 3b) and predict the speed of autonomous material transporting vehicles in a factory (Figure 3c). These predictions are made more accurately compared to other baseline models while using 1000-times fewer parameters.

This research was conducted with Jaehyuk Yi, a masters’ student, and published at The 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2020) under the title, “Hypergraph Convolutional Recurrent Neural Network”. You can watch a short video introducing the paper at.