論文の概要: Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling

• arxiv url: http://arxiv.org/abs/2111.09696v1
• Date: Mon, 15 Nov 2021 12:16:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-19 14:41:58.707597
• Title: Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling
• Title（参考訳）: simplex embedded and sampling を用いた点集合登録問題としてのキャスティンググラフ同型
• Authors: Yigit Oktar
• Abstract要約: グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。 それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。 等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph isomorphism is an important problem as its worst-case time complexity is not yet fully understood. In this study, we try to draw parallels between a related optimization problem called point set registration. A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. Given two graphs, the isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. In the case of non-isomorphism, the point set form optimization result can be used as a distance measure between two graphs having the same number of vertices and edges. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem and an orthogonal transformation invariant feature extraction based on this high dimensional point set representation may be fruitful. The concepts presented can also be extended to automorphism, and subgraph isomorphism problems and can also be applied on hypergraphs with certain modifications.
• Abstract（参考訳）: グラフ同型は、最悪の時間の複雑さがまだ完全に理解されていないため、重要な問題である。 本研究では,関連する最適化問題である点集合登録の並列化を試みる。 グラフは、単純な埋め込みとサンプリングを用いて十分な次元の点集合として表現できる。 2つのグラフが与えられたとき、それらの同型はグラフの点集合形式の間の完全登録の存在に対応する。 非同型の場合、点集合形式最適化の結果は、同じ頂点数と辺数を持つ2つのグラフ間の距離測度として使うことができる。 等値クラスの関連する考えは、グラフの正準化はグラフ同型問題に取り組む上で重要なツールであり、この高次元の点集合表現に基づく直交変換不変な特徴抽出は実数であることを示している。 与えられた概念は自己同型や部分グラフ同型問題にも拡張でき、ある種の修正のある超グラフにも適用できる。

関連論文リスト

• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Harnessing spectral representations for subgraph alignment [15.86857474914914]
  本稿では,コンパクトで計算が容易で,トポロジ的変化に頑健で,既存のパイプラインに差し込むのが容易で,特に部分グラフアライメント問題に有効である地図のスペクトル表現を提案する。 サブグラフアライメントタスクで生じる部分性がマップ係数の特別な構造として表される驚くべき現象を初めて報告する。
  論文  参考訳（メタデータ） (2022-05-30T09:03:28Z)
• Scaling up graph homomorphism for classification via sampling [1.662966122370634]
  グラフ準同型密度特徴を準同型数に対するスケーラブルな代替として使用することを検討する。 準同型密度の加法近似を計算する単純なサンプリングアルゴリズムの高性能な実装を提案する。
  論文  参考訳（メタデータ） (2021-04-08T20:25:37Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  我々は、よく知られたNPハードグラフ同型問題の平均ケースとノイズバージョンを示す。 相関式 Erd"os-R'enyi モデルでは、スパース状態における部分的回復の不可能な結果が証明される。 我々の境界はノイズのない場合(グラフ同型問題)において厳密であり、まだノイズに密接であると予想する。
  論文  参考訳（メタデータ） (2021-02-04T15:26:48Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  スペクトルグラフ理論は、これらのグラフを低次元空間にマッピングし、それらの埋め込みを整列させることで形状と一致させることができる。 我々は、ラプラシア行列の固有関数の最適部分集合を選択することによって、2つの同値な$K$-次元の点集合の最良の整合を求める新しい定式化を導出する。
  論文  参考訳（メタデータ） (2020-12-14T08:49:25Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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