論文の概要: Structural Node Embeddings with Homomorphism Counts

• arxiv url: http://arxiv.org/abs/2308.15283v2
• Date: Mon, 20 Nov 2023 15:03:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-22 18:06:55.570685
• Title: Structural Node Embeddings with Homomorphism Counts
• Title（参考訳）: 準同型数を持つ構造ノード埋め込み
• Authors: Hinrikus Wolf, Luca Oeljeklaus, Pascal K\"uhner, Martin Grohe
• Abstract要約: 準同型は局所構造情報を捉えます 準同型数に基づくノード埋め込みの有効性を実験的に示す。 本手法は,有界木幅グラフクラスに対するグラフ準同型カウントの効率的な計算可能性に着目している。
• 参考スコア（独自算出の注目度）: 2.0131144893314232
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph homomorphism counts, first explored by Lov\'asz in 1967, have recently garnered interest as a powerful tool in graph-based machine learning. Grohe (PODS 2020) proposed the theoretical foundations for using homomorphism counts in machine learning on graph level as well as node level tasks. By their very nature, these capture local structural information, which enables the creation of robust structural embeddings. While a first approach for graph level tasks has been made by Nguyen and Maehara (ICML 2020), we experimentally show the effectiveness of homomorphism count based node embeddings. Enriched with node labels, node weights, and edge weights, these offer an interpretable representation of graph data, allowing for enhanced explainability of machine learning models. We propose a theoretical framework for isomorphism-invariant homomorphism count based embeddings which lend themselves to a wide variety of downstream tasks. Our approach capitalises on the efficient computability of graph homomorphism counts for bounded treewidth graph classes, rendering it a practical solution for real-world applications. We demonstrate their expressivity through experiments on benchmark datasets. Although our results do not match the accuracy of state-of-the-art neural architectures, they are comparable to other advanced graph learning models. Remarkably, our approach demarcates itself by ensuring explainability for each individual feature. By integrating interpretable machine learning algorithms like SVMs or Random Forests, we establish a seamless, end-to-end explainable pipeline. Our study contributes to the advancement of graph-based techniques that offer both performance and interpretability.
• Abstract（参考訳）: 1967年にLov\'aszによって初めて発見されたグラフ準同型数は、グラフベースの機械学習において強力なツールとして関心を集めている。 grohe (pods 2020) はグラフレベルの機械学習やノードレベルのタスクで準同型数を使用するための理論的基礎を提案した。 その性質上、局所的な構造情報を取り込み、堅牢な構造埋め込みを作成することができる。 グラフレベルのタスクに対する最初のアプローチは、Nguyen と Maehara (ICML 2020) によるものであるが、同型数に基づくノード埋め込みの有効性を実験的に示す。 ノードラベル、ノードウェイト、エッジウェイトに富んだこれらは、グラフデータの解釈可能な表現を提供し、機械学習モデルの説明可能性を高める。 本稿では, 様々な下流タスクに適した準同型不変準同型数に基づく埋め込みに関する理論的枠組みを提案する。 本手法は有界木幅グラフクラスに対するグラフ準同型カウントの効率的な計算可能性に基いて,実世界のアプリケーションのための実用的なソリューションとなる。 ベンチマークデータセットで実験を行い,その表現性を示す。 我々の結果は最先端のニューラルネットワークアーキテクチャの精度に合わないが、他の高度なグラフ学習モデルに匹敵する。 注目すべきは、各機能の説明可能性を保証することで、我々のアプローチは相違することです。 SVMやRandom Forestsのような解釈可能な機械学習アルゴリズムを統合することで、シームレスでエンドツーエンドで説明可能なパイプラインを構築します。 本研究は,性能と解釈可能性の両方を提供するグラフベースの技術の発展に寄与する。

関連論文リスト

