論文の概要: Online Influence Maximization with Node-level Feedback Using Standard
Offline Oracles
- arxiv url: http://arxiv.org/abs/2109.06077v1
- Date: Mon, 13 Sep 2021 15:54:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-14 20:40:05.885221
- Title: Online Influence Maximization with Node-level Feedback Using Standard
Offline Oracles
- Title（参考訳）: 標準オフラインオラクルを用いたノードレベルのフィードバックによるオンライン影響最大化
- Authors: Zhijie Zhang, Wei Chen, Xiaoming Sun, Jialin Zhang
- Abstract要約: 本稿では,2つの課題に焦点をあてる。
まず、エッジレベルのフィードバックではなく、ノードレベルのフィードバックで作業します。
第二に、オフラインのペアオーラではなく、標準的なオフラインのオーラクルを使用します。
- 参考スコア（独自算出の注目度）: 20.916163957596577
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the online influence maximization (OIM) problem in social networks,
where in multiple rounds the learner repeatedly chooses seed nodes to generate
cascades, observes the cascade feedback, and gradually learns the best seeds
that generate the largest cascade. We focus on two major challenges in this
paper. First, we work with node-level feedback instead of edge-level feedback.
The edge-level feedback reveals all edges that pass through information in a
cascade, where the node-level feedback only reveals the activated nodes with
timestamps. The node-level feedback is arguably more realistic since in
practice it is relatively easy to observe who is influenced but very difficult
to observe from which relationship (edge) the influence comes from. Second, we
use standard offline oracle instead of offline pair-oracle. To compute a good
seed set for the next round, an offline pair-oracle finds the best seed set and
the best parameters within the confidence region simultaneously, and such an
oracle is difficult to compute due to the combinatorial core of OIM problem. So
we focus on how to use the standard offline influence maximization oracle which
finds the best seed set given the edge parameters as input. In this paper, we
resolve these challenges for the two most popular diffusion models, the
independent cascade (IC) and the linear threshold (LT) model. For the IC model,
the past research only achieves edge-level feedback, while we present the first
$\widetilde{O}(\sqrt{T})$-regret algorithm for the node-level feedback.
Besides, the algorithm only invokes standard offline oracles. For the LT model,
a recent study only provides an OIM solution that meets the first challenge but
still requires a pair-oracle. In this paper, we apply a similar technique as in
the IC model to replace the pair-oracle with a standard oracle while
maintaining $\widetilde{O}(\sqrt{T})$-regret.
- Abstract（参考訳）: そこで,複数のラウンドにおいて学習者が繰り返しシードノードを選択してカスケードを生成し,カスケードフィードバックを観察し,最大カスケードを生成するベストシードを徐々に学習する。
本稿では,2つの課題に焦点をあてる。
まず、エッジレベルのフィードバックではなく、ノードレベルのフィードバックで作業します。
エッジレベルのフィードバックは、カスケード内の情報を通過するすべてのエッジを明らかにし、ノードレベルのフィードバックはタイムスタンプでアクティブなノードのみを表示する。
ノードレベルのフィードバックは、実際には誰が影響を受けているのかを観察することは比較的容易であるが、どの関係(エッジ)から影響が生まれるのかを観察するのが非常に難しいため、おそらくより現実的である。
次に、オフラインペアoracleではなく、標準オフラインoracleを使用します。
次のラウンドのよいシードセットを計算するために、オフラインペアオーラは、信頼領域内で最高のシードセットと最高のパラメータを同時に見つけることができ、OIM問題の組合せコアのため、そのようなオーラクルの計算が困難である。
そこで我々は、エッジパラメータを入力として最適なシードセットを求める、標準のオフライン影響最大化オラクルの使い方に焦点をあてる。
本稿では,最も普及している拡散モデルである独立カスケード(IC)と線形しきい値(LT)モデルについて,これらの課題を解決する。
ICモデルでは、従来の研究はエッジレベルのフィードバックしか得られず、ノードレベルのフィードバックのための最初の$\widetilde{O}(\sqrt{T})$-regretアルゴリズムを提示する。
さらに、アルゴリズムは標準のオフラインオラクルのみを呼び出す。
LTモデルでは、最近の研究は最初の課題を満たすOIMソリューションのみを提供するが、それでもペアオーラを必要とする。
本稿では、ICモデルと同様の手法を適用し、$\widetilde{O}(\sqrt{T})$-regretを維持しながら、ペアオーラを標準的なオラクルに置き換える。
関連論文リスト
- Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳（メタデータ） (2024-04-16T07:05:16Z) - Online Iterative Reinforcement Learning from Human Feedback with General Preference Model [20.81421550138371]
本稿では,人間のフィードバックからの強化学習(RLHF)について,一般的な嗜好のオラクルの文脈で検討する。
我々は、RLHFの2つのLLM間の逆KL正規化ミニマックスゲームである標準的な数学的定式化を考える。
このフレームワークは報酬ベースよりも厳密に汎用的であり,事前選択された選好データセットからオフライン学習を行うためのサンプル効率のよいアルゴリズムとオンライン学習を提案する。
論文 参考訳（メタデータ） (2024-02-11T21:44:21Z) - Scalable and Efficient Temporal Graph Representation Learning via Forward Recent Sampling [7.803172953008744]
時間グラフ表現学習(TGRL)は,実世界のネットワークにおける動的システムのモデリングに不可欠である。
従来のTGRL法は、時間的隣人の非効率なサンプリングのため、重要な計算課題や推論遅延に直面していることが多い。
本稿では,新しいTGRLフレームワークであるNo-Looking-Back (NLB)を提案する。
論文 参考訳（メタデータ） (2024-02-03T00:12:36Z) - A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing
Time [6.961946145048321]
本稿では,クラスタ性が強いグラフに対して,サブ線形時間スペクトルクラスタリングオラクルを設計する問題に対処する。
アルゴリズムは仮定を緩和するが、誤分類比はわずかに高い。
私たちのクラスタリングオラクルは、いくつかのランダムなエッジ削除に対して堅牢です。
論文 参考訳（メタデータ） (2023-10-27T03:40:37Z) - A Topological Perspective on Demystifying GNN-Based Link Prediction
Performance [72.06314265776683]
トポロジカル濃度 (TC) は、各ノードの局所部分グラフと隣人の部分グラフの交点に基づいている。
また,TCLは,次数や部分グラフ密度などの他のノードレベルのトポロジ指標よりもLP性能と高い相関性を示した。
我々は, 近似トポロジカル濃度 (ATC) を提案し, 理論的・経験的にTC近似の有効性を正当化し, 複雑さを低減させる。
論文 参考訳（メタデータ） (2023-10-06T22:07:49Z) - Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
論文 参考訳（メタデータ） (2023-09-29T19:55:56Z) - Communication-Efficient Decentralized Federated Learning via One-Bit
Compressive Sensing [52.402550431781805]
分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。
集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。
我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-08-31T12:22:40Z) - On Exploring Node-feature and Graph-structure Diversities for Node Drop
Graph Pooling [86.65151066870739]
現在のノードドロッププーリング法は、ノードの特徴やグラフ構造の観点からグラフの多様性を無視し、結果としてグラフレベル以下の表現をもたらす。
そこで本稿では,textiti.fltextbfIpscore と textbfDropscore の2つの操作を持つ textbfMulti スコア空間からなる MID を新たに提案する。
具体的には、多次元スコア空間は、複数の基準を通してノードの重要さを描いており、フリップスコアは異種ノードの維持を奨励している。
論文 参考訳（メタデータ） (2023-06-22T08:02:01Z) - Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。
本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。
本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
論文 参考訳（メタデータ） (2022-10-30T19:38:23Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Online Influence Maximization under Linear Threshold Model [17.06633823730587]
オンライン・インフルエンス(OIM)は、影響力伝達モデルパラメータを学習するソーシャル・ネットワークにおいて一般的な問題である。
本稿では,線形しきい値(LT)モデルでOIMに対処する。
群観察変調された性質滑らか性(GOM)を証明することにより、次数 $tildeO(mathrmpoly(m)sqrtT)$ を後悔する。
また,モデルに依存しない,O(mathrmpoly(m) T2/3)$という残差を持つOIM-ETCアルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-11-12T13:41:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。