論文の概要: Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective

• arxiv url: http://arxiv.org/abs/2410.03517v1
• Date: Fri, 4 Oct 2024 15:36:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 21:50:00.676817
• Title: Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective
• Title（参考訳）: Weisfeiler-Lemanの微粒化表現力--準同型数論の観点から
• Authors: Junru Zhou, Muhan Zhang,
• Abstract要約: グラフニューラルネットワークの任意のクラス(GNN)の準同型カウント能力を決定するための理論的枠組みを提供する。 検討されている設計空間は、既知の強力なGNNのほとんどすべてに対応するのに十分の大きさであるので、我々の結果は既存のすべての作業を大幅に拡張し、GNNモデル設計の自動化にその応用を見出すことができるかもしれない。
• 参考スコア（独自算出の注目度）: 24.729126775414922
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several existing works have investigated the homomorphism counting power of certain GNN families, a simple and unified framework for analyzing the problem is absent. In this paper, we first propose \emph{generalized folklore Weisfeiler-Leman (GFWL)} algorithms as a flexible design basis for expressive GNNs, and then provide a theoretical framework to algorithmically determine the homomorphism counting power of an arbitrary class of GNN within the GFWL design space. As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)が準同型を数える能力は、最近、その表現力の実用的できめ細かい尺度として提案されている。 いくつかの既存の研究で特定のGNNファミリーの準同型カウント能力について研究されているが、その問題を解析するためのシンプルで統一的な枠組みは欠如している。 本稿では,まず,表現型GNNのフレキシブルな設計基盤として \emph{ Generalized folklore Weisfeiler-Leman (GFWL) アルゴリズムを提案する。 検討されている設計空間は、既知の強力なGNNのほとんどすべてに対応するのに十分の大きさであるので、我々の結果は既存のすべての作業を大幅に拡張し、GNNモデル設計の自動化にその応用を見出すことができるかもしれない。

関連論文リスト

• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。 また, 満足度問題はPSPACE完全であることを示す。
  論文  参考訳（メタデータ） (2024-04-30T21:16:38Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。 ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。 本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
  論文  参考訳（メタデータ） (2024-01-16T17:23:23Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• MGNN: Graph Neural Networks Inspired by Distance Geometry Problem [28.789684784093048]
  グラフニューラルネットワーク(GNN)は、機械学習分野における顕著な研究トピックとして現れている。 本稿では,GNNの分類段階における分類器の親近性に着想を得たGNNモデルを提案する。 合成および実世界の両方のデータセットを用いて実験を行い,本モデルの有効性を広範囲に評価した。
  論文  参考訳（メタデータ） (2022-01-31T04:15:42Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 既存のGNNモデルの多くは浅く、本質的に機能中心である。 我々は,既存の浅いGNNがグラフ構造をよく保存できないことを経験的かつ解析的に示す。 本稿では,グラフ構造保存におけるGNNの能力を高めるプラグインモジュールであるEigen-GNNを提案する。
  論文  参考訳（メタデータ） (2020-06-08T02:47:38Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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