We analyze the performance of graph neural network (GNN) architectures from
the perspective of random graph theory. Our approach promises to complement
existing lenses on GNN analysis, such as combinatorial expressive power and
worst-case adversarial analysis, by connecting the performance of GNNs to
typical-case properties of the training data. First, we theoretically
characterize the nodewise accuracy of one- and two-layer GCNs relative to the
contextual stochastic block model (cSBM) and related models. We additionally
prove that GCNs cannot beat linear models under certain circumstances. Second,
we numerically map the recoverability thresholds, in terms of accuracy, of four
diverse GNN architectures (GCN, GAT, SAGE, and Graph Transformer) under a
variety of assumptions about the data. Sample results of this second analysis
include: heavy-tailed degree distributions enhance GNN performance, GNNs can
work well on strongly heterophilous graphs, and SAGE and Graph Transformer can
perform well on arbitrarily noisy edge data, but no architecture handled
sufficiently noisy feature data well. Finally, we show how both specific
higher-order structures in synthetic data and the mix of empirical structures
in real data have dramatic effects (usually negative) on GNN performance.

图神经网络性能分析基于随机图理论，GCN 和 GAT 是关键研究领域，性能受到数据特征的影响，实验结果显示特定高阶结构对性能有负面影响。

GNNS 中的全局最小值、可恢复阈值和高阶结构

Global Minima, Recoverability Thresholds, and Higher-Order Structure in  GNNS

Recent advances in self-supervised learning and neural network scaling have
enabled the creation of large models -- known as foundation models -- which can
be easily adapted to a wide range of downstream tasks. The current paradigm for
comparing foundation models involves benchmarking them with aggregate metrics
on various curated datasets. Unfortunately, this method of model comparison is
heavily dependent on the choice of metric, which makes it unsuitable for
situations where the ideal metric is either not obvious or unavailable. In this
work, we present a metric-free methodology for comparing foundation models via
their embedding space geometry. Our methodology is grounded in random graph
theory, and facilitates both pointwise and multi-model comparison. Further, we
demonstrate how our framework can be used to induce a manifold of models
equipped with a distance function that correlates strongly with several
downstream metrics.

本文提出了一种不需要度量的基于嵌入空间几何的方法来比较基础模型，并展示了该框架如何用于诱导一组带有距离函数的模型流型，其与多个下游度量强相关。

使用数据核心比较基础模型

Comparing Foundation Models using Data Kernels

We prove anti-concentration results for polynomials of independent random
variables with arbitrary degree. Our results extend the classical
Littlewood-Offord result for linear polynomials, and improve several earlier
estimates.
We discuss applications in two different areas. In complexity theory, we
prove near optimal lower bounds for computing the Parity, addressing a
challenge in complexity theory posed by Razborov and Viola, and also address a
problem concerning OR functions. In random graph theory, we derive a general
anti-concentration result on the number of copies of a fixed graph in a random
graph.

该研究论文的主要研究领域和主题为：独立随机变量的多项式抗集中性质证明、计算机复杂度理论中的下界问题和随机图中固定图的数量的反集中性结论。