• Isomorphic-Consistent Variational Graph Auto-Encoders for Multi-Level Graph Representation Learning [9.039193854524763]
  本稿では,タスク非依存グラフ表現学習のためのアイソモルフィック-一貫性VGAE(IsoC-VGAE)を提案する。 まず、同型整合性を維持する理論的保証を提供するための復号法を考案する。 次に,逆グラフニューラルネットワーク(Inv-GNN)デコーダを直感的な実現法として提案する。
  論文  参考訳（メタデータ） (2023-12-09T10:16:53Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。 この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。 我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-05-31T11:04:53Z)
• A Multi-scale Graph Signature for Persistence Diagrams based on Return Probabilities of Random Walks [1.745838188269503]
  トポロジ的特徴のロバスト性を高めるために,マルチスケールグラフシグネチャ群の利用について検討する。 このセット入力を処理するためのディープラーニングアーキテクチャを提案する。 ベンチマークグラフ分類データセットの実験により,提案したアーキテクチャは,他の永続的ホモロジーに基づく手法よりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-09-28T17:30:27Z)
• Graph Self-supervised Learning with Accurate Discrepancy Learning [64.69095775258164]
  離散性に基づく自己監督型LeArning(D-SLA)と呼ばれる原図と摂動グラフの正確な相違を学習することを目的としたフレームワークを提案する。 本稿では,分子特性予測,タンパク質機能予測,リンク予測タスクなど,グラフ関連下流タスクにおける本手法の有効性を検証する。
  論文  参考訳（メタデータ） (2022-02-07T08:04:59Z)
• Graph Kernel Neural Networks [53.91024360329517]
  本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。 これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。 私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
  論文  参考訳（メタデータ） (2021-12-14T14:48:08Z)
• Learning to Learn Graph Topologies [27.782971146122218]
  ノードデータからグラフ構造へのマッピングを学習する(L2O)。 このモデルは、ノードデータとグラフサンプルのペアを使ってエンドツーエンドでトレーニングされる。 合成データと実世界のデータの両方の実験により、我々のモデルは、特定のトポロジ特性を持つグラフを学習する際の古典的反復アルゴリズムよりも効率的であることが示された。
  論文  参考訳（メタデータ） (2021-10-19T08:42:38Z)
• Multi-Level Graph Contrastive Learning [38.022118893733804]
  本稿では,グラフの空間ビューを対比することで,グラフデータの堅牢な表現を学習するためのマルチレベルグラフコントラスト学習(MLGCL)フレームワークを提案する。 元のグラフは1次近似構造であり、不確実性や誤りを含むが、符号化機能によって生成された$k$NNグラフは高次近接性を保持する。 MLGCLは、7つのデータセット上の既存の最先端グラフ表現学習法と比較して有望な結果が得られることを示す。
  論文  参考訳（メタデータ） (2021-07-06T14:24:43Z)
• Self-supervised Graph-level Representation Learning with Local and Global Structure [71.45196938842608]
  自己教師付き全グラフ表現学習のためのローカル・インスタンスとグローバル・セマンティック・ラーニング(GraphLoG)という統合フレームワークを提案する。 GraphLoGは、局所的な類似点の保存に加えて、グローバルなセマンティッククラスタをキャプチャする階層的なプロトタイプも導入している。 モデル学習のための効率的なオンライン予測最大化(EM)アルゴリズムがさらに開発された。
  論文  参考訳（メタデータ） (2021-06-08T05:25:38Z)
• GraphSVX: Shapley Value Explanations for Graph Neural Networks [81.83769974301995]
  グラフニューラルネットワーク(GNN)は、幾何データに基づく様々な学習タスクにおいて大きな性能を発揮する。 本稿では,既存のGNN解説者の多くが満足する統一フレームワークを提案する。 GNN用に特別に設計されたポストホックローカルモデル非依存説明法であるGraphSVXを紹介します。
  論文  参考訳（メタデータ） (2021-04-18T10:40:37Z)
• Scaling up graph homomorphism for classification via sampling [1.662966122370634]
  グラフ準同型密度特徴を準同型数に対するスケーラブルな代替として使用することを検討する。 準同型密度の加法近似を計算する単純なサンプリングアルゴリズムの高性能な実装を提案する。
  論文  参考訳（メタデータ） (2021-04-08T20:25:37Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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