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

Bonaventure C. MolokwuIJCAI 2019 · DOI

TL;DR

This paper proposes a novel approach to predict events within complex social networks by leveraging a combination of Skip-gram for node embedding and a 1D Convolutional Neural Network (ConvNet) for classification. This method effectively captures the intricate relationships and attributes within social graphs to forecast future events.

What Problem Does This Paper Address?

Social network analysis (SNA) faces a significant challenge in understanding and extracting actionable knowledge from the complex, dynamic nature of social graphs. Specifically, predicting events within these networks, which are inherently tied to the relationships and properties of actors, remains a difficult problem. Traditional methods struggle with the sheer scale and intricate interdependencies of these networks, making it hard to develop effective machine learning models for event prediction. The authors frame event prediction as a Satisfiability problem, acknowledging its NP-complete nature, and aim to build a more efficient predictive system.

Methods

The proposed methodology introduces a two-stage approach. First, a Skip-gram neural network, typically used in Natural Language Processing (NLP) for learning word embeddings, is adapted to learn vector-space embeddings for each vertex (actor) in the social graph. This step focuses on unsupervised representation learning, capturing the "context" of each actor by considering their neighbors. This process effectively reduces the dimensionality of the graph and extracts latent features.

Second, these low-dimensional node embeddings are fed as input to a 1D Convolutional Neural Network (ConvNet). This ConvNet is then trained in a supervised manner to classify and predict events based on the learned embeddings and corresponding event labels. The authors highlight that this architecture allows for learning nonlinear distributed representations within the graph structure.

Datasets

The authors trained and evaluated their proposed approach on datasets compiled in November 2017. These datasets were extracted from real-world social networks across three European countries. Each dataset comprised an average of 280,000 links and 48,000 actors. The paper does not introduce new benchmark datasets but utilizes existing real-world social network data.

Key Insights and Ideas

  • Adapting NLP Techniques for Graphs: The successful application of Skip-gram, a technique from NLP, to learn node embeddings in social networks demonstrates the power of cross-domain innovation. This highlights that the underlying principles of learning contextual representations can be generalized beyond text.
  • Dimensionality Reduction for Complexity: The pre-convolutional Skip-gram layer acts as a crucial dimensionality reduction step, making the complex graph structure more amenable to subsequent analysis by the ConvNet. This is key to handling the scale of real-world social networks.
  • Bridging Unsupervised and Supervised Learning: The methodology effectively combines unsupervised learning (Skip-gram for embeddings) with supervised learning (ConvNet for prediction), leveraging the strengths of both paradigms to tackle the event prediction task.

Key Results

The paper presents results in Table 1, showing the average performance of the 1D-ConvNet model across three different datasets (D1, D2, D3).

  • High Accuracy: The model achieved very high accuracy on both training and validation sets. For instance, on Dataset D1, the training accuracy was 99.91% and validation accuracy was 99.57%. Similar high accuracies were observed for D2 and D3.
  • Efficient Training: The training times varied across datasets, with D3 being the fastest at 321.49 seconds, suggesting that the model's efficiency scales with dataset size and complexity.

Limitations and Future Work

  • Validation Scope: The authors acknowledge that they are currently validating their propositions and aim to expand the experimentation scope to include more real-world social network datasets and benchmark methods.
  • Generalizability: While the results are promising, further validation on a wider variety of social network types and event prediction scenarios would be beneficial to assess the generalizability of the proposed approach.
  • Interpretability: The paper focuses on predictive performance. Further work could explore the interpretability of the learned embeddings and the ConvNet's decision-making process.

Summary updated

BibTeX
@inproceedings{molokwu2019event,
  author = {Bonaventure C. Molokwu},
  title = {{Event Prediction in Complex Social Graphs using One-Dimensional Convolutional Neural Network}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/914},
}

Loading related content...

Figure