論文の概要: On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
- arxiv url: http://arxiv.org/abs/2309.17053v3
- Date: Thu, 28 Mar 2024 11:00:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-29 21:43:17.474771
- Title: On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
- Title（参考訳）: グラフモチーフパラメータに対するWeisfeiler-Lemanテストのパワーについて
- Authors: Matthias Lanzinger, Pablo Barceló,
- Abstract要約: k$次元Weisfeiler-Leman(k$WL)テストは、グラフ同型を検証するための広く認識されている方法である。
本稿では,ラベル付きグラフモチーフパラメータのWL次元を正確に評価する。
- 参考スコア（独自算出の注目度）: 9.599347633285637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the $k$-dimensional Weisfeiler-Leman ($k$WL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the $k$WL test. A central focus of research in this field revolves around determining the least dimensionality $k$, for which $k$WL can discern graphs with different number of occurrences of a pattern graph $P$. We refer to such a least $k$ as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern $P$. We additionally demonstrate that in cases where the $k$WL test distinguishes between graphs with varying occurrences of a pattern $P$, the exact number of occurrences of $P$ can be computed uniformly using only local information of the last layer of a corresponding GNN. We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern $P$, answering an open question from previous work.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)の分野におけるセミナル研究は、GNNの表現能力と、グラフ同型を検証する広く認められた方法である$k$-dimensional Weisfeiler-Leman(k$WL)テストとの直接的な対応を明らかにした。
この接続は、$k$WL テストによって事実上識別可能な特定のグラフ特性を解釈することに関心を再燃させた。
この分野での研究の中心は、最小次元$k$を決定することであり、$k$WLはパターングラフ$P$の異なる回数のグラフを識別することができる。
我々は、このパターンカウント問題のWL次元として、少なくとも$k$を参照する。
この調査は伝統的に、サブグラフカウントとインダクションされたサブグラフカウントというパターンに関連する2つの異なるカウント問題に分類する。
興味深いことに、一見異なるアプローチで別の課題として最初に現れたにもかかわらず、これらの問題はどちらもより包括的な問題のコンポーネントであるグラフモチーフパラメータ(graph motif parameters)の相互接続である。
本稿では,ラベル付きグラフモチーフパラメータのWL次元を正確に評価する。
この結果の具体例として、各ラベル付きパターンに対して、サブグラフカウントのWL次元と誘導サブグラフカウントの問題を特徴づける。
さらに、$k$WLテストがパターン$P$の異なるグラフを区別する場合、対応するGNNの最後のレイヤのローカル情報のみを用いて、$P$の正確な回数を計算可能であることを示す。
最終的に、様々なグラフパラメータのWL次元を認識するという課題を掘り下げる。
与えられたパターン$P$に対する部分グラフカウント問題のWL次元を決定する多項式時間アルゴリズムを,以前の研究からオープンな質問に答える。
関連論文リスト
- Towards Self-Interpretable Graph-Level Anomaly Detection [73.1152604947837]
グラフレベルの異常検出(GLAD)は、コレクションの大多数と比べて顕著な相違を示すグラフを識別することを目的としている。
本稿では,異常なグラフを検出し,同時に情報的説明を生成する自己解釈グラフaNomaly dETectionモデル(SIGNET)を提案する。
論文 参考訳（メタデータ） (2023-10-25T10:10:07Z) - Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。
連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。
また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T14:12:23Z) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
論文 参考訳（メタデータ） (2023-02-13T22:09:02Z) - Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
グラフ上の部分グラフ同型カウントは重要な問題である。
本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
論文 参考訳（メタデータ） (2023-02-07T05:32:11Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。
ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。
合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
論文 参考訳（メタデータ） (2023-01-07T05:14:45Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Interactive Visual Pattern Search on Graph Data via Graph Representation
Learning [20.795511688640296]
視覚分析システムGraphQは、ループ内、サンプルベース、サブグラフパターン検索をサポートする。
高速で対話的なクエリをサポートするために、グラフニューラルネットワーク(GNN)を使用して、グラフを固定長潜在ベクトル表現としてエンコードする。
また,NuroAlignと呼ばれるノードアライメントのための新しいGNNを提案し,クエリ結果の検証と解釈を容易にする。
論文 参考訳（メタデータ） (2022-02-18T22:30:28Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。