1 Introduction↩︎

Graph Neural Networks (GNNs) [1]–[3] have become a popular approach for graph-based tasks due to their powerful ability to learn node representations. They have demonstrated remarkable performance in various tasks, including traffic prediction [4], drug discovery [5], and recommendation system [6]. The core principle of GNNs is the message-passing operation, which aggregates node features from neighboring nodes, thereby enhancing the smoothness of the learned node representations. As a result, GNN models produce predictions based on both the features of individual nodes and those of their immediate neighbors.

Graph Diffusion Convolution (GDC) [7], a specialized GNN architecture, aggregates information from higher-order neighbors through generalized graph diffusion. Various GDC architectures [8]–[13] are derived from the Graph Signal Denoising (GSD) problem, formulated as: \[\label{graph32signal32denoising} \underset{\mathbf{F}}{\arg \min } \;\mathcal{L}(\mathbf{F}):=\|\mathbf{F}-\mathbf{X}\|_F^2+\lambda \operatorname{tr}\left(\mathbf{F}^{\top} \tilde{\mathbf{L}} \mathbf{F}\right),\tag{1}\] where \(\mathbf{X}=\mathbf{X}^*+\boldsymbol{\Upsilon}\) is the observed noisy feature matrix, \(\boldsymbol{\Upsilon} \in \mathbb{R}^{n \times d}\) is the noise matrix, \(\mathbf{X}^*\) is the clean feature matrix, and \(\tilde{\mathbf{L}} \in \mathbb{R}^{n \times n}\) is the normalized graph Laplacian matrix. A major strength of the GDC architecture is its ability to aggregate information from a larger set of neighbors, enhancing \(\ell_2\)-based graph smoothing [10].

Despite significant advancements in GDC architectures, they rely heavily on the Laplacian matrix to derive the graph diffusion matrix. This dependency can be problematic when the graph structure is disrupted by adversarial attacks [14]–[17]. Such attacks can cause GDC to aggregate harmful information, disrupting node representations. Additionally, the limited number of neighbors restricts GDC’s ability to effectively filter out large noise in node features within some graphs [18]. These challenges raise a crucial question: Can we develop a versatile GDC architecture that addresses these issues effectively? In this work, we provide a positive solution to this question by reformulating the GSD problem. Based on this reformulation, we design a new GDC architecture that mitigates the negative impact of adversarial attacks on the graph structure, noise in node features, and inconsistent edges on heterophilic graphs.

Inspired by the saddle point formulation of adversarial training [19], we propose a min-max variant of the GSD problem, called the Adversarial Graph Signal Denoising (AGSD) problem: \[\label{intro:agsd} \underset{\mathbf{F}}{\arg\min } \; q(\mathbf{F}) := \left[\left\|\mathbf{F}-\mathbf{X}\right\|_{F}^{2}+\lambda \cdot \max_{\mathbf{L}^{\prime}} \; \operatorname{tr}\left(\mathbf{F}^{\top} \mathbf{L}^{\prime} \mathbf{F}\right)\right],\tag{2}\] where \(\mathbf{L}^{\prime}\) is the added perturbation by the adversary. In the inner optimization problem, we maximize the second term of the AGSD. Then, we minimize the loss function \(q(\mathbf{F})\) in the outer optimization problem.

Unlike adversarial training, which requires projected gradient descent (PGD) to solve the inner maximization problem, our formulation has a closed-form solution for the inner optimization problem. Utilizing this closed-form solution, we solve the outer minimization problem to derive a new GDC architecture, Graph Adversarial Diffusion Convolution (GADC). This architecture introduces an additional term compared to GDC, resulting in more adaptive GDC variants that are resilient to adversarial perturbations in the edges and noise in node features. Moreover, our GADC enhances the performance of GDC on heterophilic graphs, where nodes from different classes are linked. Extensive experimental results across various datasets validate the effectiveness of our proposed algorithm. Additionally, our novel AGSD problem can inspire the development of advanced and reliable GNN architectures.

2 Preliminaries↩︎

2.0.0.1 Notations.

Let \(\mathcal{G}=(\mathcal{V}, \mathcal{E})\) represent a undirected graph, where \(\mathcal{V}\) is the set of vertices \(\left\{v_{1}, \cdots, v_{n}\right\}\) with \(|\mathcal{V}|=n\) and \(\mathcal{E}\) is the set of edges. The adjacency matrix is defined as \(\mathbf{A} \in \{0,1\}^{n \times n}\), and \(\mathbf{A}_{i,j}=1\) if and only if \(\left(v_{i}, v_{j}\right) \in \mathcal{E}\). Let \(\mathcal{N}_{i}=\{v_j | \mathbf{A}_{i,j} = 1\}\) denote the neighborhood of node \(v_i\) and \(\mathbf{D}\) denote the diagonal degree matrix, where \(\mathbf{D}_{i,i}=\sum_{j=1}^{n} \mathbf{A}_{i,j}\). The normalized Laplacian matrix of a graph is defined as \(\mathbf{L}=\operatorname{Laplacian}(\mathbf{A})=\mathbf{I}_n-\mathbf{D}^{-1 / 2} \mathbf{A D}^{-1 / 2}\), where \(\mathbf{I}_n\) is an \(n \times n\) identity matrix. The feature matrix is denoted as \(\mathbf{X} \in \mathbb{R}^{n \times d}\). \(\operatorname{tr}\left(\cdot\right)\) denotes the trace of the matrix.

2.0.0.2 Spectral Graph Convolution.

Spectral convolution involves multiplying a signal \(\mathbf{x}\) by a Fourier domain filter \(g_\phi\), parameterized by coefficients \(\phi \in \mathbb{R}^n\). This is expressed as: \[g_\phi(\mathbf{L}) \star \mathbf{x}=\mathbf{U} g_\phi^*(\boldsymbol{\Lambda}) \mathbf{U}^{\top} \mathbf{x},\] where \(g_\phi\) can be approximated by a truncated expansion. A common approach is to use Chebyshev polynomials up to the \(K\)-th order, resulting in the following approximation: \[g_\phi^*(\boldsymbol{\Lambda}) \approx \sum_{k=0}^K \phi_k T_k(\tilde{\boldsymbol{\Lambda}}).\]

