Training Graph Neural Networks Subject to a Tight Lipschitz Constraint
Authors: Simona Ioana Juvina
Ana Antonia Neacșu
Jérôme Rony
Jean-Christophe Pesquet
Corneliu Burileanu
Ismail Ben Ayed
Venue: Accepted by TMLR ()

Abstract: We propose a strategy for training a wide range of graph neural networks (GNNs) under tight Lipschitz bound constraints. 
Specifically, by leveraging graph spectral theory, we derive computationally tractable expressions of a tight Lipschitz constant. This allows us to propose a constrained-optimization approach to control the constant, ensuring robustness to adversarial perturbations. Unlike the existing methods for controlling the Lipschitz constant, our approach reduces the size of the handled matrices by a factor equal to the square of the number of nodes in the graph. We employ a stochastic projected subgradient algorithm, which operates in a block-coordinate manner, with the projection step performed via an accelerated iterative proximal algorithm.
We focus on defending against attacks that perturb features while keeping the topology of the graph constant. This contrasts with most of the existing defenses, which tackle perturbations of the graph structure. We report experiments on various datasets in the context of node classification tasks, showing the effectiveness of our constrained GNN model.

Published in Transactions on Machine Learning Research (05/2025)
Training Graph Neural Networks Subject to a Tight Lipschitz Constraint
Simona Juvinä', Ana Neacşul,? Jean- Chrnstoiitt Pesquet?, Corneliu Burileanu' Jérôme Rony" and Ismail Ben Ayed
Nattoonl University of Science and Technology Politehnica Bucharest, SpeeD Universitéé Saclay, Inria, CentralcSupélec, CVN 3ETS Montréal
Reviewed on OpenReview:
Abstract
We propose a strategy for training a wide range of graph neural networks (GNNs) under light. Lipschitz bound constraints. Specifically, by leveraging graph spectral theory, we derive computationally tractable expressions of a tight Lipschitz constant. This allows us to propose a constraincd-optiiizztion approach to control the constant, ensuring robustness to adversarial perturbations. Unlike the existing methods for controlling the Lipschitz constant, our approach reduces the size of the handled matrices by factor equal to the square of the number of nodes in the graph. We employ stochastic projected subgradient algorithm, which operates in block-coordinate manner, with the projection step performed via an accelerated iterative proximal amg. We focus on defending against attacks that perturb features while keeping the topology of the graph constant. This contrasts with most of the existing defenses, which tackle perturbations of the graph structure. We report experiments on various datasets in the context of node classification tasks, showing the effectiveness of our constrained GNN model.
1 Introduction
In recent years, graphs reccived inereasing attention due to their offectiveness in accurately representing real- world data in a variety of fields, including social networks (Facebook, Twitter), citation networks (CiteSeer, PubMed), and biological networks (BioGRID). Node classification is one the most frequent tasks when considering graph data. Considering single graph, where labels are available only for small subset of nodes, the aim is to predict the class labels of the remaining nodes. For example, in e-commerce, GNNs leverage the interaction between users and products, achieving highly accurate product advertising (Zhou et al., 2018). In citation networks, one may use GNNs to assign scientific articles to different topics (Kipf & Welling, 2016).
Being highly complex and non-linear structures, GNNs may be very sensitive to small perturbations of the input, which may result a large deviation from the prediction. For secure applications, it mandatory control the effect of such perturbations. The Lipschitz constant a well-known mcasure (Szegody al., 2014; Scaman & Virmaux, 2018) to characterize the robustness of neural networks to small perturbations. This constant provides upper bound the ratio between the output and input variations for given distance. Thus, by controlling the Lipschitz constant, one can expect to increase the robustness of network against adversarial perturbations.
In the context of GNNs, most of the existing adversarial attacks and defenses consider binary node features and focus on perturbing the adjacency matrix, not the node features. To the best of our knowledge, this work is the first to address the case of networks with continuous node features and fixed topology, i.e., with constant graph adjacency matrix. There is breadth of applications (e.g., transportation networks,

---

Published in Transactions on Machine Learning Research (05/2025)
fnancial/commeeriall networks) where the scenario tackle is relevant, although overlooked in the GNN literature. For example, most cutting-edge tralfic control systems use GNNs to st stramlline traffie, by predicting the expected level of traffic in a given intersection or node based on information from its immediate neighbours and, to an extent, from the entire network, and directing traffic towards less congested paths. A malicious agent could disrupt this critical system by causing to mislabel already congested intersections as being uncongested and directing even more traffic toward them. In addition, GNNs are used for electric power distribution, by predicting levels of power consumption and production, and also the electrical load on each node in the electrical grid. An attack that induces misclassification of a node having low power load could push the system to route more power through that node, resulting in an electrical overload. Also, in practice, inputs can be adversarial without third-party malicious intent. For example, in the case of an electrical network, there might be faully sensors, or we might encounter erroneous readings. For economic or road networks, outliers might happen in some nodes, which may severely affect the performance of pre-trained models, with potentially harmful consequences.
In this work, we propose a learning scheme for training various GNN models under tight Lipschitz-bound constraints. We derive closed-form expressions of tight Lipschitz constant which are easily computable. In addition, we propose a constrained optimization strategy to control this constant, ensuring robustness to adversarial perturbations'. Unlike the existing methods for controlling the Lipschitz constant, our approach reduces the size of the handled matrices by a factor of K2, K being the number of nodes in the graph. We propose a stochastic projected subgradient algorithm, which operates in a block-coordinate manner, with the projection step performed via an iterative proximal technique.
As we focus defending against attacks that perturb node features, rather than graph structure, we introduce GNN attack formulations for this scenario. We focus global attacks, f.e., attacks that aim to cause misclassification of the entire test set. We employ white-bos, attacks to generate the strongest attack and use a simple budget constraint that enforces a maximum perturbation on the nodes in the test set. The attacks are performed after training, i.e., evasion attacks. Our method is tested on several publicly available social networks and web graph datasets. We analyse how the networks trained under Lipschitz constraints behave when affected by various perturbation levels, as compared to the ones trained conventionally, demonstrating better performance in most situations.
The rest of the paper is organized as follows. Section 2 provides an overview of the related literature. Section 3 introduces our main contributions concerning the computation of a tight Lipschitz bound, exemplified for two classes of GNNs. Section 4 covers experimental methodology and details the results obtained when evaluating our networks against white-box adversarial attacks. Comparisons with different methods are made. In addition, we perform an analysis of memory and computational requirements. Section dedicated to concluding remarks, while Section 6 identifies some limitations of our work.
2 Related Work
With the advancement of rege-performance GNNs, robustness issues arisc. In the context of graph-structured inputs, attacks may perturb the features, the adjacency matrix, or both simultaneously. However, given the intricacy of structural information, the majority of current attacks and defenses concentrate on perturbations of the adjacency matrix rather than the features.
2.1 Adversarial attacks of GNNs models
The authors of Dai et al. (2018) propose three methods for different attack settings, addressing only graph- structure perturbations, and covering inductive and transductive classification. The first method, RL-S2V, learns generalizable attack policy over the graph structure while only requiring the prediction labels from the target classifier, being suitable for black-box attacks and transfer. GradArgmaz is a white-box attack, which performs a greedy selection based on gradient information, and GeneticAlg is a black-box attack employing a genetic algorithm. In addition, the authors point out that the effect of the attack algorithm can be reduced by dropping edges randomly during training. In Bojchevski & Günnemann (2019), the authors introduce the
1A full Torch implementation is available at http:///gthuub..oosmmooemeee jnsaaaannnnnn//pchttt.g....
2

---

