GT-CHES: Graph transformation for classification in human evolutionary systems

1. Introduction

Human systems, consisting of agents and their interactions, tend to evolve chaotically due to natural selection, the blend of cooperation and conflict that such natural selection induces over time, and the maximal adaptability due to self-organization [52, 53]. The field of game theory has expanded considerable efforts in attempting to quantify solutions for human interactions. Solution concepts have been formulated for special types of interactions, such as pure cooperation [65] and pure conflict (also known as zero-sum games) [76]. However, for the general case, namely a mix of conflict and cooperation, there is no universal notion of optimal decision-making.

Unsurprisingly, most human interactions are mixed-motive, as well as non-reductionist, so that it is not possible to partition them into their structured and randomized subsets, solve each subset separately, and combine the results. Hence, understanding the dynamics of human (highly-connected) systems requires the synthesis of elements of network theory (network structure), game or interaction theory (strategic behavior), and non-linear system dynamics or chaos (feedback effects) [17]. We seek to improve the accuracy of classification in human systems by synthesizing solution concepts from these various theories.

In general, the system’s state cannot be adequately represented by a vector of measurements, nor indeed even estimates, of the properties of its constituent parts, as is typically done in most time-series analysis, whether it be the inputs to estimating auto-regressive embedding dimensions [73, 55, 71, 62] or the inputs to echo state architectures [30]. Hence, learning labels for the constituent parts of a system, as in node or link classification, is fundamentally different from learning labels for the system as a whole, as in graph classification.

As such, our proposed approach is to transform a graph time-series classification task into a standard graph classification task by encoding the time-series nature of a number of relevant graph structural properties through fast Fourier transforms. We then use a random forest algorithm to predict the label of each graph through time.

The rest of the paper is organized as follows. Section 2 gives a review of some of the most relevant related work. Section 3 describes our novel approach to graph classification in chaotic human systems. A number of experiments that demonstrate the validity and efficiency of the approach, as well as comparisons with competing methods inspired by state-of-the-art deep learning architectures, are described in Section 4, together with novel benchmark data sets. Finally, Section 5 concludes the paper.

2. Related work

Our focus is on classification tasks for complex, dynamic, chaotic, human systems. Lines of inquiry in classification learning have generally been restricted to one or two of these system characteristics. We review the most relevant ones here.

Many machine learning and statistical tasks usually are performed in domains with complex, yet highly structured data; thus, a stable data distribution can be assumed. Such is not the case for dynamic systems, where data shift, rather than stability, is the norm. The shift can be a product of an intractably complex system or due to the forecasts themselves in the case of interactive systems. Work has been done in the area of complex adaptive systems, where an explanatory model of the system rather than a black-box prediction are preferred. [18, 1], as well as in reinforcement learning and no-regret learning, especially in the context of autonomous robots where dynamic learning and predictions are needed [20].

Deep learning (DL) has recently allowed major advances in highly complex, yet rather structured and non-chaotic, human domains, such as natural language processing and image classification tasks. The key to moving from the early multi-layer perceptron to the modern state-of-the-art deep learning architectures is the back-propagation of error method [61, 42, 9], which allows for a priori knowledge to be built into the network architecture [41], especially in the form of convolutional layers [36] that essentially act as feature detectors [27, 40]. Further improvements have been made possible, especially in the context of natural language processing, through attention [75] and recurrence [28] mechanisms. Most recently, deep learning has been extended to graphs in the emergent field of graph neural networks (GNNs) [64]. Since all permutations of the orderings of nodes and edges produce isomorphic graphs, tabular representations of graphs for consumption by standard machine learning techniques have proven largely unsatisfactory. GNNs relax the notion of isomorphism in favor of smoother metrics associated with graph structure that can become data points for a standard vector representation [35]. The idea is to use convolution and pooling to extract these permutation-invariant properties [8, 79, 81, 43, 48, 80, 78], where convolution creates embeddings for each node through embeddings of their neighbors, and pooling essentially extracts information from subgraphs. Significant challenges faced by GNNs in their use for human systems include pooling assumptions aligned with unsigned graphs [16], loss of spectral properties for directed and signed graphs [8, 34], weights and signs combination for propagation pooling operators [15], staleness [59], and difficulties with dynamic graphs [8].