2.0.0.3 Graph Convolution Network (GCN).

GCNs approximate spectral graph convolution using first-order Chebyshev polynomials. By setting \(K=1\) and \(\phi_0=-\phi_1\), and approximating \(\lambda_n \approx 2\), the convolution becomes \(g_\phi(\mathbf{L}) \star \mathbf{x}=\left(\mathbf{I}_n+\mathbf{D}^{-1 / 2} \mathbf{A} \mathbf{D}^{-1 / 2}\right) \mathbf{x}\). Introducing self-loops and renormalization trick modifies this to \(\tilde{\boldsymbol{\mathcal{A}}}=\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}\), where \(\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_n\) and \(\tilde{\mathbf{D}}=\mathbf{D}+\mathbf{I}_n\). The GCN layer is then defined as: \[\mathbf{H}^{(l+1)}=\sigma\left(\tilde{\boldsymbol{\mathcal{A}}} \mathbf{H}^{(l)} \boldsymbol{\Theta}^{(l)}\right).\] Here, \(\sigma\) is the activation function and \(\boldsymbol{\Theta}^{(l)}\) are the trainable parameters in the \(l\)-th layer.

2.0.0.4 Adversarial Training.

[19] study the adversarial robustness of neural networks from the perspective of robust optimization as follows: \[\underset{\Theta}{\arg\min } \;\rho(\Theta):=\mathbb{E}_{(x, y) \sim \mathcal{D}}\left[\max _{\delta \in \mathcal{S}} L(\Theta, x+\delta, y)\right],\] where \(\Theta\) is the set of model parameters, \(x\) is the input sample, \(y\) is the label, \(\mathcal{D}\) is the data distribution, \(\delta\) is the perturbation, \(\mathcal{S}\) is the perturbation space, \(L\) is the loss function, and \(\mathbb{E}\) is the empirical risk. The inner maximization problem attacks the neural network, while the outer minimization problem finds model parameters to make it robust against these adversarial attacks. In this work, we introduce a min-max formulation for the GSD problem, known as AGSD.

2.0.0.5 Graph Diffusion Convolution (GDC).

Graph diffusion [7] is defined via the diffusion matrix: \[\label{eq:diffusion32matrix} \mathbf{S}=\sum_{k=0}^{\infty} \theta_k \mathbf{T}^k,\tag{3}\] where \(\theta_k\) are the weighting coefficients and \(\mathbf{T}\) is the transition matrix. Existing GNN architectures such as APPNP [20], GLP [8], S\(^2\)GC [9], and AirGNN [18] can be viewed as variations of GDC. In this work, we introduce a new GDC architecture based on our proposed AGSD.

3 Graph Adversarial Diffusion Convolution↩︎

In this section, we first introduce the min-max variant of the graph signal denoising (GSD) problem in Section 3.1.1. Then, we discuss the closed-form solution for the inner maximization problem in Section 3.1.2. In Section 3.1.3, we propose graph adversarial diffusion convolution (GADC) by solving the outer minimization problem. Finally, Sections 3.2, 3.3, and 3.4 introduce four adaptive GADC variants designed to enhance robustness against adversarial attacks on the graph structure and noise in node features, as well as improve performance on heterophilic graphs.

3.1 Adversarial Graph Signal Denoising Problem↩︎

3.1.1 Problem Formulation↩︎

Adversarial training has been recently explored in the robust optimization. [19] use a saddle point (min-max) formulation to incorporate protection against adversarial attacks into neural networks. In the inner maximization problem, the adversary uses projected gradient descent (PGD) to identify the worst-case adversarial perturbations that maximize the loss. The outer minimization problem seeks to find model parameters that minimize the adversarial loss generated by the inner attack problem.

Inspired by the saddle point (min-max) formulation in adversarial training, we introduce the Adversarial Graph Signal Denoising (AGSD) problem as shown in Eq. 2 . In the AGSD problem, the first term ensures the solution is close to the observed data, while the second term involves a graph Laplacian matrix. Defining perturbations on the graph structure to maximize the second term in the AGSD problem is less straightforward than traditional adversarial attacks. Inspired by the recent work [21] that uses spectral distance to deploy graph structural attacks, we leverage Laplacian distance to introduce perturbations.

3.1.1.1 Laplacian Distance.

[21] define the spectral distance as the changes in the eigenvalues of the graph Laplacian matrix, formulated as follows: \[\mathcal{D}_{\text{spectral }}=\left\|g_\phi^*(\boldsymbol{\Lambda})-g_\phi^*\left(\boldsymbol{\Lambda}^{\prime}\right)\right\|_2,\] where \(\boldsymbol{\Lambda}\) and \(\boldsymbol{\Lambda}^{\prime}\) denote the eigenvalues of the normalized graph Laplacian matrix for the original graph \(\mathcal{G}\) and the disrupted graph \(\mathcal{G}^{\prime}\). The idea behind using the spectral distance for graph structural attacks is that perturbing the graph to maximize this distance induces the most harmful perturbation to the graph filters [22] and significantly disrupts node embeddings. To make the attack simple and effective, we directly add perturbations to the graph filter. This allows us to define the Laplacian distance. \[\mathcal{D}_{\text{Laplacian }}=\left\|g_\phi(\tilde{\mathbf{L}})-g_\phi\left(\mathbf{L}^{\prime}\right)\right\|_F =\left\|\mathbf{L}^{\prime}-\tilde{\mathbf{L}}\right\|_{F},\] where \(\tilde{\mathbf{L}}=\mathbf{I}_n-\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}\) denotes the normalized graph Laplacian matrix.

3.1.1.2 AGSD.

