Event Prediction in Complex Social Graphs using One-Dimensional Convolutional Neural Network

1 Introduction

A social network consists of finite set(s) of actors, and the relationship(s) defined between these actors [Scott, 2017]. Analyzing and learning intrinsic knowledge from communities, comprising social actors, using given sets of standard still remains a significant research problem in social network analysis (SNA). Furthermore, an event prediction problem can be expressed as a Satisfiability problem [Hans van Maaren and Walsh, 2009] such that an event is said to exist if the variables governing the event's formal definition reduces it to true. Hence, the Cook-Levin Theorem [Cook, 1971] has proven that Satisfiability problem is NP-Complete. The proposed methodologies herein are based on a neural network architecture assembled using deep layers of stacked processing units comprising ConvNet and MLP units. This architecture makes it feasible to develop and train neural network models to be capable of learning the nonlinear distributed representations enmeshed in the graph structures [Ian Goodfellow and Courville, 2017].

2 Problem Statement

Social network graphs are characterized by their complex size and dynamic nature; and this makes it relatively challenging and difficult to develop effective machine learning (ML) as well as deep learning (DL) models which can be trained to predict events over a given network graph with respect to its constituent vertices (or actors) and edges (or relationships).

3 ProposedMethodology

My proposition employs a Skip-gram neural-network model in the pre-convolution layer; and this Skip-gram model is responsible for unsupervised representation (or feature) learning where apparent features and viable facts (in the form of node embeddings) are automatically extracted from the complex graph data. In turn, these learnt node embeddings serve as input to the 1D-ConvNet classification layer. Thus, the 1D-ConvNet model is trained effectively upon the node embeddings with respect to its corresponding event labels using a supervised learning approach. Formally, a social network, SN, can be defined as in expression 1 where SN is a tuple defined such that it comprises a set of vertices: V ; a set of edges: E; a metadata function: fV which extends the definition of the vertices' set by mapping it to a given set of attributes: M; and a metadata function: fE which extends the definition of the edges' set by mapping it to a given set of attributes: N.

Skip-gram neural network is a technique majorly employed in the domain of Natural Language Processing (NLP). Thus, given a large collection of text (text corpus); the Skipgram model focuses on learning the low-dimensional features which can be used to effectively and efficiently represent each word in the text corpus [Jason Eisner and Poliak, 2017][Tomas Mikolov and Dean, 2013] in relation to a predefined words' vocabulary, W : ∀ wm ∈ W where M : m ∈ M

is the number of unique words in the vocabulary. Given a target word, wt, within the text corpus; we define the "context" of wt as the words surrounding it in a given size-L window within the text corpus.

Thereafter, a collection of (target word, context word) pairs which we denote as D is generated to be used for training.

The goal of the Skip-grammodel is to maximize the average logarithmic probability of the context words, wt+L, being predicted as contexts for the target word, wt, with respect to all training pairs, ∀ (wt, wt+l) ∈ D. Formally, it is defined as:

To compute P(wt+l|wt), we have to quantify the proximity of each target word, wt, with respect to its context word, wt+l. The Skip-gram model measures this proximity as the cosine distance between wt and its corresponding wt+l. Hence, every word comprising the text corpus with respect to W is encoded over a real number space, R, such that ∀wt,wt+l:

The cosine distance is calculated as the dot product between the vector representations of the target word and the context word. Mathematically, P(wt+l|wt) is computed as:

Furthermore, extending this NLP methodology to graph theory, given a social network, SN, as defined by expression 1 above; the edge list, E[i, j] ⊂ G, which is a sequence of tuples is defined via equation 7. (ui, vj) denotes a link or tie from a source vertex, ui, to a target vertex, vj.

Consequently, expression 8 defines the functions which map the graph domain, G, to the words' vocabulary, W.

where M signifies the number of unique nodes in the graph's set of vertices, V , such that: ∀um ∈ V . Therefore, the objective function of our Skip-gram layer with respect to a given graph, G, is as expressed by equation 9, viz:

4 Results and Conclusion

Training of the 1D-ConvNet model follows a supervised learning function, f : X → Y , where Y denotes the set of event labels. Vector embeddings generated by the Skip-gram layer are passed to the downstream ConvNet layer for event prediction via classification based on corresponding event labels. Currently, I am validating my propositions with regard to expanding the experimentation scope to include more real world social network datasets as well as benchmark methods.

Acknowledgements

This research is supported by International Business Machines (IBM) via the provision of a high performance IBM Power System S822LC Linux Server for our laboratory work. Also, I want to acknowledge my doctoral advisor, Professor Ziad Kobti, for his guidance thus far. Consecutively, credit goes to Stanford University [Leskovec and Krevl, 2014] for making their compiled datasets readily available to us.