<(From Left) (From left) Professor Kijung Shin, Ph.D candidate Kyuhan Lee, and Ph.D candidate Geon Lee>
Just like when multiple people gather simultaneously in a meeting room, higher-order interactions—where many entities interact at once—occur across various fields and reflect the complexity of real-world relationships. However, due to technical limitations, in many fields, only low-order pairwise interactions between entities can be observed and collected, which results in the loss of full context and restricts practical use. KAIST researchers have developed the AI model "MARIOH," which can accurately reconstruct* higher-order interactions from such low-order information, opening up innovative analytical possibilities in fields like social network analysis, neuroscience, and life sciences.
*Reconstruction: Estimating/reconstructing the original structure that has disappeared or was not observed.
KAIST (President Kwang Hyung Lee) announced on the 5th that Professor Kijung Shin's research team at the Kim Jaechul Graduate School of AI has developed an AI technology called "MARIOH" (Multiplicity-Aware Hypergraph Reconstruction), which can reconstruct higher-order interaction structures with high accuracy using only low-order interaction data.
Reconstructing higher-order interactions is challenging because a vast number of higher-order interactions can arise from the same low-order structure.
The key idea behind MARIOH, developed by the research team, is to utilize multiplicity information of low-order interactions to drastically reduce the number of candidate higher-order interactions that could stem from a given structure.
In addition, by employing efficient search techniques, MARIOH quickly identifies promising interaction candidates and uses multiplicity-based deep learning to accurately predict the likelihood that each candidate represents an actual higher-order interaction.
<Figure 1. An example of recovering high-dimensional relationships (right) from low-dimensional paper co-authorship relationships (left) with 100% accuracy, using MARIOH technology.>
Through experiments on ten diverse real-world datasets, the research team showed that MARIOH reconstructed higher-order interactions with up to 74% greater accuracy compared to existing methods.
For instance, in a dataset on co-authorship relations (source: DBLP), MARIOH achieved a reconstruction accuracy of over 98%, significantly outperforming existing methods, which reached only about 86%. Furthermore, leveraging the reconstructed higher-order structures led to improved performance in downstream tasks, including prediction and classification.
According to Kijung, "MARIOH moves beyond existing approaches that rely solely on simplified connection information, enabling precise analysis of the complex interconnections found in the real world." Furthermore, "it has broad potential applications in fields such as social network analysis for group chats or collaborative networks, life sciences for studying protein complexes or gene interactions, and neuroscience for tracking simultaneous activity across multiple brain regions."
The research was conducted by Kyuhan Lee (Integrated M.S.–Ph.D. program at the Kim Jaechul Graduate School of AI at KAIST; currently a software engineer at GraphAI), Geon Lee (Integrated M.S.–Ph.D. program at KAIST), and Professor Kijung Shin. It was presented at the 41st IEEE International Conference on Data Engineering (IEEE ICDE), held in Hong Kong this past May.
※ Paper title: MARIOH: Multiplicity-Aware Hypergraph Reconstruction
※ DOI: https://doi.ieeecomputersociety.org/10.1109/ICDE65448.2025.00233
< external_image >
This research was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) through the project "EntireDB2AI: Foundational technologies and software for deep representation learning and prediction using complete relational databases," as well as by the National Research Foundation of Korea through the project "Graph Foundation Model: Graph-based machine learning applicable across various modalities and domains."