Based on the Laplacian distance, we introduce our AGSD as follows: \[\label{adv32gsd} \begin{gather} \underset{\mathbf{F}}{\arg\min } \; q(\mathbf{F}) := \left[\left\|\mathbf{F}-\mathbf{X}\right\|_{F}^{2}+\lambda \cdot \max_{\mathbf{L}^{\prime}} \; \operatorname{tr}\left(\mathbf{F}^{\top} \mathbf{L}^{\prime} \mathbf{F}\right)\right] \\ \operatorname{s.t.} \;\left\|\mathbf{L}^{\prime}-\tilde{\mathbf{L}}\right\|_{F} \leq \varepsilon. \end{gather}\tag{4}\] In the inner optimization problem, a hypothetical adversary generates perturbations based on the Laplacian distance to create a modified Laplacian matrix, \(\mathbf{L}^{\prime}\), which aims to maximize the second term of the AGSD. Then, the outer minimization problem seeks to find \(\mathbf{F}\) that minimizes the overall loss function \(q(\mathbf{F})\).

3.1.2 Closed-form Solution of the Inner Maximization Problem↩︎

The min-max formulation in Eq.@eq:adv32gsd introduces a more complex GSD problem. In contrast to adversarial training [19], where the inner maximization problem is solved using PGD before solving the outer minimization problem at each training step, our inner maximization problem is a quadratic optimization problem. This removes the need for computationally expensive adversarial perturbations at each step. Instead, we can directly identify the largest perturbation.

Let us denote the perturbations as \(\boldsymbol{\delta}\), and the perturbed Laplacian matrix as \(\mathbf{L}'=\tilde{\mathbf{L}} + \boldsymbol{\delta}\). Due to the quadratic nature of our inner maximization problem, we can reformulate it as follows: \[\begin{gather} \max_{\mathbf{L}^{\prime}} \operatorname{tr}\left(\mathbf{F}^{\top} \mathbf{L}^{\prime} \mathbf{F}\right) =\langle\tilde{\mathbf{L}}^{\top}, \mathbf{F}\mathbf{F}^{\top}\rangle + \max_{\boldsymbol{\delta}}\langle\boldsymbol{\delta}^{\top}, \mathbf{F}\mathbf{F}^{\top}\rangle \\ \operatorname{s.t.} \;\left\|\boldsymbol{\delta}\right\|_{F} \leq \varepsilon. \end{gather}\] We denote \(h(\boldsymbol{\delta})=\langle\boldsymbol{\delta}^{\top}, \mathbf{F}\mathbf{F}^{\top}\rangle\). \(h(\boldsymbol{\delta})\) reaches the largest value when \(\boldsymbol{\delta}^{\top}\) has the same direction with the gradient of \(h(\boldsymbol{\delta})\), i.e. \(\boldsymbol{\delta}^{\top}=\frac{\varepsilon\nabla h(\boldsymbol{\delta})}{\left\|\nabla h(\boldsymbol{\delta})\right\|_{F}}=\frac{\varepsilon\mathbf{F}\mathbf{F}^{\top}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\). An illustration is provided in Figure 1. Plugging this solution into Eq. 4 , we can rewrite the outer optimization problem as follows: \[\label{eq:p40h41} \begin{gather} \underset{\mathbf{F}}{\arg\min } \; q(\mathbf{F}), \\ q(\mathbf{F})=\left[\left\|\mathbf{F}-\mathbf{X}\right\|_{F}^{2}+\lambda \operatorname{tr}\left(\mathbf{F}^{\top} \tilde{\mathbf{L}} \mathbf{F}\right)+\lambda\varepsilon\operatorname{tr}\frac{\mathbf{F}^{\top}\mathbf{F}\mathbf{F}^{\top}\mathbf{F}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\right], \end{gather}\tag{5}\] where we introduce an extra loss term \(\lambda\varepsilon\operatorname{tr}\frac{\mathbf{F}^{\top}\mathbf{F}\mathbf{F}^{\top}\mathbf{F}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\) compared with the GSD.

3.1.3 Modified Transition Matrix Derived by Outer Minimization Problem↩︎

In this section, we derive our graph adversarial diffusion convolution. By taking the gradient of Eq. 5 to zero, we get the solution of the outer optimization problem as: \[\label{eq:advF} \mathbf{F} = \left(\mathbf{I}+\lambda\tilde{\mathbf{L}}+\lambda\frac{\varepsilon\mathbf{F}\mathbf{F}^{\top}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\right)^{-1}\mathbf{X}.\tag{6}\] Computing Eq. (6 ) directly involves a matrix inverse operation, resulting in a complexity of \(\mathcal{O}\left(n^3\right)\). This high computational cost can be prohibitively expensive for large graphs. Inspired by the closed-form solution of Personalized PageRank (PPR) kernel [7], [23] (graph diffusion), we can solve Eq. 6 via graph diffusion (Eq. 3 ) and obtain \[\label{eq:graph32adversarial32diffusion32inverse} \mathbf{F} = \frac{1}{\lambda+1} \sum_{k=0}^K\left[\frac{\lambda}{\lambda+1} \left(\tilde{\boldsymbol{\mathcal{A}}}-\frac{\varepsilon\mathbf{F}\mathbf{F}^{\top}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\right)\right]^k\mathbf{X},\tag{7}\] where \(\mathbf{T}=\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}-\frac{\varepsilon\mathbf{F}\mathbf{F}^{\top}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}=\tilde{\boldsymbol{\mathcal{A}}}-\frac{\varepsilon\mathbf{F}\mathbf{F}^{\top}}{\left\|\mathbf{F}\mathbf{F}^{\top}\right\|_{F}}\) represents the transition matrix, and \(\alpha =\frac{1}{\lambda+1}\) denotes the coefficient.

3.1.3.1 Approximate Solution of Eq. 7 .

Although we approximate the inverse matrix with graph diffusion to avoid \(\mathcal{O}(n^3)\) complexity, the matrix series Eq. 7 still involves high powers of the matrix \(\mathbf{F}\). Obviously, it is impossible to get an analytical solution of \(\mathbf{F}\) for this equation. Current methods exploit iterative algorithms such as Newton’s method [24] to solve this high-order nonlinear system of equations, but the computation is also very expensive. Therefore, there is no suitable solution that strictly follows the equation while also avoiding large computational complexity. We need a more efficient algorithm to solve Eq. 7 . We observe that the first term of AGSD requires \(\mathbf{F}\) to be close to \(\mathbf{X}\), thus a natural idea is to replace \(\mathbf{F}\) with \(\mathbf{X}\) in the right side of Eq. 7 to reduce the computational complexity and improve the scalability for large graphs. Thus, we now formally propose our GADC as follows: \[\label{eq:graph32adversarial32diffusion} \mathbf{S} = \frac{1}{\lambda+1}\sum_{k=0}^{K}\left[\frac{\lambda}{\lambda+1}\mathbf{T}\right]^{k},\tag{8}\] where \(\mathbf{T}=\tilde{\boldsymbol{\mathcal{A}}}-\frac{\varepsilon\mathbf{X}\mathbf{X}^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}}\). Note that the additional term \(\frac{\varepsilon\mathbf{X}\mathbf{X}^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}}\) is a unique component introduced by the closed-form solution of the inner maximization problem of AGSD. This term doesn’t appear in existing GDC architectures derived from the GSD problem. We will use this term to produce more adaptive architectures, as demonstrated in the following sections.

