Unifews: You Need Fewer Operations for Efficient Graph Neural Networks

We thank the reviewer for the insightful feedback. We have carefully checked the experiments and would like to address the questions as follows.

W1&Q4

We further evaluate other scalability methods and present representative accuracy and training time as below. We also evaluate the smaller cora for comparison. Notably, only GraphSAGE is applicable to papers100M through mini-batch training, while other methods incur OOM error. Methods such as GraphSAINT and ClusterGCN entail longer time for processing the graph data and exhibit weaker scalability on larger graphs.

Mini-batch cora

Mini-batch papers100M

We would like to highlight the difference between the settings and our evaluation in the paper as follows:

1. The training is conducted in mini-batch with batch size=100K. Testing is performed in full-graph manner on CPU due to the excessive graph size.

2. The "edge ratio" is calculated by $\eta=1-m'/m$, where $m'$ is the total number of sampled neighbors used in propagation, and $m$ is the edge size in the raw graph. This concept is different from edge sparsity since the propagation graph is not static.

3. As elaborated in Sec A.2, the graph structure used for coarsening and sampling methods is dynamically determined during training, which limits their wider generality. For example, they cannot be described by the graph smoothing framework, and can hardly apply to decoupled models.

W2&Q1

We elaborate the setups of the papers100m result in Tab 1:

1. We find that the previous result of SGC is largely affected by the "cold start" issue, where the first run is significantly slower than the others due to the overhead in accessing and loading the data. By excluding the first run, the average time is around 15K seconds, which is close to APPNP and GraphSAGE.

2. To ensure comparable results with baselines, the decoupled propagation of all methods in Tab 1 is implemented by single-thread C++ computation that successively performs message-passing for each edge. The process may be slower than the common implementation based on matrix computation, such as Eigen in C++ and PyTorch/Numpy in Python.

3. The wall-clock time also includes auxiliary operations within the propagation, such as accessing the storage of attributes and neighboring nodes. Our implementation stores edges in the format of an adjacency list, which is tailored for the pruning operation. However, it may be slower than the matrix format when the edge scale is large, and results in a greater scalability issue for the full papers100m.

In practice, both the baseline and Unifews computation can be accelerated by approaches such as multi-threading, vectorization, and enhanced data structures. However, the relative speedup can still be achieved considering the FLOPs reduction.

Q2

The acceleration ratio of wall-clock time is also affected by several factors beside the complexity analysis:

1. As suggested in Sec 4.3, the complexity provides a lower bound for computation reduction. As the edges removal is accumulated across hops, the actual reduction rate can be larger than the theoretical bound. In fact, Unifews achieves $3.3\times$ FLOPs reduction compared to SGC, which is greater than the expected $2\times$.

2. Evaluation in Fig 7 shows the improvement of embedding sparsity brought by Unifews pruning. This effect is more significant for sparse graphs such as papers100m, since the magnitude of node embedding is more likely to diminish when edges are pruned. The improved sparsity further facilitates pruning in subsequent layers and leads to faster computation.

3. As elaborated in Q1(3), the overhead of auxiliary graph operations is more sensitive to the graph scale. For example, finding a neighbor of a node is faster if the edge set is smaller. This may result in speedup greater than the linear improvement.

Q3

In Tab 1, we only present the results of approaches applicable to decoupled models with the separated graph propagation in C++. Since the official implementation of DSpar is based on the PyG framework for iterative models, we are unable to apply it to the decoupled propagation.

We are thankful for the detailed and insightful comments from the reviewer. We address the specific reviews below with further evaluation results.

W1

In the paper, we do not show the wall-clock time for iterative models mainly because of the variety in baseline implementations. The existing approaches vary greatly in terms of GNN frameworks and the implementation of sparsification. For example, GLT applies masks on the adjacency matrix, while CGP utilizes learnable edge weights stored in variable tensors. As a result, the wall-clock time among different models is hardly comparable in a fair manner. We hence employ FLOPs to measure the expected computation cost, which is also widely used in related studies.

Furthermore, the FLOPs measured in Fig 6 of different operations are not equivalent to wall-clock times. This is because the feature transformation is performed on GPU with highly efficient dense-dense matrix-matrix multiplication (MM), while the graph propagation as sparse-dense matrix-matrix multiplication (SPMM) is not applicable to most acceleration techniques. In fact, the adjacency matrix is usually loaded on CPU, rendering the propagation a complicated cross-device and irregular computation, which is usually considered as the bottleneck of GNN efficiency.

We present the inference time breakdown of Unifews for GCN+arxiv in the following table. It can be observed that both operations benefit from the sparsification.

GCN+arxiv

