Characterizing the Influence of Topology on Graph Learning Tasks

We first relate the graph topology to the graph tasks. Thanks to the graph filters in the preliminaries, the influence of the graph topology on a GNN model can be simplified and approximated as a graph filter $\boldsymbol{f}(\textbf{A})$. $\boldsymbol{f}(\textbf{A})$ can be viewed as a graph filter function $\boldsymbol{f}(\cdot):\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n\times n}$ applied to the adjacency matrix A of the observed graph. With the decoupling analysis of GNN, the prediction is obtained by $\boldsymbol{f}(\textbf{A})$ working on prediction results $\boldsymbol{g}_{\theta}(\textbf{X})$ based on feature matrix X through graph learning models [5, 29, 8], where $\boldsymbol{g}_{\theta}(\textbf{X})$ on X can be viewed as extracting task-related information in X and ideally, one of the best predictions on X could be the label matrix L. Therefore, we replace the functions with $\boldsymbol{f}(\textbf{A})\boldsymbol{g}_{\theta}(\textbf{X})$ in Equation 1 to be $\boldsymbol{f}(\textbf{A})\textbf{L}$, which simplifies the analysis from features, makes us focus on the labels and graph tasks, and provides an “upper bound” of the predicted results in the ideal situation. In the next section, we will provide a motivation analysis for this setting.

Further, instead of applying the softmax function, we perform row-normalization [9], which normalizes the summation of entries on the same row to be one, on $\boldsymbol{f}(\textbf{A})\textbf{L}$ as the prediction as used in previous works [16, 9]. The row-normalized matrix $\boldsymbol{f}(\textbf{A})\textbf{L}$ provides a summary of the edge statistics at the individual node level, as each row of $\boldsymbol{f}(\textbf{A})\textbf{L}$ represents the label neighborhood distribution of the node, which has direct connections to GNN learning [15]. As $\text{RowNorm}(\boldsymbol{f}(\textbf{A})\textbf{L})=\text{RowNorm}(\boldsymbol{f}(\textbf{A}))\textbf{L}$, we perform row-normalization on graph filter $\boldsymbol{f}(\textbf{A})$, and $\boldsymbol{f}(\textbf{A})$ is row-normalized in our subsequent analysis.

Therefore, to quantify the compatibility between graph topology and graph tasks, we propose measuring the similarity between the ideal prediction L and the graph filter that performs the ideal feature $\boldsymbol{f}(\textbf{A})\textbf{L}$. The more similar L and $\boldsymbol{f}(\textbf{A})\textbf{L}$ is ($\boldsymbol{f}(\textbf{A})\textbf{L}\sim\textbf{L}$ for short), the better the graph topology matches the graph tasks, which we provide a motivating example with mild assumptions to validate in the next section. This can be understood through various scenarios:

• •

  In graph filtering, the fact that $\boldsymbol{f}(\textbf{A})\textbf{L}\sim\textbf{L}$ indicates that signals in L, whether low or high frequency, are well preserved after being filtered by $\boldsymbol{f}(\textbf{A})$. This preservation of information suggests a good match between task labels and the graph topology.

• •

  Considering the concept of the homophily/heterophily, when $\boldsymbol{f}(\textbf{A})\textbf{L}\sim\textbf{L}$ means linked nodes described by $\boldsymbol{f}(\textbf{A})$ likely belong to the same class or have similar characteristics, which is aligned with the homophily principle.

• •

  In terms of Dirichlet energy, if $\boldsymbol{f}(\textbf{A})\textbf{L}\sim\textbf{L}$ means low Dirichlet energy of L w.r.t. the (augmented) normalized Laplacian derived from $\boldsymbol{f}(\textbf{A})$. This indicates the smoothness of L on $\boldsymbol{f}(\textbf{A})$, suggesting a good match between the graph topology and tasks.

All above, we define $\mathcal{I}(\textbf{A})$ to quantify the degree of compatibility between graph topology and graph tasks,

