Towards Inductive Robustness: Distilling and Fostering Wave-induced Resonance in Transductive GCNs Against Graph Adversarial Attacks

We consider connected graphs $\mathcal{G}=(\mathcal{V},\mathcal{E})$ consisting $N=|\mathcal{V}|$ nodes. Let $\mathbf{A}\in\{0,1\}^{N\times N}$ be the adjacency matrix. Let generic symbol $\mathbf{L}$ be the Laplacian in its broadest sense. The feature and one-hot label matrix are $\mathbf{Z}\in\mathbb{R}^{N\times d_{0}}$ and $\mathbf{Y}\in\mathbb{R}^{N\times d_{L}}$ respectively. The edge connected nodes $v_{i}$ and $v_{j}$ is written as $(v_{i},v_{j})$ or $(v_{j},v_{i})$. The neighborhood $\mathcal{N}_{i}$ of a node $v_{i}$ consists of all nodes $v_{j}$ for which $(v_{i},v_{j})\in\mathcal{E}$. Let $\mathrm{deg}_{i}$ be the degree of node $v_{i}$. The feature vector and one-hot label of node $v_{i}$ are $\mathbf{z}_{i}$ and $\mathbf{y}_{i}$.

Under the topology $\mathbf{L}$, with $\mathbf{Z}$ as the input, the output at the $k$-th layer of a GCN is denoted as $\mathcal{M}(\mathbf{Z},k;\mathbf{L})$. The $k$-th parameter matrix of $\mathcal{M}$ is $\mathbf{W}^{(k)}\in\mathbb{R}^{d_{k}\times d_{k+1}}$. $\mathbf{Z}^{(k)}=[\mathbf{z}_{1}^{(k)},\ldots,\mathbf{z}_{N}^{(k)}]$ denotes the features in $k$-th MP.

The edge-based wave equation introduces a relationship between a graph-based signal $g=\mathrm{W{\scriptstyle AVE}}(\mathbf{Z},k;\mathbf{L})$ and its topological structure. Let $c$ be a constant, it is defined as $\frac{\partial^{2}g}{\partial k^{2}}=-\mathbf{L}^{k}g\cdot c$ (Friedman and Tillich 2004). Herein $g$ can be instantiated as any discernible signal.

Here we demonstrate that the signal vibrations driven by GCNs, are equivalent to waves on graph topologies and can be characterized by nonlinear wave equations.

This study draws an analogy between the node signals in GCN-driven MP and waves, considering edges as the transmission medium. Research indicates that in systems producing waves, resonance can arise between waves and their medium (Ahmad et al. 2023; Bykov, Bezus, and Doskolovich 2019). Building on this understanding, we can reaffirm our empirical observations about the GCN training pattern: in non-adversarial contexts, GCNs converge to the most natural, or congruent with ground truth, signal MP paradigm during training. Under this premise, the messages transmitted by nodes and edges in the graph manifest a natural coupling state, maintaining a benign mapping relationship $\mathcal{M}:\mathcal{G}\to\mathbf{Y}$. The key to optimizing $\mathcal{M}$ is the resonance between node signals $\mathbf{Z}^{(\ell)}$ and edge signals $\mathbf{E}^{(\ell)}$. In adversarial situations, adversaries manipulate node signals by rewiring edges, which inadvertently induces unnatural, i.e., noncongruent with ground truth, MP patterns. Under this scheme, the benign resonance is disrupted, resulting in a malignant mapping relationship $\mathcal{M}:\mathcal{G}^{\prime}\to\mathbf{Y}^{\prime}$, where $\mathcal{G}^{\prime}$ and $\mathbf{Y}^{\prime}$ is the perturbed graph and label, respectively.

Maintaining benign resonance becomes an intuitive defensive mechanism as it intrinsically resists unnatural perturbations. To actualize control over this resonance, thereby purposefully fostering resonance within the GCN, we subsequently delineate a detailed definition of this resonance. Thus, this definition should comply with the following conditions: 1) Every node within a graph should possess a computable resonance intensity, 2) the resonance intensity of all nodes should evolve in accordance with MP, 3) each node should maintain an independent resonance intensity, and 4) the stronger a node’s connection to its surrounding topology, the greater its perceived resonance intensity.