In summary, we believe achieving practical speedup is largely an implementation problem. There is a series of works [Deng et al., 2020a] developing software and hardware systems and achieving real speed improvement, which is orthogonal to our contribution on how to achieve such sparsity by algorithmic design.

W2

While approaching 100% sparsity, Unifews still preserves certain graph structural information, which is critical to model performance. For comparison, we present the result of MLP with no graph information as below. It can be observed that the performance improvement is significant on cora and citeseer.

MLP ($L=2$)

We would like to discuss the difference of Unifews with MLP at high sparsity in the following aspects:

1. Given the large number of edge/weight entries, a number of entries remain even when the pruning threshold is high. As a result, the pruning ratio rarely reaches exactly 100% in our experiments. This phenomenon has also been observed in previous NN and GNN pruning studies [Liu et al., 2023a], where maintaining a small fraction (0.1%-1%) of edges or weights can largely preserve GNN performance.

2. As discussed in Fig 7, Unifews brings higher sparsity to the learned representation, which is known to be beneficial for model learning. This improvement is observed for both edge and weight sparsification in previous works such as [You et al., 2022; Chen et al., 2021]. As the sparsity is progressively acquired during training iterations, the model benefits from learning on perturbed variants of the data, leading to improved performance.

3. Due to the implementation of acquiring the normalized adjacency $\tilde{A}$ in PyG, the diagonal entries are $D^{-1}$ instead of $I$. Consequently, when the edge sparsity is close to 100%, each graph propagation can be viewed as a normalization to node features based on degrees, which is different from MLP. This process also incorporates graph structural information and may also contribute to better performance.

C1-3

We thank the reviewer for pointing out the issues. We will carefully fix the typos in the revised version.

The sparsified $\hat{L}$ corresponds to the pruned edge set $\hat{\mathcal{E}}$ acquired by Unifews as in Lemma 3.3 and Lemma B.1. We will improve the formulation in the revised version.

Q1

The pruning process itself is not differentiable, similar to conventional neural network pruning [Han et al, 2015]. Intuitively, pruning can be implemented by applying a 0-1 mask to the target matrix every time it is used during forward inference and backward propagation. Gradients of the pruned entries (i.e., with zero values) are naturally kept as zero. Hence, the pruning process does not affect normal model training.

It is possible to augment the pruning to be differentiable, or even adaptive during training. Works such as AdaptiveGCN, SGCN, and Shadow-GNN discussed in Sec A.1 are similar to this idea. However, the process may incur additional overhead for learning these variables. Hence, in this paper, we mainly use the simple static strategy to ensure efficiency and align with our theoretical analysis.

We sincerely appreciate the constructive feedback from the reviewer. Below, we provide detailed responses with new experiments following the suggestions.

T1

The range of the constants in Thm 4.1 is discussed in Sec B.2. The constant $2<\alpha<3$ represents degree distribution, and $\sigma>0$ is the standard deviation of feature distribution. As $t=1/(\alpha-1)$, there is $0.5<t<1$. The constant $C>0$ is related to the norm of the embedding $\|p\|$, as it maps the sparsity ratio $0\le\eta\le 1$ to the actual threshold value applied to the embedding.

On realistic datasets, we perform evaluation in Fig 12, where the blue line shows that by varying the threshold $\delta_a$ (x-axis), the acquired sparsity $\eta_a$ (right y-axis) aligns well with the relationship in Thm 4.1 with two dataset-specific constants.

We further utilize GenCAT [R1,R2] to generate synthetic graphs with randomized connections and features by varying its parameters. Then, we evaluate the relationship between the edge threshold $\delta_a$ and the edge sparsity $\eta_a$ following the settings of Fig 12. The results are available in: https://anonymous.4open.science/r/Unifews-A91B/plot.pdf . As an overview, the pattern is similar to the one in Fig 12, while the constants are effectively affected by the changes of edge and feature distribution in the GenCAT graph.

[R1] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.
[R2] Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs. NeurIPS'22.

W1

We present the results of DropEdge for GCN+cora as follows. As mentioned in the DropEdge paper, its scheme is different from graph sparsification since: (1) its edge removal is performed randomly at each training time; (2) the dropped edges are not accumulated throughout propagation layers, which differs from Unifews. In comparison, the Random baseline used in our experiments is closer to Unifews regarding the two aspects above, while using random edge removal. Hence, we mainly use the Random baseline in our experiments.

Empirically, the variance of Unifews is within the range of 1-3%, which is slightly larger than the backbone model due to the perturbation of edge and weight sparsification. We will include the variance in the revised paper.

Q1

For iterative models, Unifews removes insignificant entries and improves representation sparsity as shown in Fig 7. The increased sparsity is known to be beneficial for model learning, as revealed by [Han et al., 2015] for general neural networks, and similarly evaluated for GNNs in [You et al., 2022; Chen et al., 2021]. In brief, it is believed that sparsification can be viewed as a form of perturbation during learning. By enhancing sparsity, the model can strengthen the useful neural connections within network weights and focus on the most informative features, leading to improved performance.

