論文の概要: Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching

• arxiv url: http://arxiv.org/abs/2609.32641v1
• Date: Sat, 26 Sep 2026 14:03:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 21:43:39.63514
• Title: Extremely Fast and Compact Binary Graph Representations via Randomized Operator Sketching
• Title（参考訳）: ランダム化演算子スケッチによる超高速かつコンパクトなバイナリグラフ表現
• Abstract要約: グラフニューラルネットワークは通常、密度の高い浮動小数点ノード表現に依存する。 バイナリグラフハッシュは、ノード情報をコンパクトなビット文字列として符号化する代替手段を提供する。 グラフ構造から直接バイナリノード表現を構成する超高速で完全に代数的なハッシュ法を提案する。
• 参考スコア（独自算出の注目度）: 1.9876537502801799
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks typically rely on dense, floating-point node representations, which can impose substantial memory and computational costs. Binary graph hashing offers an alternative by encoding node information as compact bit strings. However, existing approaches either sacrifice global topological information for computational efficiency or incur substantial generation costs. We introduce an ultra-fast, entirely algebraic hashing method that constructs binary node representations directly from graph structure, without requiring node features or gradient-based training. Our method approximates a high-order structural transition matrix using randomized column sampling inspired by the Nyström method and combines it with an efficient label-safe semantic propagation mechanism. The resulting continuous representations are discretized through column-wise thresholding to obtain compact binary codes. Experiments on ten node classification datasets show that the proposed method consistently improves classification accuracy over existing feature-free binary baselines while requiring sub-second code generation on many datasets. The resulting binary representations are also naturally suited to event-driven computation, making them compatible with neuromorphic spiking neural networks and gradient-free learning rules. These results demonstrate that simple algebraic approximations can provide an efficient alternative to learned pipelines for discrete graph representation learning.
• Abstract（参考訳）: グラフニューラルネットワークは一般的に、密度の高い浮動小数点ノード表現に依存しており、かなりのメモリと計算コストを課す可能性がある。 バイナリグラフハッシュは、ノード情報をコンパクトなビット文字列として符号化する代替手段を提供する。 しかし、既存のアプローチでは、計算効率のためにグローバルなトポロジカルな情報を犠牲にするか、実質的な生成コストを発生させるかのいずれかである。 ノードの特徴や勾配に基づく訓練を必要とせず、グラフ構造から直接バイナリノード表現を構築する超高速で完全に代数的なハッシュ法を導入する。 提案手法は,Nyström法にインスパイアされたランダム化カラムサンプリングを用いて高次構造遷移行列を近似し,効率的なラベルセーフな意味伝達機構と組み合わせる。 結果の連続表現はカラムワイドしきい値によって離散化され、コンパクトなバイナリコードが得られる。 10個のノード分類データセットに対する実験により,提案手法は既存の特徴のないバイナリベースラインよりも一貫した分類精度を向上し,多くのデータセットでサブ秒単位のコード生成を必要とすることが示された。 結果として生じるバイナリ表現は、イベント駆動型計算にも自然に適しており、ニューロモルフィックスパイキングニューラルネットワークや勾配なし学習規則と互換性がある。 これらの結果は、単純な代数近似が、離散グラフ表現学習のための学習パイプラインの効率的な代替となることを示した。

関連論文リスト

• Columnar-Embedder: A Biologically Inspired Cortical Architecture for Binary Sparse Distributed Graph Representations [0.0]
  グラフノードのスパース分散表現を学習するためのカラムナー・エンベッドダーアーキテクチャを提案する。 このアーキテクチャは、ポータビリティ、ノイズに対するレジリエンス、データの破損に対する堅牢性を示す。 5つのグラフベンチマークにおいて、SDRの性能は実数値密度埋め込みと競合する。
  論文  参考訳（メタデータ） (2026-08-12T03:31:39Z)
• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。 ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
  論文  参考訳（メタデータ） (2026-07-30T02:45:31Z)
• Virtual Node Generation for Node Classification in Sparsely-Labeled Graphs [2.0060301665996016]
  本稿では,グラフに付加されたラベル付きノードとして,少数の高品質な合成ノードを注入する新しいノード生成手法を提案する。 一般的なグラフ事前学習(自己教師付き学習)、半教師付き学習、メタ学習法と互換性がある。 実験では、公開されている10のデータセットに対して、14のベースラインに対して統計的に有意なパフォーマンス改善を実証した。
  論文  参考訳（メタデータ） (2024-09-12T02:36:44Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  SparseDiffは、ほとんど全ての大きなグラフがスパースであるという観察に基づく、新しい拡散モデルである。 エッジのサブセットを選択することで、SparseDiffは、ノイズ発生過程とノイズ発生ネットワーク内のスパースグラフ表現を効果的に活用する。 本モデルでは,小規模・大規模両方のデータセットにおいて,複数のメトリクスにわたる最先端性能を示す。
  論文  参考訳（メタデータ） (2023-11-03T16:50:26Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphs [20.432261314154804]
  Digraphwaveは、有向グラフ上の構造ノード埋め込みを抽出するスケーラブルなアルゴリズムである。 この2つの組込み強化は、自己同型アイデンティティの分類において、マクロF1スコアの顕著な増加につながることが示されている。
  論文  参考訳（メタデータ） (2022-07-20T19:03:35Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。 まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。 次に,メッセージのパラメトリゼーション手法を提案する。
  論文  参考訳（メタデータ） (2020-06-26T17:15:16Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)
• Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
  本稿では,効率よく適応的なコード駆動グラフを提案する。 自動エンコーダのコンテキストでデコードすることで更新される。 ベンチマークデータセットの実験は、最先端のハッシュ手法よりもフレームワークの方が優れていることを明らかに示しています。
  論文  参考訳（メタデータ） (2020-02-27T05:58:12Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。