DL work is being extended to chaotic physical systems and some human systems. This field is rapidly growing as graphs are now taken as inputs to novel formulations of DL components (and sometimes the components being formulated as nodes of a graph to be learned [21]). We review a few here that represent the general direction taken, which involves composing recurrence and GNN architectures. Work on pollution often combines graph- and recurrence-based neural networks in order to capture both the spatial and temporal nature of the spread of PM_2.5 (Particular matter with diameter less than 2.5 μ m). The graph convolutional neural network long short-term memory (GCN-LSTM) introduced in [57] employs a GCN to extract spectral features from the input matrix. The spectral features are concatenated with the matrix to form the inputs to the LSTM. The Fourier coefficients that determine the spectral features are trained by backpropagation. Another approach to the same problem is the graph-based long short-term memory (GBLSTM) [21]. In this formulation, each forget gate of the LSTM represents an air quality monitoring station rather than an entire graph. The gates are connected by an adjacency weight matrix whose weights are learned through training. Hence, this novel approach treats DL components as a graph whose weights are learned. These methods have proven to be state-of-the-art. We note, however, that the recurrence mechanism is effective in capturing the spatial quality of the problem since the deterministic nature of physical systems is more structured than that of human systems. For human systems, a combined graph and DL approach is being taken for link and node prediction. The graph convolutional long short-term memory (GC-LSTM) proposed in [12] inputs a series of graphs into the LSTM forget gates that act as an encoder. The output of the forget gates goes into a fully connected layer that acts as a decoder, and outputs an estimation of the graph at the next time step. We see the use of attention mechanisms for link- and node-classification in temporal graphs [77, 82], however, these often lack a specific inductive bias – such as structural balance or node strategies. This reliance on universal approximators to sift out temporal behaviors in highly complex systems, rather than assuming a set of behaviors upfront, leads to overfitting the training data rather than generalization [41]. Other methods do search for behavioral motifs, such as triadic closure, for node and link prediction [50]. Such tasks do fall within the human evolutionary domain, but they concern less chaotic atomic-level predictions rather than system classification.

Reservoir computing (RC), on the other hand, has been successful at addressing chaotic, but less human-like tasks. Early efforts to predict a chaotic signal estimate the hidden state through a delayed embedding [73, 60]. This approach converts a temporal problem into a spatial one, but also introduces an artificial time horizon, an awkward representation of time, and many parameters [66]. Recurrent neural networks (RNNs) were introduced in conjunction with back-propagation [61], with an elegant theoretical justification as an Euler approximation of time-dependent ordinary differential equations [32]. However, it has been shown that RNNs cannot perform over an arbitrary time period due to the vanishing gradient problem, are not robust to noise, and lack efficiency [3]. The echo state networks (ESNs) and liquid state machines (LSMs) were introduced as a way to employ recurrence like RNNs and to convert the temporal problem to a spatial one, as Takens had done [73], but in a way similar to kernel methods and support vector machines [7]. The idea is that reservoirs of randomly connected networks can act as “a complex nonlinear dynamic filter that transforms the input signals using a high-dimensional temporal map” [66], giving rise to the notion of reservoir computing. The property that has enabled RC to be successful with short-term predictions of chaotic systems is the echo property [29], which informally states “that the current state of the network is uniquely determined by the network input up to now, and, in the limit, not by the initial state. The network is thus state forgetting.” [66] A significant difference between RC and DL is that DL is built on error backpropagation, while RC is built on a feed-forward architecture. In DL, weights are adjusted iteratively according to how a prediction matches the true label; in RC, the inputs change the activation node values, while the weights are held steady. DL learns until it converges to a steady state; RC never enters a steady state. DL is effective for tasks in which the true hypothesis is relatively fixed; RC is best suited for tasks whose true hypothesis changes chaotically. RC provides a clever improvement on the computationally expensive BP process with respect to temporal prediction tasks. The RC approach allows the network to be flexible, yet employ “massive short-term memory” [30] to estimate a nuanced model of recent samples, while forgetting such nuances from samples of the distant past. One underlying issue with RC is that it is dependent on hyper-parameters that are not tuned during training. Current lines of research focus on tuning these hyper-parameters efficiently [32]. Another weakness of RC is its black-box nature, which limits its ability to predict a complex system without attempting to model its underlying structure.

Early violence detection (EVD), in the field of political science, focuses on dynamic human prediction tasks, but scopes such tasks to make traditional statistical methods of analysis suitable. The white-box nature of EVD allows the direct comparison of a proposed model with political theory. The main approach is to identify a few critical factors associated with geopolitical instability and make predictions with logistic regression and Bayesian methods [67], or other machine learning methods [69]. The approach favors smaller data sets of aggregated data over large data sets of repurposed data. Interestingly, this research has identified network-theoretic power structures as most relevant to conflict [23, 74], and has demonstrated outstanding effectiveness, such as 80% accuracy for two-year forecasts. EVD brings two critical insights to graph classification for human systems. First, good data on the power structures of the systems is the most relevant for global predictions [67]. Second, the dynamics of systems composed of larger organizations tend to change more slowly and more predictably than systems of individuals [68]. Hence, to analyze a highly-dynamic, decentralized system which does not exhibit explicit power structures, one may want to 1) identify the implicit power structures and 2) make such an identification efficient computationally in order to keep apace with changes. Our method seeks to do precisely that.

