acceptodds
Under review as a conference paper at ICLR 2027

Studying Adversarial Resilience over Graph Topology

Abstract

Adversarial attacks to graph analytics are gaining increased attention. To date, two lines of countermeasures have been proposed to resist various graph adversarial attacks from the perspectives of either graph per se or graph neural networks. Nevertheless, a fundamental question lies in whether there exists an intrinsic adversarial resilience state within a graph regime and how to find out such a critical state if exists. This paper contributes to tackle the above research questions from three unique perspectives: i) we regard the process of adversarial learning on graph as a complex multi-object dynamic system, and model the behavior of adversarial attack; ii) we propose a generalized theoretical framework to show the existence of critical adversarial resilience state; and iii) we develop a condensed one-dimensional function to capture the dynamic variation of graph regime under adversarial perturbation, and pinpoint the critical state through solving the equilibrium point of adversarial perturbation-mapping function. Multi-facet experiments are conducted to show that the proposed approach can significantly outperform the state-of-the-art defense methods on five commonly-used real-world datasets.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Graph adversarial attack, Asymptotically-stable equilibrium points, Adversarial resilience, Perturbation modeling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ZN1nOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes EquiliRes, a defense against graph structure poisoning attacks. It models adversarial perturbations as a nonlinear dynamic system and, using Lur’e-type absolute stability results and a Laplace-transform formulation, argues that each graph has an asymptotically stable equilibrium point representing a “critical state of adversarial resilience”. Using a mean-field reduction, the dynamics are condensed into a one-dimensional equation whose parameters are computed from node degree statistics. In practice, the method computes this equilibrium point from the clean graph and then iteratively removes edges with low Jaccard similarity (over 2-hop neighborhoods) from the perturbed graph, keeping modifications that move the degree-based statistics toward the reference point. Experiments on five datasets under Metattack, CE-PGD and DICE show improvements over GCN and GCN-SVD, and gains when EquiliRes is used as a preprocessing step for GAT, RGCN, HANG, Mid-GCN and GOOD-AT.

Critical strengths

The method is simple and lightweight, with running time close to GCN and GCN-SVD, and it can be used as a preprocessing step on top of existing defenses.

Critical weaknesses
  1. The theory is largely disconnected from the method. The matrices A, B, C and the nonlinearity in the dynamic model are never derived from an actual attack or GNN, and the key parameters θ and η are set by hand for each dataset (Table 4). The stability results (Theorem 2.5) are standard textbook results for Lur’e systems, and the actual algorithm only uses degree statistics and Jaccard similarity. The claim that the theory locates a “critical state of adversarial resilience” is therefore not supported.
  2. Modeling a one-shot structure attack as a continuous-time dynamic system, analysed with Laplace transforms, is not justified. The observation that attacked graphs lie on the equilibrium curve (Figures 2–6) may be circular, since both the points and the curve are computed from the same degree-based formulas with hand-tuned parameters.
  3. The practical algorithm is essentially Jaccard-based edge pruning, similar to GCN-Jaccard and GNNGuard, but these methods are not included as baselines. Pro-GNN is only compared in running time, not accuracy.
  4. The experimental setup is non-standard and the baseline results are unusually low. Node features are ignored, so clean GCN accuracy on Citeseer is only 54.85% and GCN-SVD only 46.12%, far below commonly reported values. This makes the results hard to compare with prior work.
  5. Several reported numbers raise concerns. In Table 2, HANG on Polblogs at 15%, 20% and 25% perturbation (86.53±1.47, 81.41±1.94, 73.11±2.60) is identical to EquiliRes in Table 1. In Table 7, Ours+HANG on Citeseer at 10% and 15% are identical (49.62±2.17). On Amazon Photo, many results have standard deviations of 20–32 (e.g., 82.25±30.00), so the claimed improvements are not meaningful.
  6. The adaptive attack is weak. It only relaxes the adjacency matrix to [0,1] rather than targeting the defense (e.g., its degree statistics or the Jaccard-based pruning). Even under this attack, Ours+GAT performs worse than GAT on Polblogs at most perturbation rates (Table 8).
  7. The writing needs substantial improvement: there are many grammatical errors, inconsistent terminology (e.g., “Laplace Transfer”), and overstated claims such as a “provable” solution.
