# Energy-Based Learning for Scene Graph Generation

Mohammed Suhail1,2 Abhay Mittal4 Behjat Siddiquie4 Chris Broaddus4
Jayan Eledath4 Gerard Medioni4 Leonid Sigal1,2,3
1University of British Columbia 2Vector Institute for AI 3Canada CIFAR AI
Chair 4 Amazon
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Traditional scene graph generation methods are trained using cross-entropy
losses that treat objects and relationships as independent entities. Such a
formulation, however, ignores the structure in the output space, in an
inherently structured prediction problem. In this work, we introduce a novel
energy-based learning framework for generating scene graphs. The proposed
formulation allows for efficiently incorporating the structure of scene graphs
in the output space. This additional constraint in the learning framework acts
as an inductive bias and allows models to learn efficiently from a small
number of labels. We use the proposed energy-based framework 111Code and pre-
trained models available at https://github.com/mods333/energy-based-scene-
graph. to train existing state-of-the-art models and obtain a significant
performance improvement, of up to 21% and 27%, on the Visual Genome [9] and
GQA [5] benchmark datasets, respectively. Furthermore, we showcase the
learning efficiency of the proposed framework by demonstrating superior
performance in the zero- and few-shot settings where data is scarce.

##  1 Introduction

Figure 1: Scene Graph Generation: Figure shows scene graphs generated by a
VCTree [22] model trained using conventional cross-entropy loss (purple) and
our proposed energy-based framework (green). We make two crucial observations.
First, the model trained using cross-entropy loss is incapable of consistent
structural reasoning (riding is not possible given the rest of the graph).
Second, the trained model tends to be biased, favoring more frequent relations
(, on). Our proposed energy-based framework is designed, and able, to address
these shortcomings.

A scene graph is a graph-based representation of an image which encodes
objects along with the relationships between them. Such a representation
allows for a comprehensive understanding of images that is useful in several
vision applications, including visual question answering [5, 22], image
captioning [3, 28] and scene synthesis [4, 6].

A typical scene graph generation model comprises of the object detection
network, which extracts object regions and corresponding features, and a
message passing network with nodes initialized with these region features and
edges accounting for the potential relations among them. The features are
refined, through context aggregation, and then classified to produce both
object (node) and relation (edge) labels. These networks are often trained
end-to-end by minimizing individual cross-entropy losses on both sets of
labels. A major drawback of such an approach is that quality of prediction
(loss) is simply proportional to the number of correctly predicted labels and
ignores the rich structure of the scene graph output space (, correlation or
exclusion among object and relation label sets). In addition, the imbalance in
the number of training samples for the relations results in dominant relations
being heavily favored, leading to biased relation prediction at test time
[21].

Figure 1 (b) illustrates the scene graph generated by a model [22] trained
using the cross-entropy loss. Both the aforementioned drawbacks are apparent
in the output. First, the model predicts a relation <man, riding, wave>. A
simple examination of the rest of the scene graph reveals that such a
relationship is impossible given that the man is on a rock and holding a
surfboard. Second, the model leans towards making generic relation predictions
such as <man, on, rock> as opposed to more informative alternatives, , <man,
standing on, rock>.

The origin of these issues can be identified by examining the likelihood term.
Cross-entropy based training treats objects ($O$) and relationships ($R$) in a
scene graph as independent entities. This amounts to factorizing the
likelihood of a scene graph ($SG$), given an image ($I$), as the product of
the likelihoods for the individual objects and relations:

$\log p(SG|I)=\sum_{i\in O}\log p(o_{i}|I)+\sum_{j\in R}\log p(r_{j}|I).$ (1)

Eq.(1) brings to light the underlying cause of the problem highlighted above.
First, during loss computation, the loss for each relation term is independent
of the relations predicted in the rest of the scene graph. Thus an incorrect
relation such as <man, riding, wave> is penalized the same as <man, behind,
wave> irrespective of the other relations (<man, on, rock>). However, using
common sense reasoning, we can determine that <man, riding, wave> is highly
improbable given <man, carrying, surfboard> and should be penalized heavily as
opposed to a likely, albeit incorrect, relation behind. Second, due to the
summation over individual relation terms, the model, in order to minimize the
loss, is incentivized to predict relations which are more common in the
training data.

While prior works have tried to address the issue of biased predictions [14,
21] in the context of scene graph generation, little progress has been made
towards structured learning of scene graphs. In this work, we address both of
these issues by proposing a novel generic loss formulation that incorporates
the structure of scene graphs into the learning framework using an energy-
based learning framework. This energy-based framework relies on graph message
passing algorithm for energy computation, that is learned to model the joint
conditional density of a scene graph, given an image. Such a formulation
transforms the problem from maximizing sum of the individual likelihood terms
to that of directly maximizing the joint likelihood of the objects and
relations. Furthermore, this added structure acts as an inductive bias for the
learning, allowing the model to efficiently learn relationship statistics from
less data.

The proposed learning framework is general and hence can be used to train any
off-the-shelf scene graph generation model. We experiment with various state-
of-the-art models and demonstrate that our energy-based formulation achieves
significant improvements in the performance over the corresponding models
trained using the standard cross-entropy based formulation. We also
demonstrate the enhanced generalization capability of models trained using our
framework by evaluating zero shot relation retrieval performance. Finally, we
demonstrate the ability of our energy-based framework to learn from lesser
amounts of training data by demonstrating an improvement in relative
performance when evaluating on few-shot relation triplets.

Figure 1 (c), shows the scene graph generated by the proposed method. The
generated scene graph is more granular, predicting relations such as <man,
standing on, rock> as opposed to the biased and generic variant <man, on,
rock>. The model is also able to preclude improbable relations (, <man,
riding, wave>) and instead predicts in front of between man and wave.

Contribution: Our main contribution is a novel energy-based framework for
scene graph generation that allows for direct incorporation of structure into
the learning. We also propose a novel message passing algorithm that is used
for computing the energy of scene graph configurations. This message passing
algorithm is generic and can be used for other applications such as learning
graph embeddings. Finally, we demonstrate the efficacy of our proposed
framework by applying it to multiple state-of-the-art models and evaluating
performance on two benchmark datasets - Visual Genome [9] and GQA [5] \- where
we consistently outperform the cross-entropy based counterparts by up to
$21\%$ on Visual Genome and $27\%$ on GQA.

##  2 Related Work

Scene Graph Generation: Scene Graph generation has become increasingly popular
in the vision community [8, 12, 14, 17, 21, 26, 27, 29, 30, 31]. Early works,
, [26, 27, 31], focused on improving context aggregation modules that
facilitated learning better representations, thereby improving performance.
Recent works, [8, 14, 32], identify the shortcomings of training using cross-
entropy loss and propose handcrafted loss formulations to improve the
performance. Our work can be considered as a generalization of the latter,
where we allow the model to learn an approximate joint distribution over the
scene graphs and images using an energy based formulation. Furthermore, to the
best of our knowledge, our work is the first to incorporate structure in the
output space, into the learning paradigm.

Energy Based Modeling: Energy Based Models(EBM) learn the unnormalized density
of the data space, thereby avoiding the need to compute the partition function
[10]. EBMs have recently sparked interest in generative modeling. One line of
work uses energy models to learn the underlying data distribution and then
implicitly generates samples from the learned distribution [1, 2]. In [19],
they propose denoising score matching based training, where the model learns
to generate data by denoising progressively increasing noisy signals. While
there has been an increase in the use of energy-based modeling for generative
tasks, they have been relatively unexplored for discriminative tasks. In our
work, we show how one can formulate a discriminative task of scene graph
generation using an EBM framework.

##  3 Approach

We first provide an overview of current approaches for scene graph generation
based on the standard cross entropy loss, followed by a description of our
proposed energy-based learning framework along with the architecture used for
energy computation.

Figure 2: Model Overview of the Energy-based Learning. The region in light
blue correspond to most traditional scene graph generation pipelines. The
proposed energy-based learning framework is highlighted in light green. We
initialize the image graph with the extracted object proposal features as the
node states. We instantiate the scene graph with predictions from traditional
pipeline (or ground truth annotation). The image graph and scene graph are fed
into the energy model where they undergo state refinement using a Gated Graph
Neural Network and a novel Edged Graph Neural Network, respectively. We then
obtain vector representations of each graph using pooling layers. The
representations are concatenated and passed as input to a multi-layer
perceptron which predicts the energy of the joint input (image) - output
(scene graph) configuration. The loss is computed from the energy values of
the ground truth and predicted configuration.

###  3.1 Scene Graph Generation

Scene graph generation methods typically adopt a two stage framework. In the
first stage, given an image $\mathcal{I}$, bounding boxes are obtained using a
standard object detector such as Faster R-CNN [18]. Features corresponding to
these regions are extracted using RoIAlign along with an initial distribution
over object labels. In the next stage, these detections are used as inputs to
predict the scene graphs. The bounding-box features along with the object
label and the spatial coordinates of the bounding boxes are used to initialize
a set of node features. These features are refined using architectures such as
LSTM [31], TreeLSTM [22] or Graph Attention Networks [27], to incorporate
contextual information. Object labels, $\mathbf{O}$, are then obtained by
classifying the refined features. Relationship labels, $\mathbf{R}$, are
obtained by extracting features from union of object bounding boxes, followed
by state refinement using BiLSTMs [31] or BiTreeLSTMs [22] and subsequent
classification.