To devise a methodology compliant with the desired conditions, we consider node $v_{i}$ and utilize its latent representation (Kula 2015) $\bar{{z}}_{i}^{(k)}=\sum_{j}\mathbf{z}^{(k)}_{i,j}$ to quantify the intensity of the node signals. Furthermore, we use $T_{i}$, the count of edges among nodes in $\mathcal{N}_{i}$, to measure the connectivity strength specific to the edges at the given nodes. Then, we use the total number $p_{i}=\sum_{j}\mathbf{A}^{2}_{i,j}$ of walks of length 2 originating from $v_{i}$ to any node in $\mathcal{G}$, to quantity the magnitude of connectivity density that $v_{i}$ exhibits in the structure.

Accordingly, we propose the following definition to quantify the resonance intensity at node $v_{i}$:

The unique of defining resonance intensity can be articulated as follows: it not only allows for an interpretable quantification of the resonance on different nodes, but it is also directly observable within MP. This implies that under such a definition, the resonance intensity of any node at any given MP epoch on a graph can be independently calculated, obviating the need for the GCN computational paradigm.

Definition 1 facilitates the quantification of resonance for any signal function on any graph, irrespective of whether or not it is driven by GCN. Nonetheless, an intriguing finding has been proven: the wave system constructed by GCN inherently and involuntarily arises resonance, which is outlined in the theorem:

Theorem 2 unveils an intriguing phenomenon: for $k\geq 3$, there subsists an invariant mapping, which transposes the GCN-driven signal into a resonance intensity that bears no correlation with the GCN paradigm. Given that Definition 1 has established the resonance intensity as a measure of the coupling strength between nodes and structure within the graph, we can thus characterize it as the degree of coupling. Consequently, it can be asserted that prior to 3rd MP iteration, the GCN appears to have yet to delve into the coupling paradigm between nodes and structure within the graph. However, subsequent to the 3rd MP, due to the persistent presence of the invariant mapping, it can be construed that the GCN has fortuitously assimilated the coupling paradigm within the graph during the 3rd MP, and perpetuates this paradigm into subsequent MPs.

In light of the current absence of an effective method for quantifying the combined adversarial robustness of a specific graph and a GCN learning from said graph, we propose an intuitive approach. For a graph $\mathcal{G}$, comprised of $|\mathcal{V}|$ edges and represented by the adjacency matrix $\mathbf{A}$, and a GCN $\mathcal{M}$ with $K$ layers, where the perturbation budget is denoted as $r$, the number of matrix multiplication-based forward propagations required by the attack model can be construed as the highest attack cost. In this context, the number of subgraphs is independent of node features, hence we employ $\mathbf{A}$ as the independent variable for the attack cost function, denoted as $\mathrm{Cost}(\mathbf{A},r,K)$. We then present the following theorem:

It’s revealed that adversaries face the same computational cost for matrix multiplication-based forward propagations when $K$ = 1 or 2. However, for $K\geq 3$, the cost dramatically increases, largely due to $C(\frac{|\mathcal{V}|^{K-1}}{2},r)$. As an example, with the Cora dataset ($|\mathcal{V}|=5429$) and a 1% perturbation rate ($r=54$), the cost for $K$ = 3 becomes exponentially larger. Thus, attacking a 3-layer GCN presents a vast search space for adversaries. This insight extends Theorem 2’s real-world applications and our previous findings: a 3-layer GCN can naturally create resonance robustness. With our defined resonance, we can further boost this robustness proposefully.

