Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications
in high-stakes domains are often hampered by unreliable predictions. Although
numerous uncertainty quantification methods have been proposed to address this
limitation, they often lack \textit{rigorous} uncertainty estimates. This work
makes the first attempt to introduce a distribution-free and model-agnostic
uncertainty quantification approach to construct a predictive interval with a
statistical guarantee for GNN-based link prediction. We term it as
\textit{conformalized link prediction.} Our approach builds upon conformal
prediction (CP), a framework that promises to construct statistically robust
prediction sets or intervals. We first theoretically and empirically establish
a permutation invariance condition for the application of CP in link prediction
tasks, along with an exact test-time coverage. Leveraging the important
structural information in graphs, we then identify a novel and crucial
connection between a graph's adherence to the power law distribution and the
efficiency of CP. This insight leads to the development of a simple yet
effective sampling-based method to align the graph structure with a power law
distribution prior to the standard CP procedure. Extensive experiments
demonstrate that for conformalized link prediction, our approach achieves the
desired marginal coverage while significantly improving the efficiency of CP
compared to baseline methods.

这篇论文介绍了一种无分布和无模型偏见的不确定性量化方法，用于构建基于 GNN 的链接预测的具有统计保证的预测区间，该方法在遵循幂律分布的图结构上显著提高了基线方法的有效性。

图神经网络上的等度连通预测

Conformalized Link Prediction on Graph Neural Networks

Dense crowd counting is a challenging task that demands millions of head
annotations for training models. Though existing self-supervised approaches
could learn good representations, they require some labeled data to map these
features to the end task of density estimation. We mitigate this issue with the
proposed paradigm of complete self-supervision, which does not need even a
single labeled image. The only input required to train, apart from a large set
of unlabeled crowd images, is the approximate upper limit of the crowd count
for the given dataset. Our method dwells on the idea that natural crowds follow
a power law distribution, which could be leveraged to yield error signals for
backpropagation. A density regressor is first pretrained with self-supervision
and then the distribution of predictions is matched to the prior by optimizing
Sinkhorn distance between the two. Experiments show that this results in
effective learning of crowd features and delivers significant counting
performance. Furthermore, we establish the superiority of our method in less
data setting as well. The code and models for our approach is available at
this https URL

提出一种完全自我监督的方法来解决密集人群计数问题，该方法可以在没有任何标注图像的情况下进行训练，通过预训练密度回归器实现特征学习，并通过最优化 Sinkhorn 距离匹配预测分布和先验分布来实现计数。实验结果证明了该方法在少量数据下也具有优越性。

基于分布匹配的完全自监督人群计数

Completely Self-Supervised Crowd Counting via Distribution Matching

Random multiplicative processes $w_t =\lambda_1 \lambda_2 ... \lambda_t$
(with < \lambda_j > 0 ) lead, in the presence of a boundary constraint, to a
distribution $P(w_t)$ in the form of a power law $w_t^{-(1+\mu)}$. We provide a
simple and physically intuitive derivation of this result based on a random
walk analogy and show the following: 1) the result applies to the asymptotic
($t \to \infty$) distribution of $w_t$ and should be distinguished from the
central limit theorem which is a statement on the asymptotic distribution of
the reduced variable ${1 \over \sqrt{t}}(log w_t -< log w_t >)$; 2) the
necessary and sufficient conditions for $P(w_t)$ to be a power law are that
<log \lambda_j > < 0 (corresponding to a drift $w_t \to 0$) and that $w_t$ not
be allowed to become too small. We discuss several models, previously
unrelated, showing the common underlying mechanism for the generation of power
laws by multiplicative processes: the variable $\log w_t$ undergoes a random
walk biased to the left but is bounded by a repulsive ''force''. We give an
approximate treatment, which becomes exact for narrow or log-normal
distributions of $\lambda$, in terms of the Fokker-Planck equation. 3) For all
these models, the exponent $\mu$ is shown exactly to be the solution of
$\langle \lambda^{\mu} \rangle = 1$ and is therefore non-universal and depends
on the distribution of $\lambda$.

本文利用随机漫步的类比，简单并直观地推导了随机乘性过程在有边界约束下的功率律分布，并揭示了产生这种分布的一般机制。