These models are trained using standard cross-entropy loss on object and
relation labels. Each object and relationship is considered in isolation when
computing individual losses, which are then summed up to obtain the loss for
the given image. Such a loss formulation ignores the fact that objects and
relations in a scene graph are inter-dependent. Intuitively, incorporating
such dependencies into the learning procedure should lead to an improvement in
performance. However, it is not clear as to how one can exploit the rich
structure in the output space. Most methods ([22, 26, 27, 31]) attempt to find
a way around this by employing message passing algorithms in the input space
that allow for aggregation of context information. However, this does not
explicitly consider structure in the output space; neither in predictions, nor
in the loss function used for learning. In this work, we propose a novel
energy-based learning framework that allows scene graph generation models to
be trained using a “loss” that explicitly incorporates structure in the output
space.

###  3.2 Energy Based Modeling

Energy-based models [10] encode dependencies between variables by assigning a
scalar energy value to an input configuration. Given a data point
$\mathbf{x}\in\mathcal{X}$ with corresponding label
$\mathbf{y}\in\mathcal{Y}$, let
$E_{\theta}(\mathbf{x},\mathbf{y})\in\mathbb{R}$ be a joint energy function.
While energy models map inputs to unnormalized densities, we can define a
probability distribution via the Boltzmann distribution,
$p_{\theta}(\mathbf{x},\mathbf{y})=\frac{\exp(-E_{\theta}(\mathbf{x},\mathbf{y}))}{Z(\theta)}$,
where $Z(\theta)=\int\exp(-E_{\theta}(\mathbf{x},\mathbf{y}))$ is referred to
as the normalization constant or partition function. Computing the
normalization constant, $Z_{\theta}$ for most parameterizations of the energy
function is intractable. Therefore, learning the parameters $\theta$ using
methods such as maximum likelihood is not straightforward. Most methods
address this problem by rewriting the derivative of the log likelihood as
$\nabla_{\theta}\log
p_{\theta}(\mathbf{x},\mathbf{y})=\mathbb{E}_{p_{\theta}(\mathbf{x^{\prime}},\mathbf{y^{\prime}})}[\nabla_{\theta}E_{\theta}(\mathbf{x},\mathbf{y^{\prime}})]-\nabla_{\theta}E_{\theta}(\mathbf{x},\mathbf{y}),$
where the expectation is approximately estimated using MCMC methods that
sample from the data distribution.

Unlike most prior works that train energy models for generative modeling, our
focus is scene graph generation, a discriminative task. For such a task, we
are only concerned with the relative energies of the various label
configurations given an input $\mathbf{x}$. Training with a carefully crafted
loss function circumvents the need for estimating the partition function or
computing expectations. Therefore we can parametrize the energy function using
an arbitrary neural network architecture. For a more detailed discussion on
energy loss formulation refer to Section 2 in [11].

###  3.3 Energy Models for Scene Graphs Generation

We now describe our proposed energy-based learning framework for scene graph
generation. In our formulation of the energy function, the data space
$\mathcal{X}$ is the set of images $\mathcal{I}\in\mathbb{R}^{W\times H\times
3}$ and the label space $\mathcal{Y}$ is the set of scene graphs $SG$. The
scene graph, $SG$, is defined by a tuple $(\mathbf{O},\mathbf{R})$, where
$\mathbf{O}\in\mathbb{R}^{n\times d}$ is the set of object labels and
$\mathbf{R}\in\mathbb{R}^{n\times n\times d^{\prime}}$ is the set of
relationship labels; $n$ is the number of objects in an image; $d$ and
$d^{\prime}$ is the total number of possible object and relation labels in the
dataset.

A simple implementation of the joint energy function, would take an encoding
of the image, $\mathcal{I}$, and a scene graph, $SG$, and produce an scalar
energy value. However, there are a few challenges with this. First, a simple
global CNN-based encoding of the image may fail to highlight, potentially
small, regions relevant for scene graph prediction. Second, scene graph
representation is variable in length ($n$ is not fixed) and high dimensional.
The second challenge can be addressed by pooling object $\mathbf{O}$ and
relations $\mathbf{R}$ across $n$ and $n\times n$ dimensions respectively. We
propose a more sophisticated and effective scene graph refinement and gated
pooling formulation in Section 3.4. To facilitate the former challenge of
image encoding, we extract a graph based representation from the image. This
representation is henceforth referred to as an image graph
($\mathsf{G}_{\mathcal{I}}$). The nodes of the image graph are instantiated
using features extracted from the object bounding boxes.

Given a scene graph generation model $M$ and an image $\mathcal{I}$, we
predict a scene graph, $\mathsf{G}_{SG}^{0}$ and compute the image graph
$\mathsf{G}_{\mathcal{I}}$. The scene graph along with the image is provided
as input to the energy model ($E_{\theta}$) to compute the energy
corresponding to the predicted configuration. Similarly, we compute the energy
of the ground truth configuration using the ground truth scene graph
($\mathsf{G}_{SG}^{+}$) and image graph ($\mathsf{G}_{\mathcal{I}}^{+}$)
constructed from ground truth bounding boxes. These two energy values are then
used to compute the energy loss

$\mathcal{L}_{e}=E_{\theta}(\mathsf{G}_{\mathcal{I}}^{+},\mathsf{G}_{SG}^{+})-\min_{\mathsf{G}_{SG}\in
SG}E_{\theta}(\mathsf{G}_{\mathcal{I}},\mathsf{G}_{SG}).$ (2)

Computing this loss requires solving an optimization problem to find a scene
graph configuration that minimizes the energy value (second term in Eq.(2)).
Starting from $\mathsf{G}_{SG}^{0}$ we use Stochastic Gradient Langevine
Dynamics (SGLD) [24] which approximately solves the optimization problem in an
iterative manner:

$\displaystyle\mathbf{O}^{\tau+1}$
$\displaystyle=\mathbf{O}^{\tau}-\frac{\lambda}{2}\nabla_{\mathbf{O}}E_{\theta}(\mathsf{G}_{\mathcal{I}},\mathsf{G}_{SG}^{\tau})+\epsilon^{\tau},$
$\displaystyle\mathbf{R}^{\tau+1}$
$\displaystyle=\mathbf{R}^{\tau}-\frac{\lambda}{2}\nabla_{\mathbf{R}}E_{\theta}(\mathsf{G}_{\mathcal{I}},\mathsf{G}_{SG}^{\tau})+\epsilon^{\tau}$
(3)

where $\mathbf{O}^{t}$ and $\mathbf{R}^{t}$ are the node and edge states in
the scene graph and $\epsilon^{t}$ is sampled from a normal distribution
$\mathcal{N}(0,\lambda)$.

Conceptually, the predicted $\mathsf{G}_{SG}^{0}$ is used as an
“initialization” to arrive at the low energy configuration through a series of
steps defined by Eq.(3); each step similar to regular gradient descent with an
added Gaussian noise. Differentiation through the optimization path guides
parameter learning of the model $M$ that generates $\mathsf{G}_{SG}^{0}$ in
the first place.

When training using the above loss, we observe that the energy values get
arbitrarily large in magnitude leading to gradient overflow. We address this
problem by adding an $L2$ regularization loss on the energy values:

$\mathcal{L}_{r}=E_{\theta}(\mathsf{G}_{\mathcal{I}}^{+},\mathsf{G}_{SG}^{+})^{2}+E_{\theta}(\mathsf{G}_{\mathcal{I}},\mathsf{G}_{SG})^{2}.$
(4)

Finally, since the space of scene graphs is very high dimensional, we need to
restrict the search space of the energy model in order to stabilize the
learning. This is done by incorporating the task loss used by the underlying
scene graph generation model, $\mathcal{L}_{t}$ on the predicted output as an
added regularization on the initial prediction. The total loss for training
the scene graph generator and the the energy model is given by:

$\mathcal{L}_{total}=\lambda_{e}\mathcal{L}_{e}+\lambda_{r}\mathcal{L}_{r}+\lambda_{t}\mathcal{L}_{t},$
(5)

where $\lambda_{e}$, $\lambda_{r}$ and $\lambda_{t}$ are the relative weights.

###  3.4 Energy Model Architecture

Given an image graph ($\mathsf{G}_{\mathcal{I}}$) and a scene graph
($\mathsf{G}_{SG}$), the energy model first refines the state representations
using graph neural networks. We use a novel Edged Graph Neural Networks (EGNN)
and Graph Neural Network [13] on the scene graph and image graph respectively
to incorporate contextual information. This is followed by applying a pooling
layer on each graph to obtain a vector representation summarizing the graph
states. Finally, these two vectors are fed into a multi layer perceptron (MLP)
to compute the energy value corresponding to the predicted scene graph
configuration. We then repeat these operations for the ground truth scene
graph and the input image. The energy model can be parametrized as:

$\displaystyle E_{\theta}(\mathsf{G}_{\mathcal{I}},\mathsf{G}_{SG})$
$\displaystyle=\mathsf{MLP}\left[f(\mathtt{EGNN}(\mathsf{G}_{SG}));g(\mathtt{GNN}(\mathsf{G}_{\mathcal{I}}))\right],$
(6)

where $f$ and $g$ are pooling functions.