3.1.3.2 Error Analysis.

We plug our obtained \(\mathbf{F}\) into Eq. 7 to compute the error of this approximate solution for the equation on the Cora [25] dataset. The error matrix is computed by subtracting the left side from the right side: \(\mathbf{F}-\frac{1}{\lambda+1} \sum_{k=0}^K\left[\frac{\lambda}{\lambda+1} \mathbf{T}\right]^k \mathbf{X}\), where \(\mathbf{T}=\tilde{\boldsymbol{\mathcal{A}}}-\frac{\varepsilon\mathbf{X}\mathbf{X}^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}}\). The norm of the error matrix for our solution is 4.5. As a comparison, we generate a random \(\mathbf{F}\) from a Gaussian distribution with mean=1, std=1. If we use this random \(\mathbf{F}\), the norm of the error matrix is 2780.6. Comparing the norm of the error matrix between our solution (4.5) and a random solution (2780.6), we can conclude that replacing \(\mathbf{F}\) with \(\mathbf{X}\) indeed achieves an accurate approximation, while greatly reducing the computational complexity.

3.1.3.3 Scalability.

To leverage the additional term across various graphs, we enhance the scalability of the transition matrix by providing the following options: computing the normalized or unnormalized inner product of feature vectors \(\left(\mathbf{X}_i, \mathbf{X}_j \mid j \in \mathcal{N}_i\right)\) between adjacent neighbors, or between every pair of nodes, similar to the masked/unmasked attention mechanism in GAT. Therefore, our modified transition matrix can be formulated as follows: \[\label{eq:options} \begin{align} &\mathbf{T}=\tilde{\boldsymbol{\mathcal{A}}}-\varepsilon\mathbf{\Phi}, \;\operatorname{where} \\ \operatorname{(\uppercase{\romannumeral1}):} \;&\Phi_{ij}:= \begin{cases} \frac{\mathbf{X}_i \mathbf{X}_j^{\top}}{\left\|\mathbf{X}_i\right\|_2\left\|\mathbf{X}_j\right\|_2}, & \text{if} \left(v_i, v_j\right) \in \mathcal{E} \\ 0, & \text{otherwise},\end{cases}; \\ \operatorname{(\uppercase{\romannumeral2}):} \;&\Phi_{ij}:=\frac{\mathbf{X}_i \mathbf{X}_j^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}};\\ \operatorname{(\uppercase{\romannumeral3}):} \;&\Phi_{ij}:= \begin{cases} \frac{\mathbf{X}_i \mathbf{X}_j^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}}, & \text{if} \left(v_i, v_j\right) \in \mathcal{E} \\ 0, & \text{otherwise},\end{cases}. \end{align}\tag{9}\] For the first option, we normalize the weights by using the product of the norms of the features of connected neighbors, which measures the similarity between these neighboring nodes’ features. We will derive the fourth option from the first option to defend against adversarial attacks on the graph structure. The second option improves graph connectivity, filtering out large noise in graphs. Furthermore, we discover that even without explicitly incorporating additional graph connectivity (the third option), reassigning edge weights through the additional term improves denoising performance on large graphs. Moreover, using the first option to penalize the weights of connected neighbors enhances performance on heterophilic graphs. We will discuss the details of these options in the subsequent sections.

3.1.3.4 Connection to APPNP.

If we take the limit \(k \rightarrow \infty\) of power iterations in APPNP [20], APPNP converges to \(\mathbf{Z}^{(\infty)}=\alpha\left(\mathbf{I}-(1-\alpha) \tilde{\boldsymbol{\mathcal{A}}}\right)^{-1} \mathbf{Z}^{(0)}\), similar to Eq. 6 . Our proposed GADC introduces an additional term \(\varepsilon \boldsymbol{\Phi}\) in the transition matrix. This additional term makes GADC more adaptable compared to APPNP. As we will demonstrate in the upcoming sections, this adaptability enhances resilience in various scenarios, including adversarial attacks on the graph structure, noise in node features, and inconsistent edges on heterophilic graphs.

3.2 Defending Against Graph Adversarial Attacks↩︎

