論文の概要: Self-Directed Learning of Convex Labelings on Graphs

• arxiv url: http://arxiv.org/abs/2409.01428v2
• Date: Wed, 12 Feb 2025 09:10:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-13 13:46:58.331845
• Title: Self-Directed Learning of Convex Labelings on Graphs
• Title（参考訳）: グラフ上の凸ラベルの自己指向学習
• Authors: Georgy Sokolov, Maximilian Thiessen, Margarita Akhmejanova, Fabio Vitale, Francesco Orabona,
• Abstract要約: 本研究では,自己指向型学習環境において,与えられたグラフのノードを分類する問題について検討する。 この学習設定はオンライン学習の変種であり、敵がノードのシーケンスを決定するのではなく、学習者が自律的にそれらを選択する。 自己指向ユークリッド半空間や一般の多クラス仮説クラスは検討されたが、グラフ上の自己指向ノード分類に関して、これまではいかなる結果も存在しなかった。
• 参考スコア（独自算出の注目度）: 11.286983359775512
• License:
• Abstract: We study the problem of classifying the nodes of a given graph in the self-directed learning setup. This learning setting is a variant of online learning, where rather than an adversary determining the sequence in which nodes are presented, the learner autonomously and adaptively selects them. While self-directed learning of Euclidean halfspaces, linear functions, and general multiclass hypothesis classes was recently considered, no results previously existed specifically for self-directed node classification on graphs. In this paper, we address this problem developing efficient algorithms for it. More specifically, we focus on the case of (geodesically) convex clusters, i.e., for every two nodes sharing the same label, all nodes on every shortest path between them also share the same label. In particular, we devise an algorithm with runtime polynomial in $n$ that makes only $3(h(G)+1)^4 \ln n$ mistakes on graphs with two convex clusters, where $n$ is the total number of nodes and $h(G)$ is the Hadwiger number, i.e., the size of the largest clique minor of the graph $G$. We also show that our algorithm is robust to the case that clusters are slightly non-convex, still achieving a mistake bound logarithmic in $n$. Finally, we devise a simple and efficient algorithm for homophilic clusters, where strongly connected nodes tend to belong to the same class.
• Abstract（参考訳）: 本研究では,自己指向型学習システムにおいて,与えられたグラフのノードを分類する問題について検討する。 この学習設定はオンライン学習の変種であり、ノードが提示される順序を決定する敵ではなく、学習者が自律的に適応的に選択する。 ユークリッド半空間、線形関数、および一般多クラス仮説クラスの自己指向学習は近年検討されているが、グラフ上の自己指向ノード分類に特有な結果はない。 本稿では,効率の良いアルゴリズムを開発するために,この問題に対処する。 より具体的には、同じラベルを共有する2つのノードのそれぞれに対して、最も短いパスのすべてのノードが同じラベルを共有する(geodesically)凸クラスタの場合に焦点を当てる。 特に、$n$で実行多項式を持つアルゴリズムを考案し、2つの凸クラスタを持つグラフに対して3(h(G)+1)^4 \ln n$ミスしか生じないが、$n$はノードの総数、$h(G)$はハドウィッガー数、すなわちグラフの最大のクリッドマイナーのサイズである。 また、我々のアルゴリズムはクラスタが少し非凸である場合にも頑健であることを示し、なおも$n$の誤り境界対数を達成した。 最後に、強い連結ノードが同じクラスに属する傾向にあるホモ親和性クラスタに対して、単純で効率的なアルゴリズムを考案する。

関連論文リスト

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。 観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。 さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-06-18T12:16:00Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Graph Construction using Principal Axis Trees for Simple Graph Convolution [0.6554326244334866]
  本稿では,教師なし情報と教師なし情報を用いて隣接行列$A$を構成するグラフ構築方式を提案する。 2つのよく知られたグラフニューラルネットワーク(GNN)上で、このグラフ構築方式を検証した。
  論文  参考訳（メタデータ） (2023-02-22T12:02:23Z)
• Graph Summarization with Graph Neural Networks [2.449909275410288]
  グラフニューラルネットワークを用いて、構造化されたコンパクトな方法で大きなグラフを表現する。 異なるGNNと標準多層パーセプトロン(MLP)とブルームフィルタを非神経的手法として比較する。 以上の結果から,GNNの性能は互いに近いことが明らかとなった。
  論文  参考訳（メタデータ） (2022-03-11T13:45:34Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。 オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。 2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
  論文  参考訳（メタデータ） (2020-06-12T07:18:02Z)

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

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