論文の概要: An Approximation Algorithm for Graph Label Selection

• arxiv url: http://arxiv.org/abs/2605.18623v2
• Date: Tue, 19 May 2026 20:21:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 14:55:44.321729
• Title: An Approximation Algorithm for Graph Label Selection
• Title（参考訳）: グラフラベル選択のための近似アルゴリズム
• Authors: Josia John, Simon Meierhans, Maximilian Probst Gutenberg,
• Abstract要約: 標準予算制約の下でグラフラベル選択のための最初の$tildeO(log1.5 n)$-approximationアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.9142071346727817
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the graph label selection problem, one is given an $n$-vertex graph and a budget $k$, and seeks to select $k$ vertices whose labels enable accurate prediction of the labels on the remaining vertices. This problem formalizes distilling a small representative set from the whole graph. We present the first $\tilde{O}(\log^{1.5} n)$-approximation algorithm for graph label selection under the standard budget constraint. Prior work either relies on resource augmentation, allowing substantially more than $k$ labeled vertices, or consists primarily of heuristics without provable guarantees. Finally, we demonstrate that practical heuristic variants of our algorithm scale to significantly larger graphs than previous methods, while essentially retaining their quality.
• Abstract（参考訳）: グラフラベル選択問題では、$n$-頂点グラフと$k$が与えられ、ラベルが残りの頂点上のラベルの正確な予測を可能にする$k$頂点を選択する。 この問題はグラフ全体から小さな代表集合を蒸留する。 標準予算制約の下でグラフラベル選択のための最初の$\tilde{O}(\log^{1.5} n)$-approximationアルゴリズムを提案する。 それまでの作業は、リソース拡張に依存しており、ラベル付き頂点が$k$以上可能であるか、主に証明可能な保証のないヒューリスティックスで構成されている。 最後に、我々のアルゴリズムの実用的ヒューリスティックな変種は、本質的にその品質を維持しつつ、従来の方法よりもはるかに大きなグラフにスケールすることを示した。

関連論文リスト

• Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
  本研究では,データラベルが不足している,あるいは破損しているような状況下でのグラフに対する半教師付き学習の課題について検討する。 我々は、$p$-laplace と Poisson の学習方法を一般化した $p$-conductance learning という手法を提案する。 コンピュータビジョンと引用データセットの実証実験結果から,本手法が低ラベルレート, 劣化ラベル, 部分ラベルレジームにおける最先端の精度を実現することを示す。
  論文  参考訳（メタデータ） (2025-02-13T01:11:25Z)
• A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
  未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。 与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
  論文  参考訳（メタデータ） (2024-07-23T15:40:35Z)
• Mitigating Label Noise on Graph via Topological Sample Selection [72.86862597508077]
  トポロジ情報を活用することで,グラフ内の情報的サンプル選択プロセスを促進できる$textitTopological Sample Selection$ (TSS)法を提案する。 提案手法は,対象のクリーン分布下での予測されるリスク上限の上限を最小化し,最先端のベースラインと比較して,提案手法の優位性を実験的に示す。
  論文  参考訳（メタデータ） (2024-03-04T11:24:51Z)
• Adjacency Sketches in Adversarial Environments [3.388546694531524]
  ラベルに対して適応的なクエリを行う敵に対する確率的隣接スケッチのレジリエンスを考察する。 2dlog (1/varepsilon)$ bit labels を用いて最大次数 $d$ のグラフに対して、確率 $varepsilon$ で失敗するスケッチを構築する。
  論文  参考訳（メタデータ） (2023-09-07T14:13:44Z)
• Stochastic Contextual Bandits with Graph-based Contexts [0.0]
  オンライングラフ予測問題を文脈的帯域問題に一般化する。 我々のアルゴリズムは Zimmert と Seldin[AISTAT'19, JMLR'21] による最適帯域幅アルゴリズムに依存している。
  論文  参考訳（メタデータ） (2023-05-02T14:51:35Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• GraphHop: An Enhanced Label Propagation Method for Node Classification [34.073791157290614]
  GraphHopと呼ばれるスケーラブルな半監視ノード分類手法が提案されている。 実験結果は、GraphHopが幅広いタスクで最先端のグラフ学習方法より優れていることを示しています。
  論文  参考訳（メタデータ） (2021-01-07T02:10:20Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)
• Factorized Graph Representations for Semi-Supervised Learning from Sparse Data [8.875598257768846]
  極端に粗いラベル付きグラフでも、遠隔互換性推定と呼ばれる手法が有効であることを示す。 我々の推定器は代替手法よりも桁違いに高速であり、エンドツーエンドの分類精度は金の標準適合性に匹敵するものである。
  論文  参考訳（メタデータ） (2020-03-05T18:57:45Z)

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

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