Recent studies [15], [16] have shown that GNNs are vulnerable to adversarial attacks on the graph structure. These attacks often involve adding harmful edges or removing informative ones to manipulate the information flow, thus preventing GNNs from aggregating valuable information and disrupting node representations. GDC relies on the graph structure to derive the diffusion matrix needed for smoothing node representations. However, when the graph structure is disrupted by adversarial attacks, it becomes unreliable, and we cannot use the graph Laplacian matrix to aggregate information from neighbors. Inspired by GNNGuard [26], which assigns higher weights to edges connecting nodes with similar features while pruning edges between unrelated nodes, we employ the additional term to achieve a similar effect. The rationale is that on homophily graphs, nodes within the same class have similar features, while nodes from different classes exhibit dissimilar features. Therefore, we use the first option in Eq. 9 and assign a very large value to the additional term in the modified transition matrix, allowing this term to determine the edge weights: \[\mathbf{T}=\tilde{\boldsymbol{\mathcal{A}}}-\lim_{\varepsilon\rightarrow \infty}\varepsilon\mathbf{\Phi}.\] However, this approach may result in a numerical explosion problem. To address this issue, we introduce a trick in which we compute the modified transition matrix based on the additional term with \(\mathbf{T}=-\lim_{\varepsilon\rightarrow \infty}\frac{1}{\varepsilon}\left(\tilde{\boldsymbol{\mathcal{A}}}-\varepsilon\mathbf{\Phi}\right)\). As such, we employ the cosine value to evaluate the similarity among connected neighbors and recalculate the weights of the transition matrix as follows: \[\label{eq:fourth} \operatorname{(\uppercase{\romannumeral4}):} \; \mathbf{T}_{ij} = \left(\mathbf{X}_i \odot \mathbf{X}_j\right) /\left(\left\|\mathbf{X}_i\right\|_2\left\|\mathbf{X}_j\right\|_2\right) \;\operatorname{s.t.}\;\mathbf{A}_{ij}=1,\tag{10}\] where \(\mathbf{A}\) is the disrupted adjacency matrix by adversarial attacks and \(\odot\) denotes the inner product. By implementing this trick, we can propose the fourth option to reconstruct the informative adjacency matrix using the additional term, thereby restoring the beneficial information flow during the aggregation process.

3.3 Tackling Large Noise in Node Features↩︎

In the study by [18], feature aggregation in GNNs is suggested to function as a low-pass filter, smoothing node features across neighborhoods and filtering out node feature noise [27], [28]. However, on graphs with a limited number of neighbors, GDC’s ability to effectively filter out large noise in node features is constrained. To address this, we provide a theoretical analysis to understand the effect and introduce two simple and effective GADC (II, III) methods to handle noisy node features in graphs.

3.3.1 Convergence Analysis for the Aggregated Noisy Matrix↩︎

Consider applying GDC to a noisy node feature matrix, represented as the product of \(\mathbf{S}\) and \(\boldsymbol{\Upsilon}\): \[\mathbf{S}\boldsymbol{\Upsilon},\] where \(\boldsymbol{\Upsilon}\) denotes the noise matrix. Intuitively, if the matrix norm \(\|\mathbf{S}\boldsymbol{\Upsilon}\|_{F}\) can converge to a small value, the denoising effect is achieved. Consider the noise utilized in [29]–[31] follows Gaussian distribution, which is also covered by sub-Gaussian variable. Therefore, the noise matrix has the following property. Based on this property, we provide the analysis.

3.3.1.1 Higher-order Graph Connectivity Factor.

Intuitively, \(\mathbf{S}\) captures not only the connectivity of the graph structure (represented by \(\widetilde{\boldsymbol{\mathcal{A}}}\)), but also the higher-order connectivity (represented by \(\widetilde{\boldsymbol{\mathcal{A}}}^2, \widetilde{\boldsymbol{\mathcal{A}}}^3, \ldots, \widetilde{\boldsymbol{\mathcal{A}}}^K\)). As we will discuss later, greater higher-order graph connectivity can accelerate the convergence of the noise matrix. To formally quantify higher-order graph connectivity, we provide the following definition: \[\label{evenness32factor} \tau = \max_i \tau_i, \;\;\text{ where } \tau_i = {n\sum_{j=1}^{n}\left[\mathbf{S}\right]_{ij}^2}\Bigg/{\left(\left[\mathbf{S}\right]_{ij}\right)^2}.\tag{11}\]

Proof can be found in Appendix 7. Theorem 1 implies that the norm of the aggregated noise matrix \(\mathbf{S}\boldsymbol{\Upsilon}\) is bounded by three terms: the number of nodes of a graph \(n\), the expansion order \(K\), the higher-order graph connectivity factor \(\tau\). We provide the intuition behind Theorem 1 by viewing \(\mathbf{S}\boldsymbol{\Upsilon}\) as sampling from the noise probability distribution. Each row of \(\mathbf{S}\) represents the weighted average of these noise samples. According to the law of large numbers, each row of \(\mathbf{S}\boldsymbol{\Upsilon}\) will converge to the expected value (\(\mu=0\)) of the noise distribution, thus reducing the non-predictive stochasticity of the weighted average noise. The denoising effect of \(\mathbf{S}\boldsymbol{\Upsilon}\) depends on the number of samples (i.e., \(K\) ) and the weights \(\mathbf{S}_{i j}\), both of which are influenced by the depth of GNNs and the graph structure. We provide an illustration in Appendix 13.

3.3.2 Architecture↩︎

For low node-degree graphs, it is impossible to increase the node degree; however, introducing the additional term \(\frac{\varepsilon\mathbf{X}\mathbf{X}^{\top}}{\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}}\) can add additional graph connectivity, thereby decreasing the higher-order graph connectivity factor. Thus, we employ the second option in Eq. 9 for low node-degree noisy graphs. Furthermore, considering the noise comes from a Gaussian distribution, the magnitude of the added noise values can be unpredictable. Nonetheless, the term \(\left\|\mathbf{X}\mathbf{X}^{\top}\right\|_{F}\) can penalize the weights when noise values are excessively large, thereby mitigating the adverse effect of the noise. Note that the weights of edges also determine the factor as shown in Eq. 11 . For high node-degree graphs, we can reassign the weights of edges through the additional term to decrease the factor as shown in the third option. In the experiment section, we will demonstrate the effectiveness of our GADC (II, III) in dealing with noise in node features for both types of graphs.

3.4 Improving Performance on Heterophilic Graphs↩︎

The aggregation scheme in message-passing-based GNNs is generally considered harmful for learning node representations on heterophilic graphs. To alleviate the negative impact of inconsistent edges on heterophilic graphs, we employ the first option in Eq. 9 to reduce the weights of the Laplacian matrix coefficients. Thus, the additional term, \(\varepsilon\mathbf{\Phi}\), can obstruct the graph smoothing process. In our subsequent ablation study, we will demonstrate our GADC (I) can improve performance on heterophilic graphs.