Notation. We use $\mathbf{n}_{i}$ to represent the features of the $i^{th}$
node, which for $\mathsf{G}_{SG}$ corresponds to the $i^{th}$ object,
initialized to the corresponding $i^{th}$ row of matrix $\mathbf{O}$. For
$\mathsf{G}_{\mathcal{I}}$ $\mathbf{n}_{i}$ corresponds to the $i^{th}$ image
region, initialized by the RoIAlign image features. We use
$\mathbf{e}_{i\rightarrow j}$ to represent the feature of the directed edge
from node $i$ to $j$, initialized to $(i,j)^{th}$ column of $\mathbf{R}$.
$\mathcal{N}_{i}$ denotes the neighbours of node ${i}$.

####  3.4.1 Edge Graph Neural Network

To allow for direct application of convolution operations on graph
representations accommodating edge features such as scene graphs, we propose a
variant of graph message passing algorithm. For each node $\mathbf{n}_{i}$, we
aggregate the message from neighbouring node and edges by

$\displaystyle\mathbf{m}_{i}^{t}$
$\displaystyle=\alpha\underbrace{\mathbf{W}_{nn}\left(\sum_{j\in\mathcal{N}_{i}}\mathbf{n}_{j}^{t-1}\right)}_{\text{node
to node
message}}+(1-\alpha)\underbrace{\mathbf{W}_{en}\left(\sum_{j\in\mathcal{N}_{i}}\mathbf{e}_{j\rightarrow
i}^{t-1}\right)}_{\text{edge to node message}},$ (7)

where $\mathbf{W}_{nn}$ and $\mathbf{W}_{en}$ are the kernel matrices for
node-to-node and node-to-edge communication and $0\leq\alpha\leq 1$ is a
hyper-parameter that controls the contribution of messages from edges and
nodes. Similarly, the message passing for edges are given by

$\displaystyle\mathbf{d}_{i\rightarrow j}^{t}$
$\displaystyle=\mathbf{W}_{ee}[\mathbf{n}_{i}^{t-1}\mathbin{\|}\mathbf{n}_{j}^{t-1}],$
(8)

where $\mathbf{W}_{ee}$ is the kernel matrix for node-to-edge communication.
Note that the message passing for edges is direction aware i.e.
$\mathbf{d}_{i\rightarrow j}\neq\mathbf{d}_{j\rightarrow i}$. This is crucial
as the relationship between two nodes change depending on direction of the
edge for example <cat, has, tail> and <tail, on, cat>. The incoming messages
are combined with the states using a gating mechanism [13].

####  3.4.2 Pooling Layer

We use gated pooling layers to generate vector representations of the two
graphs. The pooling operation is given by

$\displaystyle\mathbf{N}$
$\displaystyle=\sum_{k}f_{gate}(\mathbf{n}_{k})\odot\mathbf{n}_{k}$ (9)
$\displaystyle\mathbf{E}$
$\displaystyle=\sum_{ij}g_{gate}(\mathbf{e}_{i\rightarrow
j})\odot\mathbf{e}_{i\rightarrow j}$ (10)

where $f_{gate}$ and $g_{gate}$ are gating functions that map node and edge
states to a scalar and $\odot$ represents element-wise multiplication. These
two vectors are then passed through a linear layer, after concatenation, to
obtain the final vector representation of the graph. In the image graph
$\mathsf{G}_{\mathcal{I}}$, since there are no edge features, we use the
pooled node vector $\mathbf{N}$ as the vector representation of the graph.

|  |  | Predicate Classification | Scene Graph Classification | Scene Graph Detection
---|---|---|---|---|---
Dataset | Model | Method | mR@20 | mR@50 | mR@100 | mR@20 | mR@50 | mR@100 | mR@20 | mR@50 | mR@100
Visual Genome | VCTree [22] | Cross Entropy | 13.07 | 16.53 | 17.77 | 8.5 | 10.53 | 11.24 | 5.31 | 7.16 | 8.35
EBM-Loss | 14.2 | 18.19 | 19.72 | 10.4 | 12.54 | 13.45 | 5.67 | 7.71 | 9.1
Motif [31] | Cross Entropy | 12.45 | 15.71 | 16.8 | 6.95 | 8.85 | 9.05 | 5.07 | 6.91 | 8.12
EBM-Loss | 14.17 | 18.02 | 19.53 | 8.18 | 10.22 | 10.98 | 5.66 | 7.72 | 9.27
IMP [26] | Cross Entropy | 8.85 | 10.97 | 11.77 | 5.4 | 6.4 | 6.74 | 2.2 | 3.29 | 4.14
EBM-Loss | 9.43 | 11.83 | 12.77 | 5.66 | 6.81 | 7.17 | 2.78 | 4.23 | 5.44
VCTree-TDE [21] | Cross Entropy | 16.3 | 22.85 | 26.26 | 11.85 | 15.81 | 17.99 | 6.59 | 8.99 | 10.78
EBM-Loss | 19.87 | 26.66 | 29.97 | 13.86 | 18.2 | 20.45 | 7.1 | 9.69 | 11.6
GQA | Transformer [23] | Cross Entropy | 1.17 | 2.48 | 3.69 | .54 | .97 | 1.29 | - | - | -
EBM-Loss | 1.28 | 2.94 | 4.71 | .68 | 1.32 | 1.77 | - | - | -
Motif [31] | Cross Entropy | .85 | 1.8 | 2.75 | .42 | .81 | 1.18 | - | - | -
EBM-Loss | .94 | 2.1 | 3.19 | .57 | .9 | 1.26 | - | - | -
IMP [26] | Cross Entropy | .5 | .94 | 1.32 | .28 | .5 | .65 | - | - | -
EBM-Loss | .57 | 1.07 | 1.5 | .34 | .58 | .76 | - | - | -

Table 1: Quantitative Results. We compare the proposed energy-based loss
formulation against traditional cross-entropy loss using various state-of-the-
art models. We report the mean Recall@K [22] under all three experimental
setting.

##  4 Experiments

We present experimental results on two datasets: the Visual Genome dataset [9]
and the GQA dataset [5].

Visual Genome: We use the pre-processed version of the dataset from [26]. The
dataset consists of 108k images and contains 150 object categories and 50
predicate categories We use the original split with $70\%$ of the images in
the training set and the remaining $30\%$ in the test set, with $5$k images
from the training set held out for validation [31].

GQA: The GQA dataset [5] is also constructed from images in the Visual Genome
dataset. Starting from the scene graph annotations provided in Visual Genome,
a normalization process is applied. This normalization process augments object
and relation annotations and prunes inaccurate or unnatural relations. The
resulting dataset contains a total of $1704$ object categories, $311$ relation
categories We use the same $70-30$ split for the train and the test set, with
$5$k images in the validation set. Compared to Visual Genome, the GQA dataset
has denser graphs with a larger number of object and relation categories.

###  4.1 Scene Graph Generation Models

The energy-based training introduced in this paper is generic and does not
make any assumptions on the underlying scene graph generation model. This
allows freedom in choosing the model architecture for image to scene graph
mapping. On the Visual Genome dataset, we experiment with VCTree [22], Neural
Motifs [31] and Iterative Message Passing [26]. We also experiment with
VCTree-TDE [21], where the inference involves counterfactual reasoning. On the
GQA dataset, we experiment with Transformers [23], instead of VCTree, as the
larger number of object classes in the GQA dataset leads to considerably
larger memory requirement in VCTree. The ability to experiment with different
models demonstrates the versatility of our approach.

###  4.2 Evaluation

Relationship Recall (RR). We use the mean Recall@K (mR@K) metric [22] to
evaluate the performance of the scene graph generation models. We report the
mean Recall@K instead of the Regular Recall@K (R@K) due to data imbalance that
leads to reporting bias as pointed out in recent works [21]. The evaluation is
performed under three settings, (1) Predicate Classification (PredCls):
Predict the relationship labels, given the image, object bounding boxes and
object labels. (2) Scene Graph Classification (SGCls): Predict the object and
predicate labels, given the image and bounding boxes and (3) Scene Graph
Detection (SGDet): Predict the scene graph from the image.

Zero-Shot Recall (zsR@K). Introduced in [15], zsR@K evaluates the ability to
identify subject-predictae-object relation triplets that were not observed
during training. We compute zsR@K for 3 settings: PredCls, SGCls and SGDet.

Few-Shot Recall. We introduce the few-shot Recall@K (fsR@K) metric that
reports the Recall@K for relation triplets that occur a certain number of
times in the training set. Unlike the conventional few shot metric, we use a
range of values to generate the few shot triplet splits. Thus instead of
splitting the triplets into $1$-shot, $2$-shot, , we split them into groups of
$1-5$-shot, $6-10$-shot, with triplets in a $k_{1}-k_{2}$-shot occurring
between $k_{1}$ and $k_{2}$ times.

Sentence-to-Graph Retrieval (S2GR): Introduced in [21], S2GR was designed to
address the inability of RR (Relationship Recall) and zsR (Zero-Shot Recall)
to capture graph level coherence. In S2GR, the scene graph predicted for an
image (obtained in the SGDet setting) is used as a semantic representation of
the image. The task then is to retrieve images using their graph
representation, with the image caption as a query. Note that retrieval task is
based solely on the detected scene graph and no other visual information. As a
consequence, any bias in the scene graph generation will result in a decrease
in the S2GR performance. Similar to [21], we report Recall@20/100 on 1k/5k
gallery.

###  4.3 Implementation Details