Questions for authors
  1. How are A, B, C and φ obtained for a specific attack and GNN, and how should θ and η be chosen for a new graph without tuning?
  2. Are the points in Figures 2–6 computed independently of the equilibrium curve, or do both come from the same degree formulas?
  3. How does EquiliRes compare in accuracy with GCN-Jaccard, GNNGuard and Pro-GNN under the same setting?
  4. Can you explain the identical numbers in Tables 1, 2 and 7, and report results with node features under the standard benchmark setting? How does EquiliRes perform under an adaptive attack that directly targets its degree-based statistics and edge-pruning rule?
10 comments

Q1: Disconnection between theory and attacks/GNN, θ\theta and η\eta set by hand.

The theory is the prerequisite of Algorithm 2. Eq. (1) is a unified formula to map GAAs given perturbations can be described into both linear and nonlinear perturbations. Eq. (9) presents the concrete attack with specified θ\theta and η\eta.

θ\theta and η\eta are not set by hand, they must satisfy: i) Eq. (9) has ASEP; ii) curves in Figs. 2-6 well-match practical points. Referring to theory of CDSs (No principled way to ascertain parameters), we need use a trial-and-error fashion.

Q2: Stability for Lur’e systems vs. Jaccard.

Our work bridges a connection between adversarial learning and Lur’e systems, then explore ASEP as critical attack-resilient state. We formulate continuous perturbations as a dynamic function, and employ 1D function to map GAAs. We give Theorem 2.5 referring to Stability Theory.

We don’t use Jaccard to prune edges, since GCN-Jaccard edge-level decision is based on homophily test on node features, while EquiliRes modifies edges referring to ASEP calculated solely on topology.

Q3: One-short attack as continuous-time dynamics.

The strong GAAs usually use multi-step attacks to progressively refine perturbations, e.g., our used PGD iteratively updates perturbations via gradient ascent. Metattack iteratively modifies edges using meta-gradients. They both employ multi-step optimization to construct adversarial graphs, rather than a one-shot perturbation. This is why we model GAAs as a continuous-time dynamics, and utilize Laplace Transform to capture long-time (multi-step) attack effect (Eq. (2)).

Q4: The points and curves in Figs. 2-6 are from same formulas.

We clarify two points: i) the curves are drawn using the same Eq. (9) but different θ\theta and η\eta for distinct datasets. In theory, there does not exist principled way to ascertain the values, thus we need manually figure out; ii) the points are not hand-tuned, but the actual results under the three attacks.

Q5: Baselines.

Refer to Table R1 (Q6: Reviewer GWEs).

Q6: Low baseline & node features.

The topology-only usage leads to low accuracy for baselines. If node features are involved together, the results becomes high (Tables R8-R9).

Table R8: Accuracy on Cora_ML.

GAAPer.0%5%15%25%
MetattackGCN-SVD82.71±0.8081.64±0.8478.57±0.9562.79±17.29
GCN-Jaccard84.23±0.9478.96±0.8770.28±1.4559.23±4.71
EquiliRes(Top.+Fea.)85.24±0.9685.24±0.9681.50±1.0779.20±1.28
CE-PGDGCN-SVD82.71±0.8082.29±0.6681.18±1.2280.80±0.55
GCN-Jaccard84.23±0.9483.34±1.0681.53±0.8681.17±0.82
EquiliRes(Top.+Fea.)85.24±0.9683.57±0.9283.07±0.8682.94±0.90
DICEGCN-SVD82.71±0.8081.48±0.6579.01±0.8975.90±0.87
GCN-Jaccard84.23±0.9483.00±0.9280.61±0.8877.52±1.28
EquiliRes(Top.+Fea.)85.24±0.9683.54±0.8982.42±1.0380.78±0.79

Table R9: Accuracy on Cora under Metattack.

Def.\Per.0%5%15%25%
GCN83.00±1.0075.35±1.8459.08±4.0843.97±3.58
EquiliRes(Top.+Fea.)83.24±1.0180.32±1.2878.07±1.2075.21±1.59
GAT83.28±1.0179.65±1.7571.36±4.6361.78±4.41
Ours+GAT83.88±1.1081.22±1.2279.74±1.0977.04±1.55
Mid-GCN83.10±0.4175.81±15.8275.43±1.1174.43±0.83
Ours+MidGCN83.23±0.3681.48±0.3776.41±1.1874.69±1.21

Q7: Identical values & large deviation on Amazon Photo.

We rerun experiments: 86.53±1.47/81.41±1.94/73.11±2.60 of HANG in Table 2 are replaced by 72.10±3.97/65.38±1.62/64.53±2.26, 49.62±2.17/49.62±2.17 of Ours+HANG in Table 7 are replaced by 53.91±2.61/53.13±1.61.

