Analyzing Networks with Hypergraphs: Detection, Classification, and Prediction

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


Recent advances in large graph-based models have shown great performance in a variety of tasks, including node classification, link prediction, and influence modeling. However, these graph-based models struggle to capture high-order relations and interactions among entities effectively, leading them to underperform in many real-world scenarios.

This thesis focuses on analyzing networks using hypergraphs for detection, classification, and prediction methods in social media-related problems. In particular, we study four specific applications with four proposed novel methods: detecting topic-specific influential users and tweets via hypergraphs; detecting spatiotemporal, topic-specific, influential users and tweets using hypergraphs; augmenting data in hypergraphs to mitigate class imbalance issues; and introducing a novel hypergraph convolutional network model designed for the multiclass classification of mental health advice in Arabic tweets.

For the first method, existing solutions for influential user detection did not consider topics that could produce incorrect results and inadequate performance in that task. The proposed contributions of our work include:

  1. Developing a hypergraph framework that detects influential users and tweets.
  2. Proposing an effective topic modeling method for short texts.
  3. Performing extensive experiments to demonstrate the efficacy of our proposed framework.

For the second method, we extend the first method by incorporating spatiotemporal information into our solution. Existing influencer detection methods do not consider spatiotemporal influencers in social media, although influence can be greatly affected by geolocation and time. The contributions of our work for this task include: 1) Proposing a hypergraph framework that spatiotemporally detects influential users and tweets. 2) Developing an effective topic modeling method for short texts that geographically provides the topic distribution. 3) Designing a spatiotemporal topic-specific influencer user ranking algorithm. 4) Performing extensive experiments to demonstrate the efficacy of our proposed framework.

For the third method, we address the challenge of bot detection on social media platform X, where there's an inherent imbalance between genuine users and bots, a key factor leading to biased classifiers. Our approach leverages the rich structure of hypergraphs to represent X users and their interactions, providing a novel foundation for effective bot detection. The contributions of our work include: 1) Introducing a hypergraph representation of the X platform, where user accounts are nodes and their interactions form hyperedges, capturing the intricate relationships between users. 2) Developing HyperSMOTE to generate synthetic bot accounts within the hypergraph, ensuring a balanced training dataset while preserving the hypergraph's structure and semantics. 3) Designing a hypergraph neural network specifically for bot detection, utilizing node and hyperedge information for accurate classification. 4) Conducting comprehensive experiments to validate the effectiveness of our methods, particularly in scenarios with pronounced class imbalances.

For the fourth method, we introduce a Hypergraph Convolutional Network model for classifying mental health advice in Arabic tweets. Our model distinguishes between valid and misleading advice, leveraging high-order word relations in short texts through hypergraph structures. Our extensive experiments demonstrate its effectiveness over existing methods. The key contributions of our work include:

  1. Developing a hypergraph-based model for short text multiclass classification, capturing complex word relationships through hypergraph convolution.
  2. Defining four types of hyperedges to encapsulate local and global contexts and semantic similarities in our dataset.
  3. Conducting comprehensive experiments in which the proposed model outperforms several baseline models in classifying Arabic tweets, demonstrating its superiority.

For the fifth method, we extended our previous Hypergraph Convolutional Network (HCN) model to be tailored for sarcasm detection across multiple low-resource languages. Our model excels in interpreting the subtle and context-dependent nature of sarcasm in short texts by exploiting the power of hypergraph structures to capture complex, high-order relationships among words. Through the construction of three hyperedge types, our model navigates the intricate semantic and sentiment differences that characterize sarcastic expressions. The key contributions of our research are as follows:

  1. A hypergraph-based model was adapted for the task of sarcasm detection in five short low-resource language texts, allowing the model to capture semantic relationships and contextual cues through advanced hypergraph convolution techniques.
  2. Introducing a comprehensive framework for constructing hyperedges, incorporating short text, semantic similarity, and sentiment discrepancy hyperedges, which together enrich the model's ability to understand and detect sarcasm across diverse linguistic contexts.
  3. The extensive evaluations reveal that the proposed hypergraph model significantly outperforms a range of established baseline methods in the domain of multilingual sarcasm detection, establishing new benchmarks for accuracy and generalizability in detecting sarcasm within low-resource languages.



hypergraph learning, hypergraph, graph learning, hypergraph applications