Published in Transactions on Machine Learning Research (05/2025)
first study on adversarial perturbations for unsupervised embeddings. They propose white-box attack for the family of methods based on random walks, where an attacker can add or remove edges in the original graph within a given budget. The attack is exemplified for two different scenarios: node classification and link prediction, in a local sctting (affecting a single node or a single edge, respectively). Additionally, they show that the attacks generated for one model can generalize for different models and are successful even in scenarios where the attacker restricted to specific nodes. In Zügner et al. (2018), the authors published the first study on adversarial attacks for attributed graphs, focusing on models based on graph convolution. Nettack is white-box, non-adaptive attack that targets both the node features and the graph structure, in a local setting. Given budget constraint, the attack greedily flips the best edges of the graph considering a linearized GCN. Additionally, the study distinguishes between attacker nodes and target nodes, which gives rise to two approaches, i.e., direct attacks and influencer allacks. The experiments show that the attack is effective in drastically affecting the classification accuracy even with small perturbations. Furthermore, Nettack is transferable to other node classification models and unsupervisod approaches. The study in Zügner & Günnemann (2019) focuses on a poisoning attack that targets global node classification (Melallack), where the attacker has full knowledge about the data, but no information about the model or its trained weights. The attack aims to modify the graph structure using meta-gradient backpropagation procedure and adjusts the adjacency matrix of the graph as a hyperparametric problem. Similarly to Nettack, Metattack is a greedy multistep attack that flips a single edge in each iteration, up to a predefined budget, and uses a linearized Graph Convolutional Network (GCN). Only a few iterations are required for this attack to be effective.
2.2 Defense mechanisms for GNN models
The study in Wu et al. (2019) investigated both attack and defense techniques. The proposed attack uses integrated gradients to mcasure the importance of perturbing particular nodes and edges, and then flips the most influential ones. The defense method is based on improving the graph structure (prior to any message passing), by filtering out all edges that connect nodes that exhibit low Jaccard similarity. This step does not significantly reduce the performance of the network while making the graph network more robust against targeted tatks.. ProGNN (Jin et al., 2020) is another defense designed to improve the graph structure by jointly learning the parameters of the GNN and the adjacency matrix. The defense aims to reconstruct the original clean graph by preserving the properties of the original adjacency matrix (e.g., low-rankuess, sparsity, and feature smoothness). The results reported on weal-wrrld data demonstrate that ProGNN achieves better performance compared to state-of-the-art defense methods under Metattack, Nettack, and random attacks. The authors of Zhang & Zitnik (2020) proposed GNNGuard, a method to defend against a varicty of evasion allacks that perturb the graph structure. The algorithm assigns higher weights to edges connecting nodes that exhibit a higher cosine-similarity while adaptively weighting down edges that might be adversarial. GNNGuard achioves better robustncss against both targeted and untargeted attacks compared to previous defenses. RGCN (Zhu et al., 2019) is a probabilistic defense technique aiming to improve the architecture of the network by representing the hidden states of all convolutional layers as Gaussian distributed. In addition, for each layer, the weights of node neighbourhoods are adjusted based on their variances.
The authors of Entezari et al. (2020) propose one of the few defense methods that applies to both the adjacency matrix and the binary feature matrix. The defense involves a low-rank approximation of graph data in order to filter out high-frequency noise introduced by adversarial attacks. The conducted experiments demonstrate the robustness of the proposed defense against Nettack perturbations. However, the recent study in Mujkanovic et al. (2022) suggests a limitation in the evaluation, as the paper does not include an assessment for featurc-only attacks, and, given the strong bias of Nettack toward structural porturbations, their results may not confirm feature robustness. The authors of Mujkunovic el al. (2022) pointed out the lack of studies that defend against feature perturbations, which is the objective of this work.
Randomized smoothing has also emerged as an effective approach for enhancing the robustness of GNNs against adversarial perturbations. Bojchevski et al. (2020) (ackled the challenge of achieving certified robustness against structural perturbations in graphs by leveraging sparsity. By exploiting graph connectivity and the localized nature of graph fcatures, the method reduces the computational complexity of generating robustness certificates while maintaining high accuracy. Scholten et al. (2022) proposed a gray-box certification method for GNNs to defend against adversaries with full control over multiple node features. By employing
3

---

Published in Transactions on Machine Learning Research (05/2025)
random edge deletion and node masking, they analysed the probability of adversarially controlled nodes transmitting messages to target nodes. Experimental results on binary-featured datasets show that their approach outperforms previous smoothing- certificates, providing improved robustness guarantees for GNNs..
2.3 Controlling the Lipschitz constant
To the best of our knowledge, the existing literature on the Lipschitz behavior of GNNs is relatively limited. The authors of Dasoulas et al. (2021) introduced a normalization layer for basic attention-based GNNs, enforcing Lipschitz regularity. While this constraint facilitates building deep GNN architectures, the study did not investigate the robustness of these models against adversarial attacks. The work in Arghal al. (2022) focused on GNNs where the convolution is expressed in the frequency domain. They suggested controlling the Lipschitz constant of GNN filters with respect to the node attributes and extending the formulation to dynamic graphs. Finally, Zhao et al. (2021) proposed an attack-agnostic, graph-adaptive defense against adversarial samples for GNNs. The method relies on a separable Lipschitz bound, constraining both the weight and gradient norms of each layer to 1. This corresponds to a Lipschitz bound looser than the one we propose in this work. Furthermore, the attacks considered in Zhao et al. (2021) perturb only the adjacency matrix, not the features.
3 Proposed Approach
3.1 Background and preliminaries
For the task of (semi-uupervised) node classification single large graph with continuous node features, G = (V, E) represents the (directed) graph, where V = {fi...., ux} denotes the set of nodes and E C V2 represents the edges. Each node v E V is associated with a vector I, E RNO representing continuous features and a label G, E [1....,C) C)2 with C' the number of classes. For every node u, we define its neighborhood ((v) as the set of nodes u such that there exists an edge going from u to v. We consider a (generic) graph convolutional operator (Hamilton et al., 2017b; Morris et al., 2019) at node v E V and at layer E {l.....m):
(1) (1-1) (1-(111)) + wi yo = Rí (1o w0
Σ mEN(t)
Po.uth (1-1) (1 + 15(0)
(1)
where y6dh is a vector of embeddings in RN, 6.0 is a bias vector in RN, w and w/u are weight matrices in N--1 and R₂ an activation operator from R.N. to RV. Throughout the paper, we will make the mild assumption, satisfied by ReLU and sigmoid activations, that R2 is 1-Lipschitz and that it applies componentwise, except possibly for the last layer (where a multivariate operator such as softmax might be used). For every N(e), Pu,o R represents the weight between nodes and u. For the input, we set Nu to the dimension N of the feature space and (Vu E V) yo = Ie, and for the output we set Nm = C.
We define the (weighted) adjacency matrix of the graph G as A = (A E KX where, for every (u,w) E V2
A5.u Eup ff))(
otherwise,
(2)
and Enp is the positive weight of the edge from node u to u.
Equation (1) can be expressed under the vector form:
( (W,
(111 (
(1 y (-11 + b()))
(3)
with R. RKN, RKN, 0 E RNN, and ( E RKN. Hercabove, w and w are KN, KN real-valued matrices, expressed as
w (0) = Id w (
w = M @ (
where @ denotes the standard matrix Kroneeker product. In the second part of Equation (4), the matrix M KxK may take various forms, detailed below.
4

---

Published in Transactions on Machine Learning Research (05/2025)
Consider the following K x K degree matrix: D = ((()),..,,d(xk))) One may consider mumber of variations of this model. In Equation (1), we may have:
Pe.u = 1
d(uj which amounts to setting M = A
Pu.u va(r)d(a) which amounts to setting M = =D-122ATD-112
Pu,u vuu which amounts to setting M (A
Pn,N = (ur()) where (F(v) EmeN(w) EN,, and A 2 0. This amounts to setting M
where D is the diagonal matrix with diagonal terms (d=(ve))sAsk.
It is easy to notice that Model (3) can be written more concisely as follows:
(Vi E (1.....m)))
mm)) ( w w ldk w!" + M & w(")
gd (W(w (1-)) bb(),
(5)
where
(6)
In Equation (5), we recognize the generic form of a feed-forward network. One of the main points is that, although weight matrix ( may have a large size, it is usually very sparse. The zero elements of this matrix may be identified by computing
r
= (A @ (IN, I. ((((K))((KNN)))
KXK
N,XN,-1
R. Indeed, the zero elements of ( are located at the same positions as the elements of W(O, which need to be set zero. The positions of these elements being easily identified, one could use existing methods for controlling the Lipschitz constant of standard networks (Cisse et al., 2017; Fazlyab et al., 2019; Neacşu et al., 2021) to train robust GNN based on Equation (5). However, such an approach turns out to be computationally expensive for large graphs, i.e., when the number K of nodes is large. Furthermore, it is prohibitive in terms of memory requirements, even for small datasets. requires dealing with large-size matrices size KN, x KN;-1, to perform spectral normalization of these matrices" and, at the same time, to impose sparse algebraic constraints. We propose a scalable approach, which reduces the size of the handled matrices by factor K2, being agnostic to the size of the graph.
where 1n. [I...., 1]
3.2 Robustness quantification
The forward pass through an m-layer fully connected neural network T can be viewed as the composition of functions given by Equation (5). If the graph input feature vector E KNN is perturbed by 8 I KNo the effect can be quantified by the following inequality:
T(xx + 6) T(x) s 0|
(8)
where ||||| is the Euclidean norm and 0 denotes Lipschitz constant of the model. The pioneering work of Szegedy et al. (2014) points out that, if 0, denotes the Lipschitz constant of layer i, Lipschitz constant of the full wetwork can be derived as
0 =
II 0:-
However, such separable bound might be loose (Scaman & Virmaux, 2018).
We now state our main result, which provides an easy-to-compute non-separable tight upper bound. The proof of this result is grounded on graph spectral theory and some of the results in Combettes & Pesquet (2020). The details of the proof are provided in Appendix A.2.
2Scc operations hardly benefit from the sparse matrix structure expression as sum of Kronecker products.
5

---

Published in Transactions on Machine Learning Research (05/2025)
Theorem 3.1. Consider model of generic graph convolutional neural network. Assume that matrir M in Equation (4) is symmetric (corresponding to an undivected graph) with non-negative elements. Let Ax 2 0 be its mazimum eigenvalue. Assume that, for every E mb,. matrices wh and w/ have non-negative elements, (6) u 2 0 and w/) 2 0. Let
(V
((1)= = (1(wb))) + pew("))
... (wg²) ...)))...''"") + f
(10)
where |I-Ils denotes the spectral norm. Then, a Lipschitz constant of the network is given by
== (Ak))
(11)
In addition, is the optimal Lipschitz constont when there is no bias and ReL U activations are used at all layers.
Evaluations of the differences between the loose and tight estimations can be found in Appendix B. In the following, we will study two special cases of this formulation corresponding two of the most widely used GNNs, namely Graph Convolutional Network (GCN) (Kipf & Welling, 2016) and GraphSAGE (Hamilton et al., 2017a). Then, we will propose strategy to control the Lipschitz constant A during the training of our model. It is worth noting that, not only do our results apply to other choices for the adjacency matrix, but they do not assume that the network is linear. It can include arbitrary nonexpansive activation functions and biases.
3.3 Robust GraphSAGE
We consider a symmetric version of the GraphSAGE layer (Hamilton et al., 2017a), using the mean operator as the aggregator function:
(0) d(v) 1 = Ro [1(w))) " + w [(v)
(0) (i-1)
Va
b(t).
(12)
(EA(()
where, for every u E V, Yu = yo 11-1) /v /Vd(u))
d(u). This model is a particular case of Equation (1). In the case of an undirected graph, matrix M E IR xXX X is expressed as
(i-1)
M = 1/2T 1/2
(13)
This matrix being symmetric, following Theorem 3.1 and Appendix A.i( we have
0= x(1) [[(w)()) (m) + (mm"))... (wo6 + )
(14)
3.4 Robust Graph Convolutional Network (GCN)
The GCN model (Kipf& & Welling, 2016) satisfies Equation (5), with
W = M @ wff
(15)
and
M 1-2 1-2
(16)
Ā Idld (An.)Isnesk is the adjacency matrix the undirected graph with added self-counections,
D is the diagonal matrix with diagonal elements d. EK Âe,e k E (1,...; K}, and w matrix corresponding to the i-th layer. Since Á is a symmetric matrix with non-negative elements, the results in the previous sections can be extended. As shown in Appendix A.4, when for every i E (1....,m} (8) 2 0, we obtain the following Lipschitz constant:
(t) is the weight
1 |m
(m)
w
(2) Ils-
(17)

---

Published in Transactions on Machine Learning Research (05/2025)
3.5
Constraint set
Let us summarize the constraints we need to deal with to train robust GNN. For simplicity, we focus on GraphSAGE. The extensions to other GNNs based on Model (1) are straightforwar.
(i) Non-negaticity. To ensure the validity of the proposed tight bound for the Lipschitz constant we impose that, for cach layer i E fl.....m) m), the weight matrices are non-negative valued, so leading to the closed convex constraint set.
D ((wb) (9) (0 E NIMM... wo ( 2 0 and wi (c)
|
0).
(18)
(ii) Lipschitz bound constraint. Considering as the target maximum Lipschitz constant of the network, we need to impose the following constraint on the spectral norm the weight matrices:
[1(wb(m) ((m) (afm))..... (w6 + wl)))ls= S. S0.
(19)
This bound aims improving the robustness of the network against adversarial attacks. Note that this constraint is not convex. However, if (w)) wa ( are given and we just optimize (w6 (6)
(f))
we deal with a convex constraint.
These two constraints must be handled simultaneously during training.
3.6 Dealing with the Constraint Set
Calculating the Lipschitz constant of a neural network is generally NP-hard (Scaman Virmaux, 2018), although computing a light estimate of it is of paramount importance for efficient control of the robustness during the training phase. Theorem 3.1 allows to circumvent this computational bottleneck. To impose bound on the Lipschitz constant, we resort to a stochastic projected subgradient strategy that operates in a block-coordinate manner. Although the bound on the product in Constraint 19 defines a non-convex function, we are dealing with a multi-convex problem, which justifies the use of a block-coordinate approach.
Let us describe more preciscly how we proceed by focusing on the GraphSAGE case.
To update the weights, we employ projected stochastic gradient optimizer Adam variant of it (Kingma & Ba, 2015). At epoch / > 0, we denote by wo, and wi.t the estimated weight matrices for layer and define
(9)
w(()
0.1
When optimizing this matrix at epoch & 4+1 1, Constraint (19) is re-expressed as
w
c²
W(O E (R(NN)x
| B(x) 5 {
(20)
() (1) where matrices A and D(d) represent the product of the estimated matrices (wo.) + 1.)sss for the next and previous layers, respectively:
1 = Nn IN.. ww.lw/mm)..... ... [Tree IN ( B [TN, INz (W( ... [IN, INj ((()
[T. Incl
(21)
++1-
Accordingly, for the first layer with = 1, we have B.D = Nox.N. and for the last one with = m, A,50 [N.. J. Note that the previous layers have already been updated (justifying the use of index + 1), when we deal with layer i.
Recalling that D; denotes the non-negativity constraint (Constraint 18), our training procedure performs iteratively gradient step w-(() and then projects the result. W7( onto the set. s. D(1) n c(0) for
7

---

Published in Transactions on Machine Learning Research (05/2025)
each layer i E {l,..., m) and at each epoch + 1. Note that this intersection defines a closed convex set, which is one of the main advantages of the proposed block coordinate approach operating layerwise. The projection onto the intersection of D and c, has no closed-form expression and, for computing it, we employ iterative algorithm. More specifically, we make use of an instance of the accelerated iterative dual forward-backward (DFB) algorithm proposed in Neacşu et al. (2024). The projection algorithm is detailed in Algorithm 1.
Algorithm Accelerated version of the Dual -arkrrd- (DFB) algorithm
Let: Y, E R N. x No
Set: 7 = 1/
Ils |B Is)
Sct: a E|2, f
for 1 -...... do
T 1+l+a
Zi Yi+ mi(Y- - Y1-1)
Vi = projp, (W(1) A 7B (
// Truncate negative values
Y, Z1 + 7A, V.
Y1+1 = Yi- - proj (ro (7-
end for
Return: V/2 = proj g(ي) W!
Hereabove, projp, represents the projection onto the cone of non-negative valued matrices, whereas projs stands for the projection onto the spectral ball of radius O. The latter projection easily computed by a singular value decomposition.
4 Experimental Approach and Results
4.1 Experimental Methodology
To evaluate the effectiveness of the proposed method for training robust graph networks, we conducted experiments on various publicly available graph datasets comprising real-world social networks and web graphs. The considered datasets are Facebook (Rozemberczki et al., 2021), GitHub (Rozemberczki et al., 2021), LastF'M Asia (Rozemberezki & Sarkar, 2020), and Deezer Europe (Rozemberczki & Sarkar, 2020). These graphs are attributed, allow for binary and multi-class node classification, and are variable in size and density. More details about the datasets are provided in Appendix C.1.
For all datasets, we conducted experiments using our two proposed networks: robust. GCN and robust. GraphSAGE. We report mean accuracy with standard errors calculated from 10 seeded splits, with a training- validation-testing split ratio of 60%, 20%, and 20%, respectively. For both architectures,
trained models subject to various Lipschitz bound constraints (7 E (0)) to find the best trade-off between robust and performance. Unless otherwise stated, we consider networks with m = 3 layers and hidden feature dimension N, = 16 for i E (1,2). Furthermore, in part of our studies, the influence of the depth of the network on the overall behavior is evaluated by varying the number of layers m E [2, 7] (see discussion in Appendix D.5). The rectified linear unit function (Re..U) activation function is used for intermediate layers, and Adam optimizer (Kingma & Ba, 2015) with & penalty is employed optimize the model parameters. The general formulation in Equation (1) allows for distinctive bias parameter for each node. However, in our experiments, single bias vector is used for the entire layer and applied Weeeent-wise to the features of all nodes, which is the standard practice. Our method is based on the assumption of non-ncgativity. Although this constraint is rinsic to our approach, from our experiments, we found that the non-negativity requirement affects the accuracy only by small margin, for these datasets. A comparison in accuracy between training a network with non-negative weights and conventional training is presented in Table 1. It worth highlighting that while the weights within the network are nonnegative, the inclusion of signed biases introduces arbitrary signs in the puts after each layer. Consequently, this allows for the activation function to be triggered.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Mean accuracy + standard deviation of the baseline and non-negative constrained models on all datasets from 10 sceded splits.
Facebook
LastFM
GitHub
Deezer Europe
GCN
Baseline
94.0+/-0.0
87.3+/-0.7
-6.9+/-0.6
60.5+/-0.5 59.1+/-1.2
Pos. constr.
93.2+/-0.4
85.5+/-0.7
86.0+/-0.8
GraphSAGE
Baseline
93.3+//0.55
85.5+/-0.8
86.5+/-0.5
65.2+/-0.4
Pos. constr. 92.2+/-0.6
85.3+/-0.7
85.9+/-0.7
64.4+/-0.5
Most of the existing adversarial attacks and defenses for GNNs primarily focus on perturbing the adjacency matrix rather than the node features (Mujkanovic al., 2022). From our knowledge, not all the existing works that address Lipschitz constraints GNNs consider graph convolutional operators. Arghal et al. (2022) tackle Lipschitz normalization for self-attention layers, which is not directly comparable to our approach. Additionally, these papers only provide numerical results for datasets with binary features, and their code is not always publicly available, making it challenging to make meaningful comparisons. Thus, we compare the performance of our robust training approach with two standard methods, namely Adversarial Training (AT) (Madry et al., 2018) and Randomized Smoothing (RS) (Cohen ct al., 2019). Adversarial training involves generating adversarial samples using the Auto-PGD (APGD) attack (Croce & Hein, 2020) with Difference of Logits (DL) loss and training models for different perturbation levels E [0, 1000], which represent the & norm of the perturbation on the entire test set. For RS we consider the method described in Cohen et al. (2019) and conduct experiments using various Gaussian noise levels a E [0, 2], applied element-wise to each feature vector of the input data. Finally, in the case of GCN networks, we also compare our approach with Spectral Normalization (SN) (Miyato et al., 2018) and methods aimed to defend against graph structure perturbation: GCN-Jaccard (Wu et al., 2019) and SVD-GCN (Entezari al., 2020), which focus on improving the structure of the graph, and RGCN (Zhu et al., 2019), which utilizes adaptive aggregation. Further details the training strategies can be found in Appendix C.2.
When training constrained models and imposing a lower Lipschitz constraint than that of the baseline model 7 < moddll, the standard accuracy decreases, but the model exhibits greater robustness. For instance, consider the accuracy of GCN models trained by varying constraint values on the Facebook dataset (refer to Table 2). As we lighlen the constraint, the drop in accuracy becomes more significant, but the model's ability withstand adversarial perturbations improves compared to the conventionally trained model. Figure different datascts, for both GCN and GraphSAGE architectures, presenting
exemplifies this behavior the accuracy of the baseline and constrained models with different & < moodel, while varying the lz norm of the test set perturbation. This trade-off pattern holds for the other methods presented in this paper with respect to their specific parameters, as the perturbation level increases. Acknowledging this inherent trade-off between accuracy and robustncss in all methods, we opted for choosing one model from each technique for the purpose of comparison. Thus, we selected the model with the largest area under the accuracy-robustnne curve, while ensuring that it exhibits decrease in relative accuracy on the validation dataset of less than 3% when compared to the conventionally trained model (when possible).
Table 2: Mean accuracy + standard deviation of GCN models trained under different Lipschitz constraints on the Facebook dataset from 10 seeded splits.
modee 51.99
7 30
7 25
7 = 20
f 15
7 10
T 7= 5
7 = 3
Acc.
94.0 + 0.0
93.1 + 0.4
92.9 + 0.5
92.2 0.4
91.7 + 0.5
90.8 +
0.6
87.9 + 0.7
84.3 + 1.1
4.2 Adversarial robustness evaluation
In this section, we evaluate the efficiency of our robust training approach against whitc-box adversarial attacks and compare with conventional training, AT, and RS. Although there are not many works studying adversarial attacks on graph features (Mujkanovic et al., 2022), we can use the classical Projected Gradient.
9

---

Published in Transactions on Machine Learning Research (05/2025)
Facebook
Fast MAsia
GitHuub
Deezer Europe
0-40 25
0-11.50
2.5
GCN After arack accuncy
3-.2
After atta ascueRO
3-11.0
Aft: aRCAC aSCURREO
3-110
3-50
1-
3+10
3-30
6.65
GraphSAGE aftir sto scauray
After JItUO SCRUFOCY
Afte AERICC RECUTMEY
8-3.5
7-2.0
7-1.0
300
Figure 1: Accuracy- robustness tradeoff. Accuracy vs. l norm of the test set perturbation (c) APGD attack with DL loss. The blue line represents the baseline model; the remaining lines depict constrained models with varying Lipschitz values Ø. Top row: GCN model, bottom row: GraphSAGE model.
Descent (PGD) technique (Madry et al., 2018), and its parameter free extension, Auto-PGD (APGD) (Croce & Hein, 2020), to evaluate the robustness of the models. Since we attack all the test nodes at once, we sum the loss over the attacked nodes. More information and details about the attackers can be found in Appendix C.3. We consider the task of transductive node classification, and the two architectures, GCN and GraphSAGE with the configuration described above. Our analysis involves examining how the baseline model and the models trained subject to spectral norm constraints behave when facing different levels of perturbations 8, evaluated with respect to the la norm of the entire lest. set. We select the range of perturbation magnitudes ||0|| starting from the point where the models exhibit a minimal loss in performance, up to the point where the accuracy drops to (almost) zero, or it plateaus. In evaluating a total of six attack methods, formed by combining two attack techniques (PGD and APGD) with three distinct loss functions CCross-Entropy (CE), Difference of Logits (DI.), and Difference of Logits Ratio (DLR) (Carlini & Wagner, 2017; Croce & Hein, 2020)), we consistently found that the APGD attack outperformed PGD irrespective of the chosen loss function. Furthermore, regardless of the allack method, the DL loss demonstrated the strongest adversarial impact. Specifically, the APGD attack coupled with the DL loss emerged as the most powerful among the six attacks, across all datasots. Given this observation, we further compared the efficioncy of the models subjected to an APGD-DL attack. A detailed discussion can be found in Appendix D.1.
Figure 2 displays the robustness of the models on the different datasets. Our models consistently outperform the bascline by a significant margin, showcasing robustness against adversarial attacks with minimal performance loss. These findings confirm that the theoretical concepts introduced in this paper lead to GNN models that are more robust to adversarial perturbations. Our models trained under spectral norm constraints perform much better than adversarially trained models across all datasets and configurations. AT models perform at most only slightly better than the conventionally trained models. Comparatively, the randomized smoothing approach exhibits good robustness most cases when compared the baseline model, but it is generally not as effective as our approach. It is worth noting that, although RS was proven effective, it requires multiple inferences (1000) to achieve good robustness, which is very time-consuming.
Although the considered Lipschitz constant was computed in the sense of & norm, we tested our approach with an fxo (APGD-DL) attack and observed similar or better performances across all datasets. These results are presented in Appendix D.2. Furthermore, lo demonstrate the generalizability of our findings across a wise broad range of component wise activation functions, we investigated four additional ones, besides ReLU, i.e.,
sigmoid, hyperbolic tangent (tanh), Icaky ReLU, and sigmoid lincar unit (SiLU). We have found that our models consistently surpassed the baseline in these instances as well, highlighting their robustness against adversarial attacks. The results can be found in Appendix D.3.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Facebook
Last MAsia
GitHuu
Deezer Europe
0--6.25
0.13.5
GCN After Perraackk accunc
3-11.
Alter aRrus ascueRO
3-13
After aRCACA DSCLIREY
2-65
M-441
p-2.0
cm30
GraphSAGE after sto s acorsey
Alter attacc accuriay
After JIta ScAUFOCy U0C
Afte ATRICC RECUTMEY
AT
A-
ATc-00
300
Figure 2: Robust training. Accuracy vs. l2 norm of the test set perturbation (c). APGD attack with DL loss. The blue line represents the baseline model, the orange line represents our constrained model, the green line corresponds to AT, and the red line corresponds to RS. Top row: GCN model, bottom row: GraphSAGE model.
Finally, in the context GCN networks, we conducted further comparisons to evaluate the effectiveness of our method. These comparisons entailed evaluating our method against Spectral Normalization (SN), considering both efficiency and performance. Additionally, we benchmarked our approach against three methods specifically designed to address perturbations to the graph structure: GCN-Jaccard (Wu et al., 2019), SVD-GCN (Entezari et al., 2020), and RGCN (Zhu et al., 2019). In the case of SN, our experiments revealed its ability to exhibit robustness against adversarial attacks compared to the baseline model. However, it fell short of delivering the performance achieved by our proposed approach (Figure 3a). On the other side, SN exhibits slightly faster training times compared to our method (4.9 ms per epoch, on average). The timing results are presented in Table 8, in Appendix D.4. The effectiveness of the methods designed handle modifications the graph structure demonstrated in Figure 3b. Among these methods, SVD-GON proves effective for large perturbations, but, for low to medium perturbations, it experiences significant drop in accuracy. This behavior is observed across all datasets except Deezer Europe, where it demonstrates minimal robustness compared to the bascline model. Similarly, RGCN struggles to achieve high accuracy in the case of multiclass datasets. In contrast, GCN-Jaccard demonstrates robustness on multiclass dalasets, although it shows limited effectiveness for binary datasets.
4.3 Memory and computational efficiency
Using existing techniques for controlling the Lipschitz constant of standard neural networks (often fully connected ones in the literature) (Cisse al., 2017; Anil et al., 2019; Fazlyab et al., 2019; Huang al., 2021; Neacşu et al., 2021; Araujo et al., 2022; Muthukumar & Sulam, 2023) is possible based on Equation (5). However, it is computationally inefficient and sometimes infeasible. The memory requirements associated with handling matrices of size KN, x KN pose significant challenges, even for moderately sized graphs. Additionally, performing spectral normalization and, at the same time, imposing sparse algebraic constraints on these matrices proves to be computationally expensive.
To better exemplify the great reduction in memory allowed by method, we consider the GCN used in this work and the two formulations: the fully connected one and ours. Table 3 provides the total number of elements in the weight matrices for cach dataset. Assuming that each element is represented a 32-bit floating-point number, we can estimate the memory occupied by the full matrices. For the specified datasets, the projected memory demands for these matrices range from 0.5 to 11.85 terabytes, surpassing the practical storage and handling capabilities of current GPUs. In contrast, our formulation introduces minimal additional memory overhead compared training a conventional GCN, with the maximum memory requirement for the largest dataset being only few dozen kilobytes.
11

---

Published in Transactions on Machine Learning Research (05/2025)
Facebook
Last
GitHub
Deezer Europe
Raceline Coruttranz
Baseline Carotra SM
Resebie
Al atuack attara
Corstralned SN
Alter attuck accuras
Coratrurne
180
320
(a) Comparison with Spectral Normalization (SN)
Nft wttark at acuurrcy
basdine Conszsanne 3GCN
Danntra Consiain
Atco Stto scorasy
Constrined
Dsce
Aftar uttack accuracy
RGCN
RGZN
ROCH
Geear Sxb OCN
acadd SuD-GGN
GCN-jeccard
549-GCN
SyD-SCN
200
300
205
(b) Comparison with methods designed against attacks on graph structure
Figure 3: Robust training for a GCN model. Accuracy vs. lg norm of the test set perturbation (c). APGD attack with DL loss.
Table 3: Comparison of matrix sizes between the fully connected and proposed formulations for GCN on various datasets.
Fully connected formulation
Our formulation
Dataset
W((0)
w!l)
Wr(2)
Total
W
W(1)
w
Total
Facebook
10
1,3x10
3.2x
1.2x10
2.0x103
2.6x10²
6.4x10|
2.4x103
LastFM Asia
1.2x10
1.5x1010
1.7x1010
1.5x10
2.0x103
2.6x
2.9x102
2.6x103
GitHub
10
3.6x10
1.5x
3.3x
2.0x103
2.6x
3.2x10'
2.3x103
Deezer Europe
1.
2.1x1011
2.6x1020
1.9x10
2.0x10
2.6x10²
3.2x10'
2.3x10
While our method incurs a slightly longer training duration (on average 1.36 limes slower, per epoch) than baseline training, the overhead remains reasonable given the achieved robustness against adversarial attacks. The increased training times are more pronounced for larger and more complex datasets, but for smaller datasets, the difference training time is minimal. In absolute values, our experiments show that the total time required train a whole model was between 11.57s (simplest configuration) and 45.46s (biggest dataset), as opposed 9.96s and 21.12s, respectively, for the conventionally trained model. Thus, the additional training time be considered quite acceptable. Notably, method exhibits faster training times average compared to AT, and RS does not require any additional training lime. Despite its advantages, RS exhibits a major drawback with significantly slower inference times, ranging from 150 to 400 times slower in our experiments compared to the other methods. This may render RS impractical for some real-life applications, as it may take several seconds for a single inference. In contrast, our method does not introduce any overhead inference. Comprehensive details on the time requirements for the experiments conducted this study can be found in Appendix D.4.
5 Conclusion
This paper proposes a new approach for building GNNs subject a Lipschitz bound by focusing on graphs with a constant topology and continuous features each node. We derived Theorem 3.1 which provides a tight and tractable expression for this bound by assuming that the network weights non-negative and
12

---

Published in Transactions on Machine Learning Research (05/2025)
additional mild symmetry property is met. Unlike the standard bound in Equation (9), the proposed bound is not layerwise separable. We showed that this bound can be further simplified for GraphSAGE and GCN networks. We validated our approach on four datasets for binary and multi-class classification problems. We showed that we can indeed control the Lipschitz constant of the GNN while maintaining good accuracy and benefiting from improved generalization properties. We also adapted the PGD and APGD attackers for generating white box adversarial attacks on our graph models. Overall, we observed better robustness than the one obtained by both adversarial training and randomized smoothing and, in the case of GCN networks, our method outperformed spectral normalization and methods designed against graph structure attacks.
6 Limitations and Future Work
Our work is subject to several limitations that should be taken into account when interpreting the results. We identify four main limitations:
(i) Non-negative Network Weights: Our proposed bound assumes that the network weights are non- negative. While this constraint did not in itself cause a signifieant drop in performance for our considered datasets, different conclusions might be observed on other datasets.
(ii) Undirected Graph: The graphs used in our experiments are undirected, which is the case for many datasets.
(iii) Graph Topology Attacks:
Our work does not address graph topology attacks; in turn, we address feature attacks, which are seldom considered in the literature of GNNs.
(iv) Continuous Features and Untargeted Attacks: Our tests are based on continuous features, on which we perform untargeted attacks by PGD and APGD. However, other types of features or attacks could be considered.
Addressing these limitations could further enhance the validity and applicability of our findings. In future work, we inlend to explore these constraints. Furthermore, we aim to explore the feasibility of employing norms other than the Euclidean one.
References
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In International Conference on Machine Learning (ICML), pp. 291 301, 2019.
Alexandre Araujo, Aaron J Havens, Blaise Delattre, Alexandre Allauzen, and Bin Hu. A unified algebraic perspective on Lipschitz neural networks. In International Conference on Learning Representations (ICLR), 2022.
Raghu Arghal, Eric Lei, and Shirin Sacedi Bidokhti. Robust graph neural networks via probabilistic Lipschitz constraints. In Learning for Dynamics and Coutrol Conference, pp. 1073-1085, 2022.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning (ICML.), pp. 695-704, 2019.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning (ICML), pp. 1003 1013, 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy, pp. 39-57, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parsoval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning (ICML), pp. 854-863 2017.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (ICML.), pp. 1310-1320, 2019.
Patrick L Combettes and Lean-Christoplas Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. In STAM Journal on Mathematics of Data Science, volume 2, pp. 529 557, 2020.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning (ICML.) pp. 2206-22012 2020.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference on Machine Learning (ICML), volume 80, pp. 1115-1124, 2018.
George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self-attention layers with application to graph neural networks. In International Conference on Machine Learning (ICML), pp. 2456-2466, 2021.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In International Conference Web Search and Data Mining, pp. 169-177, 2020.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of Lipschitz constants for deep neural networks. In Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 11423 11423-11434, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Annual Conference Neural Information Processing Systems (NeurIPS), 30, 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. IEEE Dala Engineering Bullelin, 40(3), 2017b.
Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local Lipschitz bounds. Annual Conference on Newral Information Processing Systems (NeurIPS), 34:22745 22757, 2021.
Kenneth Hung and William Fithian. Rank verification for exponential families. The Annals of Statistics, 47 (2):758-775 782, 2019.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In ACM SIGKDD International Conference on Knowledge Discovery and Dala Mining (KDD), pp. 66 74, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks, In International Conference on Learning Representations (ICLR), 2016.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint ar xxx::20055.011 06145.00199.. 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. Tn International Conference on Learning Representations (ICLR), 2018.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602 4609, 2019.
Felix Mujkanovie, Simon Geisler, Stephan Günnemann, and Aleksandar Bojchevski. Are defenses for graph neural networks robust? Annual Conference on Neural Information Processing Systems (NeurIPS), 35: 8954-8968, 2022.
Ramchandran Muthukumar and Jeremias Sulam. Adversarial robustness of sparse local Lipschitz predictors. STAM Journal on Mathematics of Data Science, 5(4):020-945) 2023.
Ana Neacgu, Kavya Gupla, Jean-Christophe Pesquet, and Corneliu Burileanu. Signal denoising using new class of robust neural networks. In European Signal Processing Conference (EUSIPCO), pp. 1492 1496, 2021.
Ana Neacşu, Jean-Christophe Pesquet, and Corneliu Burileanu. EMG-based automatic gesture recognition using Lipsciitz-regularrzzed neural networks. ACM Transactions Intelligent Systems and Technology, 15: 1-25, Feb. 2024.
Jérôme Rony and Ismail Ben Ayed. Adversarial Library. adverearial-Library 2023. License: BSD-33Clause.
Benedek Rozemberezki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proc. ACM International Conference on Information and Knowledge Management, pp. 1823-13344 2020.
Benedek Rozemberezki, Carl Allen, Rik Sarkar, et al. Multi-scale attributed node embedding. Journal of Complex Networks, 9(1):1-22, 2021.
Kevin Scaman and Aladin Virmaux. Lipsehitz regularity of deep neural networks: analysis and efficient estimation. In Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 3839-3848 2018.
Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message-interreptionn smoothing: Gray-box certificates for graph neural networks. Annual Conference on Neural Information Processing Systems (NeurIPS), 35:33146 35:33146-33158, 2022.
Christian Szegedy, Wojciech Zaremba, Llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing propertics of neural networks. In International Conference on Learning Representations (ICLR), 2014.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: deep insights into attack and defense. In International Joint Conference Arlificial Intelligence (IJCAI), pp. 4816 4823, 2019.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Annual Conference on Neural Information Processing Systems (NeurIPS), 02.9263-9274 2020.
Xin Zhao, Zeru Zhang, Zijie Zhang, Lingfei Wu, Jiayin Jin, Yang Zhou, Ruoming Jin, Dejing Dou, and Da Yan. Expressive 1-Lipschitz neural networks for robust multiple graph learning against adversarial attacks. In International Conference on Machine Learning (ICML), pp. 12719 12719-12735, 2021.
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for thick-through rate prediction. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1059-1068, 2018.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1399 1407, 2019.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 2847 2856, 2018.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. Tn International Conference on Learning Representations (ICLR), 2019.
16

---

Published in Transactions on Machine Learning Research (05/2025)
A Properties for Symmetric Matrices
In this section, will consider the case when M is symmetric with non-negative elements, which covers several of the examples mentioned in Section 3.1.
A.1 Preliminary results
If M is symmetric, its eigendecompositon given by
M = -UDUU
(22)
where U is an orthogonal matrix of kxx and E IR x K is a diagonal matrix with diagonal elements
S... S Ag.
(23)
Note that, since M typically has zero diagonal terms, so-called hollow symmetric malriz. This implies that its trace is zero, and thus possesses both negative and positive eigenvalues.
Lemma A.1. Suppose that M satisfies the above conditions.
Then
W(m) ... .() = (U @ Id N )AUT @ No),
(24)
where A E ((KN)))(KNN) is block diagonal matrir with K diagonal blocks. Its k-th diagonal block is expressed as
(w)m) + >>ww(m))- (w) \ E NN
(25)
Proof. By using the properties of Kronecker product, it follows from Equation (6) that, for every e {1....,m). m).
W (UUT) wn (UDU w
(U & ld Id @ of (UT @ @ I (Uol: & 8Iv
= (U @d (ld @ (0) + +D +D )( @ IN..)..
(26)
In addition, can be noticed that
Id @ Id)x) = (UUT) ) 8 (Id Id
Id k @ Id N.
=ld
(27)
Using Equation (26) and Equation (27) recursively yields
((m)... ... (()) = (U Ø ld I..)) (Id @ woth + D 18uu w (m) (Id @ w/ + +D w (1) XUT @ Ild N.).
(28)
For every E f1..... m), Id w. + D & w is a block diagonal matrix of size (KN)) (KN,-1) having
K block diagonal clements (w)) + + Iggg.. Thus A is a block diagonal matrix with K block diagonal elements of the form (25).
(1)
Lemma A.2. Assume that, for every E m), If (H. ( E R are such that
(2) 2 and w 20 0. Let uo be defined by Equation (10).
|p| - μ.
(29)
then p(v)= v(p)). In particular, ip is an increasing function [0, +o0
17

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. We can write
m
(w) (w)m)) + umm mi). ... (w0 + tum (1) = Σ
1 Win
(30)
i=0
where (Ws) are matrices in [0, +00 MoooMMxxN. For every x E RR,,,,
m m
([(wb( + u ... (wd)
+ umm (1) )x13 =
+J (w.x) (w,z)
1=0 j=0
Ht (wæx) (1)zx)
i=0
( (1a [x)
(myl=l)
1=0
(w |x) (ūglæ|),
(31)
0=
where |x]] denotes the vector whose components are the absolute values of those x and we have used in the last inequality the nonnegativity the elements matrices (w:)) We deduce from Equation (31) that
11wwb (mm) + umm (m) ... (w) pad ( (1) >=1|| - 11(16m (mm) + pww(")) ... (wo²) (1) + umi |=||l--
(32)
Consoquently,
[[(w)))) (m) pmd (m)) ... (w! + ymm (2) (2)) )oll
((1))
sup =EBMo\(0)
||
((w) (m) Fnw (mm) )... (w/) + nw (1) |ل||||
sup
||00|||
NoR (()
(ww (m) + Tew (m)) ... (wo + xw (2) all
sup
||a||
ac(0,+o001M Nox (0)
((mn))) p (m)) ... (wo + pam (
sup
|
((T)).
(33)
A.2 Proof of Theorem 3.1
In Scaman & Virmaux (2018) and Combettes & Pesquet (2020), upper bound on the Lipschitz constant of a feed forward network with weight (w Issism is derived for a broad class of activation functions (see Proposition 5.3 in Combettes & Pesquet (2020)). This bound is tight in the sense that it is finor than most of the existing bounds, in particular the classical separable one Equation (9). This can also be checked numerically on simulated networks when compared with other recent methods for computing Lipschitz bounds (Fazlyab et al., 2019). The limitation of this upper bound is that it is NP-hard to compute (Scaman & Virmaux, 2018), but it can however be lower bounded by the more tractable expression
y (m) (mm.....
(34)
This corresponds to the optimal Lipschitz constant of a lincar neural network, where activations roduce the identity function. When the network has non-expansive activation operators and non-negative weights, it is shown in Proposition 5.10 of Combettes & Pesquet (2020) that this lower bound & and the tight.
18

---

Published in Transactions on Machine Learning Research (05/2025)
expression of the Lipschitz constant coincide. Note that Equation (34) is only proved to be upper bound when using activation functions that apply womponent-wise (except for the last layer). According to the Peeron-Probenuus theorem', if w(m)... ... W1) has non-negative elements, then its spectral norm is an cigenvalue of this matrix which admits an associated cigenvector e with non-negative components. If this vector used as the input of a feed forward neural nelwork with non-negalive weights (W()) 1<tsm> no bias, and ReLU activations at all layers, it straightforvard to show that the output of the neural network is W(m)... ... e (m)....... [lle. The bound in Equation (34) being thus attained in this case, is optimal. However, it is noteworthy that & is upper bound the Lipschitz constant of non-negative neural networks for other activation functions than ReLU. In addition, this result holds for inputs with arbitrary signs.
Using the same notation as in Appendix A.1, it follows from Lemma A.1 and the orthogonality of matrices U @ Id N.. and U > No that
( ... Il = ||A||s-
(35)
Because of the block diagonal structure of A and the definition of in Equation (10),
[[ ... W max (Ax)). ISkSK
(36)
Since M is matrix with non-negative elements, it follows from the Perron-Frobenit theorem that
(Ak fI...., K K-1K) 17) Dal S Ax.
(37)
We deduce from Lemma A.2 that
(Vk E {1,...,,K K 1)) ((Aa) S (()x).
(38)
By using Equation (36), this yields Equation (11). When the considered GNN has no bias and uses only ReLU activations, the optimality of the bound in Equation (11) follows from our previous comments regarding the optimality of (34).
A.3 Remarks on the use of Theorem 3.1
(i) For every node v, let
do = Σ M uEN(U)
(39)
From standard results in spectral graph theory,* the following inequality is satisfied
Σvey de S S max de.
(40)
K
DEV
It thus follows from Lemma A.2 that under the assumptions of Theorem 3.1,
s Ever de
((m)....
w S (mmax d,).
(41)
(ii) Assume that M corresponds to the normalized (possibly weighted) adjacency matrix of an undirected graph. Then M = A (Ds)-112 where A is the nen--eeative-valuee symmetric matrix defined in Equation (2) and D* is the diagonal matrix with diagonal terms df = EuEN(() Earus E V. The case of an unweighted normalized adjaceney matrix recovered when, for every V and (V)), Eu,u = 1. Using graph spectral theory concepts, it can be shown that the maximum eigenvalue of M is AK 1. 1.
3Call D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, 2000.
Daniel A. Spielman, Spectral and Algebraic Graph Theory, Yale University, 2019.
19

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Although this result is known in the case of unweighted adjacency matrices, provide proof for completeness. For every (v, u) E V2, set
Ev,u
if f
E0,u
d=(v)
(42)
otherwise.
By symmelry, we have, for every x = (IN)NEV E RK
Σ
(Vennutio - (u,,iitt)
(M:w)VV2
Σ
Σ
Epratt 2 v
+ Σ Σ
Ea -2 E
V
VEV (EN(o)
ueV VEN(u)
(V,a)VV
= 2
Σ
Euuu
(dF(v)((())
BEV
"EViuEN(o)
2x LFx,
(43)
where L ld K MM is the weighted Laplacian matrix of the graph. Since we have proved that, for positive semi-defiitte matrix. This means that
every x RRK L 2 0, I
AK S
(44)
On the other hand, x (DE)1/21K, we have
Mr (DF)-1/2 A11
-DF) 1/2
Σ
Ev,u
T.
(45)
NEV
(EA(w)
This show that x is an eigenvector of M associated with eigenvalue 1. Consequently, the upper bound attained in Equation (44).
(iii When the weights are not assumed to be non-negative, it is also possible to evaluate a Lipschitz constant of an individual layer under the symmetry assumption for M. Indeed, it follows from Equation (26), that
[| = |ldd @ uo + D &
w " I|s
= max ISkS
+ m (3) 19..
(46)
By using the triangle inequality, have also the upper bound
w S |mll
( Ils + Ax ww (2) lls.
(47)
In particular, if wi ( = 0 then Equation (46) reduces to
( [W ||m! I|s-
(48)
A.4 GCN case
Suppose that, for every i E {1, {l,...,m), w/ > 0. The main mathematical difference in the analysis of GCN is that matrix M has nonzero diagonal elements. However, remains symmetric with non-negative elements which are the sufficient requirements in the proof of Theorem 3.1. The result thus extends straightforwardly. Let dR > 0 be the maximum eigenvalue of M. Then
[m(m....
( = \gllwa (m)) ... w lls.
(49)
Similarly, it is casy to see that the reasoning in Appendix A.3 (ii) remains valid for matrix M D-1/2 allowing us to conclude that =1=1. 1.
1/2
20

---

Published in Transactions on Machine Learning Research (05/2025)
B Lipschitz Constant Estimates
As discussed in Section 3.2, the Lipschitz constant provides an upper bound on the ratio between the output and imput variations for given metric. An accurate estimation of this bound is mandatory to ensure good trade-off between robustness and performance. Therefore, we aim to compute an estimate of the Lipschitz constant for GNNs that is as tight as possible.
In Table 4, we mumerically exemplify the difference between the different formulations for estimating a Lipschitz constant of network (Equations (9) and (34)). We consider the two particular GNNs discussed Sections 3.3 and 3.4, i.e., symmetrical GraphSAGE and GCN with non-negative weights. We train networks of varying depths, from shallow deep, the Facebook dataset and compute Lipschitz constant estimates using the two formulas mentioned above. The hidden dimension of each layer is N₁ 16 for E {l,..., m). From the results presented in the table, it can be clearly seen that the more complex the network, the bigger the discrepaney between the loose and the light bounds. The difference belween the two is higher in the case of GraphSAGE than GCN, possibly due to the higher number of parameters of the former. Note that, from a theoretical viewpoint, the ratio between & and 0 could be arbitrarily small for some choices of the weights.
Table 4: Loose and tight Lipschitz constant estimates for networks of different depths trained on the Facebook dataset.
GCN
GraphSAGE
Number of layers
1
(1)
(m)
W
(m). W
1
226.04
207.29
170.19
148.48
2
375.06
345.6
880.2
626.62
3
564.84
471.6
833.07
589.31
4
578.85
406.3
904.22
425.66
5
294.41
206.66
1034.19
349.39
10
1819.86
567.55
7260.37
1261.41
C
Comprehensive Experimental Description
C.1
Dataset details
We considered various publicly available, real-world social networks and web graph datasets:
Facebook Page-Page (Rozemberezki et al., 2021): Nodes represent verified Facebook pages and edges mutual likes. The features are extracted from the description of the page, and the label is the page category.
GitHub (Rozemberczli et al., 2021): Nodes developers on GitHub and edges represent mutual follower relationships. Node features are information about the repository and the owner (e.g., starred repositories, location, etc). The task is to classify nodes as machine learning or web developers.
Deezer Europe (Rozemberczki & Sarkar, 2020): Nodes represent and edges friendships. The binary classification task is the prediction of the users' gender, considering the liked artists features.
LastFM Asia (Rozemberczki & Sarkar, 2020): Nodes represent Asian users, edges friendships and features consist of artists liked by the users. The task is to predict the nationality of the user.
Their descriptive statistics are presented in Table 5.
21

---

Published in Transactions on Machine Learning Research (05/2025)
Table Statistics the graph datasets used for the evaluation of node classification algorithms
Dataset
Nodes
Edges
Features per node
Classes
Facebook
22470
342004
128
4
GitHub
37300
578006
128
2
LastFM Asia
7624
55612
128
18
Deezer Europe
28281
185504
128
2
C.2 Experimental configuration
In our experiments, we trained each model for 2000 iterations, following a strategy that reduces the learning rate by factor of 10 if the performance of the model did not improve for 100 epochs. We trained the model using the Adam optimizer, in the standard configuration (31 = 0.9, B2 0.99) with lz penalty. The weight decay was tuned using 5-fold cross-validation for each dataset and GNN formulation. All the layers have a hidden dimension N₂ 16. Moreover, we have implemented an early stopping mechanism, with a patience of 200 iterations. The DBF algorithm uses a maximum number of 100 iterations, but also employs an early stopping mechanism. At each step of the algorithm, we compute the current Lipschitz constant and compare it to the target Lipschitz constant. If the difference between the two is lower than tolerance parameter (chosen 0.01), stop the algorithm. Typically, the algorithm requires more iterations during the first few epochs and then just a few for subsequent ones. The common parameters for all datasets and network architectures are summarized in Table 6, while the particular weight decay values are presented in Table 7.
Table 6: Training hyperparameters
Parameter
Value
Training
Hidden dimension
16
Max num. epochs
2000
Early stopping patience
200
Initial learning rate
0.01
Learning rate patience
100
DFB algorithm
Max num. iterations
100
2.1
Max. Lipschitz difference
0.01
For adversarial training (AT), the adversarial samples were generated using the Auto-PGD attack (Croce & Hein, 2020) with Difference of Logits (DL) loss, for different perturbation levels i.e., E {10,50 50, 100, 150, 200, 300, 400, 500, 600, 800, 900, 1000), which represent the & norm of the perturbation the entire test set.
For randomized smoothing (RS), we adapted the method presented in Cohen et al. (2019) to the graph domain. We trained the base classifier (GCN or GraphSAGE) with inputs perturbed by Gaussian noise. Then, during inference, we ran noise-corrupted copies of the input through the base classifier and returned the class that appeared most frequently. We used the hypothesis test from Hung & Fithian (2019) to calibrate the abstention threshold to bound by the probability of returning time requirements of this method, we chose 8 10 that we get good trade-off between prediction time and failure probability. Thus, we chose N such that our prediction function with failure probability a = 0.001 abstained at most. 10.5% of the lime for all the datasets, architectures, and values of a. We chose N = 1000 yielding an abstention rate of at most 1.3% for o = 0.1 2.6% for o = 0.25, 3.2% for a = 0.5 6.4% for 0.75, 8.7% for
incorrect answer. Because of the high
and 10.4% for o of the noise level o, i.e., o E {0.1, 0.25, 0.5, 0.6, 0.7, 0.8, 1, 1.4, 1.6, 1.8, 2). The Gaussian noise was applied element-wise each feature vector of the input data.
We performed the experiments for multiple values
22

---

Published in Transactions on Machine Learning Research (05/2025)
Table L2 penalty for each dataset and network architecture
Network
Dataset
L2 penalty
Facebook
0.0005
GitHub
GCN
LastFM Asia
0.005
Deezer Europe
Facebook
0.005
GitHub
0.05
GraphSAGE
LastFM Asia
0.01
Doezer Europe
In the context of GCN networks, considered several additional methods, i.e., Spectral Normalization (SN) (Miyato et al., 2018), GCN-Jaccard (Wu et al., 2019), SVD-GCN (Entezari et al., 2020), and RGCN (Zhu et al., 2019). For SN we trained models subject to various upper Lipschitz bound constraints i.e., 0 E [1,30] The implementations of the strategies aiming at mitigating the effects of perturbations on the graph structure (GCN-Jaccard, SVD-GCN, RGCN) were sourced from the Li al. (2020) library. For each these methods, we adhered to the default parameters as detailed in the respective papers. To find the best model for SVD- GCN, GCN-Jaccard, and RGCN we varied the number of singular values (k {5, 10, 15, 20, 25, 30, 40, 50)), the similarity threshold (r E 0.05, 0.1, 0.3, 0.5, 0.7)), and the hyperparameter in setting the attention weights (y {0.1, 0.3, 0.5, 1, 5)), respectively. In the case of GCN-Jaccard, dissimilar edges were dropped basod on the cosine similarity.
The same experimental configuration presented in Tables and 7 also applicable for AT, RS, SN, SVD-GCN, GCN-Jaccard, and RGCN.
C.3 Attacks and robustness evaluation
We adapted the classical Projected Gradient Descont (PGD) (Madry et al., 2018) to evaluate the robustnoss of the models, building upon an existing implementation available on GitHub (Rony & Ben Ayed, 2023). Since attack several nodes at once, sum the loss over the attacked nodes. The PGD iterations on the perturbation d RN,, for the input graph features æ with labels (Co)vev, read
g
V8 Σ L((T(x )),,)),
DEV
(50)
(())
8(++) = Pas, (5()) + + [g(00
where V is the subset of nodes to attack, B, = fx ||ا|| I E} is the closed Euclidean ball of radius E, 17 is the step-size, and a classification loss. For the attack, we use a relative step-size of 1/20, i.e., 17 = 30 Additionally, it known that PGD with Cross- Pooss-Entropy (CE) can fail on robust models. One workaround is use a loss that better aligns with the misclassification objective (for untargeted allacks): either the Difference of Logits (DL) (Carlini & Wagner, 2017), the more recently proposed Difference of Logits Ratio (DLR) (Croce & Hein, 2020). Note that DLR can only be used for datasets with more than two classes because it relies on the top three (or four for targeted attacks) logits. Therefore, we perform attacks with CE and DL losses, and DLR when possible. Finally, we use a budget of 100 steps for the attack, with 9 additional random restarts, totalling 1 100 steps.
In addition, we also adapted the Auto-PGD attack (APGD) introduced by Croce & Hein (2020), whose only free parameter is the number of iterations. The key distinction in APGD, compared to the conventional
23

---

Published in Transactions on Machine Learning Research (05/2025)
PGD, lies in the selection of the step size at each iteration. In APGD, the step size is dynamically adjusted based on the available budget and the optimization progress. Furthermore, when the step size is reduced, the maximization process restarts from the best point obtained up to that point. As for PGD, we perform attacks with CE and DL losses, and DLR when possible, for 1 100 steps.
D Additional Results
D.1 Impact of the choice of the loss function on the performance of the attackers
We studied the impact of the loss function choice on the success of the PGD and APGD attacks in order to determine the strongest attack for all datasets and network configurations. Therefore, we considered three different losses for the attackers: Cross- ropss-Entrroy (CE), Difference of Logits (DL) (Carlini & Wagner, 2017), and Difference of Logits Ratio (DLR) (Croce & Hein, 2020). Because DLR can only be used for datasets with more than two classes, perform the PGD attack with CE and DL losses, and DLR when possible. Considering the task of transductive node classification, each model having = 3 layers and N; 16 for E (1,2), we analysed how the baseline model and the one trained subjected to spectral constraints behave when facing different levels of perturbations 8, computed with respect to the l2 norm. The constrained model (i.e., choice of 1)) was selected as the model with the largest area under the accuracy-robustuuss curve while ensuring that it exhibits a decrease relative accuracy on the validation dataset of less than 3% when compared to the conventionally trained model. The results for the constrained models are depicted in Figure 4. In evaluating a total of six attack methods, formed by combining two altack techniques (PGD and APGD) with the three distinct loss functions (CE, DL, and DLR), we consistently observed that, regardless of the attack method, DL loss exhibited the strongest adversarial impact, while CE loss resulted in the least effective attack. Specifically, for the Facebook dataset, at lower levels of perturbation, the DLR loss led to a slightly larger decrease in performance. Interestingly, the APGD attack demonstrated greater strength than PGD in the case of CE and DLR losses. However, for the DL loss, the two attackers exhibited almost identical effectiveness.
D.2 Adversarial robustness evaluation with respect to lo norm
While our method primarily focuses computing Lipschitz constant within the lg norm framework, it is worth noting that we evaluated the robustness of our models against an loo attack. We assessed the performance of models subjected to non-negativity and spectral norm constraints against those employing adversarial training (AT) and randomized smoothing (RS). We evaluated all models against the APGD-DL allack, considering various fxx. norms for perturbations on nodes in the test set, specifically || E [0.01, 1]. The accuracy curves are presented in Figure We found that the constrained models behaved similarly or better against for attack as compared to an lz APGD-DL attack. Our models consistently outperform standard models across all datasets and configurations. AT models show, at most, marginal improvement over conventionally trained models. Although RS exhibits better robustness compared to the baseline model, it generally falls short of the effectiveness demonstrated by our approach.
D.3 Results on alternative activation functions
In the experiments conducted this paper, we employed the rectified lincar unit (ReLU) activation function for the intermediate layers, which is the standard choice for our explored models (Kipf & Welling, 2016; Hamilton et al., 2017a). To demonstrate the generalizability of our findings across broad range of component- wise activation functions, Icaky RCLU, and sigmoid linear unit (SiLU). As for ReLU, we asscssed the performance of the bascline and constrained models against. the l APGD-DL allack. Figure 6 presents the results for these models combined with the four activation functions, where et, denotes our constrained models, and the baseline models are represented with a dashed line. In all cases, our models surpassed the bascline in these instances as well, highlighting that our findings hold for diverse array of activation functions, extending beyond the conventional ReL.U choice.
investigated four additional ones, namely, sigmoid, hyperbolic tangent (tanh),
24

---

Published in Transactions on Machine Learning Research (05/2025)
GCN
8-110
3-13.9
After attack accurbiy
60
After atlakk accuracy
PGD
APGD CE
84-
APGID CF
PGD
APGD DLR
APCID DIR
PGD
APGD DL
APGID DL
302
(a) Facebook
(b) LastFM Asia
After attack accuracy
After attack accuracy
APGD CE
10
22-
60
APGD DL
50
60
FGD
APGD
FGD DL
20
APGD
3-0.5
302
400
200
402
302
(c) GitHub
(d) Deezer Europe
GraphSAGE
8-18.0
8-11.
Afher attackk accuracy
60
After attack accuracy
50
PGD CE
PGD
APGD CE
APGD CE
PGD DLR
PGD DLR.
APGD DLR
APGD DUR
20
PGD
PGD
APGD
APGD DL
(e) Facebook
(1) LastFM Asia
Afeer attacck accuracy
8-2.0
After attack accuracy
APGD CE
PGD
PGD
APGD DL
APGD CE
20
APGD DL
102
420
140
(g) GitHub
(h) Deezer Europe
Figure 4: Impact of the loss function on the performance the attackers. Accuracy vs. l norm of the test set perturbation (c). PGD and APGD attack with different loss functions constrained models. (a)-(d) GCN model. (e)-(h) GraphSAGE model.
D.4 Time requirements and experimental durations
All experiments conducted in this paper were performed on an NVIDIA A100 80GB GPU. The cumulative execution time for all experiments amounted to approximately one week.
Tables and present the training times for the bascline model, the constrained model, adversarial training (AT), randomized smoothing (RS), and spectral normalization (SN), averaged across 10 splits. As discussed
25

---

Published in Transactions on Machine Learning Research (05/2025)
GCN
6m448.25
0- 15.99
After attack accuracy
c-150
AT c=100
RS gm0.6
R5 cm0.7
Facebook
(b) Fast
After attock accuracy
7=0.5
RS d-12
0-6.41
AT cm150
38
32
0.4
0.5
86
0.7
0.
0.
03
3.2
0.5
0.7
(c) GitHub
(d) Deezer Europe
GraphSAGE
2-33.34
9-24.63
8-10.0
After attack socuracy
3-10.0
em
AT em50
(e) Facebook
(f) LastF 'MAsia
LastE'MAsia
7.0.5
2
Afeer sttackk accuracy
AT 4-550
RS am:0.5
50
7=2.0
p-0.8
(g) CitHub
(h) Deezer Europe
Figure 5: Robust training. Accuracy vs. foo norm of the test set perturbation (e). APGD attack with DL loss. The blue line represents the bascline model, the orange line represents the constrained model, the green line corresponds to AT, and the red line corresponds to RS. (a)-(d) GCN model. (e)-(h) GraphSAGF. model.
in Appendix C.2, we employ an carly stopping mechanism with patience of 200 iterations. Table 8 presents the average lime per epoch for training each network. Training the constrained GCN model takes, on average, 1.38 the time needed to train the baseline model per epoch. For the GraphSAGE architecture, this ratio is 1.35. Imposing the constraint takes a longer time for more complex datasets, such as Facebook and LastFM
Asia. Naturally, the average time per epoch for RS and AT (without taking into account the additional time for generating the ad adversarial samples and pre-training) is comparable to the time needed to train the
26

---

Published in Transactions on Machine Learning Research (05/2025)
GCN
LeakyRell LeakyRaW
LeakyRelU
After attack accuraicy
After attack accuracy
LeakyReLU
Tanih
Tanh
80
Sigmoid
Sigmoid
Sigmold
Sigmola
SIU
SILLI
50
302
(a) Facebook
(b) LastFM Asia
After attack accuracy
LeakyRRLL ct.
LeakyReLU
After attacck accuracy
LeakyReLL ct.
LeakyReLu
10
60
Tanh
Tanh ct.
50
Sigmold
Sigmald
Sigmold
Sigmald ct.
SIU
SILU
302
400
200
402
302
(c) GitHuu
Deezer Europe
GraphSAGE
LeakyyRLL
LeakyReLL
After attackk accuracy
LeekyReLL
After attack accuracy
LeakyReLU
Tanh
Tanh
Sigmold
Sigmold
Sigrnoid
SIUU
SILU
SiLU
(e) Facebook
(1) LastFM Asia
After attack accuracy
Lea
LeakyReLL ct. Tanih
After attack accuracy
LeakyReLL LeakyReLU ct.
Tanh
Tarth
Tanh ct.
Sigmoid
Sigmaid
80
Sigmoid ct
Sigmoid ct.
SILU
22
SiLUI
SIU ct.
SILU
100
140
(g) GitHub
(h) Deezer Europe
Figure 6: Results on alternative activation functions. Accuracy vs. l norm of the test set perturbation (e). APGD attack with DL loss. The constrained models plotted with solid line and denoted by ct., and the baseline models are represented with dashed line. (a)-(d) GCN model. (e)-(h) GraphSAGE model.
baseline model. In the case of the GCN network, SN exhibits slightly faster training times than our method, and takes, on average, 1.12 x the time needed to train the baseline model per epoch.
Table records the average total time for training each network. As AT being performed starting from a pro-trained network, the total training time represented by the time needed for the conventional training (Baseline GNN), the time required to generate the adversarial samples (AT attack), and the actual training time with the adversarial input (AT). Because training the network subjected to Lipschitz constraint does
27

---

Published in Transactions on Machine Learning Research (05/2025)
not require starting from pre-trained network, our method takes less time to train model, average, than AT. As expected, RS is comparable to the baseline GNN in terms of training time. However, we need to take into account its major drawbacks. To achieve decent robustness, RS requires performing inference multiple times, which results in extensive time consumption, particularly for larger graphs (as shown in Table 10). our experiments, RS took 150 to 400 times longer for inference compared to the other methods. This might. render RS impractical for real-life applications, as takes several seconds for a single inference. In contrast, our method requires minimal time for inference, making it a more efficient choice.
Table 8: Average training time = standard deviation per epoch (GPU) in milliscconds.
Dataset
Baseline GNN
Constrained GNN
RS
AT
SN
Facebook
17.7:10.2
24.2:10.2
19.2.:0.7
18.4+0.5
19.7+00.4
GCN
GitHuub
17.6++0.2
23.3+H0.4
19.9+-2.0
18.3+0.4
19.4+0.3
LastFM Asia
17.5#1..4
27.7::0.2
17.4+0.3
17.610.2
20.0
Deezer Europe
17.4=10.3
23.2
17.5+0.5
17.9+0.4
19.6#0.2
Facebook
19.5+0.22
26.3
18.340.9
20.0
Graph
SAGE
GitHub
21.4++0.3
27.0++0.2
19.8+-211
21.9+0.3
LastFM Asia
18.3+0.3
28.8+0.3
18.3+0.3
18.5+0.2
Deezer Europe
18.7+00.2
24.6++0.3
18.9+0.3
19.4+0.4
Table 9: Average total training time + standard deviation in seconds (GPU). AT allack represents the time to perform APGD attack with DL loss; AT total represents the total time for performing adversarial training.
Baseline GNN
Constrained GNN
Dataset
RS
AT
AT attack AT total
SN
Facebook
12.0+0..8
22.0+8.2
11.9+1.0
9.5+0.9
1.240.1
22.7+1.2
15.6=0.9
GCN
GitHub
18.7+2.2
15.5++2.0
14.8+5.0
13.9-4.0
1.340.0
33.9+4.6
14.2+2.0
LastFM Asia
21.1#:4.0
45.449.4
21.748.6
9.0
1.040.0
31.114.4
28.2+1.7
Deezer Europe
12.94:3.1
15.742.3
10.4
9.340.7
1.1
23.2
13.910.9
Facebook
12.4+-0.7
20.0+99.4
16.0+4.0
11.9-
1.9.0.1
26.2+11.2
Graph SAGE
GitHub
11.5::1.9
18.7#1.77
17.848.5
10.0=0.4
2.640.0
24.242.0
LastFM Asia
12.5#11.8
44.947.55
10.4+0.7
8.8+0.2
1.2+0.0
22.5+11.8
Deezer Europe
9.4-L0.3
17.4
9.340.55
9.0.1..4
1.540.0
19.9
Table 10: Average inference time + standard deviation in milliseconds for different models (GPU).
Dataset
Baseline GNN
Constrained GNN
RS
AT
SN
Facebook
14.8++2.3
13.7++3.9
4275.94242.2
14.8
14.6422.9
GCN
GitHub
16.1
16.3:14.4
6268.24428.6
16.3+4.2
16.1#4.1
Deezer Europe
14.4+0.3
15.0=
4848.8+247.6
14.4+1.2
14.8+0.66
LastFM Asia
12.3+4.11
10.7+3..3
2536.0+277.7
10.3+0.3
11.043.7
Facebook
16.0+1..3
17.943.44
5099.612300.7
15.911.9
Graph
SAGE
GitHub
19.0+1.2
18.643.99
7795.14227.1
18.6+2.99
Deezer Europe
16.110.5 12.5+10.4
14.7:10.4
5376.91218.6
14.614.2
LastFM Asia
11.7+3.0
2614.6+175.3
10.5+0.7
D.5 Impact of the number of layers on robustness
We consider the two particular GNN formulations, symmetrical GraphSAGE and GCN, for which we train networks of varying depths E {2, 4, 6,6,7 7). The hidden dimension of each layer is N, 16 for E (!....,m).
28

---

Published in Transactions on Machine Learning Research (05/2025)
We observe that the deeper the network, the less robust it is to adversarial perturbations. The example of the Facebook dataset is shown in Figure 7. As the number of layers increases, the initial Lipschitz constant. of the network is higher, and thus, it is harder to impose a tight Lipschitz bound. However, we can still find a Lipschitz bound that gives a good robustness accuracy trade-off as the number of layers increases.
GCN
0-25.59
0-9100
0-14.0
After attack accuracy
0-14.0
63
330
(a) 771 layers
(b) 772 4 layers
4.8
8-220.47
8-353.65
3.8
3-18.0
After stttack accuracy
6.-
8-20.0
0.7
6.7
0.1
0.5
65
200
216
400
280
300
(c) m layers
(d) m 7 layers
GraphSAGE
6-25.59
Ø-14,0
After attack wwwtttkaaceee accuracy
3-14.0
2.4
E.
103
202
326
400
5.00
300
2.0
403
5.00
(e) layers
(I)
layers
0-270.47
0.353.65
8-18.0
Afher attack sccuracy
8-20.0
(g) 77 6 layers
(h) 177 7 layers
Figure 7: Impact of the number of layers robustness for the Facebook dataset. Accuracy vs. b norm of
the test set perturbation (c). APGD attack with DI. loss. (a)-(d) GCN model. (c)-(h) GraphSAGE model
29


Reviews:
[{"review_id": "wwjhtwO7kR", "reviewer": "Reviewer_sCZQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Clarity: the article is written clearly, in an accessible and easy to read manner. \n2. Relevance: the authors motivated their work well, and the topic is of interest to at least some TMLR readers.\n3. Correctness: the theoretical claims are, to the best of my knowledge (I did not check the supplementary materials line by line), correct and reasonable. \n4. Promising experimental results. \n\nWeaknesses: \n\n1. Wording: Certain wording of the phrases/text makes the material appear unclear. I outline such requested changes in the section below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes a tighter, non-separable bound for the Lipschitz constant of a graph neural network, and then proposes a projected subgradient approach for constrained optimization of such graph neural networks. Experiments that evaluate the efficacy of such an approach are provided. The authors motivated the approach from a security and robustness perspective.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Lipschitz constants of a function/class of function is not unique. A 1-Lipschitz function is also 2-Lipschitz. What the authors show in theorem 3.1 is a upper bound on Lipschitz constants. As such, words like \"the Lipschitz constant\" (which appears frequently, including in the abstract) is confusing. This wording confusion is furthered by the author's tendency to mix \"the Lipschitz constant\" with \"a Lipschitz constant\" together, for example in page 5 of section 3.2. If the authors are referring to the smallest lipschitz constant possible for a given function, I suggest that they can use \"the optimal Lipschitz constant\" in the text, like in theorem 3.1, to avoid confusion.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z74I0wCteH", "reviewer": "Reviewer_HsXc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the paper is generally well-written and easy to follow\n- the topic is interesting, the proposed solution is clever and seems to perform well on the selected datasets\n- the paper and appendices are quite complete\n\nWeaknesses:\n- the major weakness in my opinion is the nonnegativity constraint on the weights. As pointed out by the authors, this does not seem to affect *the selected datasets*, but it is very probable that it is a **very** strong constraint otherwise. In particular, when using ReLU activations as done in the experiments, after the first layer the outputs are themselves nonnegative, so the subsequent ReLU will never be activated, and the GNN is essentially linear!! (in which case the Lipschitz constant is indeed trivially tight). Linear GNNs might still perform okay (see the SGC model), but the contribution is substantially different in this case. At the very least, other activation functions should be tried (sigmoid, tanh, or even non-conventional ones that output negative values for positive inputs, to emphasize non-trivial interactions with nonnegative weights).\n- again regarding nonnegativity, the paper by Combette and Pesquet is quite extensive, and nonnegative NNs are only a small particular case, could you see other results from this paper be adapted to GNNs? If not, why?\n- a discussion on the proof of the theorem would be appreciable, in particular, how different is it from the original proof? Is this \"just\" adapted to the particular case of GNNs (which is absolutely fine), or are there intrinsic difficulties due to GNNs?\n\nMinor remark:\n- the presentation of the GNNs is quite verbose, with many notations and matrices for simple models. This might be improved, leaving more space for discussions", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the author analyze the Lipschitz constant of Graph Neural Networks with nonnegative weights (the proof is based on an adaptation of a particular case of a paper by Combette and Pesquet.), and develop an optimization method to train these GNNs while enforcing constraints on this Lipschitz constant (based on projected block gradient descent). Motivated by robustness to adversarial attacks on the node features, they perform experiments to showcase the performance and stability of their method compared to baselines, focusing on the popular GCN and GraphSage architecture.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above. A thorough discussion, and at the very least more experiments, around the nonnegativity constraints, which seems very constraining.", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yQTw6rmFhq", "reviewer": "Reviewer_EkfX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- The writing is clear. I can understand the main points of the paper without difficulties.\n- As far as I have confirmed, the theoretical analysis, specifically the proof of Theorem 3.1, is correct.\n- It is numerically verified that the proposed method is robust against adversarial attacks (Figure 2).\n- The proposed estimation method has the limitation that it can only be applied when the weights are positive. This paper properly verifies that this limitation does not significantly impact performance (Table 2).\n- The limitation is discussed correctly (Section 6).\n- Audience is appropriate. In the research of social networks, it is important to study protection against adversarial attacks, such as preventing the propagation of fake news and misinformation. Therefore, robust training of GNNs is an important research topic that interests the TMLR audience.\n\nWeakness\n- This paper claims that the lower the Lipschitz constant is, the better the robustness. However, if I get all the information, no such experimental results are shown (ref: Q.4).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new method of estimating the Lipschitz constant for MPNN-type GNNs whose activation functions are Lipschitz continuous and whose weights are non-negative. This estimation is tight when the activation function is ReLU. The proposed method includes GraphSAGE and GCN as special cases and specific estimates of the Lipschitz constant are derived for those cases.\nBased on the proposed estimation, this paper also proposes an algorithm for robust training in which the Lipschitz constant of the model is constrained to a given value.\nNumerical experiments apply white box global adversarial attacks that modify node features (PGD and APGD) to GNNs trained by the proposed method. The accuracy and robustness are evaluated using multiple datasets and compared with multiple baselines, including robust training methods (adversarial training, Randomized Smoothing), regularization methods (spectral normalization), and robust training for adversarial attacks that change the topology of the input graph (GCN-Jaccard, SVD-GCN, RGCN).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Q.1 This paper claims that the first of the robust training against GNNs is to address the case of networks with continuous node features and fixed topology. However, robust training methods for usual FNNs are defense methods against adversarial attacks that change node features. I want to clarify whether we can use them as baseline methods.\n\n\nQ.2 In Algorithm 1, does DFB stand for dual forward-backward? If so, write it explicitly.\n\n\nQ.3 Section 4.1 writes:\n\n> However, in our experiments, we consider the same bias vector, which is the standard practice.\n\nDoes this mean numerical experiments use the same learnable bias vector for all layers? I want to clarify the supporting evidence because I do not know such a practice if my understanding is correct.\n\n\nQ.4 Section 4.1 writes:\n\n> As we tighten the constant, the drop in accuracy becomes more significant, but the model's ability to withstand adversarial pertubations improves compared to the conventionally trained model\n\nHowever, I could not find the rationale for this. Table 2 shows that the accuracy is increased. However, it was not clear whether lowering θ improves robustness. I want to clarify this point.\n\n\nQ.5 In Section 4.2, this sentence was hard to parse:\n\n> Comparing the performance of the PGD and APGD attacks with Cross Entropy [...] and Difference of Logitis [...] losses, and Differences of Logits [...] kisses\n\nDoes this mean that six different attack methods were compared by combining two attack methods (PGD and APGD) and three losses (CE, DL, DLR)?", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers found the paper well-written, interesting, and correct. They mostly had only minor concerns about it, many of which have been addressed in the revised version of the paper. It is not clear how limiting the constraint for the weights to be non-negative is in general, but the authors are upfront about this and the results in the paper show that it does not degrade model performance substantially on a range of datasets.
Decision: Accept (poster)