論文の概要: On statistical learning of graphs

• arxiv url: http://arxiv.org/abs/2507.13054v1
• Date: Thu, 17 Jul 2025 12:26:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-18 20:10:24.486918
• Title: On statistical learning of graphs
• Title（参考訳）: グラフの統計的学習について
• Authors: Vittorio Cipriani, Valentino Delle Rose, Luca San Mauro, Giovanni Solda,
• Abstract要約: 数え切れない無限グラフGのコピーによって形成された仮説クラスのPACとオンライン学習可能性について検討する。 本結果から, 有限対応コピーのPAC学習性は, G の完全同型型のオンライン学習性を意味することが示された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing its structure and label set. We consider classes where permutations move only finitely many vertices. Our main result shows that PAC learnability of all such finite-support copies implies online learnability of the full isomorphism type of G, and is equivalent to the condition of automorphic triviality. We also characterize graphs where copies induced by swapping two vertices are not learnable, using a relaxation of the extension property of the infinite random graph. Finally, we show that, for all G and k>2, learnability for k-vertex permutations is equivalent to that for 2-vertex permutations, yielding a four-class partition of infinite graphs, whose complexity we also determine using tools coming from both descriptive set theory and computability theory.
• Abstract（参考訳）: 無限個のグラフ G のコピーによって生成される仮説クラスのPACとオンライン学習可能性について検討し、各コピーは G の頂点を置換することによって誘導される。 これはグラフのラベリングを学習し、その構造とラベリングセットを知ることに対応する。 置換が有限個の頂点だけを移動するクラスを考える。 本研究の主な成果は, 有限対応コピーのPAC学習性は, G の完全同型型のオンライン学習性を示し, 自己同型自明性の条件と等価であることを示す。 また、無限ランダムグラフの拡張特性の緩和を利用して、2つの頂点を交換することによって引き起こされるコピーを学習できないグラフを特徴付ける。 最後に、すべての G と k>2 に対し、k-頂点置換の学習性は 2-頂点置換の学習性と同値であり、無限グラフの4階分割を生じる。

関連論文リスト

• Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks [23.01521187724899]
  ホモモルフィズムは、その構造を保存するグラフの間のキーマッピング技術である。 グラフ準同型のための最初のグラフニューラルネットワークフレームワークであるHFrameを提案する。 HFrameは正確なマッチングアルゴリズムよりも最大101.91倍高速で、平均精度は0.962である。
  論文  参考訳（メタデータ） (2025-07-27T11:10:15Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Graph Contrastive Learning with Personalized Augmentation [17.714437631216516]
  グラフの教師なし表現を学習するための有効なツールとして,グラフコントラスト学習(GCL)が登場した。 我々は、textitPersonalized textitAugmentation (GPA) を用いたtextitGraph コントラスト学習と呼ばれる原則付きフレームワークを提案する。 GPAは、学習可能な拡張セレクタを介して、そのトポロジとノード属性に基づいて、各グラフの調整された拡張戦略を推論する。
  論文  参考訳（メタデータ） (2022-09-14T11:37:48Z)
• Quantum isomorphism of graphs from association schemes [0.0]
  同じ数の頂点上の任意の2つのアダマールグラフが量子同型であることを示す。 これは、ある関連スキームから生じるグラフの量子同型を示すより一般的なレシピから従う。
  論文  参考訳（メタデータ） (2022-09-10T03:22:28Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  本稿では,幾何学コントラスト学習(Geometry Contrastive Learning, GCL)と呼ばれる,新しい自己指導型学習手法を提案する。 GCLはユークリッドと双曲的な視点からヘテロジニアスグラフを同時に見ることができ、リッチな意味論と複雑な構造をモデル化する能力の強い融合を目指している。 4つのベンチマークデータセットの大規模な実験は、提案手法が強いベースラインよりも優れていることを示している。
  論文  参考訳（メタデータ） (2022-06-25T03:54:53Z)
• A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
  グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。 本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。 データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
  論文  参考訳（メタデータ） (2022-06-23T17:28:55Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  グラフオートエンコーダ(GAE)は、グラフ埋め込みのための表現学習において強力なツールである。 本稿では,2つの新しい教師なしグラフ埋め込み法,適応グラフ学習(BAGE)による教師なしグラフ埋め込み,変分適応グラフ学習(VBAGE)による教師なしグラフ埋め込みを提案する。 いくつかのデータセットに関する実験的研究により、我々の手法がノードクラスタリング、ノード分類、グラフ可視化タスクにおいて、ベースラインよりも優れていることが実証された。
  論文  参考訳（メタデータ） (2020-03-10T02:33:14Z)

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

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