Detector. We pre-train a Faster R-CNN [18] with ResNeXt-101-FPN [16, 25]
backbone and freeze the weights of the network prior to scene graph generation
training. We obtain the weights of the pre-trained detector for Visual Genome
from [20]. For GQA, we pre-train the object detector using standard Faster-
RCNN settings. The object detector has $28$ mAP on Visual Genome and $10$ mAP
on GQA.

Scene Graph Generator. The baseline models, trained with standard cross
entropy loss, as well as our proposed framework, are trained using an
identical setup. We use an SGD optimizer with an initial learning rate of
$10^{-2}$. For the Visual Genome models, we incorporate frequency bias [31]
into the training and inference. We do not use the frequency bias on GQA
dataset, due to high memory requirements.

Energy Model. In the sampling step of SGLD (Eq. 3), we set the number of
iterations ($\tau$) to $20$ and the number of message passing iterations in
EGNN and GNN to $3$. We use a step size of $1$ and clip the gradients within
$[-0.01,0.01]$. After every gradient update step, we normalize the node and
edge states of the scene graph to the range of $[0,1]$.

Sentence-to-Graph Retrieval. We use the same formulation for S2GR as previous
work [21]. The problem is formulated as a graph matching problem where the
image caption is converted to graph structure using [9]. The scene graphs and
text graphs are mapped into a joint embedding space for retrieval using a
Bilinear Attention Network [7].

|  |  | PredCls | SGCls | SGDet
---|---|---|---|---|---
Dataset | Model | Method | zsR@20/50 | zsR@20/50 | zsR@20/50
VG | VCTree | CE | 1.43/4 | .39/1.2 | .19/.46
EB | 2.25/5.36 | .87/1.87 | .21/.54
Motif | CE | 1.28/3.56 | .39/.83 | 0/.04
EB | 2.07/4.87 | .52/1.25 | .11/.23
IMP | CE | 12.17/17.66 | 2.09/3.3 | .14/.39
EB | 12.6/18.6 | 2.29/3.7 | .16/.43
VCTree-TDE | CE | 8.98/14.52 | 3.16/4.97 | 1.47/2.3
EB | 9.58/15.14 | 4.18/6.38 | 1.62/2.68
GQA | Transformer | CE | 19.55/33.33 | .94/1.83 | -
EB | 20.11/34.33 | 1.2/2.05 | -
Motif | CE | 17.74/30.61 | 1.27/2.16 | -
EB | 19.47/33.45 | 1.49/2.48 | -
IMP | CE | 15.58/27.6 | 1.02/1.88 | -
EB | 16.65/27.77 | 1.1/1.98 | -

Table 2: Zero-shot Recall. The zero shot recall performance comparison of
model trained using cross-entopy (CE) and energy-based loss (EB) on the Visual
Genome (VG) and GQA dataset.

##  5 Experimental Results

Quantitative Results: Table 1 compares performance of various state-of-the-art
methods trained using cross-entropy and our energy-based loss on two datasets,
Visual Genome and GQA. We observe that training using the proposed energy loss
leads to a consistent improvement in the the mean Recall in all three tasks,
for all the models. For the VCTree model we obtain a relative improvement of
$12.7\%$, $22.3\%$ and $5.6\%$ on mR@$20$ for PredCls, SGCls and SGDet
respectively when compared to cross entropy based training. We obtain relative
improvements of similar magnitudes with the Motif, IMP and VCTree-TDE models.
In addition, using our proposed method with the VCTree-TDE [21] model, we
achieve the new state-of-the-art performance on the Visual Genome dataset. On
the GQA dataset, we present results of three models, Transformer, Motif and
IMP. Similar to the Visual Genome dataset, we observe a consistent improvement
in the mean Recall metric under PredCls and SGCls, with each of the models. We
omit experiments on SGDet task due to low mAP of the underlying object
detector. The proposed method leads to a relative improvement of $8.5\%$ and
$25.92\%$ in the mR@$20$ metric for the PredCls and SGCls task when using the
Transformer model for scene graph generation. The absolute performance on the
GQA dataset is lower, compared to Visual Genome dataset due to larger number
of object and relationship classes. Due to memory constraints, we omit the
frequency prior on the GQA dataset, which was shown to be highly effective on
the Visual Genome dataset [31].

We provide additional results along with individual relation recall in the
supplementary material. We observe that energy-based models obtain larger
improvement in relations that have fewer training annotations, compared to
their cross-entropy based counterparts.

Zero-Shot Recall: Table 2 reports zero-shot recall (zsR@$20$ and zsR@$50$) for
all models. Similar to mR@K, we note consistent improvement on the zero-shot
recall. We attribute this behaviour to our energy-based structure aware
framework, which facilitates learning of models that are capable of performing
global scene graph reasoning.

Few-shot Recall: In Section 1, we hypothesized that the energy based learning
bakes an inductive bias into the learning, thereby allowing the models to
learn from less amounts of data. To test this hypothesis, we measure the few-
shot Recall@$20$ for the VCTree model. We train a scene graph detection model
using the proposed energy-based model as well as the standard cross-entropy
loss. The result, as shown in Table 3, demonstrate that our training framework
is able to provide a significant boost in performance in few-shot scenarios,
when less data is available. This shows that the energy formulation provides a
data efficient method for learning scene graph generation.

| Few-Shot Recall@20
---|---
$k_{1}-k_{2}$ shot | 1-5 | 6-10 | 11-15 | 16-20 | 20-25
C.E. | 16.9 | 24.41 | 27.73 | 31.52 | 32.31
E.B.M. | 18.55 | 25.22 | 28.1 | 32.05 | 32.57
Table 3: Few-shot Recall@20. Table compares the few short recall performance
of a VCTree [22] model trained using cross-entropy and energy-based loss. We
observe larger improvement in performance when data is scarce.

Sentence to Graph Retrieval
---
Gallery Size | 1000 | 5000
|  | R@20 | R@50 | R@100 | R@20 | R@50 | R@100
VCTree | CE | 14 | 28.4 | 44.6 | 4.1 | 8.9 | 14.98
EBM | 17.2 | 32.5 | 48.6 | 5 | 10.96 | 18.52
Motif | CE | 15.5 | 29.4 | 46.7 | 4.56 | 9.7 | 17
EBM | 19.2 | 32 | 49.2 | 5.22 | 10.96 | 18.64

Table 4: Sentence to Graph Retrieval. We compare the scene graph retrieval performance on gallery of $1000$ and $5000$ images. | Predicate Classification
---|---
Ablation | mR@20 | mR@50 | mR@100
0-steps | 14.18 | 18.14 | 19.66
20-steps | _14.2_ | _18.19_ | _19.72_
40-steps | 14.37 | 18.18 | 19.81
60-steps | 14.41 | 18.23 | 19.79
120-steps | 14.59 | 19.29 | 20
No-Image-Graph | 14.19 | 18.05 | 19.55
Table 5: Ablation. We experiment with the number of optimization steps
($\tau$) needed to estimate the energy loss and the effect of excluding image
information in the energy model. All numbers were obtained using a VCTree [22]
model. Figure 3: Qualitative Results. Visualizations of scene graphs generated
by a VCTree [22] model trained using cross-entropy loss (in purple) and
proposed energy-based loss (in green). The top two rows show visualization of
relation retrieval. The bottom row shows zero-shot relation retrieval results
with the zero shot triplet show in yellow.

Sentence-to-Graph Retrieval: Table 4 compares the results of sentence-to-graph
retrieval experiments. We use VCTree and Motif as our scene graph generation
architecture. For each model we observe relative improvements ranging from
5%-23% in the retrieval recall compared to the scene graphs generated using
corresponding baselines. This improvement in performance can be attributed to
the more coherent and informative scene graphs generated by models trained
using the proposed framework.

Ablation Studies: We investigated the impact of optimization in Eq.(2) on the
effectiveness of the energy model. We experimented with a different number of
optimization steps while training a predicate classification model using
VCTree. Note that increasing the number of iterations corresponds to a more
precise minima. We also investigated the effect of removing the image graph
input to the energy model to determine the effectiveness of modeling the
energy density over the joint space of scene and image graph. Table 5
summarizes the mean recall@K for both of these experiments. We find that with
an increase in the number of optimization steps in the energy loss, the mean
recall almost consistently increases. Intuitively, this is expected as a
larger number of optimization steps means that we have better chance of
convergence when trying to find the minima in Eq.(2). This increase, however,
comes with the added computation overhead and increase in training time.
Similarly, we note that removing the image information from the joint
modeling, there is a drop in performance as the model is now forced to learn
from only the scene graph labels.

Qualitative Results: We visualize the qualitative results obtained from a
VCTree model trained using the proposed energy-based framework as well as
cross-entropy loss in Figure 3. The top two rows show results from the regular
relation retrieval task. We observe that the models trained using our proposed
framework can consistently generate instructive relationships such as mounted
on, parked on, walking on, standing on as opposed to the less informative and
biased variant on generated by the baseline model. Similarly, in the top-left
image, the energy-based training generates spatially informative relations
such as <cat, in front of, door> instead of <cat, near, door> and <cat,
looking at, dog> as opposed <dog, near, cat>.

The bottom row shows results of zero-shot relation retrieval. In the first
image, due to the triplets of elephants with glasses not being present in the
training data, the baseline model predicts <women, wearing, glasses> whereas
our method generates the accurate prediction <elephant, has, glasses>.

##  6 Conclusion

