Fugu-MT 論文翻訳(概要): Adjacency Sketches in Adversarial Environments

論文の概要: Adjacency Sketches in Adversarial Environments

arxiv url: http://arxiv.org/abs/2309.03728v1
Date: Thu, 7 Sep 2023 14:13:44 GMT
ステータス: 処理完了
システム内更新日: 2024-03-25 22:59:44.270202
Title: Adjacency Sketches in Adversarial Environments
Title（参考訳）: 逆境環境における隣接スケッチ
Authors: Moni Naor, Eugene Pekel,
Abstract要約: ラベルに対して適応的なクエリを行う敵に対する確率的隣接スケッチのレジリエンスを考察する。 2dlog (1/varepsilon)$ bit labels を用いて最大次数 $d$ のグラフに対して、確率 $varepsilon$ で失敗するスケッチを構築する。
参考スコア（独自算出の注目度）: 3.388546694531524
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: An adjacency sketching or implicit labeling scheme for a family $\cal F$ of graphs is a method that defines for any $n$ vertex $G \in \cal F$ an assignment of labels to each vertex in $G$, so that the labels of two vertices tell you whether or not they are adjacent. The goal is to come up with labeling schemes that use as few bits as possible to represent the labels. By using randomness when assigning labels, it is sometimes possible to produce adjacency sketches with much smaller label sizes, but this comes at the cost of introducing some probability of error. Both deterministic and randomized labeling schemes have been extensively studied, as they have applications for distributed data structures and deeper connections to universal graphs and communication complexity. The main question of interest is which graph families have schemes using short labels, usually $O(\log n)$ in the deterministic case or constant for randomized sketches. In this work we consider the resilience of probabilistic adjacency sketches against an adversary making adaptive queries to the labels. This differs from the previously analyzed probabilistic setting which is ``one shot". We show that in the adaptive adversarial case the size of the labels is tightly related to the maximal degree of the graphs in $\cal F$. This results in a stronger characterization compared to what is known in the non-adversarial setting. In more detail, we construct sketches that fail with probability $\varepsilon$ for graphs with maximal degree $d$ using $2d\log (1/\varepsilon)$ bit labels and show that this is roughly the best that can be done for any specific graph of maximal degree $d$, e.g.\ a $d$-ary tree.
Abstract（参考訳）: グラフの任意の$n$ vertex $G \in \cal F$を、各頂点に対するラベルの代入として$G$で定義する手法である。目標は、ラベルを表現するために可能な限り数ビットを使用するラベリングスキームを考案することである。ラベルを割り当てるときにランダム性を使用することで、ラベルサイズがはるかに小さい隣接スケッチを作成できる場合もあるが、これはエラーの確率を導入するコストがかかる。決定論的およびランダムなラベリングスキームは、分散データ構造や普遍グラフへの深い接続、通信複雑性など、広く研究されている。主な関心事は、グラフ族がどのスキームをショートラベル(通常は$O(\log n)$)を使うか、あるいはランダム化されたスケッチに対して定数を持つかである。本研究では,ラベルに対して適応的なクエリを行う敵に対する確率的隣接スケッチのレジリエンスを検討する。これは以前分析された ``one shot' の確率的設定とは異なる。適応逆数の場合、ラベルのサイズは、$\cal F$のグラフの最大次数と密接に関連していることを示す。この結果、非敵対的な設定で知られているものと比較して、より強力な特徴付けがもたらされる。より詳しくは、最大次数$d$のグラフに対して、確率$\varepsilon$で失敗するスケッチを2d\log (1/\varepsilon)$ bit labelsを用いて構築し、これは、最大次数$d$, e g \ a $d$-ary tree の任意のグラフに対してできる、ほぼ最高のグラフであることを示す。

関連論文リスト

Self-Directed Linear Classification [50.659479930171585]
オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
論文参考訳（メタデータ） (2023-08-06T15:38:44Z)
Stochastic Contextual Bandits with Graph-based Contexts [0.0]
オンライングラフ予測問題を文脈的帯域問題に一般化する。我々のアルゴリズムは Zimmert と Seldin[AISTAT'19, JMLR'21] による最適帯域幅アルゴリズムに依存している。
論文参考訳（メタデータ） (2023-05-02T14:51:35Z)
Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs [20.470934944907608]
ホモフィリーあるいはヘテロフィリーなグラフでよく機能する新しいフレームワークについて検討する。ラベルに関するメッセージパッシングでは、類似の擬似ラベルを持つ隣人が集約される。また、ホモフィリー・ヘテロフィリーなグラフのモデルを自動的に選択するバイレベル最適化法を提案する。
論文参考訳（メタデータ） (2021-10-15T14:49:45Z)
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。三角凸分解はその上部に対応する変換によって保証されることを示す。
論文参考訳（メタデータ） (2021-09-17T17:46:12Z)
Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文参考訳（メタデータ） (2021-06-03T07:22:48Z)
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)
GraphHop: An Enhanced Label Propagation Method for Node Classification [34.073791157290614]
GraphHopと呼ばれるスケーラブルな半監視ノード分類手法が提案されている。実験結果は、GraphHopが幅広いタスクで最先端のグラフ学習方法より優れていることを示しています。
論文参考訳（メタデータ） (2021-01-07T02:10:20Z)
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文参考訳（メタデータ） (2020-12-10T15:40:07Z)
A Study on the Autoregressive and non-Autoregressive Multi-label Learning [77.11075863067131]
本稿では,ラベルとラベルの依存関係を共同で抽出する自己アテンションに基づく変分エンコーダモデルを提案する。したがって、ラベルラベルとラベル機能の両方の依存関係を保ちながら、すべてのラベルを並列に予測することができる。
論文参考訳（メタデータ） (2020-12-03T05:41:44Z)
Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
論文参考訳（メタデータ） (2020-07-12T12:06:17Z)
Higher-Order Label Homogeneity and Spreading in Graphs [24.20979516244867]
エッジに加えて三角形を用いた高次ラベル拡散は,エッジのみを用いたラベル拡散よりも最大4.7%よいことを示す。従来の手法や最先端手法と比較して,提案手法は統計的に有意な精度向上をもたらす。
論文参考訳（メタデータ） (2020-02-18T19:09:21Z)

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

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