Instruction Set and Language for Hypergraphs

• URL: http://arxiv.org/abs/2607.10194v1
• Date: Sat, 11 Jul 2026 08:15:52 GMT
• Title: Instruction Set and Language for Hypergraphs
• Abstract summary: We present IsalHG, a method for representing the structure of any finite, connected hypergraph of hyperedge arity as a string.<n>Every string over $_mathrmHG$ decodes to a valid hypergraph; the alphabet is closed.<n>We contribute the representation framework, a conjecture of canonical completeness, and the first native-versus-Levi benchmark for hypergraph isomorphism.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet $Σ_{\mathrm{HG}}$. The encoding is executed by a small virtual machine comprising a sparse hypergraph, a circular doubly-linked list (CDLL) of node references, and $k$ traversal pointers, where $k$ bounds the hyperedge arity. Instructions either move a pointer through the CDLL or insert a hyperedge, optionally together with new nodes, into the hypergraph. Every string over $Σ_{\mathrm{HG}}$ decodes to a valid hypergraph; the alphabet is closed. A greedy \emph{HypergraphToString} (h2s) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a \emph{canonical string} $w^{*}$, which we conjecture to be a complete isomorphism invariant. Canonical-string equality then decides hypergraph isomorphism natively, without the standard reduction to the Levi incidence graph followed by a graph-isomorphism engine. We verify the round-trip property $s2h(h2s(H)) \cong H$ on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss operating on the 2-coloured Levi graph -- across a $(n, c)$ grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio $311\times$ to $117{,}672\times$), which we report as measured. We contribute the representation framework, a conjecture of canonical completeness, and the first native-versus-Levi benchmark for hypergraph isomorphism.

Related papers

• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  We prove Feige's 2008 conjecture on the hypergraph Moore bound.<n>For every $kge3$ and every $1leellle n$, any $k$-uniform hypergraph on $n$ vertices with more than $C,nk/2/ellk/2-1$ hyperedges contains an even cover of size at most $A,elllog(en/ell)$.
  arXiv  Detail & Related papers  (2026-07-28T17:38:31Z)
• Hypergraph as Language [49.35033483821496]
  We propose a hypergraph-native alignment framework for large language models.<n>For hypergraph structures, existing methods often fail to preserve the native semantics that multiple objects are jointly connected by the same high-order relation.<n>We show that Hyper-Align significantly outperforms existing methods across in-domain and zero-shot evaluations.
  arXiv  Detail & Related papers  (2026-05-21T01:09:48Z)
• DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
  We introduce DRESS, a framework that refines the structural similarity of edges in a graph to produce a canonical fingerprint.<n>The fingerprint is isomorphism-invariant by construction, numerically stable (all values lie in $[0,2]$), fast and embarrassingly parallel to compute.<n>$$-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and iterated deletion ($k$-DRESS) climbs the staircase, achieving $(k+2)$-WL at each depthk$.
  arXiv  Detail & Related papers  (2026-02-24T12:18:42Z)
• Non-adaptive Learning of Random Hypergraphs with Queries [0.9831489366502302]
  We study the problem of learning a hidden hypergraph $G=(V,E)$ by making a single batch of queries (non-adaptively)<n>We generalize the result of Li et al. to the setting of random $k$-uniform hypergraphs.
  arXiv  Detail & Related papers  (2025-01-22T10:14:27Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Hypergraph $p$-Laplacian regularization on point clouds for data interpolation [3.79830302036482]
  Hypergraphs are widely used to model higher-order relations in data.<n>We define the $varepsilon_n$-ball hypergraph and the $k_n$-nearest neighbor hypergraph on a point cloud.<n>We prove the variational consistency between the hypergraph $p$-Laplacian regularization and the $p$-Laplacian regularization in a semi-supervised setting.
  arXiv  Detail & Related papers  (2024-05-02T09:17:32Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  We present a method for solving general non-strongly-concave bilevel optimization problems. Our results also improve upon the existing complexity for finding second-order stationary points in non-strongly-concave problems.
  arXiv  Detail & Related papers  (2023-06-30T20:36:44Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Semi-supervised Hypergraph Node Classification on Hypergraph Line Expansion [7.933465724913661]
  We propose a new hypergraph formulation named the emphline expansion (LE) for hypergraphs learning. The proposed emphline expansion makes existing graph learning algorithms compatible with the higher-order structure. We evaluate the proposed line expansion on five hypergraph datasets, the results show that our method beats SOTA baselines by a significant margin.
  arXiv  Detail & Related papers  (2020-05-11T03:02:21Z)

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.