3.5 Decoupling Feature Aggregation from Downstream Training↩︎

GADC is formulated as Eq. 8 , with four options presented in Eq. 9 and Eq. 10 . Depending on the scenario, we first select the appropriate option and then calculate \(\Phi_{i j}\) using the feature matrix \(\mathbf{X}\). This allows us to obtain the graph diffusion matrix \(\mathbf{S}\). We then multiply the graph diffusion matrix by the feature matrix \(\mathbf{X}\) to get the aggregated features \(\mathbf{S}\mathbf{X}\). Finally, we use the aggregated features as input to train a linear model or an MLP. This approach effectively decouples feature aggregation from downstream training. The overall process is illustrated in Algorithm 2.

3.5.0.1 Differences from APPNP and GNNGuard.

For the fourth option, our algorithm is a pre-computation method that uses the additional term to reconstruct the graph structure once. After reconstructing the adjacency matrix, we use it directly to aggregate node features. GNNGuard evaluates the importance of neighbors using the cosine similarity of node embeddings for each layer and normalizes the similarity. Therefore, the features used for computing similarity differ between GADC (I) and the higher layers (\(\geq 2\)) of GNNGuard. Additionally, our GADC differs from APPNP. APPNP performs a nonlinear transformation on the feature matrix and then uses the graph diffusion matrix to aggregate node features. In contrast, we introduce an additional term to create more adaptable GADC architectures.

4 Experiments↩︎

In this section, we conduct extensive experiments to demonstrate the effectiveness of our proposed GADC architectures in various scenarios.

4.1 Evaluation of Defense against Adversarial Attacks on the Graph Structure↩︎

In this section, we demonstrate the defense performance of our proposed GADC (IV) against adversarial attacks on the graph structure, including non-adaptive and adaptive attacks [32], by utilizing the additional term in the modified transition matrix. We conduct experiments on three citation network datasets [25]: Cora, Citeseer, and Pubmed. The statistics for all datasets used in this paper can be found in Appendix 9. For non-adaptive attacks, we use Mettack [16], and for adaptive attacks, we use Aux-Attack.

3pt

4.1.0.1 Baselines.

For the baselines on non-adaptive attacks, we use two popular GNNs: GCN [1] and GAT [3]; two GDCs: APPNP [20] and S\(^2\)GC [9]; a graph transformer: NAGphormer [33]; and various defense methods against Meta-attack [16], including RobustGCN [34], GCN-Jaccard [35], GCN-SVD [36], Pro-GNN [17], GNNGuard [26], Elastic GNN [10], STABLE [37], EvenNet [38], GCN-GARNET [39], and HANG-quad [40]. For the baselines on adaptive attacks, we consider GCN, GCN-SVD, GNNGuard, and Soft-Median-GDC [41].

4.1.0.2 Setting.

For non-adaptive attacks, we use DeepRobust [42] to generate disrupted graph structures on Cora, Citeseer, and Pubmed datasets with perturbation rates of \(0.25,0.5\), and 0.75. We follow dataset splits used in [17]. Each experiment is repeated 10 times, and we report the mean test accuracy and its standard deviation on the node classification task. For our GADC (IV) model, we add a 2-layer MLP with 32 hidden units after feature aggregation. We tune hyper-parameters with the validation dataset. We also tune some baselines such as HANG-quad, GCN-GARNET, and EvenNet. All hyper-parameter details of our methods can be found in Appendix 10. For adaptive attacks, we set the attack budget to 1000 for the Cora and Citeseer datasets and use dataset splits from [32]. The experiment is repeated once. For our model, we set \(K=2\) and discard the terms for \(k=0/1\), similar to SGC [43].

8pt

4.1.0.3 Results.

Table ¿tbl:tab:metaattack? reports the results of non-adaptive attacks for our method and other baselines. Our method outperforms other baselines on Citeseer and Pubmed and achieves performance relatively close to the best baseline on Cora. Additionally, our GADC (IV) significantly outperforms both APPNP and S\(^2\)GC. As the perturbation rate increases, the adjacency matrix becomes increasingly unreliable. However, our additional term leverages the inherent homophily properties of these graphs to reconstruct the clean adjacency matrix, thereby restoring effective information flow within the aggregation scheme. GNNGuard and NAGphormer also evaluate the importance of neighbors using the attention mechanism on node embeddings at each layer to mitigate the disruption of the graph structure caused by adversarial attacks. In contrast, our algorithm is a pre-computation method that uses the additional term to reconstruct the graph structure directly in one step. After reconstructing the adjacency matrix, we use it directly to aggregate features. We think that smoothing node features makes the recalculated weights less accurate. Therefore, our method performs much better than GNNGuard and NAGphormer.

Table 1 reports the experimental results of our method and the baselines under adaptive attacks. The results demonstrate that our method significantly outperforms the baselines. This indicates that even when adaptive attacks modify the graph structure during inference, our additional terms can still effectively reconstruct the adjacency matrix and provide a robust defense.

4.2 Evaluation of Denoising against Noise in Node Features↩︎

In this section, we compare the denoising performance of our proposed GADC (II, III) with various baselines by evaluating their test accuracy when models are trained on noisy feature matrices.

20pt

4.2.0.1 Datasets.

For our experiments, we use three small-scale graph datasets: Cora, Citeseer, and Pubmed, and three large-scale graph datasets: Coauthor-CS, Coauthor-Phy [44], and ogbn-products [45]. We follow dataset splits used in [46] for the citation network datasets. For the Coauthor datasets, we split the nodes into 60% for training, 20% for validation, and 20% for testing. For the ogbn-products dataset, we follow dataset splits provided by OGB [45].

4.2.0.2 Baselines.

For the baselines, we consider several variants of GDC, including APPNP [20], GLP [8], S\(^2\)GC [9], and AirGNN [18]. Additionally, we include popular GNNs such as GCN [1] and GAT [3]. We also consider IRLS [11], a GNN architecture derived from GSD, and an MLP, which does not employ any aggregation scheme.

4.2.0.3 Setting.