We present a novel model-agnostic energy-based learning framework for training
scene graph generation models. Unlike cross-entropy based training, the
proposed method embraces structure in the output space allowing the model to
perform structure aware learning. We show that scene graph generation models
can benefit from the proposed training framework by performing experiments on
the Visual Genome and GQA datasets. We observe significant improvement in
performance as compared to traditional cross-entropy based training. We also
exhibit the generality and efficiency of our model through experiments in
zero-shot and few-shot relationship settings. Finally, the proposed method
does not make any assumptions on the underlying generation model and can be
easily used with any model.

## References

  * [1] Yilun Du and Igor Mordatch.  Implicit generation and modeling with energy based models.  In Advances in Neural Information Processing Systems, pages 3608–3618, 2019.
  * [2] Will Grathwohl, Kuan-Chieh Wang, Joern-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky.  Your classifier is secretly an energy based model and you should treat it like one.  In International Conference on Learning Representations, 2020.
  * [3] Jiuxiang Gu, Shafiq Joty, Jianfei Cai, Handong Zhao, Xu Yang, and Gang Wang.  Unpaired image captioning via scene graph alignments.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10323–10332, 2019.
  * [4] Roei Herzig, Amir Bar, Huijuan Xu, Gal Chechik, Trevor Darrell, and Amir Globerson.  Learning canonical representations for scene graph to image generation.  In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
  * [5] Drew A Hudson and Christopher D Manning.  Gqa: A new dataset for real-world visual reasoning and compositional question answering.  Conference on Computer Vision and Pattern Recognition (CVPR), 2019\.
  * [6] Justin Johnson, Agrim Gupta, and Li Fei-Fei.  Image generation from scene graphs.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1219–1228, 2018.
  * [7] Jin-Hwa Kim, Jaehyun Jun, and Byoung-Tak Zhang.  Bilinear attention networks.  In Advances in Neural Information Processing Systems, pages 1564–1574, 2018.
  * [8] Boris Knyazev, Harm de Vries, Cătălina Cangea, Graham W Taylor, Aaron Courville, and Eugene Belilovsky.  Graph density-aware losses for novel compositions in scene graph generation.  arXiv preprint arXiv:2005.08230, 2020.
  * [9] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, Michael Bernstein, and Li Fei-Fei.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision, 123(1):32–73, 2017.
  * [10] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang.  A tutorial on energy-based learning.  Predicting structured data, 1(0), 2006.
  * [11] Yann LeCun and Fu Jie Huang.  Loss functions for discriminative training of energy-based models.  In AIStats, volume 6, page 34. Citeseer, 2005.
  * [12] Yikang Li, Wanli Ouyang, Zhou Bolei, Shi Jianping, Zhang Chao, and Xiaogang Wang.  Factorizable net: An efficient subgraph-based framework for scene graph generation.  In Proceedings of the European Conference on Computer Vision (ECCV), 2018.
  * [13] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel.  Gated graph sequence neural networks.  In 4th International Conference on Learning Representations, ICLR, 2016.
  * [14] Xin Lin, Changxing Ding, Jinquan Zeng, and Dacheng Tao.  Gps-net: Graph property sensing network for scene graph generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [15] Cewu Lu, Ranjay Krishna, Michael Bernstein, and Li Fei-Fei.  Visual relationship detection with language priors.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 852–869. Springer, 2016.
  * [16] Francisco Massa and Ross Girshick.  maskrcnn-benchmark: Fast, modular reference implementation of Instance Segmentation and Object Detection algorithms in PyTorch.  https://github.com/facebookresearch/maskrcnn-benchmark, 2018.
  * [17] Alejandro Newell and Jia Deng.  Pixels to graphs by associative embedding.  In Advances in neural information processing systems, pages 2171–2180, 2017.
  * [18] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In Advances in neural information processing systems, pages 91–99, 2015.
  * [19] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  In Advances in Neural Information Processing Systems, pages 11918–11930, 2019.
  * [20] Kaihua Tang.  A scene graph generation codebase in pytorch, 2020.  https://github.com/KaihuaTang/Scene-Graph-Benchmark.pytorch.
  * [21] Kaihua Tang, Yulei Niu, Jianqiang Huang, Jiaxin Shi, and Hanwang Zhang.  Unbiased scene graph generation from biased training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3716–3725, 2020.
  * [22] Kaihua Tang, Hanwang Zhang, Baoyuan Wu, Wenhan Luo, and Wei Liu.  Learning to compose dynamic tree structures for visual contexts.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6619–6628, 2019.
  * [23] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [24] Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient langevin dynamics.  In Proceedings of the 28th international conference on machine learning (ICML-11), pages 681–688, 2011.
  * [25] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1492–1500, 2017.
  * [26] Danfei Xu, Yuke Zhu, Christopher B Choy, and Li Fei-Fei.  Scene graph generation by iterative message passing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5410–5419, 2017.
  * [27] Jianwei Yang, Jiasen Lu, Stefan Lee, Dhruv Batra, and Devi Parikh.  Graph r-cnn for scene graph generation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 670–685, 2018.
  * [28] Xu Yang, Kaihua Tang, Hanwang Zhang, and Jianfei Cai.  Auto-encoding scene graphs for image captioning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10685–10694, 2019.
  * [29] Alireza Zareian, Svebor Karaman, and Shih-Fu Chang.  Bridging knowledge graphs to generate scene graphs.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 606–623. Springer, 2020.
  * [30] Alireza Zareian, Zhecan Wang, Haoxuan You, and Shih-Fu Chang.  Learning visual commonsense for robust scene graph generation.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 642–657. Springer, 2020.
  * [31] Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi.  Neural motifs: Scene graph parsing with global context.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5831–5840, 2018.
  * [32] Ji Zhang, Kevin J Shih, Ahmed Elgammal, Andrew Tao, and Bryan Catanzaro.  Graphical co ntrastive losses for scene graph parsing.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11535–11543, 2019.


# Training Stable Graph Neural Networks
Through Constrained Learning

###### Abstract

Graph Neural Networks (GNN) rely on graph convolutions to learn features from
network data. GNNs are stable to different types of perturbations of the
underlying graph, a property that they inherit from graph filters. In this
paper we leverage the stability property of GNNs as a typing point in order to
seek for representations that are stable within a distribution. We propose a
novel constrained learning approach by imposing a constraint on the stability
condition of the GNN within a perturbation of choice. We showcase our
framework in real world data, corroborating that we are able to obtain more
stable representations while not compromising the overall accuracy of the
predictor.

Index Terms—  Graph Neural Networks, Constrained Learning, Stability

##  1 Introduction

Graph Neural Networks (GNNs) are deep convolutional architectures tailored to
graph machine learning problems [1, 2] which have achieved great success in
fields such as biology [3, 4] and robotics [5, 6], to name a few. Consisting
of layers that stack graph convolutions and pointwise nonlinearities, their
successful empirical results can be explained by theoretical properties they
inherit from graph convolutions. Indeed, convolutions are the reason why GNNs
are invariant to node relabelings [7, 8]; stable to deterministic [2],
stochastic [9], and space-time graph perturbations [10]; and transferable from
small to large graphs [11].

Stability is an especially important property because, in practice, networks
are prone to perturbations. For instance, in a social network, friendship
links can not only be added or removed, but also strengthened or weakened
depending on the frequency of interaction. Similarly, in a wireless network
the channel states are dramatically affected by environment noise. Because
GNNs have been proved to be stable to such perturbations, in theory any GNN
should do well in these scenarios. In practice, however, actual stability
guarantees depend on factors such as the type of graph perturbation, the
smoothness of the convolutions, the depth and width of the neural network, and
the size of the graph [12]. In other words, GNNs are provably stable to graph
perturbations, but we cannot always ensure that they will meet a certain
stability requirement or constraint. In improve stability, other works have
focused on making GNNs more robust. Some works enforce lipschitz constraints
[13], other arts focus on the architecture of the GNN to make it more robust
[14], and others focus on removing noise [15].

In this paper, our goal is thus to enforce GNNs to meet a specific stability
requirement, which we do by changing the way in which the GNN is learned.
Specifically, we modify the statistical learning problem by introducing GNN
stability as a constraint, therefore giving rise to a constrained statistical
learning problem. This leads to an non-convex constrained problem for which
even a feasible solution may be may challenging to obtain in practice. To
overcome this limitation, we resort to the dual domain, in which the problem
becomes a weighted unconstrained minimization problem that we can solve using
standard gradient descent techniques. By evaluating the constraint slackness,
we iteratively update the weights of this problem. This procedure is detailed
in Algorithm 1. In Theorem 1, we quantify the duality gap, i.e., the mismatch
between solving the primal and the dual problems. In Theorem 2, we present
convergence guarantees for Algorithm 1. These results are illustrated
numerically in Section 4, where we observe that GNNs trained using Algorithm 1
successfully meet stability requirements for a variety of perturbation
magnitudes and GNN architectures.

##  2 Graph Neural Networks

A graph is a triplet
${\mathbf{G}}=({\mathcal{V}},{\mathcal{E}},{\mathcal{W}})$, where
${\mathcal{V}}=\\{1,\dots,N\\}$ is its set of nodes,
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ is its set of edges,
and ${\mathcal{W}}$ is a function assigning weights ${\mathcal{W}}(i,j)$ to
edges $(i,j)\in{\mathcal{E}}$. A graph may also be represented by the graph
shift operator (GSO) ${\mathbf{S}}\in{\mathbb{R}}^{N\times N}$, a matrix which
satisfies $S_{ij}\neq 0$ if and only if $(j,i)\in{\mathcal{E}}$ or $i=j$. The
most common examples of GSOs are the graph adjacency matrix ${\mathbf{A}}$,
$[{\mathbf{A}}]_{ij}={\mathcal{W}}(j,i)$; and the graph Laplacian
${\mathbf{L}}=\mbox{diag}({\mathbf{A}}\boldsymbol{1})-{\mathbf{A}}$.

