論文の概要: Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables

• arxiv url: http://arxiv.org/abs/2605.25985v1
• Date: Mon, 25 May 2026 16:04:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:20.456053
• Title: Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables
• Title（参考訳）: 複数の自由変数を持つ複雑な論理的クエリのためのニューラルネットワークのスケーラブルなシンボリック検索フレームワーク
• Authors: Weizhi Fei, Hang Yin, Zihao Wang, Shukai Zhao, Wei Zhang, Yangqiu Song,
• Abstract要約: 複雑クエリアンサーリング(CQA)は、不完全知識グラフ(KG)上の基本的な知識表現と推論タスクである ここで$mathcalEk$はKGのエンティティセットを表す。 既存のベンチマークとメソッドは、個々の変数よりも限界ランクに依存している。 我々は、$mathcalEk$を列挙することなく、共同ランキングを近似するフレームワークであるNeural Scalable Symbolic Search (NS3)を提案する。
• 参考スコア（独自算出の注目度）: 55.952069550106906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complex Query Answering (CQA) is a fundamental knowledge representation and reasoning task over incomplete knowledge graphs (KGs). Answering existential first-order queries with $k$ free variables (i.e., $\text{EFO}_k$ queries) is a crucial yet challenging problem, as it requires ranking answer tuples in $\mathcal{E}^k$, where $\mathcal{E}$ denotes the entity set of a KG. This quickly becomes intractable as $k$ grows. Consequently, existing benchmarks and methods rely on marginal rankings over individual variables; however, marginal rankings are a poor proxy for the true joint ranking of tuples. Building on neural symbolic search for $\text{EFO}_1$ queries, we propose Neural Scalable Symbolic Search (NS3), a budgeted framework that approximates joint ranking without enumerating $\mathcal{E}^k$. NS3 (i) answers marginalized sub-queries to obtain necessary candidate sets, (ii) merges multiple free variables into hypernodes whose domains are pruned and controlled by a dynamic budget $B$, and (iii) progressively reduces an $\text{EFO}_k$ query to an $\text{EFO}_{k-1}$ query over a budgeted reduced domain. Across three standard KG datasets, NS3 substantially improves joint ranking performance while retaining strong marginal accuracy. We further release a joint-ranking benchmark that extends existing $\text{EFO}_1$ datasets to $k=3$, enabling systematic evaluation of multi-variable queries. Our code is provided in https://github.com/HKUST-KnowComp/NS3_KDD2026.
• Abstract（参考訳）: 複雑クエリアンサーリング(CQA)は、不完全知識グラフ(KG)上の基本的な知識表現および推論タスクである。 k$自由変数(例えば$\text{EFO}_k$クエリ)で存在可能な1次クエリを答えることは非常に難しい問題であり、$\mathcal{E}^k$で答えのタプルをランク付けする必要がある。 これは、$k$が成長するにつれて、すぐに難易度が上がる。 その結果、既存のベンチマークとメソッドは個々の変数よりも限界ランクに依存している。 そこで我々は,$\mathcal{E}^k$を列挙することなく,共同ランキングを近似するフレームワークであるNeural Scalable Symbolic Search (NS3)を提案する。 NS3 一 必要候補集合を得るための余分なサブクエリーを回答すること。 (ii)複数の自由変数をハイパーノードにマージし、ドメインは動的予算で$B$でプルーニングされ、制御される。 (iii)$\text{EFO}_k$クエリを、予算の削減されたドメイン上の$\text{EFO}_{k-1}$クエリに段階的に還元する。 3つの標準KGデータセット全体で、NS3は強い限界精度を維持しながら、共同ランキング性能を大幅に改善する。 さらに、既存の$\text{EFO}_1$データセットを$k=3$に拡張し、マルチ変数クエリの体系的な評価を可能にした。 我々のコードはhttps://github.com/HKUST-KnowComp/NS3_KDD2026で提供されている。

関連論文リスト

• Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
  未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。 非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。 我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
  論文  参考訳（メタデータ） (2025-05-08T07:27:29Z)
• Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding [27.138031759281745]
  ボルダのスコアリングとレーマー符号を用いた最初の連邦ランクアグリゲーション法を提案する。 この結果は,Mallowsモデルの下での集中的および分散的設定におけるボルダ法の最初の厳密な解析である。
  論文  参考訳（メタデータ） (2024-09-01T21:36:09Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis [36.646876613637325]
  マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T08:18:47Z)
• Adapting Neural Link Predictors for Data-Efficient Complex Query Answering [45.961111441411084]
  本稿では,複雑な問合せタスクに対して,ニューラルネットワーク予測スコアを再校正するために最適化されたパラメータ効率のスコア強調モデルを提案する。 CQD$mathcalA$は現在の最先端手法よりもはるかに正確な結果が得られる。
  論文  参考訳（メタデータ） (2023-01-29T00:17:16Z)
• How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
  機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。 本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。 さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
  論文  参考訳（メタデータ） (2021-10-05T20:15:35Z)
• A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
  すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。 このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2020-06-29T03:03:29Z)
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings [84.0206612938464]
  query2boxは、不完全な知識グラフ上の任意のクエリを推論するための埋め込みベースのフレームワークである。 query2boxは、スケーラブルな方法で$wedge$, $vee$, $exists$で任意の論理クエリを処理可能であることを示す。 本稿では,3つの大規模KGに対するQuery2boxの有効性を示すとともに,クエリ2boxが技術状況に対して最大25%の相対的な改善を達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-14T11:20:10Z)

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

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