# Graph Sparsification via Mixture of Graphs

Guibin Zhang1, Xiangguo Sun211footnotemark: 1, Yanwei Yue1, Kun Wang3,
Tianlong Chen4, Shirui Pan5
1 Tongji University 2 The Chinese University of Hong Kong
3 University of Science and Technology of China
4 Massachusetts Institute of Technology 5 Griffith University The first two
authors contributed equally.

###### 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+ogbn-proteins and $1.74\%\uparrow$ on
DeeperGCN+ogbg-ppa). The source code is publicly available at
https://github.com/yanweiyue/MoG.

##  1 Introduction

Graph Neural Networks (GNNs) [1, 2] have become prominent for confronting
graph-related learning tasks, including social recommendation [3, 4], fraud
detection [5, 6, 7], drug design [8], and many others [9, 10]. 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) [11, 12]), and the latter updates the
central nodes’ embeddings using dense matrix-based operations (e.g., MatMul)
[11, 12]. SpMM typically contributes the most substantial part ($\sim$70%) to
the computational demands [13, 14], influenced largely by the graph’s scale.
Nevertheless, large-scale graphs are widespread in real-world scenarios [15,
16, 17], 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.

Figure 1: (Left) We illustrated the $k$-hop neighborhood expansion rates for
nodes 6 and 14, which is proportional to the amount of 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
$(v_{1},v_{2})$ might be due to its non-bridge identity, while pruning
$(v_{5},v_{6})$ could be attributed to it non-homophilic nature; (Right) The
overview of our proposed MoG.

To conquer the above challenge, graph sparsification [18, 19] has recently
seen a revival as it directly reduces the aggregation process associated with
SpMM [13, 14] in GNNs. Specifically, graph sparsification is a technique that
approximates a given graph by creating a 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 [20], DSpar [13], and
AdaGLT [21] have achieved notable successes, with some maintaining GNN
performance even with up to 40% edge sparsity.

Beyond serving as a computational accelerator, the purpose of graph
sparsification extends further. Another research line leverages graph
sparsification as a performance booster to remove task-irrelevant edges and
pursue highly performant and robust GNNs [22]. Specifically, it is argued that
due to uncertainty and complexity in data collection, graph structures are
inevitably redundant, biased, and noisy [23]. Therefore, employing graph
sparsification can effectively facilitate the evolution of graph structures
towards cleaner conditions [22, 24], and finally boost GNN performance.

However, existing sparsification methods, namely sparsifiers, whether aimed at
achieving higher sparsity or seeking enhanced performance, often adopt a
rigid, global approach to conduct graph sparsification, thus suffering from
the inflexibility in two aspects:

  * ❶

Inflexibility of sparsity level. Previous sparsifiers globally score all edges
uniformly and prune them based on a preset sparsity level [18]. However, as
shown in Figure 1 (Left), 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 [25, 26], 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 a
unified guiding principle, such as pruning non-bridge edges [27], non-
homophilic edges [28], or edges with low effective resistance [29, 13], among
others. However, as 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 to
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 a novel graph sparsifier dubbed Mixture of Graphs
(MoG). It comprises multiple sparsifier experts, each equipped with distinct
pruning criteria and sparsity settings, as in Figure 1 (Right). Throughout the
training process, MoG dynamically selects the most suitable sparsifier expert
for each node based on its neighborhood properties. This fosters
specialization within each MoG expert, focusing on specific subsets of nodes
with similar neighborhood contexts. After each selected expert prunes the
1-hop subgraph of the central nodes and outputs its sparse version, MoG
seamlessly integrates these sparse subgraphs on the Grassmann manifold in an
expert-weighted manner, thereby forming an optimized sparse graph.

We validate the effectiveness of MoG across six datasets and three GNN
backbones, and show that MoG can ❶ effectively locate well-performing sparse
graphs, maintaining GNN performance losslessly at satisfactory sparsity levels
($8.67\%\sim 50.85\%$), and even only experiencing a $1.65\%$ accuracy drop at
$69.13\%$ sparsity on ogbn-proteins; ❷ achieve a tangible $1.47\sim
2.62\times$ inference speedup with negligible performance drop; and ❸ boost
ROC-AUC by $1.81\%$ on ogbg-molhiv, $1.02\%$ on ogbn-proteins and enhances
accuracy by $0.95\%$ on ogbn-arxiv.

##  2 Technical Backgound

#### Notations & Problem Formulation

We consider an undirected graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$,
with $\mathcal{V}$ as the node set and $\mathcal{E}$ the edge set. The node
features of $\mathcal{G}$ is represented as $\mathbf{X}\in\mathbb{R}^{N\times
F}$, where $N=|\mathcal{V}|$ signifies the total number of nodes in the graph.
The feature vector for each node $v_{i}\in\mathcal{V}$, with $F$ dimensions,
is denoted by $x_{i}=\mathbf{X}[i,\cdot]$. An adjacency matrix
$\mathbf{A}\in\\{0,1\\}^{N\times N}$ is utilized to depict the inter-node
connectivity, where $\mathbf{A}[i,j]=1$ indicates an edge
$e_{ij}\in\mathcal{E}$, and $0$ otherwise. For our task of graph
sparsification, the core objective is to identify a subgraph
$\mathcal{G}_{\text{sub}}$ given a sparsity ratio $s\%$:

$\mathcal{G}^{\text{sub}}=\\{\mathcal{V},\mathcal{E}\setminus\mathcal{E}^{\prime}\\},\;s\%=\frac{|\mathcal{E}^{\prime}|}{|\mathcal{E}|},$
(1)

where $\mathcal{G}^{\text{sub}}$ only modifies the edge set $\mathcal{E}$
without altering the node set $\mathcal{V}$, and $\mathcal{E}^{\prime}$
denotes the removed edges, and $s\%$ represents the ratio of removed edges.

#### Graph Neural Networks

Graph neural networks (GNNs) [30] have become pivotal for learning graph
representations, achieving benchmark performances in various graph tasks at
node-level [31], edge-level [32], and graph-level [33]. At the node-level, two
of the most famous frameworks are GCN [34] and GraphSAGE [35], which leverages
the message-passing neural network (MPNN) framework [36] to aggregate and
update node information iteratively. For edge-level and graph-level tasks, GCN
and GraphSAGE can be adapted by simply incorporating a predictor head or
pooling layers. Nevertheless, there are still specialized frameworks like SEAL
[37] and Neo-GNN [38] for link prediction, and DiffPool [39] and PNA [40] for
graph classification. Regardless of the task, MPNN-style GNNs generally adhere
to the following paradigm:

$\mathbf{h}_{i}^{(l)}=\text{{COMB}}\left(\mathbf{h}_{i}^{(l-1)},\text{{AGGR}}\\{\mathbf{h}_{j}^{(k-1)}:v_{j}\in\mathcal{N}(v_{i})\\}\right),\;0\leq
l\leq L$ (2)

where $L$ is the number of GNN layers, $\mathbf{h}_{i}^{(0)}=\mathbf{x}_{i}$,
and $\mathbf{h}_{i}^{(l)}(1\leq l\leq L)$ denotes $v_{i}$’s node embedding at
the $l$-th layer. AGGR($\cdot$) and COMB($\cdot$) represent functions used for
aggregating neighborhood information and combining ego- and neighbor-
representations, respectively.

#### Graph Sparsification

Graph sparsification methods can be categorized by their utility into two main
types: computational accelerators and performance boosters. Regarding
computational accelerators, early works aimed at speeding up traditional tasks
like graph partitioning/clustering often provide theoretical assurances for
specific graph properties, such as pairwise distances [41], cuts [42],
eigenvalue distribution [43], and effective resistance [29]. More contemporary
efforts focus on the GNN training and/or inference acceleration, including
methods like SGCN [44], GEBT [45], UGS [20], DSpar [13], and AdaGLT [17].
Regarding performance boosters, methods like NeuralSparse [22] and PTDNet [24]
utilize parameterized denoising networks to eliminate task-irrelevant edges.
SUBLIME [46] and Nodeformer [47] also involve refining or inferring a cleaner
graph structure followed by $k$-nearest neighbors ($k$NN) sparsification.

#### Mixture of Experts

The Mixture of Experts (MoE) concept [48] traces its origins to several
seminal works [49, 50]. Recently, the sparse MoE architecture [51, 52, 53, 54,
55] has regained attention due to its capacity to support the creation of vast
(language) models with trillions of parameters [54, 56]. Given its stability
and generalizability, sparse MoE is now broadly implemented in modern
frameworks across various domains, including vision [57], multi-modal [58],
and multi-task learning [59, 60]. As for graph learning, MoE has been explored
for applications in graph classification [61], scene graph generation [62],
molecular representation [63], graph fairness [64], and graph diversity
modeling [65].

##  3 Methodology

###  3.1 Overview

Figure 2 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, a routing network calculates the
expert scores. Based on the router’s decisions, sparsifier experts with
different sparsity levels and pruning criteria are allocated to different
nodes. Ultimately, a mixture of graphs is obtained based on the weighted
consensus of the sparsifier experts. In the following sections, we will first
detail how to route different sparsifiers in Section 3.2, then describe how to
explicitly model various sparsifier experts in Section 3.3 and how to ensemble
the sparse graphs output by sparsifiers on the Grassmann manifold in Section
3.4. Finally, the overall optimization process and complexity analysis of MoG
is placed in Section 3.5.

Figure 2: The overview of our proposed method. MoG primarily comprises ego-
graph decomposition, expert routing, sparsifier customization, and the final
graph mixture. For simplicity, we only showcase three pruning criteria
including Jaccard similarity, gradient magnitude, and effective resistance.

###  3.2 Routing to Diverse Experts

Following the classic concept of a (sparsely-gated) mixture-of-experts [66],
which assigns the most suitable expert(s) to each input sample, MoG aims to
allocate the most appropriate sparsity level and pruning criteria to each
input node. To achieve this, we first decompose the input graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ into 1-hop ego graphs centered on
different nodes, denoted as
$\\{\mathcal{G}^{(1)},\mathcal{G}^{(2)},\cdots,\mathcal{G}^{(N)}\\}$, where
$\mathcal{G}^{(i)}=\\{\mathcal{V}^{(i)},\mathcal{E}^{(i)}\\}$,
$\mathcal{V}^{(i)}=\\{v_{j}|v_{j}\in\mathcal{N}(v_{i})\\}$, and
$\mathcal{E}^{(i)}=\\{e_{ij}|(v_{i},v_{j})\in\mathcal{E}\\}$. Assuming we have
$K$ sparsifier experts, for each node $v_{i}$ and its corresponding ego graph
$\mathcal{G}^{(i)}$, we aim to select the $k$ most suitable sparsifiers. We
employ the classic noisy top-$k$ gating mechanism following [51]:

$\displaystyle\Psi(\mathcal{G}^{(i)})=\operatorname{Softmax}(\operatorname{TopK}(\psi(x_{i}),k)),$
(3)
$\displaystyle\psi(x_{i})=x_{i}W_{g}+\epsilon\cdot\operatorname{Softplus}(x_{i}W_{n}),$
(4)

where $\psi(x_{i})\in\mathbb{R}^{K}$ is the calculated scores of $v_{i}$ for
total $K$ experts, $\operatorname{TopK}(\cdot)$ is a selection function that
outputs the largest $k$ values, and
$\Psi(\mathcal{G}^{(i)})\in\mathbb{R}^{k}=[E^{(i)}_{1},E^{(i)}_{2},\cdots,E^{(i)}_{k}]$
represents those for selected $k$ experts. In $\Psi(\mathcal{G}^{(i)})$,
$\epsilon\in\mathcal{N}(0,1)$ denotes the standard Gaussian noise,
$W_{g}\in\mathbb{R}^{K\times F}$ and $W_{n}\in\mathbb{R}^{K\times F}$ are
trainable parameters that learn clean and noisy scores, respectively.

After determining the appropriate experts, we proceed to generate different
sparse graphs with diverse sparsifiers. We denote each sparsifier by
$\kappa(\cdot)$, which takes in a dense graph $\mathcal{G}$ and outputs a
sparse one $\tilde{\mathcal{G}}=\kappa(\mathcal{G})$. Based on this, for each
node $v_{i}$ and its ego graph $\mathcal{G}^{(i)}$, the routing network
selects $k$ experts that produce $k$ 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 dynamic
selection of different sparsifiers for each node aids in identifying pruning
strategies truly adapted to the node’s local context. Formally, the mixture of
$k$ sparse graphs can be written as:

$\widehat{\mathcal{G}^{(i)}}=\text{{ESMB}}(\\{\widetilde{\mathcal{G}}^{(i)}_{m}\\}_{m=1}^{k}),\;\;\widetilde{\mathcal{G}}^{(i)}_{m}=\kappa^{m}(\mathcal{G}^{(i)}),$
(5)

where $\text{{ESMB}}(\cdot)$ is a combination function that receives $k$
sparse graphs and ideally outputs an emsemble version
$\widehat{\mathcal{G}^{(i)}}=\\{\widehat{\mathcal{V}^{(i)}},\widehat{\mathcal{E}^{(i)}}\\}$
that preserves their desirable properties. It 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:

$\mathbf{h}_{i}^{(l)}=\text{{COMB}}\left(\mathbf{h}_{i}^{(l-1)},\text{{AGGR}}\\{\mathbf{h}_{j}^{(k-1)}:v_{j}\in\widehat{\mathcal{V}^{(i)}}\\}\right).$
(6)

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 task-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, we 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(\mathbf{Y}|\mathcal{G})$, which means
learning the distribution of the target $\mathbf{Y}$ given an input graph.
Based on this, a sparsifier $\kappa(\cdot)$ can be formally expressed as
follows:

$\displaystyle P(\mathbf{Y}|\mathcal{G})$
$\displaystyle\approx\sum_{g\in\mathbb{S}_{\mathcal{G}}}P(\mathbf{Y}\;|\;\tilde{\mathcal{G}})P(\tilde{\mathcal{G}}\;|\;\mathcal{G})$
$\displaystyle\approx\sum_{g\in\mathbb{S}_{\mathcal{G}}}Q_{\Theta}(\mathbf{Y}\;|\;\tilde{\mathcal{G}})Q_{\kappa}(\tilde{\mathcal{G}}\;|\;\mathcal{G})$
(7)

where $\mathbb{S}_{\mathcal{G}}$ is a class of sparsified subgraphs of
$\mathcal{G}$. The second term in Equation 7 aims to approximate the
distribution of $\mathbf{Y}$ using the sparsified graph $\tilde{\mathcal{G}}$
as a bottleneck, while the third term uses two approximation functions
$Q_{\Theta}$ and $Q_{\kappa}$ for $P(\mathbf{Y}\;|\;\tilde{\mathcal{G}})$ and
$P(\tilde{\mathcal{G}}\;|\;\mathcal{G})$ parameterized by $\Theta$ and
$\kappa$ respectively. The parameter $\Theta$ typically refers to the
parameters of the GNN, while the sparsifier $\kappa(\cdot)$, on the other
hand, is crafted to take an ego graph $\mathcal{G}^{(i)}$ and output its
sparsified version $\tilde{\mathcal{G}^{(i)}}$, guided by a specific pruning
paradigm $C$ and sparsity $s^{m}\%$:

$\kappa^{m}(\mathcal{G}^{(i)})=\\{\mathcal{V}^{(i)},\mathcal{E}^{(i)}\setminus\mathcal{E}_{p}^{(i)}\\},\;\mathcal{E}_{p}^{(i)}=\operatorname{TopK}\left(-C^{m}(\mathcal{E}),\lceil|\mathcal{E}^{(i)}|\times
s^{m}\%\rceil\right),$ (8)

where $C^{m}(\cdot)$ acts as the $m$-th expert’s scoring function that
evaluates edge importance. We leverage long-tail gradient estimation [67] to
ensure the $\operatorname{TopK}(\cdot)$ operator is differentiable.
Furthermore, to ensure the sparsifier is driven by different sparsity
criteria, we implement $C^{m}(\cdot)$ as follows:

$\displaystyle
C^{m}(e_{ij})=\operatorname{FFN}\left(x_{i},x_{j},c(e_{ij})\right),\;c^{m}(e_{ij})\in\left\\{\begin{array}[]{c}\text{Degree:
}\left(|\mathcal{N}(v_{i})+\mathcal{N}(v_{j})|\right)/2\\\ \text{Jaccard
Similarity:
}\frac{|\mathcal{N}(v_{i})\cap\mathcal{N}(v_{j})|}{|\mathcal{N}(v_{i})\cup\mathcal{N}(v_{j})|}\\\
\text{ER: }(e_{i}-e_{j})^{T}\mathbf{L}^{-1}(e_{i}-e_{j})\\\ \text{Gradient
Magnitude: }|\partial\mathcal{L}/\partial e_{ij}|\end{array}\right\\},$ (9)

where $\operatorname{FFN}(\cdot)$ is a feed-forward network, $c^{m}(e_{ij})$
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 [68], Jaccard
similarity [69, 70], effective resistance [29, 13] and gradient magnitude [71,
17]. Details regarding these criteria and their implementations are in
Appendix B.

###  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 to ensemble these $k$ sparse
subgraphs and maximize the aggregation of their advantages. A straightforward
approach is voting or averaging [72]; however, such simple merging may fail to
capture the intricate relationships among multi-view graphs [73], potentially
resulting in the loss of advantageous properties from all experts. Inspired by
recent advances in manifold representations [74, 75], we develop a subspace-
based sparse graph ensembling mechanism. We first provide the definition of
the Grassmann manifold [75] as follows:

######  Definition 1 (Grassmann manifold).

Grassmann manifold $Gr(n,p)$ is the space of $n$-by-$p$ matrices (e.g.,
$\mathbf{M}$) with orthonormal columns, where $0\leq p\leq n$, i.e.,

$Gr(n,p)=\left\\{\mathbf{M}|\mathbf{M}\in\mathbb{R}^{n\times
p},\mathbf{M}^{\top}\mathbf{M}=\mathbf{I}\right\\}.$ (10)

According to Grassmann manifold theory, each orthonormal matrix represents a
unique subspace and thus corresponds to a distinct point on the Grassmann
manifold [76]. This applies to the eigenvector matrix of the normalized
Laplacian matrix ($\mathbf{U}=\mathbf{L}[:,:p]\in\mathbb{R}^{n\times p}$),
which comprises the first $p$ eigenvectors and is orthonormal [77], and
thereby can be mapped onto the Grassmann manifold.

Consider the $k$ sparse subgraphs
$\\{\widetilde{\mathcal{G}}^{(i)}_{m}\\}_{m=1}^{k}$, their subspace
representations are
$\\{\mathbf{U}^{(i)}_{m}\in\mathbb{R}^{|\mathcal{N}(v_{i})|\times
p}\\}_{m=1}^{k}$. We aim to identify an oracle subspace $\mathbf{U}^{(i)}$ on
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:

$\displaystyle\min_{\mathbf{U^{(i)}}\in\mathbb{R}^{|\mathcal{N}(v_{i})|\times
p}}\sum_{m=1}^{k}\left(\underbrace{\operatorname{tr}(\mathbf{U^{(i)}}^{\top}\mathbf{L}_{m}\mathbf{U}^{(i)})}_{\textrm{(1)
node connectivity}}+\underbrace{\overbrace{E^{(i)}_{m}}^{\text{expert
score}}\cdot d^{2}(\mathbf{U}^{(i)},\mathbf{U}^{(i)}_{m})}_{\textrm{(2)
subspace
distance}}\right),\operatorname{s.t.}\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}=\mathbf{I}$
(11)

where $\operatorname{tr}(\cdot)$ calculates the trace of matrices,
$\mathbf{L}_{m}$ is the graph Laplacian of $\mathcal{G}^{(i)}_{m}$,
$d^{2}(\mathbf{U}_{1},\mathbf{U}_{2})$ denotes the project distance between
two subspaces [74], and $E^{(i)}_{m}$ is the expert score for the $m$-th
expert, calculated by the routing network $\Psi$, which determines which
expert’s subspace the combined subspace should more closely align with. In
Equation 11, the first term is 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
$\mathbf{U}^{(i)}$. Using the Rayleigh-Ritz Theorem [78], we provide a closed-
form solution for Equation 11 and obtain the graph Laplacian of the ensemble
sparse graph $\widehat{\mathcal{G}^{(i)}}$ as follows:

$\widehat{\mathbf{L}^{(i)}}=\sum_{m=1}^{k}\left(\mathbf{L}_{m}-E_{m}^{(i)}\cdot\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}\right).$
(12)

We provide detailed derivations and explanations for Equations 11 and 12 in
Appendix C. Consequently, we can reformulate the function
$\text{{ESMB}}(\cdot)$ in Equation 5 as follows:

$\text{{ESMB}}(\\{\widetilde{\mathcal{G}}^{(i)}_{m}\\}_{m=1}^{k})=\\{\mathbf{D}-\widehat{\mathbf{L}^{(i)}},\mathbf{X}^{(i)}\\}=\left\\{\mathbf{D}-\sum_{m=1}^{k}\left(\mathbf{L}_{m}-E_{m}^{(i)}\cdot\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}\right),\mathbf{X}^{(i)}\right\\}.$
(13)