Regarding over-smoothing, we further study the particular effect with the iterative GCNII of 32 layers in Appendix Fig 11, and with the decoupled SGC of 5-80 layers in Fig 14. Both results demonstrate that, by increasing model layers, the accuracy of the pruned model is largely preserved thanks to the residual connections. Hence, we conclude that Unifews pruning also benefits accuracy by alleviating over-smoothing.

Q2

The performance near 100% sparsity is affected by various factors. We would like to compare it to MLP in the following aspects:

1. Given the large number of edge/weight entries, a number of entries remain even when the pruning threshold is high. As a result, the pruning ratio rarely reaches exactly 100% in our experiments. This phenomenon has also been observed in previous NN and GNN pruning studies [Liu et al., 2023a], where maintaining a small fraction (0.1%-1%) of edges or weights can largely preserve performance.

2. As elaborated in Q1, higher sparsity induced by Unifews pruning can inherently enhance model performance. During training iterations where pruning is progressively applied, the model benefits from learning on perturbed variants of the data, leading to improved performance. This improvement is observed in both edge and weight sparsification.

3. Due to the implementation of acquiring the normalized adjacency $\tilde{A}$ in PyG (torch_geometric.nn.conv.gcn_conv.gcn_norm), the diagonal entries are $D^{-1}$ instead of $I$. Consequently, when the edge sparsity is close to 100%, each graph propagation can be viewed as a normalization to node features based on degrees, which is different from MLP. This process incorporates graph structural information and may also contribute to better performance. We will revise Alg 1 to reflect this distinction explicitly.

We are thankful to the reviewer for recognizing our theoretical and experimental contributions. We respectfully address the specific reviews below.

W1

Power-law for degree distributions is frequently observed in real-world graphs, especially large-scale ones focused on in this study, such as social networks, citation networks, and web graphs [R1]. We present an empirical evaluation in Fig 8(a), where the blue bars show the distribution of inversion of edge degrees on Cora. It can be observed that edges with larger magnitudes (i.e., smaller degrees) exhibit higher relative density, while only a small portion of edges have magnitudes close to 0 (i.e., nodes with large degrees).

The assumption of the Gaussian distribution can apply to node attributes or output features of linear transformations, depending on the exact input of iterative or decoupled models. The Gaussian distribution is commonly used for depicting the feature distribution of neural networks as an extension of the central limit theorem. For example, text embeddings are commonly used as node attributes on text-attributed graphs, which can be regarded as multivariate Gaussian distributions. The similar assumption is commonly employed in graph generation and GNN research [R2-R5].

We will clarify the rationale when deriving Thm 4.1 in the revised version. In Reviewer t1S7 T1, we further present a new empirical evaluation regarding these two assumptions on synthetic graphs generated by GenCAT.

[R1] Power-law distributions in empirical data. SIAM Rev'09.
[R2] Contextual Stochastic Block Models. NeurIPS'18.
[R3] Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. ICLR'18.
[R4] Distribution Knowledge Embedding for Graph Pooling. TKDE'22. [R5] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.

W2

We mainly utilize Thm 4.1 for determining the edge threshold $\delta_a$. In realistic applications for GNN sparsification, the sparsity $\eta_a$ is usually given by users. Then, as indicated by Thm 4.1, $\delta_a$ is monotonically related to $\eta_a$ with two constants determined by the dataset and model aggregation. To set the threshold for a model-dataset pair, only a few trial epochs under different $\delta_a$ are needed to fit the actual curve between $\delta_a$ and $\eta_a$ and decide the desired value of $\delta_a$. Empirical evaluation in Fig 12 (blue line) shows that the relationship between $\eta_a$ (right y-axis) and $\delta_a$ (x-axis) aligns well with the theory. In fact, for a large range of sparsity (empirically 10%-90%), the relationship is almost linear (note that Fig 12 is drawn with a logarithmic x-axis), which further simplifies the selection.

The weight threshold $\delta_w$ can be similarly determined by fitting empirical trials when additionally assuming a Gaussian distribution for the weight matrix. This process is identical to conventional neural network pruning in practice, such as [Han et al, 2015].

C1

One potential limitation and future direction lies in the consideration of graph heterophily, as the current strategy prunes insignificant messages. However, under heterophily, where connected nodes have dissimilar labels, messages with large magnitudes may not be beneficial to model inference. In this case, the graph smoothing objective Def 3.1 needs to be refined, and consequently, the sparsification strategy should be adjusted. While there are recent works on the spectral optimization process for heterophilic graphs, how to apply sparsification is largely unexplored.