We run experiments to analyze deviation in Table R10, they can be remarkably declined via adequate settings.

Table R10. Accuracy on Amazon Photo under Metattack.

Def.Setting\Per.5%15%25%
EquiliRes200 epochs+10 runs91.59±0.6389.18±0.9677.13±7.84
200 epochs+50 runs91.16±1.3389.27±1.2373.19±10.00
1000 epochs+10 runs91.92±0.2490.54±0.4585.93±2.14

Q8: Adaptive attacks.

We use the strategy, i.e. knowing edge-pruning rule. Seen from Table R11, EquiliRes performs well due to dual-direction approaching to ASEP.

Table R11: Accuracy under knowing edge-pruning rule.

DatasetDef.\Per.15%20%25%
PolblogsGCN57.67±2.1650.39±3.0549.53±2.23
EquiliRes61.84±1.1157.22±1.4957.12±2.57
HANG72.10±3.9765.38±1.6264.53±2.26
Ours+HANG88.54±2.2986.36±1.8979.59±3.59
GOOD-AT93.50±0.9893.70±1.1992.73±1.85
Ours+GOOD-AT95.24±0.3594.05±0.5793.80±0.96

We study another strong adaptive attack (Mujkanovic et al.) in Table R12.

Table R12: Accuracy.

DatasetDef.\Per.5%10%
CiteseerGCN58.49±2.0249.75±1.22
GCN-SVD61.33±4.6658.13±1.58
GCN-Jaccard60.91±2.1254.75±0.95
GNNGuard56.16±2.3052.37±1.11
EquiliRes65.60±1.5862.66±0.95

Thank you for the response and the additional experiments. However, my main concerns remain. The parameters are still chosen by trial and error to match the observed points, so the theory–method connection and the circularity issue are not resolved. The modelling of a one-shot structural attack as continuous-time dynamics is still not justified. The practical algorithm still remains essentially Jaccard-based pruning. In addition, the identical numbers are corrected without explanation, and similar duplications appear in the new tables. This raises further concerns about the reliability of the results. I therefore keep my original score.

We thank the reviewer for raising these remaining concerns. We would like to further clarify them as follows:

Q1: The parameters are still chosen by trial and error to match the observed points, so the theory–method connection and the circularity issue are not resolved.

We clarify this issue in more detail:

i) Theory Guidance: the theorems 2.5/3.2/3.3 provide a generalized theoretical framework to present the ASEP represents a critical attack-resilient state for graphs.

ii) ASEP-Trajectory Fitting via Trial-and-Error: resorting to the above theory, we use “trial-and-error” fashion to fit the ASEP trajectories in Figs. 2-6 by setting θ\theta and η\eta by hand.

iii) Why Use Trial-and-Error Fashion: there does not exist a universal construction theorem that guarantees an explicit dynamical function satisfying both exact data fitting and asymptotic stability (ASEP) for arbitrary datasets.

To support this point, we give the following two simple counterexamples:

Counterexample I:

Consider the scalar autonomous system x˙=f(x)\dot{x}=f(x). Suppose the equilibrium x∗x^*=0 is required to be asymptotically stable. A necessary condition is that, in some neighborhood of the equilibrium,

f(x)>0for x<0,f(x)>0 \quad \text{for }x<0,

f(x)<0for x>0.f(x)<0 \quad \text{for }x>0.

Now consider a dataset containing the single observation D=(1,1)\mathcal D={(1,1)}, which imposes the exact interpolation constraint (f(1)f(1)=1). This constraint contradicts the necessary stability condition (f(1)f(1)<0), provided the equilibrium is required to be globally asymptotically stable. Thus, no function can satisfy both requirements for this dataset.

Counterexample II:

Even when a given dataset is fully fitted with an asymptotically-stable dynamical function, the underlying dynamical function cannot, in general, be uniquely identified from a finite set of observations.

Consider a finite dataset $ \mathcal D={(x_i,y_i)}_{i=1}^{N}$, and suppose function f0(x)f_0(x) exactly interpolates all observations: $ f_0(x_i)=y_i, i=1,\ldots,N. $

We can construct another function:

$ f_1(x)=f_0(x)+c\prod_{i=1}^{N}(x-x_i), $

where cc is an arbitrary constant. By construction, $ f_1(x_i)=f_0(x_i)=y_i, i=1,\ldots,N. $

