Unifews: You Need Fewer Operations for Efficient Graph Neural Networks
Authors: Ningyi Liao
Zihao Yu
Ruixiao Zeng
Siqiang Luo
Venue: ICML 2025 poster (2025)
Keywords: Graph neural networks
Graph sparsification
Network pruning
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose an efficient GNN framework with theoretically bounded spectral sparsification.

Abstract: Graph Neural Networks (GNNs) have shown promising performance, but at the cost of resource-intensive operations on graph-scale matrices. To reduce computational overhead, previous studies attempt to sparsify the graph or network parameters, but with limited flexibility and precision boundaries. In this work, we propose Unifews, a joint sparsification technique to unify graph and weight matrix operations and enhance GNN learning efficiency. The Unifews design enables adaptive compression across GNN layers with progressively increased sparsity, and is applicable to a variety of architectures with on-the-fly simplification. Theoretically, we establish a novel framework to characterize sparsified GNN learning in view of the graph optimization process, showing that Unifews effectively approximates the learning objective with bounded error and reduced computational overhead. Extensive experiments demonstrate that Unifews achieves efficiency improvements with comparable or better accuracy, including 10-20x matrix operation reduction and up to 100x acceleration on graphs up to billion-edge scale.

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Ningyi Liao Zihao Yu
Ruixiao Zeng'
Siqiang Luo
Abstract
Despite their success, canonical GNNs are recognized for their high resource consumption. especially when scaling up to large graphs (Wu et al., 2021). The performance bottleneck arises from the connection with graph size, as both graph propagation and feature transformation can be viewed as multiplications on graph-scale matrices, and lead to computational complexities proportional the numbers of edges and nodes in the graph, respectively (Chen et al., 2020). Hence, the essence of improving GNN learning effi- ciency lies in reducing the number of operations associated with graph diffusion and model weights (Liu et al., 2022; Zhang et al., 2023a).
Graph Neural Networks (GNNs) have shown promising performance. but at the cost of resource-intensive operations on graph-scale ma- trices. To reduce computational overhead, previ- ous studies attempt to sparsify the graph or net- work parameters, but with limited flexibility and precision boundaries. In this work, we propose UNIFEWS, a joint sparsification technique to unify graph and weight matrix operations and enhance GNN learning efficiency. The UNIFEWS design enables adaptive compression across GNN layers with progressively increased sparsity, and is ap- plicable to a variety of architectures with on-the- fly simplification. Theoretically, we establish a novel framework to characterize sparsified GNN learning in view of the graph optimization pro- cess, showing that UNIFEWS effectively approxi- mates the learning objective with bounded error and reduced computational overhead. Extensive experiments demonstrate that UNIFEWS achieves efficiency improvements with comparable or bet- ter accuracy, including 10-28 - 20x matrix operation reduction and up to 100x acceleration for graphs up to billion-edge seale. Our code is available https:/ /ttp::///tttttt com/ comm//mmn///////////////m /Uni fews.
In efforts reduce the graph part of computation, prior GNN graph sparsification techniques (Liu et al., 2019) typ- ically remove graph components based on either predeter- mined (Zheng et al., 2020; Zeng et al., 2021; Liu et al., 2023b) or learned (Li et al., 2021; 2022; Jin et al., 2022) criteria. Another direction is exploit compression on the model architecture by integrating network pruning ap- proaches (Deng et al., 2020a), which gradually sparsifies weight elements during GNN training (Zhou et al., 2021; Chen et al., 2021; You et al., 2022; Wang et al., 2023b). Both approaches, however, suffer from limited flexibility due to the static graph structure throughout all propagation iterations: the topology may become overly coarse, thereby omitting crucial information for GNN feature extraction, or may be under-sparsified and model efficiency is scarcely improved. Moreover, there is a noticeable gap in the theoret- ical interpretation of GNN sparsification. Existing works are either constrained to the layer-agnostic graph approximation (Chen et al., 2018; Zou et al., 2019), or only provide straight- forward representation error analysis (Srinivasa et al., 2020; Liu al., 2023b). The impact of simplified graphs on the GNN learning process, particularly through multiple layers, remains inadequately addressed.
1. Introduction
Graph Neural Networks (GNNs) have undergone extensive development for learning from graph-structure data and have achieved remarkable performance (Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018). The power GNNs mainly attributed to the message-passing scheme containing two alternative operations, namely graph propagation and feature transformation, which aggregates neighborhood information in the graph and updates repre- sentation by trainable weights.
To mitigate the drawbacks of current GNN compression, we propose UNIFEWS, UNIFied Entry-Wise sparsi-fication framework for GNN graph and weights. As illustrated in Figure by considering the two stages in GNN as matrix operations, graph and model sparsification can be unified in an entry-wise manner, i.c., manipulating individual elements during matrix multiplication. We then establish a theoretical framework to quantify the impact of UNIFEWS on precision and efficiency. By bridging the graph learning process in
'College of Computing and Data Science, Nanyang Techno- logical University, Singapore. Correspondence to: Siqiang Luo <siqiang. liiiaag..oo@nuuuccuu...
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
the spectral domain, our analysis elucidates the effect of joint sparsification across iterative GNN layers in holistic
Neighborhiood
Unimporbat
Unimpertnni Messge
manner, which differs from previous approaches focusing on a particularized metric for approximation.
Tany Saky
Importan
Center
Nods
Self-loop
In practice, UNIFEWS is capable of reducing operations in the two-stage GNN message-passinng and improving ef- ficiency. The simple but effective strategy is powerful in conducting flexible computation for each node and each GNN layer, effectively balancing the operational reduction while retaining precision. The theoretical and implementa- tion framework of UNIFEWS is applicable to broad family of GNNs, covering the representative models of both itera- tive and decoupled architectures.
Graph @
Diffusion
(a) An example graph and the corresponding diffusion matrix.
Attribute
Graph Diffusion
Embedding
Model Weight
Representation
Propagatic
Transform
Spansty 25%
Spesity: 32%
Graph Sparsification
X
Pruned Entry
Weight Sparsiflcation
Prumed Entry
Graph Propagation
Feature Transformation
In summary. (1) we propose UNIFEWS for unifying GNN graph and model sparsification from an entry-wise perspec- tive to reduce graph-scale operations and alleviate compu- tational cost; (2) we develop novel theoretical framework bridging graph spectral filtering and sparsification as approx- imation; (3) experimentally demonstrate that UNIFEWS outperforms existing GNN compressions by reaching over 90% of joint sparsity without compromising accuracy. On the billion-scale graph papers 10M, UNIFEWS is able to boost the computation time by x00x.
(b) UNIFEWS sparsification on graph and model entries.
Figure 1: (a) Graph propagation messages from neighbors with larger diffusion values are associated with greater im- portance. (b) UNIFEWS jointly applies sparsification to both GNN stages. Unimportant entries of the diffusion and weight matrices are pruned to reduce operations.
As an exemplar, the diffusion matrices for SGC (Wu et al., 2019) and APPNP (Klicpera et al., 2019) are T = and T = a(1 - a) A according to their respective designs.
2.2. Taxonomy of GNN Sparsification
2. Preliminaries and Related Works
Iterative Graph Sparsification. Graph sparsification methods aim to augment the iterative peessag-ppssing and improve accuracy (Liu et al., 2022). NeuralSparse (Zheng et al., 2020) and LSP (Kosman et al., 2022) drop edges based on topological properties, while AdaptiveGCN (Li et al., 2021) and SGCN (Li et al., 2022) implement lear- able graph connections. FastGAT (Srinivasa et al., 2020) and DSpar (Liu et al., 2023b) specifically examine spectral patterns. However, these techniques modify the graph in a one-time and layer-agnostic manner, resulting in limited flcxibility for balancing efficiency and efficacy.
2.1. GNN Architecture
Graph Notation. Consider graph G EV,E) with = [ nodes and m |8| edges. The neighborhood set of a node u E V is Nu)) = {v (u, E E}. and its degree d(u)= = [( The self-looped adjacency matrix is A E Rax" and the diagonal degree matrix is D = (dig(d(())) d(uu)).... ,((u)))))))) )). The normalized ad- jacency and Laplacian matrices are A D-1/2 A-1/2AD-11 AD-ADD111 1/2 and L A, respectively.
Iterative GNN. Iterative models such as GCN (Kipf & Welling, 2017) take the node attribute X E Rax as in- put, and recurrently update by applying the graph diffusion matrix T. The representation matrix H(++)) of the (1 + 1)- th layer is updated as Ha-n a (1 (()., where E (0, L 1), and a(.) denotes the activation fune- tion. It implies two consecutive steps, that graph propaga- tion computes the embedding Pt) = TH) (1), and feature transformation multiplies the learnable weight Way- For example, the diffusion matrix of GCN is T = Å.
Decoupled Propagation Personalization. A particular- ized branch emerges for simplifying decoupled GNNs (Zhang et al., 2021; Huang et al., 2023; Liao et al., 2023b; Zeng et al., 2021). Since the graph operation is isolated, it is more flexible for fine mme-grained modification, which replaces the graph-level message- message-passing with separate maneuver the edge connection for each propagation hop as in Fig- ure 2(a). Our UNIFEWS is akin to this idea, but with a better suitability for both iterative and decoupled propagations.
Decoupled GNN. This variant simplifies GNN architec- ture by separating the propagation from iterative updates (Wu et al., 2019; Gasteiger et al., 2019; Wang et al., 2021a). The graph-related propagation is computed in ad- vance as the embedding matrix P((41) = Tiy Pt) for l E {O..... L 1}, and the transformation is as simple as an L-layer MLP that H()+)) = a (H W(),, where the boundary conditions are Pio) = X and ( P(L)-
Architectural and Joint Compression. A series of re- search take the network architecture into account. Their general pipeline, as outlined in Figure 2(b), involves model compressor and a static graph sparsifier. Some works treat the two stages independently (Zhou et al., 2021; Liu et al., 2023a), while others exploit joint updates (You et al., 2022; Sui et al., 2024; Chen et al., 2021; Wang et al., 2023b;a). One critical drawback of these methods lies in the additional
2

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Crmphh
Grapl
Spunsified
Graph Sparsilictionn
Propagation Personalization
Graph Sjau sification
Propogate
Enibodding
Propagaic
Repeesontation
Goaph
Propogaatc
Regrosenttie
Time
Mais
Transkans
Transtonn
Attiibute
Astritano
Amaibut
Weight
Weiight
Weight
Weights
Sparsification
Wright Spurification
Wen
Wio.
Way
Reprsventation
(a) Propagation Personalization
(b) Joint Compression
(c) UNIFEWS (on Iterative GNN)
Figure 2: Comparison of GNN pipelines between conventional simplification techniques and our UNIFEWS framework. (a) Personalized propagation iteratively simplifies the node-dependent graph diffusion but only applicable to decoupled GNNs. (b) Joint model compression can sparsify both graph and weight, whereas the same diffusion is utilized across all layers. (c) UNIFEWS implements entry-wise sparsification of both graph and weights for each layer with increased sparsity.
bottleneck for learning the compression strategy, which still incurs full-scale computation and are less efficient. A thor- ough discussion regarding other efficient GNNs such as graph sampling can be found in Appendix A.
of approximation and its impact on learning outcomes, consider the spectral similarity:
Definition 3.2 (e-Spectral Similarity). The approximate
Laplacian matrix L is said to be e-spectrally similar to the raw Laplacian matrix L if:
3. Graph Smoothing under Sparsification
x =T - cI) x Lx S (L+ef)a Ye E E.. (2)
In this section, we first relate GNN learning with the graph smoothing process, which enables us to characterize the process by our novel approximation bound. Generally, broad scope of both iterative and decoupled GNNs can be interpreted by spectral graph smoothing process (Zhu et al., 2021). We adopt the optimization framework as:
Graph approximation satisfying Definition 3.2 can be re- garded as spectral sparsification (Spielman & Srivastava, 2011; Batson et al., 2013), which identifies operations that maintains certain spectral properties such as eigenvalues during modification. Compared to the common multiplica- five spectral similarity (Sadhanala et al., 2016; Calandriello et al., 2018: Charalambides & Hero, 2023), Definition 3.2 possesses an additive tolerance, which allows for manipu- lating specific entries of L and suits our scenario.
Definition 3.1 (Graph Laplacian Smoothing (Ma et al., 2021)). Given weighted graph G E) with Lapla- cian matrix L. Based on an input signal vector x E R", the Graph Laplacian Smoothing problem aims to optimize vector p E IR" with the goal:
Then, we are able to characterize the graph smoothing prob- lem for sparsified graphs. Under edge modifications, we intend to bound the optimization goal under approximation:
= arg min C, L c=lp-<>l c.. 2..p Lp, (L)
Lemma 3.3 (Approximate Graph Laplacian Smoothing). Given two graphs G = <VVE) and & = =(,E), where is the sparsified edge set. When the Laplacian L of & is e-similar to L of G, the solution 8 to the problem Equa- tion (1) w.nt L is called an e-approximation of the solution pa w.r.t L, and:
where ||- is the vector L2 norm and the regularization coefficient i chosen from [0, 1].
In Equation (1), L the general Laplacian matrix, as nor- malization only causes difference in coefficient. The first term of L reflects the closeness to the input signal, i.e., node attributes representing their identity. The second term is associated with the graph structure, acting as a regu- larization that constrains the representation values con- nected node pairs to be similar. The closed-form solution p" (I + cL)--1a can be inferred when the derivative OC/0p = 0. However, note that it is prohibitive to directly acquire the converged solution due to the inverse calculation on large graph-scale matrix. Hence, GNN models employ an iterative approach to learn the representation under this framework with varying architectural designs. For example, GCN convolution corresponds to c 1.
11 -p0pppl @'llsclllp"1l
The proof of Lemma 3.3 can be found in Appendix B.I. It establishes a novel interpretation for characterizing the smoothing procedure under a sparsified graph, that if a spar- sifier complies with the spectral similarity Definition 3.2, it is capable of effectively approximating the iterative graph optimization and achieving close output with bounded er- ror. Compared to approximation bounds specifying feature values in previous GNN sparsification theories (Srinivasa et al., 2020; Zhang et al., 2023b), our analysis highlights the impact of graph sparsifier throughout the holistic learning process, which enjoys better expressiveness and suitability.
Next, we introduce graph sparsifiers as an approximation process of graph smoothing. In order to measure the extend
3

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
4. UNIFEWS Algorithm and Theory
to sparsifying T with a node-wise threshold 6' as:
This section presents our UNIFEWS framework by respec- tively developing its application to decoupled and iterative GNNs, where graph and weight sparsification are separately performed in the former architecture, and are combined in the latter. Our key theoretical insights are summarized as: Bridging sparsification and smoothing: UNIFEWS can be described as an spectral sparsifier. Its sparsification strength is determined by the threshold of entry removal.
T u] = thrs (T(u, ul).Tlu, v), 5. - 6a (5)
where the pruning function with an arbitrary threshold 8 is (hr)(x)) = 1 if |a|| > 6, and thr,(x) = 0 otherwise. Sparsification by Equation (5) has two concurrent effects: for graph computation, messages with small magnitudes are prevented from propagating to neighbors and composing the output representation; for graph topology, corresponding edges are removed from the diffusion process.
Multi-layer bounds: UNIFEWS provides an approxima- tion the graph smoothing optimization. Its representation error to the original objective is effectively bounded.
Next, we show that edge pruning in Equation (5) for one layer can be considered as a spectral sparsification following Definition 3.2, which enables us to derive its approximation bound. Practically, the target sparsity v) E [0, 1] is usually determined by the realistic application. Let E be the edge set achieved by UNIFEWS sparsification and the corresponding Laplacian is L, there is 74 the following lemma a general guarantee associating sparsification and spectral similarity:
Improvements on efficiency and efficacy: UNIFEWS is advantageous in enhancing efficiency, mitigating the over- smoothing issue, and facilitating enhanced joint sparsity.
|8//m. We first derive
4.1. UNIFEWS as Spectral Sparsification
Intuition: Entry Values Denote Importance in Graph Computation. As depicted in Figure 2(b), conventional graph sparsification methods for GNNs only provide fixed and uniform graph-level adjustments through the entire learning process. This lack of flexibility hinders their per- formance when employing to the recurrent update design with multiple GNN layers. Contrarily, node-wise models in Figure 2(a) aim to personalize the graph-bases propa- gation, but come with additional explicit calculations and impaired runtime efficiency. We are henee motivated de- sign sparsification approach that (1) enables modifications in a fine- fine-grained manner to further simplify the computa- tion; and (2) can be seamlessly integrated into the matrix operation with negligible overhead.
Lemma 4.1. Given graph G and embedding p. let & be the edge set achieved by graph sparsification with threshold d.- The sparsified Laplacian matrix L is e-similar to L when 9a S <l|p]], where qa is the number of edges removed.
The proof of Lemma 4.1 is detailed in Appendix B.2. To derive more specific bounds of qa. we need to examine the actual distribution of entry values. Regarding the assump- tion on edge distribution, we particularly investigate the scale-free graph, which is common in realistic large-scale graphs (Clauset et al., 2009). For input attribute values, we consider the Gaussian distribution, which is also com- monly used for depicting the feature distribution of neural networks an extension of the central limit theorem (Desh- pande et al., 2018; Bojchevski & Günnemann, 2018). 8). With these two assumptions, the following theorem relates the threshold and approximation bound with sparsification:
To this end, we first focus the isolated graph propagation stage and express the propagation of decoupled models in an entry-wise manner on node u as:
P(41)]1] [x]
Twlu, v)
To Po)(u), (4) vEN(w)
Σ
Theorem 4.2 (Bound for UNIFEWS). Given a graph G, embedding p. and required edge sparsity na- the threshold 8a can be decided by ó₂ = Ci(1 - -na)=², and the sparsified Laplacian É is e-similar to L with the approximation bound:
(E)(
where the propagation message T()) [u, u) from node to is regarded as an entry. As illustrated in Figure 1(a), in a single hop of GNN diffuusin, edges carrying propagation messages exert varying impacts on neighboring nodes, whose impor- tance is dependent on the graph topology. Messages with minor significance are usually considered redundant and can be eliminated to facilitate sparsity. From the perspec- tive of matrix computation, this is achieved by omitting the particular message r(u, v] in current aggregation based on an importance indicator such as its magnitude.
c c= (7a((11 - ?%))=')
(6)
where C and t are positive constants. C is determined by the embedding values ||pl). and 0 < t < depicts the degree distribution.
The proof of Theorem 4.2 and specific derivations of C and t can be found in Appendix B.3. The significance of Theorem 4.2 lies in bridging the sparsification technique and Laplacian smoothing with specific precision bound for the first time to the best of our knowledge. Its implication is that, the adaptive sparsification by UNIFEWS for a single layer qualifies as a graph spectral sparsifier bounded by c. Its pivotal parameter, i.e., the sparsification threshold,
Edge Pruning for Single Layer. In order to perform prun- ing on entry T[M T(u, v). the diffusion matrix T can be utilized to record the pruning information, which is exactly the con- cept of graph sparsification. Given a universal magnitude threshold 6,, zeroing out entries |r (u, v]]l < 8g is equivalent
4

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
and its approximation bound can be determined once given the sparsity 7a-- A sparsity closer to 1 results in larger threshold value as well as a loose error guarantee.
additional matrix-wise overhead. For multi-dimensional fea- ture matrix, the pruning function Equation (5) is performed by replacing |p(e]| with the specific norm || across feature dimensions. Note that we adopt skip connections to each layer in the algorithm by initializing P(++)) explicitly with the value in the previous hop, in order to preserve at least one meaningful value for each node embedding in case all connected edges are pruned.
4.2. UNIFEWS for Graph Propagation
Thanks to the adaptive property of the entry-wise pruning scheme, we able to further perform fine-grained and gradual sparsification across propagation layers. Intuitively, a message deemed of minor significance in the current prop- agation is unlikely to propagate further and influence more distant nodes in subsequent layers. UNIFEWS hence offers progressively increasing sparsity throughout GNN layers.
Approximation Bound. From the theoretical perspective, the error introduced by multi-hop propagation is more com- plicated than the single-layer case in Theorem 4.2, it is composed of both the diffusion and embedding values in approximation. By exploiting the GNN graph smoothing process in Definition 3.1, we show that:
As depicted in Figure 2(c), UNIFEWS iteratively applies sparsification to each layer, and the pruned diffusion ma- trix Tay is inherited the next layer for further edge re- moval. Denote the edge set corresponding to T(t) as Eiy, there is En S EQ- .... S εo) S E. which indi- cates diminishing number of operations for deeper layers. Consequently, Equation (4) is modified as the following to represent entry-level diffusion on the sparsified graph:
P P(+ = P - PP +0(0)-0(()---0) Pl)l-
Therefore, as long the sparsification satisfies Theorem 4.2 for each hop, the whole process of pruning and accumulating the sparsified graph across multiple hops can be regarded as the approximate smoothing in Lemma 3.3, as stated in the following proposition and detailed in Appendix B.4:
Pa+1)lu = Σ
Tollu,e e] Panlo] = Σ Taylu, v). (7)
(M)
Proposition 4.3 (Progressive UNIFEWS for graph prop- agation). For L-hop graph propagation under Algo- rithm 1, if the final sparsifier satisfies c-similarity, then the overall process is an e-approximation to the original graph smoothing problem.
where the neighborhood composed by remaining connec- tions is (w) {v (u, E E
We illustrate the application of UNIFEWS decoupled graph propagation in Algorithm 1 as highlighted compo- nents. Note that the nested loops starting from Line 5 are identical to the canonical graph propagation conducted by sparse-dense matrix multiplication in common GNNs. Com- pared to the normal propagation Line 11, it refrains the value update and prunes the corresponding edge for insignificant entries in Line 9. Hence, UNIFEWS can be implemented into the GNN computation to enhance efficiency without
Moreover, the feature transformation stage in decoupled GNNs is feasible to the weight pruning described in the following section, which is similar to classical irregular pruning with magnitude- based based thresholds for MLP networks (Han et al., 2015; Srinivas & Babu, 2015).
Algorithm 2: UNIFEWS on Iterative GNN
Algorithm 1: UNIFEWS on Decoupled Propagation
Input: Graph g = E). diffusion Tay, attribute X, net- work layer L. graph sparsification threshold 5g, weight sparsification threshold ow
Input: Graph 9 = E), diffusion Ti), attribute X, propa- gation hop L, graph sparsification threshold &a Output: Approximate embedding P(L.)
Output: Approximate representation H(L)
A [o) t- X, & E
Poo + X, &
2 for 1= 0 L - 1 do
2 for - to do
H(111) 0, P()
H()
3
P(+1) + P())
Ei + EQ- T(gy= T()
4 Acquire sparsified P(oyEun: Puy as in Algorithm I
5
for all u E do
[matrix op]
for i +- 1 to do for + to f and W (() [.. +
[matrix op]
6
(w)(w) + {u| (u, m) E En v # #
6
do
7
for all v E do
if Wonll i|| 6w/ P Poll:iI then
if (iTa w|l 6 [e]] then
8
W Wi 5
fm + En) \ {(u, v)}. T [4. wj +
else
H Hatplud + Hannb + Wob. Pobl
10
else
Pati)lu+ <- Putzylu]+ Faylu, (u, u] P(ylo]]
11
((+1) + a (A(4))
12
return P(r)
12 return H H(I)
5

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
4.3. UNIFEWS for Iterative Update
weight sparsification processes. Hence, the unified prun- ing produces advantageous approximation of the learned representations across GNN layers, which completes our framework for characterizing the approximation bound of UNIFEWS for general GNN schemes by examining the graph smoothing optimization throughout model learning.
Compared to decoupled designs, graph propagation and fea- ture transformation in iterative GNN models are tightly inte- grated in each layer. Traditionally, this poses a challenge to GNN sparsification methods depicted in Figure 2(b), as spe- cialized schemes are necessary for simultancously modify- ing the two components without impairing the performance. On the contrary, our UNIFEWS approach takes advantage of this architecture for jointly sparsifying the model towards a win-win situation in graph learning.
Complexity Analysis. As shown in Algorithms I and 2, entry-level operations can be naturally inserted into the computation without additional overhead. For graph prop- agation, when the graph sparsity is The = qa/m, where da is the number of removed edges, the computation complex- ity for propagation in each layer is reduced from ((m) to ( - Ta)m)) )m). In particular, for iterative models, this applies to both time and memory overhead. For weight prun- ing regarding matrices P, .H& E R and W E R let the pruning ratio of weight matrix be 7u-- The sparsification scheme at least reduces complexity to O ),)nn.f)) The favorable merit of joint graph and weight sparsification by UNIFEWS is that, both the propagation result P and the weight multiplication product H enjoy sparsity from the previous input alternatively. In fact, as proven by (Zhang et al., 2023b), the scale of reduced computational operation can be advanced to (1 n,,)² for certain distribution.
The sparsification of iterative UNIFEWS for the entire message-passingg process is presented in Algorithm 2, where the difference from the common scheme is also highlighted. Similarly, although presented as nested loops in the algorithm, the multiplication and sparsification are implemented as matrix operations. Its graph propagation stage identical to Algorithm 1, except that the embed- ding P() is initialized by the previous representation H() Mcanwhile, sparsification for weights is relatively straight- forward compared to graph edges, since weight matrices are structured and their approximation is well-studied as network pruning (Han et al., 2015; Srinivas & Babu, 2015; Deng et al., 2020a). Given the embedding of the current layer Pwy. we similarly rewrite the iterative GNN update as:
5. Experimental Evaluation
Ha-n)iii]) - (I Wob.i Prl...)).
(8)
Datasets and Metries. In the main experiment, we adopt 6 representative datasets including 3 small-scale (Kipf & Welling, 2017) and 3 large-scale ones (Hu et al., 2020) con- sidering the applicability of evaluated methods. We mainly focus on the transductive node classification task. The ef- ficiency is comprehensively assessed by computation time and peating-ppint operations (FL.Oss, and 1FT.Pss R 2MACs. More datasets are evaluated in Appendix C.I.
where H (141))e,d) denotes the i-th column vector of all nodes in H 1(++)), and the weight entry Wiyli, i] symbol- izes the neuron mapping the j-th embedding feature to the i-th representation feature. UNIFEWS sparsification on the weight matrix can thus be presented in the entry-wise man- ner following weight threshold بw:
Wbi = thrsg, iI) W]. 5% =
(9)
We em- ploy GCN (Kipf & Welling, 2017) and GAT (Brody et al., 2022) as iterative backbone GNNs, since they are com- monly used for sparsification. Four graph and joint com- pression methods are considered baselines: GLT (Chen et al., 2021), GEBT (You et al., 2022), CGP (Liu al., 2023a), and DSpar (Liu et al., 2023b). Additionally, we examine the random entry-wise scheme RAN by randomly removing entries according to the given sparsity. Back- bones of decoupled models are SGC (Wu et al., 2019) and APPNP (Klicpera et al., 2019). Two baselines with propaga- tion personalization techniques, NDLS (Zhang et al., 2021) and NIGCN (Huang al., 2023), used, while both are only available for SGC.
Backbone Models and Sparsification Methods.
Approximation Bound. To derive the precision bound for UNIFEWS on iterative models, we investigate the difference of layer representation:
Ha+1) H(+1) (Pn) P (w) -W W
The first term is similar to graph propagation in Proposi- tion 4.3, while the second term can be bounded by the weight pruning scheme regarding & Hence, we are able to show that the representation under layer-progressive UNIFEWS for iterative networks containing both graph and weight operations satisfies the following proposition:
Proposition 4.4 (Progressive UNIFEWS for iterative up- date). For an L-round iterative update under Algorithm 2, the approximation error on output (1.) H(,)le is
Hyperparameters. We commonly utilize graph normal- ization r = 0.5, model layer depth L, = 2, and layer width früdden = 512. For decoupled models, the number of prop- agation hops is 20. We employ full-batch and mini-batch training for iterative and decoupled methods, respectively. The total number of training epochs is 200, including pre-
bounded by O(e H(L)l lI ).))
The detailed interpretation of Proposition 4.4 is discussed in Appendix B.5. In brief, the approximation of layer repre-
sentation is jointly bounded by factors depicting graph and
6

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Raw
Randon
GLT
GEBT
OGP
DSpor
Unitons [Ouz)
+CN+cora
GAT+cora
+AT+cora
90-
50
90
Anouany (0%
85
85-
80-
80-
-00
80-
215
90 100
100
25
50
90
100
(a) GCN Edge Pruning
(b) GCN Weight Pruning
(c) GAT Edge Pruning
(d) GAT Weight Pruning
Figure 3: Accuracy of iterative models over cora, while more results are in Figure 10. Columns of "Edge" and "Weight Sparsity" present the average results of models with solely edge and weight sparsification, respectively.
training or fine-tuning process in applicable methods. The batch size is 512 for small datasets and 16384 for large ones.
APPNP 800 NDAS SCC+NICCN
S0C=Undio APPSP+Unifeee
Decoupletcora
Decouple-citssee
80
We tune the edge and weight sparsity of evaluated models across their entire available ranges.
Acneny (R)
5.1. Performance Comparison
We first separately apply only one part of sparsification, i.e., either edge or weight pruning, for better comparison. Figure 3 presents accuracy results of iterative backbones and compression methods over representative datasets. GEBT encounters out of memory error pubmed. For larger graphs, most of the iterative baselines suffer from the out of memory error due to the expense of trainable adjacency matrix design and full-graph training process.
100
Fily Spanitt (50)
Rdy Spunity (9)
(a) Edge Pruning on cora
(b) Edge Pruning on citeseer
Figure 4: Accuracy of decoupled models over cora and citeseer. UNIFEWS is employed with solely edge removal.
graph edges without sacrificing efficacy, thanks to its fine- grained and adaptive scheme.
Edge Sparsification. For the iterative architecture in Fig- ures 3(a) and 3(c), UNIFEWS outperforms state-of-the-ar graph and joint compression approaches in most backbone- dataset combinations. Typically, for relatively small ratios Me < 80%, models with UNIFEWS pruning achieve compa- rable or exceeding accuracy, aligning with our approxima- tion analysis. For higher sparsity, UNIFEWS benefits from the skip connection design, which carries essential infor- mation of node identity and therefore retains accuracy no worse than the trivial transformation. On the contrary, most of the competitors experience significant accuracy drop on one or more datasets. CGP and DSpar exhibit poor utility on the GAT backbone since its variable connections are more vulnerable to removal. Additionally, the comparison with random sparsification indicates that, the entry-wise scheme is particularly effective for small ratios, as the randomized pruning even surpasses dedicated methods for some circum- stances. For high edge sparsity, the UNIFEWS preservation of dominant edges and identity mapping critical accu- racy, which validates the advantage of our design.
Weight Sparsification. Figures 3(b) and 3(d) display the efficacy of network pruning. For all combinations of mod- els and graphs, UNIFEWS achieves top-tier accuracy with a wide range of weight sparsity. For small ratios, the model produces up to 3% accuracy gain over the bare GNN, resem- bling the benefit of neural network compression (Hoefler et al., 2021). Most evaluated baselines also maintain low error rate compared to their performance in graph pruning, indicating that the GNN weights are relatively redundant and are suitable for substantial compression. Thanks to the redundancy in GNN architecture, baselines including GEBT and CGP present strong performance in certain cases com- pared to edge sparsification. Random removal fails for high weight sparsity, which implies that the magnitude- scheme is the key to maintain model effectiveness.
Joint Sparsification. For unified pruning on graph edges and network weights, accuracy comparison is provided by Figure 5 with applicable methods. It is noticeable that UNIfEWS retains comparable or better accuracy than the backbone GCN with up to 3% improvement. Most base- line methods only obtain suboptimal accuracy especially for weight pruning, which is affected by their comparatively poor graph sparsification. While GEBT mostly retains ef- feetiveness on cora, it is highly limited by the specific archi- tecture and high training overhead. The evaluation further
Similarly, for decoupled propagation in Figure 4, UNIFEWS is able to preserve remarkable accuracy and outperform per- sonalized propagation methods. On citeseer, it raises SGC accuracy by 2% through mitigating the omoossmng is- sue. We hence conclude that, compared to heuristic prun- ing schemes, UNIFEWS successfully removes unimportant
7

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Wegght Theshold 6 6 Am64
Wesgit Thrshold d. Am00
Baw
Random
GLT
GEBT
DGP
Unilow (Ouns
A-000
4,00
Aym12
4,-00
4-122
GCN cora
GCN cora
20
Pooz
MAC+ (G)
Otler
Aucures (3)
85-
Aumuary (%)
1.0
0,6
75
0.0
00
1.2
00 1
d0 14 69
12
00 dn uu to ou ED
Diltikan Thrshold &
Difirtion Trrsboli K/KC0
00
(00
25
30
03 100
Edge Spanity (35)
Weggtt Spunsty (9)
(a) GCN on arxiv
(b) GAT on arxiv
(a) Edge Pruning, ni 30% (b) Weight Pruning, na 30%
Wiele Thnslabl 4
Wengi Timsdell
6,-36
A-005 4,-00
Am00
A,-0,
Figure 5: Accuracy of joint sparsification with varying edge and weight ratios, while fixing the other at 30%.
Php
MACa (0)
200-
highlights the advantage of UNIFEWS in considering the two GNN operation stages in unified manner.
230-
00 122
1.2
5.2. Efficiency Analysis
Diftasion Thacheld AUXx10-))
Difueion Tusboli 6xX:0"")
(c) SGC on arxiv
(d) SGC on products
FLOPs. As graph computation is the primary bottleneck for large-scale tasks, we particularly study the efficiency improvement utilizing decoupled models in Table 1. Eval- uation implies that, UNIFEWS is effective in producing op- erational reduction proportional to the sparsity, i.e., saving 50% computation FLOPs. It also achieves higher compres- sion such as for APPNP over products, by recognizing more unnecessary edges than required. Contrarily, NDLS suf- fers from out of memory eπror on large datasets due to its complex calculation and implementation, while NIGCN does not guarantee decreased computation because of its expansionary propagation design. Table 1 also presents the transformation FLOPs for reference, where the sparsified embedding of UNIFEWS also benefits the downstream com- putation. We remark that, although the FLOPs value for transformation stage appears be on the same level with propagation, in practice it can be efficiently processed uti- lizing parallel computation on devices such as GPU (Liu et al., 2020; Peng et al., 2022). Hence the GNN scalability bottleneck, especially on large datasets, is still the graph propagation. In this context, the ability of UNIFEWS in
Figure 6: Propagation and transformation FLOPs. Iterative
models: (a) GCN and (b) GAT over arxiv. Decoupled
models: SGC over (c) arxiv and (d) products.
reducing propagation operations is of unique importance.
Runtime. Within each method in Table 1, the propagation time is correlated with its FLOPs, and escalates rapidly with the data size due to the nature of graph operations. Compar- ison across methods demonstrates that UNIFEWS excels in efficiently conducting graph propagation with regard to both FL TTPSs and execution time. It realizes significant accelera- tion on large graphs by favorably reducing the graph scale across all layers, which benefits the system workload such as better entry-level access. The papers 100m result highlights the superiority of UNIFEWS with 85- 100x improvement over the backbone and 9x speed-up over NIGCN.
Operation Breakdown. To specifically evaluate the effi- ciency enhancement, in Figure 6, we separately assess the FLOPs related to graph propagation and network transfor- mation for different backbone models and datasets under
Table 1: Results nf. = 50% graph sparsification on decoupled models. "Time" denotes propagation time (in seconds), while "FLOPs" separately presents the operations (in GMACs) for propagation and transformation all nodes. "Improvement" is the comparison between UNIFEWS and the backbone model, where improved accuracy is marked in bold fonts.
Dataset
cora
citeseer
pubmed
arxiv 169, 313
products
papers100m
Nodes m
2, 485
3, 327 9, 228
19, 717
2, 400 608 123, 718, 024
111, 05,,099,9000 956 3. 228 124, 712
Edges
12, 623
88, 648
2,315, 598
Metric
Acc Time
FLOPs
Acc Time
FLOPs
Aze
Time
FLOPs
Ace
Time
FLOPS
Are
Time
FLOPs
Ace
Time
FLOPS
SGC
85.8 0.13 0.36+2.2
67.7 0.44 0.68+2.8
83.0 0.36 0.8942.3
68.8 3.9 5.9+15.0
79.1 289.6 247.4444.44
63.3 19212 17.74253.6
*NDLS
80.3 1362
0.1942.7
64.7 1940
0,33+4.3
77.0 4717
0.4242.0
(0OM)
(OOM)
(OOM)
+NIGCN
84,2 0.45 0.22+3.0
70.4
0.47
0.28+2.1
85.0
9.2
0.44+2.0
63.7
87.6
15.6+14.7
77.9
1026
137.2+182.0
53.7 1770
110.74238.6
+UNIFEWS
86,0 0.10 0,18+1.2
73,0
0.26
0.35+1.7
83.0
0.24
0.4742.0
69.4 1.5
3.0+
78.5
203.1
124.0+186.9
63.1 192.4
5,3+143.8
Improvement
0.2 1.3x 2.0x, 1.9x
5.3
1.7x
2.0x. 1.7x
0.0 1.5x
1.9x, 1.2x
0.6 2.6x 2.0x.
1.1x
-0.5
1.4x
2.0x. 2.3x
-0.2
99.8x
3.3x. 188x
APPNP 86.2 0.15 0,36+2.2
71.6
0.43
0.68+2.8
187.6
0.33
0.8942.3
64.8 2.6 5.9420.9
72.5
248.5
247 442994 4 60.9
15305
17.74247.7
+UNIFEWS 86.5 0.08 0,18+1.8
73.7
0.21
0,31+2.3
88.0
0.26 0.43+1.8
65.0
0.93
3.0+15.0
76.9
58.5
31.7+186.9
62,8
178.5
8.94241.8
Improvement 0.4 1.8x 2.0x, 1.2x
2.1 2.0x 2.2x.
1.2x
0.4 1.3x 2.1x. 1.3x
0.2 2.8x 1.9x, 1.4x
4.5
4.2x
7.8x. 1.4x
1.9 85.7x
2.0x. 1.0x
8

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
by
Auc
Edac Spandis
Wkizld Syanky J,
Reighe RelgheDDgeih Dogely
Teleine
Weight 6,
Winght 6-
Spunsy
Sponty
1.2
0.0
Difrodon Thrndekl
Delform Thoshald
RP Dilatio Throbold
10
(a) Message T(O)
(b) Representation (a)
Diltuio Thesheld s.
(a) GCN on cora
(b) GAT on cora
Entry sparsity under joint sparsification, evalu- ated by matrix norm relative to the unpruned one on a 2- layer GCN over cora. (a) Edge-wise message [[) [To)ll
Figure 7:
Spuniity (90
Spanity (9)
(b) Node-wise representation /|)
UNIFEWS sparsification. For better presentation, model width is set to 64 in this experiment. Figures 6(a) and 6(b) imply that the majority of computational overhead of iter- alive models is network transformation, even on graphs as large as arxiv. Consequently, weight compression essen- tial for reducing GNN operations.
10
10
Diluttn Thredold
Diftuion Theshold &
(c) SGC on cora
(d) APPNP on cora
Figure 8: Sensitivity of joint sparsification thresholds on four models over cora. We respectively set the weight ratio & to 0 and 0.5, then evaluate the accuracy, edge sparsity, and weight sparsity of the model. Note that the x-axis representing diffusion threshold is on logarithmic scale.
On the other hand, graph propagation becomes the bottle- neck in decoupled designs, and is increasingly significant on graphs with greater scales. This is because of the larger number of propagation hops L = 20 for these structures. In this case, UNIFEWS is effective in saving computational cost by simplifying the propagation and bypassing unnec- essary operations, with over 20x and 5x joint reduction on arxiv and products, respectively. We also discover the benefit of joint pruning that higher threshold results in smaller FLOPs of both operations in Figures 6(C) and 6(d), which signifies the win-win situation brought by increased sparsity. By combining these two sparsifications, we sum- marize that the unified scheme of UNIFEWS is capable of mitigating the computational overhead for both propagation- and transformation-heet heavy tasks.
sparsity nh 95%. The experiment reveals that, the rela- tion between edge sparsity and adjacency threshold aligns with Theorem 4.2, and decoupled models typically require a larger range of threshold to traverse the sparsity range, which is because of the wider distribution of their entry values throughout the deeper propagation. Interestingly, the weight sparsity when dw = 0.5 also increases under high edge pruning ratios. The pattern is also observed in the reverse case. We deduce that the reciprocal enhancement in graph and model sparsity is brought by the unified sparsifi- cation of UNIFEWS, which conforms to our analysis as well as previous studies (Zhang et al., 2023b).
5.3. Parameter Discussion
6. Conclusion
Sparsity. Figure 7 displays the relative density of the edge message and node representation matrices, respectively. It can be observed that the entry sparsity is enhanced with the increase of both two pruning ratios, signifying our the- oretical analysis that UNIFEWS not only directly shrinks edges and weights, but promotes the sparsity of the product matrix as well. It also supports our claim that UNIFEWS superior in employing dual sparsification where the two stages benefit each other alternatively and enjoy a win-win situation brought by the increased sparsity.
In this work, we present UNIFEWS, an entry-wise GNN sparsification with unified framework for graph edges and model weights. By bridging spectral graph smoothing and GNN sparsification, we showcase in theory that the layer- progressive UNIFEWS provides an effective approximation on the graph learning process with a close optimization objective, which is favorable for multi-layer GNN updates in both iterative and decoupled architectures. Comprehen- sive experiments underscore the superiority of UNIFEWS in terms of efficacy and efficiency, including comparable or improved accuracy, 90 - 95% operational reduction, and up to 100x faster computation.
Joint Sparsification Thresholds. The thresholds control- ling diffusion and weight sparsification are pivotal to UNIFEWS compression, affecting both efficacy and effi- ciency of the produced model. Figure& 8 presents the changes of inference accuracy and dual sparsity of GNN models un- der graph and joint sparsification with varying adjacency thresholds 5a. Accuracy in the plot follows the conclusion in previous evaluation, that it only degrades above extreme
Limitation. One potential limitation lies in the considera- tion of graph heterophily, as messages with large magnitudes may not be beneficial to model prediction. In this case, the graph smoothing objective in Definition 3.1 needs to be refined; consequently, the sparsification strategy should be adjusted.

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Acknowledgements
Chen, T., Sui, Y., Chen, X., Zhang, A., and Wang. Z. A unified lottery ticket hypothesis for graph neural networks. In 38th International Conference Machine Learning, volume 139, pp. 1695-1706. PMLR, 2021.
This research is supported by Singapore MOE AcRF Tier- 2 Grant (T2EP20122-00033 and NTU-NAP startup grant (022029-00001). Ningyi Liao is supported by the Joint NTU-WeBank Research Centre on FinTeech, Nanyang Tech- nological University, Singapore.
Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster-gen gent: An efficient algorithm for training deep and large graph convolutional networks. In Proceed- ings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Pp. 257-266, Anchorage AK USA, July 2019. ACM
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.
Clauset, A., Shalizi, C. R., and Newman, M. J. Power- law distributions in empirical data. SIAM Review, 51()): 661-703, 2009.
References
Deng, B. L., Li, G., Han, S., Shi, L.., and Xie, Y. Model com- pression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108 (4):485-532, April 2020a.
Bahri, M., Bahl, G., and Zafeiriou, S. Binary graph neural
networks. In 2021 JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9492-9501, 2021.
Batson, J., Spielman, D. A., Srivastava, N., and Teng, S.-H. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8):77-94, August 2013.
Deng. C., Zhao, Z., Wang, Y., Zhang, Z., and Feng, Z. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. In 8th International Con- ference on Learning Representations, February 2020b.
Bojchevski, A. and Günnemann, S. Deep gaussian em- bedding of graphs: Unsupervised inductive learning via ranking. In 6th International Conference on Learning Representations, 2018.
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Con- textual stochastic block models. In 31st Advances in Neural Information Processing Systems, 2018.
Brody, S., Alon, U., and Yahav, E. How attentive are graph attention networks? In 10th International Conference on Learning Representations, January 2022.
Ding, H., Wei, Z.., and Ye, Large-scale spectral graph neural networks via laplacian sparsification. In 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2025.
Cai, C., Wang, D., and Wang, Y. Graph coarsening with neural networks. In 9th International Conference on Learning Representations, February 2021.
Ding, M., Kong, K., Li, J., Zhu, C., Dickerson, J. P., Huang, F. and Goldstein, T. VQ-GNN: A universal framework to scale up graph neural networks using vector quantiza- tion. In 34th Advances in Neural Information Processing Systems, 2021.
Calandriello, D., Koutis, I., Lazaric, A., and Valko, M. Im- proved large-scale graph learning through ridge spectral sparsification. In 35th International Conference on Ma- chine Learning, volume 80, Stockholm, Sweden, 2018. PMLR.
Fang, T., Xiao, Z., Wang, C., Xu, J., Yang, X., and Yang, Y. Dropmessage: Unifying random dropping for graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):4267-4275. June 2023.
Charalambides, N. and Hero, A. O. Graph sparsification by approximate matrix multiplication. In 2023 IEEE Statistical Signal Processing Workshop (SSP), pp. 180- 184, Hanoi, Vietnam, July 2023. IEEE.
Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th Interna- tional Conference on Learning Representations, pp. 1-42, 2019.
Chen, J., Ma. T., and Xiao, C. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representa- fions, pp. 1-15, 2018
Gasteiger, J., Weißenberger, S., and Günnemann, S. Dif- fusion improves graph learning. In 32nd Advances in Neural Information Processing Systems, 2019.
Chen, M., Wei, 7., Ding, B., Li, Y., Yuan, Y., Du, X., and Wen, J. R. Scalable graph neural networks via bidirec- tional propagation. In 33rd Advances in Neural Informa- tion Processing Systems, volume 2200-Deemm, pp. 1-14, 2020.
Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning in large attributed graphs. In 30th Advances in Neural Information Processing Systems, pp. 1-11, Long Beach, CA, USA, October 2017.
10

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Han, S., Pool, J., Tran, J., and Dally, J. Learning both weights and connections for efficient neural networks. In 28th Advances in Neural Information Processing Systems, pp. 1135-11444 1143, June 2015.
Lai, K.-H., Zha, D., Zhou, K., and Hu, X. Policy-gnn: Aggregation optimization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 461-471, Virtual Event CA USA, August 2020. ACM
Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., and Peste, A. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241), January 2021.
Li, D., Yang. T., Du, L.,, He, Z., and Jiang, L. Adaptivegen: Efficient gen through adaptively sparsifying graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3206- 3210, Virtual Event Queensland Australia, October 2021. ACM.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., Leskovec, J., Barzilay, R., Battaglia, P., Ben- gio, Y., Bronstein, M., Günnemann, S., Hamilton, W., Jaakkola, T., Jegelka, S., Nickel, M., Re, C., Song. L., Tang, J., Welling, M., and Zemel, R. Open graph bench- mark: Datasets for machine learning on graphs. In 33rd Advances in Neural Information Processing Systems, vol- 2020-Decem, pp. 1 1-34, 2020.
Li, J., Zhang, T., Tian, H., Jin, S., Fardad, M., and Za- farani, R. Graph sparsification with graph convolutional networks. International Journal of Data Science and Analytics, 13(1):33-46, January 2022.
Li, Q. Han, Z., and Wu, X. M. Deeper insights into graph convolutional networks for semi semi-supervised learning. Pro- ceedings of the AAAI Conference on Artificial Intelli- gence, 32) 2018
Huang, K., Tang, J., Liu, J., Yang. R., and Xiao, X. Node- wise diffusion for scalable graph learning. In Proceedings of the ACM Web Conference 2023, pp. 1723-1733, Austin TX USA, April 2023, ACM.
Liao, N., Mo, D.,, Luo, S., Li, X., and Yin, P. SCARA: Scalable graph neural networks with feature-oriented op- timization. Proceedings of the VLDB Endowment, 15(11): 3240-3248, 2022.
Huang, W., Zhang, T., Rong, Y., and Huang, J. Adaptive sampling towards fast graph representation learning. In 31st Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018.
Huang, Z., Zhang, S., Xi, C., Liu, T., and Zhou, M. Scal- ing up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery& & Data Mining, volume I, pp. 675- 684, Virtual Event Singapore, August 2021. ACM.
Liao, N., Luo, S., Li, X., and Shi, J. LD?: Scalable het- erophilous graph neural network with decoupled embed- dings. In Advances in Neural Information Processing Sys- tems, volume 36, pp. 10197-10209. Curran Associates, Inc., Dec 2023a.
Hui, B., Yan, D., Ma, X., and Ku, W.S. Rethinking graph lottery tickets: Graph sparsity matters. In 1 11th Interna- tional Conference on Learning Representations, 2023.
Liao, N., Mo, D., Luo, S., Li, X., and Yin, P. Scalable decoupling graph neural network with feature-oriented optimization. The VLDB Journal, December 2023b.
Jin, W., Zhao, L., Zhang, S., Liu, Y., Tang, J., and Shah, N. Graph condensation for graph neural networks. In 10th International Conference on Learning Representations, September 2022.
Liao, N., Luo, S., Xiao, X., and Cheng, R. Advances in designing scalable graph neural networks: The perspec- tive of graph data management. In Companion of the 2025 International Conference on Management of Data, Berlin, Germany, 2025. ACM.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, pp. 1-14, 2017.
Liao, N., Liu, H. L., Zhu, Z., Luo, S., and Lakshmanan, L. V. A comprehensive benchmark on spectral GNNs: The impact on efficiency, memory, and effectiveness. In 2026 ACM SIGMOD International Conference on Management of Data. ACM, 2026.
Klicpera, J., Bojehevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, pp. 2019.
Kosman, F., Oren, J., and Di Castro, D. Lsp: Acceleration of graph neural networks via locality sensitive pruning of graphs. In 2022 IEEE International Conference on Data Mining Workshops (ICDMW). pp. 690-697, Orlando, FL, USA, November 2022, IEFE.
Liu, C., Ma, X., Zhan, Y., Ding, L., Tao, D., Du, B., Hu, W., and Mandic, D. P. Comprchensive graph gradual pruning for sparse training in graph neural networks. JEEE Trans- actions on Neural Networks and Learning Systems, pp. 1-15, 2023a.

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Liu, H., Lu, S., Chen, X., and He, B. G3: When graph neural networks meet parallel graph processing systems gpus. Proceedings of the VLDB Endowment, 13(12); 2813-2816, August 2020.
Rong, Y., Huang, W., Xu, T., and Huang. J. Dropedge:
Towards deep graph convolutional networks node clas- sification. In 8th International Conference on Learning Representations, March 2020.
Liu, H., Liao, N., and Luo. S. SIGMA: An efficient het- erophilous graph neural network with fast global aggre- gation. In JEEE 41st International Conference on Data Engineering, pp. 1924 1924-1937, 2025.
Sadhanala, V., Wang. Y.-X., and Tibshirani, R. Graph sparsification approaches for laplacian smoothing. In 19th International Conference on Artificial Intelligence and Statistics, pp. 1250-12555 Cadiz, Spain, May 2016. PMLR.
Liu, X., Yan, M., Deng, L., Li, G., Ye, X., Fan, D., Pan, S., and Xie, Y. Survey on graph neural network acceleration: An algorithmic perspective. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, April 2022.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. In 31st Advances in Neural Information Processing Systems Relational Representation Learning Workshop, Montréal, Canada, June 2019.
Liu, Y., Safavi, T., Dighe, A., and Koutra, D. Graph sum- marization methods and applications: A survey. ACM Computing Surveys, (1): May 2019.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6): 1913-1926, January 2011.
Liu, Z., Zhou, K., Jiang, Z., Li. L.,, Chen, R., Choi, S.-H., and Hu, X. Dspar: An embarrassingly simple strategy for efficient gnn training and inference via degree-based spar- sification. Trunsactions Machine Learning Research, July 2023b.
Spinelli, I., Scardapane, S., and Uncini, A. Adaptive propa- gation graph convolutional network. IEEE Transactions Neural Networks and Learning Systems, 32(10))4755- 4760, October 2021.
Ma, Y., Liu, X., Zhao, T., Liu, Y., Tang, J., and Shah, N. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1202-1211, Virtual Event Queensland Australia, Oc- tober 2021. ACM.
Srinivas, S. and Babu, V. Data-free parameter pruning for deep neural networks. In Procedings of the British Ma- chine Vision Conference 2015, pp. 31.1-31.12, Swansea, 2015. British Machine Vision Association.
Srinivasa, R. S., Xiao, C., Glass, L., Romberg. J., and Sun, J. Fast graph attention networks using effective resistance based graph sparsification, October 2020.
Maekawa, S., Noda, K., Sasaki, Y., and Onizuka, M. Beyond real-world benchmark datasets: An empirical study of node classification with gnns. In 35th Advances in Neural Information Processing Systems, 2022.
Sui, Y., Wang, X., Chen, T., He, X., and Chua, T.-S. In- ductive lottery ticket leamiing for graph neural networks. Journal of Computer Science and Technology, 39(6): 1223 1237, 2024.
Mackawa, S., Sasaki, Y., Fletcher, G., and Onizuka, M. GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems, 115:102195 2023.
Veličković, P., Casanova, A., Liò, P., Cucurull, G., Romero, A., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representations, pp. 1-12, 2018
Miao, X. Zhang, W., Shao, Y., Cui, B., Chen, L., Zhang, C., and Jiang, J. Lasagne: A multi-layer graph convolutional network framework via node-aware deep architecture. IEEE Transactions on Knowledge and Data Engineering,
Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018
pp. 1-1, 2021.
Ming, C., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In 37th Interna- tional Conference on Machine Learning, volume 1 119, pp- 1703-1713. PMLR, 2020.
Wang. H., He, M., Wei, Z., Wang, S., Yuan, Y., Du, X., and Wen, J.-R. Approximate graph propagation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1686-1696. Virtual Event Singapore, August 2021a. ACM.
Peng. J., Chen, Z., Shao, Y., Shen, Y., Chen, L.,, and Cao, full-
J. Sancus: Staleness-aware communication-avoidee graph decentralized training in large-scale graph neural networks. Proceedings of the VLDB Endowment, 15(9): 1937-1950, 2022.
Wang. J., Wang, Y., Yang, Z., Yang, L., and Guo, Y. Bi-gen: Binary graph convolutional network. In 202 IEEE/CVE
12

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Conference on Compuler Vision and Puttern Recognition, pp. 1561-1570, 2021b.
Zhang, W., Yin, Z., Sheng, Z., Li, Y., Ouyang, W., Li, X., Tao, Y., Yang, Z., and Cui, B. Graph attention multi-layer perceptron. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4570- Washington DC USA, August 2022. ACM.
Wang, K., Li, G., Wang. S., Zhang, G., Wang, K., You, Y., Peng, X., Liang, Y., and Wang, Y. The snowflake hypoth- esis: Training deep gnn with one node one receptive field, 2023a.
Zheng, C., Zong, B., Cheng, W. Song, D., Ni, J., Yu, W., Chen, H., and Wang, W. Robust graph represen- tation learning via neural sparsification. In 37th Interna- tional Conference on Machine Learning, volume 119, pp. 1 11458-11468. PMLR, 2020.
Wang, K., Liang, Y., Wang. P., Wang. X., Gu, P., Fang, J., and Wang, Y. Searching lottery tickets in graph neu- ral networks: A dual perspective. In / Ith International Conference on Learning Representations, 2023b.
Wu, F., Zhang, T., de Souza, A. H., Fifty, C., Yu, T., and Weinberger, Q. Simplifying graph convolutional net- works. In 36th International Conference on Machine Learning, volume 2019-June, pp. 11884-11894, PMLR, 2019.
Zhou, H., Srivastava, A., Zeng, H., Kannan, R., and Prasanna, V. Accelerating large scale real-time gnn infer- ence using channel pruning. Proceedings of the VLDB Endowment, 14(9):1977-1055 2021.
Zhu, M., Wang, X., Shi, C., Ji, H., and Cui, P. Interpreting and unifynng graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pp. 1215- 1226, Ljubljana Slovenia, April 2021. ACM.
Wu, Z.,, Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P. S. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, (2(1):4-24, January 2021.
Zou, D., Hu, Z.,, Wang, Y., Jiang, S., Sun, Y., and Gu, Q. Layer-dependent importance sampling for training deep and large graph convolutional networks. In 33rd Ad- vances in Neural Information Processing Systems, 2019.
You, H., Lu, Z., Zhou, Z., Fu, Y., and Lin, Y. Early-bird gens: Graph-network co-optimization towards more efficient gen training and inference via drawing early-bird lottery tickets. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8910-8918 June 2022.
Zeng. H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. Graphsaint: Graph sampling based induc- tive learning method. In 8th International Conference Learning Representations, July 2020.
Zeng, H., Zhang, M., Xia, Y., Srivastava, A., Malevich, A., Kannan, R., Prasanna, V., Jin, L.,, and Chen, R. Decou- pling the depth and scope of graph neural networks. In 34th Advances in Neural Information Processing Systems, volume 34, pp. 19665-19679. Curran Associates, Inc., 2021.
Zhang, S., Sohrabizadeh, A., Wan, C., Huang, Z., Hu, Z.,, Wang, Y., Yingyan, Lin, Cong, J., and Sun, Y. A survey on graph neural network acceleration: Algorithms, systems, and customized hardware, June 2023a.
Zhang, S., Wang, M., Chen, P.-Y., Liu, S., Lu, S., and Liu, M. Joint edge-model sparse learning is provably efficient for graph neural networks. In / 1th International Conference on Learning Representations, 2023b.
Zhang, W. Yang, M., Sheng, Z., Li, Y., Ouyang, W., Tao, Y., Yang, Z., and Cui, B. Node dependent local smoothing for scalable graph learning. In 34th Advances in Neural Information Processing Systems, pp. 20321-20333 2021.
13

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
A. Detailed Related Works and Comparison
A.1. GNNs Simplification
Iterative Graph Sparsification. Simplification techniques mainly aim to reduce GNN pressage-passingg operations while maintaining its scheme. Consequently, these methods usually enjoy better expressiveness and generality to different model architectures. Among them, a large portion of works sparsify edge connections for accuracy improvement, typically through deleting edges. NeuralSparse (Zheng et al., 2020) and LSP (Kosman et al., 2022) drop edges based on k-nnighbor metric for each node and layer-wise local graph topology, respectively, while AdaptiveGCN (Li et al., 2021) and SGCN (Li et al., 2022) choose to implement sparsity by learnable edge features and graph adjacency.
In comparison, FastGAT (Srinivasa et al., 2020) and DSpar (Liu et al., 2023b) relate graph modification to spectral sparsification mainly as an attempt to boost efficiency. FastGAT climinates connections the GAT (Veličković al., 2018) model by calculating the Effective Resistance (Spielman & Srivastava, 2011) but at the expense of high computational time. DSpar employs a loose approximation and successfully applies to larger datasets.
Most of the simplification techniques, however, conduct graph modification in one-time and layer-agnoste manner, resulting in limited flexibility and urility under the trade-off between efficiency and efficacy.
Decoupled Propagation Personalization. To make of the model propagation and perform some studies design fine-grained optimizations on each diffusion step in node-dependent fashion to resolve GNN defects such as inefficiency (Chiang et al., 2019; Chen et al., 2020; Liu et al., 2025; Liao et al., 2026) and over-smoothing (Li et al., 2018; Liao et al., 2025). NDLS (Zhang et al., 2021) and NIGCN (Huang et al., 2023) personalize the hop number per node in the decoupled GNN design as an approach to acknowledge the local structure and mitigate over-smoothing. SCARA (Liao al., 2022; 2023b) and LD2 (Liao al., 2023a) replace the hop-base peessage-asssing with graph-oriented pushing scheme and eager termination, while Shadow-GNY (Zeng al., 2021) explicitly selects the appropriate node-wise aggregation neighborhood.
adaptive maneuvers,
Another set of works (Lai et al., 2020; Spinelli al., 2021; Miao et al., 2021; Zhang et al., 2022) achieves customized diffusion by gradually learning the hop-level importance of nodes at the price of introducing more overhead, which are less relevant to the efficient GNN computation.
Architecture Compression. The concept of GNN pruning takes the neural network architecture into account and exploits sparsification for efficiency without hindering effectiveness (Zhang et al., 2023b). (Zhou et al., 2021) consider structural channel pruning by reducing the dimension of weight matrices, while CGP (Liu et al., 2023a) appends a prune-and-regrow
Table 2: Summary of primary symbols and notations.
Notation
Description
9, V,E
Graph, node set, and edge set Neighboring node set of node u Node, edge, and feature size Number of propagation hops and network layers Graph smoothing regularization coefficient Graph smoothing gradient descent step size Graph spectral approximation rate
N(w)
n, m.
L
b
e
sa dw
Thresholds for graph and weight sparsification Numbers of removed edges and weight entries Graph sparsity and weight sparsity
Ja Tw
na: Tu
A, Ā
Self-looped and normalized adjacency matrix of graph g Raw and normalized Laplacian matrix of graph G Approximate adjacency and Laplacian matrix of graph ş Graph diffusion matrix and weight matrix Message entry corresponding to edge (u, v) Network entry corresponding to neuron (j, Node attribute matrix and feature- wise vector Embedding matrix and feature- ceature-wise wise vector of layer I Representation matrix and feature-wise vector of layer
L, L
Á, L
T, W
7 T(U,0) v]
X, x
P(o, P()
14

---

IL --l1 sup x |||||=| UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
scheme the graph structure.
A line of research refers to the lottery ticket hypothesis (Frankle & Carbin, 2019; Hui et al., 2023) in the context of graph learning in search of a smaller yet effective substructure in the network. Among these approaches, GEBT (You et al., 2022) finds the initial subnetwork with simple magnitude-bade based pruning on both adjacency and weight matrices, whilst ICPG (Sui et al., 2024) learns the importance of edges as an external task. GLT (Chen et al., 2021) and DGLT (Wang et al., 2023b) employ an alternative optimization strategy that progressively processes the graph and network components. Other compression techniques such quantization (Ding et al., 2021; Bahri et al., 2021; Wang et al., 2021b) are also investigated.
We mark the difference between our work and compression methods that the latter graph and network sparsification are loosely coupled, usually entailing a training procedure on the full-size graph and model to identify sparsification components, which prevents their application to large-scale data.
A.2. GNNs Modification
Graph Sampling. Different from simplification, modification techniques change the message-passingg scheme in GNNs, leading to new models with distinct expressiveness after modification. Sampling is common strategy for improving GNN efficiency by altering the message-passingg process. It is based on the intuition that the learning process only require a portion of data samples for each iteration. Thence, strategies on various hicrarchies are designed for retrieving useful information (Chen et al., 2018; Huang et al., 2018; Zou et al., 2019; Zeng et al., 2020; Rong et al., 2020; Fang et al., 2023). contemporary work (Ding et al., 2025) also investigates the utilization of spectral sparsification for sampling GNNs in the polynomial form, which echos with our theoretical analysis that graph sparsification process is useful in offering bounded approximation for ceessageppsssngg GNNs. We however note that the sampling approach exhibits iterative processing of the graph components and does not produce a deterministic sparsified graph. Consequently, its capability on decoupled models, which are dominant on large graphs, is relatively constrained.
Graph Coarsening. Graph coarsening describes another modification approach that reduces the graph size by contracting nodes into subsets. GraphZoom (Deng et al., 2020b), GOREN (Cai et al., 2021), and (Huang et al., 2021) explore various coarsening schemes and enhance training scalability, while GCond (Jin et al., 2022) alternatively adopts an analogous condensation strategy.
A.3. Comparative Discussion
We highlight three advantages of our UNIFEWS approach compared with above simplification and modification techniques in the context of GNN learning. Firstly, realistic graph propagation and feature transformation are conducted in an entry-centric fashion. Therefore, entry-level operations can be naturally inserted into the computation the fly by modifying the matrix multiplication operator. Secondly, different from previous node- or edge-dependent strategies, our sparsification operates on the messages being passed during propagation, which is inherently informative to foster effective pruning while retaining model expressivity. Lastly, the progressive pruning across layers is capable of promoting greater graph sparsity, thereby alleviating intrinsic drawbacks of the GNN architecture including over-smoothing and neighborhood explosion. We empirically showcase the improvement on entry sparsity in Appendix C.3.
B. Detailed Proof and Theoretical Analysis
B.1. Proof of Lemma 3.3
Proof. By using the closed-form solution p" =[I +1+cle cLi -x and the fact that A 1 B B B- A)A-1 we have:
x. p'-p'- c -0--I
(I+ ( cL) -
= (I - cL) (L+ = clI + - LL)p".
From Equation (2), we can acquire the difference between the raw and approximate Laplacian matrices based on the spectral property:
TeTLL 1) [[ (L i) S c Iwv = e,
(10)
where || |12 is the matrix spectral norm, and the supremum is achieved when 20-
The distance between p" and pr follows the consistency of spectral norm |Ax|| S || ||||||/a]] By substituting Equation (10)
15

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
and utilizing the property of spectral norm, have:
-pp -p"ll
c||(T ee)
112
|| L||2 ||p'||
1
ce cellp"|| ccllp"ll,
pp1 max
1x(1 + +cL)
1 c
where (A) denotes the i-th smallest eigenvalue of matrix A.
Given the additive nature of the graph specifier, the bound for graph smoothing problem Lemma 3.3 is dissimilar to the approximation setting with multiplicative similarity bounded by the quadratic form Occep" Lp) (Sadhanala et al., 2016 Calandriello et al., 2018), but instead correlates with the embedding vector norm p I|. This correlation arises from the bias introduced by the pruned entries in the diffusion matrix, which is associated with the embedding value.
B.2. Proof Lemma 4.1
Proof. We outline the diffusion by the general graph adjacency T A. The entry-wise difference matrix for the sparsified diffusion can be derived as Y A A = L L. Additionally, the pruned edges form the complement set Er E E. and the number of removed edges is 9a = |rl. If an edge is pruned (u, v) E &r, the entry T(u, e| = A(u, u).
For current embedding p. its product with the difference matrix Tp only correlates with entries that have been pruned. Based on the Minkowski inequality and sparsification scheme Equation (5), the L1 norm of the product vector satisfies:
\Ppl1
Σ
Σ
Alu, v
ulplu]
=
Σ
T(u, 2)
NEV
vENr(u)
WEV
rEAr(w)
Σ
Σ
T(u,
S
Σ Σ WEV
8a = qa.a.
NEV (ENT(a)
VEN((1)
Employing the relationship between vector norms given by the Cauchy-Schware inequality ||>:|| S || the difference of quadratic forms with regard to graph Laplacian can be bounded as:
p T Lp p Lp = p T Tpl s |pl|
|| S ga ||p||-
Referring to Definition 3.2, Equation (2) is equivalent to:
x
Va E R". T (L - و) I e ||0
(11)
Therefore, when the condition &, S <||p|| is met, the sparsified É is spectrally similar to with approximation rate e.
B.3. Proof Theorem 4.2
Proof. Recall in Equation (5) pruning, there is Er {u, v) |T|U, ui]l 8.). The fraction of entries below the threshold is thence expressed by the probability:
la = 111 = m. P(A[u, [u, v]
ppf]] S 5.) = 2m / P(A
- fpiv| ( (x)dæ,
where [p( represents the probability distribution function of embedding values. As A [u, e] 2 Imins we have
P(A[u, v) < fx) = =0, when x > Sa The integral upper bound changes to An j.e.
8g -0) P(A []
G. = 2m
(pl
Acknowledging the assumptions, in scale-free graphs, the distribution of nodes follows the power law P(d) = d=a, where P(d) is the fraction of nodes of degree for large values, and a a constant typically within range 2 a 3. For the normalized adjacency matrix 112 AD -1/2, its entry distribution also follows the power law as x & The
16

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
embedding value plu] N(O, )²). By substituting the distributions have:
Je Fmin
x²2
Qa
2m
exp
dr
12T022
20
0a/2mins Xmin
5n_ Fmin
80
a++1
x²
2m
err
V20
v 1TT
exp
2
dx
2m(
1
8a
a++1
xmmin
exp
x²
dr),
v 2
Imin
20²
2
c dt, (8, = / t. 1-_ c-
where
crf(2) =
dt.
V
The last term can be given by the lower incomplete Gamma function:
5
6a
exp
x² 20
dr
0
2 a-2 7
a (6a/
2
20²
Therefore,
aa = m Jer[[ =m(erf( 6a/ Fmin
V2o
T
Tmin
a-1
2
22
7
2
Panin
2
8x )²
(12)
To understand Equation (12), we discuss in two extreme cases.
Case 1. When 5a + 0, only a small number of edges are affected. Considering the Taylor Expansion with respect to 6a. there is:
Ga = ci +
2/ a-1
where CJ Taiin
Case 2. When 6g > 0 is sufficiently large, this is the main case concerned where a portion of edges pruned. The formula will be approximated by:
2 2
8a
1-a
= m 2m
V vTa+t
Emsin
or equivalently, 1/a = /a/m = Co.-a. Therefore, the relative strength of sparsification represented by the threshold 5./ /|pl and the relative sparsity 14a can be represented by each other.
Referring to Lemma 4.1, the approximation bound given as:
O (a Na) )
(13)
which corresponds to Theorem 4.2 for giving the approximation bound.
B.4. Proof Sketch of Proposition 4.3
Consider consecutively sparsifying the diffusion for each hop by Equation (7). Intuitively, as the edges are gradually removed from the original graph, there is (a,(1)) < (t)(ss) for 1 < la with the same relative threshold. If the sparsest graph T(L) satisfies Definition 3.1, then the multi-layer update is also bounded.
Recall that common GNN learning can be expressed by the graph smoothing process Definition 3.1. Such optimization problem can be iteratively solved by employing a gradient descent scheme (Ma et al., 2021), where each iteration derives the 1-th hop of graph propagation as in Equation (1):
b 0c
P(++) P()
(1 b)- bcLp(1) + bac
(14)
0p
p=P()
where b/2 is the step size and initially there is P()) = x. Equation (14) is expressive to represent various propagation operations in decoupled GNN models. For example, APPNP (Klicpera et al., 2019) can achieved by letting b = a and e = - a)/a, while SGC (Wu et al., 2019) is the edge case with only the graph regularization term.
17

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Missage
1--10
Delativn Dinaree
Relattiv Baror
1.0
022
0.9
0.1
0.85
D0C
0.2
11.4
0.8
0.7
0.2
0.1
0.5
0.5
Relative Entry Magaitude
Pidutioon Thifftsion
A./lm
Relation Diffesiom Theslokk A./lll
(a) Distribution of Entries
(b) Approximate Embedding Error
(c) Distance to Over-smoothed Embedding
Figure 9: Empirical evaluation on the SGC graph propagation and the effect of UNIFEWS on cora dataset. (a) Distribution of entries in the diffusion matrix T and the message T(o) at hop 7 = O. (b) The relative error margin || P((,) P P of approximation to the raw embedding against the strength of UNIFEWS and propagation hops. (c) The relative distance
PPu - P |||||| ||||| | to the converged emhedding against the strength of UNIFEWS and propagation hops.
Now consider the layer-wise graph sparsification under Equation (14) updates. For the initial state, there is P(o) P(0) If in the 1-th hop, Equation (5) edge sparsification is applied to the graph L, then the approximation gap is:
P(+1) P(+1) = (1 - () - P()) + be LPO - LPw))
(15)
To demonstrate that P(++) an c-approximation, we use induction by assuming P() P() Ap. 1..p////o)ll O(c). Then the bound for approximation follows:
PP++) - Pu++yll = -1 -1-11111)) b + bc be( (p(() - iA, - LP(;))
< 1(beL (1- -11-b)))ll | bcll E1l2llP + Apll
S O()) (1 + (cc + (+)) P(yl
where the inequalities follows from the property of matrix spectral norm and Equation (10). Hence, the relative error of approximate representation P(++)) is constrained by O
B.5. Proof Sketch of Proposition 4.4
To apply the approximation analysis to iterative GNNs, first extend the analysis multi-feature input matrix. When there are f' input vectors, i.e., the input matrix is X E Raxx, then the matrix form of graph Laplacian smoothing corresponding to Equation (1) is:
P = arg min P
X + tr(P LP),
(16)
where II is the matrix Frobenius norm and the closed-form solution is P' (I+cL)-IX.
Since graph operations among feature dimensions are mutually independent, conclusion from Theorem 4.2 and Proposi- tion 4.3 are still valid in their matrix forms. In iterative models, the gradient update similar to Equation (14) is instead employed to the representation matrix H (1) and derives each layer as:
Pay = (1 b) H (H +bX.
As detailed in (Ma al., 2021; Zhu et al., 2021), the update scheme above is able to describe an array of iterative GNNs. For instance, when H() X and b l/c, it yields the GCN propagation Pu) AH GAT convolution can be imitated by node-wise depending on the attention values (Veličković et al., 2018; Brody et al., 2022).
To interpret the effect of UNIFEWS sparsification, we first investigate the entry-wise graph pruning in Algorithm 2 and its outcome, i.c., the embedding matrix Pay. For simplicity, we assume the sparsification is only employed upon the (1 1)-th layer and H H()- Invoking Equation (10) and the fact that || P < || BlIF, the margin of approximate embeddings can be written as:
P -Wylle S bell H
Hol S boc
H Holee lr
Then, consider the weight pruning Equation (9). The entry-wise error is a composition of joint embedding and weight approximation:
ت م li. :] + = P -
Let My) W - Win- Recalling the iterative update scheme Equation (8), the total difference on linear transformation
18

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
H' P() W(y (1) is built up by:
H'- - Poll..)Manii
s-=1
Its first term corresponds to the embedding approximation:
AP P Pl) Polle ||W|| S bee H (1) (1 W
and the second term adheres to weight sparsification as per Equation (9):
Aw
Poll: al]| S gwow.
where qu is the number of pruned weight entries. Finally, the representation matrix in the (1 + 1) layer can be bounded by:
Ha++) Hu+nlle S to be Hoy W + loqwows
(17)
where la is the Lipschitz constant representing the non-linearity of activation function a (Virmaux & Scaman, 2018). The above equation corresponds to the one in Proposition 4.4.
The above analysis shows that UNIFEWS with unified graph and weight pruning produces good approximation of the learned representations across GNN layers, and the margin of output representations is jointly bounded by the graph sparsification rate and weight threshold ó A recent work (Zhang et al., 2023b) offers a theoretical evaluation specifically on model weight pruning throughout training iterations, under more narrow assumptions and the particular GCN scheme. We believe their results could be supplemental to our theory whose focus is the graph perspective.
C. Additional Experiments
C.1. Detailed Experiment Settings
Dataset. To showcase the scalability of UNIFEWS, we evaluate it on a range of datasets where the backbone models are applicable. Statistics of the datasets can be found in Table 3, where we follow the common settings including the graph preparing and training set splitting pipeline in these benchmarks. In the table, we incorporate self-loop edges and count undirected edges twice to better reflect the propagation overhead.
Evaluation are conducted on server with 32 Intel Xeon CPUs (2.4GHz). Nvidia A30 (24GB memory) GPU, and 512GB RAM. Specifically, most iterative sparsification baselines fail to produce results graphs larger than pubmed due to the out of memory (OOM) error. As they usually involve graph-scale trainable matrix or cache, their memory overhead is typically greater than the raw backbone model, rendering them less applicable to large graphs. In comparison, UNIFEWS performs sparsification on the fly and does not incur additional memory footprint.
Backbone Models. We select classic GNNs as our backbones, i.c., subject architectures of sparsification methods, due to the consideration that most baselines are only applicable couple of classic architectures such as GCN and GAT, In contrast, we demonstrate the generality of UNIFEWS on more backbones including GraphSAGE and GCNII. Iterative backbone models include:
GCN (Kipf& & Welling, 2017) is the representative message-passing GNN with diffusion matrix T Á across all layers.
GAT (Brody et al., 2022) learns a variable diffusion T for each layer by multi-head attention. We set the number of heads to 8 for hidden layers.
Table Statistics of graph datasets. f and N: are the numbers input attributes and label classes, respectively. Numbers in the "Split" column are percentages of nodes in vaiiiing/alidaiion/eetiggg set w.r.t. labeled nodes, respectively
Dataset
Nodes 72
Edges m
Features f
Classes N.
Split
cora (Kipf Welling, 2017)
2, 485
12, 623
1433
7
0.50/0.25/0.25
citeseer (Kipf& Welling, 2017)
3, 327
9, 228
3703
6
0.30/0.25/0.25
pubmed (Kipf & Welling, 2017)
19, 717
88, 648
500
3
0.50/0.25/0.25
physics (Shchur et al., 2019)
31, 493
195, 921
8415
5
0.50/0.25/0.25
arxiv (Hu et al., 2020)
169, 343
315,1, 598
128
40
0.54/0.18/0.29
products (Hu et al., 2020)
2, 400, 608
123. 718, 024
100
47
0.08/0.02/000
papers100ml (Hu et al., 2020)
111, 059, 956
3, 228,
124, 712
128
172
0.78/0.08/0.14
19

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
GraphSAGE (Hamilton al., 2017) performs more specialized message-passingg aggregation and is suitable for large graphs.
GCNII (Ming al., 2020) features residual connections and identity mapping. We use 32 for demonstrating the effect of sparsification deep GNNs.
For decoupled designs, we implement the pre-propagation version (Wang et al., 2021a) of the following models:
SGC (Wu et al., 2019) corresponds GCN spectral smoothing, but computes the propagation P -A X separately
in advance.
APPNP (Klicpera et al., 2019) accumulates and propagates the embedding with a decay factor P == EtE a A'
Baseline Methods. Our selection of baselines is dependent on their applicable backbones. We mostly utilize their public source codes and retain original implementations. For iterative models, we consider state of the arts in graph and joint compression, which are methods with the capability to produced sparsified graphs with smaller edge sets for both GNN training and inference:
GLT (Chen et al., 2021) proposes concurrently sparsifying GNN structure by gradient- based masking on both adjacency and weights.
GEBT (You et al., 2022) gradually discovers the small model during training. Its implementation is limited to the GCN backbone.
CGP (Liu et al., 2023a) iteratively prunes and regrows graph connections while exploiting irregular compression on weights.
DSpar (Liu et al., 2023b) employs one-shot graph sparsification according to degree- metric, which implies an upper bound for pruning rate. It does not perform weight pruning.
Random (RAN) refers to the sparsification method that removes entries with uniform probability based on the specified sparsity.
For the decoupled scheme, we mainly evaluate the graph sparsification. There are two propagation personalization techniques, both only available for the SGC backbone:
NDLS (Zhang et al., 2021) determines the hop number by calculating the distance to convergence, which produces a customized propagation.
NIGCN (Huang et al., 2023) offers better scalability by performing degree-based estimation on the node-wise propagation depth.
The graph and weight sparsities are calculated as portions of pruned entries compared to the original matrices. For layer-dependent methods, the average sparsity across all layers used. For UNIFEWS, the pruming thresholds 6, and 6 are determined by Theorem 4.2. Note that as Algorithm naturally preserve diagonal elements in T, a GCN layer with na 100% UNIFEWS pruning is equivalent to an MLP layer.
C.2. Additional Results on Effectiveness
Extending Figure 3, results of edge and weight sparsification of UNIFEWS and other baselines on more datasets are in Figure 10, while the performance comparison discussed in Section 5. Additionally, we present the experimental results of UNIFEWS on larger datasets and on more backbone architectures in Figure 11 and Figure 12, respectively. No baseline method is available for these settings. It can be observed that UNIFEWS constantly achieves satisfying performance in large range of sparsity. The effect of graph sparsification on GCNII is relatively unstable, likely because the deeper layers amplify the approximation error.
Variance. The variance of UNIFEWS is particularly shown Figure 13 corresponding to Figure Typically, the variance of iterative UNIFEWS models are between the range of 1-3%, which slightly larger than the backbone model due the perturbation of edge and weight sparsification.
20

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
Rew
Random
GLT
GEBT
CGP
Depar
Unitews (Ouns)
CCN+citeeerr
citreeee
GATtciteserr
50
80
80
80
Accurary 156)
76
15
70
70
25
100
GCN+puumed
+CN++pbbeed
GAT+
GAT +AT+-ubmeed
90
Accureey
85
85
85
50
80
80
80
130
(d) GAT Weight Pruning Figure 10: Accuracy of iterative models over citeseer and pubmed, supplementing Figure 3. Columns of "Edge" and
(a) GCN Edge Pruning
(b) GCN Weight Pruning
GAT Edge Pruning
"Weight Sparsity" present the average results of models with solely edge and weight sparsification, respectively.
GCN physics
GCN physics
+aNia
GCN+arxiv
100
100
80
96
70
Accuncyy
60
60
94-
50
50
082
07
90
30
75
100
50
25
50
100
40
100
Edge Sporsty (95)
Wright Sparsty (%)
Frlgo Spunityy (56)
Weight Sporsity (%)
(a) GCN Edge Pruning
(b) GCN Weight Pruning
(c) GCN Edge Pruning
(d) GCN Weight Pruning
Figure 11: Accuracy of iterative UNIFEWS over physics and arxiv, while baseline methods meet OOM.
GCNIT
GCNIT
GSAGE+cora
GSAGE+rora
85-
85-
85
Ancurary
80-
75
75-
75-
75-
25
90
100
05
10
50
100
25
30
75
50
100
50
775
90
100
GCNII+citeseer
GCNII+ccteseer
GSAGE+oiteser
CSAGE-citeeed
80
80
80
75-
Aceuracy
100
25
25
25
100
Edge Sparsity (9))
Wenght Sparsity (9E)
Edge Squinity (%)
Whight Sposity (56)
(a) GCNII Edge Pruning
(b) GCNII Weight Pruning
(c) GraphSAGE Edge Pruning (d) GraphSAGE Weight Pruning
Figure 12: Accuracy of iterative UNIFEWS for GCNII and GraphSAGE backbones, while no baseline method is applicable.
21

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
GCN+cora
GCN+ccora
GAT+cora
+cora
92
92
92
92
90
50.
90-
Acvurnyy
88
88-
66
66-
84
84
82
62
100
100
100
(a) GCN Edge Pruning
(b) GCN Weight Pruning
(c) GCN Edge Pruning
(d) GCN Weight Pruning
Figure 13: Accuracy and variance of iterative UNIFEWS over cora.
C.3. Effect of Hyperparameters
Effectiveness of Joint Sparsification. For effectiveness, the impact of jointly changing 8, and 6n is displayed in Figure 14, Intuitively, GCN is more resilient to UNIFEWS sparsification, considering its relatively high redundancy of the wide distribution of entry values. In comparison, GAT is more sensitive to weight removal, that beyond a certain threshold o its accuracy drops significantly. This observation suggests that the value of learnable attention weights in GAT are highly concentrated, and selecting an appropriate sparsity critical to its performance.
Dier Spanitt (5)
2.0
60.
61.3
92.9
85.6
80L
86.7
2.0
$1.2
61.2
22.0
BLT
518
51.2
81.5
Aettaay (8)
Spority
1.0
V777
67.7
67.5
1.0
60.6
871
67.6
Wegle Wigle-Toee Thmmbl
0.5-
68.6
Wedlh Timmbe3
82.6
52.6
d
-04
20
65.4
0.0
Hoo
(a) Propagation Hop
(b) Network Layer
0000-
45.4
85.0
67.0
BL02
14.11
65.7
41.
540
6.0
18.5
1
09
0500
0.0
6712
0
45.
65
18.5
Figure 15: Sensitivity of propagation and network trans- formation layers evaluated on SGC over cora. (a) Impact on accuracy and average edge sparsity of varying numbers of propagation hops. (b) Impact on accuracy and average weight sparsity of varying numbers of network layers. Note that the x-axis representing layers is on a logarithmic scale.
00
0.6
0.2
05
20
0.0
0.56
0.2
0.5
20
(a) GCN cora
(b) GAT cora
Figure 14: Accuracy of varying joint sparsification thresh- olds on GCN and GAT over cora.
Sparsification on Synthetic Graphs. We further utilize GenCAT (Maekawa et al., 2022; 2023) to generate synthetic graphs with randomized connections and features by varying its parameters. GenCAT((a, o) is the state-of-the-an graph generation approach that allows for configuring the edge connections and node attributes synthesis by specifying their distributions, where is the coefficient of edge power law distribution P(d) d= and ø is the deviation of attribute Gaussian distribution piv] ~ NO0 o²), both sharing the definitions in our paper. The remaining inputs of GenCAT, including label distribution and attribute-label correlation, are set by mimicking the statistics from cora. We utilize two groups of a and a values to generate 4 graphs with different edge and attribute distributions and evaluate UNIFEWS.
Then, we evaluate the relationship between the edge threshold 6, and the edge sparsity Ta following the settings of Figure 8. The results are available in Figure 16. As an overview, the pattern is similar to the one Figure 8, while the constants are effectively affected by the changes of edge and feature distribution in the GenCAT graph. For 6, not too close to 0, the relation with 7/, largely follows Theorem 4.2.
Propagation and Network Layer L. Since UNIPEWS adopts layer-dependent graphs, we additionally evaluate its perfor- mance on models with varying layers. Figure 15(a) is the result of iteratively applying UNIFEWS edge sparsification to SGC with different propagation depths. The backbone model without pruning 5, = 0 typically suffers from the over-smoothing issue under large hop numbers. On the contrary, as elaborated in Section 4.2, UNIFEWS is powerful for identifying and eliminating unimportant propagations, especially for larger hops, and thereby prevents information loss. With respect to architectural compression Figure 15(b), it is noticeable that UNIFEWS promotes model performance and average weight sparsity at the same time for deeper layers, effectively reducing network redundancy.
22

