Graph Sparsification via Mixture of Graphs
Authors: Guibin Zhang
Xiangguo Sun
Yanwei Yue
Chonghe Jiang
Kun Wang
Tianlong Chen
Shirui Pan
Venue: ICLR 2025 Spotlight (2025)
Keywords: Graph Sparsification
Mixture-of-Experts
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have demonstrated superior performance across various graph learning tasks but face significant computational challenges when applied to large-scale graphs. One effective approach to mitigate these challenges is graph sparsification, which involves removing non-essential edges to reduce computational overhead. However, previous graph sparsification methods often rely on a single global sparsity setting and uniform pruning criteria, failing to provide customized sparsification schemes for each node's complex local context.
In this paper, we introduce Mixture-of-Graphs (MoG), leveraging the concept of Mixture-of-Experts (MoE), to dynamically select tailored pruning solutions for each node. Specifically, MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Subsequently, MoG performs a mixture of the sparse graphs produced by different experts on the Grassmann manifold to derive an optimal sparse graph. One notable property of MoG is its entirely local nature, as it depends on the specific circumstances of each individual node. Extensive experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNN backbones, demonstrate that MoG (I) identifies subgraphs at higher sparsity levels ($8.67\\%\sim 50.85\\%$), with performance equal to or better than the dense graph, (II) achieves $1.47-2.62\times$ speedup in GNN inference with negligible performance drop, and (III) boosts ``top-student'' GNN performance ($1.02\\%\uparrow$ on RevGNN+\textsc{ogbn-proteins} and $1.74\\%\\uparrow$ on DeeperGCN+\textsc{ogbg-ppa}). The source code is available at \url{https://github.com/yanweiyue/MoG}.

Published as a conference paper at ICLR 2025
GRAPH SPARSIFICATION VIA MIXTURE OF GRAPHS
Guibin Zhang': Xiangguo Sun Yanwei Yue',, Chonghe Jiang", Kun Wang Tianlong Chen Shirui Pan 'Tongji University CCHK @NTU *UNC-Chapel Hill GGriffith University
ABSTRACT
Graph Neural Networks (GNNs) have demonstrated superior performance across various graph learning tasks but face significant computational challenges when applied to large-scale graphs. One effective approach to mitigate these challenges is graph sparsification, which involves removing non- non-essential edges to reduce computational overhead. However, previous graph sparsification methods often rely on a single global sparsity setting and uniform pruning criteria, failing to provide customized sparsification schemes for each node's 's complex local context. In this paper, we introduce Mixture-of Gfrrrh (MoG), leveraging the concept of Mixture- of-EExerrs (MoE), to dynamically select tailored pruning solutions for each node. Specifically, MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Subsequently, MoG performs a mixture of the sparse graphs produced by different experts on the Grassmann manifold derive an optimal sparse graph. One notable property of MoG is its entirely local nature, as it depends on the specific cireumstances of each individual node. Extensive experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNN backbones, demonstrate that MoG (I) identifies subgraphs at higher sparsity levels (8.67% 50.85%), with performance equal to better than the dense graph, (II) achieves 1.47 - 2.62 speedup in GNN inference with negligible performance drop, and (III) boosts "top-student" GNN performance (1.02% t RevGNN+OGBN- PROTEINS and 1.74% t on DeeperGCN++GBBG-PPA) The source code is available at httpt: / hub. com www.elywwwweeeeeeeeeee /MoG.
INTRODUCTION
Graph Neural Networks (GNNs) (Sun et al., 2023a; Zhou et al., 2020) have become prominent for confronting graph-related learning tasks, including social recommendation (Wu et al., 2021; Yu et al., 2022), fraud detection (Sun et al., 2022; Wang al., 201 9a; Cheng et al., 2020), drug design (Zhang & Liu, 2023), and many others (Wu et al., 2023; Sun et al., 2023b), The superiority of GNNs stems from iterative aggregation and update processes. The former accumulates embeddings from neighboring nodes via sparse matrix-based operations (e.g., sparse-dense matrix multiplication (SpMM) and sampled dense-dense matrix multiplication (SDDMM) (Fey & Lenssen, 2019; Wang al., 2019b)). and the latter updates the central nodes' embeddings using dense matrix-based operations (e.g., MatMul) (Fey & Lenssen, 2019; Wang et al., 201 10)9b.. SpMM typically contributes the most substantial part (~70%) to the computational demands (Liu et al., 2023b; Zhang et al., 2024b), influenced largely by the graph's is scale. Nevertheless, large-scale graphs are widespread in real-world scenarios (Wang et al., 2022a; Jin et al., 2021; Zhang et al., 2024a), leading to substantial computational burdens, which hinder the efficient processing of features during the training and inference, posing headache barriers to deploying GNNs in the limited resources environments.
To conquer the above challenge, graph sparsification (Chen et al., 2023; Hashemi et al., 2024) has recently seen a revival as it directly reduces the aggregation process associated with SpMM (Liu et al., 2023b; Zhang et al., 2024b) in GNNs. Specifically, graph sparsification is a technique that approximates a given graph by creating sparse subgraph with a subset of vertices and/or edges. Since the execution time of SpMM is directly related to the number of edges in the graph, this method can significantly accelerate GNN training or inference. Existing efforts such as UGS (Chen et al.,
Equual Contribution, CCoresponding Authors

---

Published as a conference paper at ICLR 2025
Center Node: 14
Pruning alinitationn Low lnforme Resteonee
Zioar Skyp
1.hop
2-hop
3.8ep
Center Noue: 6
[Eyert
Pruning altribution Non-Brily Eige
Pruning attribuzion: Kon-komuphlll Elyy
Assegaied Spare Grggh)
Figure 1: (Left) We illustrated the k-hop neighborhood expansion rates for nodes 6 and 14, which is proportional to the amount message they receive as the GNN layers deepen; (Middle) The local patterns of different nodes vary, hence the attributions of edge pruning may also differ. For instance, pruning (vi, U2) might be due to its non-bridge identity, while pruning (05, vp) could be attributed to its nom-hooopiilic nature; (Right) The overview of our proposed MoG.
2021), DSpar (Liu et al., 2023b), and AdaGLT (Zhang et al., 2023) have achieved notable successes, with some maintaining GNN performance even with up to 40% edge sparsity.
Beyond serving as computational accelerator, the purpose of graph sparsification extends further. Another research line leverages graph sparsification as performance booster to remove task- irrelevant edges and pursue highly performant and robust GNNs (Zheng et al., 2020). Specifically, it argued that due uncertainty and complexity in data collection, graph structures are inevitably redundant, biased, and noisy (Li et al., 2024). Therefore, employing graph sparsification can effectively facilitate the evolution of graph structures towards cleaner conditions (Zheng et al., 2020; Luo et al., 2021), and finally boost GNN performance.
However, existing sparsification methods, namely sparsifiers, whether aimed at achieving higher sparsity or seeking enhanced performance, often adopt rigid, global approach to conduct graph sparsification, thus suffering from the inflexibility two aspects:
Inflexibility of sparsity level. Previous sparsifiers globally score all edges uniformly and prune them based a preset sparsity level (Chen et al., 2023). However, as shown in Figure (Leff), the degrees of different nodes vary, which leads to varying rates of k-hop neighborhood expansion. This phenomenon, along with prior work on node-wise aggregation (Lai al., 2020; Wang et al., 2023a), suggests that different nodes require customized sparsity levels tailored to their specific connectivity and local patterns.
Inflexibility of sparsity criteria. Previous sparsifiers often operate under unified guiding principle, such as pruning non-bridge edges (Wang et al., 2022b), non-homophilic edges (Gong et al., 2023), or edges with low effective resistance (Spiclman & Srivastava, 2008; Liu et al., 2023b), among others. However, illustrated in Figure 1 (Middle), the context of different nodes varies significantly, leading to varied rationales for edge pruning. Therefore, it is essential to select appropriate pruning criteria tailored the specific circumstances of each node to customize the pruning process effectively.
Based on these observations and reflections, we propose the following challenge: Can we customize the sparsity level and pruning criteria for each node, in the meanwhile ensuring the efficiency of graph sparsification? Towards this end, we propose novel graph sparsification method dubbed Mixture of Graphs (MoG). comprises multiple sparsifier experts, each equipped with distinct pruning criteria and sparsity settings, as in Figure (Right). Throughout the training process, MoG dynamically selects the most suitable sparsifier expert for each node based on neighborhood properties. This fosters specialization within each MoG expert, focusing specific subsets of nodes with similar neighborhood contexts. After each selected expert prunes the 1 1-hop subgraph of the central nodes and outputs its sparse version, MoG seamlessly integrates these sparse subgraphs the Grassmann manifold in an expert-wa weighted manner, thereby forming an optimized sparse graph.
We validate the effectiveness of MoG through a comprehensive series of large-scale tasks. Experi- ments conducted across six datasets and three GNN backbones showcase that MoG can O effectively locate well werfopeeno sparse graphs, maintaining GNN performance losslessly at satisfactory graph
2

---

Published as a conference paper at ICLR 2025
sparsity levels (8.67% ~ 50.85%). and even only experiencing a 1.65% accuracy drop 69.13% sparsity on performance drop; and @ boost ROC-AUC by 1.81% on DGBG-MOLHIV, 1.02% on ogbn-proteins and enhances accuracy by 0.95% on OGBN-ARXIV compared to the vanilla backbones.
achieve a tangible 1.47 ~ 2.62x inference speedup with negligible
The key contributions of MoG can be found in appendix H.2.
TECHNICAL BACKGROUND
Notations & Problem Formulation We consider an undirected graph 9 = E}, with V as the
node set and & the edge set. The node features of G is represented as X E R X where N = [V] signifies the total number of nodes in the graph. The feature vector for each node o E V, with F dimensions, is denoted by x; X(i, J. An adjacency matrix A E {0, 10,1 is utilized to depiet the inter-node connectivity. where A[i,j] = 1 indicates an edge Eij E E, and otherwise. For our task of graph sparsification, the core objective is identify a subgraph Guub given a sparsity ratio s%c
gaub =
8%
[
where Gsub only modifies the edge set & without altering the node set V, and E' denotes the removed edges, and 8% represents the ratio of removed edges.
Graph Neural Networks Graph neural networks (GNNs) (Wu et al., 2020) have become pivotal for learning graph representations. achieving benchmark performances in various graph tasks at node-level (Xiao et al., 2022), edge-level (Sun et al., 2021), and graph-level (Liu et al., 2022a). At the node-level, two of the most famous frameworks are GCN (Kipf & Welling, 2017) and GraphSAGE (Hamilton et al., 2017), which leverages the pesssage-passing neural network (MPNN) framework (Gilmer et al., 2017) to aggregate and update node information iteratively. For edge-level and graph-level tasks, GCN and GraphS can be adapted by simply incorporating a predictor head or pooling layers. Nevertheless, there are still specialized frameworks like SEAL (Zhang & Chen, 2018) and Neo-GNN (Yun et al., 2021) for link prediction, and DiffPool (Ying et al., 2018) and PNA (Corso et al., 2020) for graph classification. Regardless of the task, MPNN-style GNNs generally adhere to the following paradigm:
h
COMB [b (1-1) (h, (k (k-1)
by N(())))) 0 OSISL
where L is the number of GNN layers, h x, and h ( <IS L) denotes vy's node embed- ding at the 1-th layer. AGGR(-) and COMB(.) represent functions used for aggregating neighborhood information and combining ego- and reighboorrprresennttinn,, respectively.
Graph Sparsification Graph sparsification methods can be categorized by their utility into two main types: computational accelerators and performance boosters. Regarding computational accel- erators, early works aimed at speeding up traditional tasks like graph partitioning/chustering often provide theoretical assurances for specific graph properties, such as pairwise distances (Althöfer et al., 1990), cuts (Abboud et al., 2022), eigenvalue distribution (Batson et al., 2013), and effective resis- tance (Spielman & Srivastava, 2008). More contemporary efforts focus on the GNN training and/or inference acceleration, including methods like SGCN (Li et al., 2020b), GEBT (You et al., 2022), UGS (Chen et al., 2021), DSpar (Liiu al., 2023b), and AdaGLT (Zhang et al., 2024a). Regarding performance boosters, methods like NeuralSparse (Zheng et al., 2020) and PTDNet (Luo et al., 2021) utilize parameterized denoising networks to eliminate task-irrelevant edges. SUBLIME (Liu et al., 2022b) and Nodeformer (Wu et al., 2022) also involve refining or inferring cleaner graph structure followed by k-nearest neighbors (kNN) sparsification.
Mixture of Experts The Mixture of Experts (MoE) concept (Jacobs et al., 1991) traces its origins to several seminal works (Chen et al., 1999; Jordan & Jacobs, 1994). Recently, the sparse MoE architecture (Shazeer et al., 2017: Lepikhin et al., 2020; Fedus et al., 2021; Clark et al., 2022) has regained attention due to its capacity to support the creation of vast (language) models with trillions of parameters (Clark et al., 2022; Hoffmann et al., 2022). Given its stability and generalizability. sparse MoE is now broadly implemented in modern frameworks across various domains, including vision (Riquelme al., 2021), multi-modal (Mustafa et al., 2022), and multi-task learning (Ma et al.,
3

---

Published as a conference paper at ICLR 2025
Ego-graph Decomposition
Routing
Customized Sparsifier
Mixture-of-Graph
Input Graph g = (V,8)
Routing Network (AA) h,W, Softplus(h,W.)
Sparsity Levels
Expert Scores for g [f1 2 (( Sparsity Ensembling
Ego subgraphs Decompose into node-spacific ego graphs (s
85%
Candidate Experts
Pruning Criterion
total K sparisifers:
Jaccord Similority: Nodes'
2 LAW
select kout
shared neighbors
Mixture- Grrrph g - (G (ea...m,, g0) -. GriDD)
Sparsifier Selection
Soltmax(TopX() (ft). X))
Gradient Monitude:
EffectiveResisatnic
Gresmann Manifold
Sporsifier Expert
G (sinn)) or-prro fern
Routing Network (hr)
Expert Scores
Criteria: C()
Sparsity:
byaeli
a
Expert No.1
Criteria Sparsity
Expert Scores
Expert No.
g (No.1)
Criterio Sporsity
Sevenas
Expert No.K
Griteria
Sparsity
g
G19
Expert Scorca
(No.k)
Figure The overview of our proposed method. MoG primarily comprises ego-gra gro-rraph decomposition, expert routing, expert customization, and the final graph mixture. For simplicity, we only showcase three pruning criteria including Jaccard similarity, gradient magnitude, and effective resistance.
2018; Zhu al., 2022). As for graph learning, MoE has been explored for applications in graph clas- sification (Hu et al., 2022), scene graph generation (Zhou et al., 2022), molecular representation (Kim al., 2023), graph fairness (Liu et al., 2023a), and graph diversity modeling (Wang et al., 2024).
3
METHODOLOGY
3.1 OVERVIEW
Figure illustrates the workflow of our proposed MoG. Specifically, for an input graph, MoG first decomposes it into 1-hop ego graphs for each node. For each node and its corresponding ego graph, routing network calculates the expert scores. Based on the router's 's decisions, sparsifier experts with different sparsity levels and pruning criteria allocated to different nodes. Ultimately, mixture of graphs is obtained based on the weighted consensus of the sparsifier experts. In the following sections, will first detail how various sparsifier experts in Section 3.3 and how to ensemble the sparse graphs output by experts on the Grassmann manifold in Section 3.4. Finally, the overall optimization process and complexity analysis of MoG is placed in Section 3.5.
different experts in Section 3.2, then describe how explicitly model
3.2 ROUTING TO DIVERSE EXPERTS
Following the classic concept isparsely-gated mixture-of-expprts (Zhao et al., 2024), which as- signs the most suitable expert(s) to each input sample, MoG aims to allocate the most appropriate spar- sity level and pruning criteria to each input node. To achieve this, we first decompose the input graph g= (= }} into 1-hop ego graphs centered on different nodes, denoted as (g(1) g(?) G(M), (uyle, A((,))), g() {eny(w, vy) E E}. Assuming we have K sparsifier experts, each node v; and its corresponding ego graph ((0), we aim to select most suitable experts. We employ the noisy top-k gating mechanism following Shazeer et al. (2017);
where g( {>(+), g()). ). p())
V (g(() =
(xx)) z; W + Softplus(I; W...
where vb(x;) E R is the calculated scores U; for total experts, TopK(.) a selection function that outputs the largest values, and (g(()) R
[F(*] E2(0 ... [0(() represents those for
4

---

Published as a conference paper at ICLR 2025
selected & experts. In (g))), c N/ 1) denotes the standard Gaussian noise, W3 E RR*x XxF Wn E _K*F are trainable parameters that learn clean and noisy scores, respectively.
and
After determining the appropriate experts, we proceed to generate different sparse graphs with diverse sparsifiers. We denote each sparsifier by k(-), which takes in a dense graph G and outputs sparse one 9 = k()). Based on this, for each node e2 and its ego graph g(+), the routing network selects k experts that produce l sparse ego graphs. Notably, sparsifiers differ in their pruning rates (i.e. the proportion of the edges to be removed) and the pruning criteria, which will be detailed in Section 3.3. MoG's s dynamic selection of different sparsifiers for each node aids in identifying pruning strategies truly adapted the node's local context. Formally, the mixture of sparse graphs can be written as:
(5) where ESM(-) () is combination function that receives k sparse graphs and ideally outputs an emsemble version g))) = (V(G) that preserves their desirable properties. is noteworthy that, MoG can seamlessly integrate with any GNN backbone after obtaining each node's sparse ego graph. Specifically, we modify the aggregation method in Equation (2) as follows:
G ESMB (
G <² (G("),
h COMB
(n!-
(111))
AGG (k-1), My E D(O))
MoG acts as a plug-and-play module that can be pre-attached to any GNN architecture, leveraging multi-expert sparsification to enhance GNNs with (1) performance improvements from removing fask-irrelevant edges (validated in Section 4.3); (2) resistance to high graph sparsity through precise and customized sparsification (validated in Section 4.2). The remaining questions now are: how can we design explicitly different sparsifiers? and further, how can we develop an effective combination function that integrates the sparse graphs from different experts?
3.3 CUSTOMIZED SPARSIFIER MODELING
With the workflow of MoG in mind, in this section, will delve into how to design sparsifiers driven by various pruning criteria and different levels of sparsity. Revisiting graph-related learning tasks, their objective can generally be considered as learning P(Y|g), which means learning the distribution of the target Y given an input graph. Based on this, a sparsifier x<-) can be formally expressed as follows:
P(YI)) ~ P 9) ~ - ( g)
gE3g
gEBg
where Sg is class of sparsified subgraphs of G. The second term in Equation (7) aims approximate the distribution of Y using the sparsified graph & as a bottleneck, while the third term uses two approximation functions Qe and Q₂ for P(Y 9) and P(ğ | g) parameterized by O and respectively. The parameter θ typically refers to the parameters of the GNN, while the sparsifier re(-),
on the other hand, is crafted to take an ego graph (( and output its sparsified version g( guided by a specific pruning paradigm C' and sparsity sm:
xTHh (g(() = (V(0) ()()) E()), E = TopK (-CT (E), [|8(1] x smm1)
(8)
where (.) acts as the m-th expert's scoring function that evaluates edge importance. We leverage long-tail gradient estimation (Liu al., 2020) to ensure the TopK(.) operator is differentiable. Furthermore, to ensure different sparsity criteria drive the sparsifier, we implement (*)(-) as follows:
Degree: (IV(v,) + ((x))))
Jaccard Similarity: Win
C (Cigg = FFN (z,, 25,,z))) cth (eiz)
(9)
ER: (c. - e, (ee ee,)
Gradient Magnitude: |0C/0egl
where FFN(.) is feed-forward network, cm (e:s) represents the prior guidance on edge significance. By equipping different sparsifiers with various priors and sparsity levels, we can customize the most appropriate pruning strategy for each node's local scenario. In practice, we select four widely-used pruning criteria including edge degree (Seo et al., 2024), Jaccard similarity (Murphy, 1996a; Satuluri et al., 201, effective resistance (Spielman & Srivastava, 2008; Liu et al., 2023b) and gradient magnitude (Wan & Schweitzer, 2021; Zhang et al., 2024a). Details regarding these criteria and their implementations are in Appendix B.
5

---

Published as a conference paper at ICLR 2025
3.4 GRAPH MIXTURE ON GRASSMANN MANIFOLD
After employing k sparsifiers driven by different criteria and sparsity levels, we are in need of an effective mechanism ensemble these sparse subgraphs and maximize the aggregation of their advantages. A straightforward approach is voting or averaging (Sagi & Rokach, 2018); however, such simple merging may fail to capture the intricate relationships among multi-view graphs (Kang et al., 2020), potentially resulting in the loss of advantageous properties from all experts. Inspired by recent advances manifold representations (Dong et al., 2013; Bendokat et al., 2024), we develop a cisspace-based sparse graph ensembling mechanism. We first provide the definition of the Grassmann manifold (Bendokat et al., 2024) as follows:
Definition (Grassmann manifold). Grassmann manifold Gr(n,p) is the space of n-by-p matrices (e.g., M) with orthonormal columns, where 0 S p S n, i.e., Gr(n,p) (MM RO*P M M=
(10)
According to Grassmann manifold theory, each orthonormal matrix represents a unique subspace and thus corresponds to distinct point the Grassmann manifold (Lin et al., 2020). This applies to the eigenvector matrix of the normalized Laplacian matrix (U = Ll::: p] E R=*P), which comprises the first p eigenvectors and is orthonormal (Merris, 1995), and thereby be mapped onto the Grassmann manifold.
Consider the At sparse subgraphs {Gm } Jm=1, their subspace representations are {Ul RIA(e))lxpE m==1- We aim to identify an oracle subspace U(+) the Grassmann manifold, which essentially represents a graph, that serves as an informative combination of k base graphs. Formally, we present the following objective function:
expert
tr(( L. U())
E d (U (U!) s. U U.) UO= =I (11)
min UUER (())
connectivity
subspace
where tr(-) calculates the trace of matrices, Lm the graph Laplacian of G du, U2) denotes the project distance between subspaces (Dong et al., 2013), and Fill) is the expert score for the m-th expert, calculated by the routing network V which determines which expert's subspace the combined subspace should more closely align with. In Equation (11), the first term designed to preserve the original node connectivity based on spectral embedding, and the second term controls that individual subspaces are close to the final representative subspace U Using the Rayleigh-Rin Theorem (Jia & Stewart, 2001), we provide closed-form solution for Equation (11) and obtain the graph Laplacian of the ensemble sparse graph (+) as follows:
I:
Lm -
U U
(12)
m=1
We provide detailed derivations and explanations for Equations (11) and (12) in Appendix C. Conse- quently, we can reformulate the function ESMB(-) in Equation (5) as follows:
ESMB (W ====) = (D - Lo x (1)
D
Σ (L.. m=1
ElS U U
x
(13)
where (() is the degree matrix of vs's ego- ego-graph. On the Grassmann manifold, the subspace ensemble effectively captures the beneficial properties each expert's sparse graph. After obtaining the final version of each node's ego-graph, glo) { [ x we conduct a post-sparsiffiattio step as the graph ensembled on the Grassmann manifold can become dense again. Specifically, we obtain
the final sparsity (00% for o by weighting the sparsity of each expert and sparsifying g(o)
g (TopK(A (10) x 80%) x()). 500
Σ
m%.
(14)
Post-sparsified (()) are then reassembled together into & + g()) g(MD) }. with detailed
explanations in appendix I. Ultimately, the sparsified graph & produced by MoG can be input into any MPNN (Gilmer et al., 2017) graph transformer (Min et al., 2022) for end-to-end training.

---

Published as a conference paper at ICLR 2025
3.5 TRAINING AND OPTIMIZATION
Additional Loss Functions Following classic MoE works (Shazeer et al., 2017; Wang et al., 2024), introduce expert importance loss to prevent MoG from converging trivial solution where only single group of experts is consistently selected:
M
Importance(V) =
Σ
Eli
Limportance (V) CV(Importancee())
(15)
where Importance(V)) represents the sum of each node's 's expert scores across the node-set, CV(-) calculates the coefficient of variation, and Limportance ensures the variation of experts. Therefore, the final loss function combines both task-specific and MoG-related losses, formulated follows:
L = Lusk + X Limpontance:
(16)
where À is a hand-tuned scaling factor, with its sensitivity analysis placed in Section 4.4.
Complexity Analysis To better illustrate the effectiveness and clarity of MoG, we provide comprehensive algorithmic table in Appendix and detailed complexity analysis in Appendix E. To address concerns regarding the runtime efficiency of MoG, we have included an empirical analysis of efficiency in Section 4.5.
4 EXPERIMENTS
In this section, we conduct extensive experiments to answer the following research questions: (RQ1) Can MoG effectively help GNNs combat graph sparsity? (RQ2) Does MoG genuinely accelerate the GNN inference? (RQ3) Can MoG help boost GNN performance? (RQ4) How sensitive MoG to its key components and parameters?
4.1 EXPERIMENT SETUP
Datasets and Backbones We opt for four large-scale OGB benchmarks (Hu et al., 2020), including OGBN-ARXIV, OGBN-PROTEINS and OGBN-PRODUCTS for node classification, and OGBG-PPA for graph classification. The dataset splits are given by (Hu et al., 2020). Additionally, we choose two superpixel datasets, MNIST and CIFAR-10 (Knyazev et al., 2019). We select GraphSAGE (Hamilton et al., 2017), DeeperGCN (Li et al., 2020a), and PNA (Corso al., 2020) as the GNN backbones. More details are provided in Appendix
Parameter Configurations For MoG, adopt the m 4 sparsity criteria outlined in Section 3.3, assigning n = 3 different sparsity levels {s1. $2, $y} to each criterion, resulting in a total of K = m n 12 experts. We select h: 2 sparsifier experts for each node, and set the loss scaling factor == le - across all datasets and backbones. By adjusting the sparsity combination, we can control the global sparsity of the entire graph. We present more details parameter settings in Appendix F.4, and recipe for adjusting the graph sparsity in Appendix F.6.
4.2 MoG AS GRAPH SPARSIFIER (RQ1& & RQ2)
To answer RQ1 and RQ2, comprehensively compare MoG with eleven widely- topology- guided sparsifiers and five semantic-guided sparsifiers, as outlined in Table 1, with more detailed explanations in Appendix F.5. The quantitative results on five datasets are shown in Tables and to 12 and the efficiency comparison is in Figure 3. We give the following observations (Obs.):
Obs. MoG demonstrates superior performance in both transductive and inductive settings. As shown Tables 1, and 11, MoG outperforms other sparsifiers in both transductive and inductive settings. Specifically, for node classification tasks, MoG achieves a 0.09% performance improvement while sparsifying 30% of the edges on SEEENN-PRREEISSGGaPpSSAC.. sparsifying 50% of the edges on For graph classification tasks, MoG can remove up 50% of the edges on MNIST with 0.14% performance improvement, surpassing other sparsifiers by 0.99% 12.97% in accuracy.
Even when the ROC-AUC only drops by 0.81 %.
Obs. @ Different datasets and backbones exhibit varying sensitivities to sparsification. As shown in Tables and 10, despite OGBN-PROTER being relatively insensitive to sparsification, sparsification at extremely high levels (e.g., 70%) causes more performance loss for GraphSAGE
7

---

Published as a conference paper at ICLR 2025
Table 1: Node classification performance comparison state-of-the-art sparsification methods. All methods are trained using GraphSAGE, and the reported metries represent the average of five runs. We denote methods with i that do not have precise control over sparsity; their performance is reported around the target sparsity +2% "Sparsity %% refers to the ratio of removed edges as defined in Section 2. "OOM" and "OOT" denotes out-of-memory and out- of-tim respectively.
Dalaset
OGBN-ARXIV (Aucuracy))
OGBN-PROTEINS (ROC-AUC")
Sparsity %
10
30
50
70
10
30
70
Random
70.03.1.48
68.40.5.00
64.32
61.18
16.72
75.03
73.58
72.30.
Topology -iiiieedd
Rank Degree" (Voudigari et al., 2016)
68.13
67.01
65.58 (.0
62.17 (9.32
77.47
76.15
75.59.1.r
74.23
p.17
Local Degree" (Hamann el al., 2016)
68.94
9.55
67.20
65.45
65.5915.m 15.00
76,20
76.05
76.09.
72.88 (2.58
Forest Fire!
(Leskovec et al., 2006)
68.39 La.10
(8.10
67.36.4.15
65,22,0.27
76.50,0.90
15.37
74.29...
.a.1
72.11
G-Spar (Murphy, 1996h)
71.30
69.29
65,56
65.49
77.38
77.36
76.02,1
75.89 (1.5
LSim! (Satuluri et al. 1a)
69. 29.22
66.15
61.07
60.32
76.83 1o.67
76.01 11 .99
74,83,2.37
73.65 La.75
SCAN (Xu 2007)
71.55-0.00
.9.27.2.28
65.14.9.55
64.72,0.77
77.60
76.88.o.08
76.19.1.21
74.32,3.05
ER (Spielman & Srivastana, 2008>
71.63-u.14
69.48 (2.01
69.00
67.15 p4.344
OOT
DSpar (Lio al., 2023b)
71.23 p.os
68.50 22:00
64.79 1o
63.11
18.08
77.34 00.06
77.06go.0
1o.34
76.38
75.49 (1.1
Semantic suideedded
UGS! (Chen et al., 2021)
68.77.a.ra 66.30
66.72.6.77
13.10
76.80
75.46
19
73.28
12
73.31,4.00
GEBT (You et 2022)
69.04.2.4
65.29.0.20
65. 88.888.18
65.62.5.87
76.30
76.17
74.43,2.00
14.12
MGSppr (Wan Schweitzer, 2021)
..22
69.13 (2:96
68. 27 p3:22
66.55
14.04
00M
ACE-GLI" (Wang
2023b)
71.88-u.m
70.14
68.08 (3:43
67.04 pa.es
77.59 10.19
76.14
41 as
75.43 p1. 0OM
13.28
WD-GLI" (Hui et al., 2023)
71.92.0.43
70.21
68, 30
0.19
66.57
AdaGLT (Zhang et 2024a)
71.22,0.3
70.18 1:51
69.13
67.02
77.49
76.76
64 76.00,
2 40
75.44.a.
MoG (Ours))
71.93
70.53
69.06
67.31
77.78
77.49
76.46
76.12
Whole Dataset
71.49 01
77.40
Table 2: Graph classification performance comparison to state-of-the-art sparsification methods. The reported metrics represent the average of five runs.
Dataset
MNIST + PNA (Accuracy f)
OGBN-PPA- + DeeperGCN (Accuracy '))
Spansity %
Random
94.61.2.74
87.23
(1.1
84.82.12.5
80.07 (17.5
75.44_1.66
73.81,4.00
71.97,6.12
69.62,1.47
Topology- guided
Rank Degree! (Voudigari al., 2016)
96.42
94,23 (s.1
92.36_..0
89.20
75.81
11:28
74.99
74.12
70.68
Local Degree! (Hamann et al., 2016)
95.95
93.37
90.11
86.24
76.43
jo.0s
75.87_1.22
72.11
69.93,7.8
Forest Fire! (1 (leskovec et al., 2006)
96.75 00:00
95.42
95.03
(2:02
93.10 4.
76.38
75.33.1.76
73.18
71.49:5.00
G-Spar (Murphy, 1996b)
97.10_0.26
96.59.0.70
94.36_2.00
92.48.4.87
77.68-0.69
73.90.a.19
69.52.
68.10,s.00
LSim" (Satuluri al., 2011a)
95.79_1
92.14.6.21
92.29
91.95 15.40
76.04_1.s
74.40.2.00
72.78.4.81
68.21
SCAN (Xu et al., 2007)
95.81 1.04
93.48,aar
90.18,
86.48,10.8
75.23 1.00
75.18
72.48,
71.11
ER (Spielmmn& & Srivastava, 2008)
94.77 (2.88
93.91
(3-40
93.45
(3.00
91.07 16.2
77.94
75.15 (1.95
73.23
72.74.1.35
DSpar (Liu et al,, 20236)
94.97 99....s
93.80
(a.05
92.23
52
90.48
66.87
76.33 m0
73.37
Lo.77
72.98
(4.13
70.77 (6.32
Sermnticc
ICPG (Sui al., 20233
97.69.0.84
17.39
96.80_n.65
93.77
18.68
77.36,0.27
75.24_1.85
73.18
71.09.0.00
AdaGLT (Zlung et al., 20244)
97.31 .n.0a
96.58 (0.27
94.14 (5.23
92.08
p5.27
76,22 po.rt
73.54 (1.85
70,10,
69.28 (7.83
MoG (Ours)'
97.80 y0.45
97.74
97.79 m0.44
95.30
3.46
78.43 1:34
(o.90
75.23 1.56
73.09
Whole Datnset
97.35
77.09_0.00
compared to DeeperGCN, with the former experiencing 2.28% drop and the latter only 1.07%. which demonstrates the varying sensitivity of different GNN backbones to sparsification. Similarly. we observe in Table 2 that the MNIST dataset shows a slight accuracy increase even with 50% sparsification, whereas the OGBG-PPA dataset suffers a 1.86% performance decline, illustrating the different sensitivities to sparsification across graph datasets.
Obs. MoG can effectively accelerate GNN inference with negligible performance loss. Figure 3 illustrates the actual acceleration effects of MoG compared to other baseline sparsifiers. It is evident that MoG achieves 1.6x lossless acceleration on PRUDN-RRDUCTS+GrappSACCC
and meaning the performance is equal to or better than the vanilla backbone. Notably, on ---POODUTS+Depppeeee than 1. 1.0% performance drop. Overall, MoG provides significantly superior inference acceleration compared to its competitors.
MoG achieves 3.3x acceleration with less
4.3 MoG AS PERFORMANCE BOOSTER (RQ3)
In the context of RQ3, MoG is developed to augment GNN performance by selectively remov- ing limited amount of noisy and detrimental edges, while simultaneously preventing excessive sparsification that could degrade GNN performance. Consequently, we uniformly set the sparsity combination to (90%, 85%, 80%). We combine MoG with state-of-the-ant GNNs both node-level
8

---

Published as a conference paper at ICLR 2025
10
Recurcyy (56)
Accuracy (16)
Vandhe
ROC
Vuziaa lake Déper
Vindll 1an D5ger
12
1.0x
1as
L.
2.6x
12x
14x
30
85x
1.x
2.0x
Inference Speedup (arsiv)
Inference Speedup (proteins)
Inference Speedup (prodhect))
Accuncy (10
Acsuney (3%
Vaeilaa
Vasila
Vialia
18m
12
MaG
1.4
2.5H
1.2
2.0x
1.2
1.x
2.0
Inference Speedug (arsiv)
Infermnce Speedup (proteins)
Inderence Speedup (prodhacta)
The trade-off between inference speedup and model performance for MoG and other sparsifiers. The first and second rows represent results on GraphSAGE and DeeperGCN, respectively, The gray pentagon represents the performance of the original GNN without sparsification.
Figure 3:
Table 3:
Node classification results on OGBN-PROTHINS with RevGNN and GAT+BoT and graph classification results on OGBG-PPA with PAS and DeeperGCN, Mean and standard deviation values from five random runs are presented.
OGBN-PROTEINS (ROC-AUC1)
OGBG-PPA (Accuracy))
Model
RevGNN
GAT+BoT
PAS
DeeperGCN
w/o MoG
88. 0.24
88.09 + 0.16
78.28 + 0.24
77.09 + 0.04
89.04 = 0.72
88.72 + 0.50
78.66 +: 0.47
78.43 1 0.19
w/ MoG
(Sparsity: 9.2%)
(Sparsity: 12.7%)
(Sparsity: 6.6%)
(Sparsity: 10.8%)
and graph-level tasks. The former include RevGNN (Li et al., 2021) and GAT+BoT (Wang et al., 2021), which rank fourth and seventh, respectively, the AGEN-PROTEINS benehmark, and the latter include PAS (Wei et al., 2021) and DeeperGCN (Li et al., 2020a), ranking fourth and sixth on the OGRN-PPA benchmark. We observe from Table 3:
Obs. O MoG can assist the "top-student" backbones to learn better. Despite RevGNN and PAS being high-ranking backbones for OGBN-PROTEINS and OGBG-PPA, MoG still achieves non-marginal performance improvements through moderate graph sparsification: 1.02% on ReyGNN+OGBN- PROTEINS and 1.74% 1 on DeeperGCN+OGGG- serve as a plugin to boost GNN performance by setting a relatively low sparsification rate.
This demonstrates that MoG can effectively
4.4 SENSITIVITY ANALYSIS (RQ4)
To answer RQ4, we perform a sensitivity analysis on the two most important parameters in MoG: the number of selected experts & and the expert importance loss coefficient x. We compared the performance of MoG when choosing different numbers of experts per node, as outlined in Figure 4. The effect of different scaling factors Ả on O DeeeeesnN is shown in Table 4. Based on the results of the above sensitivity analysis, we observe that:
Obs. ① Sparse expert selection helps customized sparsification. can be observed FROM Figure 4 that the optimal & varies with the level of graph sparsity. At lower sparsity (10%), k 1 yields relatively good performance. However, as sparsity increases to 50%, model performance peaks 4, suggesting that in high sparsity environments, more expert opinions contribute to better sparsification. Notably, when & increases to 6, MoG's performance declines, indicating that a more selective approach in sparse expert selection aids in better model generalization. For a balanced consideration of performance and computational efficiency, we set k = in all experiments. We further provide sensitivity analysis results of parameter & on more datasets, as shown Appendix G.2.
Obs. Sparsifier load balancing is essential. We conduct a sensitivity analysis of the expert importance loss coefficient X. A larger À indicates greater variation in the selected experts. As shown

---

Published as a conference paper at ICLR 2025
in Table 4, À 0 consistently resulted in the lowest performance, as failing to explicitly enforce variation among experts leads to the model converging to a trivial solution with the same set of experts (Wang et al., 2024; Shazeer et al., 2017). Conversely, 1e performed slightly better than À = le 2 at higher sparsity levels, supporting the findings in Obs. 5 that higher sparsity requires more diverse sparsifier experts.
Rowwe 191
Raundy
A
1o-2
1o-1
Accssacy
10%
81.1940.00 os
83.32_0.18
83.04g0
30%
79.7740
82.14
82.08
50%
79.40+0.00
81.79+0.21
82.04.0.20
70%
78 18
80.9010.24
80.97 20.28
Figure 4: Sensitivity study parameter k. i..., how many experts are chosen per node. The results are reported based on NGBN-ARXIV+GrapSSACE.
Table 4: Sensitivity study on scaling fac- tor X. The results are reported on OGBN- PROTEINS+DeepeGGNN.
Table 5: Running time efficiency comparison on OGBN-
We consistently 4, k 2, corresponding to utilizing 4 pruning criteria and selecting 2 experts for each node, and vary m E (1, to check how the training cost grows with m increasing.
Sparsity
30%
50%
Metric
Per-epoch Time (s)
Accuracy (%)
Per-epoch Time (s)
Accuracy (%)
Random
18.71 0.14
74.21 0.28
15.42 + 0.24
71.08+ 0.34
AdaGLT
23.55+ 0.20
77.30 + 0.54
21.68 + 0.26
74.38 + 0.79
MoGim 1.
20.18+ 0.14
77.75 + 0.22
18.19 + 0.30
76.10 + 0.49
MoG(m
21,25+ 0.22
78.23 0.29
19.70 + 0.30
76.43 + 0.49
MoGim = 3, K = 12)
23.19 0.18
78.15 + 0.32
20.83 + 0.29
76.98 + 0.49
4.5 EFFICIENCY ANALYSIS AND ABLATION STUDY (RQ4)
Efficiency Analysis To verify that MoG can achieve better results with less additional training cost than the previous SOTA methods, we compare the accuracy and the time efficiency of MoG with AdaGLT on COENN-RODUCT-GrapSSAGGEE as outlined Table We have:
Obs. MoG achieve better accuracy with less additional training cost. It is evident in Table that MoG incurs less additional training cost compared to AdaGLT while achieving significant improvements in sparsification performance. More importantly,
demonstrate that with 1: = 2, MoG does not incur significantly heavier training burdens as the number of sparsifiers increases. Specifically,
s% 50%, the difference in per epoch time between MoG (K 3) and MoG (K = 12) is only 2.63 seconds, consistent with the findings of mainstream sparse MoE approaches (Wang et al., 2024).
Ablation Study We test three different settings of e (in Equation (3)) on OGBN- Graph (1) ~ N' I). (2) 0, and (3) 0.2, presented in Table 15. Our key finding is that randomness in gating networks consistently benefits our model. More results and detailed analysis can be found in Appendix G.3.
CONCLUSION & LIMITATION
In this paper, we introduce new graph sparsification paradigm termed MoG, which leverages multiple graph sparsifiers, each equipped with distinct sparsity levels and pruning criteria. MoG selects the most suitable sparsifier expert based on each node's 's local context, providing customized graph sparsification solution, followed by an effective mixture mechanism on the Grassmann manifold to ensemble the sparse graphs produced by various experts. Extensive experiments four large-scale OGB datasets and two superpixel datasets have rigorously demonstrated the effectiveness of MoG. A potential limitation of MoG is its current reliance 1 --hop decomposition represent each node's 's local context. The performance of extending this approach to k-hop contexts remains unexplored, suggesting possible direction for future research.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Friendly cut sparsifiers and faster gomory-hu trees. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3630-3649. SIAM, 2022.
Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph. Generating sparse spanners for weighted graphs. In SWAT 90: 2nd Scandinavian Workshop on Algorithum Theory Bergen, Sweden, July 11-14, 1990 Proceedings 2. pp. 26-37. Springer, 1990.
Joshua Batson, Daniel A Spielman, Nikhil Srivastava, and Shang-Hur Teng. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8):87-94, 2013.
Thomas Bendokat, Ralf Zimmermann, and P-A Absil. A grassmann manifold handbook: Basic geometry and computational aspects. Advances in Computational Mathematics, 50(1):1-51, 2024.
Ke Chen, Lei Xu, and Huisheng Chi. Improved learning algorithms for mixture of experts in multiclass classification. Neural networks, (000):122912200 1999.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706. PMLR, 2021.
Yuhan Chen, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge, and Nishil Talati. Demystifying graph sparsification algorithms graph properties preservation. arXiv preprint arXiv:2311.12311 2023.
Dawei Cheng, Xiaoyang Wang, Ying Zhang, and Liqing Zhang. Graph neural network for fraud detection via spatial-temporal attention. IEEE Transactions on Knowledge and Data Engineering. 34(8):3800-3813, 2020.
Aidan Clark, Diego de Las Casas, Aurelia Guy, Arthur Mensch. Michela Paganini, Jordan Hoffmann. Bogdan Damoc, Blake Hechtman, Trevor Cai, Sebastian Borgeaud, et al. Unified scaling laws for routed language models. In ICML, pp. 4057-4084 2022.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances Neural Information Processing Systems, 13:13260-13271 2020.
Tim Dettmers, Luke Zettlemoyer, and Zhang. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.048400 2019.
Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov, Clustering on multi- layer graphs via subspace analysis grassmann manifolds. IEEE Transactions signal process- ing, 62(4))905-918, 2013.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint 0rXiv:2003.00983 2020.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, 2021.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 022422. 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp. 1263-1272. PMLR, 2017.
Zheng Gong, Guifeng Wang, Ying Sun, Qi Liu, Yuting Ning, Hui Xiong, and Jingyu Peng. Be- yond homophily: Robust graph anomaly detection via neural sparsification. In Proceedings of International Joint Conference Artificial Intelligence, pp. 2104-2113 2023.
11

---

Published as a conference paper at ICLR 2025
Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner. Structure- pruuctur-prreerrvnng sparsification methods for social networks. Social Network Analysis and Mining, 6:1-22, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of NIPS, 2017.
Mohammad Hashemi, Shengbo Gong, Juntong Ni, Wenqi Fan, B Aditya Prakash, and Wei Jin. A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation. arXiv preprint arXiv:2402.03338, 2024.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint 2tti::22223.555555 2022.
Fenyu Hu, W Liping, I. Qiang, Shu Wu, Liang Wang, and Tieniu Tan. Graphdive: graph classifcation by mixture of diverse experts. In IJCAI, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. In The Eleventh International Conference on Learning Representations, 2023.
Robert A Jacobs, Michael Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural computation, 3(1):79-77, 1991.
Zhongxiao Jia and GW Stewart. An analysis of the rayleigh-rize method for approximating eigenspaces. Mathematics of computation, 70(234):637-647, 2001.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jilliang Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv preprint 1rXiv:2/10.075880 2021.
Michael I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm. Neural computation, 6(2):181-22) 1994.
Zhao Kang, Guoxin Shi, Shudong Huang, Wenyu Chen, Xiaorong Pu, Joey Tianyi Zhou, and Zenglin Xu. Multi-graph fusion for multi-view spectral clustering. Knowledge-Baad Systems, 189:105102 2020.
Suyeon Kim, Dongha Lee, Seong Kang, Seonghyeon Lee, and Hwanjo Yu. Learning topology- specific experts for molecular property prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8291-8299, 2023.
Thomas N. Kipf and Max Welling. Semi- SupeiSuuer Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. Advances in neural information processing systems, 32, 2019.
Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu, Policy-gnn: Aggregation optimization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 461-471, 2020.
Namhoon Lec, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity, arXiv preprint 11x.v:1810.02340, 2018.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. Gshard: Scaling giant models with conditional computation and automatic sharding. arXiv preprint arXiv:2006. 2020.
Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1:2, 2006.
12

---

Published as a conference paper at ICLR 2025
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, arXiv preprint arXiv:2006.07739, 2020a.
Guohao Li. Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449, PMLR, 2021.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based on graph convolutional networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 275-287. Springer, 2020b.
Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, al. Gslb: The graph structure learning benchmark. Advances in Neural Information Processing Systems, 36, 2024.
Guangfeng Lin, Jing Wang, Kaiyang Liao, Fan Zhao, and Wanjun Chen. Structure fusion based on graph convolutional networks for node classification in citation networks. Electronics, 9(3):432, 2020.
Chuang Liu, Yibing Zhan, Jia Wu, Chang Li, Bo Du, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. arXiv preprint arXiv:2204.07321, 2022a.
Junjie Liu, Zhe Xu, Runbin Shi. Ray CC Cheung, and Hayden KH So. Dynamic sparse train- ing: Find efficient sparse network from scratch with trainable masked layers. arXiv preprint arXiv:2005.cm 06870, 2020.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. Proceedings of the ACM Web Conference 2022, pp. 1392-1403, 2022b.
Zheyuan Liu, Chunhui Zhang, Yijun Tian, Erchi Zhang, Chao Huang, Yanfang Ye, and Chuxu Zhang. Fair graph representation learning via diverse mixture of experts. In The Web Conference, 2023a.
Zirui Liu, Kaixiong Zhou, Zhimeng Jiang, Li Li, Rui Chen, Soo-Hyun Choi, and Xia Hu. Dspar: An embarrassingly simple strategy for efficient gnn training and inference via degree-based based sparsification. Transactions on Machine Learning Research, 2023b.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference web search and data mining, pp. 779-787, 2021.
Jiaqi Ma. Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed Chi. Modeling task relation- ships in multi-task learning with multi-gate mixture-of-experts. In ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 1930-1939, 2018
Russell Merris. A survey of graph laplacians. Linear and Multilinear Algebra, (9(1-2)11--1,, 1995.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.0844 2022.
Allan H. Murphy. The finley affair: A signal event in the history of forecast verification. Weather and Forecasting, 11(1):3 - 20, 1996a. doi: wttp:///ww.....1111/3/0000000110
wtt.://oo//.....11......./.. TFAASE>2.0.C022. URL https: http://etrraaaaaatssstsoaaoaoooe
ame wttp//vvewwwe/ooooooooooooee//ee journals/ 2ttp::oo___aaaaa____________ http:///w////////s////// o1t____aaa1000taaaaaaaeeeeeeeee_
wefo/L1/1/1520-044
xml.
Allan H Murphy. The finley affair: A signal event in the history of forecast verification. Weather and
forecasting. 11(1):3-20, 1996b.
Basil Mustafa, Carlos Riquelme, Joan Puigcerver, Rodolphe Jenatton, and Neil Houlsby. Multi- modal contrastive learning with limoe: the language-image mixture experts. arXiv preprint 2YKv:22006002770 2022.
13

---

Published as a conference paper at ICLR 2025
Carlos Riquelme, Joan Puigcerver, Basil Mustafa, Maxim Neumann, Rodolphe Jenatton, André Susano Pinto, Daniel Keysers, and Neil Houlsby. Scaling vision with sparse mixture of experts. In Advances in Neural Information Processing Systems, volume 34, pp. 8583-8595, 2021.
Omer Sagi and Lior Rokach. Ensemble learning: A survey. Wiley intendisciplinary reviews: data mining and knowledge discovery, 8(4):e 1249, 2018.
Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 20/ ACM SIGMOD International Conference Management of data, pp. 721-732, 201 la.
Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD '11, pp. 721-732, New York, NY, USA, 201 1b. Association for Computing Machinery. ISBN 97814503066 14. doi: 10.1145/1989323 D9.1145/199998 1989399.
URL https://ddeet //t::://////./// org/
Hyunjin Seo, Jihun Yun, and Eunho Yang. TEDDY: Trimming edges with degree-based discrimination strategy. In The Twelfth International Conference on Learning Representations, 2024. URL
net/ forum? -ow.:iid--SRSSyy--- ftttps://cpennevieee http:/rtteeettaeeeeeeeeeee
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-expene layer. arXiv preprint arXiv: 170106680,,,6888,, 2017.
Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth anmual ACM symposium on Theory of computing, pp. 563-568, 2008.
Christian Staudt, Alcksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530, 2016.
Yongduo Sui. Xiang Wang. Tianlong Chen, Meng Wang, Xiangnan He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. Journal of Computer Science and Technology, 2023. ISSN (00090000(Print) /1 (18604774((nline)) doi: https:// jost. ict ac en / en http://rrr.eee//////...0///01100
URL
1 1007
Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Qing Meng. Wang Han, and Jiuxin Cao. Multi-level hyperedge distillation for social linking prediction on sparsely observed networks. In Proceedings of the Web Conference 2021, pp. 2934-2945. 2021.
Xiangguo Sun, Hongzhi Yin, Bo Liu, Qing Meng, Jiuxin Cao, Alexander Zhou, and Hongxu Chen. Structure learning via meta-hyperedge for dynamic rumor detection. IEEE Transactions Knowledge and Data Engineering, 2022.
Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2120-2131, 2023a.
Xiangguo Sun, Hong Cheng, Bo Liu, Jia Li, Hongyang Chen, Guandong Xu, and Hongzhi Yin. Self-supervised hypergraph representation learning for sociological analysis. IEEE Transactions on Knowledge and Data Engineering, 2023b.
N. Talati, H. Ye, Vedula, K. Chen, Y. Chen, D. Liu, Y. Yuan, D. Blaauw, A. Bronstein, T. Mudge, and R. Dreslinski. Mint: An accelerator for mining temporal motifs. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pp. 1270-1287, Los Alamitos, CA, https: 2022. 2022.00089.
USA, oct 2022. IEEE Computer Society. doi: 10. 10.1109/MCR0556248 202...000222002.02. ///oi..eeeeeoooeeeoo.oooooeoeece www.eceepteeeoocceeoooooo http://cc....ttt..oooooooooooooa
Kale-ab Tessera, Sara Hooker, and Benjamin Rosman. Keep the gradients flowing: Using gradient flow study sparse network optimization. arXiv preprint arXiv:2
2021.
Elli Voudigari. Nikos Salamanos, Theodore Pupageorgiou, and Emmanuel J Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In 2016 IEEE/ACM International Conference Advances in Social Networks Analysis and Mining (ASONAM), pp. 120-129. IEFF, 2016.
14

---

Published as a conference paper at ICLR 2025
Guihong Wan and Haim Schweitzer. Edge sparsification for graphs via meta- meta-learning. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 2733-2735 2738. IEFE, 2021.
Daixin Wang. Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 598-607. IEEE, 2019a.
Haotao Wang, Ziyu Jiang, Yuning You, Yan Han, Gaowen Liu, Jayanth Srinivasa, Ramana Kompella, Zhangyang Wang, al. Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling. Advances in Neural Information Processing Systems, 36, 2024.
Kun Wang, Yuxuan Liang, Pengkun Wang, Xu Wang. Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets in graph neural networks: dual perspective. In The Eleventh Interna- tional Conference on Learning Representations, 2022a.
Kun Wang, Guohao Li, Shilong Wang, Guibin Zhang, Kai Wang, Yang You, Xiaojiang Peng, Yuxuan Liang, and Yang Wang- The snowflake hypothesis: Training deep gnn with one node one receptive field, 2023a.
Li Wang, Wei Huang, Miao Zhang, Shirui Pan, Xiaojun Chang, and Steven Weidong Su. Pruning graph neural networks by evaluating edge properties. Knowledge-Bar Based Systems, 256:109847, 2022b.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprini urXiv:1909.011
2019b.
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint 1rXiv:2103.13323 2021.
Yuwen Wang, Shunyu Liu, Kaixuan Chen, Tongtian Zhu, Ji Qiao, Mengjie Shi, Yuanyu Wan, and Mingli Song. Adversarial erasing with pruned elements: Towards better graph lottery ticket. arXiv preprint 2rXiv:2308.0299 2023b.
Lanning Wei, Huan Zhao, Quanming Yao, and Zhiqiang He. Pooling architecture search for graph classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 2091-2100, 2021.
Jiancan Wu, Xiang Wang, Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. Self- supervised graph learning for recommendation. In Proceedings of the 44th international ACM SIGIR conference research and development in information retrieval, pp. 726-735, 2021.
Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, Bo Long, et al. Graph neural networks for natural language processing: A survey. Foundations and Trends@ in Machine Learning, 16(2):1 19-328, 2023.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-2744 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, :444):440 24, 2020.
Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33(1):4, 2022.
Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas AJ Schweiger. Scan: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on 2007.
Knowledge discovery and data mining, pp.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
15

---

Published as a conference paper at ICLR 2025
Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin. Early-bird gens: Graph- network co-optimization towards more efficient gen training and inference via drawing early-bird lottery tickets. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp.
8910-8918, 2022.
Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoe Viet Hung Nguyen. Are graph augmentations necessary? simple graph contrastive learning for recommendation. Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval, pp. 1294-1303, 2022.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34: 1111633836694 2021.
Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin Zeng, and Yuxuan Liang. Graph lottery ticket automated. In The Twelfth International Conference on Learning Representations, 2023.
Guibin Zhang, Kun Wang, Wei Huang, Yanwei Yue, Yang Wang, Roger Zimmermann, Aojun Zhou, Dawei Cheng, Jin Zeng", and Yuxuan Liang*. Graph lottery ticket automated. In The International Conference on Learning Representations, 2024a.
Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang, Yongduo Sui, Kai Wang, Yuxuan Liang, Dawei Cheng, Shirui Pan, and Tianlong Chen. Two heads are better than one: Boosting graph sparse training via semantic and topological awareness. arXiv preprint arXiv:2402.01242, 2024b.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proceedings of NIPS, 2018.
Zaixi Zhang and Qi Liu. Learning subpocket prototypes for generalizable structure-based drug design. In International Conference on Machine Learning, pp. 41382-41398. PMLR, 2023.
Xinyu Zhao, Xuxi Chen, Yu Cheng, and Tianlong Chen. Sparse moe with language guided routing for multilingual machine translation. In The Twelfth International Conference Learning Representations, 2024. URL https: htmpps///opet http///pppe//eeeeeeeeeeeeeeeeeet www.rreeieeweeeeeeeeee net/ www.:eeooooo.i////nemmmmm smL.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458-1146. PMLR, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
Liguang Zhou, Yuhongze Zhou, Tin Lun Lam, and Yangsheng Xu. CAME: Context-aware mixture- of-experts for unbiased scene graph generation. arXiv preprint arXiv:2208.07 109, 2022.
Jinguo Zhu, Xizhou Zhu, Wenhai Wang, Xiaohua Wang, Hongsheng Li, Xiaogang Wang, and Jifeng Dai. Uni-Perceiver-MofF Learning sparse generalist models with conditional moes. arXiv preprint 2rXiv:2206.04674. 2022.
A NOTATIONS
We conclude the commonly used notations throughout the manuscript in Table
B DEATILS ON PRUNING CRITERIA
In this section, we will thoroughly explain the four pruning criteria we selected and the rationale behind these choices.
16

---

Published as a conference paper at ICLR 2025
Table 6: The notations that commonly used in the manuscript.
Notation
Definition
(V,
[A,X) X}
Input graph
Input adjacency matrix
X
Node feature matrix
L
Graph Laplacian matrix
COMB(.)
GNN ego-node transformation function GNN message aggregation function Sparse graph combination on function Sparsity ratio (the ratio removed edges)
AGGR(.)
ESM(-)
8%
The i-th node in G Node feature vector for es The I-hop ego-graph for ey Routing network
g()
((g())
The number of total sparsifier experts
k
The number of selected sparsifier experts per node Trainable parameters in the routing network
Wg, Wr
k())
A graph sparsifier
The sparse ego-graph of produced by the m-th graph sparsifier
g
The ensemble sparse graph produced by MoG for e
(() c (eis)
Edges removed surrounding 2
Prior guidance on edge importance eij
Edge degree of Eiy is defined as follows:
Degree (esy) (et)) = (LV(es) ((V()))
+ +(x))))
(17)
Previous methods (Wang et al., 2022b; Seo et al., 2024) have explicitly implicitly used edge degree for graph sparsification. Intuitively, edges with higher degrees are more replaceable. (Wang et al., 2022b) further formalizes this intuition from the perspective of bridge edges.
Jaccard Similarity (Murphy, 1996b) measures the similarity between two sets by computing the portion of shared neighbors between two nodes (u;add v;), as defined below:
JaceradSimilarity 0, 02) [V(v,) (w))
(18)
((,,) UN(c))
Jaccard similarity is widely used for its capacity for detecting clusters, hubs, and outliers on social networks (Murphy, 1996b; Xu al., 2007; Satuluri al., 201 la).
Effective Resistance, derived from the analogy electrical circuits, is applied graphs where edges represent resistors. The effective resistance of an edge is defined as the potential difference generated when a unit current is introduced at one vertex and withdrawn from the other. Once the effective resistance is calculated, a sparsified subgraph can be constructed by selecting edges with probabilities proportional to their effective resistances. Notably, (Spielman & Srivastava, 2008) proved that the quadratic form of the Laplacian for such sparsified graphs closely approximates that of the original graph. Consequently, the following inequality holds for the sparsified subgraph with high probability:
VE Y ()-e)="La Læ I x LLx S (L+))x"aa
(19)
where L is the Laplacian of the sparsified graph, and 0 is small number. The insight is that effective resistance reflects the significance of an edge. Effective resistance aims to preserve the quadratic form of the graph Laplacian. This property makes it suitable for applications relying
17

---

Published as a conference paper at ICLR 2025
the quadratic form of the graph Laplacian, such min-cut/max-fou problems. For computation simplicity, we do not directly utilize the definition of effective resistance, and use its approximation version (Liu et al., 2023b).
Gradient Magnitude, a widely used pruning criterion, prevalent not only in the field of graph sparsification but also in classical neural network pruning. Numerous studies (Lee et al., 2018; Tessera et al., 2021; Dettmers et al., 2019) leverage gradient magnitude to estimate parameter importance. Specifically for graph sparsification, MGSpar (Wan & Schweitzer, 2021) was the first to propose using meta-gradient to estimate edge importance. We consider gradient magnitude a crucial indicator of the graph's topological structure during training. Therefore, we explicitly design some sparsifier experts to focus on this information.
C GRAPH MIXTURE ON GRASSMANN MANIFOLD
In this section, detail how we leverage the concept of Grassmann Manifold to effectively combine different sparse (ego-)graphs output by various sparsifiers.
According Equation (10), each orthonormal matrix represents unique subspace and thus corre- sponds to a distinct point on the Grassmann manifold (Lin et al., 2020). This applies to the eigenvector matrix of the normalized Laplacian matrix (U L[::: p] R=xP), which comprises the first p eigenvectors and orthonormal (Merris, 1995), and thereby can be mapped onto the Grassmann manifold. Additionally, each row of the eigenvector matrix encapsulates the spectral embedding of n
each node in a p-dimensional space, where adjacent nodes have similar embedding vectors. This subspace representation, summarizing graph information, applicable various tasks such as clustering, classification, and graph merging (Dong et al., 2013).
In the context of MoG, we aim to efficiently find the final version that aggregates all the excellent properties of each point's k versions of sparse ego-graph (9m jk Jm=1 on the Grassmann Manifold. Moreover, this should guided by the expert scores computed by the routing network in Section 3.2.
Let Dm and Am denote the degree matrix and the adjacency matrix for Gm (we omit the superscript ())() denoting v; for simplicity in the subsequent expressions), then the normalized graph Laplacian is defined as:
L D (Dm Am D
(20)
Given the graph Laplacian Lm for each sparse graph, calculate the spectral embedding matrix Um through trace minimization:
min tr Lm Um), s.t. U U I,
(21)
Un CR..
which can be solved by the Rayleigh-Rizz theorem. As mentioned above, each point the Grassmann manifold can be represented by orthonormal matrix Y E [R((())) whose columns span the corresponding p-dimensional subspace in IR (Vx())) The distance between such subspaces can be computed as a set of principal angles {0,)*_ between these subspaces. (Dong al., 2013) showed that the projection distance between two subspaces Y, and Y, can be represented as separate trace minimization problem:
Y1. Y2
sin 0g = tr Y.Y.Y,Y))
(22)
proj
Based on this, we further define the projection of the final representative subspace U and the & sparse candidate subspace (mm m
( (U, ( )
Σ Proj (U (U, =
tr (U
(23)
which ensures that individual subspaces close to the final representative subspace U.
Finally, to maintain the original vertex connectivity from all & sparse ego-graphs and emphasize the connectivity relationship from more reliable sparsifiers (with higher expert scores), propose the
18

---

Published as a conference paper at ICLR 2025
following objective function:
k
& pxk Σ
min U. (Pm
E(i
tr (OU
Un U
(24)
M==1
m=1
where E represents the expert score of the node vs mntth sparsifier expert. Based on Equations (21) and (24), we present the overall objective:
min UWER NOO XP
tr(U Lm
U
E (f U
88 U
U =I.
(25)
(1) node connectivity
(2) subspace distance
For simplicity, we omit the superscript (4) in the following content. Substituting Equation (23) into Equation (25), we obtain:
Em (pxk- - Σ UU U/))
min
U.L
(26)
m=1
m=1
Further simplification by neglecting constant terms like Em p k yields:
ur(U" Lm U) - Em
U SLU
(27)
m=1
Reorganizing the trace form of the second term, we obtain:
tintr
UT
Lm
Em
U UT J
SLU'U=L
(28)
At this point, the optimization problem essentially becomes a trace minimization problem, and thus the solution this minimization problem essentially the between U and U, which is:
L
Em
Σ
U
U m
[L Em U U
(29)
km1
Since computations involving the Grassmann manifold unavoidably entail eigenvalue decomposition, concerns about computational complexity may arise. However, given that MoG only operates mixtures on the ego-graph each node, such computational burden is entirely acceptable. Specific complexity analyses presented in Appendix E.
C.1 FURTHER DISCUSSION ON THE USE OF GRASSMANN MANTFOLD
In this section, we visualize the impact of different ego-graph ensemble methods on the eigenvalue distribution. Specifically, we select node [2458] from the OGBN-ARXIV dataset and compare its original ego-graph, the sparse ego-graphs produced by three different sparsifiers, and the ensembled ego-graphs obtained through simple averaging and Grassmann optimization. The eigenvalue distri- butions are shown in Figure 5. As observed, when the three candidate sparse graphs are combined through simple averaging followed by sparsification, the resulting graph's 's eigenvalue distribution can deviate significantly from the original distribution. In contrast, the Grassmann ensembling method effectively preserves the spectral properties of each graph view, resulting in a sparse ego-graph whose eigenvalue distribution closely aligns with that of the original graph.
D ALGORITHM WORKFLOW
The algorithm framework is presented in Algo. 1.
19

---

Published as a conference paper at ICLR 2025
Original Graph
Sparse Graph 1
Sparse Graph
Sparse Graph 3
Average Craph
Eigenvalus aauua
Grassmann Sparse Graph
0
6
10
Eigenvaluc Index
Figure 5: Case study the eigenvalue distribution of ego-graph.
E COMPLEXITY ANALYSIS
In this section, delve into comprehensive analysis of the time and space complexity of MoG. Without loss of generality, we consider the scenario where MoG is applied to vanilla GCN. is worth recalling that the forward time complexity of vanilla GCN is given by:
OLL x | X D L [V] D²),
(30)
where L is the number of GNN layers, [3 and [V] denotes the number of edges and nodes, respectively, and D the hidden dimension. Similarly, the forward space complexity of GCN is:
O(L |E| L D2 + L |V] D)
(31)
When MoG is applied to GCN, each sparsifier expert rc(-) essentially introduces additional complexity equivalent to that of an FFN(-), :) as depicted in Equation (9). Incorporating the Sparse MoE-style structure, the forward time complexity of GCN+MoG becomes:
O(L x E x D L x [V] D + x |8l Dx
(32)
where D represents the hidden dimension the nerdaro network Equation (9) and & denotes the number of selected experts. Similarly, the forward space complexity is increased to:
O(L x [ + L 2 + L x [V] x D &s x [E] x D x D*).
(33)
It is noteworthy that we omit the analysis for the routing network, as its computational cost is meanwhile negligible compared the of selected experts, since both W, R and W,, RKFF; is in much smaller dimension that the weight matrix W FxF in GCN.
Furthermore, we present the additional complexity introduced by the step of graph mixture on the Grassmann manifold. For each center node's sparse ego-graphs, need compute the graph Laplacian and the eigenvector matrix, which incurs an extra time complexity of O x [ ))):
compute the Laplacian L(t) of the final ensemble sparse graph, additional complexity of Ok x g 2 x p) is required. the end, the complete time complexity of MoG is expressed as:
[8]
[ 1
3
[ V
O IXIEXxD+LXIXXDPPXXXXXXX
(34)
vanilla GCN
sparsifier experts
graph mixture
To empirically verify that MoG does not impose excessive computational burdens GNN backbones, we conduct experiments in Section 4.5 to compare the per-epoch time efficiency metric of MoG with other sparsifiers.
20

---

Published as a conference paper at ICLR 2025
Algorithm 1: Algorithm workflow of MoG
Input :g = X), GNN model f(g, θ), epoch number Q.
: graph Gzuh (V,E") for iteration + to Q do
Ego-graph decomposition
Decompose into ego-graph representations (g(1), g()), (.(N).
* Sparsifien fier expert a allocation
*/
for node i + to [V] do
Calculate the total K expert score of by routing network (x;));
> Eq.
Select & sparsifier expert for node e; by (
b Eq.
end
* Produce sparse graph condidates for iteration + to V do
for sparsifier index m <- to do Sparisifier x" determines which edges remove by
Eg = Topk (-C"M(E), [|gt)] x 1%
D Eq.
Produce sparse graph candidate g xm (g (16)) g6) cl0) }. end
+ Ensenmble sparse graphs on Grassmann manifold Calculate the ensemble graph's graph Laplacian by
*/
L -
Lm (() U
U
D Eq. 12
Obtain 0y 's final sparse graph by ESM(IG = (D D L x()); 1
Eq. 13
Compute vs's weighted sparsity by s 500%
8 Em=1 5n
> Eq. 14
Post-sparsify go: go < [TopK (i), |g(0| x 8)) x()):
b Eq. 14
end
/ Combine ego graphs
x/
- (G(1), g(2) g(PD)
/* Standard GNN training
x/
Feed the sparse graph & into GNN model for any kinds of downstream training:
b Eq.
Compute loss Lins + A Limpontance'
b Eq. 16
Backpropagate to update GNN (G, θ), routing network s and sparsifiers (N² 1
mm=1"
end
EXPERIMENTAL DETAILS
F.1 DATASET STATISTICS
We conclude the dataset statistics in Tab.
Table 7: Graph datasets statistics.
Dataset
#Graph
#Node
#Edge
#Classes
Metric
OGRN-ARXIV CGRN-PROTEINS
169,343
1,166,243
40
Accuracy ROC-AUC
132,534
39,561,252
OGRN-PRODUCTS
2,449,029
61,859,140
47
Accuracy
OGBG-PPA
158,100
243.4
2,266.1
47
Accuracy
MNIST
70,100
50.5
564.5
10
Accuracy
CIFAR- 10
60,000
117.6
914.0
10
Accuracy
21

---

Published as a conference paper at ICLR 2025
F.2 EVALUATION METRICS
Accuracy represents the ratio of correctly predicted outcomes to the total predictions made. The ROC-AUC (Receiver Operating Characteristic-Ai Area Under the Curve) value quantifies the probability that randomly selected positive example will have a higher rank than a randomly selected negative example.
F.3 DATASET SPLITS
For node-level tasks, the data splits for OGBN-ARXIV, OGBN-PROTEINS, and OGBN-PRODUCTS were provided by the benchmark (Hu al., 2020). Specifically, for OGBN-ARXIV, we train on papers published until 2017, validate on papers from 2018 8 and test on those published since 2019. For
protein nodes were segregated into training, validation, and test sets based on their species of origin. For OGBN-PRODUCTS we sort the products according to their sales ranking and use the top 8% for training, next top 2% for validation, and the rest for testing.
For graph-level tasks, we follow (Hu et al., 2020) for OGBG-PPA Concretely, we adopt the species split, where the neighborhood graphs in the validation and test sets are extracted from protein associa- tion networks of species not encountered during training but belonging to one of the 37 taxonomic groups. This split stress-tests the model's capacity to extract graph features crucial for predicting taxonomic groups, enhancing biological understanding of protein associations. For MNIST and CIFAR-10, consistent with (Dwivedi et al., 2020), we split them to 55000 train/5000 validation/ 10000 test for MNIST, and 45000 train/5000 validation/1000 test for CIFAR10, respectively. We report the test accuracy at the epoch with the best validation accuracy.
F.4 PARAMETER SETTING
Backbone Parameters For node classification backbones, we utilize 3-layer Graph- SAGE with hidden_dim E {128, 256). As for DeeperGCN, we set layer_num = 28, block same as in https://github:
rest, hidden_din dim = 64. The other configurations are the /masmmmttrrree
httm//igggaaime/eeepa. httee//eee_cccsttoccceeeeeeeeeee examples comples/ogbi http//gb///o/// http:/ooonpprroiiine For graph classification backbones, we leverage 4-layer PNA with weiidde__diiie = 300. Rest configurations are the same as in https: / / gighub...... com/ Lukecavabareet/ppa.
MoG parameters We adopt the m sparsity criteria outlined in Section 3.3, assigning
different sparsity levels {s1, 82, } to each criterion, resulting in a total of K m X 12 experts.
We select 2 sparsifier experts for each node, and set the loss scaling factor X = 1e 2 across all datasets and backbones.
All the experiments are conducted on NVIDIA Tesla V100 (32GB GPU), using PyTorch and Py Torch Geometric framework.
F.5 SPARSIFIER BASELINE CONFIGURATIONS
Topology-basee sparsification
- RRnn Degree (Talati et al., 2022): The Rank Degree sparsifier initiates by selecting a random set of "seed" vertices. Then, the vertices with connections these seed vertices ranked based on their degree in descending order. Subsequently, the edges linking each seed vertex to its top-ranked neighbors are chosen and integrated into the sparsified graph. The newly added nodes in the graph act as new seeds for identifying additional edges. This iterative process continues until the target sparsification limit attained. We utilize the implementation in (Chen al., 2023).
Local Degree (Hamann et al., 2016): Local Degree sparsifier, similar to Rank Degree, incor- porates edges to the top deg(v) (1) neighbors ranked by their degree descending order, where [0, 1] represents the degree of sparsification.
Forest Fire (Leskovec et al., 2006): Forest fire assembles "burning" through edges probabilisti- cally, and use the implementation in (Staudt al., 2016).
-
22

---

Published as a conference paper at ICLR 2025
G-Spar (Murphy, 1996b): G-Spar sorts the Jaccard scores globally and then selects the edges with the highest similarity score. We opt for the code from (Staudt et al., 2016).
LLcaal Similarity (Satuluri et al., la): Local Similarity ranks edges using the Jaccard score and computes log (rank((e;)) /) http//oo(dcog) (dcg((e)) as the similarity score, and selects edges with the highest similarity scores. We utilize the implementation in (Chen et al., 2023).
SCAN (Spielman & Srivastava, 2008): SCAN uses structural similarity (called SCAN similarity) measures to detect clusters, hubs, and outliers. We utilize the implementation (Chen et al., 2023)
DSpaar (Liu al., 2023b): DSpar is an extension of effective resistance sparsifier, which aims to reduce the high computational budget of calculating effective resistance through an unbiased approximation. We adopt their official implementation (Liu et al., 2023b).
Semantic-based sparsification
UGS (Chen et al., 2021): We utilize the official implementation from the authors. Notably, UGS was originally designed for joint pruning of model parameters and edges. Specifically, it sets separate pruning parameters for parameters and edges, namely the weight pruning ratio Pa and the graph pruning ratio Pg- In each iteration, a corresponding proportion of parameters/edges pruned. For a fairer comparison, we set pe 0%, while maintaining Pg E (5%, 10} (consistent with the original paper).
GEBT (You et al., 2022): GEBT, for the first time, discovered the existence of graph early- bird (GEB) tickets that emerge at the very early stage when sparsifying GCN graphs. (You et al., 2022) has proposed two variants of graph early bird tickets, and opt for the graph- sparsification-only version, dubbed GEB Ticket Identification.
Meta-gradient sparsifier (Wan & Schweitzer, 2021): The Meta- Meta-gradiem sparsifier prunes edges based on their meta-grasn veea-graddiet importance scores, assessed over multiple training epochs. Since no official implementation is provided, we carefully replicated the results following the guidelines in the original paper.
ACE-GLT (Wang et al., 2023b): ACE-GI GCE inherits the iterative magnitude pruning (IMP) paradigm from UGS. Going beyond UGS, it suggested mining valuable information from pruned
after each round of IMP, which in the meanwhile doubled the computa- tional cost of IMP. We utilize the official implementation provided by (Wang et al., 2023b), and set pa = 0%, Pg E (5%, 10}.
WD-GLT (Hui et al., 2023): WD-GLT also inherits the iterative magnitude pruning paradigm from UGS, so we also set Pg 0%, Pg (5%, 10%} across all datasets and backbones. The perturbation ratio is tuned among {0, 1). Since official implementation is provided, carefully reproduced the results according to the original paper.
AdaGLT (Zhang et al., 2024a): AdaGLT revolutionizes the original IMP-based graph lottery ticket methodology into an adaptive, dynamic, and automated approach, profi- cient in identifying sparse graphs with layer-adaptive structures. We fix 1ee = 0%, fl (le 6, le 5, le - 4, le 3, le 2), w across datasets and backbones.
F.6 ADJUSTING GRAPH SPARSITY
In Table 8, provide detailed guidelines how to achieve the desired global sparsity by adjusting the three sparsity levels (81, 82, 83} in MoG across six datasets.
G ADDTIONAL EXPERIMENT RESULTS
G.1 RESULTS FOR RQ1
We report the performances of MoG and other sparsifiers on OGEN-PRODUCTS Table
G.2 SENSITIVITY ANALYSIS OF PARAMETER K
Based on the experiments in Section 4.4, we further provide sensitivity analysis results OGBN- PROTEINS+RevGNY as shown in Table 13. It can be observed that MoG achieves peak performance l {2, 3) and begins decline after A: > 4, which is consistent with finding in Observation 6.
23

---

Published as a conference paper at ICLR 2025
Table 8: The recipe for adjusting graph sparsity via different sparsifier combinations.
Datasets
81
$2
$3
1 8%
1
0.9
0.8
[88.0%,90.99%
0.8
0.7
0.5
[69.0%,.3.2%%]
OGBN-ARXIV
0.6
0.5
0.3
[49.5%.52.7%
0.5
0.3
0.15
[27.1%, 31.6%)
1
0.9
0.8
[86.1%.89.33
0.8
0.7
0.6
[65.1%.69.2%%
OGBN-PROTEINS
0.6
0.5
0.4
[45.2%,44933%)
0.4
0.3
0.2
129.2%,31.1%%
1
0.9
0.8
[90.1%,93.25%
0.8
0.7
0.6
169.3%,72.0%%
OGBN-PRODUCTS
0.6
0.5
0.4
[51.5%,54.9%%
0.4
0.3
0.2
[28.7%_36.0%%
1
0.85
0.8
[90.4%.92.75
0.8
0.5
0.4
[67.1%,668.3%
MNIST
0.6
0.3
0.2
[46.2%,,49.3%)
0.35
0.1
0.1
[29.8%_31.3%
1
0.85
0.8
[90.6%,93.7]
0.8
0.5
0.4
[67.5%
CIFAR 10
0.6
0.3
0.2
[47.7%
0.35
0.1
0.1
[30.1%.31.3%
0.95
0.9
0.8
[86.5%,88.
0.8
0.65
0.6
[68.0%
OGBG-PPA
0.6
0.5
0.3
[47.8%,48.9%
0.4
0.3
0.15
[30.1%.33.6%)
Table 9: Node classification performance comparison to state-of-the-art sparsification methods. All methods are trained using GraphSAGE, and the reported metrics represent the average of five runs. We denote methods with that do not have precise control over sparsity; their performance is reported around the target sparsity +.2%. We do not report results for sparsifiers like for OOT issues and those like UGS for their infeasibility in inductive settings (mini-batch training).
Dataset
OGBN-PRODUCTS (Aceuracy 1)
Sparsity
10
30
50
Random
76.99 jo.999.1.08
11.05
74.21 13.88
L3.28
71.08
L0.95
67.24
Rank Degree* (Voudigari et al., 2016)
76.08 11.96
74.26
71.85
(..19...9
70.66_7.as (7.38
Topology
Local Degree"
(Hamann et al., 2016)
77.19.1.65
76.40
.1.4
72.77
J5.27
72.48_5.50 _6.56
72.48,
G-Spar (Murphy, 1996b)
16.15
74.20 L3.84
71.55
(6.49
69.42,.8.z
LSim! (Satuluri al., 201 la)
77.96.o.o8
74.98
,2.06
72.67
J5.37
70.43 J7.61
SCAN (Xu al., 2007)
76.30
74.33
L3.71
71.25
J6.79
71.12,6.00 66.92
DSpar (Liu et al., 2023b)
78.25
75.
12.98
74.57
J3.47
73.16 .1.88
Sema
AdaGLT (Zhang et al., 2024a)
78. 15
77.30
LO.74
74.38
(3.66
73.04
15.00
MoG (Ours)t
78.77 H0.73
78.15 F0.11
76.98
1.06
74.91 LA.17
Whole Dataset
78.04
24

---

Published as a conference paper at ICLR 2025
Table 10: Node classification performance comparison to state-of-the sparsification methods. All methods are trained using DeeperGCN, and the reported metrics represent the average of five runs. We denote methods with i that do not have precise control over sparsity; their performance is reported around the target sparsity +2%. "OOM" and "OOT" denotes out-of-memory and out-of-time, respectively.
Dataset
OGBN-ARXIV (Accuracy f)
Sparsity %
70
Random
70.66 .1.28
68.74ga.20
65.38 ja.56
63.5518.30
Rank Degree", (Voudigari et al., 2016)
69.44_2.50
67.82
65.08 (6.86
63,19
Topology eey-ggddddd
Local Degree (Hamann et al., 2016)
08..7733.15
67.92
66.10
65.97
Forest Fire
(Leskovec et al., 2006)
68.70
68.95
67.23 j4.71
67.29 14.65
G-Spar (Murphy, 1996b)
70.57
70.15
68.77..3.15
65.26 16.68
LSim (Satuluri et al., 201 10)
69.33
67.19
63.55 18.39
62.20
SCAN (Xu et al., 2007)
71.33, _..63
(2.72
67.88 (4.06
64.32 (7.62
ER (Spielman & Srivastava, 2008)
71.33 _0.61
69.6512.29
69.08 $2.86
67.10 (4.84
DSpar (Liu al., 2023b)
71.65.o.28
70.66
68.03.g3.01
67.25 (4.65 (4.60
UGS (Chen et al., 2021)
72.01-0.93
70.29 (1.65
68.43
67.85 14.09
Semantic-guice guided
GEBT (You et al., 2022)
70.22_1.72
69.40
07.8444.10
67.49. 44445
MGSpar (Wan & Schweitzer, 2021)
70.02.1.92
69.34
68.02 j3.92
65.78, 18.16
ACF--GIT (Wang et al., 2023h)
72.13-0.19
71.96
69.1312.88
07.9314.01
WD-GLT (Hui et al., 2023)
71.92. .0.02
70.21
68.30 L3.64
66.57 15.37
AdaGLT (Zhang al., 2024a)
71.98-o. -0.88
70.44.1.0 (1.00
69.15 (2.79
68.05 33.80
MoG (Ours)
72.08 0.14
71.98
10.05
69.86
-2.08
68.20 (3374
Whole Dataset
71.93
Table 11: Node classification performance comparison to state-of-the sparsification methods. All methods are trained using DeeperGCN, and the reported metrics represent the average of five runs. We denote methods with i that do not have precise control over sparsity; their performance is reported around the target sparsity +2%. "OOM" and "OOT" denotes out-of-memor and out-of-time, respectively.
Dataset
OGBN-PROTEINS (ROC-AUC T)
Sparsity %
10
30
50
70
Random
78.92 80.18
|2.66
33.83
76.57
(6.16
72.69.10 110.0
Topology -guided
Topology-guided
Rank Degree! (Voudigari et al., 2016)
10.14
79.05
78.59,4.13
76.22.jo.1
Local Degree (Hamann al., 2016)
79.40
79.83
j3.90
78.50
(8.50,4.22
78.25
j4.48
Forest Fire
(Leskovec et al., 2006)
81.4 81.49 11.24
78.47
14.26
76_14
73.89
19.64
G-Spar (Murphy, 1996b)
81.5611.17
81.12
19.13
79.13
L3.60
77.45
j8.28
LSim² (Satuluri et al., 201 1a)
80.30
79.19
19.19,3.54
J3.54
77.13 L5.66
77.85
(4.68
SCAN (Xu et al., 2007)
81.60
80.19
2.544
81.53
81.53.1120
78.58.4.18
ER (Spielman & Srivastava, 2008)
OOT
DSpar (Liu et al., 2023b)
81.46
80.57
u2.16
77.41 15.82
75.35
UGS (Chen et al., 2021)
82.33 10.40
81.54
78.75
14.98
76.40,6.a3
Semantic-guided
GEBT (You et al., 2022)
80.74 12.99
80.22
22.51
79.81
(3.92
76.05 (6.05_6.68.
MGSpar (Wan & Schweitzer, 202 1)
OOM
ACE-GLT (Wang et al., 2023b)
82.93 y0.80 f2.93
82.01
10.72
81.05
g1.6
75.92
WD-GLT! (Hui al., 2023)
OOM
AdaGLT (Zhang et al., 2024a)
82.60
82.76 82.60Ja.13 pa.18
80.55
12.18
78.42
(4.31
MoG (Ours)?
83.32 10.41
82.14
|0.se
81.92 (0.8
80.90
11833
Whole Dataset
82.73 $ 0..03.000
25

---

Published as a conference paper at ICLR 2025
Table 12: Graph classification performance comparison to state-of-the-arr sparsification methods. All methods are trained using PNA, and the reported metrics represent the average of five runs. We denote methods with i that do not have precise control over sparsity; their performance reported around the target sparsity +2%.
Dataset
CIFAR- 10 (Accuracy 1)
Sparsity %
10
30
50
70
Random
68.04.1.70
66,81 (2.93
63.35
62.144
Rank Degree' (Voudigari et al., 2016)
68.27 11.77
67.14_2.60
64.05 (5.69
60.22|.9.52
Topology
Local Degree!
(Hamann al., 2016)
68.10...d6
67.29. L2.45
64.96 64.9644.78
61.77 18.97
G-Spar (Murphy, 1996b)
67.13.2.61
65.06 .4.68
64.86.4.65
62.92 16.82
I.Sim (Satuluri et al., 201 la)
69.75fo.01
67.33_p..
66.58 66.5813.16
64.86
SCAN (Xu al., 2007)
68.25 L1.49
66.1 L3.63
64.59 15.15
63.20
DSpar (Liu et al., 2023b)
68.9440.53
66,80 .2.94
64.87 14.67
64.10
Sema
AdaGLT (Zhang et al., 2024a)
69.7770.02
67.97.1.75
65.06 65.06.44.68
64.22 16.52
MoG (Ours)
70.04.0.30
69.80 10.994
68.28
-1.46
66.55 1-319
Whole Dataset
69.7
69.74
Table 13: Sensitivity analysis of parameter & when applying MoG to OONN-POOTEIN--RCGNN
MoG 88.37
89.04
89.09
88.55 88.20
We also reported the impact of selecting different values of & on the per-epoch training time and inference time, when applying MoG to CEEN-ARXIV+GraphSSS that although the training and inference cost of MoG increases as the number of selected experts increases, this additional cost is not significant: when A doubles from 2 to 4, the inference time only increases by 23%. More importantly, we can already achieve optimal performance with E (2,3) 3). so there is no need to select too many experts, therefore avoiding significant inference delay.
in Table 14. It can be observed
Table 14: Sensitivity analysis of parameter i when applying MoG to OGEN-ARKIV-GGAAAAAAEE
Sparsity
Selected Expert k
Per-Eppoch Time Inference Time
Acc.
30%
2
0.213
0.140
70.53
30%
0,241
0.161
70.48
30%
4
0.266
0.173
70.13
30%
5
0.279
0.190
69.57
G.3 ABLATION STUDY ON THE NOISE CONTROL OF THE ROUTER NETWORK
We test three different settings of epsilon on GraphSAGE+Ogbnn Arxiv:: (1) E ~
0.
and (3) < 0.2, and report their performance under different sparsity levels in Table 15. We that trainable noisy parameters always bring the greatest performance gain to the model, which is consistent with previous practices in MoE that the randomness in the gating network is beneficial.
G.4 SENSITIVITY ANALYSIS OF PARAMETER P
How is determined in Equation (10)? Since the egographs of individual nodes vary in size, calculate p proportionally as = 7 [Vex)]], where rр % represents the ratio of selected columns in the ego-graph of U,. In our experiments, we r,, % 50% for simplicity.
What is its impact on performance? We conduct additional tests on GraphSAGE + OGBN-ARXIV using different values of r2%, as shown in Table 16. It can be observed that while excessively small values of p negatively impact the performance of MoG, the model remains largely insensitive to variations in p within broader range.
26

---

Published as a conference paper at ICLR 2025
Table 15: Ablation study on the noise control of the router network V. c ~ (0, I) corresponds to the original setting in our paper, c corresponds to completely remove the noise modeling, and 0.2 corresponds to fixing the noise coefficient.
Sparsity
Train Ace
Valid Ace
Test Acc
~~ (0.
10%
77.20
72.68
71.93
70.53
50%
72.45
69.54
69.06
10%
71.27
30%
75.99
71.15
70.14
50%
72.09
68.34
67.05
0.2
10%
76.98
72.22
71.75
30%
75.98
71.48
70.27
50%
73.15
68.45
Table 16: The sensitivity analysis of rp % on GrapISAGE+OGBN with 50.
7
0.1
0.3
0.5
0.7
30
69.92
70.03
70.53
70.41
= 50
68.27
69.12
69.06
69.19
G.S EXPERIMENTS INCORPORATING GLOBAL INFORMATION
While MoG prunes edges based on the node's local context, the edge importance evaluation func- ct (er)), can incorporate multi-hop or even global tion in Equation (9), C" (ex, = FFN (a,, Ijj Ty,
information. Specifically, we explored two approaches and conducted supplementary experiments accordingly:
Expanding v, to xo with aggregated K-hop features: To integrate multi-hop informa- tion, expanded n, into
x (K) CONCAT(N)), (..,,,,,,K)))))
where (1(
Nu(e) EveNa Ty represents the K-hop features for node with (u
denoting the K-hop neighbors of
2. Incorporating cm (ees) with prior global edge significance: For the em (eiy) function in Equation (9), we consider global edge significance as prior guidance. This involved computing edge importance metrics such as PageRank, Betweenness Centrality, or Eigen- vector Centrality across the entire graph and passing them to each ego graph to improve edge evaluation.
Table 17: Performance of MoG-Khop with multi-hop features and MoG-m incorporating global edge significance as prior guidance on GraphSAGE+OGBN- ARXIVV (node classification, 50% sparsity) and DeeperGCN+OGBG- (graph classification, 50% sparsity).
Method
GrapDSAGGEOOGE-AARTT
DeeperGCN+OGBG-PPE
MoG-1hop
69.06
75.23
MoG-2hop
69.54
75.79
MoG-3hop
69.27
76.38
MoG-PageRRank
69.03
75.70
BoGG-Betweenness
69.14 14
75.68
Eigeenvgeee
68.74
75.14
The results in Table 17 showcase that the performance gain from integrating global information varies across different tasks: in tasks such as graph classification, which rely more heavily on global information, MoG-3hop results in notable 1.15% accuracy improvement compared to MoG-
27

---

Published as a conference paper at ICLR 2025
However, in node classification tasks, the gains from both hop expansion and global priors relatively limited.
G.6 ADDITIONAL EXPERIMENT WITH LINK PREDICTION
Table 18:
Additional experiments on DeppeGGN++OGB--OLLAA. The reported metries represent
the average of five runs. (Metric = Hits@ 50, Baseline = 53,53%)
Sparsity %
10
30
50
Random
52.92
47.38
44.62
Local Degree
53.57
51.80
49.92
UGS
53.65
52.25
49.67
AdaGLT MoG
53.82
53.61
52.69
53.80
53.77
53.28
Table 19: Additional Experiments on GIN+PUBMED. The reported metrics represent the average of five runs. (Metric ROC-AUC, Baseline 0.895)
Sparsity %
10
30
50
Random
0.889
0,850
0.817
Local Degree
0,905
0.875
0.846
UGS 0.902
0.862
0.839
AdaGLT 0.898
0.884
0.851
MoG
0.910
0.893
0.862
We follow the experimental setting in Chen et al. (2021) to test link prediction on PUBMED and OGBL-COLLAB From Tables 18 and 19, we can further verify that MoG also effective the link prediction task, demonstrating strong generalization across diverse datasets and backbones.
H BROADER IMPACT AND DISCUSSION
H.1 BROADER IMPACT
MoG, novel concept in graph sparsification, holds vast potential for general application. It allows for the sparsification of each node based on its specific circumstances, making it well-suited to meet the demands of complex real-world scenarios such financial fraud detection and online recommender systems, which require customized approaches. More importantly, MoG provides selectable pool for future sparsification, enabling various pruning algorithms to collaborate and enhance the representational capabilities of graphs.
H.2 KEY CONTRIBUTIONS OF MoG
Briefly put, contributions can be summarized as:
Node-Granular Customization: We propose a new paradigm of graph sparsification by introducing, for the first time, method that customizes both sparsity levels and criteria for individual node modeling based on their local context.
MoE for Graph Sparsification: We design an innovative and highly pluggable graph sparsifier, dubbed Mixture of Graphs (MoG), which pioneers the application of Mixture-of- Experts (MoE) in graph sparsification, supported by robust theoretical foundation rooted in the Grassmann manifold.
Empirical Evidence: Our extensive experiments on seven datasets and six backbones demonstrate that MoG is (1) a superior graph sparsifier, maintaining GNN performance losslessly 8.67% 50.85% sparsity levels; (2) computational accelerator, achieving a tangible 1.47 2.62x inference speedup; (3) a performance booster, which boosts ROC-AUC by 1.81 OGRG-MOLHIV, 1.02% OGBN-PROTEINS.
28

---

Published as a conference paper at ICLR 2025
H.3 REAL-WORLD USE CASES
SpMM frequently represents the primary computational bottleneck in GNNs, accounting for 50%-70% of the total computational load (Liu al., 2023b), thereby severely limiting their scalability on large graphs. There are some real use cases:
Online Fraud Detection: Financial transaction graphs are often massive, incurring signifi- cant SpMM costs during inference. The high computational cost of SpMM hinders the rapid detection and response required for financial fraud prevention, compromising user security.
Recommender Systems: Large-scale user-item interaction graphs in recommender systems face substantial SpMM costs, restricting GNN deployment. MoG enhances the feasibility and responsiveness of GNNs in recommender systems.
Network Architecture Search (NAS): NAS involves optimizing parameters for each archi- tecture. The large parameter and gradient storage requirements of GNNs intensify memory demands. Moreover, NAS evaluates numerous candidate architectures, each requiring multiple training and validation cycles, amplifying SpMM's computational cost.
Federated Graph Learning: The large-scale graph structures in Federated Graph Learning entail significant local SpMM computations and parameter transmission. MoG mitigates this by extracting sparse structures from local GNNs, reducing the parameter load sent to the central server.
We believe MoG's potential alleviate SpMM bottlenecks could unlock broader applications of GNNs across these domains.
I POST-SPARSIFIED EGO-GRAPHS ASSEMBLING
we provide a detailed explanation of how post-sparsified ego-graphs are assembled as follows:
M
M
-- --(ssign (TopK(A, | 5%)) X]: 5%
1
(0% A
Σ / AAO)
where f WOOINNNO + RM denotes the mapping of edges from the ego-graph to the global graph. After generating the post-sparsified ego- ago-graphs, we compute the global sparsity s% by averaging the sparsity levels of each ego ego-graph and applying function f that maps each ego- ego-graph into the global graph. Afterward, we sum the weights of unpruned edges across all ego-graphs to form the weighted adjacency matrix A. Finally, we prune the global graph to achieve the target sparsity s%, yielding the final sparsified graph.
29


Reviews:
[{"review_id": "l56c9a1A0E", "reviewer": "Reviewer_f3PB", "summary": "This paper presents a novel graph sparsification method, Mixture-of-Graphs (MoG), to optimize Graph Neural Networks (GNNs) for large-scale graphs. MoG dynamically selects node-specific sparsification levels and criteria, improving computational efficiency and performance.\nInspired by the Mixture-of-Experts framework, MoG employs multiple sparsifier experts, each with distinct sparsity settings and pruning criteria. This approach customizes edge pruning for each node, addressing limitations of previous global sparsification techniques.\nMoG assembles sparse subgraphs on the Grassmann manifold, enhancing graph structure while preserving node connectivity. Extensive experiments across diverse datasets demonstrate MoG’s ability to achieve significant sparsity with minimal performance loss.\nThe authors validate MoG’s effectiveness through experiments on large-scale datasets. MoG achieves faster GNN inference and better performance in some cases. MoG’s flexible sparsification method shows potential for advancing GNN deployment in resource-limited environments.\n\n-----------------------------------\nAfter reading all the responses and the improved manuscript, I think this paper can be considered to be accepted. Thus, I raised my rating to 'accept', because there is no '7'.", "questions": "Please refer to the weaknesses above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The experiments show the MoG's adaptability across different graph learning tasks. They also show MoG’s ability to improve inference speed while maintaining or even boosting accuracy (up to 1.74% in some cases) demonstrates its practical benefits. \n2. The paper introduces a novel method, Mixture-of-Graphs (MoG), which applies the Mixture-of-Experts (MoE) concept to graph sparsification. Unlike traditional sparsification methods with uniform criteria, MoG combines sparsity levels and pruning criterias to each node’s local context.\n3. The paper clearly defines the MoG framework, including the sparsifier expert selection process, node-wise routing, and mixture on the Grassmann manifold. The mathematical framework is well-detailed, particularly in describing the sparsifier expert selection via the noisy top-k gating mechanism and the Grassmann manifold’s role in mixing sparse subgraphs.\n4. MoG's ability to achieve significant sparsity without a substantial performance drop highlights its potential to improve GNN deployment in resource-limited environments. By effectively balancing computational efficiency and accuracy, MoG could effectively serve as a plugin to boost GNN performance, from real-time social network analysis to large-scale molecular data processing.", "weaknesses": "1. The paper does not clarify in “4 EXPERIMENTS” or “Appendix F.6” why the specific 12 combinations of sparsity levels and criteria were selected. Additionally, the variance of each row across combinations in Table 8 is minimal, raising questions about the distinctiveness of each sparsifier.\nFurthermore, in “Appendix F.6”, different sparsity criteria are applied in different datasets without an explanation of the selection rationale.\nTo enhance experimental completeness, the authors might consider exploring a wider range of sparsity combinations with greater variance. Additionally, providing the reasoning behind dataset-specific combinations would help readers understand the adaptability of MoG across different graph structures.\n\n2. The process of integrating sparse subgraphs on the Grassmann manifold, as outlined in Section 3.4, is mathematically dense and lacks intuitive explanation. While the theoretical basis is strong, the connection between the Grassmann manifold’s properties and its benefits for graph sparsification may not be immediately clear to all readers.\n\n3. The terminology for sparsifiers and experts appears inconsistent across sections, which could lead to confusion. For instance, “sparsifier experts” and “experts” are used interchangeably.\n\nMinor Comment:\n4. In Section 2, there is a spelling error in the title “TECHNICAL BACKGOUND,” which should be “TECHNICAL BACKGROUND.” I recommend reviewing the document to ensure there are no similar spelling errors throughout.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "dUrLwlsZSo", "reviewer": "Reviewer_XfnA", "summary": "This paper proposes a method called **MoG**, which uses the technique of MoE to integrate multiple ego-net sparsifier strategies in GNNs. \n\nFirst, for each ego-net, the authors introduce a simple noisy top-k gating mechanism as a routing module to select K sparsifier experts, each with different sparsity levels and sparsification strategies. \n\nThen, using Grassmann manifold techniques, the authors combine these sparsified ego graphs, with objective function Eq.11 and its closed-form solution in Eq.12.\n\nThe experiments show that compared to other sparsification methods:\n- In terms of accuracy, MoG has a slight advantage in two node classification datasets and a more noticeable effect in two graph classification datasets.\n- In terms of balancing inference speed and accuracy, MoG achieves higher accuracy when reaching the same speedup.\n\nThe authors also conducted additional experiments, such as sensitivity analysis.", "questions": "Please check weakness 1.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method has a certain degree of innovation, especially in the use of MoE and the approach to combining graphs.\n2. The proposed method can be integrated with any framework.\n3. The paper includes extensive experiments.", "weaknesses": "1. Eq.11 is a core objective, but it is quite heuristic. Moreover, after obtaining the combined graph with Eq.12, there is a post-sparsification operation. Does the final ensembled sparse Laplacian truly integrate the eigenvectors of multiple sparsified ego-net Laplacians as the authors hope? Regardless of the degree achieved, it would be helpful to see experimental evidence here.\n\n2. There are only two node classification and two graph classification datasets, which is relatively few.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "nIDsSmyeGQ", "reviewer": "Reviewer_D6Ca", "summary": "The authors propose a mixture-of-graphs (MoG) approach inspired by mixture-of-experts for graph sparsification. Instead of having global/uniform pruning criteria, they create a dynamic strategy tailored to each node’s neighborhood. This is done by utilizing each node’s egograph to select a few sparsifiers (experts) from a larger pool. The outputs of selected sparsifiers are ensembled using Grassmann manifold theory to generate a single sparsified ego graph per node and are later re-combined to form the final graph. Their approach outperforms baselines across several datasets, maintaining performance at higher sparsity levels and sometimes even improving it due to reduction of noise after sparsification.", "questions": "A couple of questions on output:\n\n1. In figure 1 (Middle), we attribute edge pruning to different sparsifiers. Did we perform this qualitative analysis on an actual sparsified graph, or is it an imagined example to represent our hypothesis? Although not required to perform this if not done already, I was simply wondering if it was the case and was interested in knowing more about it.\n2. What is the difference between observed average sparsity just after ensembling in eq. 13 and after the post-sparsification step of eq. 14? Curious to understand how much more the graph density changes after the optimization in eq 11.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Tackles a topical and highly relevant problem in graph learning on large graphs.\n2. Highly flexible, well-motivated approach that accounts for local node variations while determining optimal pruning strategy.\n3. Ample experiments across baselines and datasets, replete with sensitivity analysis, ablation studies, and efficiency comparison.", "weaknesses": "Adding below-mentioned minor clarifications around methodology may be useful:\n\n1. How are post-sparsified ego-graphs assembled? Is it possible that for two nodes $i$ and $j$, the post-sparsified ego graph of $i$ connects to $j$ but the post-sparsified ego graph of $j$ doesn’t connect to $i$? If yes, how is this handled?\n2. How do we select $p$ in equation 10? What is its impact on performance?\n3. What does $D$ in eq. 13 correspond to? Is it from the original ego graph of the given node? If yes, why do we use the same $D$? Would it not introduce some approximation error since it doesn’t correspond exactly to the learned laplacian?\n4. The method seems entirely local. For some downstream tasks, it may be relevant to take the global graph structure into consideration, for example, to ensure the graph stays connected. How does the proposed approach tackle this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "GUov1NeDCN", "reviewer": "Reviewer_aseP", "summary": "This work leverages the Mixture-of-Experts (MoE) approach, a well-established technique in deep learning domains such as language modeling, to scale model capacity (i.e., the number of parameters) while managing computational demands. In this context, the MoE concept is applied dynamically and locally sparsity to the underlying graph during GNN inference. The authors demonstrate that this method maintains performance while reducing inference time.", "questions": "**Significance**\n\nIs there a real use case the authors can point to where SpMM compute limits people who are using/want to use GNNs? In my opinion, the significance of this type of ML research is measured by the significance of the problem it is solving/the capability it unlocks. Otherwise this is a more of a neat contribution to the literature which we simply speculate to be useful eventually.\n\n&nbsp;\n\n**The use of Gaussian Noise in the MoE step**\n\nPerhaps I show my naivety re: MoE, but why do we believe added \\epsilon \\sim N(0,1) noise is of a suitable scale to effectively alter the routing? Is there a particular normalization of activations to ensure \\epsilon interacts with numbers of this scale?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "I thought the writing was clear for the most part, with the exception being the contributions/intro (see Weaknesses). The figures are excellent. I haven't seen prior work on MoE re: sparsity, so I believe it to be original, although not very confident. \n\n&nbsp;\n\nThis work could be significant. Indeed, GNN inference cost has motivated much GNN research in the past; see Questions for more of my thoughts on this.", "weaknesses": "**Making Contributions Clear**\n\nI suggest making more clear the contributions of the paper and what the authors are claiming novelty on. Many papers use bullet points at the end of the introduction section to denote this; this work has bullet points near the end of the introduction, but they do not correspond to contributions, making the reading a bit confusing for regular readers of ICLR proceedings.\n\n&nbsp;\n\n**Some Missing Background in Graph Sparsification**\n\nThere is extensive literature on graph sparsification coming from the statistics and optimization world, commonly referred to under the umbrella term ‘Graph Structure Learning’. Most of these approaches indeed use some global sparsity promoting criteria; you could state how your approach has advantages over this more coarse approach. I include references to a classical work and a recent work. The latter has an overview of recent Graph Structure Learning approaches, most of which indeed use some global sparsity criterion in their objective.\n\n&nbsp;\n\nFriedman, Jerome, Trevor Hastie, and Robert Tibshirani. \"Sparse inverse covariance estimation with the graphical lasso.\" Biostatistics 9.3 (2008): 432-441.\n\nWasserman, Max, and Gonzalo Mateos. \"Graph Structure Learning with Interpretable Bayesian Neural Networks.\" Transactions on machine learning research (2024).\n\n&nbsp;\n\n**Missing Experiment/Ablation Study**\n\nA simple baseline I expect to see would be to somehow prune the graph to a particular sparsity level and run a GNN on that. Perhaps some sort of edge sampling procedure selects a subset of edges to prune such that the global sparsity is set to ~=x, perhaps preferring edges to remove in proportional to the adjacent nodes' degree, while ensuring no disconnected nodes. Do so for a few sparsity levels. This would provide a good idea for how much benefit is really to be gotten from this whole effort, beyond the straightforward pruning approach.\n\nPerhaps this ablation study is done implicitly in one of the baselines. Please correct me if so.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Spotlight)