Consequently, both functions produce exactly the same predictions at every observed data point, despite generally exhibiting different behaviors outside the observed sample locations. Indeed, varying cc yields infinitely many distinct functions that are observationally indistinguishable w.r.t. the given dataset. This issue is closely related to structural identifiability in system identification [1] [2], which concerns whether distinct model parameters can produce identical observable outputs.

To sum up, there is no universal theorem guaranteeing an explicit function that exactly fits every dataset while simultaneously guaranteeing ASEP. This is why we need use trial-and-error fashion.

[1] Identifiability and numerical algebraic geometry, PLOS ONE 2019.

[2] Data-based identifiability analysis of non-linear dynamical models, Bioinformatics, 2007.

Algorithm 2 follows the theory, but it does not use θ\theta or η\eta. The theory first gives a measure of how resilient a graph is: β~\tilde \beta, computed from node degrees (Algorithm 1); second, it shows a critical attack-resilient state (ASEP) exists for graphs. An attack moves away from the critical state, and β~\tilde \beta drops. Algorithm 2 moves the graph back: it removes an edge only if the removal increases β~\tilde \beta. θ\theta and η\eta are used for one purpose only, to draw the theoretical curves in Figs. 2-6. Algorithm 2 never reads them, so the accuracy results do not depend on their values.

Q2: The modelling of a one-shot structural attack as continuous-time dynamics is still not justified.

After a one-shot attack the graph is fixed, and nothing evolves in physical time. The continuous-time equation describes the computation of the node representations on the attacked graph. Here three things have to be kept apart:

i) The Attack Acts Once. It changes the topology and is then over.

ii) What changes is the representation that a GNN computes on the attacked graph. This representation is not obtained in one step: it is computed by message passing, layer by layer, each layer aggregating the neighbours once more.

iii) xi(t)x_i(t) in Eq. (1) denotes the representation (state) of node ii, and tt is the propagation time, i.e. the continuous counterpart of the layer index. This is similar as graph neural diffusion/flow (Chamberlain et al., 2021; Song et al., 2022; HANG, Zhao et al., 2023), which also study robustness to one-shot topology attack.

The attack therefore enters the model as a one-time change of the coupling between the nodes, not as a process in time. The dynamics determines where the representations settle on the attacked graph, and whether this is still the equilibrium of the graph. This is what matters for the defense.

Reviewer_YUSGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a graph topology-based defense against adversarial attacks on graph neural networks, which is named EquiliRes. It models graph adversarial perturbations using a continuous-time dynamical system and identifies an asymptotically stable equilibrium point to characterize graph resilience. It then uses a one-dimensional approximation of graph dynamics and reconstructs the graph topology based on the identified equilibrium point. Experiments on five graph datasets show improvements in node classification accuracy under several adversarial attacks.

Critical strengths
  1. The paper studies graph adversarial robustness from the perspective of dynamical system stability, offering a different approach to graph defense.
  2. The authors provide a theoretical analysis of stable equilibrium points and use the results to guide graph topology reconstruction.
  3. The experiments cover five datasets and several adversarial attacks. The method is also combined with existing GNN defenses, showing its potential as a preprocessing approach.
Critical weaknesses
  1. The theoretical results rely on several assumptions about the system matrices and nonlinear mapping function. However, the paper does not sufficiently justify whether these assumptions hold for different graph topologies and attack strategies.
  2. The proposed framework mainly relies on degree-related properties to characterize graph resilience. However, graphs with similar degree distributions can have very different local structures and adversarial vulnerabilities. It is unclear whether these properties are sufficient to characterize graph robustness.
  3. Eq. (6) reduces graph dynamics to a single variable using a heterogeneous mean-field approximation. This simplifies the analysis but may discard important structural information. It would be helpful to clarify this design.
  4. The experiments mainly focus on edge perturbations. Other common attacks, such as node feature perturbations and node injection, are not evaluated, which limits the generality of the experimental findings.
Questions for authors
  1. How can the theoretical stability assumptions be verified for real-world graphs and different adversarial attacks?
  2. Why are degree-related properties sufficient to characterize graph resilience? How would EquiliRes perform on graphs with similar degree distributions but different connectivity structures?
  3. Does the existence of an asymptotically stable equilibrium point necessarily lead to improved GNN robustness? Can the authors establish a more direct theoretical connection?
  4. How would EquiliRes perform against node feature perturbations and node injection attacks, given that the method mainly focuses on graph topology reconstruction?
3 comments