where $\mathcal{S}(\cdot)$ is a similarity measurement, which can be chosen according to the requirements of the problem, for example, similarity induced by the inner product or Euclidean distance.

To find a graph topology that matches the graph tasks well, our goal is to maximize $\mathcal{I}(\textbf{A})$ over A. However, $\mathcal{I}(\textbf{A})$ would be trivially maximized with $\boldsymbol{f}(\textbf{A})=\textbf{I}$, where the graph topology is completely removed. To address this issue, we introduce a regularization function $\mathcal{R}(\cdot)$, which penalizes $\mathcal{I}(\textbf{A})$ if $\boldsymbol{f}(\textbf{A})$ is close to the identity matrix, to minimize the modification of $\boldsymbol{f}(\textbf{A})$. We also demonstrate such regularization from the perspective of graph denoising in the next section. Therefore, the optimization problem is formulated as

where $\lambda$ is a hyperparameter used to balance the trade-off between $\mathcal{I}(\textbf{A})$ and $\mathcal{R}(\textbf{A})$. However, there are $2^{n\times n}$ possible states of A, making the optimization of $\mathcal{C}(\textbf{A})$ computationally intractable due to its nondifferentiability and combinatorial nature. Moreover, the optimization does not consider the original topology. Therefore, instead of optimizing the problem globally, a more practical and effective approach is to start with the originally observed graph and locally optimize it, as we will present in the next subsection.

Now we zoom in the general compatibility to the node level: for every node $v_{i}$, we use the node level similarity function $\mathcal{S}_{\textbf{v}}(\cdot)$ to measure the similarity of its one-hot label vector $\textbf{L}_{i,:}$ and its normalized soft label vector $\overline{\textbf{L}}_{i,:}$ filtered by $\boldsymbol{f}(\textbf{A})$, and node level regularization function $\mathcal{R}_{\textbf{v}}(\cdot)$ to measure the regularization of its connectivity to other nodes, specifically, the $i^{\text{th}}$ row of $\boldsymbol{f}(\textbf{A})$. Let $\mathcal{C}_{\textbf{A}}(v_{i})$ denote the compatibility between the topology of node $v_{i}$’ and graph tasks. The overall compatibility metric becomes the following

where $\mathcal{I}_{\textbf{A}}(v_{i})=\mathcal{S}_{\textbf{v}}(\textbf{L}_{i,:}\|\overline{\textbf{L}}_{i,:})$ and $\mathcal{V}_{t}\subseteq\mathcal{V}$ is the node set. Notice that $\mathcal{V}_{t}$ can be not only the whole node set but also be chosen flexibly as the node set whose compatibility we care about most in correspondence to the circumstances. For example, in adversarial attack tasks, $\mathcal{V}_{t}$ can be a collection of targeted nodes to be attacked; in graph node classification tasks, $\mathcal{V}_{t}$ can be the nodes to be predicted. In this work, we choose the inner product as the similarity metric, where $\mathcal{I}_{\textbf{A}}(v_{i})$ can be evaluated as $\mathcal{I}_{\textbf{A}}(v_{i})=\overline{\textbf{L}}_{i,c_{i}}$, and $c_{i}$ is the true label of $v_{i}$, and the reciprocal of degree as the regularizer, where $\mathcal{R}_{\textbf{A}}(v_{i})$ can be evaluated as $\mathcal{R}_{\textbf{A}}(v_{i})=1/d_{i}$, and $d_{i}$ is the degree of node $v_{i}$.

