論文の概要: Instruction Set and Language for Hypergraphs
- arxiv url: http://arxiv.org/abs/2607.10194v1
- Date: Sat, 11 Jul 2026 08:15:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 15:40:48.33423
- Title: Instruction Set and Language for Hypergraphs
- Title（参考訳）: ハイパーグラフのための命令セットと言語
- Abstract要約: IsalHG は任意の有限連結なハイパーグラフの構造を文字列として表現する手法である。
$_mathrmHG$上のすべての文字列は有効なハイパーグラフにデコードされる。
我々は、表現フレームワーク、標準完全性予想、およびハイパーグラフ同型のための最初のネイティブ・ヴァース・レヴィベンチマークに貢献する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: IsalHG は、有界なハイパーエッジアリティの任意の有限連結ハイパーグラフの構造をコンパクトな命令アルファベット $Σ_{\mathrm{HG}}$ 上の文字列として表す方法である。
符号化は、スパースハイパーグラフ、ノード参照の円形二重リンクリスト(CDLL)、および$k$のトラバースポインタからなる小さな仮想マシンで実行される。
命令は、CDLLを通してポインタを移動させるか、オプションで新しいノードと共にハイパーエッジをハイパーグラフに挿入する。
Σ_{\mathrm{HG}}$ 上のすべての文字列は有効なハイパーグラフに復号する。
greedy \emph{HypergraphToString} (h2s) アルゴリズムは任意の連結ハイパーグラフを文字列にエンコードする。
カノニカルストリングの等式は、レヴィ入射グラフへの標準還元を伴わずに、ハイパーグラフ同型を自然に決定し、グラフ同型エンジンが続く。
我々は、150個の連結したランダムな均一なハイパーグラフと名前付き組合せ設計上のラウンドトリップ特性$s2h(h2s(H)) \cong H$を検証し、この標準アルゴリズムを、セル毎に10のシードを持つ$(n, c)$グリッドの2色Leviグラフ上で動作している3つの実用的正確なベースライン – nauty, Traces, bliss – に対してベンチマークする。
4つの方法はすべて、完全性予想と一致して、600の同型検証のうちの1つに一致する。
壁面時間では、Leviベースラインがテストされた全てのセルを3～5桁(幾何学平均比311\times$から117{,}672\times$)で支配している。
我々は、表現フレームワーク、標準完全性予想、およびハイパーグラフ同型のための最初のネイティブ・ヴァース・レヴィベンチマークに貢献する。
関連論文リスト
- A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
ハイパーグラフムーア境界に関するファイゲの2008年の予想を証明する。
すべての$kge3$と$1leellle n$に対して、$n$ vertices 上の任意の $k$-uniform hypergraph は、$C,nk/2/ellk/2-1$ hyperedges は、最大$A,elllog(en/ell)$で偶数被覆を含む。
論文 参考訳（メタデータ） (2026-07-28T17:38:31Z) - Hypergraph as Language [49.35033483821496]
大規模言語モデルのためのハイパーグラフネイティブアライメントフレームワークを提案する。
ハイパーグラフ構造の場合、既存のメソッドは複数のオブジェクトが同じ高次関係で結合されているというネイティブセマンティクスを保存するのに失敗することが多い。
また,Hyper-Alignはドメイン内およびゼロショット評価において,既存手法よりも大幅に優れていることを示す。
論文 参考訳（メタデータ） (2026-05-21T01:09:48Z) - DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
本稿では,グラフ内のエッジの構造的類似性を洗練し,標準指紋を生成するフレームワークDRESSを紹介する。
フィンガープリントは構成上は同型不変であり、数値的には安定である(すべての値は$[0,2]$)。
$-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除(k$-DRESS)が階段を登り、各深さk$で$(k+2)$-WLを達成する。
論文 参考訳（メタデータ） (2026-02-24T12:18:42Z) - Non-adaptive Learning of Random Hypergraphs with Queries [0.9831489366502302]
隠れハイパーグラフの$G=(V,E)$を1バッチのクエリで(非適応的に)学習する問題について検討する。
We generalize the results of Li et al. to the setting of random $k$-uniform hypergraphs。
論文 参考訳（メタデータ） (2025-01-22T10:14:27Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Hypergraph $p$-Laplacian regularization on point clouds for data interpolation [3.79830302036482]
ハイパーグラフはデータの高次関係をモデル化するために広く使われている。
点クラウド上の$varepsilon_n$-ballハイパーグラフと$k_n$-nearest 近傍ハイパーグラフを定義する。
半教師付き環境でのハイパーグラフ$p$-ラプラシアン正則化と$p$-ラプラシアン正則化の間の変分一貫性を証明した。
論文 参考訳（メタデータ） (2024-05-02T09:17:32Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Hypergraph Convolutional Networks via Equivalency between Hypergraphs
and Undirected Graphs [59.71134113268709]
本稿では,EDVWおよびEIVWハイパーグラフを処理可能な一般学習フレームワークであるGeneral Hypergraph Spectral Convolution(GHSC)を提案する。
本稿では,提案するフレームワークが最先端の性能を達成できることを示す。
ソーシャルネットワーク分析,視覚的客観的分類,タンパク質学習など,様々な分野の実験により,提案手法が最先端の性能を達成できることが実証された。
論文 参考訳（メタデータ） (2022-03-31T10:46:47Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Semi-supervised Hypergraph Node Classification on Hypergraph Line
Expansion [7.933465724913661]
本稿では,ハイパーグラフ学習のためのEmphline expansion (LE) という新しいハイパーグラフの定式化を提案する。
提案手法は,既存のグラフ学習アルゴリズムを高次構造に適合させる。
提案手法を5つのハイパーグラフデータセット上で評価し,提案手法がSOTAベースラインを有意差で上回ることを示す。
論文 参考訳（メタデータ） (2020-05-11T03:02:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。