Q1: Whether theoretical assumptions hold for real-world graphs and different adversarial attacks.

Our approach aims to propose a generalized defense for graph data, thus, Eq. (1) is not a concrete but unified formula to map all graph adversarial attacks from the viewpoint of dynamics, regarding adversarial perturbations over graph can usually be described into two parts: i) linear perturbation; and ii) nonlinear perturbation. Therefore, the dynamic-variation function under continuous perturbations can be defined a differential function of time tt, and matrices AA, BB, CC are leveraged to specify different adversarial attacks.

In addition, the designed heterogeneous mean-field (HMF) theory resorts to the basic in/out-degree of nodes to approximate the whole graph’s information, thus, whatever types of graphs, as long as there exist nodes and associated edges, the HMF approximation fashion can always be applied.

Therefore, from the viewpoints of unified GAA modeling (Eq. (1)) and HMF-based graph information, the theoretical assumptions can hold for different graph topologies and adversarial attacks.

Q2: Why degree-related properties sufficient to characterize resilience, regarding similar degree-distributions with different connectivity structures.

From the angle of topology, we can find out the asymptotically-stable equilibrium point (ASEP) to locate the critical attack-resilient state, thus it is sufficient for our proposed theoretical framework to serve as a guidance to enhance graph's resilience.

We run experiments w.r.t. similar degree-distribution with different connectivity structures, and depict the results in Table R6, from which we observe that our method still performs well.

Table R6. Accuracy on Polblogs with degree-preserving rewiring of r·|E| edge pairs.

SettingDef.\rr=0r =0.1r=0.3r =0.5
Graphβ~\tilde \beta81.2681.2681.2681.26
Homophily0.9060.8090.6890.615
DICE 20%GCN80.08±0.2474.85±0.4462.97±0.6451.49±0.41
Mid-GCN62.33±4.3251.12±0.6751.06±0.7051.55±0.41
RUNG78.24±0.4973.84±0.4957.26±1.0848.83±1.60
EquiliRes86.52±1.4381.69±0.2672.48±0.4256.41±0.50
CE-PGD 20%GCN70.86±0.3169.98±0.2166.99±1.2253.74±1.93
Mid-GCN67.55±1.2759.33±3.6748.98±2.3650.63±0.75
RUNG70.53±0.2868.90±1.9865.83±1.3654.38±1.04
EquiliRes75.04±0.7574.00±0.2074.50±0.5666.54±1.21

Q3: HMF approximation discards important structure information.

Consider the expensive overhead for high-dimensional graph data, especially today’s large-scale networks/graphs, we need design a feasible dimension-reduction fashion, thus, the HMF theory is used to approximate the entire graph’s perturbation into 1D function (Eq. 6).

In fact, the best way is to build one dimension for each node, which can capture the fine-grained adversarial perturbations. Nevertheless, such operation may be difficult regarding the feasibility, resulting from two main reasons: i) theoretically, there is no principled guidance on how to establish an ASEP-reserved function; and ii) for high-dimensional function, the analysis on whether it has an ASEP is extremely sophisticated due to the intrinsic correlation among different dimensions, leading to impossible to calculate under GCN-related models.

Q4: Focus on node feature perturbations.

We run experiments at different rates of node-feature perturbations, and report the results in Table R7.

Table R7: Accuracy on Cora_ML under node-feature perturbation.

GAADef.\Per.5%10%15%20%25%
MetattackGCN78.01±0.9372.36±1.9166.06±2.5958.29±3.1049.94±3.77
GCN-SVD80.98±0.8777.26±0.4275.68±0.7474.05±0.2673.73±0.56
Ours+GCN-SVD80.62±0.50 (0.36%↓)79.50±0.43 (2.24%↑)77.89±0.76 (2.21%↑)74.38±0.51 (0.33%↑)74.22±0.40 (0.49%↑)
GCN-Jaccard77.93±1.2676.62±0.7975.52±0.8874.52±1.2373.49±1.13
Ours+GCN-Jaccard78.92±0.39 (0.99%↑)75.71±0.62 (0.91%↓)76.69±0.45 (1.17%↑)75.55±0.56 (1.03%↑)74.85±0.35 (1.36%↑)
GNNGuard77.13±0.6774.57±1.4573.99±1.1672.66±1.6173.35±0.77
Ours+GNNGuard77.16±0.79 (0.03%↑)76.33±1.04 (1.76%↑)74.86±1.02 (0.87%↑)72.60±0.64 (0.06%↓)74.44±0.83 (1.09%↑)
RUNG84.15±0.3079.76±0.5775.36±0.5373.33±0.8967.94±1.77
Ours+RUNG83.83±0.24 (0.32%↓)82.09±0.47 (2.33%↑)81.46±0.29 (6.10%↑)80.98±0.51 (7.65%↑)80.08±0.29 (12.14%↑)

