論文の概要: Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
- arxiv url: http://arxiv.org/abs/2602.00657v1
- Date: Sat, 31 Jan 2026 11:07:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-03 19:28:33.320245
- Title: Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
- Title（参考訳）: グラフにおける非切り抜き教育:アルゴリズム、複雑度、境界
- Authors: Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney,
- Abstract要約: グラフ内の閉近傍に対する(正の)非クラッシング教育を考える。
我々は、より一般的なパラメータのクラスのためのFPTアルゴリズムを含む改良されたアルゴリズム結果を提供する。
より広いグラフのクラスに対してより強い上限を得る。
- 参考スコア（独自算出の注目度）: 5.718194486637426
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the collusion-avoidance benchmark established in the seminal work of Goldman and Mathias [COLT 1993]. Recently, (positive) non-clashing teaching was thoroughly studied for balls in graphs, yielding numerous algorithmic and combinatorial results. In particular, Chalopin et al. [COLT 2024] and Ganian et al. [ICLR 2025] gave an almost complete picture of the complexity landscape of the positive variant, showing that it is tractable only for restricted graph classes due to the non-trivial nature of the problem and concept class. In this work, we consider (positive) non-clashing teaching for closed neighborhoods in graphs. This concept class is not only extensively studied in various related contexts, but it also exhibits broad generality, as any finite binary concept class can be equivalently represented by a set of closed neighborhoods in a graph. In comparison to the works on balls in graphs, we provide improved algorithmic results, notably including FPT algorithms for more general classes of parameters, and we complement these results by deriving stronger lower bounds. Lastly, we obtain combinatorial upper bounds for wider classes of graphs.
- Abstract（参考訳）: Kirkpatrick et al [ALT 2019] と Fallat et al [JMLR 2023] は、非クラッシング教育を導入し、ゴールドマン・アンド・マティアス(COLT 1993)の独創的な研究で確立された共謀回避ベンチマークを満たす最も効率的なバッチマシン教育モデルであることを証明した。
近年、グラフ内の球に対して(肯定的な)非クラッシング教育が徹底的に研究され、多くのアルゴリズム的および組合せ的な結果が得られた。
特に、Chalopin et al [COLT 2024] と Ganian et al [ICLR 2025] は、正の変項の複雑さの風景をほぼ完全に表現し、問題と概念クラスの非自明な性質のため、制限グラフクラスに対してのみ引き出すことができることを示した。
本研究では,グラフ内の閉近傍に対する(正の)非クラッシング教育について考察する。
この概念クラスは、様々な関連する文脈で広く研究されているだけでなく、任意の有限二項の概念クラスをグラフ内の閉近傍の集合で同値に表現できるため、広範な一般性も示している。
グラフ内の球についての研究と比較して、より一般的なパラメータのクラスに対するFPTアルゴリズムを含む改良されたアルゴリズム結果を提供し、より強い下界を導出することでこれらの結果を補完する。
最後に、より広いグラフのクラスに対する組合せ上界を得る。
関連論文リスト
- Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
可換性構造を符号化するグラフ、すなわちフラストレーショングラフによって、グラフ理論と量子情報の間の自然なインターフェースを提供する。
このクラスを$hbar$-perfectと呼び、完全グラフと$hbar-perfectグラフのクラスを拡張します。
絡み合い検出のための効率的なスキーム,シャドウトモグラフィーの複雑さへの接続,厳密な不確実性関係,地中エネルギーの低い計算のための構成を見いだす。
論文 参考訳（メタデータ） (2025-11-17T16:05:28Z) - Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference [18.101059380671582]
ネットワーク干渉下でのマルチアームバンディットについて検討する。
これにより指数的に大きな作用空間が生じる。
本稿では,局所グラフ構造を用いて後悔を最小限に抑える新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-03-10T17:25:24Z) - The Computational Complexity of Positive Non-Clashing Teaching in Graphs [13.564319117200561]
概念の集合の正の非クラッシング教育次元を計算する際の古典的およびパラメータ化された複雑性について検討する。
我々は、正の非クラッシング教育次元 k=2 のインスタンスに制限された場合でも、問題のNPハードネスを確立する。
論文 参考訳（メタデータ） (2025-03-08T21:48:02Z) - Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳（メタデータ） (2024-12-03T18:36:45Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Graph Soft-Contrastive Learning via Neighborhood Ranking [19.241089079154044]
グラフコントラスト学習(GCL)は,グラフ自己教師型学習の領域において,有望なアプローチとして登場した。
グラフソフトコントラスト学習(GSCL)という新しいパラダイムを提案する。
GSCLは地域ランキングを通じてGCLを促進するため、全く同様のペアを特定する必要がなくなる。
論文 参考訳（メタデータ） (2022-09-28T09:52:15Z) - GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。
本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
論文 参考訳（メタデータ） (2022-03-24T02:58:36Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。
本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。
提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
論文 参考訳（メタデータ） (2021-08-15T13:14:28Z) - Group Contrastive Self-Supervised Learning on Graphs [101.45974132613293]
グラフ上での自己教師型学習をコントラッシブ手法を用いて研究する。
複数の部分空間におけるグラフの対比により、グラフエンコーダはより豊富な特徴を捉えることができる。
論文 参考訳（メタデータ） (2021-07-20T22:09:21Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。