論文の概要: Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index
- arxiv url: http://arxiv.org/abs/2606.24421v1
- Date: Tue, 23 Jun 2026 10:58:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:48.906632
- Title: Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index
- Title（参考訳）: 不変量の集約は連続部分グラフマッチングを加速させるか?限界、法則、動的スペクトル指数
- Authors: Minghao Chen, Jiale Zheng,
- Abstract要約: 本研究では, 動的グラフ上での非連続部分グラフマッチングを高速化できるかどうかを考察する。
4回のタッチアップデートで、基本的にすべてのプルーニングパワーを失うことを示しています。
分離されたCSMベンチマークに統合され、同一のマイナススペクトル制御に対して、テストは最大51%の候補を削除した。
- 参考スコア（独自算出の注目度）: 9.08583070642464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to $51\%$ of candidates or safely skip up to $47\%$ of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and $77$ solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists ($-99.9\%$ intermediates, $748\times$ faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.
- Abstract（参考訳）: スペクトルフィルタリング(Spectral filtering)は、最近emph{static}サブグラフマッチングに実質的なプルーニングを提供した: Laplacian interlacingは、クエリをホストできない候補を拒否する。
このような集合構造試験が動的グラフ上での 'emph{continuous} subgraph matching (CSM) を加速し、3つの部分で解答できるかどうかを検討する。
まず、遅延的に維持されたスペクトル境界は、スペクトルプルーニングが価値を持つ場所において、正確には不可能である:我々は、形式化された摂動緩和よりも最も厳密な安全な規則を特徴付け、それが4つの更新で本質的に全てのプルーニングパワーを失うことを示す。
第二に、プルーニングユーティリティと再計算コストは、バーチカンで反相関関係にある -- ハブは間違いなく決してプルーンではない -- なので、タッチで小さな隣のスペクトルを再計算することは、更新1秒あたりの正確なローカルスペクトルを、建設によって完結させる。
第三に、デカップリングされたCSMベンチマークと同一のミナススペクトル制御に比較して、テストは最大で511\%の候補を削除し、安全に47\%の更新列挙をスキップするが、列挙中間子は、ゲートのスキップされた第1レベルのバインディング(典型的にはゼロ)を超えて、2つのエンジン、4つの実グラフ、2つのストリームタイプ、77$の解決されたクエリをまたいだままである。
集計テストは、候補セット(建設、リストスキャン)のスケールを加速させる。
我々は、CSMフィルタの評価のための中間不変手法を蒸留し、再利用可能な動的局所スペクトル指数を解放する。
関連論文リスト
- Multi-Modal Spatio-Temporal Graph Neural Network with Mixture of Experts for Soil Organic Carbon Prediction [0.0]
既存のアプローチでは、手作りのコモーダルを古典的なMLとペアリングするか、豊富なスペクトルと時間情報を見逃す単一モードのディープモデルである。
本稿では,SpTGNNとグリッドベースアーキテクチャの両方に対処するマルチテンポラルグラフニューラルネットワークであるSpTG-NNを紹介する。
微調整されたTerraMindエンコーダは、Sentinel-2、Sentinel-1、DEM信号からノード特徴を抽出する。
論文 参考訳（メタデータ） (2026-06-15T11:25:38Z) - Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
モデルマージは、個別に調整された複数の専門家をトレーニングデータなしで単一のマルチタスクモデルに結合する。
State-of-the-art merging method formulate merging as a layer-wise interference problem。
本稿では,逐次降下の勾配-流路に一致するソフト指数フィルタを組み合わせた閉形式手法SWUDIを提案する。
論文 参考訳（メタデータ） (2026-06-05T14:00:47Z) - Benchmarking Recursive-Collapse Warning Claims Under Matched False-Positive Control [0.0]
再帰的なシステムは、過度な失敗が見える前に、崩壊のような状態に入ることができる。
障害が指向性テレメトリパターンに従うかどうかをテストするためのクレームバウンド型ベンチマークフレームワークであるLoopzeroを紹介した。
凍結した2つの公開アーティファクトベンチマークのブリッジを評価する。
論文 参考訳（メタデータ） (2026-05-29T20:12:42Z) - Tight Convergence Rates for Online Distributed Linear Estimation with Adversarial Measurements [66.94250413799232]
分散パラメータ-サーバ-ワーカー設定における乱数ベクトル$X$の推定について検討する。
主な課題は、敵の計測と非同期である。
その結果, 分散線形推定におけるロバスト性, 識別性, 統計的効率の統一的有限時間評価が得られた。
論文 参考訳（メタデータ） (2026-04-07T11:45:55Z) - Spectral Tempering for Embedding Compression in Dense Passage Retrieval [17.660889990235656]
最適スケーリング強度$$はグローバル定数ではないことを示す。
本研究では,適応的な$(k)$をコーパス固有スペクトルから直接導出する学習自由化手法であるSpectral Temperingを提案する。
論文 参考訳（メタデータ） (2026-03-19T10:01:32Z) - Learning Accurate Segmentation Purely from Self-Supervision [87.78965637247107]
Selfmentは完全に自己管理型のフレームワークで、人間のラベルなしでオブジェクトを生画像から直接分割する。
Selfmentは、複数のベンチマークで新しい最先端(SoTA)結果を設定する。
論文 参考訳（メタデータ） (2026-02-27T07:36:32Z) - Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
楽器分解位相空間に基づく取得レベルスカラー$S_mathcal B$を提案する。
本稿では, (S_mathcal B) が周期サンプリングの位相空間コヒーレンスを正確に同定できることを理論的に示す。
$|S_mathcal B|$は一貫してサンプリングジオメトリをランク付けし、トレーニングなしで下流での再構築/認識の困難を予測します。
論文 参考訳（メタデータ） (2025-12-22T10:03:51Z) - Robust Nearest Neighbour Retrieval Using Targeted Manifold Manipulation [0.0]
最近傍の検索は、分類と説明可能なAIパイプラインの中心である。
特徴多様体の指定された領域に各サンプルをどの程度容易に適用できるかを評価することによって,検索を再現するTMM-NNを提案する。
TMM-NNは軽量でクエリ固有のトリガパッチを通じてこれを実装している。
論文 参考訳（メタデータ） (2025-11-09T07:37:05Z) - Progressive End-to-End Object Detection in Crowded Scenes [96.92416613336096]
以前のクエリベースの検出器は2つの欠点に悩まされていた: まず、複数の予測が1つのオブジェクトに対して推論される。
具体的には、まず受理されたクエリを選択して正の予測を生成し、その後、受理された予測に従って残雑音のあるクエリを精査する。
提案手法は,混み合ったシーンにおける問合せ型検出器の性能を大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2022-03-15T06:12:00Z) - E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。
私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。
統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
論文 参考訳（メタデータ） (2022-03-07T17:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。