Q5: Does ASEP lead to improved GNN robustness? Establish more direct theoretical connection.

Our approach enhances the resilience from the viewpoint of graph topology through locating the critical attack-resilient state, without retraining GNN/GCN-related models, thus our approach is model-agnostic, in other words, the Theorem 2.5 (Existence of ASEP) adapts GNN as well, the new experiments in Table R1 showcase our approach outperforms GNNGuard, which also verifies this point.

I thank the authors for the clarification and additional experiments. They help address some of my concerns. However, I still have questions about the limitations of the HMF approximation and how ASEP leads to better GNN robustness. These points could be further clarified. Therefore, I will keep my original score.

We thank the reviewer for the feedback. We clarify the two remaining points with new measurements.

Q1: Limitations of the HMF approximation.

(i) What it assumes. The HMF reduction replaces the neighbours of each node by a degree-weighted average over the graph. This is accurate when the degree correlation is small (Appendix E).

(ii) How well the assumption holds. We measured the degree assortativity rr of the five graphs: Citeseer +0.01+0.01, Amazon Photo −0.05-0.05, Cora −0.07-0.07, Cora_ML −0.08-0.08, Polblogs −0.22-0.22. The condition is well satisfied.

(iii) What it cannot capture. The reduced function keeps the degree sequence only. Structure beyond the degrees (communities, clustering) is not represented, so it describes the graph at a coarse level. Table R6 shows this: the rewired graphs have the same β~\tilde \beta (81.26) but different homophily and different accuracy.

(iv) How our method handles it. Algorithm 2 uses only the direction in which β~\tilde \beta changes, not the value of the predicted equilibrium, and it examines the edges in the order of their 2-hop similarity, which brings in the local structure that the HMF reduction leaves out. EquiliRes therefore remains above GCN in all eight settings of Table R6. A multi-dimensional mapping (Remark 3.1) is the natural refinement if the high computational power is allowed.

Q2: How ASEP leads to better GNN robustness.

We measured it on the attacked graphs of our protocol (Metattack, budget b=0.5b = 0.5, average of 3 attacked graphs) as shown in Tables R13-R14:

Table R13. Ratio of removing the inserted/perturbed edges on Polblogs.

5%15%25%
Edge homophily, attacked graph0.8770.8270.794
Edge homophily, after EquiliRes0.9070.8990.888
Inserted edges removed by EquiliRes (%)98.895.287.3

Table R14. Ratio of removing the inserted/perturbed edges on Cora.

5%15%25%
Edge homophily, attacked graph0.7680.7060.656
Edge homophily, after EquiliRes0.8190.8080.785
Inserted edges removed by EquiliRes (%)87.090.186.7

(i) The attack inserts mainly inter-class edges. It moves the graph away from the ASEP (β~\tilde \beta on Polblogs drops from 81.3 to 72.5) and lowers the homophily.

(ii) Moving the graph back toward the ASEP removes 87.3–98.8% of the inserted/perturbed edges on Polblogs and 86.7%-90.1% on Cora and brings the homophily back to the level of the clean graph.

(iii) Message passing aggregates the neighbours of a node, so a GNN is accurate when the neighbours share the label of the node. With the homophily restored, the accuracy recovers (Table 1). No retraining or change of the GNN is needed, which is why EquiliRes also improves GAT, RGCN, HANG, Mid-GCN and GOOD-AT (Table 2).

Theorems 2.5 and 3.3 establish the existence and stability of the ASEP; the link from the ASEP to the accuracy is supported by the measurements above.

Reviewer_GWEsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes EquiliRes, a structure-based defense against GNN poisoning attacks. It models attacks as a nonlinear dynamic system, gives conditions for an asymptotically stable equilibrium point (ASEP), and reduces graph dynamics to a 1D resilience function. Extensive experiments on five real-world datasets demonstrate that the proposed approach significantly outperforms state-of-the-art baselines

Critical strengths
  1. Viewing graph robustness through dynamic-system stability is a fresh perspective.
  2. The method is lightweight and works as a plug-in for existing defenses.
  3. Experiments cover several datasets, attacks, and backbones, with runtime analysis.
