論文の概要: Arc search in graphs via Szegedy walks

• arxiv url: http://arxiv.org/abs/2604.19134v1
• Date: Tue, 21 Apr 2026 06:32:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-22 22:41:49.651332
• Title: Arc search in graphs via Szegedy walks
• Title（参考訳）: Szegedy walkによるグラフのアークサーチ
• Authors: Sho Kubota, Kiyoto Yoshino,
• Abstract要約: 本稿では,Szegedy ウォークを用いたグラフ内の1つの弧の探索について検討する。 アークサーチは、その位置だけでなく、特定の内部状態でも量子粒子を見つけることができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the search for a single arc in a graph using the Szegedy walk. Arc search can be interpreted as finding a quantum particle not only in its position but also with a specific internal state. The quantum walk employed in this study is essentially the model proposed by Segawa and Yoshie for the purpose of edge search. First, we investigate how the symmetry of a graph is reflected in its time evolution matrix, and provide a sufficient condition under which the success probability of the search is independent of the marked arc. In particular, we prove that if a graph is arc-transitive, the success probability is independent of the choice of the marked arc. Next, we analyze path and cycle graphs and show that the quantum search is ineffective for these graphs, whereas it performs well for complete bipartite graphs $K_{n,n}$. These results provide a theoretical foundation for studying arc and edge searches on various graphs, while also suggesting new problems concerning the eigenvalue analysis of edge-signed graphs in spectral graph theory.
• Abstract（参考訳）: 本稿では,Szegedy ウォークを用いたグラフ内の1つの弧の探索について検討する。 アークサーチは、その位置だけでなく、特定の内部状態でも量子粒子を見つけることができる。 本研究で用いた量子ウォークは、基本的に、エッジサーチのために瀬川と吉江が提唱したモデルである。 まず、グラフの対称性が時間発展行列にどのように反映されているかを調べ、探索の成功確率がマークされた弧に依存しない十分な条件を与える。 特に、グラフが弧-推移性であれば、成功確率はマークされた弧の選択とは無関係であることを示す。 次に、パスグラフとサイクルグラフを分析し、量子探索がこれらのグラフには有効でないことを示すが、完全な二部グラフでは$K_{n,n}$に対してうまく機能する。 これらの結果は、様々なグラフ上のアークとエッジ探索を研究するための理論的基盤を提供するとともに、スペクトルグラフ理論におけるエッジ符号グラフの固有値解析に関する新しい問題も提案する。

関連論文リスト

• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
  論文  参考訳（メタデータ） (2024-07-01T06:09:19Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  グラフ機械学習のための微粒なグラフ合理化(FIG)を提案する。 私たちのアイデアは、入力ノード間のリッチなインタラクションを提供するセルフアテンションメカニズムによって推進されます。 実験では,実世界の7つのデータセットを対象とし,提案したFIGは,13のベースライン手法と比較して大きな性能上の優位性を示した。
  論文  参考訳（メタデータ） (2023-12-13T02:56:26Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。 我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
  論文  参考訳（メタデータ） (2023-07-30T05:14:19Z)
• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  従来見過ごされていた現象を調査し、多くの場合、元のグラフに対して密に連結された補グラフを見つけることができる。 より密度の高いグラフは、選択的で有意義な知識を伝達するための自然なブリッジを提供する元のグラフとノードを共有することができる。 この設定をグラフインターセクション誘導トランスファーラーニング(GITL)とみなし,eコマースや学術共同オーサシップ予測の実践的応用に動機づけられた。
  論文  参考訳（メタデータ） (2023-02-27T22:56:06Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• A quantum searching model finding one of the edges of a subgraph in a complete graph [0.0]
  我々は,与えられた部分グラフのエッジの1つを完全グラフで探索する量子探索モデルを構築した。 モデルが任意の部分グラフ、すなわち完備グラフに対して有効であることを示す。
  論文  参考訳（メタデータ） (2022-02-03T08:45:39Z)
• Residual2Vec: Debiasing graph embedding with random graphs [1.9280643035418397]
  本稿では,グラフの様々な構造バイアスをランダムグラフを用いてデバイアスするグラフ埋め込み法であるRess2vecを提案する。 この偏りがリンク予測やクラスタリング性能を改善するだけでなく、グラフ埋め込みにおける健全な構造特性を明示的にモデル化できることを実証する。
  論文  参考訳（メタデータ） (2021-10-14T18:24:11Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  本稿では,グラフ構造形成の暗黙的モデルを学ぶエンドツーエンドフレームワークを提案し,その基盤となる最適化機構を明らかにする。 学習した目的は、観測されたグラフプロパティの説明として機能し、ドメイン内の異なるグラフを渡すために自分自身を貸すことができる。 GraphOptは、グラフ内のリンク生成をシーケンシャルな意思決定プロセスとして、最大エントロピー逆強化学習アルゴリズムを用いて解決する。
  論文  参考訳（メタデータ） (2020-07-07T16:51:39Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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