Compressing Hypergraphs using Suffix Sorting

Enno Adler, Stefan Böttcher, Rita Hartel · 2025

Read Compressing Hypergraphs using Suffix Sorting by Enno Adler, Stefan Böttcher, Rita Hartel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05023.txt.

Introduction

Enno Adler, Stefan Böttcher, and Rita Hartel showed HyperCSA in 2025, a squeezing method for hypergraphs. Hypergraphs catch relationships including whole groups at once, co-authorships, social memberships, recommendations, and they grow large enough to strain storage, transmission, and query speed. Earlier squeezing methods either answered queries slowly or stopped scaling.

HyperCSA adapts suffix sorting, a method from text squeezing, to squeeze hypergraphs while still supporting standard queries on the squeezed form. On real-world hypergraphs it shrank files to between roughly a quarter and four fifths of their first size, beating current methods on every large test case. And it handled bigger data sets than its rivals. Neighbor queries, a basic operation, ran many times faster than on both normal data forms and competing squeezed versions.

Catalog record

CREATOREnno Adler, Stefan Böttcher, Rita Hartel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-05023

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Compressing Hypergraphs using Suffix Sorting Enno Adler, Stefan Böttcher, Rita Hartel Abstract Hypergraphs model complex, non-binary relationships like co-authorships, social group memberships, and recommendations. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26 % 26\% to 79 % 79\% of the original file size on real-world hypergraphs—outperforming existing methods on all large hypergraphs in our experiments. Additionally, HyperCSA scales to larger datasets than existing approaches. Furthermore, for common real-world hypergraphs, HyperCSA evaluates neighbor queries 6 6 to 40 40 times faster than both standard data structures and other hypergraph compression approaches. 1 Introduction Hypergraphs are powerful tools for modeling complex, non-binary relationships in data. Unlike traditional graphs, where edges connect only two nodes, hypergraphs allow edges to connect any number of nodes, enabling a more accurate representation of real-world systems. This modeling flexibility has made hypergraphs useful in a range of domains, such as social networks and groups [ 5 , 24 , 27 ] , recommendation systems for music [ 23 ] or news [ 14 ] , authorship of papers, telephone plants [ 9 ] , and tagged data from online platforms [ 7 ] . Recently, hypergraph learning algorithms demonstrated strong performance in various applications [ 11 ] including test retrieval [ 10 ] , image retrieval [ 15 ] , protein interactions [ 12 ] , users’ identification via different social networks [ 24 ] , computer vision [ 4 ] and multimedia retrieval [ 22 ] . In this paper, we introduce a succinct data structure for hypergraphs, HyperCSA. HyperCSA builds on Sadakane’s Compressed Suffix Array (CSA) [ 19 ] and is inspired by RDFCSA [ 1 ] . The CSA is a succinct data structure that can represent a string or a text collection and allows pattern searches like the Suffix Array (SA) [ 17 ] . Herein, our main contributions are as follows: • An algorithm, HyperCSA, to compress hypergraphs. • Theoretical bounds on compression size, compression speed, and query performance for HyperCSA. • An thorough experimental analysis of compression ratio, construction time, construction memory usage and query performance of HyperCSA. 2 Related Work Like graphs, hypergraphs can be very large. For large hypergraph databases, there is the research branch of partitioning a hypergraph [ 20 ] and of parallel graph processing with tools like Hygra [ 21 ] and CHGL [ 13 ] . Each hypergraph can be translated into a graph with edges connecting only two nodes, that describes essentially the same data as a hypergraph. Most common methods are the clique expansion, where the rank-k hyperedge is represented by a k-clique, and the star expansion, where a new node is introduced and all nodes of the hyperedge are connected by a new edge with that node. Both methods have multiple downsides regarding compression and querying: They increase the number of objects in the graph by a large factor in comparison to using hyperedges. These expanded graphs are less effective to compress and need many edge lookups to check for an existing hyperedge between multiple nodes. Huang et al. [ 11 ] conclude in the context of distributed hypergraph processing, that expanding hypergraphs to graphs cause major efficiency drawbacks. Liu et al. [ 16 ] argue likewise for graph processing acceleration. They propose a hypergraph compression method based on the incidence list: They use two one-dimensional arrays, one for the incident hyperedges and one for the nodes and two indexes for each one that contain the start and end of ranges in the arrays. They achieve compression by overlapping the equal nodes (or equal incident hyperedges) of successive hyperedges (or successive nodes). As neither nodes nor hyperedges have an order, they propose a reordering strategy for better compression and less cache misses on access. 3 Preliminaries In Appendix 0.C , there is a list of symbols used in this paper. A hypergraph is a pair G=(V_{G},E_{G}) with nodes V_{G}=\{0,1,\ldots,p\}\subset\mathbb{N}_{0} and edges E_{G}=\{e_{0},\dots,e_{m-1}\} . An edge e_{i}=\{v_{0},\ldots,v_{n-1}\}\subset V_{G} with e_{i}\not=\emptyset is an undirected hyperedge of rank(e_{i})=|e_{i}|=n . We call all elements in E_{G} edges regardless of their rank. HyperCSA can also handle non-simple hypergraphs, meaning E_{G} can contain the same edge multiple times. 1 1 1 We require that an edge contains each of its nodes exactly once because having the highest node in an edge twice would break our desired properties of the later introduced \Psi . In Figure 1 , we visualized the example hypergraph H=(\{0,1,2,3,4\},\{\{0,1,2,3\},\{1,2,3\},\{2\},\{0,1,2,4\},\{2\}\}) . Figure 1 : The example hypergraph H=(\{0,1,2,3,4\},\{\{0,1,2,3\},\{1,2,3\},\{2\}, \{0,1,2,4\},\{2\}\}) with 5 hyperedges. We define the degree(v)=|\{e\in E_{G}:v\in e\}| and M_{G}=\sum_{e\in E_{G}}rank(e)=\sum_{v\in V}degree(v) . For the example hypergraph H , degree(2)=5 and M_{H}=13 . We define a string T of length |T| over an alphabet \Sigma as a sequence T=T[0]\cdot T[1]\cdots T[|T|-1] of characters T[i]\in\Sigma for i<|T| . We write T[i,j] for a substring T[i]\cdot T[i+1]\cdots T[j] of T , T[i,j]=\epsilon if i>j , and T[i..]=T[i,|T|-1] for the suffix starting at position i . We define rank_{T}(x,c)=|\{i\leq x:T[i]=c\}| as the number of times c occurs in the first x+1 characters of T (including the current position). Next, we define select_{T}(x,c)=\min\{i<|T|:rank_{T}(i,c)=x\} as the position of the x -th c in T . The suffix array SA [ 17 ] of a string T is a permutation of \{0,\ldots,n-1\} such that the i -th smallest suffix of T is T[SA[i]..] with i\in\{0,\ldots,n-1\} . As permutations are one-to-one mappings, we denote the inverse of the suffix array by SA^{-1} . We use the term T-position for a position in T and SA-position for a position in SA . The compressed suffix array CSA [ 19 ] of a string T consists of a bitvector D of length |T| and a permutation \Psi of \{0,\ldots,n-1\} (and other data structures that we omit, because we do not need them). D is a succinct representation for T using the suffix array SA : D[i]=1 marks the first suffix in the sorted suffixes of T that start with a new character, so D[i]=1 if and only if T[SA[i]]>T[SA[i-1]] or i=0 . We assume that all symbols of \Sigma have at least one occurrence in T . By this assumption, we get T[SA[i]]=rank_{D}(i,1)-1 . \Psi[i] stores the SA-position j that points to the next T-position SA[i]+1 after the T-position SA[i] at SA-position i . In one term, SA[\Psi[i]]=(SA[i]+1)\mod n . Using the inverted suffix array SA^{-1} , we obtain \Psi as \Psi[i]=SA^{-1}[(SA[i]+1)\mod n] \Psi is a cyclic permutation, so \Psi contains exactly one cycle. By computing the ranks on D for the SA-positions i in order of the cycle of \Psi , we retrieve a rotation of T . 4 HyperCSA 4.1 Construction We begin with outlining the three major steps involved in constructing HyperCSA. First, because we use a CSA as the main component to compress a hypergraph G , we encode G as a string T . Second, we build the CSA for T . Third, we adjust \Psi to ensures that repeated applications of \Psi cycles within the same edge e\in E_{G} . This way, each edge has its

Read the complete text