論文の概要: Wasserstein Graph Distance Based on $L_1$-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees

• arxiv url: http://arxiv.org/abs/2207.04216v2
• Date: Mon, 1 May 2023 06:22:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-02 19:47:53.109467
• Title: Wasserstein Graph Distance Based on $L_1$-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees
• Title（参考訳）: Weisfeiler-Lehmanサブツリー間の$L_1$-近似木編集距離に基づくWassersteinグラフ距離
• Authors: Zhongxi Fang, Jianming Huang, Xun Su, Hiroyuki Kasai
• Abstract要約: Weisfeiler-Lehman (WL) テストはグラフ機械学習において広く使われているアルゴリズムである。 この問題に対処するために,WWLS(Wasserstein WL Subtree)距離と呼ばれる新しいグラフ測度を提案する。 提案したWWLS距離は,計量検証およびグラフ分類実験において,ベースラインよりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 17.855077077275567
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Weisfeiler-Lehman (WL) test is a widely used algorithm in graph machine learning, including graph kernels, graph metrics, and graph neural networks. However, it focuses only on the consistency of the graph, which means that it is unable to detect slight structural differences. Consequently, this limits its ability to capture structural information, which also limits the performance of existing models that rely on the WL test. This limitation is particularly severe for traditional metrics defined by the WL test, which cannot precisely capture slight structural differences. In this paper, we propose a novel graph metric called the Wasserstein WL Subtree (WWLS) distance to address this problem. Our approach leverages the WL subtree as structural information for node neighborhoods and defines node metrics using the $L_1$-approximated tree edit distance ($L_1$-TED) between WL subtrees of nodes. Subsequently, we combine the Wasserstein distance and the $L_1$-TED to define the WWLS distance, which can capture slight structural differences that may be difficult to detect using conventional metrics. We demonstrate that the proposed WWLS distance outperforms baselines in both metric validation and graph classification experiments.
• Abstract（参考訳）: Weisfeiler-Lehmanテスト(WL)は、グラフカーネル、グラフメトリクス、グラフニューラルネットワークなど、グラフ機械学習で広く使用されているアルゴリズムである。 しかし、グラフの一貫性だけに焦点を当てており、わずかな構造的差異を検出できないことを意味する。 これにより、構造情報をキャプチャする能力が制限され、WLテストに依存する既存のモデルの性能も制限される。 この制限は、WLテストによって定義される伝統的なメトリクスでは特に深刻であり、わずかに構造的な違いを正確に捉えることはできない。 本稿では,WWLS(Wasserstein WL Subtree)距離と呼ばれる新しいグラフ計量を提案し,この問題に対処する。 提案手法では,WLサブツリーをノード近傍の構造情報として利用し,ノードのWLサブツリー間の木編集距離(L_1$-TED)を用いてノードメトリクスを定義する。 その後、WWLS距離を定義するためにワッサースタイン距離と$L_1$-TEDを組み合わせ、従来の測定値を用いて検出することが難しいわずかな構造差を捉えることができる。 提案したWWLS距離は,計量検証およびグラフ分類実験において,ベースラインよりも優れていることを示す。

関連論文リスト

• On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters [9.599347633285637]
  k$次元Weisfeiler-Leman(k$WL)テストは、グラフ同型を検証するための広く認識されている方法である。 本稿では,ラベル付きグラフモチーフパラメータのWL次元を正確に評価する。
  論文  参考訳（メタデータ） (2023-09-29T08:26:44Z)
• 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)
• On a linear fused Gromov-Wasserstein distance for graph structured data [2.360534864805446]
  埋め込み間のユークリッド距離として定義される2つのグラフ間の新しい距離である線形FGWを提案する。 提案した距離の利点は2つある: 1) ノードの特徴とグラフの構造を考慮して、カーネルベースのフレームワークにおけるグラフ間の類似性を測定する。
  論文  参考訳（メタデータ） (2022-03-09T13:43:18Z)
• SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
  グラフマッチングの精度、構造的不整合(SI)を測定するための新しい基準を提案する。 具体的には、SIは、グラフのマルチホップ構造に対応するために熱拡散ウェーブレットを組み込む。 ミラー降下法を用いて,新しいK-ホップ構造に基づくマッチングコストでGromov-Wasserstein距離を解くことにより,SIGMAを導出可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-06T15:18:37Z)
• Weisfeiler-Lehman meets Gromov-Wasserstein [8.142448470345762]
  ラベル付きマルコフ連鎖間の距離の概念であるWeisfeiler-Lehman距離を提案する。 WL距離は時間計算可能であり、WLテストとも互換性がある。 LMMC上のニューラルネットワークアーキテクチャを同定し、連続関数の普遍的なw.r.t.連続関数であることが判明した。
  論文  参考訳（メタデータ） (2022-02-05T05:53:31Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。 我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
  論文  参考訳（メタデータ） (2021-10-27T10:45:21Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• node2coords: Graph Representation Learning with Wasserstein Barycenters [59.07120857271367]
  グラフの表現学習アルゴリズムである node2coords を導入する。 低次元空間を同時に学習し、その空間内のノードを座標する。 実験の結果,node2coordで学習した表現は解釈可能であることがわかった。
  論文  参考訳（メタデータ） (2020-07-31T13:14: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)

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

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