We consider the graph ${\mathbf{G}}$ to be the support of data
${\mathbf{x}}=[x_{1},\dots,x_{N}]^{\top}$ which we call graph signals. The
$i$th component of a graph signal ${\mathbf{x}}$, $x_{i}$, corresponds to the
value of the data at node $i$. The operation ${\mathbf{S}}{\mathbf{x}}$
defines a graph shift of the signal ${\mathbf{x}}$. Leveraging this notion of
shift, we define graph convolutional filters as linear shift-invariant graph
filters. Explicitly, a graph convolutional filter with coefficients
${\mathbf{h}}=[h_{1},\dots,h_{K-1}]^{\top}$ is given by

$\displaystyle{\mathbf{y}}={\mathbf{h}}*_{{\mathbf{S}}}{\mathbf{x}}=\sum_{k=0}^{K-1}h_{k}{\mathbf{S}}^{k}{\mathbf{x}}$
(1)

where $*_{{\mathbf{S}}}$ is the convolution operation parametrized by
${\mathbf{S}}$.

GNNs are deep convolutional architectures consisting of $L$ layers, each of
which contains a bank of graph convolutional filters like (1) and a pointwise
nonlinearity $\rho$. Layer $l$ produces $F_{l}$ graph signals
${\mathbf{x}}_{l}^{f}$, called features. Defining a matrix ${\mathbf{X}}_{l}$
whose $f$th column corresponds to the $f$th feature of layer $l$ for $1\leq
f\leq F_{l}$, we can write the $l$th layer of the GNN as

${\mathbf{X}}_{l}=\rho\left(\sum_{k=0}^{K-1}{\mathbf{S}}^{k}{\mathbf{X}}_{l-1}{\mathbf{H}}_{lk}\right)\text{.}$
(2)

In this expression, $[{\mathbf{H}}_{lk}]_{gf}$ denotes the $k$th coefficient
of the graph convolution (1) mapping feature $g$ to feature $f$ for $1\leq
g\leq F_{l-1}$ and $1\leq f\leq F_{l}$. A more succinct representation of this
GNN can be obtained by grouping all learnable parameters ${\mathbf{H}}_{lk}$,
$1\leq l\leq L$, in a tensor ${\mathcal{H}}=\\{{\mathbf{H}}_{lk}\\}_{l,k}$.
This allows expressing the GNN as the parametric map
${\mathbf{X}}_{L}=\phi({\mathbf{X}}_{0},{\mathbf{S}};{\mathcal{H}})$. For
simplicity, in the following sections we assume that the input and output only
have one feature, i.e., ${\mathbf{X}}_{0}={\mathbf{x}}\in{\mathbb{R}}^{N}$ and
${\mathbf{X}}_{L}={\mathbf{y}}\in{\mathbb{R}}^{N}$.

###  2.1 Statistical Learning on Graphs

To learn a GNN, we are given pairs $({\mathbf{x}},{\mathbf{y}})$ corresponding
to an input graph signal ${\mathbf{x}}\in{\mathbb{R}}^{N}$ and a target output
graph signal ${\mathbf{y}}\in{\mathbb{R}}^{N}$ sampled from the joint
distribution $p({\mathbf{x}},{\mathbf{y}})$. Our objective is to find the
filter coefficients ${\mathcal{H}}$ such that
$\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}})$ approximates ${\mathbf{y}}$
over the joint probability distribution $p$. To do so, we introduce a
nonnegative loss function
$\ell:{\mathbb{R}}^{N}\times{\mathbb{R}}^{N}\to{\mathbb{R}}_{+}$ which
satisfies $\ell(\phi({\mathbf{x}}),{\mathbf{y}})=0$ when
$\phi({\mathbf{x}})={\mathbf{y}}$. The GNN is learned by averaging the loss
over the probability distribution as follows,

$\displaystyle\underset{{\mathcal{H}}\in{\mathbb{R}}^{Q}}{\min}$
$\displaystyle\underset{\tiny
p({\mathbf{x}},{\mathbf{y}})}{{\mathbb{E}}}[\ell\left({\mathbf{y}},\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}}),{\mathbf{y}})\right)].$
(3)

Problem 3 is the Statistical Risk Minimization problem [16] for the GNN.

###  2.2 Stability to Graph Perturbations

In the real world, it is not uncommon for graphs to be prone to small
perturbations such as, e.g., interference noise in wireless networks. Hence,
stability to graph perturbations is an important property for GNNs.
Explicitly, we define a graph perturbation as a graph that is $\epsilon$ close
to the original graph,

$\hat{\mathbf{S}}:\ \|\hat{\mathbf{S}}-{\mathbf{S}}\|\leq\epsilon.$ (4)

An example of perturbation is an additive perturbation of the form
$\hat{\mathbf{S}}={\mathbf{S}}+{\mathbf{E}}$, where ${\mathbf{E}}$ is a
stochastic perturbation with bounded norm $\|{\mathbf{E}}\|\leq\epsilon$ drawn
from a distribution $\Delta$.

The notion of GNN stability is formalized in Definition 1. Note that the
maximum is taken in order to account for all possible inputs.

######  Definition 1 (GNN stability to graph perturbations)

Let $\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}})$ be a GNN (2) and let
$\hat{\mathbf{S}}$ be a graph perturbation (4) such that
$\|\hat{\mathbf{S}}-{\mathbf{S}}\|\leq\epsilon$. The GNN
$\phi({\mathbf{X}},{\mathbf{S}};{\mathcal{H}})$ is $C$-stable if

$\displaystyle\max_{{\mathbf{x}}}\|\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}})-\phi({\mathbf{x}},\hat{\mathbf{S}};{\mathcal{H}})\|\leq
C\epsilon$ (5)

for some finite constant $C$.

A GNN is thus stable to a graph perturbation
$\|\hat{\mathbf{S}}-{\mathbf{S}}\|\leq\epsilon$ if its output varies at most
by $C\epsilon$. The smaller the value of $C$, the more stable the GNN is to
perturbations $\hat{\mathbf{S}}$. Under mild smoothness assumptions on the
graph convolutions, it is possible to show that any GNN can be made stable in
the sense of Definition 1 [12]. However, for an arbitrary GNN the constant $C$
is not guaranteed to be small and, in fact, existing stability analyses show
that it can vary with the GNN depth and width (i.e. number of layers $L$, and
number of features $F$ respectively), the size of the graph $N$, and the
misalignment between the eigenspaces of ${\mathbf{S}}$ and $\hat{\mathbf{S}}$.
What is more, problem 3 does not impose any conditions on the stability of the
GNN, thus solutions ${\mathcal{H}}^{*}$ may not have small stability bounds
$C$. In this paper, our goal is to enforce stability for a constant $C$ of
choice. In the following, we show that, on average over the support of the
data, better stability can be achieved by introducing a modification of
definition 1 as a constraint of the statistical learning problem for the GNN.

##  3 Constrained Learning

In order to address the stability of the GNN, we can explicitly enforce our
learning procedure to account for differences between the unperturbed and the
perturbed performance, to do this we resort to the constrained learning theory
[17]. We modify the standard unconstrained statistical risk minimization
problem (cf. (3)) by introducing a constraint that requires the solution
${\mathcal{H}}$ to attain at most an $C\epsilon$ difference between the
perturbed and unperturbed problem.

$\displaystyle P^{*}=\underset{{\mathcal{H}}\in{\mathbb{R}}^{Q}}{\min}$
$\displaystyle\underset{\tiny
p({\mathbf{x}},{\mathbf{y}})}{{\mathbb{E}}}[\ell\left(y,\phi({\mathbf{x}},{\mathbf{S}};{\mathbf{y}})\right)]$
(6) s.t. $\displaystyle\underset{\tiny
p({\mathbf{x}},{\mathbf{y}},\Delta)}{{\mathbb{E}}}[\ell({\mathbf{y}},\phi({\mathbf{x}},\hat{\mathbf{S}};{\mathcal{H}}))-\ell(y,\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}}))]\leq
C\epsilon$

Note that if the constant $C$ is set at a sufficiently large value, the
constraint renders inactive, making problems (6) and (3) equivalent. As
opposed to other methods based on heuristics, or tailored solutions, our novel
formulation admits a simple interpretation from an optimization perspective.

###  3.1 Dual Domain

In order to solve problem (6), we will resort to the dual domain. To do so, we
introduce the dual variable $\lambda>0\in{\mathbb{R}}$, and we define the
Lagrangian function as follows,

