在完全未知图结构下，用最少探查找最影响人的节点。
Revealing graph bandits for maximizing local influence
- 主动逐步探索图，每次只问一个节点影响谁
- 理论证明误差随可探测维度增长，远小于节点总数
- 适合社交营销等需高效发现关键节点的场景
我们研究一种图强化学习设置，目标是通过最少信息探查，找出图中最具影响力的节点。该问题在社交网络营销中有重要应用，即识别最具影响力的用户并加以利用。现有图上带权问题方法通常依赖部分或完整图结构知识，本文不假设任何先验知识，而是考虑一种可通过序列化主动方式逐步揭示图结构的设定。每轮中，学习者选择一个节点，仅获得该节点当前影响的随机节点集合作为反馈。为此，我们提出 BARE 策略，并证明其遗憾界与可探测维度相关，该问题相关量通常远小于节点数量。
原文摘要 · Abstract (English)
We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible. One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers. The existing approaches for bandit problems on graphs require either partial or complete knowledge of the graph. In this paper, we do not assume any knowledge of the graph, but we consider a setting where it can be gradually discovered in a sequential and active way. At each round, the learner chooses a node of the graph and the only information it receives is a stochastic set of the nodes that the chosen node is currently influencing. To address this setting, we propose BARE, a bandit strategy for which we prove a regret guarantee that scales with the detectable dimension, a problem dependent quantity that is often much smaller than the number of nodes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。