論文の概要: Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance

• arxiv url: http://arxiv.org/abs/2606.18267v1
• Date: Mon, 01 Jun 2026 06:21:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-21 20:00:42.790533
• Title: Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance
• Title（参考訳）: グラフインスタンスのランドスケープ: 構造的類似性が(Not)最短パスのパフォーマンスを反映する
• Authors: Maryam Gholami Shiri, Ivana Krminac, Marko Djukanović, Sašo Džeroski, Eva Tuba, Tome Eftimov,
• Abstract要約: ショートパスアルゴリズムのベンチマークは、一般に異種グラフ集合上の集約性能に基づいている。 グラフを低コストな構造的特徴空間に埋め込み、類似した構造の領域にクラスタリングすることで、グラフベンチマークのインスタンスランドスケープビューを採用する。
• 参考スコア（独自算出の注目度）: 3.1732512178699745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Benchmarking shortest-path algorithms is commonly based on aggregate performance over heterogeneous graph sets, which limits insight into how different search paradigms react to instance structure. We adopt an instance-landscape view of graph benchmarking by embedding graphs into a low-cost structural feature space and clustering them into regions of similar structure. Three benchmark suites are studied: weighted Erdős--Rényi graphs, random geometric (wireless) graphs, and real-world road networks. We evaluate four representative shortest-path solvers spanning uninformed exact search (Dijkstra), bidirectional exact search (bidirectional Dijkstra), heuristic-guided exact search (A$^{*}$), and deque-based strategies (DEQ). Clustering robustness is analyzed under multiple feature-selection schemes, and runtime distributions are compared across landscape regions using non-parametric tests. While generator parameters induce stable structural regions, we find that feature-space similarity does not necessarily imply performance similarity: significant runtime shifts are frequently observed even within the same landscape region. A merged-suite analysis further shows that different benchmark families occupy largely disjoint regions. These results highlight both the potential and the limits of structural landscapes for the structure-aware benchmarking of shortest-path algorithms.
• Abstract（参考訳）: ショートパスアルゴリズムのベンチマークは、通常、異種グラフ集合上の集約性能に基づいており、異なる探索パラダイムがインスタンス構造にどう反応するかについての洞察を制限している。 グラフを低コストな構造的特徴空間に埋め込み、類似した構造の領域にクラスタリングすることで、グラフベンチマークのインスタンスランドスケープビューを採用する。 重み付きエルデシュ-レーニグラフ、ランダムな幾何学的(ワイヤレス)グラフ、現実世界の道路網の3つのベンチマークスイートが研究されている。 非形式的完全探索(Dijkstra)、双方向的完全探索(Dijkstra)、ヒューリスティック的誘導的完全探索(A$^{*}$)、復調的戦略(DEQ)の4つの代表的最短経路解法について検討した。 クラスタリングのロバスト性は複数の特徴選択スキームで分析され、非パラメトリックテストを用いてランドスケープ領域のランタイム分布を比較した。 ジェネレータパラメータは安定な構造領域を誘導するが,特徴空間の類似性は必ずしも性能の類似性を示唆するものではない。 マージスーツ解析により、異なるベンチマークファミリーが主に不整合領域を占めることが示された。 これらの結果は、最短パスアルゴリズムの構造を意識したベンチマークにおける構造景観の可能性と限界の両方を強調している。

関連論文リスト

• TopoAlign: Topology-Aware Visual Representation Alignment [18.80110544625249]
  TopoAlignは、構造の観点からモデル表現を視覚的に比較するためのフレームワークである。 TopoAlignは、トポロジカルな視点から表現構造とアライメントについて有意義な洞察を提供する。
  論文  参考訳（メタデータ） (2026-05-25T07:58:26Z)
• Persistent Homology of Time Series through Complex Networks [0.0]
  時系列は、3つのファミリーにまたがる5つの構造のうちの1つを通してグラフにマップされる。 グラフは、Vietoris-Rips濾過が永続図を生成する非相似行列に変換される。 これらの図は、持続的景観と位相的要約統計によって、固定長の特徴にベクトル化される。
  論文  参考訳（メタデータ） (2026-05-02T22:28:42Z)
• Robust Graph Matching through Semantic Relationship Generation for SLAM [0.15635627702544694]
  Scene Graphsは、ローカルに観測されたグラフと事前マップをマッチングすることで、構造化された屋内環境のローカライズを可能にする。 本稿では,検出対象と構造要素の関係を明示的にモデル化する意味強化グラフマッチング手法を提案する。 その結果、意味的関係は、候補マッチングの数を大幅に減らし、計算効率を向上し、より高速な収束を可能にした。
  論文  参考訳（メタデータ） (2026-04-28T09:15:51Z)
• PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
  グラフのクラスタリングノードは、グラフ解析の土台である。 いくつかの一般的な方法は、非常に大きなグラフには適さない。 この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
  論文  参考訳（メタデータ） (2024-12-18T08:15:55Z)
• GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs [72.51835626235368]
  2つのグラフを比較するとき、ノード構造的特徴の分布は、グローバルグラフ統計よりも有益である、と我々は主張する。 本稿では,各ノード表現セットのアライメントに基づいてグラフ間の類似性を評価するフレームワークGraphDCAを提案する。
  論文  参考訳（メタデータ） (2022-02-08T14:19:19Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。 まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。 次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
  論文  参考訳（メタデータ） (2021-03-25T09:31:41Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  カーネル重み付けの観点からノード集約を再解釈する。 本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。 特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
  論文  参考訳（メタデータ） (2020-05-16T04:44:29Z)
• Efficient and Stable Graph Scattering Transforms via Pruning [86.76336979318681]
  グラフ散乱変換(GST)は、グラフデータから特徴を抽出する訓練のないディープGCNモデルを提供する。 GSTが支払う価格は、層の数によって増加する空間と時間の指数関数的な複雑さである。 本研究は, GST の複雑性の限界に対処し, 効率的な (p) GST アプローチを導入する。
  論文  参考訳（メタデータ） (2020-01-27T16:05:56Z)

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

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