$\displaystyle{\mathcal{L}}({\mathcal{H}},\lambda)=$
$\displaystyle(1-\lambda){\mathbb{E}}[\ell({\mathbf{y}},\phi({\mathbf{x}},{\mathbf{S}};{\mathcal{H}})]$
(7)
$\displaystyle+\lambda{\mathbb{E}}[\ell({\mathbf{y}},\phi({\mathbf{x}},\hat{\mathbf{S}};{\mathcal{H}}))-\epsilon
C].$

We can introduce the dual function as the minimum of the Lagrangian
${\mathcal{L}}({\mathcal{H}},\lambda)$, over ${\mathcal{H}}$ for a fixed value
of dual variables $\lambda$ [18],

$\displaystyle
d(\lambda)=\min_{{\mathcal{H}}\in{\mathbb{R}}^{Q}}{\mathcal{L}}({\mathcal{H}},\lambda).$
(8)

Note that to obtain the value of the dual function $d(\lambda)$ we need to
solve an unconstrained optimization problem weighted by $\lambda$. Given that
the dual function is a point wise minimum of a family of affine functions, it
is concave, even when the problem (6) is not convex. The maximum of the dual
function $d(\lambda)$ over $\lambda$ is called the dual problem $D^{*}$, and
it is always a lower bound of problem $P^{*}$ as follows,

$\displaystyle d(\lambda)\leq
D^{*}\leq\min_{{\mathcal{H}}\in{\mathbb{R}}^{Q}}\max_{\lambda\in{\mathbb{R}}^{+}}{\mathcal{L}}(\phi,\lambda)=P^{*}.$
(9)

The advantage of delving into the dual domain, and maximizing the dual
function $d$ is that it allows us to search for solutions of problem 6 by
minimizing an unconstrained problem. The difference between the dual problem
$D^{*}$ and the primal problem $P^{*}$ (cf. 6), is called duality gap and will
be quantified in the following theorem.

###### AS 1

The loss function $\ell$ is $L$-Lipschitz,
i.e.$\|\ell(x,\cdot)-\ell(z,\cdot)\|\leq L\|x-z\|$, strongly convex and
bounded by $B$.

###### AS 2

The conditional distribution $p({\mathbf{x}},\Delta|{\mathbf{y}})$ is non-
atomic for all ${\mathbf{y}}\in{\mathbb{R}}^{N}$, and there a finite number of
target graph signals ${\mathbf{y}}$.

###### AS 3

There exists a convex hypothesis class $\hat{\mathcal{C}}$ such that
${\mathcal{C}}\subseteq\hat{\mathcal{C}}$, and there exists a constant $\xi>0$
such that $\text{for all}\hat{\phi}\in\hat{\mathcal{C}}$, there exists
${\mathcal{H}}\in{\mathbb{R}}^{Q}$ such that
$\sup_{x\in{\mathcal{X}}}\|\hat{\phi}(x)-\phi(x,{\mathcal{H}})\|\leq\xi$.

Note that assumption 1 is satisfied in practice by most loss functions (i.e.
square loss, $L_{1}$ loss), by imposing a bound. Assumption 2 can be satisfied
in practice by data augmentation [19]. Assumption 3 is related to the richness
of the function class of GNNs ${\mathcal{C}}$, the parameter $\xi$ can be
decrease by increasing the capacity of the GNNs in consideration. To obtain a
convex hypothesis class $\hat{\mathcal{H}}$, it suffices to take the convex
hull over the function class of GNNs.

######  Theorem 1 (Near-Zero Duality Gap)

Under assumptions 1, 2, and 3, if the Constrained Graph Stability problem (6)
over $\hat{\mathcal{C}}$ is feasible with constraint slack $\epsilon-\xi$,
then the Constrained Graph Stability problem (6), has near zero duality gap,

$\displaystyle P^{*}-D^{*}\leq(\lambda^{*}+1)L\xi$ (10)

where $\lambda^{*}$ is the optimal dual variable of the non-parametric problem
with constraint slack $\epsilon-\xi$.

The importance of Theorem 1 is that is allows us to quantify the penalty that
we incur by delving into the dual domain. Note that this penalty decreases as
we make our parameterization richer, and thus we decrease $\xi$. Also note
that the optimal dual variable $\lambda^{*}$ accounts for the difficulty of
finding a feasible solution, thus we should expect this value to be small
given the theoretical guarantees on GNN stability [12].

Algorithm 1 Graph Stability Algorithm

1:Initialize model ${\mathcal{H}}^{0}$, and dual variables $\lambda=0$

2:for epochs $e=1,2,\dots$ do

3: for batch $i$ in epoch $e$ do

4: Obtain $N$ samples $\\{({\mathbf{x}}_{i},{\mathbf{y}}_{i})\\}_{i}\sim
p({\mathbf{x}},{\mathbf{y}})$

5: Obtain $M$ perturbations $\\{(\hat{\mathbf{S}}_{i})\\}_{i}\sim\Delta$

6: Get primal gradient
$\nabla_{\mathcal{H}}{\mathcal{L}}({\mathcal{H}},\lambda)$ (cf. eq (11))

7: Update params.
${\mathcal{H}}^{k+1}={\mathcal{H}}^{k}-\eta_{P}\hat{\nabla}_{\mathcal{H}}{\mathcal{L}}({\mathcal{H}}^{k},\lambda)$

8: end for

9: Obtain $N$ samples $\\{({\mathbf{x}}_{i},{\mathbf{y}}_{i})\\}_{i}\sim
p({\mathbf{x}},{\mathbf{y}})$

10: Obtain $M$ perturbations $\\{(\hat{\mathbf{S}}_{i})\\}_{i}\sim\Delta$

11: Update dual variable
$\lambda\leftarrow[\lambda+\eta_{D}\nabla_{\lambda}{\mathcal{L}}({\mathcal{H}},\lambda)]_{+}$

12:end for

###  3.2 Algorithm Construction

| RMSE for $1$ Layer GNN | RMSE for $2$ Layer GNN
---|---|---
Norm Of Perturbation | Unconstrained | Constrained (Ours) | Unconstrained | Constrained (Ours)
$0$ | $0.8631(\pm 0.1056)$ | $\mathbf{0.8696(\pm 0.0940)}$ | $0.8582(\pm 0.1126)$ | $\mathbf{0.8480(\pm 0.1307)}$
$0.0001$ | $0.8631(\pm 0.1056)$ | $\mathbf{0.8420(\pm 0.0884)}$ | $0.8582(\pm 0.1126)$ | $\mathbf{0.8273(\pm 0.1121)}$
$0.001$ | $0.8631(\pm 0.1055)$ | $\mathbf{0.8420(\pm 0.0884)}$ | $0.8586(\pm 0.1128)$ | $\mathbf{0.8273(\pm 0.1122)}$
$0.01$ | $0.8625(\pm 0.1052)$ | $\mathbf{0.8418(\pm 0.0877)}$ | $0.8622(\pm 0.1147)$ | $\mathbf{0.8277(\pm 0.1132)}$
$0.1$ | $0.8631(\pm 0.1025)$ | $\mathbf{0.8473(\pm 0.0807)}$ | $0.9395(\pm 0.1374)$ | $\mathbf{0.8320(\pm 0.1226)}$
$0.2$ | $0.8735(\pm 0.0960)$ | $\mathbf{0.8598(\pm 0.0831)}$ | $1.1228(\pm 0.2291)$ | $\mathbf{0.8483(\pm 0.1342)}$
$0.5$ | $1.0182(\pm 0.1587)$ | $\mathbf{0.9386(\pm 0.1079)}$ | $2.0327(\pm 0.5074)$ | $\mathbf{0.9500(\pm 0.1572)}$
Table 1: Evaluations of the RMSE and variance of the trained GNN for $20$
epochs on the testing set (unseen data) for different magnitudes of relative
perturbations. We consider GNNs of $1$, and $2$ layers with $K=5$ filter taps
and $F_{1}=64$, and $F_{2}=32$ features for the first and second layer
respectively. The constrained learning approach is able to keep a comparable
performance on the unperturbed evaluation (i.e., Norm of Perturbation$=0$)
while it is more stable as the norm of the perturbation increases.

In order to solve problem 6, we will resort to iterativelly solving the dual
function $d(\lambda)$, evaluate the constraint slack and update the dual
variable $\lambda$ accordingly. We assume that the distributions are unknown,
but we have access to samples of both graph signals
$({\mathbf{x}}_{i},{\mathbf{y}}_{i})\sim p({\mathbf{x}},{\mathbf{y}})$, and
perturbed graphs $\hat{\mathbf{S}}_{j}\sim\Delta$. In a standard learning
procedure, to minimize the Lagrangian ${\mathcal{L}}({\mathcal{H}},\lambda)$
with respect to a set of variables $\lambda$ we can take stochastic gradients
as follows,

$\displaystyle\hat{\nabla}_{{\mathcal{H}}}{\mathcal{L}}({\mathcal{H}},\lambda)=$
$\displaystyle\nabla_{{\mathcal{H}}}\bigg{[}\frac{1-\lambda}{N}\sum_{i=1}^{N}\ell(\phi({\mathbf{x}}_{i},{\mathbf{S}};{\mathcal{H}}^{k}),{\mathbf{y}}_{i})$
(11)
$\displaystyle+\frac{\lambda}{NM}\sum_{i=1}^{N}\sum_{j=1}^{M}\ell(\phi({\mathbf{x}}_{i},\hat{\mathbf{S}}_{j};{\mathcal{H}}^{k}),{\mathbf{y}}_{i})\bigg{]}$

The main difference with a regularized problem is that the dual variables
$\lambda$ are also updated. To update the dual variables $\lambda$, we
evaluate the constraint violation as follows,

$\displaystyle\hat{\nabla}_{\lambda}{\mathcal{L}}({\mathcal{H}},\lambda)=$
$\displaystyle\frac{1}{NM}\sum_{i=1}^{N}\sum_{j=1}^{M}\ell(\phi({\mathbf{x}}_{i},\hat{\mathbf{S}}_{j};{\mathcal{H}}^{k}),{\mathbf{y}}_{i})$
$\displaystyle-\frac{1}{N}\sum_{i=1}^{N}\ell(\phi({\mathbf{x}}_{i},{\mathbf{S}};{\mathcal{H}}^{k}),{\mathbf{y}}_{i})-C\epsilon.$
(12)

The intuition behind the dual step is that the dual variable $\lambda$ will
increase while the constraint is not being satisfied, adding weight to the
stability condition in the minimization of the Lagrangian. Conversely, if the
constraint is being satisfied, we will increase the relative weight of the
objective function. This means, that if the constraint is more restrictive the
optimal dual variable will be larger.

######  Theorem 2 (Convergence)

Under assumptions 1, 2, and 3, if for each dual variable $\lambda^{k}$, the
Lagrangian is minimized up to a precision $\alpha>0$, i.e.
${\mathcal{L}}({\mathcal{H}}_{\lambda^{k}},\lambda^{k})\leq\min_{{\mathcal{H}}\in{\mathbb{R}}^{Q}}{\mathcal{L}}({\mathcal{H}},\lambda^{k})+\alpha$,
then for a fixed tolerance $\beta>0$, the iterates generated by Algorithm 1
achieve a neighborhood of the optimal $P^{*}$ problem in finite time

$\displaystyle
P^{*}+\alpha\geq{\mathcal{L}}({\mathcal{H}}^{k},\lambda^{k})\geq
P^{*}-(2\lambda^{*}+1)L\xi-\alpha-\beta-\frac{\eta_{D}B^{2}}{2}$

Theorem (2) allows us to show convergence of Algorithm 1 to a neighborhood of
the optimal problem (6).

##  4 Experiments

We consider the problem of predicting the rating a movie will be given by a
user. We leverage the dataset MovieLens 100k [20] which contains $100,000$
integer ratings between $1$ and $5$, that were collected among $U=943$ users
and $M=1682$ movies. Nodes in this case are movie ratings, and we construct
one graph signal ${\mathbf{x}}_{i}$ per user $i$. Each entry
$[{\mathbf{x}}_{i}]_{j}$ storage the rating that user $i$ gave to movie $j$,
and $0$ if there is no rating. To obtain the edges, we calculate the movie
similarity graph, obtained by computing the pairwise correlations between the
different movies in the training set [21]. In order to showcase the stability
properties of GNNs, we perturb the graph shift operator according to the
Relative Perturbation Modulo Perturbation [12][Definition 3] model
$\hat{\mathbf{S}}={\mathbf{S}}+{\mathbf{E}}{\mathbf{S}}+{\mathbf{S}}{\mathbf{E}}$.
We consider a uniform distribution of ${\mathbf{E}}$ such that,
$\|{\mathbf{E}}\|\leq\epsilon$.

We split the dataset into $90\%$ for training and $10\%$ for testing,
considering $10$ independent random splits. For the optimizer we used a $5$
sample batch size, and ADAM [22] with learning rate
$0.005,\beta_{1}=0.9,\beta_{2}=0.999$ and no learning decay. We used the
smooth $L_{1}$ loss. For the GNNs, we used ReLU as the non-linearity, and we
considered two GNNs: (i) one layer with $F=64$ features, and (ii) two layers
with $F_{1}=64$ and $F_{2}=32$. In both cases, we used $K=5$ filter taps per
filter. For the Algorithm 1 we used dual step size $\eta_{D}=0.05$, stability
constant $C=0.25$, and magnitude of perturbation $\epsilon=0.2$. For number of
perturbation per primal step we used $M=3$, and to evaluate the constraint
slackness we used $20\%$ of the training set.

Table 1 shows the RMSE achieved on the test set when the GNN is trained using
Algorithm 1 and when trained unconstrained for different magnitudes of
perturbations of the graph. The numerical results shown in Table 1 express the
manifestation of the claims that we put forward. First, using Algorithm 1 we
are able to attain a comparable performance to the one we would have achieved
by training ignoring the perturbation. As seen in the first row, the
evaluation of the trained GNNs produces comparable results for both the $1$
and the $2$ layer GNN. Second, with our formulation we are able to obtain more
stable representations because when the perturbation magnitude increases, the
loss deteriorates at a slower rate. This effect is especially noticeable for
the $2$ layer GNN. It is well studied that GNN stability worsens as the number
of layers increases[12, 23], however using Algorithm 1 we are able to curtail
this undesirable effect.

##  5 Conclusion

In this paper we introduced a constrained learning formulation to improve the
stability of GNN. By explicitly introducing a constraint on the stability of
the GNN we are able to obtain filter coefficients that are more resilient to
perturbations of the graph. The benefit of our novel procedure was benchmarked
in a recommendation system problem with real world data.

## References

  * [1] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun,  “Graph neural networks: A review of methods and applications,”  AI Open, vol. 1, pp. 57–81, 2020.
  * [2] Fernando Gama, Antonio G Marques, Geert Leus, and Alejandro Ribeiro,  “Convolutional neural network architectures for signals supported on graphs,”  IEEE Transactions on Signal Processing, vol. 67, no. 4, pp. 1034–1049, 2018.
  * [3] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur,  “Protein interface prediction using graph convolutional networks,”  in Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds. 2017, vol. 30, Curran Associates, Inc.
  * [4] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams,  “Convolutional networks on graphs for learning molecular fingerprints,”  in Advances in Neural Information Processing Systems, C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, Eds. 2015, vol. 28, Curran Associates, Inc.
  * [5] Siyuan Qi, Wenguan Wang, Baoxiong Jia, Jianbing Shen, and Song-Chun Zhu,  “Learning human-object interactions by graph parsing neural networks,”  in Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 401–417.
  * [6] Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok,  “Graph neural networks for decentralized multi-robot path planning,”  arXiv preprint arXiv:1912.06095, 2019.
  * [7] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna,  “On the equivalence between graph isomorphism testing and function approximation with gnns,”  arXiv preprint arXiv:1905.12560, 2019.
  * [8] Nicolas Keriven and Gabriel Peyré,  “Universal invariant and equivariant graph neural networks,”  in Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [9] Zhan Gao, Elvin Isufi, and Alejandro Ribeiro,  “Stability of graph convolutional neural networks to stochastic perturbations,”  Signal Processing, p. 108216, 2021.
  * [10] Samar Hadou, Charilaos I Kanatsoulis, and Alejandro Ribeiro,  “Space-time graph neural networks,”  arXiv preprint arXiv:2110.02880, 2021.
  * [11] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro,  “Graphon neural networks and the transferability of graph neural networks,”  Advances in Neural Information Processing Systems, vol. 33, 2020\.
  * [12] Fernando Gama, Joan Bruna, and Alejandro Ribeiro,  “Stability properties of graph neural networks,”  IEEE Transactions on Signal Processing, vol. 68, pp. 5680–5695, 2020.
  * [13] Raghu Arghal, Eric Lei, and Shirin Saeedi Bidokhti,  “Robust graph neural networks via probabilistic lipschitz constraints,”  arXiv preprint arXiv:2112.07575, 2021.
  * [14] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang,  “Graph structure learning for robust graph neural networks,”  in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 66–74.
  * [15] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang,  “Learning to drop: Robust graph neural network via topological denoising,”  in Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021, pp. 779–787.
  * [16] Shai Shalev-Shwartz and Shai Ben-David,  Understanding machine learning: From theory to algorithms,  Cambridge university press, 2014.
  * [17] Luiz Chamon and Alejandro Ribeiro,  “Probably approximately correct constrained learning,”  Advances in Neural Information Processing Systems, vol. 33, 2020\.
  * [18] Stephen Boyd and Lieven Vandenberghe,  Convex Optimization,  Cambridge University Press, 2009.
  * [19] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio,  Deep learning, vol. 1,  MIT press Cambridge, 2016.
  * [20] F Maxwell Harper and Joseph A Konstan,  “The movielens datasets: History and context,”  Acm transactions on interactive intelligent systems (tiis), vol. 5, no. 4, pp. 1–19, 2015.
  * [21] Weiyu Huang, Antonio G Marques, and Alejandro R Ribeiro,  “Rating prediction via graph signal processing,”  IEEE Transactions on Signal Processing, vol. 66, no. 19, pp. 5066–5081, 2018.
  * [22] Diederik P. Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  CoRR, vol. abs/1412.6980, 2015.
  * [23] Luana Ruiz, Zhiyang Wang, and Alejandro Ribeiro,  “Graph and graphon neural network stability,”  arXiv preprint arXiv:2010.12529, 2020.

##  Appendix A Proof of Theorem 1

Denoting $P_{\mathcal{C}}$ the primal problem 6 over the non-parametric class
of functions ${\mathcal{C}}$, by [17, Proposition 2], we express know that,

$\displaystyle D^{*}\leq P^{*}_{\mathcal{C}}+(1+L\xi)\lambda^{*}$ (13)

Now noting that ${\mathcal{P}}\subseteq{\mathcal{C}}$, it implies that

$\displaystyle P^{*}_{\mathcal{C}}\leq P^{*}$ (14)

Combining (13) and (11) attains the desired result.

##  Appendix B Proof of Theorem 2

See [17, Theorem 3].