Critical weaknesses
  1. Theorem 2.5 is essentially the classical Popov criterion [1], and the 1D reduction follows Gao et al. [2]. The novel parts are unclear.
  2. The mapping from attacks to Eq. (1) is metaphorical: x(t), A, B, C, φ, and “time” are never concretely defined for any attack.
  3. Theorem 3.3 conflicts with Figs. 2–6: the fold-shaped curve [2] has an unstable lower branch, so not all equilibria can be asymptotically stable.
  4. Algorithm 2 uses none of the theory (no Hurwitz condition, k, θ, or Lyapunov function). It is essentially Jaccard edge pruning with a degree-based acceptance rule.
  5. Feature usage seems inconsistent across methods.
  6. Missing baselines: GCN-Jaccard [3] (the closest method), GNNGuard [4], Pro-GNN accuracy [5], and RUNG [6].
  7. The adaptive attack (relaxing A to [0, 1]) is not truly adaptive [7]. It is tested only on Polblogs, where Ours+X is often worse than X. Scalability is overstated: the largest graph has 7.6k nodes, there is no complexity analysis, and Ours+GAT/HANG take about 3× longer on Citeseer.
  8. Larger graphs such as ogbn-arxiv [8] should be tested.

1] H. K. Khalil, Nonlinear Systems, 3rd ed., Prentice Hall, 2002 .

[2] J. Gao, B. Barzel, A.-L. Barabási, Universal Resilience Patterns in Complex Networks, Nature 2016.

[3] Adversarial Examples for Graph Data: Deep Insights into Attack and Defense, IJCAI 2019.

[4] GNNGuard: Defending Graph Neural Networks against Adversarial Attacks, NeurIPS 2020.

[5] Graph Structure Learning for Robust Graph Neural Networks, KDD 2020.

[6] Robust Graph Neural Networks via Unbiased Aggregation, NeurIPS 2024.

[7] Are Defenses for Graph Neural Networks Robust?, NeurIPS 2022.

[8] Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.

Questions for authors
  1. What are x(t), A, B, C, φ, and t for a concrete attack such as Metattack?
  2. Which equilibrium is stable, and how is the unstable lower branch handled?
  3. How were θ and η chosen, and how sensitive are the results to them?
  4. How does EquiliRes compare with plain Jaccard pruning at the same edge budget?
  5. Were node features used for all baselines? Why is GCN only 54.85% on Citeseer?
  6. Can you verify the duplicated entries in Tables 2, 7, and 12?
  7. How does EquiliRes compare with GCN-Jaccard, GNNGuard, and Pro-GNN?
  8. How does it perform under an adaptive attack that knows the pruning rule?
  9. What is the complexity of Algorithm 2? Can it run on graphs with more than 100k nodes?
1 comment

Q1: Novelty.

Our work attempts to bridge a connection between adversarial learning and CDSs, and explores ASEP as critical attack-resilient state. We formulate continuous perturbations using dynamic-variance function (Eq. (1)), and use 1D function to map GAAs.

We give Theorem 2.5 referring to Stability Theory (Popov/Lyapunov criterion).

For 1D function, it differs from Gao et al. [2], since the mapping function we use need to consider the property of GAA, different from the resilience of ecological networks generated by randomly removing nodes in [2].

Q2: Parameters of Eq. (1) never defined.

Eq. (1) is a unified formula to map GAAs, regarding the perturbations can usually be described into linear and nonlinear perturbations. So the dynamics can be defined as a differential function of time tt, with matrices AA, BB, CC specifying attacks.

Q3: Confliction between Theorem 3.3 and Figs. 2-6.

Eq. (8) satisfies Theorem 3.3. If x~=0\tilde x=0, then dx~dt=0\frac{{d\tilde x}}{{dt}} =0, it represents the so-called “fold-shaped” curve, implying the entire graph is completely broken. Although such a curve denotes the equilibria, but not what we want, we need to infer other equilibria as shown in Figs. 2-6. Theorem 3.3 evidences Eq. (8) has ASEP, by which the solid curves are drawn theoretically, thus Theorem 3.3 does not conflict Figs. 2-6.

Q4: Algorithm 2 uses none of theory & Jaccard pruning.

Algorithm 2 actually depends on the theory. In Algorithm 2, β~\tilde \beta is the nonlinear function of variable x~\tilde x (Eq. (9)) which is subject to the ASEP, i.e. Theorems 2.5/3.2/3.3 guarantee the existence of ASEP, by which Algorithm 2 can locate the critical attack-resilient state.

