論文の概要: Fast, Accurate and Interpretable Graph Classification with Topological Kernels
- arxiv url: http://arxiv.org/abs/2509.17693v1
- Date: Mon, 22 Sep 2025 12:31:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-23 18:58:16.375531
- Title: Fast, Accurate and Interpretable Graph Classification with Topological Kernels
- Title（参考訳）: トポロジカルカーネルを用いた高速・高精度・解釈可能なグラフ分類
- Authors: Adam Wesołowski, Ronin Wu, Karim Essafi,
- Abstract要約: コンパクトな特徴ベクトルにより各グラフを表すトポロジ的指標に基づく明示的特徴写像のクラスを導入する。
これらのコンパクトベクトル上の放射基底関数カーネルを用いて、グラフ間の類似性の尺度を定義する。
標準分子データセットの評価を行い, 単一トポロジカル・インデックス特徴ベクトルによる分類精度の低下を観測した。
- 参考スコア（独自算出の注目度）: 0.04588028371034406
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We introduce a novel class of explicit feature maps based on topological indices that represent each graph by a compact feature vector, enabling fast and interpretable graph classification. Using radial basis function kernels on these compact vectors, we define a measure of similarity between graphs. We perform evaluation on standard molecular datasets and observe that classification accuracies based on single topological-index feature vectors underperform compared to state-of-the-art substructure-based kernels. However, we achieve significantly faster Gram matrix evaluation -- up to $20\times$ faster -- compared to the Weisfeiler--Lehman subtree kernel. To enhance performance, we propose two extensions: 1) concatenating multiple topological indices into an \emph{Extended Feature Vector} (EFV), and 2) \emph{Linear Combination of Topological Kernels} (LCTK) by linearly combining Radial Basis Function kernels computed on feature vectors of individual topological graph indices. These extensions deliver up to $12\%$ percent accuracy gains across all the molecular datasets. A complexity analysis highlights the potential for exponential quantum speedup for some of the vector components. Our results indicate that LCTK and EFV offer a favourable trade-off between accuracy and efficiency, making them strong candidates for practical graph learning applications.
- Abstract（参考訳）: 本稿では,各グラフをコンパクトな特徴ベクトルで表現し,高速かつ解釈可能なグラフ分類を可能にする,トポロジ的指標に基づく新しい特徴写像のクラスを導入する。
これらのコンパクトベクトル上の放射基底関数カーネルを用いて、グラフ間の類似性の尺度を定義する。
我々は,標準分子データセットの評価を行い,単一トポロジカル・インデックス特徴ベクトルに基づく分類精度が,最先端のサブストラクチャベースカーネルと比較して低いことを観察した。
しかし、Weisfeiler-Lehmanサブツリーカーネルと比較して、Gram行列の評価(最大20\times$ faster)が大幅に高速になる。
性能向上のために,我々は2つの拡張を提案する。
1)複数のトポロジカル指標を \emph{Extended Feature Vector} (EFV) に分解し、
2) 個々のトポロジカルグラフ指標の特徴ベクトル上で計算されたラジアル基底関数カーネルを線形に結合することにより, トポロジカルカーネルの固有結合(LCTK)を導出する。
これらの拡張によって、すべての分子データセットの精度が最大12.5%向上する。
複雑性解析は、ベクトル成分のいくつかに対する指数的量子スピードアップの可能性を強調している。
以上の結果から,LCTKとEFVは精度と効率のトレードオフを良好に実現し,実用的なグラフ学習アプリケーションへの強力な候補となることが示唆された。
関連論文リスト
- Metric Graph Kernels via the Tropical Torelli Map [0.0]
本稿では,熱帯代数幾何学を用いた計量グラフの研究を基礎とした新しいグラフカーネルを提案する。
我々のグラフカーネルは、基礎となる計量空間の幾何学と位相に基づいている。
経験的に、カーネルはラベルのない設定で既存のメソッドよりも優れています。
論文 参考訳（メタデータ） (2025-05-17T20:00:50Z) - Towards Subgraph Isomorphism Counting with Graph Kernels [45.687427850611314]
部分グラフ同型は#P完全 (#P-complete) と呼ばれ、正確な解を見つけるには指数時間を必要とする。
サブグラフ同型を数えることの可能性について先駆的に検討し、様々な変種を通してカーネル能力の増大を探求する。
本稿では,拡張グラフカーネルの有効性を実証する広範な実験結果について述べるとともに,今後の研究の方向性について述べる。
論文 参考訳（メタデータ） (2024-05-13T06:33:06Z) - AKBR: Learning Adaptive Kernel-based Representations for Graph Classification [43.87164777893224]
グラフ分類のための適応カーネルベース表現(AKBR)を学習するための新しいモデルを提案する。
提案手法は,グラフの適応型カーネル行列を構築するために,エンドツーエンドの表現学習モデルを定義することを目的としている。
実験結果から,提案したAKBRモデルは,標準グラフベンチマークにおいて,既存の最先端グラフカーネルやディープラーニング手法よりも優れていることがわかった。
論文 参考訳（メタデータ） (2024-03-24T13:01:05Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Graph Kernel Neural Networks [53.91024360329517]
本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。
これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。
私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
論文 参考訳（メタデータ） (2021-12-14T14:48:08Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-06-19T13:09:44Z) - An End-to-End Graph Convolutional Kernel Support Vector Machine [0.0]
グラフ分類のためのカーネルベースサポートベクターマシン(SVM)を提案する。
提案したモデルは、教師付きエンドツーエンドで訓練される。
実験結果から,提案モデルが既存のディープラーニングベースラインモデルよりも優れていることが示された。
論文 参考訳（メタデータ） (2020-02-29T09:57:42Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳（メタデータ） (2020-02-20T09:53:28Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z) - A Hierarchical Transitive-Aligned Graph Kernel for Un-attributed Graphs [11.51839867040302]
我々は、グラフ間の頂点を推移的に整列させることにより、新しいグラフカーネル、すなわち階層的推移型カーネルを開発する。
提案したカーネルは、分類精度の観点から、標準グラフベースのデータセット上で最先端のグラフカーネルより優れている。
論文 参考訳（メタデータ） (2020-02-08T11:46:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。