---

UNIFEWS: You Need Fewer Operations for Efficient Graph Neural Networks
C.4. Specific Experiments
Entry Distribution. An example on the real-word graph cora is shown in Figure 9(),, which demonstrates that the distribution of node degree follows the power law, and the distribution of message values correlated with the diffusion entries. Hence, message magnitude is effective in representing edge importance and determining entry removal. Setting entries in the diffusion matrix T to zero according to Equation (5) implies removing the corresponding edges from the graph diffusion process. Consequently, messages with small magnitudes are prevented from propagating neighboring nodes and composing the output embedding.
Approximation Error. An empirical evaluation of multi-hop UNIFEWS on cora is shown in Figure 9b), which validates that the approximation error affected by the sparsification threshold 6, as well as propagation hops L. Mcanwhile, even under aggressive sparsification, the error is still adequately bounded to yield meaningful learning outcomes.
Additionally, we note that the "error" induced in Algorithm is not necessarily harmful. Examining Equation (1), excessive propagation of common GNNs can lead to decline performance known as the over-smoothing issue, where the graph regularization dominant and meaningful node identity is lost (Li al., 2018). By eliminating portion of graph diffusion, UNIFEWS effectively alleviates the over-smoothing issue.
Over-smoothing.
We showcase the effect of alleviating ser-thng in UNIFEWS by depicting the embedding difference to optimization convergence in Figure 9(c). With increased number of hops, the output embedding tends towards over-smoothed state. However, a stronger sparsification prevents the rapid smoothing and hereby contributes to better graph learning performance.
We further study the particular effect with the iterative GCNII of 32 layers in Figure 12, and with the decoupled SGC of 5-80 layers in Figure 15. 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.
2.10
100
100
0.20
Sparsity (96)
Sparsity (%)
Frequency
9.15
50-
50
0.10
0.05
()
2
3
0.00
25
50
15
100
Diffusion Threshold &
Diffusion Threshold &, (b) (enCAT((.1,
Drgme
(a) (2.,00)
(c) 2.1 Degree Distribution
100
100
0.20
Sporsity (96)
Spansity (96)
Frequenyy neneyy
0.15
50-
0.10
0.05
0
2
3
3
0.00
25
50
75
100
Diffusion Threshold 8,
Diffusion Threshold &
Degroe
(d) (2.9.0)
(e) GenCAT(2.9, 1.0)
(1) a 2.9 Degree Distribution
Figure 16: Relationship between edge threshold 6, and sparsity Ta on synthetic graphs generated by GenCAT. We also
present the degree distribution of nodes in different GenCAT graphs controlled by a to illustrate the power law.
23


Reviews:
[{"review_id": "gPjdDLdX3m", "reviewer": "Reviewer_mKp3", "summary": "The paper proposes a framework named UNIFEWS (UNIFied Entry-Wise Sparsification), which aims to improve the learning efficiency of Graph Neural Networks (GNNs) by jointly sparsifying the graph and the weight matrix. By incrementally increasing sparsity layer by layer, the framework significantly reduces the computational operations in GNNs without notably compromising model accuracy. Theoretically, the authors establish a new framework to characterize the learning of sparsified GNNs and prove that UNIFEWS can effectively approximate the learning objective within bounded error. Experiments show that UNIFEWS achieves efficiency improvements on multiple datasets, reducing matrix operations by 10 to 20 times and accelerating computations by up to 100 times for graphs with billions of edges.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful to the reviewer for recognizing our theoretical and experimental contributions. We respectfully address the specific reviews below.\n\n## W1\n**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).\n\nThe 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].\n\nWe will clarify the rationale when deriving Thm 4.1 in the revised version.\nIn *Reviewer t1S7 T1*, we further present a new empirical evaluation regarding these two assumptions on synthetic graphs generated by GenCAT.\n\n[R1] Power-law distributions in empirical data. SIAM Rev'09.  \n[R2] Contextual Stochastic Block Models. NeurIPS'18.  \n[R3] Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. ICLR'18.  \n[R4] Distribution Knowledge Embedding for Graph Pooling. TKDE'22.\n[R5] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.\n\n## W2\nWe 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$.\nEmpirical 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.\n\nThe **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].\n\n## C1\nOne 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes. All experimental frameworks were rigorously validated through specific statistical method, and cross-verified against benchmark datasets, documented in Evaluation Section and Supplementary Materials.", "relation_to_broader_scientific_literature": "This study makes a meaningful contribution to the existing body of knowledge in the related literature.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strength:\n* A novel joint sparsification technique is proposed, which unifies the operations of the graph and the weight matrix and establishes a theoretical connection between the graph optimization process and sparsification. This innovative perspective provides new ideas for the optimization of GNNs and fills the theoretical gap in existing research regarding the joint sparsification of graphs and weights.\n* The concept of ϵ-spectral similarity is introduced, and its effectiveness in the spectral domain is theoretically demonstrated for UNIFEWS. This provides a more rigorous theoretical guarantee for the sparsification of GNNs.\n* It demonstrates significant efficiency improvements on large-scale graph data, especially achieving a 100-fold acceleration on graphs with billions of edges. This is of great significance for processing large-scale graph data and can effectively alleviate the bottleneck issues of existing GNNs in terms of computational resources and time.\n* By incrementally increasing sparsity layer by layer, UNIFEWS progressively reduces the computational load in multi-layer GNNs, further enhancing the scalability of the model.\n\nWeakness:\n* Although the paper proposes a theoretical framework to analyze the impact of sparsification on GNN learning, its theoretical analysis is based on several assumptions, such as the distribution of the graph (e.g., power-law distribution) and the Gaussian distribution of input features. These assumptions may not always hold in practical applications, which could lead to certain discrepancies between the theoretical results and the actual performance. Please further clarify the rationality. \n* The performance of UNIFEWS depends on the choice of sparsification thresholds (δa and δw). However, the authors do not provide a systematic method for automatically selecting these hyperparameters, instead relying on manual tuning or empirically based choices. This may make it difficult to find the optimal combination of hyperparameters in practical applications, thereby affecting the performance of the model.", "other_comments_or_suggestions": "The paper does not discuss the limitations of the proposed method.", "questions_for_authors": "Please refer to the Other Strengths And Weaknesses section for detailed inquiries.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7SCQmPdNxq", "reviewer": "Reviewer_t1S7", "summary": "This paper explores strategies to accelerate GNN computation by integrating both structural sparsification and weight parameter pruning. Specifically, it introduces a framework called UNIFEWS, which adaptively and progressively simplifies computations while providing theoretical guarantees on the accuracy tradeoff. Experimental results validate the proposed approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the constructive feedback from the reviewer. Below, we provide detailed responses with new experiments following the suggestions.\n\n## T1\nThe 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. \n\nOn **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. \n\nWe 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. \n\n[R1] GenCAT: Generating attributed graphs with controlled relationships between classes, attributes, and topology. Information Systems'23.  \n[R2] Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs. NeurIPS'22.\n\n## W1\nWe 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.\n\n|Edge Sparsity|30%|50%|80%|90%|\n|--|--|--|--|--|\n|`DropEdge`|86.4|86.8|79.5|43.7|\n|`Random`|85.5|86.3|85.0|80.8|\n\nEmpirically, 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.\n\n## Q1\nFor 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.\n\nRegarding **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.\n\n## Q2\nThe performance near 100% sparsity is affected by various factors. We would like to compare it to MLP in the following aspects:\n\n1. 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**.\n\n2. 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.\n\n3. 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "For Theorem 4.1, I have not verified the proof; however, it is crucial to include synthetic examples illustrating the bounds. This would help readers better understand their behavior, especially since the ranges of the constants in the theorem are not provided.", "experimental_designs_or_analyses": "I find the experimental section to be quite comprehensive and did not notice any major shortcomings, except for a few questions, which I have outlined in the \"Questions\" section below.", "relation_to_broader_scientific_literature": "The broader connection of this paper to general scientific discovery is not immediately clear. However, the proposed efficiency improvements contribute to the wider deployment of GNNs on larger-scale datasets and applications, which is certainly a valuable advantage.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "## Strengths\n\n1. The paper is well-presented with excellent readability, supported by clear diagrams and algorithmic aids for better clarification.\n2. The distinction between iterative GNNs and decoupled GNNs enhances the generality of the proposed approach.\n3. A complexity analysis of the proposed method(s) is provided.\n\n## Weaknesses\n\n1. DropEdge [Rong et al., 2020] should be included as a baseline in the comparisons for iterative sparsification.\nThe variance of numerical metrics should be reported in all plots and tables.\n2. Please check my questions below.", "other_comments_or_suggestions": "Please see my questions below.", "questions_for_authors": "## Questions \n1. In the experiments, the backbone GNNs are all set to 2 layers, effectively avoiding the over-smoothing problem. This suggests that the improvements from sparsification may stem from factors other than mitigating over-smoothing. What are your thoughts on this? What other possible explanations could there be?\n2. The results in Figures 3 and 5 are somewhat difficult to interpret when weight/edge sparsity approaches 100%, as the performance even improves compared to the corresponding backbones. Wouldn’t a 100% edge sparsity reduce the model to an MLP, making performance entirely dependent on node features? Similarly, when weight sparsity nears 100%, no node feature information should be preserved—so how is high node classification accuracy still achieved?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5b4gJbdpNH", "reviewer": "Reviewer_9jfo", "summary": "This paper introduces UNIFEWS a technique to sparsify GNNs by dropping messages. The authors justify their UNIFEW by proofs that provide theoretical guarantees. In experiments, UNIFEWS allows dropping almost all edges in the graphs without much impact on predictive performance. This leads to a significant speed-up by a factor of up to x100.\n\n## update after rebuttal\nThe authors have addressed many concerns effectively in the rebuttal. While I still believe the work primarily demonstrates that graph structure is often unimportant for many datasets, the authors' contributions are nonetheless meaningful and well-supported. My recommendation lies between a weak accept and an accept; given the options, I lean toward recommending acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful for the detailed and insightful comments from the reviewer. We address the specific reviews below with further evaluation results.\n\n## W1\nIn 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.\n\nFurthermore, 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.\n\nWe 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. \n\n### `GCN+arxiv`\n| Edge Sparsity | Weight Sparsity | Graph Propagation (s) | Feature Transform (s) |\n| --- | --- | --- | --- |\n| 0% | 0% | 5.85 | 0.58 |\n| 50% | 0% | 3.54 | 0.61 |\n| 0% | 50% | 5.54 | 0.36 |\n| 50% | 50% | 3.66 | 0.36 |\n\nIn 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.\n\n## W2\nWhile 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`.\n\n### `MLP` ($L=2$)\n| Dataset | `cora` | `citeseer` | `pubmed` |\n| --- | --- | --- | --- | \n| Acc (%) | 75.2 | 71.7 | 87.0 |\n\nWe would like to discuss the difference of Unifews with MLP at high sparsity in the following aspects:\n\n1. 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**.\n\n2. 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.\n\n3. 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.\n\n## C1-3\nWe thank the reviewer for pointing out the issues. We will carefully fix the typos in the revised version.\n\nThe 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.\n\n## Q1\nThe 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**.\n\nIt 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.", "claims_and_evidence": "The authors provide convince evidence in the form of proofs and experimentts.", "methods_and_evaluation_criteria": "See (W2).", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "The experimental design seems sound.", "relation_to_broader_scientific_literature": "Related work is good.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**\n- (S1)The proposed method is intuitive and conceptually simple: it is clear that dropping unimportant messages will lead to a speed-up at little cost to predictive performance (the hard part is chosing which messages to drop).\n- (S2) The proposed method is backed by theoretical arguments:\n\t- Theorem 4.1 gives us a bound on the spectral similarity between sparsified and non-sparsified laplacian\n\t- For decoupled architectures, UNIFEWS allows for an $\\epsilon$ approximation of graph smoothing (Proposition 4.2)\n- (S3) The proposed method allows to drop almost all edges without losing predictive performance (Figure 4).\n\n**Weaknesses:**\n- Speed Analysis (Section 5.2) is done only for decoupled models and not for iterative models. Since decoupled models are more niche than iterative models, this weakens the paper. This is especial crucial as Fig. 6 shows that for iterative models the propagation step is not important, implying that UNIFEWS might lead to only little speedup on iterative models.\n- (W2) I am not convinced that the strong predictive performance in the low edge regime (S2) is truly caused by UNIFEWS. After all, achieving the same accuracy with 1% with just edges should simply mean that the graph structure is uninformative. In this case, it is not clear what the true utility of UNIFEWS is. This could be combated, by testing UNIFEWS on more diverse datasets to see how it behaves for problems where the graph structure is important \n\n**Overall,** I think that this is a good paper that is held back by some small issues (mainly W2). Thus I vote for weak accept.", "other_comments_or_suggestions": "- Please use `\\mid` in your definition of neighborhood instead of |  ($\\{ a | ...\\}$ vs  $\\{ a \\mid ...\\}$)\n- \"in an one-time\", maybe \"a one-time\"?\n- Theorem 4.1 could be formulated better, it is not mentioned how the sparsified laplacian is obtained which is the crucial part of the theorem.", "questions_for_authors": "- The operation performed by UNIFEWS simply thresholds out messages (=vectors) whose magnitude is smaller than some $\\delta$. This operation is by default non-differentiable. Could this cause problems? Might it improve to make this process differentiable during training?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CKZhMXsXdh", "reviewer": "Reviewer_D2Wc", "summary": "This paper proposes Unifews, a sparsification for both graph and weight matrix. The purpose of such sparsification is to boost the scalability of GNN.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback. We have carefully checked the experiments and would like to address the questions as follows. \n\n## W1&Q4\nWe 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.\n\n### Mini-batch `cora`\n| Edge ratio | 30% | 50% | 80% | 90% |\n|------------|-----|-----|-----|-----|\n| `DropEdge` Acc (%) | 86.4  | 86.8 | 79.5 | 43.7 |\n| `DropEdge` Time (s) | 7.13 | 7.31 | 7.09 | 6.87 |\n| `GraphSAGE` Acc (%) | 77.6 | 78.2 | 79.4 | 78.7 |\n| `GraphSAGE` Time (s) | 2.00 | 1.80 | 1.86 | 1.83 |\n| `GraphSAINT` Acc (%) | 74.7 | 78.1 | 77.8 | 77.2 |\n| `GraphSAINT` Time (s) | 228.02 | 167.29 |  179.58 | 193.31 |\n| `ClusterGCN` Acc (%) | 78.3 | 76.9 | 77.1 | 74.3 |\n| `ClusterGCN` Time (s) | 4.50 | 4.20 | 3.47 | 2.66 |\n\n### Mini-batch `papers100M`\n| Edge ratio | 30% | 50% | 80% | 90% |\n|------------|-----|-----|-----|-----|\n| `GraphSAGE` Acc (%) |  46.25   |  48.45   |  41.02   |  42.64   |\n| `GraphSAGE` Time (s) |  18208   |  13662   |  6565   |  3850   |\n\nWe would like to highlight the difference between the settings and our evaluation in the paper as follows:\n\n1. 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.\n\n2. 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**.\n\n3. 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**.\n\n## W2&Q1\nWe elaborate the setups of the `papers100m` result in *Tab 1*:\n\n1. 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`.\n\n2. 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.\n\n3. 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`.\n\nIn 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.\n\n## Q2\nThe acceleration ratio of wall-clock time is also affected by several factors beside the complexity analysis:\n\n1. 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$.\n\n2. 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.\n\n3. 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.\n\n## Q3\nIn *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.", "claims_and_evidence": "A major claim of this paper is the speed-up on the Ogbn-papers100m dataset, I have some questions about this claim, please refer to latter sections.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I briefly check the theoretical claims, they looks solid.", "experimental_designs_or_analyses": "No obvious problem.", "relation_to_broader_scientific_literature": "The key contribution is scalability, this is a very active field of GNN.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "S1: The paper is easy to follow.\n\nS2: Theoretical results seem solid.\n\nS3: The literature review is comprehensive.\n\nW1: It would be better to include more baseline. Currently, only graph sparsification methods are used, but since this paper is about scalability, I think other methods should also be included, e.g., other compression method like coarsening/condensation, neighbor sampling methods.\n\nW2: The 100 times acceleration on the ogbn-papers100m is the main contribution of this paper, the authors mention this multiple times in the paper. But the experimental setup of this result is a bit unclear. Please refer to the question section.", "other_comments_or_suggestions": "No obvious typo.", "questions_for_authors": "Q1: About the 100 times acceleration, Table 1 reports 19212s for the graph propagation of SGC on the ogbn-papers100m dataset. It is more than 5 hours. I remember this operation takes roughly 30 minutes on my machine with only CPU, I know there are performance discrepancies among hardwares, but can you double-check your result? It seems too long.\n\nQ2: On the other hand, the acceleration seems conflict with the \"Complexity Analysis\" section in Line 294? It says the computation complexity is reduced by $O(1-\\eta_{\\alpha})$, and the $\\eta_{\\alpha}$ is set to 50% in Table 1, so there should be 2 times of acceleration? This matches the results on all other datasets, but only not ogbn-papers100m. Please kindly correct me if I am missing something.\n\nQ3: DSpar is not used as a baseline in Table 1, could you elaborate why?\n\nQ4: Can you try other scalability method, like GraphSAGE with neighbor sampling, graphsaint and clustergcn on ogbn-papers100m and report the runtime and accuracy? These are all classical scalability methods and their code should be easy to find.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously recommend acceptance of the paper with varying degrees of strength. I agree with their assessment and am happy to recommend acceptance of this paper. Several reviewers mentioned that the paper is clear and well-written. They furthermore appreciated the theoretical backing of the proposed method as well as the close to 100-fold acceleration that is observed in one instance. The reviewer's concerns have largely been addressed in the discussion period.

The reviews and the rebuttal have given rise to several interesting points and results that I encourage the authors to include in their revised manuscript. This includes the missing discussion of the limitations of our method, especially with regards to heterophilic graphs, as well as the additional empirical results you provided during the rebuttal.
Decision: Accept (poster)