On the Grassmann manifold, the subspace ensemble effectively captures the
beneficial properties of each expert’s sparse graph. After obtaining the final
version of each node’s ego-graph,
$\widehat{\mathcal{G}^{(i)}}=\\{\widehat{\mathbf{A}^{(i)}},\mathbf{X}^{(i)}\\}$,
we conduct a post-sparsification step as the graph ensembled on the Grassmann
manifold can become dense again. Specifically, we obtain the final sparsity
$s^{(i)}\%$ for $v_{i}$ by weighting the sparsity of each expert and
sparsifying $\widehat{\mathcal{G}^{(i)}}$.

$\widehat{\mathcal{G}^{(i)}}\leftarrow\\{\operatorname{TopK}(\widehat{\mathbf{A}^{(i)}},|\mathcal{E}^{(i)}|\times
s^{(i)}\%),\mathbf{X}^{(i)}\\},\;s^{(i)}\%=\frac{1}{k}\sum_{m=1}^{k}s^{m}\%.$
(14)

These post-sparsified $\widehat{\mathcal{G}^{(i)}}$ are then reassembled
together into
$\widehat{\mathcal{G}}\leftarrow\\{\widehat{\mathcal{G}^{(1)}},\widehat{\mathcal{G}^{(2)}},\cdots,\widehat{\mathcal{G}^{(|\mathcal{V}|)}}\\}$.
Ultimately, the sparsified graph $\widehat{\mathcal{G}}$ produced by MoG can
be input into any MPNN [36] or graph transformer [79] architectures for end-
to-end training.

###  3.5 Training and Optimization

#### Additional Loss Functions

Following classic MoE works [51, 65], we introduce an expert importance loss
to prevent MoG from converging to a trivial solution where only a single group
of experts is consistently selected:

$\operatorname{Importance}(\mathcal{V})=\sum_{i=1}^{|\mathcal{V}|}\sum_{j=1}^{k}E^{(i)}_{m},\;\;\mathcal{L}_{\text{importance}}(\mathcal{V})=\operatorname{CV}(\operatorname{Importance}(\mathcal{V}))^{2},$
(15)

where $\operatorname{Importance}(\mathcal{V})$ represents the sum of each
node’s expert scores across the node-set, $\operatorname{CV}(\cdot)$
calculates the coefficient of variation, and $\mathcal{L}_{\text{importance}}$
ensures the variation of experts. Therefore, the final loss function combines
both task-specific and MoG-related losses, formulated as follows:

$\mathcal{L}=\mathcal{L}_{\text{task}}+\lambda\cdot\mathcal{L}_{\text{importance}},$
(16)

where $\lambda$ 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 a
comprehensive algorithmic table in Appendix D 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 G.2.

##  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 is MoG to its key components and
parameters?

###  4.1 Experiment Setup

#### Datasets and Backbones

We opt for four large-scale OGB benchmarks [80], including ogbn-arxiv, ogbn-
proteins and ogbn-products for node classification, and ogbg-ppa for graph
classification. The dataset splits are given by [80]. Additionally, we choose
two superpixel datasets, MNIST and CIFAR-10 [81]. We select GraphSAGE [35],
DeeperGCN [82], and PNA [40] as the GNN backbones. More details are provided
in Appendix F.

#### Parameter Configurations

For MoG, we adopt the $m=4$ sparsity criteria outlined in Section 3.3,
assigning $n=3$ different sparsity levels $\\{s_{1},s_{2},s_{3}\\}$ to each
criterion, resulting in a total of $K=m\times n=12$ experts. We select $k=2$
sparsifier experts for each node, and set the loss scaling factor
$\lambda=1e-2$ across all datasets and backbones. By adjusting the sparsity
combination, we can control the global sparsity of the entire graph. We
present more details on parameter settings in Section F.4, and a recipe for
adjusting the graph sparsity in Section F.6.

###  4.2 MoG as Graph Sparsifier

To answer RQ1 and RQ2, we comprehensively compare MoG with eleven widely-used
topology-guided sparsifiers and five semantic-guided sparsifiers, as outlined
in Table 1, with more detailed explanations in Section F.5. The quantitative
results on five datasets are shown in Tables 1, 9, 8, 11 and 10 and the
efficiency comparison is in Figure 3. We give the following observations
(Obs.):

Table 1: 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
${\dagger}$ that do not have precise control over sparsity; their performance
is reported around the target sparsity $\pm 2\%$. “Sparsity %” refers to the
ratio of removed edges as defined in Section 2. “OOM” and “OOT” denotes out-
of-memory and out-of-time, respectively.

