論文の概要: Weisfeiler-Lehman meets Gromov-Wasserstein

• arxiv url: http://arxiv.org/abs/2202.02495v1
• Date: Sat, 5 Feb 2022 05:53:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-08 17:47:00.936723
• Title: Weisfeiler-Lehman meets Gromov-Wasserstein
• Title（参考訳）: Weisfeiler-Lehman、Gromov-Wassersteinと出会う
• Authors: Samantha Chen, Sunhyuk Lim, Facundo M\'emoli, Zhengchao Wan, Yusu Wang
• Abstract要約: ラベル付きマルコフ連鎖間の距離の概念であるWeisfeiler-Lehman距離を提案する。 WL距離は時間計算可能であり、WLテストとも互換性がある。 LMMC上のニューラルネットワークアーキテクチャを同定し、連続関数の普遍的なw.r.t.連続関数であることが判明した。
• 参考スコア（独自算出の注目度）: 8.142448470345762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we propose the Weisfeiler-Lehman (WL) distance, a notion of distance between labeled measure Markov chains (LMMCs), of which labeled graphs are special cases. The WL distance is polynomial time computable and is also compatible with the WL test in the sense that the former is positive if and only if the WL test can distinguish the two involved graphs. The WL distance captures and compares subtle structures of the underlying LMMCs and, as a consequence of this, it is more discriminating than the distance between graphs used for defining the state-of-the-art Wasserstein Weisfeiler-Lehman graph kernel. Inspired by the structure of the WL distance we identify a neural network architecture on LMMCs which turns out to be universal w.r.t. continuous functions defined on the space of all LMMCs (which includes all graphs) endowed with the WL distance. Finally, the WL distance turns out to be stable w.r.t. a natural variant of the Gromov-Wasserstein (GW) distance for comparing metric Markov chains that we identify. Hence, the WL distance can also be construed as a polynomial time lower bound for the GW distance which is in general NP-hard to compute.
• Abstract（参考訳）: weisfeiler-lehman (wl) テストはグラフ同型テストの古典的な手順である。 wlテストはまた、グラフカーネルの設計とグラフニューラルネットワークの解析の両方に広く使われている。 本稿では,ラベル付きグラフが特別な場合であるラベル付き測度マルコフ鎖(lmmcs)間の距離の概念であるweisfeiler-lehman(wl)距離を提案する。 WL 距離は多項式時間計算可能であり、前者が正であることと WL テストが関連する2つのグラフを区別できる場合に限り、WL テストと互換性がある。 wl距離は基礎となるlmmcの微妙な構造を捉えて比較し、その結果、最先端のwasserstein weisfeiler-lehmanグラフカーネルを定義するのに使用されるグラフ間の距離よりも識別性が高い。 WL距離の構造に着想を得て、WL距離が与えられたすべてのLMMC(全グラフを含む)の空間上で定義される普遍的なw.r.t.連続関数である、LMMC上のニューラルネットワークアーキテクチャを同定する。 最後に、WL 距離は安定であることが判明し、Gromov-Wasserstein (GW) 距離の自然な変種は、私たちが同定した計量マルコフ連鎖を比較するためのものである。 したがって、WL 距離は一般の NP-ハードである GW 距離の多項式時間下界として解釈することもできる。

関連論文リスト

• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。 ベンチマークに基づく表現力の拡張的定義と測定について論じる。
  論文  参考訳（メタデータ） (2023-07-11T20:06:12Z)
• Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points [58.9648095506484]
  Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。 我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサフィスを3回だけ繰り返すことである。
  論文  参考訳（メタデータ） (2023-03-22T18:23:24Z)
• Distances for Markov Chains, and Their Differentiation [6.534615862914506]
  ノード属性を持つ有向グラフを持つマルコフ連鎖の距離を生成する統一的なフレームワークを提案する。 割引されたWL距離は理論的性質に優れており,既存のOTCおよびWL距離のいくつかの制限に対処できることを示す。
  論文  参考訳（メタデータ） (2023-02-16T23:14:40Z)
• The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs [6.359018583826099]
  Wesfeiler-Lehman (WL) 距離の新たな解釈を陳らによって紹介する(2022年)。 WL距離はグラフとノードの特徴を比較することを目的としており、古典的なWeisfeiler-Lehmanグラフ同型テストと同じ離散パワーを持ち、グロモフ-ワッサーシュタイン距離と深い関係を持つ。
  論文  参考訳（メタデータ） (2023-02-01T19:13:27Z)
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations [26.77596449192451]
  グラフニューラルネットワーク(GNN)は、グラフ上の機械学習問題を解決するための有望なツールとして登場した。 本論文では,Weisfeiler-Leman(WL)アルゴリズムによって生成される階層に基づいて,ノード間の距離関数を定義する。 本稿では,ノード間の距離を保存する表現を学習するモデルを提案する。
  論文  参考訳（メタデータ） (2022-11-04T15:03:41Z)
• Wasserstein Graph Distance Based on $L_1$-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees [17.855077077275567]
  Weisfeiler-Lehman (WL) テストはグラフ機械学習において広く使われているアルゴリズムである。 この問題に対処するために,WWLS(Wasserstein WL Subtree)距離と呼ばれる新しいグラフ測度を提案する。 提案したWWLS距離は,計量検証およびグラフ分類実験において,ベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-07-09T07:45:16Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  グラフニューラルネットワーク(GNN)のリンク予測 リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。 テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
  論文  参考訳（メタデータ） (2022-06-20T04:50:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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