From the above analysis, we can evaluate how well the overall graph topology and learning tasks are in accordance with $\mathcal{C}(A)$. We are interested in optimizing $\mathcal{C}(A)$, which can improve the compatibility between graph topology and tasks, and, by extension, improve the performance of the learning model. We are also interested in characterizing the influence of modifying part of topology on the degree of task compatibility, which can provide more interpretability of graph learning and meanwhile guide the topology modification for better task performance. To maximize $\mathcal{C}(\textbf{A})$, we can take the “derivative” of $\mathcal{C}(\textbf{A})$ by obtaining the change of $\mathcal{C}(\textbf{A})$ with local topology perturbation. Here we focus on the topology of edges and the same analysis can be simply extended to nodes and substructures. The influence of edge $e_{ij}$ can be measured by the difference between $\mathcal{C}(\textbf{A})$ on original (normalized) adjacency matrix A and $\mathcal{C}(\textbf{A}^{\prime})$ on the modified (normalized) adjacency matrix $\textbf{A}^{\prime}$ obtained by removing edge $e_{ij}$. Therefore, we define such topology influence as TopoInf of edge $e_{ij}$, denoted as $\nabla\mathcal{C}_{\textbf{A}}(e_{ij})$, is given by

The sign of TopoInf reflects the positive or negative influence of removing the edge on the matching of topology and tasks, which also indicates that removing the edge can increase or decrease the model performance. Remark that edges with positive TopoInf correspond to edges with a “negative” effect on the model performance, such that removing those can bring a positive influence, and vice versa. The absolute value of TopoInf measures the magnitude of influence: a higher absolute value means a higher influence.

It should be noted that to compute TopoInf of an edge, we do not need to recompute $\boldsymbol{f}(\textbf{A}^{\prime})\textbf{L}$, which is computationally expensive. The difference between $\mathcal{I}(\textbf{A}^{\prime})$ and $\mathcal{I}(\textbf{A})$ after removing $e_{ij}$ is limited within $K$ hop neighborhood of $v_{i}$ and $v_{j}$ considering a $K$-order filter $\boldsymbol{f}(\textbf{A})$. Therefore, we only need to compute the difference of node influence on the neighborhood affected by the edge removal in Equation 3.

Remark that we do not assume that we have all the true labels. Using all labels is for the convenience of analysis to demonstrate the effectiveness of the metric. In practical graph tasks where not all labels are available, we can use pseudo labels obtained by MLP or GNN models as replacements for true labels and compute estimated TopoInf based on pseudo labels. This will introduce errors, but can still be effective which we will show in our experiment.

Moreover, due to the presence of nonlinearity in GNN models, the extraction of $\boldsymbol{f}(\textbf{A})$ can be challenging for graph models, and an approximation of $\boldsymbol{f}(\textbf{A})$ is required. We assume that $\boldsymbol{f}(\textbf{A})$ can be obtained or approximated for the graph models, and a better approximation can improve the accuracy of the influence metric. Here, we present our approach to obtaining, approximating and learning $\boldsymbol{f}(\textbf{A})$ for several representative GNN models.

• •

  Obtained graph filters. For SGC [26], S2GC [30], APPNP [13], and other decoupled GNNs, $\boldsymbol{f}(\textbf{A})$ can be directly obtained by Equation 1.

• •

  Approximated graph filters. For GCN [12] and other GCN-like models, the presence of nonlinearities introduces additional complexities to $\boldsymbol{f}(\textbf{A})$, as it becomes dependent not only on the observed graph topology but also on the learnable parameters and the activation function. In this study, we adopt an approximate approach to estimate $\boldsymbol{f}(\textbf{A})$ by removing the nonlinear activation to simplify the analysis, as works in [26, 15]. For GCNII [3] and other GNNs with residual connections between layers, we can employ a similar approximate approach as in GCN to estimate $\boldsymbol{f}(\textbf{A})$ by removing the nonlinear normalization. This approximation without nonlinearity, can still capture the effects of graph learning models performing on the topology, as we will show in our experiments.

• •

  Learned graph filters. For GPRGNN [4], ChebNet [6], and other GNNs driven by learning filters, the filter weights are learned based on backpropagation, where we are not able to obtain the graph filter $\boldsymbol{f}(\textbf{A})$ before training. In this study, we adopt two approximate approaches to deal with this problem. One approach is to train the filter-based GNN model, obtain the trained filter weights, and then apply the learned graph filter as $\boldsymbol{f}(\textbf{A})$. Another approach is to use fixed filter weights or predefined filters as the graph filter $\boldsymbol{f}(\textbf{A})$, such as $\hat{\textbf{A}}^{K}$. This approach ignores the effect of the learned filter weights in the GNN model but can still preserve the order information and other prior knowledge from the GNN model. Moreover, for GAT [25] and other attention-based GNNs, unlike GNNs driven by learning filters, the learned filters are implicitly determined by the weights of the neural network and the input features, and the learned filters may change due to the randomness during initialization and training. In this case, we apply only the second approach with a predefined fixed filter as an approximation.