We employ GRN to enhance the resonance of the GCN. The underlying concept of the GRN is articulated as follows. Definition 1 exhibits that for a node $v_{i}$, there exists a local graph structure that resonates, known as the local resonance subgraph (LRS) for node $v_{i}$, denoted as $G_{i}=(\mathcal{V}_{G_{i}},\mathcal{E}_{G_{i}})$, used to represent the maximal subgraph structure that node $v_{i}$ can capture. During end-to-end training, both the node signals $\mathbf{Z}^{(\ell)}$, and the signals transmitted through edges $\mathbf{E}^{(\ell)}$ concurrently vibrate within the LRS. Consequently, for $v_{i}$, if a learnable parameter $\mathbf{W}^{(\ell)}$ capable of jointly embedding MP’s result $\mathbf{A}_{G_{i}}\mathbf{Z}^{(\ell)}_{G_{i}}$, and $\mathbf{E}^{(\ell)}_{G_{i}}$, into $v_{i}$’s output representation, this aggregation intentionally accomplishes a learnable resonance, generating a local-level embedding. This identical aggregate pattern is applied across all nodes to facilitate a mapping, thereby achieving a global-level forward propagation within the GRN.

In summary, a single forward propagation of the GRN is:

Next, we provide explicit definitions for $G_{i}$ and $\mathbf{E}^{\ell}_{G_{i}}$.

As per Definition 1, LRS comprises three components: 1) edges formed amongst all first-order neighbors, as counted by $T_{i}$, with these edges’ weights equal 1; 2) edges formed between it and all 2nd- (inevitably includes 1st-) order neighbors, as counted by $p_{i}$, with these edges’ weights equal 2; 3) edges between it and all first-order neighbors, as counted by $\mathrm{deg}_{i}$, with these edges’ weights equal 8. Consequently, the LRS can be viewed as a weighted graph, in which the weights of edges serve as attention for the joint combination of $\mathbf{Z}^{(\ell)}$ and $\mathbf{E}^{(\ell)}$. An illustrative example of the LRS is presented in Figure 1.

In the MP driven by adjacency matrices, only signals at the nodes are observable, while the signals transmitted across each edge remain imperceptible. To ascertain the quantified signals on every specific edge within $G_{i}$, we first obtain the global edge-transmitted signals $\mathbf{E}^{\ell}_{\mathcal{G}}$. Then, $\mathbf{E}^{\ell}_{G_{i}}$ is subsequently derived through a sampling procedure on $\mathbf{E}^{\ell}_{\mathcal{G}}$ using the edge indices within $G_{i}$.

Specifically, within $\mathbf{E}^{\ell}_{\mathcal{G}}$, the edge-transmitted signals on $(v_{j},v_{k})$ are denoted as $\mathbf{e}^{\ell}_{j,k}$. For $\ell>0$, $\mathbf{e}^{\ell}_{j,k}$ is defined via a sequential procedure: 1) The edge $(v_{j},v_{k})$ in $\mathcal{G}$ is deleted, producing a new graph $\mathcal{G}^{j,k}$ with its adjacency matrix $\mathbf{A}_{\mathcal{G}^{j,k}}$. 2) A new forward propagation is executed in the same layer on $\mathcal{G}^{j,k}$, obtaining a feature matrix $\mathbf{Z}^{(\ell)}_{\mathcal{G}^{j,k}}$. This matrix does not contain any messages transmitted through the edge $(v_{j},v_{k})$. Consequently,

The feature of node $v_{j}$ in $\mathbf{Z}^{(\ell)}_{\mathcal{G}^{j,k}}$ denoted as $\mathbf{z}^{(\ell)}_{\mathcal{G}^{j,k},j}$, is obtained. 3) In $\mathcal{G}^{j,k}$, there is no edge between the nodes $(v_{j},v_{k})$. Hence, the feature transmitted from node $v_{k}$ to $v_{j}$ (i.e., $\mathbf{e}^{(\ell)}_{j,k}$) is calculated by subtracting the feature obtained through the re-propagation on $\mathcal{G}^{j,k}$ (i.e., $\mathbf{z}^{(\ell)}_{G_{i}^{j,k},j}$) from the original feature (i.e., $\mathbf{z}^{(\ell)}$). Similarly, the signal transmitted through the pair $(v_{j},v_{k})$ could be interpreted as the average of the mutually transmitted signals. At $\ell=0$, since MP has not been initiated, $\mathbf{e}^{(\ell)}_{j,k}$ would ideally be 0. For end-to-end training, it is defined as a random infinitesimal value. In conclusion, $\mathbf{E}^{(\ell)}_{G_{i}}$ is determined as

