MARIOH: Multiplicity-Aware Hypergraph Reconstruction

• URL: http://arxiv.org/abs/2504.00522v2
• Date: Tue, 06 May 2025 14:22:16 GMT
• Title: MARIOH: Multiplicity-Aware Hypergraph Reconstruction
• Authors: Kyuhan Lee, Geon Lee, Kijung Shin,
• Abstract summary: We propose MARIOH, a supervised approach for reconstructing the original hypergraph from its projected graph by leveraging edge multiplicity.<n>In our experiments using 10 real-world datasets, MARIOH achieves up to 74.51% higher reconstruction accuracy compared to state-of-the-art methods.
• Score: 26.07529457537888
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Hypergraphs offer a powerful framework for modeling higher-order interactions that traditional pairwise graphs cannot fully capture. However, practical constraints often lead to their simplification into projected graphs, resulting in substantial information loss and ambiguity in representing higher-order relationships. In this work, we propose MARIOH, a supervised approach for reconstructing the original hypergraph from its projected graph by leveraging edge multiplicity. To overcome the difficulties posed by the large search space, MARIOH integrates several key ideas: (a) identifying provable size-2 hyperedges, which reduces the candidate search space, (b) predicting the likelihood of candidates being hyperedges by utilizing both structural and multiplicity-related features, and (c) not only targeting promising hyperedge candidates but also examining less confident ones to explore alternative possibilities. Together, these ideas enable MARIOH to efficiently and effectively explore the search space. In our experiments using 10 real-world datasets, MARIOH achieves up to 74.51% higher reconstruction accuracy compared to state-of-the-art methods.

Related papers

• Learning Efficient and Generalizable Graph Retriever for Knowledge-Graph Question Answering [75.12322966980003]
  Large Language Models (LLMs) have shown strong inductive reasoning ability across various domains.<n>Most existing RAG pipelines rely on unstructured text, limiting interpretability and structured reasoning.<n>Recent studies have explored integrating knowledge graphs with LLMs for knowledge graph question answering.<n>We propose RAPL, a novel framework for efficient and effective graph retrieval in KGQA.
  arXiv  Detail & Related papers  (2025-06-11T12:03:52Z)
• HERGC: Heterogeneous Experts Representation and Generative Completion for Multimodal Knowledge Graphs [6.615362280237532]
  Multi-modal knowledge graphs (MMKGs) enrich traditional knowledge graphs (KGs) by incorporating diverse modalities such as images and text.<n>MMKGC seeks to exploit these heterogeneous signals to infer missing facts, thereby mitigating the intrinsic incompleteness of MMKGs.<n>Recent generative completion approaches powered by advanced large language models (LLMs) have shown strong reasoning abilities in unimodal knowledge graph completion.<n>We propose HERGC, a Heterogeneous Experts Representation and Generative Completion framework for MMKGs.
  arXiv  Detail & Related papers  (2025-06-01T04:12:25Z)
• BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs [18.281284442275457]
  We introduce BEACON: a benchmark designed to rigorously evaluate both algorithmic (AL) and machine learning (ML) subgraph counting methods. BEACON provides a standardized dataset with verified ground truths, an integrated evaluation environment, and a public leaderboard. Our experiments reveal that while AL methods excel in efficiently counting subgraphs on very large graphs, they struggle with complex patterns.
  arXiv  Detail & Related papers  (2025-04-15T07:53:47Z)
• Constrained Auto-Regressive Decoding Constrains Generative Retrieval [71.71161220261655]
  Generative retrieval seeks to replace traditional search index data structures with a single large-scale neural network. In this paper, we examine the inherent limitations of constrained auto-regressive generation from two essential perspectives: constraints and beam search.
  arXiv  Detail & Related papers  (2025-04-14T06:54:49Z)
• rEGGression: an Interactive and Agnostic Tool for the Exploration of Symbolic Regression Models [0.0]
  We introduce rEGGression, a tool using e-graphs to enable the exploration of a large set of symbolic expressions. The main highlight is its focus in the exploration of the building blocks found during the search that can help the experts to find insights about the studied phenomena.
  arXiv  Detail & Related papers  (2025-01-29T18:57:44Z)
• Small Object Detection via Coarse-to-fine Proposal Generation and Imitation Learning [52.06176253457522]
  We propose a two-stage framework tailored for small object detection based on the Coarse-to-fine pipeline and Feature Imitation learning. CFINet achieves state-of-the-art performance on the large-scale small object detection benchmarks, SODA-D and SODA-A.
  arXiv  Detail & Related papers  (2023-08-18T13:13:09Z)
• Towards General Visual-Linguistic Face Forgery Detection [95.73987327101143]
  Deepfakes are realistic face manipulations that can pose serious threats to security, privacy, and trust. Existing methods mostly treat this task as binary classification, which uses digital labels or mask signals to train the detection model. We propose a novel paradigm named Visual-Linguistic Face Forgery Detection(VLFFD), which uses fine-grained sentence-level prompts as the annotation.
  arXiv  Detail & Related papers  (2023-07-31T10:22:33Z)
• IMKGA-SM: Interpretable Multimodal Knowledge Graph Answer Prediction via Sequence Modeling [3.867363075280544]
  Multimodal knowledge graph link prediction aims to improve the accuracy and efficiency of link prediction tasks for multimodal data. New model is developed, namely Interpretable Multimodal Knowledge Graph Answer Prediction via Sequence Modeling (IMKGA-SM) Model achieves much better performance than SOTA baselines on multimodal link prediction datasets of different sizes.
  arXiv  Detail & Related papers  (2023-01-06T10:08:11Z)
• Supervised Hypergraph Reconstruction [3.69853388955692]
  Many real-world systems involving high-order interactions are best encoded by hypergraphs. Their datasets often end up being published or studied only in the form of their projections. We propose supervised hypergraph reconstruction. Our approach outperforms all baselines by an order of magnitude in accuracy on hard datasets.
  arXiv  Detail & Related papers  (2022-11-23T23:15:03Z)
• Learning Multi-Granular Hypergraphs for Video-Based Person Re-Identification [110.52328716130022]
  Video-based person re-identification (re-ID) is an important research topic in computer vision. We propose a novel graph-based framework, namely Multi-Granular Hypergraph (MGH) to better representational capabilities. 90.0% top-1 accuracy on MARS is achieved using MGH, outperforming the state-of-the-arts schemes.
  arXiv  Detail & Related papers  (2021-04-30T11:20:02Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• MRDet: A Multi-Head Network for Accurate Oriented Object Detection in Aerial Images [51.227489316673484]
  We propose an arbitrary-oriented region proposal network (AO-RPN) to generate oriented proposals transformed from horizontal anchors. To obtain accurate bounding boxes, we decouple the detection task into multiple subtasks and propose a multi-head network. Each head is specially designed to learn the features optimal for the corresponding task, which allows our network to detect objects accurately.
  arXiv  Detail & Related papers  (2020-12-24T06:36:48Z)
• Robust Facial Landmark Detection by Multi-order Multi-constraint Deep Networks [35.19368350816032]
  We propose a Multi-order Multi-constraint Deep Network (MMDN) for more powerful feature correlations and shape constraints learning. An Implicit Multi-order Correlating Geometry-aware (IMCG) model is proposed to introduce the multi-order spatial correlations and multi-order channel correlations. An Explicit Probability-based Boundary-adaptive Regression (EPBR) method is developed to enhance the global shape constraints.
  arXiv  Detail & Related papers  (2020-12-09T09:11:47Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.