We assume that the original feature matrix is clean and devoid of noise. To introduce noise, we synthesize it from a standard Gaussian distribution and add it to the original feature matrix, as suggested in AirGNN [18]. After adding Gaussian noise, we apply row normalization to node features and train all models using these noisy feature matrices. The noise level \(\xi\) controls the magnitude of the noise added to the feature matrix: \(\mathbf{X}+\xi\boldsymbol{\Upsilon}\), where \(\boldsymbol{\Upsilon}\) is sampled from a standard i.i.d. Gaussian distribution. For Cora and Citeseer, we test \(\xi \in \{0.1, 0.2, 0.3, 0.4, 0.5, 100\}\), and for Pubmed, we test \(\xi \in \{0.01, 0.02, 0.03, 0.04, 0.05, 100\}\). For Coauthor-CS, Coauthor-Phy, and ogbn-products, we test \(\xi \in \{0.1, 1.0\}\). For each model’s hyperparameters, we follow the settings reported in their original papers. To reduce randomness, we repeat the experiment 100 or 10 times and report the mean test accuracy. In each repeated run, different Gaussian noises are added; however, within the same run, the same noisy feature matrix is used to train all models. For the citation network datasets, we employ the second option in Eq. 9 , and we set \(K=16\) and \(\lambda=32\) by default. We select \(K\) for other datasets based on the best performance on the validation dataset. For coauthor datasets, we use the second option. For ogbn-products, we use the third option and don’t add additional graph connectivity since it is a very large graph. Therefore, we only compute \(\Phi_{i j}\) based on connected neighbors in the original graph.

4.2.0.4 Results.

Table 2, 3, and 4 report test accuracy results across various noise levels for node classification tasks. As demonstrated in Table 2, 3, and 4, under high noise levels, the performance of MLP approximates random guessing, as the test accuracy is close to the inverse of the total number of labels. This implies that the added noise has effectively obscured the original features. Compared to GDC variants, our proposed GADC (II, III) demonstrates superior denoising performance at high noise levels. This demonstrates the effectiveness of the additional term in our modified transition matrix for tracking large noise. We also synthesize noise by flipping individual features with a small Bernoulli probability on three citation network datasets. We report the results in Appendix [appendix:result].

4.2.0.5 Computational Complexity.

Introducing additional edges in GADC (II) does increase the time complexity of the aggregation process. However, we mitigate this issue by decoupling the aggregation process from downstream training, ensuring that aggregation occurs only once. This differs from APPNP, which repeats the aggregation process during each training iteration (i.e., aggregation occurs \(n\) times for \(n\) iterations). As a result, completing 100 runs (one experiment) of GADC (II) on the Pubmed dataset takes only 58 seconds, and completing 10 runs on the Coauthor-CS dataset takes 22 seconds. Without introducing additional edges (\(\varepsilon=0\)), 100 runs on the Pubmed dataset take only 41 seconds. In contrast, APPNP requires 232 seconds to complete 100 runs on the Pubmed dataset. This demonstrates the computational efficiency of our method. For the ogbn-products dataset, we maintain only the one-hop connections and adjust the edge weights, without introducing additional edges, resulting in a time complexity similar to that of GDC.

4.3 Ablation Study on the Effectiveness of the Additional Term↩︎

We conduct an ablation study by setting \(\varepsilon\) to zero to observe its impact. As shown in Table ¿tbl:ablation32denoising?, for the low node-degree graph (Cora), our additional term effectively enhances denoising performance under both small and large noise. However, for high node-degree graphs (Coauthor and ogbn-products), performance improvement is noticeable only under large noise. This is because low node-degree graphs have relatively fewer neighboring nodes, so introducing the additional term increases graph connectivity, effectively filtering out noise. In high node-degree graphs, the inherent connectivity is already strong enough under small noise, reducing the need for additional connectivity to filter out noise. However, under large noise, enhanced connectivity still improves denoising for Co-author. In the ogbn-products graph, although GADC (III, \(\varepsilon \neq 0)\) doesn’t introduce new connections, it reassigns the weights of existing edges, successfully reducing the value of \(\tau\) and thereby improving denoising performance.

4.4 Improving Performance on Heterophilic Graphs↩︎

We conduct an ablation study to show that our GADC (I) can improve performance on heterophilic graphs. Due to the space limit, we provide the experimental results in Appendix 12 and discuss related work in Appendix 8.

5 Conclusion↩︎

We introduce a min-max formulation of the graph signal denoising problem and develop various GADC variants. Extensive results demonstrate that our GADC effectively addresses noisy features in graphs, graph structure attacks, and inconsistent edges on heterophilic graphs.

Acknowledgements↩︎

We thank all the anonymous reviewers for their helpful comments and suggestions. Songtao Liu thanks ICML and NeurIPS so much for providing financial aid, making him attend ICML 2022/2023 and NeurIPS 2023 in person, as he was unable to get other funding sources for attendance (ICML 2023, NeurIPS 2023).

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

6 The Row Summation of the Graph Diffusion Convolution Matrix↩︎

We provide the derivations of the row sum of \(\mathbf{S}=\frac{1}{\lambda+1} \sum_{k=0}^K\left[\frac{\lambda}{\lambda+1} \widetilde{\boldsymbol{\mathcal{A}}}\right]^k\) in this section. Before we derive the row summation of \(\mathbf{S}\), we first derive the row summation of \(\widetilde{\boldsymbol{\mathcal{A}}}^{k}\). Note we consider \(\widetilde{\boldsymbol{\mathcal{A}}}=\widetilde{\mathbf{D}}^{-1} \widetilde{\mathbf{A}}\) for the simplicity of the proof.

Lemma 1 describes the row summation of \(\widetilde{\boldsymbol{\mathcal{A}}}^{k}\) is 1. Now we can obtain the row summation for \(\mathbf{S}\).

Then for any \(i\), we have \[\begin{align} \sum_{j=1}^{n}\left[\mathbf{S}\right]_{ij} &=\frac{1}{\lambda+1}\sum_{k=0}^{K} \left(\frac{\lambda}{\lambda+1}\left[\widetilde{\boldsymbol{\mathcal{A}}}\right]_{ij}\right)^{k}\\ &=\frac{1}{\lambda+1}\sum_{k=0}^{K}\left(\frac{\lambda}{\lambda+1}\right)^{k} \\ &=1-\left(\frac{\lambda}{\lambda+1}\right)^{K+1}. \end{align}\]

