Learning with higher-order interactions: from hypergraphs to multi-agent systems

Thesis

Higher-order interactions are defined by the capacity of multiple entities to collectively produce a meaningful group-level outcome, distinguishing their collaboration from a mere random assembly. They involve two key elements: the entity-level features of the entities involved and the group-level outcomes that emerge. Such interactions are pervasive across domains, from researchers co-authoring publications to programmers developing software. Therefore, it is crucial to explore learning methods that capture both sides of higher-order interactions: their interplay with entity-level features and their influence on group-level outcomes. This thesis addresses this challenge with a portfolio of novel methods at both the entity and group levels. At the entity level, we leverage the lens of hypergraph machine learning. We begin with the task of inferring implicit higher-order interactions from observed entity features, proposing HGSL, a hypergraph structure learning framework that infers implicit higher-order interactions with a novel dual-smoothness prior. For explicitly defined higher-order interactions, the key entity-level challenge is exploiting such interactions to enrich entity features. To this end, we propose two novel approaches: Hypergraph-MLP, which embeds higher-order interaction directly with a multi-layer perceptron via an original loss function, and TF-HNN, which uses a novel training-free message-passing module to encode higher-order interaction into entity features. Moving beyond the entity level, we turn to the study of higher-order interactions at the group level. We study this through the lens of large language model (LLM) based multi-agent systems. We first propose MATRIX, an LLM multi-agent simulation framework with a novel homophily-guided communication mechanism, showing that the group-level outcomes of higher-order interactions can lead to high-quality data for LLM posttraining. We then present a novel analysis framework revealing how the intrinsic characteristics of a task, especially its logical depth and capability width, critically determine whether higher-order interactions within LLM-based agents will yield effective group-level outcomes. To sum up, this thesis contributes to learning with higher-order interactions at both the entity and group levels from hypergraphs to multi-agent systems.

Authors: Tang, B

• DOI: 10.5287/ora-vmj9my4p0
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English