3. Graph classification in chaotic systems

We seek to bring together the solution concepts for dynamic systems, and cooperative and competitive interactions to improve prediction in the mixed-motive environment. Although the latter two concepts only offer partial solutions to the mixed-motive game, they provide the insight needed to attempt to go beyond simply modeling some low-dimensional input-output signal (as in the Reservoir Computing case) to modeling the internal workings of the system. Essentially, we convert the problem from a purely temporal one to a spatial one, thus combining the various solution concepts in a way that captures the chaotic dynamics ensuing from the mixed-motive interactions, as follows.

1.

Convert event data into dynamic graphs, which are higher-order representations of cooperation and conflict.

2.

Transform dynamic graph measures to the frequency domain, which is a higher-order representation of the evolution of cooperation and conflict.

3.

Embed the frequency domain distributions into a suitable space for classification.

In step 2, graph data (cooperation) is transformed to the frequency domain (conflict) so as to estimate properties of the chaotic attractor (dynamic systems). In step 3, the resulting feature vector includes static data about the graphs (cooperation) and dynamic data that captures the frequency domain distributions (conflict) of the graph data. We neither claim that these are the only solution concepts for cooperation and conflict, nor that this is the optimal way to combine them. We will show, however, that it improves prediction over other approaches in a number of real-world applications.

3.1 Graph representation: Modeling cooperation and conflict

Graphs are the most natural abstraction for the representation of interactions among agents. The structure of the graph is a product of the cooperation and conflict within the system it models, and that structure evolves as the balance of cooperation and conflict changes through time.

We focus on tasks whose corresponding graphs are derived from event data. An event is defined as a quadruple { t , src, dest, 𝑣𝑎𝑙 } where t is a time stamp, src is the initiator of the action, dest is the recipient of the action, and 𝑣𝑎𝑙 ∈ [ - 1 , 1 ] is the intensity of the action. The edges of our dynamic graphs are directed from src to dest with weight val. We select a few representative network properties, inspired from the literature, to characterize graphs at each time step, as shown in Table 1. Node-level properties, such as eigenvector centrality, are transformed into graph-level properties by computing the correlation between the list of values of that property and the corresponding list of values of some application-specific notion of node influence. Intuitively, if the correlation is high, then we may assume that the associated property generates high influence, and vice versa. We denote by S the set of structural properties.

We note that three of the features in S have several variants: eigen has four variants based on the value of its parameter β = { - 1 , - .5 , .5 , 1 } ; assort consists of 6 combinations of weight considerations ( + ( + , + ) , + ( + , - ) , + ( - , - ) , - ( + , + ) , - ( + , - ) , - ( - , - ) ), where the first terms relates to the edge sign that defines neighbors, the first term in the parentheses refers to the type of signed term for the source and the last term refers to the type of signed term for the target; and prop consists of three strategies, namely direct propagation, co-citation, and tit-for-tat, together with an error term.

In a mixed-motive environment, the elements of cooperation and conflict induce structure and randomness, respectively. For human systems, the additional element of evolutionary pressure induces chaos, resulting in a chaotic trajectory of the system [58].

We require some way to synthesize the notions of cooperation, conflict, and chaos by estimating the level of chaos in the trajectory’s attractor. Just as the graph is a higher-order representation of human interaction, the frequency domain becomes a higher-order representation of how the balance of cooperation and conflict fluctuates dynamically. The frequency domain captures global properties of a dynamic system, one of which is the structure of its trajectory. We therefore propose to capture the trajectory of the structural properties introduced above by converting them to the frequency domain through a Fast Fourier Transform (FFT).

We can then estimate the degree to which the resulting distribution is uniform in order to gauge randomness, or the degree to which it fits a distribution that would represent a structured trajectory. To illustrate the value of this approach, consider Fig. 1, which depicts three different time series and their corresponding FFTs. In addition to the FFTs, the graph shows uniform (flat, dark gray) and gamma (light gray) distribution fits. The first distribution (1a) exhibits high structure, monotonically decreasing at a constant rate. Its FFT (1d), has pronounced amplitudes in two narrow frequency ranges, and as expected does not fit either uniform nor gamma distributions very well. The second distribution (1b) is random, with no underlying structure. Its FFT (1e) exhibits similar randomness, and as such fits an uniform distribution. Finally, the third distribution (1c) represents the Dow Jones daily closing levels over a period of 100 days. It exhibits chaotic behavior (i.e., both some structure and some randomness), and its FFT (1f) shows a range of pronounced amplitudes at the higher frequencies, as well as good fit to a gamma distribution, as expected for such a chaotic trajectory.