7 Proof of Theorem 1↩︎

We first introduce the General Hoeffding Inequality [47], which is essential for bounding \(\left\|\mathbf{S}\boldsymbol{\Upsilon}\right\|_{F}^{2}\).

Now, we prove Theorem 1.

8 Related Work↩︎

8.0.0.1 Adversarial Attacks on Graph Structure.

Several defense methods have recently been proposed to counter graph structural attacks [49]–[53]. [35] introduce GNN-Jaccard, which works with the graph’s adjacency matrix to identify fake edges. RobustGCN [34] employs Gaussian distributions in hidden layers to mitigate the effects of attacks. GNN-SVD [36] reduces the rank of the adjacency matrix to counteract NETTACK, which targets high-rank singular components in graph data. Lastly, Pro-GNN [17] presents an approach that jointly generates a new structural graph and a robust GNN model from the perturbed graph. By utilizing the additional term in our proposed GADC (IV), we can reconstruct the informative adjacency matrix, thus restoring efficient information flow and defending against adversarial structure attacks.

8.0.0.2 Implicit Denoising in GNNs.

Existing graph denoising works primarily focus on graph smoothing techniques [29], [54]–[56]. It is well-established that GNNs can increase node feature smoothness through neighbor information aggregation, counteracting the influence of noisy features in the GNN’s output. Some recent GNN models, such as GLP [8], S\(^2\)GC [9], and IRLS [11], are derived from the perspective of signal denoising. Additionally, Ma et al. [57] connect signal denoising to popular GNNs by considering the message passing scheme as a process of solving the GSD problem.

9 Datasets Details↩︎

10 Hyperparameter Details↩︎

We provide details about the hyparatemeters of GADC in Table 5,  6, 7, 8, and 9.

0.6mm

0.6mm

0.6mm

0.6mm

0.6mm

11 Denoising Performance against Flipping Perturbations↩︎

We provide results in Table ¿tbl:table:flip?.

12 Ablation Study on Heterophilic Graphs↩︎

In this section, we show the improvement of our proposed GADC (I) on heterophilic graphs with the additional term in the modified transition matrix through a series of ablation studies.

12.0.0.1 Datasets.

We use four datasets for fully supervised node classification on heterophilic graphs: Cornell, Texas, Wisconsin, and Actor. For each dataset, we randomly split nodes into 60%, 20%, and 20% for training, validation, and testing, as suggested in [58].

12.0.0.2 Setting and Results.

We evaluate the performance of the additional term on heterophilic graphs by setting \(\varepsilon\) to a series of values. We also add a 2-layer MLP with 64 hidden units after the feature aggregation of GADC (I). For GADC (I), we set \(\lambda\) to 1 and \(K\) to 16. We conduct experiments 100 times and report the mean test accuracy for the node classification task. Note that in each repeated run, we use a different dataset split. From the results summarized in Table ¿tbl:table:heterophily?, it is evident that incorporating the additional term (\(\varepsilon \in \{1.0, 2.0\}\)) can lead to improved performance compared to the scenario where it is disabled (\(\varepsilon=0\)). Furthermore, we notice that when \(\varepsilon\) is set to 1.0, the performance improvement is maximized. This observation suggests that these specific perturbation levels could be optimal for the context of our study.

3mm

Test accuracy with \(100\) runs of GADC (I) on heterophilic graphs. For these datasets, we use \(\varepsilon\) of 0, 1.0, 2.0, 3.0, and 4.0, respectively.

13 Illustration of Higher-order Graph Connectivity Factor on Various Graphs↩︎

In this case study, we present four illustrative samples in Figure 3: \(G_1\), \(G_2\), \(G_3\), and \(G_4\).

Graphs \(G_1\), \(G_2\), and \(G_3\) have the same number of nodes. However, the nodes in \(G_1\) are isolated, \(G_2\) consists of a single connected component with a central node \(v_1\), and \(G_3\) is a complete graph where each node is connected to every other node. Additionally, we include a larger graph, \(G_4\), to analyze the influence of graph size on the denoising effect. From Figure 3, we can derive the following insights:

• No Denoising on Isolated Graph (\(G_1\)): Since the nodes in \(G_1\) are isolated, there is no denoising effect, as indicated by the large value of \(\tau\log n /n\).

• Best Denoising on Complete Graph (\(G_3\)): The complete graph \(G_3\) exhibits the best denoising effect among the graphs of the same size. This is because the elements in each row are uniformly distributed, leading to the lowest possible value of \(\tau\).

• Central Node Impact on Connected Graph (\(G_2\)): Although \(G_2\) has only one connected component, the presence of a central node \(v_1\) creates an imbalance in the value of elements in each row. Consequently, \(\tau\) tends to be larger compared to \(G_3\).

• Denoising on Decentralized Larger Graph (\(G_4\)): The decentralized structure of \(G_4\) also results in a smaller value of \(\tau\), indicating a good denoising effect.

• Influence of Graph Size: Larger graphs, such as \(G_4\), tend to have a better denoising effect due to their size.

By analyzing these graphs, we get a deeper understanding of how graph structure and size influence the denoising effect.

14 Reproducibility↩︎

We use Pytorch [59] and PyG [60] to implement GADC. All the experiments in this work are conducted on a single NVIDIA Tesla A100 with 80GB memory size. The software that we use for experiments are Python 3.6.8, pytorch 1.9.0, pytorch-scatter 2.0.9, pytorch-sparse 0.6.12, pyg 2.0.3, ogb 1.3.4, numpy 1.19.5, torchvision 0.10.0, and CUDA 11.1.

15 Work Statement↩︎

This is an extended work based on our manuscript [61] that appeared in 2022 NeurIPS GFrontiers. Songtao Liu independently extends [61] and rewrites the initial versions of this work.

References↩︎