論文の概要: Building Navigable Graphs Without Search in Three Composable Stages
- arxiv url: http://arxiv.org/abs/2610.09041v1
- Date: Tue, 06 Oct 2026 19:42:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 21:58:22.575552
- Title: Building Navigable Graphs Without Search in Three Composable Stages
- Title（参考訳）: 3つの構成可能なステージで検索なしでナビゲート可能なグラフを構築する
- Abstract要約: ナビゲーション可能なグラフは、隣人を探すことなく構築できる。
中間者が品質を決定することを示す。
GIST上に構築されたすべてのプールは、正確なkNN天井の4%以内に着陸する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Navigable graphs can be built without searching for neighbors: partition the data, evaluate every pair inside each part, and select each point's edges from the candidates. We give such a construction in three separable stages and show that the middle one decides the quality. The pool is any partition with a few memberships per point. The ending turns a point's candidates into out-edges; ours keeps a bounded heap, prunes by occlusion with a per-corpus slack, and appends reverse edges, re-pruning only where a list overflows. The spine is any edge set, exempt from the prune, that keeps the graph reachable from its entry; ours, half-space-proximal edges over a random sample, routes monotonically to every sampled point and replaces a spanning tree at 1/10 to 1/500 of its cost. The ending composes with any partitioner: on PiPNN's own candidate pool it beats PiPNN's ending on each of six corpora from $10^6$ to $10^8$ points, by 3 to 14% in distance evaluations at equal recall, and with 60 to 120 memberships per point the composed build matches or beats a full dense construction at k=10 and k=100 on all six, in 0.5 to 0.9 of its build time, deterministically. The analysis explains why. Once a pool is localised its quality is set by the data: every pool built on GIST lands within 4% of the exact-kNN ceiling, and the pairs a block cover misses are predicted, point by point, by the local clustering of the kNN graph, whose zero-clustering tail sets the memberships a corpus needs and grows with n. All code, patches and logs are public.
- Abstract（参考訳）: データを分割し、各部分内のすべてのペアを評価し、候補から各ポイントのエッジを選択する。
このような構成を3つの分離可能な段階で行い、中間が品質を決定することを示す。
プールは任意のパーティションであり、ポイントごとにいくつかのメンバシップがある。
エンディングはポイントの候補をアウトエッジに回し、リストがオーバーフローする場所にのみ再プルーニングして、境界ヒープを保持し、コーパスごとのスラックで排他的にプルーンを保持します。
スピンは任意のエッジセットであり、プルーから除外され、グラフはそのエントリから到達可能であり、ランダムなサンプルの上の半空間近縁であり、単調に全てのサンプル点にルートし、そのコストの1/10から1/500でスパンニングツリーを置き換える。
PiPNN自身の候補プールでは、6つのコーパスのそれぞれでPiPNNのエンディングを10^6$から10^8$ポイントに、同じリコールでの距離評価で3から14%、構成されたビルドがk=10とk=100で完全に密集した構成を6つすべてで60から120のメンバシップで、決定論的に0.5から0.9で打ち負かす。
その分析は理由を説明します。
プールがローカライズされると、その品質はデータによって設定される: GIST上に構築された全てのプールは、正確なkNN天井の4%以内に到達し、ブロックカバーミスのペアは、kNNグラフの局所クラスタリングによって予測される。
すべてのコード、パッチ、ログは公開されています。
関連論文リスト
- EDiS: Edge Disjoint Subgraph Sparsification Framework for Graph Neural Networks [66.67492452029822]
EDiS (Edge-Disjoint Subgraph Sparsification framework) を導入する。
EDiSは平均ベンチマークスコア(精度/ROC-AUC)が最も高く、ランク付けされたメソッドの中では平均ランクとギャップ・ツー・ベストが低い。
論文 参考訳（メタデータ） (2026-10-06T20:09:02Z) - QAM: Quadratic-Accurate Checkpoint Merging via Sequential Consistency [44.9106079497003]
保存されたチェックポイントはトレーニングの軌道に沿って状態を記録しますが、通常、異なるスケジュールで訪問される状態の更新を判断しません。
これらのチェックポイントが、所定の更新強度でシーケンシャル参照のエンドポイントをいかに正確に再構築できるかを検討する。
論文 参考訳（メタデータ） (2026-09-28T13:39:41Z) - AutoGraphForge: Towards Automated Graph Theory Discovery [0.0]
AutoGraphForgeは、自動グラフ理論の導出-拡散-ホルマライゼーション-自明なシステムである。
新規性フィルタは、既知の結果によって既に候補が示唆されているか否かを線形プログラムを介して決定する。
HPCクラスタ上で数ラウンド実行されると、リフューテーションデータセットを生き残った6,522ドルの予想が生成される。
論文 参考訳（メタデータ） (2026-09-03T07:35:29Z) - Edge-Girth as a Structural Edge Feature for Graph Neural Networks [2.16169908192004]
メッセージパッシングに基づくグラフニューラルネットワーク(GNN)は1次元Weisfeiler-Leman色補正テスト(1-WL)ほど強力ではないことが証明された。
一般的な治療は、前もって計算された構造記述子でノードやエッジの機能を増強し、多くの場合、三角形や長いサイクルのような固定された小さな部分グラフを数えている。
我々は、この選択を避ける記述子について研究する。エッジのエッジ幅は、それを通る最も短いサイクルの長さであり、その乗法性はそのような最も短いサイクルの数である。
論文 参考訳（メタデータ） (2026-09-01T15:50:42Z) - The optimization landscape of peaked-circuit generation [0.0]
ピーク回路(Peaked circuit)は、ランダムな量子回路で、1ビットストリングを偶然よりもはるかに頻繁に返す。
私たちはその答えが依存する風景を地図化します。
L-BFGS-B は 3 つの例において n = 16 で収束したアダムより3.9 +/- 1.6% 上である。
論文 参考訳（メタデータ） (2026-08-12T10:17:41Z) - Right Makes Might: Aligning Verified Hidden States Empowers RL Reasoning [55.264863369127774]
現在の方法では、それぞれの正しいロールアウトを単一の報酬ビットに減らし、隠れた状態間で共有される幾何学的構造を無視している。
本稿では,RLトレーニングにおけるアンカートークンにおける正ロールアウトの最終層を,トレーニングと推論の両方においてゼロオーバーヘッドで整列する補助損失関数Hidden-Alignを提案する。
8つの数学的推論ベンチマークでは、Hidden-AlignはDAPOベースラインの平均パス@1をQwen3-1.7B, 4B, 14Bで3.8, 6.2, 5.4ポイント改善し、3つのスケールで一貫したパス@kゲインを得る。
論文 参考訳（メタデータ） (2026-06-02T06:51:15Z) - Coordination-Free Lane Partitioning for Convergent ANN Search [0.0]
生産ベクトルサーチシステムは、遅延サービスレベル目標(SLO)を満たすために、並列レーンにまたがる各クエリをファンアウトすることが多い。
複製を相補的な作業に同じコストと期限で変換する調整不要レーン分割器を提案する。
論文 参考訳（メタデータ） (2025-11-06T09:36:18Z) - Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits [24.592554830963966]
グラフが任意の開始ノードから任意のターゲットノードへの移動に成功すれば、グラフはナビゲート可能である。
アプリケーションにとって重要な問題は、スペーサーグラフを構築することができるかどうかである。
任意の次元において、任意の距離関数に対して、平均次数$O(sqrtn log n )$の任意の$n$点に対してナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
論文 参考訳（メタデータ） (2024-05-29T01:07:26Z) - Time-Aware Neighbor Sampling for Temporal Graph Networks [44.78349188966666]
TNSは時間情報から学習し、いつでも各ノードに対して適応的な受容的近傍を提供する。
TNSは、時間的複雑さを増大させることなく、その有効性を向上するために、人気のある時間的グラフネットワークに柔軟に組み込むことができる。
複数の標準データセットに対する実験結果から、TNSはエッジ予測とノード分類において大きな利益をもたらすことが示された。
論文 参考訳（メタデータ） (2021-12-18T05:08:51Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - PMP-Net: Point Cloud Completion by Learning Multi-step Point Moving
Paths [54.459879603473034]
我々はPMP-Netと呼ばれる新しいニューラルネットワークを設計し、地球移動体の動作を模倣する。
不完全な入力の各点を移動させ、ポイントクラウドを完結させ、ポイント移動パスの合計距離が最も短くなる。
点レベルの厳密でユニークな対応を学習し、不完全な形状と完全なターゲットの間の詳細なトポロジーと構造的関係を捉えることができる。
論文 参考訳（メタデータ） (2020-12-07T01:34:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。