論文の概要: Expressive Power of Deep Homomorphism Networks over Relational Databases

• arxiv url: http://arxiv.org/abs/2605.22852v1
• Date: Mon, 18 May 2026 06:28:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:19.994493
• Title: Expressive Power of Deep Homomorphism Networks over Relational Databases
• Title（参考訳）: 関係データベース上での深層準同型ネットワークの表現力
• Authors: Moritz Schönherr, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Arie Soeteman,
• Abstract要約: 我々は,関係データベース上で学習するモデルとして,ディープホモモーフィズムネットワーク(DHN)を提唱する。 我々は、DHNの正確な表現力について、様々な自然断片と一階述語論理の拡張を関連づけて研究する。 また、DHNに対する2つの基本静的解析問題の決定可能性、空度問題と仮定問題についても検討する。
• 参考スコア（独自算出の注目度）: 9.932884719997432
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly well-suited for learning over relational databases, due to their close connection to important fragments of SQL such as conjunctive queries. We study the precise expressive power of DHNs by relating them to various natural fragments and extensions of first-order logic (FO). For DHNs with max, sum, and mean aggregations, we establish connections to the unary negation fragment (UNFO) and to the extensions of UNFO with counting quantifiers and with ratio quantifiers. We further relate sum-aggregation DHNs to the unary quantifier alternation fragment of FO and to an extension of FO with expressive counting. Through the classical correspondence between FO and SQL, these results also illuminate the relation between DHNs and SQL. They also enable us to study the decidability of two fundamental static analysis problems for DHNs, the emptiness problem and the subsumption problem. Finally, we confirm through experiments that the established differences in expressive power are reflected in the performance on suitable prediction tasks.
• Abstract（参考訳）: メッセージパスグラフニューラルネットワーク(GNN)の表現力のある制限は、より強力なグラフ学習アーキテクチャを動機付けている。 我々はDHN(Deep Homomorphism Networks)を,特に関係データベース上での学習に適したモデルとして提唱する。 本稿では,DHNの表現力について,様々な自然断片と一階述語論理の拡張を関連づけて検討する。 最大,和,平均アグリゲーションを持つDHNに対して、ユニタリ否定フラグメント(UNFO)とUNFOの拡張との接続を確立する。 さらに、和集合DHNsは、FOの単項量化器の変質フラグメントと、表現的数え上げを伴うFOの拡張とを関連付ける。 FOとSQLの古典的な対応を通して、これらの結果はDHNとSQLの関係を照らす。 また, DHN に対する2つの基本静的解析問題, 空度問題, 仮定問題の決定可能性についても検討できる。 最後に,表現力の確立された相違が適切な予測タスクの性能に反映されていることを実験を通して確認する。

関連論文リスト

• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  本稿では,Large Language Models (LLM) を用いたエンドツーエンド学習のための新しいグラフ検索手法を提案する。 抽出したサブグラフでは, 構造的知識と意味的特徴をそれぞれ軟式トークンと言語化グラフで符号化し, LLMに注入する。 提案手法は、複雑な推論タスクに対する結合グラフ-LLM最適化の強みを検証し、最先端の性能を一貫して達成する。
  論文  参考訳（メタデータ） (2025-09-20T02:38:00Z)
• Database Views as Explanations for Relational Deep Learning [7.126902744514975]
  本稿では,リレーショナルデータベース上での機械学習モデルを記述するための新しいフレームワークを提案する。 我々は,全データベースの空間を網羅的に探索することを避けるアルゴリズムを開発した。 この手法はRelBenchコレクションに関する広範な実証研究を通じて評価される。
  論文  参考訳（メタデータ） (2025-09-11T14:11:48Z)
• Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures [50.46688111973999]
  グラフ機械学習は、任意のグラフ構造化データで学習するモデルの能力を大幅に向上させた。 従来の工学的特徴を伴わない'関係エンティティグラフ'のエンドツーエンド表現を可能にする新しい青写真を提案する。 本稿では、大規模マルチテーブル統合や、時間力学と異種データのモデリングの複雑さなど、重要な課題について論じる。
  論文  参考訳（メタデータ） (2025-06-19T23:51:38Z)
• LLM Enhancers for GNNs: An Analysis from the Perspective of Causal Mechanism Identification [19.389891710579022]
  グラフニューラルネットワーク(GNN)の入力として使用されるノード表現を最適化する機能拡張器として,大規模言語モデル(LLM)を用いて検討する。 解析結果に基づいて,LLMエンハンサーとGNN間の情報伝達を改善するためのプラグアンドプレイ最適化モジュールを設計する。
  論文  参考訳（メタデータ） (2025-05-13T06:29:25Z)
• Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning [73.2950349728376]
  大規模言語モデル(LLM)は、幅広いタスクで顕著な成功を収めている。 しかし、彼らは情報片間の関係を理解し、推論する必要があるタスクの推論において、依然として課題に直面している。 この課題は、論理的推論やマルチホップ質問応答など、多段階プロセスに関わるタスクにおいて特に顕著である。 本稿では、まず文脈から明示的なグラフを構築することにより、グラフを用いた推論(RwG)を提案する。
  論文  参考訳（メタデータ） (2025-01-14T05:18:20Z)
• G-SAP: Graph-based Structure-Aware Prompt Learning over Heterogeneous Knowledge for Commonsense Reasoning [8.02547453169677]
  本稿では,G-SAP という名称のコモンセンス推論のためのグラフベース構造認識プロンプト学習モデルを提案する。 特にエビデンスグラフは、ConceptNet、Wikipedia、Cambridge Dictionaryといった複数の知識ソースを統合することで構築される。 その結果、既存のモデル、特にOpenbookQAデータセット上のSoTA LM+GNNsモデルよりも6.12%改善された。
  論文  参考訳（メタデータ） (2024-05-09T08:28:12Z)
• Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs [53.03085605769093]
  我々は、マルチソースグラフデータに対するプライバシ保護推論を促進する先駆的な体系的フレームワークであるFederated Neural Graph DataBase(FedNGDB)を学習することを提案する。 FedNGDBは、フェデレートされた学習を活用して、複数のソースにわたるグラフ表現を協調的に学習し、エンティティ間の関係を強化し、グラフデータの全体的な品質を改善する。
  論文  参考訳（メタデータ） (2024-02-22T14:57:44Z)
• SUN: Exploring Intrinsic Uncertainties in Text-to-SQL Parsers [61.48159785138462]
  本稿では,ニューラルネットワークに基づくアプローチ(SUN)における本質的な不確かさを探索することにより,テキストから依存への変換性能を向上させることを目的とする。 5つのベンチマークデータセットの大規模な実験により、我々の手法は競合より大幅に優れ、新しい最先端の結果が得られた。
  論文  参考訳（メタデータ） (2022-09-14T06:27:51Z)
• MrGCN: Mirror Graph Convolution Network for Relation Extraction with Long-Term Dependencies [32.27755470353054]
  関係抽出では、豊富な構文的手がかりを含む依存木がテキストの長期依存を捉えるのに広く使われている。 関係抽出に適したプールアンプール構造を持つGNNモデルであるミラーグラフ畳み込みネットワーク(MrGCN)を提案する。 2つのデータセットを用いた実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2021-01-01T00:52:53Z)

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

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