ELRUHNA: Elimination Rule-basedHypergraph Alignment
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912425149726720 |
|---|---|
| author | Ibrahim, Cameron Ferdous, S M Safro, Ilya Minutoli, Marco Halappanavar, Mahantesh |
| author_facet | Ibrahim, Cameron Ferdous, S M Safro, Ilya Minutoli, Marco Halappanavar, Mahantesh |
| contents | Hypergraph alignment is a well-known NP-hard problem with numerous practical applications across domains such as bioinformatics, social network analysis, and computer vision. Despite its computational complexity, practical and scalable solutions are urgently needed to enable pattern discovery and entity correspondence in high-order relational data. The problem remains understudied in contrast to its graph based counterpart. In this paper, we propose ELRUHNA, an elimination rule-based framework for unsupervised hypergraph alignment that operates on the bipartite representation of hypergraphs. We introduce the incidence alignment formulation, a binary quadratic optimization approach that jointly aligns vertices and hyperedges. ELRUHNA employs a novel similarity propagation scheme using local matching and cooling rules, supported by an initialization strategy based on generalized eigenvector centrality for incidence matrices. Through extensive experiments on real-world datasets, we demonstrate that ELRUHNA achieves higher alignment accuracy compared to state-of-the-art algorithms, while scaling effectively to large hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09866 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ELRUHNA: Elimination Rule-basedHypergraph Alignment Ibrahim, Cameron Ferdous, S M Safro, Ilya Minutoli, Marco Halappanavar, Mahantesh Social and Information Networks Hypergraph alignment is a well-known NP-hard problem with numerous practical applications across domains such as bioinformatics, social network analysis, and computer vision. Despite its computational complexity, practical and scalable solutions are urgently needed to enable pattern discovery and entity correspondence in high-order relational data. The problem remains understudied in contrast to its graph based counterpart. In this paper, we propose ELRUHNA, an elimination rule-based framework for unsupervised hypergraph alignment that operates on the bipartite representation of hypergraphs. We introduce the incidence alignment formulation, a binary quadratic optimization approach that jointly aligns vertices and hyperedges. ELRUHNA employs a novel similarity propagation scheme using local matching and cooling rules, supported by an initialization strategy based on generalized eigenvector centrality for incidence matrices. Through extensive experiments on real-world datasets, we demonstrate that ELRUHNA achieves higher alignment accuracy compared to state-of-the-art algorithms, while scaling effectively to large hypergraphs. |
| title | ELRUHNA: Elimination Rule-basedHypergraph Alignment |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2506.09866 |