Figure 2 illustrates the computation of $\mathbf{e}^{(\ell)}_{j,k}$.

Equation (5) explicates the method of re-propagation on $\mathcal{G}_{j,k}$. Given that there are $|\mathcal{V}|$ ways to choose $(v_{j},v_{k})$, it necessitates the computation of $|\mathcal{V}|$ matrix multiplications (where $\mathbf{Z}_{\mathbf{W}}^{(\ell-1)}=\mathbf{Z}^{(\ell-1)}\mathbf{W}^{(\ell-1)}$ remains the same for all $(v_{j},v_{k})$ selections and can be considered a constant matrix), thereby constituting the primary computational cost of $\mathbf{E}^{(\ell)}_{G_{i}}$. Here, we provide a computational method equivalent to Equation (5), reducing the $|\mathcal{V}|$ times to once.

Evidently, a single matrix multiplication, i.e., $\mathbf{A}_{G}\mathbf{Z}_{\mathbf{W}}^{(\ell-1)}$, is sufficient to iterate over all $(v_{j},v_{k})$ and yield the results.

Each layer of GRN only contains trainable parameters $\mathbf{W}^{(\ell)}$, and each has a distinct output representation $\mathbf{Z}^{(\ell)}$. Thus, in accordance with the requirements of the downstream task, GRN can accommodate either supervised or unsupervised loss functions, thereby tuning their weight matrices. Specifically, we denote the discrepancy function as $D(\cdot,\cdot)$. In semi-supervised scenarios, the loss function is $J_{s}(\mathbf{z}^{(K)}_{i})=D(\mathbf{z}^{(K)}_{i},\mathbf{y}_{i})$; in unsupervised scenarios (Müller 2023), $J_{u}(\mathbf{z}^{(K)}_{i})=D(\mathbf{z}^{(K)}_{i},\{\mathbf{y}_{j}:v_{j}\in\mathcal{N}_{i}\})$. Depending on the downstream applications, $D(\cdot,\cdot)$ can take various forms, such as cross-entropy, etc. The general workflow of GRN is illustrated in Figure 3.

Our findings are evaluated on five real-world datasets widely used for studying graph adversarial attacks (Sun et al. 2020; Liu et al. 2022; Zhu et al. 2019; Entezari et al. 2020; Li et al. 2022), including Cora, Citeseer, Polblogs, and Pubmed.

Comparison defending models. We compare GRN with other defending models including: 1) RGCN which leverages the Gaussian distributions for node representations to amortize the effects of adversarial attacks, 2) GNN-SVD which is applied to a low-rank approximation of the adjacency matrix obtained by truncated SVD, 3) Pro-GNN (Jin et al. 2020) which can learn a robust GNN by the intrinsic properties of nodes, 4) Jaccard (Wu et al. 2019) which defends attacks based on the measured Jaccard similarity score, 5) EGNN (Liu et al. 2021) which filters out perturbations by $l_{1}$- and $l_{2}$-based graph smoothing. Attack methods. The experiments are designed under the following attack strategies: 1) Metattack (Zügner and Günnemann 2018), a meta-learning based attack, 2) CLGA (Sixiao et al. 2022), an unsupervised attack, 3) RL-S2V (Dai et al. 2018), a reinforcement learning based attack.