| Dataset |  ogbn-arxiv (Accuracy$\uparrow$) |  ogbn-proteins (ROC-AUC$\uparrow$)
---|---|---|---
Sparsity % | 10 | 30 | 50 | 70 | 10 | 30 | 50 | 70
Topology-guided | Random |  70.03↓1.46 |  68.40↓3.09 |  64.32↓7.17 |  61.18↓10.3 |  76.72↓0.68 |  75.03↓2.37 |  73.58↓3.82 |  72.30↓5.10
Rank Degree† [83] |  68.13↓3.36 |  67.01↓4.48 |  65.58↓5.91 |  62.17↓9.32 |  77.47↑0.07 |  76.15↓1.25 |  75.59↓1.81 |  74.23↓3.17
Local Degree† [84] |  68.94↓2.55 |  67.20↓4.29 |  65.45↓6.04 |  65.59↓5.90 |  76.20↓1.20 |  76.05↓1.35 |  76.09↓1.31 |  72.88↓4.52
Forest Fire† [85] |  68.39↓3.10 |  68.10↓3.39 |  67.36↓4.13 |  65.22↓6.27 |  76.50↓0.90 |  75.37↓2.03 |  74.29↓3.11 |  72.11↓5.29
G-Spar [86] |  71.30↓0.19 |  69.29↓2.20 |  65.56↓5.93 |  65.49↓6.00 |  77.38↓0.02 |  77.36↓0.04 |  76.02↓1.38 |  75.89↓1.51
LSim† [87] |  69.22↓2.27 |  66.15↓5.34 |  61.07↓10.4 |  60.32↓11.2 |  76.83↓0.57 |  76.01↓1.39 |  74.83↓2.57 |  73.65↓3.75
SCAN [88] |  71.55↑0.06 |  69.27↓2.22 |  65.14↓6.35 |  64.72↓6.77 |  77.60↑0.20 |  76.88↓0.52 |  76.19↓1.21 |  74.32↓3.08
ER [29] |  71.63↑0.14 |  69.48↓2.01 |  69.00↓2.49 |  67.15↓4.34 | OOT
DSpar [13] |  71.23↓0.26 |  68.50↓2.99 |  64.79↓6.70 |  63.11↓8.38 |  77.34↓0.06 |  77.06↓0.34 |  76.38↓1.02 |  75.49↓1.91
Semantic-guided |  UGS† [20] |  68.77↓2.72 |  66.30↓5.19 |  65.72↓5.77 |  63.10↓8.39 |  76.80↓0.60 |  75.46↓1.94 |  73.28↓4.12 |  73.31↓4.09
GEBT [45] |  69.04↓2.45 |  65.29↓6.20 |  65.88↓5.61 |  65.62↓5.87 |  76.30↓1.10 |  76.17↓1.23 |  74.43↓2.97 |  74.12↓3.28
MGSpar [71] |  70.22↓1.27 |  69.13↓2.36 |  68.27↓3.22 |  66.55↓4.94 | OOM
ACE-GLT† [89] |  71.88↑0.39 |  70.14↓1.35 |  68.08↓3.41 |  67.04↓4.45 |  77.59↑0.19 |  76.14↓1.26 |  75.43↓1.97 |  73.28↓4.12
WD-GLT† [90] |  71.92↑0.43 |  70.21↓1.28 |  68.30↓3.19 |  66.57↓4.92 | OOM
AdaGLT [17] |  71.22↓0.27 |  70.18↓1.31 | 69.13↓2.36 |  67.02↓4.47 |  77.49↑0.09 |  76.76↓1.64 |  76.00↓2.40 |  75.44↓2.96
MoG (Ours)† | 71.93${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 70.53${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>|  69.06↓2.43 | 67.31${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 77.78${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 77.49${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 76.46${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 76.12${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>
Whole Dataset |  71.49±0.01 |  77.40±0.1

#### Obs. ❶ MoG demonstrates superior performance in both transductive and
inductive settings.

As shown in Tables 1, 2, 8, 9 and 10, 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 ogbn-proteins+GraphSAGE. Even when
sparsifying $50\%$ of the edges on ogbn-proteins+DeeperGCN, the ROC-AUC only
drops by $0.81\%$. For graph classification tasks, MoG can remove up to $50\%$
of the edges on MNIST with a $0.14\%$ performance improvement, surpassing
other sparsifiers by $0.99\%\sim 12.97\%$ in accuracy.

#### Obs. ❷ Different datasets and backbones exhibit varying sensitivities to
sparsification.

As shown in Tables 1 and 9, despite ogbn-proteins being relatively insensitive
to sparsification, sparsification at extremely high levels (e.g., $70\%$)
causes more performance loss for GraphSAGE compared to DeeperGCN, with the
former experiencing a $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.6\times$ lossless
acceleration on ogbn-proteins+DeeperGCN and ogbn-products+GraphSAGE, meaning
the performance is equal to or better than the vanilla backbone. Notably, on
ogbn-products+DeeperGCN, MoG achieves $3.3\times$ acceleration with less than
a $1.0\%$ performance drop. Overall, MoG provides significantly superior
inference acceleration compared to its competitors.

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 $\uparrow$) |  ogbn-ppa \+ DeeperGCN (Accuracy $\uparrow$)
---|---|---|---
Sparsity % | 10 | 30 | 50 | 70 | 10 | 30 | 50 | 70
Topology-guided | Random |  94.61↓2.74 |  87.23↓10.1 |  84.82↓12.5 |  80.07↓17.3 |  75.44↓1.65 |  73.81↓4.09 |  71.97↓5.12 |  69.62↓7.47
Rank Degree† [83] |  96.42↓0.93 |  94.23↓3.12 |  92.36↓4.99 |  89.20↓8.15 |  75.81↓1.28 |  74.99↓2.10 |  74.12↓2.97 |  70.68↓6.41
Local Degree† [84] |  95.95↓1.40 |  93.37↓3.98 |  90.11↓7.24 |  86.24↓11.1 |  76.43↓0.66 |  75.87↓1.22 |  72.11↓4.98 |  69.93↓7.16
Forest Fire† [85] |  96.75↓0.60 |  95.42↓1.93 |  95.03↓2.32 |  93.10↓4.25 |  76.38↓0.71 |  75.33↓1.76 |  73.18↓3.91 |  71.49↓5.60
G-Spar [86] |  97.10↓0.25 |  96.59↓0.76 |  94.36↓2.99 |  92.48↓4.87 |  77.68↑0.59 |  73.90↓3.19 |  69.52↓7.57 |  68.10↓8.99
LSim† [87] |  95.79↓1.56 |  92.14↓5.21 |  92.29↓5.06 |  91.95↓5.40 |  76.04↓1.05 |  74.40↓2.69 |  72.78↓4.31 |  68.21↓8.88
SCAN [88] |  95.81↓1.54 |  93.48↓3.87 |  90.18↓7.17 |  86.48↓10.9 |  75.23↓1.86 |  75.18↓1.91 |  72.48↓4.61 |  71.11↓5.98
ER [29] |  94.77↓2.58 |  93.91↓3.44 |  93.45↓3.90 |  91.07↓6.28 |  77.94↑0.85 |  75.15↓1.94 |  73.23↓3.86 |  72.74↓4.35
DSpar [13] |  94.97↓2.38 |  93.80↓3.55 |  92.23↓5.12 |  90.48↓6.87 |  76.33↓0.76 |  73.37↓3.72 |  72.98↓4.11 |  70.77↓6.32
Semantic |  ICPG [91] |  97.69↑0.34 |  97.39↑0.04 |  96.80↓0.55 |  93.77↓3.58 |  77.36↑0.27 |  75.24↓1.85 |  73.18↓3.91 |  71.09↓6.00
AdaGLT [17] |  97.31↓0.04 |  96.58↓0.77 |  94.14↓3.21 |  92.08↓5.27 |  76.22↓0.87 |  73.54↓3.55 |  70.10↓6.99 |  69.28↓7.81
| MoG (Ours)† | 97.80${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 97.74${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 97.79${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 95.30${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 78.43${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 77.90${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 75.23${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 73.09${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>
Whole Dataset |  97.35±0.07 |  77.09±0.04

Figure 3: 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.

###  4.3 MoG as Performance Booster

In the context of RQ3, MoG is developed to augment GNN performance by
selectively removing a 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-art GNNs on both
node-level and graph-level tasks. The former include RevGNN [92] and GAT+BoT
[93], which rank fourth and seventh, respectively, on the ogbn-proteins
benchmark, and the latter include PAS [94] and DeeperGCN [82], ranking fourth
and sixth on the ogbn-ppa benchmark. We observe from Table 3:

#### Obs. ❹ 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\%\uparrow$ on RevGNN+ogbn-proteins and
$1.74\%\uparrow$ on DeeperGCN+ogbg-ppa. This demonstrates that MoG can
effectively serve as a plugin to boost GNN performance by setting a relatively
low sparsification rate.

Table 3: Node classification results on ogbn-proteins 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-AUC$\uparrow$) |  ogbg-ppa (Accuracy$\uparrow$)
---|---|---
Model |  RevGNN |  GAT+BoT |  PAS |  DeeperGCN
w/o MoG | 88.14$\pm$ 0.24 | 88.09 $\pm$ 0.16 | 78.28 $\pm$ 0.24 | 77.09 $\pm$ 0.04
w/ MoG |  89.04 $\pm$ 0.72 |  88.72 $\pm$ 0.50 |  78.66 $\pm$ 0.47 |  78.43 $\pm$ 0.19
(Sparsity: 9.2%) | (Sparsity: 12.7%) | (Sparsity: 6.6%) | (Sparsity: 10.8%)

###  4.4 Sensitivity Analysis

#### Obs. ❺ Sparse expert selection helps customized sparsification.

We conduct a parameter sensitivity analysis on the number of sparsifier
experts $k$ selected for each node, as shown in Section 4.4. It can be
observed that the optimal $k$ 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 at $k=4$, suggesting that
in high sparsity environments, more expert opinions contribute to better
sparsification. Notably, when $k$ 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=2$ in all experiments.

#### Obs. ❻ Sparsifier load balancing is essential.

We conduct a sensitivity analysis of the expert importance loss coefficient
$\lambda$. A larger $\lambda$ indicates greater variation in the selected
experts. As shown in Section 4.4, $\lambda=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 [65, 51]. Conversely, $\lambda=1e-1$ performed slightly better than
$\lambda=1e-2$ at higher sparsity levels, supporting the findings in Obs. 5
that higher sparsity requires more diverse sparsifier experts.

Figure 4: Sensitivity study on parameter $k$, i.e., how many experts are chosen per node. The results are reported based on ogbn-arxiv+GraphSAGE.  $\lambda$ | 0 | 1e-2 | 1e-1
---|---|---|---
$10\%$ | $81.19_{\pm 0.08}$ | $\mathbf{83.32}_{\pm 0.19}$ | $83.04_{\pm 0.23}$
$30\%$ | $79.77_{\pm 0.08}$ | $\mathbf{82.14}_{\pm 0.23}$ | $82.08_{\pm 0.25}$
$50\%$ | $79.40_{\pm 0.06}$ | $81.79_{\pm 0.21}$ | $\mathbf{82.04}_{\pm 0.20}$
$70\%$ | $78.22_{\pm 0.13}$ | ${80.90}_{\pm 0.24}$ | $\mathbf{80.97}_{\pm 0.28}$
Table 4: Sensitivity study on scaling factor $\lambda$. The results are
reported on ogbn-proteins+DeeperGCN.

##  5 Conclusion & Limitation

In this paper, we introduce a 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 local context, providing a 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 on 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 on 1-hop decomposition to represent
each node’s local context. The performance of extending this approach to
$k$-hop contexts remains unexplored, suggesting a possible direction for
future research.

## References

  * [1] 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 on Knowledge Discovery and Data Mining, pages 2120–2131, 2023.
  * [2] 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.  AI open, 1:57–81, 2020.
  * [3] 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 on research and development in information retrieval, pages 726–735, 2021.
  * [4] Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoc Viet Hung Nguyen.  Are graph augmentations necessary? simple graph contrastive learning for recommendation.  In Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval, pages 1294–1303, 2022.
  * [5] 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 on Knowledge and Data Engineering, 2022.
  * [6] 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), pages 598–607. IEEE, 2019.
  * [7] 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.
  * [8] Zaixi Zhang and Qi Liu.  Learning subpocket prototypes for generalizable structure-based drug design.  In International Conference on Machine Learning, pages 41382–41398. PMLR, 2023.
  * [9] 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):119–328, 2023.
  * [10] 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, 2023.
  * [11] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  arXiv preprint arXiv:1903.02428, 2019.
  * [12] 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 preprint arXiv:1909.01315, 2019.
  * [13] 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 sparsification.  Transactions on Machine Learning Research, 2023.
  * [14] 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, 2024.
  * [15] Kun Wang, Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang.  Searching lottery tickets in graph neural networks: A dual perspective.  In The Eleventh International Conference on Learning Representations, 2022.
  * [16] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah.  Graph condensation for graph neural networks.  arXiv preprint arXiv:2110.07580, 2021.
  * [17] 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, 2024.
  * [18] Yuhan Chen, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge, and Nishil Talati.  Demystifying graph sparsification algorithms in graph properties preservation.  arXiv preprint arXiv:2311.12314, 2023.
  * [19] 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.03358, 2024.
  * [20] 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, pages 1695–1706. PMLR, 2021.
  * [21] 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.
  * [22] 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, pages 11458–11468. PMLR, 2020.
  * [23] Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al.  Gslb: The graph structure learning benchmark.  Advances in Neural Information Processing Systems, 36, 2024.
  * [24] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang.  Learning to drop: Robust graph neural network via topological denoising.  In Proceedings of the 14th ACM international conference on web search and data mining, pages 779–787, 2021.
  * [25] 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 on Knowledge Discovery & Data Mining, pages 461–471, 2020.
  * [26] 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, 2023.
  * [27] Li Wang, Wei Huang, Miao Zhang, Shirui Pan, Xiaojun Chang, and Steven Weidong Su.  Pruning graph neural networks by evaluating edge properties.  Knowledge-Based Systems, 256:109847, 2022.
  * [28] Zheng Gong, Guifeng Wang, Ying Sun, Qi Liu, Yuting Ning, Hui Xiong, and Jingyu Peng.  Beyond homophily: Robust graph anomaly detection via neural sparsification.  In Proceedings of International Joint Conference on Artificial Intelligence, pages 2104–2113, 2023.
  * [29] Daniel A Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 563–568, 2008.
  * [30] 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, 32(1):4–24, 2020.
  * [31] 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.
  * [32] 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, pages 2934–2945, 2021.
  * [33] 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, 2022.
  * [34] Thomas N. Kipf and Max Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  In Proceedings of the 5th International Conference on Learning Representations, 2017.
  * [35] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Proceedings of NIPS, 2017.
  * [36] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International conference on machine learning, pages 1263–1272. PMLR, 2017.
  * [37] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  In Proceedings of NIPS, 2018.
  * [38] Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim.  Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction.  Advances in Neural Information Processing Systems, 34:13683–13694, 2021.
  * [39] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  Advances in neural information processing systems, 31, 2018.
  * [40] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković.  Principal neighbourhood aggregation for graph nets.  Advances in Neural Information Processing Systems, 33:13260–13271, 2020.
  * [41] Ingo Althöfer, Gautam Das, David Dobkin, and Deborah Joseph.  Generating sparse spanners for weighted graphs.  In SWAT 90: 2nd Scandinavian Workshop on Algorithm Theory Bergen, Sweden, July 11–14, 1990 Proceedings 2, pages 26–37. Springer, 1990.
  * [42] 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), pages 3630–3649. SIAM, 2022.
  * [43] Joshua Batson, Daniel A Spielman, Nikhil Srivastava, and Shang-Hua Teng.  Spectral sparsification of graphs: theory and algorithms.  Communications of the ACM, 56(8):87–94, 2013.
  * [44] Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani.  Sgcn: A graph sparsifier based on graph convolutional networks.  In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 275–287. Springer, 2020.
  * [45] Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin.  Early-bird gcns: Graph-network co-optimization towards more efficient gcn training and inference via drawing early-bird lottery tickets.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8910–8918, 2022.
  * [46] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan.  Towards unsupervised deep graph structure learning.  In Proceedings of the ACM Web Conference 2022, pages 1392–1403, 2022.
  * [47] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan.  Nodeformer: A scalable graph structure learning transformer for node classification.  Advances in Neural Information Processing Systems, 35:27387–27401, 2022.
  * [48] Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton.  Adaptive mixtures of local experts.  Neural computation, 3(1):79–87, 1991.
  * [49] Ke Chen, Lei Xu, and Huisheng Chi.  Improved learning algorithms for mixture of experts in multiclass classification.  Neural networks, 12(9):1229–1252, 1999.
  * [50] Michael I Jordan and Robert A Jacobs.  Hierarchical mixtures of experts and the em algorithm.  Neural computation, 6(2):181–214, 1994.
  * [51] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  arXiv preprint arXiv:1701.06538, 2017.
  * [52] 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.16668, 2020.
  * [53] William Fedus, Barret Zoph, and Noam Shazeer.  Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, 2021.
  * [54] 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, pages 4057–4086, 2022.
  * [55] Stephen Roller, Sainbayar Sukhbaatar, Jason Weston, et al.  Hash layers for large sparse models.  In Advances in Neural Information Processing Systems, pages 17555–17566, 2021.
  * [56] 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 arXiv:2203.15556, 2022.
  * [57] 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, pages 8583–8595, 2021.
  * [58] Basil Mustafa, Carlos Riquelme, Joan Puigcerver, Rodolphe Jenatton, and Neil Houlsby.  Multimodal contrastive learning with limoe: the language-image mixture of experts.  arXiv preprint arXiv:2206.02770, 2022.
  * [59] Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi.  Modeling task relationships in multi-task learning with multi-gate mixture-of-experts.  In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1930–1939, 2018.
  * [60] Jinguo Zhu, Xizhou Zhu, Wenhai Wang, Xiaohua Wang, Hongsheng Li, Xiaogang Wang, and Jifeng Dai.  Uni-Perceiver-MoE: Learning sparse generalist models with conditional moes.  arXiv preprint arXiv:2206.04674, 2022.
  * [61] Fenyu Hu, W Liping, L Qiang, Shu Wu, Liang Wang, and Tieniu Tan.  Graphdive: graph classifcation by mixture of diverse experts.  In IJCAI, 2022.
  * [62] 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.07109, 2022.
  * [63] Suyeon Kim, Dongha Lee, SeongKu 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, pages 8291–8299, 2023.
  * [64] 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, 2023.
  * [65] Haotao Wang, Ziyu Jiang, Yuning You, Yan Han, Gaowen Liu, Jayanth Srinivasa, Ramana Kompella, Zhangyang Wang, et al.  Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling.  Advances in Neural Information Processing Systems, 36, 2024.
  * [66] Xinyu Zhao, Xuxi Chen, Yu Cheng, and Tianlong Chen.  Sparse moe with language guided routing for multilingual machine translation.  In The Twelfth International Conference on Learning Representations, 2024.
  * [67] Junjie Liu, Zhe Xu, Runbin Shi, Ray CC Cheung, and Hayden KH So.  Dynamic sparse training: Find efficient sparse network from scratch with trainable masked layers.  arXiv preprint arXiv:2005.06870, 2020.
  * [68] Hyunjin Seo, Jihun Yun, and Eunho Yang.  TEDDY: Trimming edges with degree-based discrimination strategy.  In The Twelfth International Conference on Learning Representations, 2024.
  * [69] Allan H. Murphy.  The finley affair: A signal event in the history of forecast verification.  Weather and Forecasting, 11(1):3 – 20, 1996.
  * [70] 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, page 721–732, New York, NY, USA, 2011. Association for Computing Machinery.
  * [71] Guihong Wan and Haim Schweitzer.  Edge sparsification for graphs via meta-learning.  In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 2733–2738. IEEE, 2021.
  * [72] Omer Sagi and Lior Rokach.  Ensemble learning: A survey.  Wiley interdisciplinary reviews: data mining and knowledge discovery, 8(4):e1249, 2018.
  * [73] 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-Based Systems, 189:105102, 2020.
  * [74] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov.  Clustering on multi-layer graphs via subspace analysis on grassmann manifolds.  IEEE Transactions on signal processing, 62(4):905–918, 2013.
  * [75] 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.
  * [76] 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.
  * [77] Russell Merris.  A survey of graph laplacians.  Linear and Multilinear Algebra, 39(1-2):19–31, 1995.
  * [78] Zhongxiao Jia and GW Stewart.  An analysis of the rayleigh–ritz method for approximating eigenspaces.  Mathematics of computation, 70(234):637–647, 2001.
  * [79] 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.08455, 2022.
  * [80] 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.
  * [81] Boris Knyazev, Graham W Taylor, and Mohamed Amer.  Understanding attention and generalization in graph neural networks.  Advances in neural information processing systems, 32, 2019.
  * [82] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem.  Deepergcn: All you need to train deeper gcns.  arXiv preprint arXiv:2006.07739, 2020.
  * [83] Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J Yannakoudakis.  Rank degree: An efficient algorithm for graph sampling.  In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 120–129. IEEE, 2016.
  * [84] Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner.  Structure-preserving sparsification methods for social networks.  Social Network Analysis and Mining, 6:1–22, 2016.
  * [85] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  ACM Trans. Knowl. Discov. Data, 1:2, 2006.
  * [86] Allan H Murphy.  The finley affair: A signal event in the history of forecast verification.  Weather and forecasting, 11(1):3–20, 1996.
  * [87] 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, pages 721–732, 2011.
  * [88] 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 Knowledge discovery and data mining, pages 824–833, 2007.
  * [89] 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 arXiv:2308.02916, 2023.
  * [90] 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.
  * [91] Yongduo Sui, Xiang Wang, Tianlong Chen, Xiangnan He, and Tat-Seng Chua.  Inductive lottery ticket learning for graph neural networks.  2021\.
  * [92] Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun.  Training graph neural networks with 1000 layers.  In International conference on machine learning, pages 6437–6449. PMLR, 2021.
  * [93] 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 arXiv:2103.13355, 2021.
  * [94] 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, pages 2091–2100, 2021.
  * [95] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr.  Snip: Single-shot network pruning based on connection sensitivity.  arXiv preprint arXiv:1810.02340, 2018.
  * [96] Kale-ab Tessera, Sara Hooker, and Benjamin Rosman.  Keep the gradients flowing: Using gradient flow to study sparse network optimization.  arXiv preprint arXiv:2102.01670, 2021.
  * [97] Tim Dettmers, Luke Zettlemoyer, and Zhang.  Sparse networks from scratch: Faster training without losing performance.  arXiv preprint arXiv:1907.04840, 2019.
  * [98] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  arXiv preprint arXiv:2003.00982, 2020.
  * [99] N. Talati, H. Ye, S. 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), pages 1270–1287, Los Alamitos, CA, USA, oct 2022. IEEE Computer Society.
  * [100] Christian L Staudt, Aleksejs Sazonovs, and Henning Meyerhenke.  Networkit: A tool suite for large-scale complex network analysis.  Network Science, 4(4):508–530, 2016.

##  Appendix A Notations

We conclude the commonly used notations throughout the manuscript in Table 5.

Table 5: The notations that are commonly used in the manuscript. Notation |  Definition
---|---
$\mathcal{G}=\left\\{\mathcal{V},\mathcal{E}\right\\}=\left\\{\mathbf{A},\mathbf{X}\right\\}$ |  Input graph
$\mathbf{A}$ |  Input adjacency matrix
$\mathbf{X}$ |  Node feature matrix
$\mathbf{L}$ |  Graph Laplacian matrix
$\texttt{COMB}(\cdot)$ |  GNN ego-node transformation function
$\texttt{AGGR}(\cdot)$ |  GNN message aggregation function
$\texttt{ESMB}(\cdot)$ |  Sparse graph combination function
$s\%$ |  Sparsity ratio (the ratio of removed edges)
$v_{i}$ |  The $i$-th node in $\mathcal{G}$
$x_{i}$ |  Node feature vector for $v_{i}$
$\mathcal{G}^{(i)}$ |  The 1-hop ego-graph for $v_{i}$
$\phi(\mathcal{G}^{(i)})$ |  Routing network
$K$ |  The number of total sparsifier experts
$k$ |  The number of selected sparsifier experts per node
$W_{g},W_{n}$ |  Trainable parameters in the routing network
$\kappa(\mathcal{G})$ |  A graph sparsifier
$\mathcal{G}^{(i)}_{m}$ |  The sparse ego-graph of $v_{i}$ produced by the $m$-th graph sparsifier
$\widehat{\mathcal{G}^{(i)}}=\\{\widehat{\mathcal{V}^{(i)}},\widehat{\mathcal{E}^{(i)}}\\}$ |  The ensemble sparse graph produced by MoG for $v_{i}$
$\mathcal{E}_{p}^{(i)}$ |  Edges removed surrounding $v_{i}$
$c^{m}(e_{ij})$ |  Prior guidance on edge importance $e_{ij}$

##  Appendix B Deatils on Pruning Criteria

In this section, we will thoroughly explain the four pruning criteria we
selected and the rationale behind these choices.

  * •

Edge degree of $e_{ij}$ is defined as follows:

$\operatorname{Degree}\;(e_{ij})=\frac{1}{2}\left(|\mathcal{N}(v_{i})+\mathcal{N}(v_{j})|\right).$
(17)

Previous methods [27, 68] have explicitly or implicitly used edge degree for
graph sparsification. Intuitively, edges with higher degrees are more
replaceable. [27] further formalizes this intuition from the perspective of
bridge edges.

  * •

Jaccard Similarity [86] measures the similarity between two sets by computing
the portion of shared neighbors between two nodes ($v_{i}$and $v_{j}$), as
defined below:

$\operatorname{JaccradSimilarity}\;v_{i},v_{j})=\frac{|\mathcal{N}(v_{i})\cap\mathcal{N}(v_{j})|}{|\mathcal{N}(v_{i})\cup\mathcal{N}(v_{j})|}.$
(18)

Jaccard similarity is widely used for its capacity for detecting clusters,
hubs, and outliers on social networks [86, 88, 87].

  * •

Effective Resistance, derived from the analogy to electrical circuits, is
applied to 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, [29] 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:

$\forall\boldsymbol{x}\in\mathbb{R}^{|\mathcal{V}|}\ \ \
(1-\epsilon)\boldsymbol{x}^{T}\mathbf{L}\boldsymbol{x}\leq\boldsymbol{x}^{T}\tilde{\mathbf{L}}\boldsymbol{x}\leq(1+\epsilon)\boldsymbol{x}^{T}\mathbf{L}\boldsymbol{x},$
(19)

where $\tilde{\mathbf{L}}$ is the Laplacian of the sparsified graph, and
$\epsilon>0$ is a 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 on the quadratic form of the graph Laplacian, such as
min-cut/max-flow problems. For computation simplicity, we do not directly
utilize the definition of effective resistance, and use its approximation
version [13].

  * •

Gradient Magnitude, a widely used pruning criterion, is prevalent not only in
the field of graph sparsification but also in classical neural network
pruning. Numerous studies [95, 96, 97] leverage gradient magnitude to estimate
parameter importance. Specifically for graph sparsification, MGSpar [71] 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.

##  Appendix C Graph Mixture on Grassmann Manifold

In this section, we detail how we leverage the concept of Grassmann Manifold
to effectively combine different sparse (ego-)graphs output by various
sparsifiers.

According to Equation 10, each orthonormal matrix represents a unique subspace
and thus corresponds to a distinct point on the Grassmann manifold [76]. This
applies to the eigenvector matrix of the normalized Laplacian matrix
($\mathbf{U}=\mathbf{L}[:,:p]\in\mathbb{R}^{n\times p}$), which comprises the
first $p$ eigenvectors and is orthonormal [77], and thereby can be mapped onto
the Grassmann manifold. Additionally, each row of the eigenvector matrix
encapsulates the spectral embedding of each node in a p-dimensional space,
where adjacent nodes have similar embedding vectors. This subspace
representation, summarizing graph information, is applicable to various tasks
such as clustering, classification, and graph merging [74].

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 $\\{\widetilde{\mathcal{G}}^{(i)}_{m}\\}_{m=1}^{k}$ on the Grassmann
Manifold. Moreover, this should guided by the expert scores computed by the
routing network in Section 3.2. Let $\mathbf{D}_{m}$ and $\mathbf{A}_{m}$
denote the degree matrix and the adjacency matrix for
$\widetilde{\mathcal{G}}^{(i)}_{m}$ (we omit the superscript $(\cdot)^{(i)}$
denoting $v_{i}$ for simplicity in the subsequent expressions), then the
normalized graph Laplacian is defined as:

$\mathbf{L}_{m}=\mathbf{D}_{m}^{-\frac{1}{2}}(\mathbf{D}_{m}-\mathbf{A}_{m})\mathbf{D}_{m}^{\frac{1}{2}}.$
(20)

Given the graph Laplacian $\mathbf{L}_{m}$ for each sparse graph, we calculate
the spectral embedding matrix $\mathbf{U}_{m}$ through trace minimization:

$\min_{\mathbf{U}_{m}\in\mathbb{R}^{|\mathcal{N}(v_{m})|\times
p}}\operatorname{tr}\;(\mathbf{U}_{m}^{\top}\mathbf{L}_{m}\mathbf{U}_{m}),\;\;\operatorname{s.t.}\;\mathbf{U}_{m}^{\top}\mathbf{U}_{m}=\mathbf{I},$
(21)

which can be solved by the Rayleigh-Ritz theorem. As mentioned above, each
point on the Grassmann manifold can be represented by an orthonormal matrix
$\mathbf{Y}\in\mathbb{R}^{|\mathcal{N}(v_{i})|\times p}$ whose columns span
the corresponding $p$-dimensional subspace in
$\mathbb{R}^{|\mathcal{N}(v_{i})|\times p}$. The distance between such
subspaces can be computed as a set of principal angles
$\\{\theta_{i}\\}_{i=1}^{k}$ between these subspaces. [74] showed that the
projection distance between two subspaces $\mathbf{Y}_{1}$ and
$\mathbf{Y}_{2}$ can be represented as a separate trace minimization problem:

$d^{2}_{\text{proj}}(\mathbf{Y}_{1},\mathbf{Y}_{2})=\sum_{i=1}^{p}\sin^{2}{\theta_{i}}=k-\operatorname{tr}\;(\mathbf{Y}_{1}\mathbf{Y}_{1}^{\top}\mathbf{Y}_{2}\mathbf{Y}_{2}^{\top}).$
(22)

Based on this, we further define the projection of the final representative
subspace $\mathbf{U}$ and the $k$ sparse candidate subspace
$\\{\mathbf{U}_{m}\\}_{m=1}^{k}$:

$d^{2}_{\text{proj}}(\mathbf{U},\\{\mathbf{U}_{m}\\}_{m=1}^{k})=\sum_{m=1}^{k}d^{2}_{\text{proj}}(\mathbf{U},\mathbf{U}_{m})=p\times
k-\sum_{m=1}^{k}\operatorname{tr}\;(\mathbf{U}\mathbf{U}^{\top}\mathbf{U}_{m}\mathbf{U}_{m}^{\top}),$
(23)

which ensures that individual subspaces are close to the final representative
subspace $\mathbf{U}$.

Finally, to maintain the original vertex connectivity from all $k$ sparse ego-
graphs and emphasize the connectivity relationship from more reliable
sparsifiers (with higher expert scores), we propose the following objective
function:

$\min_{\mathbf{U}_{m}\in\mathbb{R}^{|\mathcal{N}(v_{m})|\times
p}}\sum_{m=1}^{k}E^{(i)}_{m}\left(p\times
k-\sum_{m=1}^{k}\operatorname{tr}\;(\mathbf{U}\mathbf{U}^{\top}\mathbf{U}_{m}\mathbf{U}_{m}^{\top})\right),$
(24)

where $E^{(i)}_{m}$ represents the expert score of the node $v_{i}$’s $m$-th
sparsifier expert. Based on Equations 21 and 24, we present the overall
objective:

$\min_{\mathbf{U^{(i)}}\in\mathbb{R}^{|\mathcal{N}(v_{i})|\times
p}}\sum_{m=1}^{k}\left(\underbrace{\operatorname{tr}(\mathbf{U^{(i)}}^{\top}\mathbf{L}_{m}\mathbf{U}^{(i)})}_{\textrm{(1)
node connectivity}}+\underbrace{E^{(i)}_{m}\cdot
d^{2}(\mathbf{U}^{(i)},\mathbf{U}^{(i)}_{m})}_{\textrm{(2) subspace
distance}}\right),\operatorname{s.t.}\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}=\mathbf{I}.$
(25)

According to Rayleigh-Ritz theorem [74], we give the closed-form solution of
Equation 25 as follows:

$\widehat{\mathbf{L}^{(i)}}=\sum_{m=1}^{k}\left(\mathbf{L}_{m}-E_{m}^{(i)}\cdot\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}\right).$
(26)

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 of each node,
such computational burden is entirely acceptable. Specific complexity analyses
are presented in Appendix E.

##  Appendix D Algorithm Workflow

The algorithm framework is presented in Algo. 1.

Input : $\mathcal{G}=(\mathbf{A},\mathbf{X})$, GNN model
$f(\mathcal{G},\mathbf{\Theta})$, , epoch number $Q$.

Output : Sparse graph
$\mathcal{G}^{\text{sub}}=\\{\mathcal{V},\mathcal{E}^{\prime}\\}$

for  _iteration $q\leftarrow 1$ to $Q$_ do

/* Ego-graph decomposition */

Decompose $\mathcal{G}$ into ego-graph representations
$\\{\mathcal{G}^{(1)},\mathcal{G}^{(2)},\cdots,\mathcal{G}^{(N)}\\}$.

/* Sparsifier expert allocation */

for  _node $i\leftarrow 1$ to $|\mathcal{V}|$_ do

Calculate the total $K$ expert score of $v_{i}$ by routing network
$\psi(x_{i})$;

$\triangleright$ Eq. 3

Select $k$ sparsifier expert for node $v_{i}$ by
$\operatorname{Softmax}(\operatorname{TopK}(\psi(x_{i}),k))$;

$\triangleright$ Eq. 3

end for

/* Produce sparse graph condidates */

for  _iteration $i\leftarrow 1$ to $|\mathcal{V}|$_ do

for  _sparsifier index $m\leftarrow 1$ to $m$_ do

Sparisifier $\kappa^{m}$ determines which edges to remove by
$\mathcal{E}_{p}^{(i)}=\operatorname{TopK}\left(-C^{m}(\mathcal{E}),\lceil|\mathcal{E}^{(i)}|\times
s\%\rceil\right)$;

$\triangleright$ Eq. 8

Produce sparse graph candidate
$\widetilde{\mathcal{G}}^{(i)}=\kappa^{m}(\mathcal{G}^{(i)})=\\{\mathcal{V}^{(i)},\mathcal{E}^{(i)}\setminus\mathcal{E}_{p}^{(i)}\\}$.

end for

/* Ensenmble sparse graphs on Grassmann manifold */

Calculate the ensemble graph’s graph Laplacian by
$\widehat{\mathbf{L}^{(i)}}=\sum_{m=1}^{k}\left(\mathbf{L}_{m}-E_{m}^{(i)}\cdot\mathbf{U^{(i)}}^{\top}\mathbf{U^{(i)}}\right)$;

$\triangleright$ Eq. 12

Obtain $v_{i}$’s final sparse graph by
$\texttt{ESMB}(\\{\widehat{\mathcal{G}^{(i)}}=\\{\mathbf{D}-\widehat{\mathbf{L}^{(i)}},\mathbf{X}^{(i)}\\})$;

$\triangleright$ Eq. 13

Compute $v_{i}$’s weighted sparsity by
$s^{(i)}\%=\frac{1}{k}\sum_{m=1}^{k}s^{m}\%$;

$\triangleright$ Eq. 14

Post-sparsify $\widehat{\mathcal{G}^{(i)}}$:
$\widehat{\mathcal{G}^{(i)}}\leftarrow\\{\operatorname{TopK}(\widehat{\mathbf{A}^{(i)}},|\mathcal{E}^{(i)}|\times
s^{(i)}\%),\mathbf{X}^{(i)}\\}$;

$\triangleright$ Eq. 14

end for

/* Combine ego-graphs */

$\widehat{\mathcal{G}}\leftarrow\\{\widehat{\mathcal{G}^{(1)}},\widehat{\mathcal{G}^{(2)}},\cdots,\widehat{\mathcal{G}^{(|\mathcal{V}|)}}\\}$

/* Standard GNN training */

Feed the sparse graph $\widehat{\mathcal{G}}$ into GNN model for any kinds of
downstream training ;

$\triangleright$ Eq. 6

Compute loss
$\mathcal{L}_{\text{task}}+\lambda\cdot\mathcal{L}_{\text{importance}}$;

$\triangleright$ Eq. 16

Backpropagate to update GNN $f(\mathcal{G},\mathbf{\Theta})$, routing network
$\psi$ and sparsifiers $\\{\kappa^{m}\\}_{m=1}^{K}$.

end for

Algorithm 1 Algorithm workflow of MoG

##  Appendix E Complexity Analysis

In this section, we delve into a 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. It is worth recalling that the forward time
complexity of vanilla GCN is given by:

$\mathcal{O}(L\times|\mathcal{E}|\times D+L\times|\mathcal{V}|\times D^{2}),$
(27)

where $L$ is the number of GNN layers, $|\mathcal{E}|$ and $|\mathcal{V}|$
denotes the number of edges and nodes, respectively, and $D$ is the hidden
dimension. Similarly, the forward space complexity of GCN is:

$\mathcal{O}(L\times|\mathcal{E}|+L\times D^{2}+L\times|\mathcal{V}|\times D)$
(28)

When MoG is applied to GCN, each sparsifier expert $\kappa(\cdot)$ essentially
introduces additional complexity equivalent to that of an
$\operatorname{FFN}(\cdot)$, as depicted in Equation 9. Incorporating the
Sparse MoE-style structure, the forward time complexity of GCN+MoG becomes:

$\mathcal{O}(L\times|\mathcal{E}|\times D+L\times|\mathcal{V}|\times
D^{2}+k\times|\mathcal{E}|\times D\times D^{s}),$ (29)

where $D^{s}$ represents the hidden dimension of the feed-forward network in
Equation 9 and $k$ denotes the number of selected experts. Similarly, the
forward space complexity is increased to:

$\mathcal{O}(L\times|\mathcal{E}|+L\times D^{2}+L\times|\mathcal{V}|\times
D+k\times|\mathcal{E}|\times D\times D^{s}).$ (30)

It is noteworthy that we omit the analysis for the routing network, as its
computational cost is meanwhile negligible compared to the cost of selected
experts, since both $W_{g}\in\mathbb{R}^{K\times F}$ and
$W_{n}\in\mathbb{R}^{K\times F}$ is in a much smaller dimension that the
weight matrix $W\in\mathbb{R}^{F\times F}$ in GCN.

Furthermore, we present the additional complexity introduced by the step of
graph mixture on the Grassmann manifold. For each center node’s $k$ sparse
ego-graphs, we need to compute the graph Laplacian and the eigenvector matrix,
which incurs an extra time complexity of
$\mathcal{O}(k\times(\frac{|\mathcal{E}|}{|\mathcal{V}|})^{3})$; to compute
the Laplacian $\widehat{\mathbf{L}^{(i)}}$ of the final ensemble sparse graph,
an additional complexity of
$\mathcal{O}(k\times(\frac{|\mathcal{E}|}{|\mathcal{V}|})^{2}\times p)$ is
required. In the end, the complete time complexity of MoG is expressed as:

$\mathcal{O}\left(\underbrace{L\times|\mathcal{E}|\times
D+L\times|\mathcal{V}|\times D^{2}}_{\text{vanilla
GCN}}+\underbrace{k\times|\mathcal{E}|\times D\times D^{s}}_{\text{sparsifier
experts}}+\underbrace{k\left(\frac{|\mathcal{E}|}{|\mathcal{V}|}\right)^{3}+k\left(\frac{|\mathcal{E}|}{|\mathcal{V}|}\right)^{2}p}_{\text{graph
mixture}}\right).$ (31)

To empirically verify that MoG does not impose excessive computational burdens
on GNN backbones, we conduct experiments in Section G.2 to compare the per-
epoch time efficiency metric of MoG with other sparsifiers.

##  Appendix F Experimental Details

###  F.1 Dataset Statistics

We conclude the dataset statistics in Tab. 6

Table 6: Graph datasets statistics.

Dataset |  $\\#$Graph |  $\\#$Node |  $\\#$Edge |  $\\#$Classes | Metric
---|---|---|---|---|---
Ogbn-ArXiv | 1 | 169,343 | 1,166,243 | 40 | Accuracy
Ogbn-Proteins | 1 | 132,534 | 39,561,252 | 2 | ROC-AUC
Ogbn-Products | 1 | 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

###  F.2 Evaluation Metrics

Accuracy represents the ratio of correctly predicted outcomes to the total
predictions made. The ROC-AUC (Receiver Operating Characteristic-Area Under
the Curve) value quantifies the probability that a 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 [80]. Specifically, for Ogbn-ArXiv, we
train on papers published until 2017, validate on papers from 2018 and test on
those published since 2019. For Ogbn-Proteins, 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 [80] for Ogbg-PPA. Concretely, we adopt the
species split, where the neighborhood graphs in the validation and test sets
are extracted from protein association 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 [98], we split them to
55000 train/5000 validation/10000 test for MNIST, and 45000 train/5000
validation/10000 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 a 3-layer GraphSAGE with
$\texttt{hidden\\_dim}\in\\{128,256\\}$. As for DeeperGCN, we set
$\texttt{layer\\_num}=28$, $\texttt{block}=\texttt{res+}$,
$\texttt{hidden\\_dim}=64$. The other configurations are the same as in
https://github.com/lightaime/deep_gcns_torch/tree/master/examples/ogb/ogbn_proteins.
For graph classification backbones, we leverage a 4-layer PNA with
$\texttt{hidden\\_dim}=300$. Rest configurations are the same as in
https://github.com/lukecavabarrett/pna.

#### MoG parameters

We adopt the $m=4$ sparsity criteria outlined in Section 3.3, assigning $n=3$
different sparsity levels $\\{s_{1},s_{2},s_{3}\\}$ to each criterion,
resulting in a total of $K=m\times n=12$ experts. We select $k=2$ sparsifier
experts for each node, and set the loss scaling factor $\lambda=1e-2$ across
all datasets and backbones.

All the experiments are conducted on NVIDIA Tesla V100 (32GB GPU), using
PyTorch and PyTorch Geometric framework.

###  F.5 Sparsifier Baseline Configurations

  * •

Topology-based sparsification

    * –

Rank Degree [99]: The Rank Degree sparsifier initiates by selecting a random
set of "seed" vertices. Then, the vertices with connections to these seed
vertices are 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 is attained. We utilize the
implementation in [18].

    * –

Local Degree [84]: Local Degree sparsifier, similar to Rank Degree,
incorporates edges to the top $\operatorname{deg}(v)^{\alpha}$ neighbors
ranked by their degree in descending order, where $\alpha\in[0,1]$ represents
the degree of sparsification.

    * –

Forest Fire [85]: Forest fire assembles “burning” through edges
probabilistically, and we use the implementation in [100].

    * –

G-Spar [86]: G-Spar sorts the Jaccard scores globally and then selects the
edges with the highest similarity score. We opt for the code from [100].

    * –

Local Similarity [87]: Local Similarity ranks edges using the Jaccard score
and computes
$\log(\operatorname{rank}(e_{ij}))/\log(\operatorname{deg}(e_{ij}))$ as the
similarity score, and selects edges with the highest similarity scores. We
utilize the implementation in [18].

    * –

SCAN [29]: SCAN uses structural similarity (called SCAN similarity) measures
to detect clusters, hubs, and outliers. We utilize the implementation in [18]

    * –

DSpar [13]: 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 [13].

  * •

Semantic-based sparsification

    * –

UGS [20]: 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 $p_{\theta}$ and the graph pruning ratio
$p_{g}$. In each iteration, a corresponding proportion of parameters/edges is
pruned. For a fairer comparison, we set $p_{\theta}=0\%$, while maintaining
$p_{g}\in\\{5\%,10\\}$ (consistent with the original paper).

    * –

GEBT [45]: 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. [45] has proposed two variants of graph early bird tickets, and we opt
for the graph-sparsification-only version, dubbed GEB Ticket Identification.

    * –

Meta-gradient sparsifier [71]: The Meta-gradient sparsifier prunes edges based
on their meta-gradient 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 [89]: ACE-GLT inherits the iterative magnitude pruning (IMP) paradigm
from UGS. Going beyond UGS, it suggested mining valuable information from
pruned edges/weights after each round of IMP, which in the meanwhile doubled
the computational cost of IMP. We utilize the official implementation provided
by [89], and set $p_{\theta}=0\%,p_{g}\in\\{5\%,10\\}$.

    * –

WD-GLT [90]: WD-GLT also inherits the iterative magnitude pruning paradigm
from UGS, so we also set $p_{\theta}=0\%,p_{g}\in\\{5\%,10\%\\}$ across all
datasets and backbones. The perturbation ratio $\alpha$ is tuned among
$\\{0,1\\}$. Since no official implementation is provided, we carefully
reproduced the results according to the original paper.

    * –

AdaGLT [17]: AdaGLT revolutionizes the original IMP-based graph lottery ticket
methodology into an adaptive, dynamic, and automated approach, proficient in
identifying sparse graphs with layer-adaptive structures. We fix
$\eta_{\theta}=0\%,\eta_{g}\in\\{1e-6,1e-5,1e-4,1e-3,1e-2\\},\omega=2$ across
all datasets and backbones.

###  F.6 Adjusting Graph Sparsity

In Table 7, we provide detailed guidelines on how to achieve the desired
global sparsity by adjusting the three sparsity levels
$\\{s_{1},s_{2},s_{3}\\}$ in MoG across six datasets.

Table 7: The recipe for adjusting graph sparsity via different sparsifier combinations.  Datasets | $1-s_{1}$ | $1-s_{2}$ | $1-s_{3}$ | $k$ | $1-s\%$
---|---|---|---|---|---
ogbn-arxiv | 1 | 0.9 | 0.8 | 2 | [88.0%,90.9%]
0.8 | 0.7 | 0.5 | 2 | [69.0%,73.2%]
0.6 | 0.5 | 0.3 | 2 | [49.5%,52.7%]
0.5 | 0.3 | 0.15 | 2 | [27.1%, 31.6%]
ogbn-proteins | 1 | 0.9 | 0.8 | 2 | [86.1%,89.3%]
0.8 | 0.7 | 0.6 | 2 | [65.1%,69.2%]
0.6 | 0.5 | 0.4 | 2 | [45.2%,49.3%]
0.4 | 0.3 | 0.2 | 2 | [29.2%,31.1%]
ogbn-products | 1 | 0.9 | 0.8 | 2 | [90.1%,93.2%]
0.8 | 0.7 | 0.6 | 2 | [69.3%,72.0%]
0.6 | 0.5 | 0.4 | 2 | [51.5%,54.9%]
0.4 | 0.3 | 0.2 | 2 | [28.7%,36.0%]
mnist | 1 | 0.85 | 0.8 | 2 | [90.4%,92.7%]
0.8 | 0.5 | 0.4 | 2 | [67.1%,68.3%]
0.6 | 0.3 | 0.2 | 2 | [46.2%,49.3%]
0.35 | 0.1 | 0.1 | 2 | [29.8%,31.3%]
cifar-10 | 1 | 0.85 | 0.8 | 2 | [90.6%,93.7%]
0.8 | 0.5 | 0.4 | 2 | [67.5%,69.9%]
0.6 | 0.3 | 0.2 | 2 | [47.7%,49.3%]
0.35 | 0.1 | 0.1 | 2 | [30.1%,31.3%]
ogbg-ppa | 0.95 | 0.9 | 0.8 | 2 | [86.5%,88.9%]
0.8 | 0.65 | 0.6 | 2 | [68.0%,70.1%]
0.6 | 0.5 | 0.3 | 2 | [47.8%,48.9%]
0.4 | 0.3 | 0.15 | 2 | [30.1%,33.6%]

##  Appendix G Addtional Experiment Results

###  G.1 Results for RQ1

We report the performances of MoG and other sparsifiers on ogbn-products in
Table 8.

Table 8: 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 ${\dagger}$ that do not have precise control over sparsity; their performance is reported around the target sparsity $\pm 2\%$. We do not report results for sparsifiers like ER for OOT issues and those like UGS for their infeasibility in inductive settings (mini-batch training).  | Dataset |  ogbn-products (Accuracy $\uparrow$)
---|---|---
Sparsity % | 10 | 30 | 50 | 70
Topology | Random |  76.99↓1.05 |  74.21↓3.83 |  71.08↓6.96 |  67.24↓10.80
Rank Degree† [83] |  76.08↓1.96 |  74.26↓3.89 |  71.85↓6.19 |  70.66↓7.38
Local Degree† [84] |  77.19↓1.58 |  76.40↓1.64 |  72.77↓5.27 |  72.48↓5.56
G-Spar [86] |  76.15↓1.89 |  74.20↓3.84 |  71.55↓6.49 |  69.42↓8.62
LSim† [87] |  77.96↓0.08 |  74.98↓2.06 |  72.67↓5.37 |  70.43↓7.61
SCAN [88] |  76.30↓1.74 |  74.33↓3.71 |  71.25↓6.79 |  71.12↓6.92
DSpar [13] |  78.25↑0.21 |  75.11↓2.93 |  74.57↓3.47 |  73.16↓4.88
Sema |  AdaGLT [17] |  78.19↑0.15 |  77.30↓0.74 |  74.38↓3.66 |  73.04↓5.00
MoG (Ours)† | 78.77${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 78.15${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 76.98↓1.06 | 74.91${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>
Whole Dataset |  78.04±0.31
Table 9: Node classification performance comparison to state-of-the-art sparsification methods. All methods are trained using DeeperGCN, and the reported metrics represent the average of five runs. We denote methods with ${\dagger}$ that do not have precise control over sparsity; their performance is reported around the target sparsity $\pm 2\%$. “OOM” and “OOT” denotes out-of-memory and out-of-time, respectively.  | Dataset |  ogbn-arxiv (Accuracy $\uparrow$)
---|---|---
Sparsity % | 10 | 30 | 50 | 70
Topology-guided | Random |  70.66↓1.28 |  68.74↓3.20 |  65.38↓6.56 |  63.55↓8.39
Rank Degree† [83] |  69.44↓2.50 |  67.82↓4.12 |  65.08↓6.86 |  63.19↓8.75
Local Degree† [84] |  68.77↓3.17 |  67.92↓4.02 |  66.10↓5.84 |  65.97↓5.97
Forest Fire† [85] |  68.70↓3.24 |  68.95↓3.99 |  67.23↓4.71 |  67.29↓4.65
G-Spar [86] |  70.57↓1.37 |  70.15↓1.79 |  68.77↓3.17 |  65.26↓6.68
LSim† [87] |  69.33↓2.61 |  67.19↓4.75 |  63.55↓8.39 |  62.20↓9.74
SCAN [88] |  71.33↓0.61 |  69.22↓2.72 |  67.88↓4.06 |  64.32↓7.62
ER [29] |  71.33↓0.61 |  69.65↓2.29 |  69.08↓2.86 |  67.10↓4.84
DSpar [13] |  71.65↓0.29 |  70.66↓1.28 |  68.03↓3.91 |  67.25↓4.69
Semantic-guided |  UGS† [20] |  72.01↑0.93 |  70.29↓1.65 |  68.43↓3.51 |  67.85↓4.09
GEBT [45] |  70.22↓1.72 |  69.40↓2.54 |  67.84↓4.10 |  67.49↓4.45
MGSpar [71] |  70.02↓1.92 |  69.34↓2.60 |  68.02↓3.92 |  65.78↓6.16
ACE-GLT† [89] |  72.13↑0.19 |  71.96↑0.02 |  69.13↓2.81 |  67.93↓4.01
WD-GLT† [90] |  71.92↓0.02 |  70.21↓1.73 |  68.30↓3.64 |  66.57↓5.37
AdaGLT [17] |  71.98↑0.04 |  70.44↓1.50 |  69.15↓2.79 |  68.05↓3.89
MoG (Ours)† | 72.08${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 71.98${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 69.86↓-2.08 | 68.20${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>
Whole Dataset |  71.93±0.04
Table 10: Node classification performance comparison to state-of-the-art sparsification methods. All methods are trained using DeeperGCN, and the reported metrics represent the average of five runs. We denote methods with ${\dagger}$ that do not have precise control over sparsity; their performance is reported around the target sparsity $\pm 2\%$. “OOM” and “OOT” denotes out-of-memory and out-of-time, respectively.  | Dataset |  ogbn-proteins (ROC-AUC $\uparrow$)
---|---|---
Sparsity % | 10 | 30 | 50 | 70
Topology-guided | Random |  80.18↓2.55 |  78.92↓3.83 |  76.57↓6.16 |  72.69↓10.04
Rank Degree† [83] |  80.14↓2.59 |  79.05↓3.73 |  78.59↓4.13 |  76.22↓6.51
Local Degree† [84] |  79.40↓3.33 |  79.83↓3.90 |  78.50↓4.23 |  78.25↓4.48
Forest Fire† [85] |  81.49↓1.24 |  78.47↓4.26 |  76.14↓6.59 |  73.89↓9.84
G-Spar [86] |  81.56↓1.17 |  81.12↓1.61 |  79.13↓3.60 |  77.45↓5.28
LSim† [87] |  80.30↓2.43 |  79.19↓3.54 |  77.13↓5.60 |  77.85↓4.88
SCAN [88] |  81.60↓1.13 |  80.19↓2.54 |  81.53↓1.20 |  78.58↓4.15
ER [29] | OOT
DSpar [13] |  81.46↓1.27 |  80.57↓2.16 |  77.41↓5.32 |  75.35↓7.39
Semantic-guided |  UGS† [20] |  82.33↓0.40 |  81.54↓1.19 |  78.75↓4.98 |  76.40↓6.33
GEBT [45] |  80.74↓2.99 |  80.22↓2.51 |  79.81↓3.92 |  76.05↓6.68
MGSpar [71] | OOM
ACE-GLT† [89] |  82.93↑0.80 |  82.01↓0.72 |  81.05↓1.68 |  75.92↓6.81
WD-GLT† [90] | OOM
AdaGLT [17] |  82.60↓0.13 |  82.76↑0.97 |  80.55↓2.18 |  78.42↓4.31
MoG (Ours)† | 83.32${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 82.14${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 81.92${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>| 80.90${}_{\color[rgb]{0.15,1,0.67}\definecolor[named]{pgfstrokecolor}{rgb}{0.15,1,0.67}\pgfsys@color@cmyk@stroke{0.85}{0}{0.33}{0}\pgfsys@color<EMAIL_ADDRESS>
Whole Dataset |  82.73±0.02
Table 11: Graph classification performance comparison to state-of-the-art sparsification methods. All methods are trained using PNA, and the reported metrics represent the average of five runs. We denote methods with ${\dagger}$ that do not have precise control over sparsity; their performance is reported around the target sparsity $\pm 2\%$.  | Dataset |  cifar-10 (Accuracy $\uparrow$)
---|---|---
Sparsity % | 10 | 30 | 50 | 70
Topology | Random |  68.04↓1.70 |  66.81↓2.93 |  65.35↓4.39 |  62.14↓7.60
Rank Degree† [83] |  68.27↓1.77 |  67.14↓2.60 |  64.05↓5.69 |  60.22↓9.52
Local Degree† [84] |  68.10↓1.64 |  67.29↓2.45 |  64.96↓4.78 |  61.77↓8.97
G-Spar [86] |  67.13↓2.61 |  65.06↓4.68 |  64.86↓4.88 |  62.92↓6.82
LSim† [87] |  69.75↑0.01 |  67.33↓2.41 |  66.58↓3.16 |  64.86↓4.88
SCAN [88] |  68.25↓1.49 |  66.11↓3.63 |  64.59↓5.15 |  63.20↓6.54
DSpar [13] |  68.94↑0.53 |  66.80↓2.94 |  64.87↓4.87 |  64.10↓5.64
Sema |  AdaGLT [17] |  69.77↑0.02 |  67.97↓1.78 |  65.06↓4.68 |  64.22↓5.52
MoG (Ours)† | 70.04${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 69.80${}_{\color[rgb]{1,0.23,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.23,0.13}\pgfsys@color@cmyk@stroke{0}{0.77}{0.87}{0}\pgfsys@color<EMAIL_ADDRESS>| 68.28↓-1.46 | 66.55↓-3.19
Whole Dataset |  69.74±0.17

###  G.2 Results for Efficiency Validation

In Table 12, we present a comparison of the precision and per epoch time
between MoG and Random, AdaGLT. It can be observed that MoG incurs less
additional training cost compared to AdaGLT while achieving significant
improvements in sparsification performance. More importantly, we demonstrate
that with $k=2$, MoG does not incur significantly heavier training burdens as
the number of sparsifiers increases. Specifically, at $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 [65].

Table 12: Running time efficiency comparison on ogbn-products+GraphSAGE. We consistently set $n=4,k=2$, corresponding to utilizing 4 pruning criteria and selecting 2 experts for each node, and vary $m\in\\{1,2,3\\}$ 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$\pm$ 0.14 | 74.21$\pm$ 0.28 | 15.42 $\pm$ 0.24 | 71.08$\pm$ 0.34
AdaGLT | 23.55$\pm$ 0.20 | 77.30 $\pm$ 0.54 | 21.68 $\pm$ 0.26 | 74.38 $\pm$ 0.79
MoG ($m=1,K=3$) | 20.18$\pm$ 0.14 | 77.75 $\pm$ 0.22 | 18.19 $\pm$ 0.30 | 76.10 $\pm$ 0.49
MoG ($m=2,K=6$) | 21.25$\pm$ 0.22 | 78.23 $\pm$ 0.29 | 19.70 $\pm$ 0.30 | 76.43 $\pm$ 0.49
MoG ($m=3,K=12$) | 23.19$\pm$ 0.18 | 78.15 $\pm$ 0.32 | 20.83 $\pm$ 0.29 | 76.98 $\pm$ 0.49

##  Appendix H Broader Impact.

MoG, as a 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 as financial fraud detection and online
recommender systems, which require customized approaches. More importantly,
MoG provides a selectable pool for future sparsification, enabling various
pruning algorithms to collaborate and enhance the representational
capabilities of graphs.