We argue that Transformers are essentially graph-to-graph models, with
sequences just being a special case. Attention weights are functionally
equivalent to graph edges. Our Graph-to-Graph Transformer architecture makes
this ability explicit, by inputting graph edges into the attention weight
computations and predicting graph edges with attention-like functions, thereby
integrating explicit graphs into the latent graphs learned by pretrained
Transformers. Adding iterative graph refinement provides a joint embedding of
input, output, and latent graphs, allowing non-autoregressive graph prediction
to optimise the complete graph without any bespoke pipeline or decoding
strategy. Empirical results show that this architecture achieves
state-of-the-art accuracies for modelling a variety of linguistic structures,
integrating very effectively with the latent linguistic representations learned
by pretraining.

我们认为 Transformer 模型本质上是图到图的模型，序列只是一种特殊情况。注意力权重在功能上等价于图中的边。我们的图到图 Transformer 架构明确地表达了这个能力，通过将图的边作为输入用于注意力权重计算，并使用类似于注意力的函数预测图中的边，从而将显式图集成到预训练的 Transformer 模型中学习出的潜在图中。添加迭代的图优化过程提供了输入、输出和潜在图的联合嵌入，使得非自回归图预测能够优化完整图，无需任何专门的流水线或解码策略。实证结果表明，该架构在对各种语言结构建模方面取得了最先进的准确性，与预训练学习的潜在语言表示非常有效地集成在一起。

将 Transformer 模型作为图到图模型

Transformers as Graph-to-Graph Models

Given a stream of graph edges from a dynamic graph, how can we assign anomaly
scores to edges in an online manner, for the purpose of detecting unusual
behavior, using constant time and memory? Existing approaches aim to detect
individually surprising edges. In this work, we propose MIDAS, which focuses on
detecting microcluster anomalies, or suddenly arriving groups of suspiciously
similar edges, such as lockstep behavior, including denial of service attacks
in network traffic data. MIDAS has the following properties: (a) it detects
microcluster anomalies while providing theoretical guarantees about its false
positive probability; (b) it is online, thus processing each edge in constant
time and constant memory, and also processes the data 162-644 times faster than
state-of-the-art approaches; (c) it provides 42%-48% higher accuracy (in terms
of AUC) than state-of-the-art approaches.

本文提出 MIDAS 算法，用于在线检测动态图中的异常行为，关注于检测突然出现的被怀疑相似的边缘组，比现有方法快 162-644 倍，并提高了 42-48% 的准确性。

MIDAS: 基于微簇的边缘流异常检测器

MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams

In the Network Inference problem, one seeks to recover the edges of an
unknown graph from the observations of cascades propagating over this graph. In
this paper, we approach this problem from the sparse recovery perspective. We
introduce a general model of cascades, including the voter model and the
independent cascade model, for which we provide the first algorithm which
recovers the graph's edges with high probability and $O(s\log m)$ measurements
where $s$ is the maximum degree of the graph and $m$ is the number of nodes.
Furthermore, we show that our algorithm also recovers the edge weights (the
parameters of the diffusion process) and is robust in the context of
approximate sparsity. Finally we prove an almost matching lower bound of
$\Omega(s\log\frac{m}{s})$ and validate our approach empirically on synthetic
graphs.

研究图网络推断问题，探讨基于稀疏恢复的级联模型，提出第一个可以高概率和 O（slog m）的测量找到图的边缘的算法，并能恢复边权及适用于近似稀疏条件下的情景。最后，通过人造数据验证了本算法的可靠性及降低边缘误差和参数估计误差的能力。