EquiliRes is essentially not a variant of Jaccard, since GCN-Jaccard edge-level decision is based on a homophily test on node features. Differently, our method modifies edges referring to ASEP calculated solely on topology.

Q5: Feature usage.

All methods only use topology without features.

Q6: Baselines.

Table R1 shows comparative results.

Table R1: Accuracy (%) under Metattack.

DatasetDef.\Per.10%15%20%
CoraGCN-Jaccard58.35±3.3255.91±3.0255.04±3.76
EquiliRes59.75±2.7958.22±2.6657.36±2.91
GNNGuard73.06±1.4472.65±1.5873.01±1.80
Ours+GNNGuard74.29±1.4072.21±1.4073.29±1.46
RUNG76.92±0.5674.37±0.6471.90±0.79
Ours+RUNG78.05±0.5376.88±0.5976.26±0.44

Q7: Adaptive attacks.

Use the mentioned strategy, i.e. knowing edge-pruning rule. Table R2 shows the results.

Table R2: Accuracy under knowing edge-pruning rule.

DatasetDef.\Per.15%20%25%
PolblogsGCN57.67±2.1650.39±3.0549.53±2.23
EquiliRes61.84±1.1157.22±1.4957.12±2.57
HANG72.10±3.9765.38±1.6264.53±2.26
Ours+HANG88.54±2.2986.36±1.8979.59±3.59
GOOD-AT93.50±0.9893.70±1.1992.73±1.85
Ours+GOOD-AT95.24±0.3594.05±0.5793.80±0.96

We also study strong adaptive attack (Mujkanovic et al. [7]) in Table R3.

Table R3: Accuracy under adaptive attacks.

DatasetDef.\Per.5%10%
CiteseerGCN58.49±2.0249.75±1.22
GCN-SVD61.33±4.6658.13±1.58
GCN-Jaccard60.91±2.1254.75±0.95
GNNGuard56.16±2.3052.37±1.11
EquiliRes65.60±1.5862.66±0.95

Q8: Sensitivity of θ\theta and η\eta.

θ\theta and η\eta are sensitive to ASEP. Referring to theory of CDSs (No principled way to ascertain parameters), we need use a trial-and-error fashion. However, as long as the curves w.r.t. θ\theta and η\eta match the practical points, EquiliRes will perform well.

Q9: GCN only 54.85%.

EquiliRes only considers topology, leading to low 54.85%, if features are integrated, the accuracy will raise remarkably (Tables R8-R9).

Q10: Duplicated entries.

We mistakenly posted the wrong values and correct that: 86.53±1.47/81.41±1.94/73.11±2.60 of HANG on Polblogs in Table 2 are replaced by 72.10±3.97/65.38±1.62/64.53±2.26, and 49.62±2.17/49.62±2.17 of Ours+HANG on Citeseer in Table 7 by 53.91±2.61/53.13±1.61.

Q11: Complexity & larger graph.

Algorithm 2: Θ(C+mlogm) (m= # edges, C= # 2-hop neighbors of paired nodes per edge).

We run ogbn-arxiv (#node: 169,343) in Table R4.

Table R4: Accuracy.

GAADef.\Per.5%10%
PR-BCDGCN42.79±0.2335.42±0.12
GCN-Jaccard43.46±0.1235.97±0.08
GNNGuard42.66±0.2335.46±0.09
EquiliRes55.05±0.1548.09±0.09

Q12: Comparison with Jaccard at same budget.

Compare EquiliRes with plain Jaccard pruning (PJP) that removes exactly the same number of edges (Table R5).

Table R5: Accuracy under Metattack.

DatasetDef.\Per.5%15%25%
CoraPJP62.33±2.6555.91±3.0253.96±3.31
EquiliRes62.47±2.7558.22±2.6656.88±2.74
PolblogsPJP88.24±1.3280.28±0.8276.86±2.63
EquiliRes90.19±2.4189.83±2.3779.71±3.31

Comments on the paper

1 comment
AuthorsOpenReview ↗

Kind Reminder from Authors

Dear Reviewers and AC,

Thank you for your valuable feedback on our work. We have addressed the comments point by point, providing additional experiments and clarifications.

As the discussion period is drawing to a close, we would greatly appreciate it if you could review our responses. If you have any remaining concerns or questions, please let us know, and we will be happy to provide further explanations.

Thank you again for your time and consideration.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.