論文の概要: Active Learning on Adversarially Corrupted Graphs

• arxiv url: http://arxiv.org/abs/2607.04869v1
• Date: Mon, 06 Jul 2026 09:42:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:30.105672
• Title: Active Learning on Adversarially Corrupted Graphs
• Title（参考訳）: 逆崩壊グラフのアクティブラーニング
• Abstract要約: 敵は、グラフの$G*$の中にエンプコープされた頂点の集合を隠そうとする。 敵の力は、崩壊した頂点の大きさによって、$G*$で測られる。 我々は, 競合のパワーとemph展開の$G*$に依存する問合せ複雑性を伴って, 破損した頂点をほぼ復元する効率的なアルゴリズムを考案した。
• 参考スコア（独自算出の注目度）: 34.01867185404678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph $G^*$. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and $G^*$, and its power is then measured by the size of the \emph{neighborhood} of the corrupted vertices in $G^*$. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the \emph{vertex expansion} of $G^*$, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.
• Abstract（参考訳）: 悪意のあるエンティティが既存のネットワークを改ざんする現実世界のシナリオに触発され、敵がグラフの$G^*$内に \emph{corrupted vertices} のセットを隠そうとするモデルを定義する。 この目的のために、敵は腐敗した頂点間の縁と、腐敗した頂点と$G^*$の間の縁を付加することができ、その力は、崩壊した頂点の$G^*$のemph{neighborhood}の大きさで測定される。 我々のゴールは、少数のラベルクエリを用いて、破損した頂点のサブセットを効率的に見つける能動的学習アルゴリズムを設計することである。 グラフ接続の基本的な尺度である$G^*$ の敵のパワーと \emph{vertex expansion} の両方に多項式的に依存する問合せ複雑性で、破損した頂点を近似的に復元する効率的なアルゴリズムを考案する。 この結果の核心は多項式時間アルゴリズムであり、最小展開を近似するために二乗和アルゴリズムを慎重に適用することで得られる。 我々の知る限りでは、この頂点拡大が、構造的敵攻撃に対して堅牢な能動学習アルゴリズムのクエリ複雑性を決定する上で重要な役割を担っていることが示されるのは、これが初めてである。

関連論文リスト

• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  自然のオラクルから補助情報を得た階層的クラスタリングの問題を考察する。 分割オラクルは、アルゴリズムが標準のHCアプローチより優れていることを示す。 我々のアプローチはサブ線形設定にまで拡張され、保証を改善した新しいストリーミングとPRAMアルゴリズムが示されます。
  論文  参考訳（メタデータ） (2025-06-05T18:22:40Z)
• 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)
• BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs [0.3277163122167434]
  本稿では,二部グラフ内の最大双斜線を包括的に列挙するアルゴリズムを提案する。 BBK for Bipartite Bron-Kerboschと呼ばれるこのアルゴリズムは、Bron-Kerboschアルゴリズムの新しい拡張である。 最先端のアルゴリズムよりも高速で、既存の実装では管理できない巨大な二部グラフの列挙を可能にする。
  論文  参考訳（メタデータ） (2024-05-07T15:49:34Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。 我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
  論文  参考訳（メタデータ） (2020-03-13T20:03:01Z)

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

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