In Theorem 2, we establish an equivalence relation between the $k$-th and the $k+3$-th layer’s output latent representations, as derived from Equations (1) and (2). This elucidates that when $k=0$, the $3$-th layer involuntarily captures local structures, thereby inducing resonance. To facilitate experimental variable control, we first demonstrate the equivalence relation under varying “gap layer numbers” (denoted as $k_{gap}$). If the equivalence between Equations (1) and (2) only holds when $k_{gap}\geq 3$, it substantiates the validity of Theorem 2. Specifically, we first train a 5-layer GCN, then obtain the resonance intensity denoted as $R_{def}(k)=\bar{{z}}_{i}^{(k)}T_{i}+2p_{i}+8\mathrm{deg}_{i}$, and the actual observed signal denoted as $R_{real}(k+k_{gap})=64\bar{{z}}_{i}^{(k+k_{gap})}-32$, for each epoch. Given these observational variables, we delineate their transformations over the learning process using lists $\{R_{def}(k)\}$ and $\{R_{real}(k+k_{gap})\}$ respectively. Each list chronicles its corresponding variable’s fluctuations across all epochs. Subsequently, we standardize (using the standardize function $\mathrm{{\scriptstyle STD}}(\cdot)$) the sequences under different $k_{gap}$ and calculate the absolute difference to obtain a difference sequence:

The parameter $\mathbf{d}_{k,k_{gap}}$, serving as an indicator variable, accurately encapsulates the discrepancy between $R_{def}(k)$ and $R_{real}(k+k_{gap})$. The experimental results are illustrated in Figure 4. Owing to the large number of nodes, we display the mean value (central line) and standard deviation (shadow areas) of all nodes. As epochs progress, $\mathbf{d}_{0,3}$ gradually converges to zero. After the initial several epochs, it significantly diverges from $\mathbf{d}_{0,1}$ and $\mathbf{d}_{0,2}$. This validates the intriguing phenomenon mentioned in Theorem 2: a correlation has been established between the signal at the 3-th layer and the graph’s initial signal and structure. Subsequent experimental results echo the aforementioned findings, thereby affirming the correctness of Theorem 2 when $k>0$.

Intuitively, the complexity of an attack tends to increase with the number of GCNs’ layer. Observing the pattern of attack success rate (ASR) declines as the number of GCN layers increases helps validate our claim that the 3-layer GCN, derived from resonance, can significantly enhance robustness. Specifically, we start by initializing 10 GCNs with the number of layers ranging from 1 to 10. Next, we conduct experiments on 4 datasets using 3 typical attacks, setting the perturbation rate uniformly at 20%. We then train a surrogate model for each GCN separately, placing perturbations in the dataset, and clearing these perturbations after each attack. We repeat each attack five times and report the average ASR accuracy (depicted by the lines) and variation range (represented by the shaded areas). The results, as shown in Figure 6, clearly reveal a steep drop in ASR at the 3-layer GCN. However, further layer addition seems unable to significantly reduce the ASR, as the additional layers maintain the same resonance pattern as the 3-layer GCN to achieve adversarial robustness. These findings articulate the concept of distilling the resonance from GCNs and fostering this resonance to design a inductive approach.

Derived from a transductive model, the LRS captures distinct resonance regions and transforms a localized, unweighted graph (also perceivable as a graph with unitary weights) into a weighted one. The implementation of the LRS within the GRN enables the demarcation of a learnable resonance scope for inductive learning. Consequently, it becomes essential to validate the efficacy of the LRS through its embedding precision within the transductive model.

We initiate by presenting results obtained under non-adversarial conditions. We sum the LRS of all nodes in $\mathcal{G}$ and apply min-max scaling to all weights, thus creating a global weighted graph $\mathcal{G}_{LRS}$. Then, we train a standard 2-layer GCN $\mathcal{M}_{\mathcal{G}}$ on Cora dataset (denoted as $\mathcal{G}$) and visualize its well-trained representations. Then, we feed $\mathcal{G}_{LRS}$ into $\mathcal{M}_{\mathcal{G}}$ to generate its visualization. Lastly, for comparison, we create a random-weighted graph $\mathcal{G}_{random}$ whose edge distribution is the same as $\mathcal{G}$, and input it into $\mathcal{M}_{\mathcal{G}}$ to get the corresponding visualization. As Figure 5(a) shows, under identical weights, the representations of different categories in $\mathcal{G}_{LRS}$ are tighter than those in $\mathcal{G}$. This suggests that introducing LRS brings beneficial global weights, which enhance the model’s performance in non-adversarial scenarios.