Here we present a theoretical analysis to validate our TopoInf and enhance its comprehensibility. According to the definition of cSBMs [7], the feature matrix $\textbf{F}=\textbf{L}\mu$ is directly related to the prediction L and contains sufficient information for the graph learning task, which is also discussed and empirically verified in [16]. In this part, we follow the setting in [16] as a motivating example, and treat F as the true signals and $\boldsymbol{f}(\textbf{A})\textbf{X}$ as the prediction, and evaluate the effect of the low-pass filter by measuring the difference between the filtered feature matrix $\boldsymbol{f}(\textbf{A})\textbf{X}$ and the true feature matrix F. To analyze the difference, we focus on the low-pass filter, which is true for most GCN-like models [12, 26, 13, 16], use $\left\|\boldsymbol{f}(\textbf{A})\textbf{X}-\textbf{F}\right\|$ as the prediction error introduced by the learning model and the topology, and consequently establish the following theorem.

Theorem 4.1 suggests that the effect of a graph filter is upper bounded by two parts, as shown on the right side of Equation 5. For the first part, $\left\|\boldsymbol{f}(\textbf{A})\textbf{L}-\textbf{L}\right\|$ represents the bias introduced by the filter $\boldsymbol{f}(\textbf{A})$ on the ideal feature matrix $\textbf{F}=\textbf{L}\mu$, which is related to the label matrix L, weighted by a constant of the embedding vectors of the labels. For the second part, $\left\|\boldsymbol{f}(\textbf{A})\right\|$ weighted by the constant related to the noise, reflects the effect that $\boldsymbol{f}(\textbf{A})$ filters the noise N. Intuitively, better performance can be achieved when bias is minimized and more noise is filtered out. Our definition of $\mathcal{C}(\textbf{A})$, which captures the compatibility between graph topology and tasks, aligns with Theorem 4.1, as it considers both parts. On the one hand, $\mathcal{I}(\textbf{A})$ corresponds to $\left\|\boldsymbol{f}(\textbf{A})\textbf{L}-\textbf{L}\right\|$, as a smaller value of $\left\|\boldsymbol{f}(\textbf{A})\textbf{L}-\textbf{L}\right\|$ indicates a higher similarity between $\boldsymbol{f}(\textbf{A})\textbf{L}$ and L. On the other hand, $\mathcal{R}(\textbf{A})$ aligns with $\left\|\boldsymbol{f}(\textbf{A})\right\|$, as a smaller value of $\left\|\boldsymbol{f}(\textbf{A})\right\|$ implies less regularization on $\boldsymbol{f}(\textbf{A})$. Furthermore, our definition of $\mathcal{C}(\textbf{A})$ offers more flexibility, as the similarity function $\mathcal{S}(\cdot)$ is not limited to Euclidean distance and the regularization function $\mathcal{R}(\cdot)$ is not limited to L2-norm. This flexibility allows for a broader range of choices in defining the compatibility measure based on specific requirements and characteristics of the graph learning task at hand.

We further investigate the bias introduced by $\boldsymbol{f}(\textbf{A})$ on F by analyzing the change in the distance between a node and its farthest inter-class node, which represents the radius of nodes belonging to a different community distributed, centered on the node. A larger radius indicates easier classification. For noise filtering, we measure the change in variance after applying the filter. In the following, we present the results in detail.

Theorem 4.2 shows that the distances analyzed decrease after applying the graph filter, indicating that the difficulty increases for classification and reflects that bias is introduced. For noise, the variance of the noise decreases through the low-pass filter, suggesting that the noise is reduced. In order to analyze the compatibility comprehensively, we need to consider these two effects simultaneously. This also explains why $\mathcal{I}(\textbf{A})$ and $\mathcal{R}(\textbf{A})$ are necessary in $\mathcal{C}(\textbf{A})$.

