Discriminability of Single-Layer Graph Neural Networks
  Network data can be conveniently modeled as a graph signal, where data values
are assigned to the nodes of a graph describing the underlying network
topology. Successful learning from network data requires methods that
effectively exploit this graph structure. Graph neural networks (GNNs) provide
one such method and have exhibited promising performance on a wide range of
problems. Understanding why GNNs work is of paramount importance, particularly
in applications involving physical networks. We focus on the property of
discriminability and establish conditions under which the inclusion of
pointwise nonlinearities to a stable graph filter bank leads to an increased
discriminative capacity for high-eigenvalue content. We define a notion of
discriminability tied to the stability of the architecture, show that GNNs are
at least as discriminative as linear graph filter banks, and characterize the
signals that cannot be discriminated by either.