Then, we explored the similarity between $\mathcal{G}$ and $\mathcal{G}_{LRS}$. Using strength distribution, akin to degree distribution for unweighted graphs (Zügner, Akbarnejad, and Günnemann 2018), we found the two weighted graphs are notably similar. Figure 5(b) confirms this, showing a stark difference from $\mathcal{G}_{random}$. Therefore, $\mathcal{G}_{LRS}$ maintains the traits of $\mathcal{G}$.

We next assessed the classification accuracy of $\mathcal{G}_{LRS}$ under adversarial attacks using varying Metattack perturbation rates $p_{r}=\frac{r}{|\mathcal{E}|}$. Figure 5(c) shows that as $p_{r}$ increases, $\mathcal{G}_{LRS}$’s accuracy consistently edges out $\mathcal{G}$. This suggests that the LRS introduces a resonance in the transductive model, marginally boosting its adversarial robustness.

We assess the adversarial robustness of the 3-layer GRN under generalization demands by comparing its accuracy against other baselines on perturbed graphs. We partition a subset of the dataset as training set with proportions (also named “seen” rate) $s_{r}$ as 20%, 40%, and 60%. The data within these proportions are deemed “seen” by the GRN, while the remaining data is categorized as “unseen”. Utilizing Metattack as our attack approach, we adopt the standard 2-layer GCN as the surrogate model. By adjusting $p_{r}$, we derive the corresponding perturbed graphs. Then, we evaluate the classification performance of the baselines on these graphs, placing an emphasis on the accuracy upon model convergence. For each setting, we executed 10 iterations, tabulating both the average outcome and its variability. Table 1 reports the results.

From the data, both clean and perturbed graphs show GRN with a $s_{r}$ = 60% generally surpasses the baseline in accuracy. There are three exceptions: 1) For the Pubmed dataset at $p_{r}$ = 10%, this is due to EGNN using graph smoothing to enhance adversarial robustness. In this case, perturbations may be more pronounced in a certain area, and EGNN could leverage this by smoothing concentrated perturbation patterns. However, these incidents are rare, and as $p_{r}$ increases, GRN’s accuracy returns to its peak. 2) With the Polblogs dataset at $p_{r}$ = 0%, GRN is slightly behind EGNN by 0.28%. Yet, as $p_{r}$ rises, the decline in GRN’s accuracy is the least noticeable among all baselines, ensuring its top position. 3) An intriguing pattern emerging from the Polblogs dataset is the non-proportional relationship between the GRN’s $s_{r}$ and its accuracy. The peculiarity of the Polblogs dataset is that its nodes lack intrinsic features. Typically, scholars have used node degrees as proxies for these absent attributes. This substitution results in the inherent attributes of Polblogs leaning towards uniformity. Expanding the training set’s scale exacerbate the oversmoothing phenomenon, culminating in diminished accuracy.

GRNs combine edge-transmitted signal $\mathbf{E}^{(\ell)}_{G_{i}}$ and node signal $\mathbf{Z}^{(\ell)}_{G_{i}}$ for node $v_{i}$’s representation. We initiate an ablation study to delve into this process. First, we embed only $\mathbf{Z}^{(\ell)}_{G_{i}}$, naming the model GRN_Z. This appears similar to a 2-depth GraphSAGE with mean aggregation, indicating potential vulnerability to adversarial attacks. We then examine the combination order of $\mathbf{E}^{(\ell)}_{G_{i}}$ and $\mathbf{Z}^{(\ell)}_{G_{i}}$. The default GRN order is GRN_E,Z. We test GRN_Z,E (reversed order) and GRN_shuf (shuffled rows). Results (Table 2) show GRN_Z underperforms, especially in adversarial settings, emphasizing the importance of co-embedding both signals. Precisions of GRN_Z,E, GRN_E,Z, and GRN_shuf are comparable due to the edge-transmitted signal, which, combined with the node signal through shared parameters, results in consistent performance regardless of order. This suggests that GRN has the capability to recognize a latent graph structure, wherein edge-transmitted signals function as latent node signals, contributing to adversarial robustness and insensitivity to signal order.