論文の概要: Wasserstein Graph Distance based on $L_1$-Approximated Tree Edit
Distance between Weisfeiler-Lehman Subtrees
- arxiv url: http://arxiv.org/abs/2207.04216v1
- Date: Sat, 9 Jul 2022 07:45:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-12 13:35:20.806387
- 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)距離と呼ぶ計量を定義する。
WWLSは従来のメトリクスでは難しい構造の変化を捉えることができる。
- 参考スコア（独自算出の注目度）: 17.855077077275567
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Weisfeiler-Lehman (WL) test has been widely applied to graph kernels,
metrics, and neural networks. However, it considers only the graph consistency,
resulting in the weak descriptive power of structural information. Thus, it
limits the performance improvement of applied methods. In addition, the
similarity and distance between graphs defined by the WL test are in coarse
measurements. To the best of our knowledge, this paper clarifies these facts
for the first time and defines a metric we call the Wasserstein WL subtree
(WWLS) distance. We introduce the WL subtree as the structural information in
the neighborhood of nodes and assign it to each node. Then we define a new
graph embedding space based on $L_1$-approximated tree edit distance
($L_1$-TED): the $L_1$ norm of the difference between node feature vectors on
the space is the $L_1$-TED between these nodes. We further propose a fast
algorithm for graph embedding. Finally, we use the Wasserstein distance to
reflect the $L_1$-TED to the graph level. The WWLS can capture small changes in
structure that are difficult with traditional metrics. We demonstrate its
performance in several graph classification and metric validation experiments.
- Abstract（参考訳）: Weisfeiler-Lehman(WL)テストは、グラフカーネル、メトリクス、ニューラルネットワークに広く適用されている。
しかし、グラフの一貫性のみを考慮し、構造情報の弱い記述力をもたらす。
これにより,適用手法の性能向上が制限される。
さらに、WLテストで定義されるグラフ間の類似性と距離は粗い測定である。
我々の知る限り、この論文はこれらの事実を初めて明らかにし、ワッサーシュタインWL部分木(WWLS)距離と呼ばれる計量を定義する。
我々は,ノード近傍の構造情報としてwlサブツリーを導入し,各ノードに割り当てる。
次に、新しいグラフ埋め込み空間を$L_1$-approximated tree edit distance (L_1$-TED): $L_1$ 空間上のノード特徴ベクトル間の差のノルムは、これらのノード間の$L_1$-TEDである。
さらに,グラフ埋め込みのための高速アルゴリズムを提案する。
最後に、ワッサーシュタイン距離を用いて、$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。