  Graph Neural Networks (GNNs) are a broad class of connectionist models for
graph processing. Recent studies have shown that GNNs can approximate any
function on graphs, modulo the equivalence relation on graphs defined by the
Weisfeiler--Lehman (WL) test. However, these results suffer from some
limitations, both because they were derived using the Stone--Weierstrass
theorem -- which is existential in nature, -- and because they assume that the
target function to be approximated must be continuous. Furthermore, all current
results are dedicated to graph classification/regression tasks, where the GNN
must produce a single output for the whole graph, while also node
classification/regression problems, in which an output is returned for each
node, are very common. In this paper, we propose an alternative way to
demonstrate the approximation capability of GNNs that overcomes these
limitations. Indeed, we show that GNNs are universal approximators in
probability for node classification/regression tasks, as they can approximate
any measurable function that satisfies the 1--WL equivalence on nodes. The
proposed theoretical framework allows the approximation of generic
discontinuous target functions and also suggests the GNN architecture that can
reach a desired approximation. In addition, we provide a bound on the number of
the GNN layers required to achieve the desired degree of approximation, namely
$2r-1$, where $r$ is the maximum number of nodes for the graphs in the domain.

Machine Learning;Computer Vision and Pattern Recognition