OPEN IN VIEWER

We denote by 𝐹𝐹𝑇 ( S i , t - w : t ) the FFT of structural property S i over the time window [ t - w , t ] , where w is an application-dependent hyperparameter. After fitting each FFT for S i to a gamma distribution, we compute a goodness-of-fit measure D i . We denote by D the set of all of these measures. In addition, we track the interplay of the structural properties’ trajectories by computing a multidimensional Fourier Transform over them, denoted by 𝑀𝐹𝐹𝑇 ( t - w : t ) . As with the individual trajectories, the resulting function is fit to a gamma distribution. It is also fit to a log normal and an uniform distributions, and goodness-of-fit values are computed. They are denoted by M ⁢ D g , M ⁢ D l , and M ⁢ D u , respectively. We expect the fit of 𝑀𝐹𝐹𝑇 ( t - w : t ) to not vary from a gamma distribution for long.

We now transform our graph time-series into tabular form by transforming each graph G t with the following algorithm.

: GT-CHES Algorithm[1] Extract the values of the properties in S from G t each property S i in S Compute 𝐹𝐹𝑇 ( S i , t - w : t ) . Extract the values of goodness-of-fit D i of 𝐹𝐹𝑇 ( S i , t - w : t ) to the Γ distribution Compute 𝑀𝐹𝐹𝑇 ( t - w : t ) Extract the goodness-of-fit values M ⁢ D = M ⁢ D g , M ⁢ D l , M ⁢ D u of 𝑀𝐹𝐹𝑇 ( t - w : t ) to the gamma, the log normal, and the uniform distributions, respectively

As in all classification tasks, each graph G t is further labelled with a value from the corresponding application-specific set Y of possible classes. Given the above transformation of graph data into traditional tabular data, where vectors of values drawn from features in S , D and M ⁢ D are mapped to values in Y , the graph classification algorithm of GT-CHES can now be drawn from the rich pool of candidate classification learning algorithms. We choose to use a bagging ensemble of 10 random forest models, each containing 15 trees.

Note that the proposed transformation allows our applications to still benefit from being framed as graph classification problems, as opposed to just using a feature vector of other related data to classify, or make prediction, at each time step. The graph transformation step allows us to leverage network structure and interaction. Indeed, the feature vector does not consist of aggregated data (e.g., total attacks, number of attacks, etc.) but of graph centrality measures that represent levels of organization and randomness, which are hard to measure with aggregated (non-graph) data.

4. Experiments

We encountered challenges to assessing the value of GT-CHES and comparing its results against those of others. There are very few models that have been designed specifically for the kinds of problems we address. Two fundamental implications follow from this. First, there is a lack of benchmark data sets, where the domain consists of events in a mixed-motive, evolutionary environment, and the data is sufficiently heterogeneous (i.e., directed, weighted, signed, temporal edges). Second, there are a lack of frameworks for making comparisons if suitable data were obtained for graph classification.

We begin with data sets that may be used as proof-of-concept in the sense that they include mixed-motive event-based data as input, but we have to formulate the labels since no graph labels exist for such data sets. Since these are limited, we also design benchmark data sets, which can henceforth be used by others.

To evaluate GT-CHES, we run a number of experiments involving our Proof-of-Concept data sets and our benchmark data sets, against a number of baseline algorithms as well as graph neural networks and state-of-the-art solutions.

We have introduced GT-CHES, an approach for graph classification in the context of human evolutionary systems, based on principles from game theory and chaos theory. We capture explicit structural properties of the graphs at each time step and transform the corresponding time series into the frequency domain. The resulting sets of features are then used by a random forest algorithm to build a predictive model. Results on a number of simple data sets show that GT-CHES matches or exceeds baseline approaches such as a majority learner and a naive classifier. Furthermore, accuracy tends to be increasing as the level of chaos in the system increases. We also compared GT-CHES with deep graph neural networks and showed that GT-CHES outperforms these approaches. This is particularly interesting in the context of very recent findings about the relationships between Fourier analysis and deep learning [72].

Given the relative recency of work in evolutionary graph classification, we designed two real-world benchmark data sets based on well-known geo-political data. These benchmarks are available to the broader community. We showed that GT-CHES performs comparatively to the best published results in political science with approaches based on extensive crafting of predictive features and tuning of models. We expect that tuning of GT-CHES will lead to further improvements. It is also possible that GT-CHES should be viewed as orthogonal to the current macro-structural data approaches. Hence, when used in combination with the current approaches, for example in an ensemble, it may effectively boost performance.