We further present a case study on cSBM to analyze the performance of GCN with different feature noise and show the effects of $\boldsymbol{f}(\textbf{A})$.

As shown in Figure 1, MLP outperforms GCN when the noise variance $\sigma$ is close to zero. The performance gap occurs because $\boldsymbol{f}(\textbf{A})$ biases the prediction of GCN and the lower the quality of the topology, i.e., the lower $p$, the larger the gap, from left to right. However, as $\sigma$ increases, the performance of both MLP and GCN decreases, but the performance of GCN decreases more slowly than that of MLP because GCN smooths the noise through topology. During this phase, the performance of MLP gradually approaches that of GCN until GCN outperforms MLP. When the noise variance is too large to dominate the feature, the performance of MLP and GCN drops and converges. The convergence performance of GCN is usually higher than MLP, as MLP degenerates into random guesses, while GCN is still able to learn from topology.

This motivating experiment shows that, compared with MLPs which do not utilize graph topology, the bias introduced by the low-pass filter $\boldsymbol{f}(\textbf{A})$ results in that MLPs outperform GNNs when the noise variance in features is near zero, suggesting that this effect is generally bad for performance. However, compared to MLPs, low-pass filters $\boldsymbol{f}(\textbf{A})$ also provide an additional noise reduction ability, which improves the performance of GNNs when the noise variance in features is greater than zero. Therefore, to fully analyze the compatibility between topology and task in GNN models, we design both $\mathcal{I}(\textbf{A})$ and $\mathcal{R}(\textbf{A})$ in $\mathcal{C}(\textbf{A})$ to analyze and quantify these two effects simultaneously.

As is shown in Figure 2, performance curves exhibit an S-shaped pattern. Specifically, after removing edges in the positive set, the model performance increases, while removing edges in the negative set diminishes the performance. Moreover, removing edges with higher absolute TopoInf values results in a greater derivative of the performance plots. These are consistent with our previous analysis and show the effectiveness of TopoInf.

In addition, we compare our edge removal strategies with other methods. We choose two baseline methods, namely Random and AdaEdge. For Random, we randomly remove edges with equal probability. AdaEdge [2] divides edges between nodes with the same labels into the negative set and different ones into the positive set. AdaEdge randomly removes edges in each set, while TopoInf removes edges in each set in descending order, sorted by the absolute values of their TopoInf.

Figure 3 shows our results. When an equal number of positive/negative edges are removed, the model performance of Random remains unchanged almost, while the model performance of AdaEdge and TopoInf increases/decreases distinctly, indicating a correlation between both the homophily metric and our compatibility metric with the model performance. Moreover, the model performance of TopoInf increases/decreases more significantly than that of AdaEdge. This shows the effectiveness of TopoInf as it not only identifies the direction of influence but also measures the magnitude of influence.

When ground truth labels are generally only available on training sets, we employ an initial training phase using the GNN model to obtain pseudo labels for each node. Thereafter, we estimate TopoInf using these pseudo labels for the nodes without true labels and remove edges based on the estimated TopoInf.

Table 3 shows the results. We can see that in almost all cases, the refined topologies based on estimated TopoInf outperform the original ones, in both retraining and non-retraining settings. On SOTA models, such as BernNet, TAGCN and GCNII, TopoInf still achieves competitive results or improves performance. This experiment shows that the estimated TopoInf is still an effective metric for enhancing topology.

Table 3 shows the results. In almost all cases, our TopoInf-guided DropEdge method achieves the highest accuracy, and in all cases, our method outperforms DropEdge. Even in cases where DropEdge degenerates the performance of GNNs, such as BernNet on CiteSeer, and GPRGNN on PubMed, TopoInf-guided DropEdge can still improve the performance. This experiment shows the potential to combine TopoInf with other methods for topology modification and performance improvement.