- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
- 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
- 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?
- Are the points in Figures 2–6 computed independently of the equilibrium curve, or do both come from the same degree formulas?
- How does EquiliRes compare in accuracy with GCN-Jaccard, GNNGuard and Pro-GNN under the same setting?
- 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
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 and 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 . Suppose the equilibrium =0 is required to be asymptotically stable. A necessary condition is that, in some neighborhood of the equilibrium,
Now consider a dataset containing the single observation , which imposes the exact interpolation constraint (=1). This constraint contradicts the necessary stability condition (<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 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 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 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 or . The theory first gives a measure of how resilient a graph is: , 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 drops. Algorithm 2 moves the graph back: it removes an edge only if the removal increases . and 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) in Eq. (1) denotes the representation (state) of node , and 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.
Response
Q1: Disconnection between theory and attacks/GNN, θ and η 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 θ and η.
θ and η 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 θ and η 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.
Table R9: Accuracy on Cora under Metattack.
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.
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.
We study another strong adaptive attack (Mujkanovic et al.) in Table R12.
Table R12: Accuracy.