Recently, implicit graph neural networks (GNNs) have been proposed to capture
long-range dependencies in underlying graphs. In this paper, we introduce and
justify two weaknesses of implicit GNNs: the constrained expressiveness due to
their limited effective range for capturing long-range dependencies, and their
lack of ability to capture multiscale information on graphs at multiple
resolutions. To show the limited effective range of previous implicit GNNs, We
first provide a theoretical analysis and point out the intrinsic relationship
between the effective range and the convergence of iterative equations used in
these models. To mitigate the mentioned weaknesses, we propose a multiscale
graph neural network with implicit layers (MGNNI) which is able to model
multiscale structures on graphs and has an expanded effective range for
capturing long-range dependencies. We conduct comprehensive experiments for
both node classification and graph classification to show that MGNNI
outperforms representative baselines and has a better ability for multiscale
modeling and capturing of long-range dependencies.

本文介绍和证明了隐式图神经网络存在的两个弱点：他们的限制表达能力由于他们对捕获长程依赖性的有效范围有限以及他们无法在多个分辨率上对图进行多尺度信息建模。为了缓解这些弱点，我们提出了一种带有隐式层次的多尺度图神经网络 (MGNNI)，它能够模拟图的多尺度结构，具有更广泛的有效范围，能够捕获长程依赖性，并且在节点分类和图分类方面，我们进行了全面的实验来表明 MGNNI 优于代表性基准，并具有更好的多尺度建模和捕获长程依赖性的能力。

MGNNI: 带隐式层的多尺度图神经网络

MGNNI: Multiscale Graph Neural Networks with Implicit Layers

We study how the regret guarantees of nonstochastic multi-armed bandits can
be improved, if the effective range of the losses in each round is small (e.g.
the maximal difference between two losses in a given round). Despite a recent
impossibility result, we show how this can be made possible under certain mild
additional assumptions, such as availability of rough estimates of the losses,
or advance knowledge of the loss of a single, possibly unspecified arm. Along
the way, we develop a novel technique which might be of independent interest,
to convert any multi-armed bandit algorithm with regret depending on the loss
range, to an algorithm with regret depending only on the effective range, while
avoiding predictably bad arms altogether.

研究了如何提高非随机多臂老虎机的后悔保证，如果每轮损失的有效范围很小（例如，在给定轮次中两个损失之间的最大差异）。通过一些温和的额外假设，如可用的粗略估计损失或单个可能未指定的臂的损失的预先知识，我们展示了这是如何可能的。我们还开发了一种新的技术，可以将任何具有取决于损失范围的后悔的多臂老虎机算法转换为仅取决于有效范围的算法，同时完全避免有问题的臂。