  Despite the recent success of graph neural networks (GNN), common
architectures often exhibit significant limitations, including sensitivity to
oversmoothing, long-range dependencies, and spurious edges, e.g., as can occur
as a result of graph heterophily or adversarial attacks. To at least partially
address these issues within a simple transparent framework, we consider a new
family of GNN layers designed to mimic and integrate the update rules of two
classical iterative algorithms, namely, proximal gradient descent and iterative
reweighted least squares (IRLS). The former defines an extensible base GNN
architecture that is immune to oversmoothing while nonetheless capturing
long-range dependencies by allowing arbitrary propagation steps. In contrast,
the latter produces a novel attention mechanism that is explicitly anchored to
an underlying end-toend energy function, contributing stability with respect to
edge uncertainty. When combined we obtain an extremely simple yet robust model
that we evaluate across disparate scenarios including standardized benchmarks,
adversarially-perturbated graphs, graphs with heterophily, and graphs involving
long-range dependencies. In doing so, we compare against SOTA GNN approaches
that have been explicitly designed for the respective task, achieving
competitive or superior node classification accuracy.
