TEDDY: Trimming Edges with Degree-based Discrimination Strategy
Authors: Hyunjin Seo
Jihun Yun
Eunho Yang
Venue: ICLR 2024 poster (2024)
Keywords: Graph Lottery Tickets; Graph Compression; Graph Sparsification; Graph Neural Networks
Primary area: learning on graphs and other geometries & topologies

Abstract: Since the pioneering work on the lottery ticket hypothesis for graph neural networks (GNNs) was proposed in Chen et al. (2021), the study on finding graph lottery tickets (GLT) has become one of the pivotal focus in the GNN community, inspiring researchers to discover sparser GLT while achieving comparable performance to original dense networks. In parallel, the graph structure has gained substantial attention as a crucial factor in GNN training dynamics, also elucidated by several recent studies. Despite this, contemporary studies on GLT, in general, have not fully exploited inherent pathways in the graph structure and identified tickets in an iterative manner, which is time-consuming and inefficient. To address these limitations, we introduce **TEDDY**, a one-shot edge sparsification framework that leverages structural information by incorporating *edge-degree* statistics. Following the edge sparsification, we encourage the parameter sparsity during training via simple projected gradient descent on the $\ell_0$ ball. Given the target sparsity levels for both the graph structure and the model parameters, our TEDDY facilitates efficient and rapid realization of GLT within a *single* training. Remarkably, our experimental results demonstrate that TEDDY significantly surpasses conventional iterative approaches in generalization, even when conducting one-shot sparsification that solely utilizes graph structures, without taking feature information into account.

Published as a conference paper at ICLR 2024
TEDDY: TRIMMING EDGES WITH DEGREE-BASED DISCRIMINATION STRATEGY
Hyunjin Seo' Jihuu Yun' Eunho Yang!
Korea Advanced Institute of Science and Technology (KAIST)', AITRICS (bella72, arcprime, eunhoy/ @kaist...... kr
ABSTRACT
Since the pioneering work on the lottery ticket hypothesis for graph neural networks (GNNs) was proposed in Chen et al. (2021), the study on finding graph lottery tickets (GLTT) has become one the pivotal focus in the GNN community, inspiring researchers to discover sparser GLT while achieving comparable performance original dense networks, In parallel, the graph structure has gained substantial attention as crucial factor in GNN training dynamics, also elucidated by several recent studies. Despite this, contemporary studies on GLT, in general, have not fully exploited inherent pathways in the graph structure and identified tickets an iterative manner, which is time-consuming and inefficient. To address these limitations, we introduce TEDDY, a one-shot edge sparsification framework that leverages structural information by incorporating edge-degree statistics. Following the edge sparsification, we encourage the parameter sparsity during training via simple projected gradient descent the to ball. Given the target sparsity levels for both the graph structure and the model parameters, our TEDDY facilitates efficient and rapid realization of GLT within a single training. Remarkably, our experimen- tal results demonstrate that TEDDY significantly surpasses conventional iterative approaches in generalization, even when conducting one-shot sparsification that solely utilizes graph structures, without taking feature information into account.
INTRODUCTION
Graph neural networks (GNNs) have emerged as powerful tool for modeling graph-structured data and addressing diverse graph-based tasks, such as node classification (Kipf & Welling, 2016; Hamilton et al., 2017; Xu et al., 201 8b; Wang et al., 2020; Park et al., 2021), link prediction (Zhang & Chen, 2018; Li et al., 2018; Yun et al., 2021b; Ahn & Kim, 2021; Zhu et al., 2021), and graph classification (Hamilton et al., 2017; Xu et al., 2018b; Lee et al., 2018; Sui et al., 2022; Hou et al., 2022). In conjunction with the notable performance achieved GNNs, a substantial number of recent attempts have been made to handle large-scale real-world datasets. Owing to this, datasets and network architectures in graph-related tasks have progressively become more intricate, which incurs the notorious computational overhead both in training and inference.
In response to this challenge, GNN compression has emerged as one of the main research areas in GNN communities, and the Graph Lottery Ticket (GLT) hypothesis was articulated (Chen al., 2021), serving as an extension of the conventional lottery ticket hypothesis (LTH, Frankle & Carbin (2019)) for GNN. Analogous to the conventional LTH, Chen al. (2021) claimed that the GNNs possess pair of core sub-dataset and sparse sub-network with admirable performance, referred to as GLT, which can be jointly identified from the original graph and the original dense model. order to identify GLT, Chen et al. (2021) employ an iterative pruning LTH where the edges/parameters are pruned progressively through multiple rounds until they arrive at the target sparsity level.
In parallel with advancements in GNN compression, surge of recent studies has begun to underscore the increasing significance of graph structure over node features in GNN training dynamics. Notably, Tang & Liu (2023) have derived generalization error bounds for various GNN families. Specifically, they have discovered that the model generalization of GNNs predominantly depends on the graph
Equal contribution.

---

Published as a conference paper at ICLR 2024
structure rather than node features model parameters. Furthermore, highlighted by the recent study (Sato, 2023), it has been both theoretically and empirically elucidated that GNNs can recover the hidden features even when trained on uninformative node features without the original node feature. Despite this, the preceding edge sparsification studies on identifying GLT have largely overlooked the paramount importance of graph structure.
Given the studies on GLT and the growing significance of graph structure, we introduce TEDDY, a novel edge sparsification framework that considers the structural information of the graph, aiming to maintain the primary message pathways. We begin by presenting the impact of degree information, which is observed in terms of both pruning performance and spectral stability. In alignment with our observation, TEDDY selectively discards graph edges based on scores designed by utilizing edge degrees. Our TEDDY integrates degree characteristics into the peassage-passing algorithm to carefully identify essential information pathways in multi-level consideration. Following this, our framework directly sparsifies parameters via projected gradient descent on Eo ball. It should be noted that the sparsification of both edges and parameters in our TEDDY can be achieved within single training, promoting enhanced efficiency compared to existing methods that require iterative procedures.
Our contributions are summarized as follows:
We introduce TEDDY, novel edge sparsification method that leverages structural information to preserve the integrity of principal information flow. In particular, our key observation for TEDDY lies in the importance of low-degree edges in the graph. We validate the significance of low-degree edges via comprehensive analysis.
We encourage the parameter sparsity via projected gradient descent (PGD) onto Eo ball. While conventional approaches identify the parameter tickets in iterative fashion, only single training process is required for our PGD strategy, which is much more computationally affordable.
Our extensive experiments demonstrate the state-of-the-arr performance of TEDDY over iterative GLT methods across diverse benchmark datasets and architectures. We note that TEDDY accom- plishes one-shot edge pruning without considering node features, yet it asserts highly superior performance compared to the baselines that take node features into account.
2 RELATED WORK
Graph compression can be broadly categorized into two main approaches.
Edge Sparsífication removes the edges in the graph with the number of nodes unchanged. In this line of work, in general, GNNs have differentiable masks for both graph and model parameter, and edges are pruned by the magnitudes of trained masks (Chen et al., 2021; You et al., 2022; Hui et al., 2023). As the first example, Chen et al. (2021) propose a unified framework for finding GLT by training l fi-regularized masks. To reach the target sparsity levels, they employ an iterative pruning which involves multiple pruning rounds gradually removing edges/parameters at each round. Due to the considerable time required for an iterative pruning, You et al. (2022) devise an algorithm to find GLT in an early pruning stage. More recent study (Hui et al., 2023) points that the graph sparsity matters in GLT and proposes novel regularization based on Wasserstein distance between different classes, thereby searching better generalized GLT.
Graph Coarsening, in general, reduces the graph structure typically by grouping the existing nodes into super (or virtual) nodes and defining connections between them. Loukas & Vandergheynst (2018); Loukas (2019) propose randomized edge contraction, which provably ensures that the spectral properties of the coarsened graph and the original graph are close. Also, Chiang et al. (2019) cluster the entire graph into several small subgraphs and approximate the entire gradient via the gradient for the subgraphs, thereby increasing scability. Cai et al. (2021) introduce a novel framework that learns the connections between the super nodes via graph neural networks. Jin et al. (2022) propose graph condensation to reduce the number of nodes and to learn synthetic nodes and connections in a supervised manner. The recent study (Si al., 2023) focus on graph compression in serving time, which constructs a small set of virtual nodes that summarize the entire training set with artificially modified node features.
The main purpose of this paper is to devise the edge sparsification algorithm that carefully considers the structural information of graph.
2

---

Published as a conference paper at ICLR 2024
3
PRELIMINARIES
Before introducing TEDDY, we organize the problems of interest and necessary concepts in the paper.
3.1 PROBLEM SETUP
We consider an undirected graph = (V. which consists of N | vertices and M [8] edges. The vertex set V is characterized by feature matrix X E RR XxF with rows (æ; N i=1 In parallel, the edge set & is characterized by an adjacency matrix A E R RNNx N where Aii,ji = if an edge eij (1,j) &, and A[i.j] = 0 otherwise. Given a graph G (V, and a feature matrix X, GNN fe learns the representation of each node v by iteratively aggregating hidden representations of its adjacent nodes the neighborhood set N₂ the previous layer, formulated as follows:
h (1+1) s (h,), o0 ((h) Vu E N.))))
(I)
where Φ serves as aggregation function, s combines the previous representation of v and aggregated neighbors. The initial representation h Ty and we denote this multi-layered process by f(g, θ) fe (g) where 9 is characterized by g
Our focus is semi-supervised node classification task, and the objective function L is defined as the cross-entropy loss between the prediction P = softmax (Z) = softmax (ffimax(f(((,, θ)) E RNN and the label matrix Y E RNNCC
C
L 0)
1
Σ
Yı log Pik.
N
iEV
k=1
where denotes the representation from the GNN, and represents the total number of classes.
3.2 GRAPH LOTTERY TICKET (GLT)
In recent study (Chen et al., 2021), the conventional lottery ticket hypothesis (LTH, Frankle & Carbin (2019)) was extended to graph representation learning. Analogous to conventional LTH, which asserts that one discover sparse subnetworks with comparable performance dense networks, Chen et al. (2021) claim that both core sub- dataset and sparse sub-networks can simultancously identified, called graph lottery ticket (GLT). Formally, graph lottery ticket can be characterized as follows.
Definition 1 (Graph Lottery Tickets (GLT), Chen et al. (2021)). Given a graph G = (A,X) and GNN f purametrzied by θ E Redd let my E {0, 1) and mg E {0, 1]d be the binary masks for A and θ respectively. Let A' = mmg @ θ be sparse parameter and G' {A', ; X} be sparse subgraph where A' = my O A with ||ool < M and |O'llo- < d. If subnetwork for (-) trained on subgraph A' has comparable superior performance to the original GNN fe(-) trained on the entire graph G, then we call A' and for as graph lottery ticket (GLT).
After the proposal GLT, numerous studies (Chen et al., 2021: You al., 2022; Hui al., 2023; Wang et al., 2023) have been carried out to identify more sparse masks m. and mg with better performance. The most studies identify GLT in an iterative manner, in which the edges/parameters are gradually removed at each round and GLT with desired sparsity levels is realized after multiple rounds. However, a majority of studies falls short in contemplating the graph structure information.
MOTIVATION: LOW-DEGREE EDGES ARE IMPORTANT
Empirical observations. We first highlight a critical graph structural property that profoundly impacts the performance of the graph sparsification. Toward this, we compare the performances of GAT (Veličković al., 2017) with two simple edge pruning strategies: pruning graph edges by (1) the highest edge degree and (2) the lowest edge degree. Throughout our observations, we define the edge degree of e = (i.) j) as (IA(i)) + [W))))/ where (K) denotes the set neighboring nodes connected the node k. As illustrated in Figure/ 1, pruning low-degree edges significantly degrades the performance compared to the pruning of high-degre edges. In particular, the performance gap gradually increases approaching to high sparsity regime, especially in Citeseer and Pubmed datasets. Similar observations can be found for other standard GŇN architectures such as GCN (Kipf & Welling, 2016) and GIN (Xu al., 201 8a), and they are provided in in Appendix A.1.
3

---

Published as a conference paper at ICLR 2024
0.87
0.75
0.75
Accuracy (GAT)
Accuracy (GAT)
Accuracy (GAT)
0.73
0.64
0.34
0.64
0.59
0.92
0.45
0.33
0.47
Graph Sparsity (Cora)
Graph Sparsity (Citeseer)
Graph Sparsity (Pubmed)
Figure Empirical observations for the importance of edge degrees.
Cora
Citeseer
Pubmed
1.00
0.75
E(G
0.50
0.00
0.50
-0.00
-1.00
100
200
300
50
100
150
200
100
200
300
Edge Degree,
Edge Degree, Moll
Edge Degree, [АИНН(М]
Figure 2: The changes of I Laplacian energy for single edge removal on Cora/Citeseer/Pubmee datasets.
Normalized graph Laplacian energy. In addition to empirical observations, we further explore the influence edge degree on the graph stability. Toward this, the context of graph theory, we 1
consider the graph Laplacian energy E(g) mathematically defined as: Σ |An-1 where {An V represents the spectrum of normalized graph Laplacian (Allem al., 2016). Since all eigenvalues of the normalized graph Laplacian are bounded in [0, 2]. E(g) measures how much the spectrum deviates from the median value 1. In our analysis, investigate the quantity Aij = -E(Giig) - E(g) where G-ij (V,& {)), that is, how the energy changes if we remove each edge (i,j) for all (i,5) E &. If Aij 0, it means that the subgraph G-sj has higher energy than that of the original graph, thus it can be understood that removing edge (1,j) makes the graph spectrally unstable. As depicted in Figure for popular graph datasets, is observed that the higher energy predominantly occurs when low-degree edges are eliminated. This observation substantiates the importance of preserving low-degree edges terms of spectral stability.
Theoretical evidence. The very recent study (Tang & Liu, 2023) provides the theoretical under- standing of model generalization for popular GNN families. More precisely, the upper bound for generalization етror of each GNN family FF relies on its Lipschitz constant, denoted by LF. In the same study, case GCN (the following argument is similar for other GNN families), LOCN is known to be dominantly governed by the norm | rather than the node feature X or model parameter where Asym symmetrically normalized adjacency matrix. Further, the norm
/derant1 +I where degmux and degmin represent the maximum A loc can be bounded by V degmat1
and minimum node degree respectively. From this bound, removing low-degree edges would result in a larger generalization gap, which corroborates the importance of low-degree edges in theory.
5 TEDDY: TRIMMING EDGES WITH DEGREE-BASED DISCRIMINATION STRATEGY
Given the empirical and theoretical evidence on the importance of graph structures in Section 4, we introduce TEDDY, a novel framework for one-shot edge sparsification. Our method selectively prunes edges leveraging scores assigned to individual edges derived from degree information (Section 5. 1), followed by parameter sparsification (Section 5.3) based on lu projection. The whole process is accomplished within a single training phase, eliminating the need for conventional iterative training to attain GLT.
4

---

Published as a conference paper at ICLR 2024
(a) Edge-ccnttric MP
(c) & Projection
(bj Distill KL Loss Cau
g
Zeruoi1
Z,
Figure 3: Overall framework for our graph sparsification TEDDY and parameter sparsification with projected gradient descent on to ball.
5.1 GRAPH SPARSIFICATION
To integrate the significance of degree information discussed in Section we design an edge-wise score in proportional to the inverse degree. The primary observation here is that relying solely on the degree of the corresponding node pair to prune high-degree edges does not sufficiently uncover the structural in- formation pathways across multi-hop neighbors.
deg dtg -4 dagg/nal 233
Ut
Aesu/ 2.26
To see this more clearly, we consider a toy exam- ple in Figure In this example, the edge degree of directly attributed nodes i and j is defined as hop (ety) (IMG + [W51),, and the respective 2-hop edge degree is represented as deg2-to((es) (EneN, [aal + EAEN, [2)))/2. The most natural con- sideration of degrees is deg1-bop to average the degrees of the node pairs, but fails to distinguish the relative importance of e12, 613, and e23 in this example since they are all identical, i.e., degi hop (e12) deg based score overlooks diverse message pathways through the common neighbor v2 (colored green) and h-hop adjacent nodes (colored in gray) of U1 and 133 In contrast, the 2-hop edge degree allows for giving the priorities to edges C and 623 over 613, Lee. deg (e12) < deg (C2a) < deg (C13). facilitating more refined edge score. This emphasizes the necessity recognize degree information from a hierarchical perspective, culminating in a more nuanced score.
12
Figure 4:
toy example highlighting the im- portance of multi-level degree incorporation.
deg hopg:tup((23) (E23). As result, deg, hop"
Inspired by this insight, facilitate multi-level consideration of degree information within the message-passing (MP) algorithm, the core nature of contemporary GNNs. Our TEDDY adapts the original MP by injecting an edge-wise score within the MP. Toward this edge-wise score construction, we first define several quantities related to node-wise score connected to individual edges. As an initial step, we adopt monotonically decreasing function with respect to the node degree dog(v), defined by g - RR that can be regarded monotonically decreasing characteristic of the function g would reflect the importance of low-degree edges to some extent. As design choice of g, there can be several candidates and we simply adopt g(v) 1/ 1/ deg((e) in this paper. Equipped with this function g. TEDDY computes the importance of each node considering the average degree information of neighbors as below:
type of score function for each node E V. The
g(v)
Σ g(u)
W
DEN,
5

---

Published as a conference paper at ICLR 2024
Following this, TEDDY divides ((V) by the degree of the node itself, represented ğ(v), reflecting the significance of preserving edges with lower degrees:
(vv)
(4)
(v)
Let E RN denote the aggregated values of the function computed at all nodes v E V. Finally, our method attains edge-wise scores Tedge through the outer-produce of g:
Tedge gg
(5)
In practice, Eq. (3) is computed as Ag E RN, where D with D being utilized to average the degree information of neighbors. Hence, Eq. (4) can be equivalently written as Agg R In this perspective. the computation of exhibits form of edge-centrie MP, which is depicted as well in Figure 5(b). As illustrated, the degree information neighboring edges, Cik, of the given edge Cıj is propagated via proposed edge-wit wise score matrix Tedge- At the same time, the self-information 1/deg(i) is integrated during our edge-centric MP, analogous to standard MP across all nodes illustrated (a).
Propagating the degree information, TEDDY effec- tively assigns lower scores non-critical edges those with high priority for removal. These edges either possess high degree or are part of alternative multi-hop pathways for message propagation. Our method also demonstrates linear complexity in the number of nodes and edges, which will be detailed Appendix A. Concurrently, our TEDDY aims to selectively preserve pivotal edges by considering low- degrees in a broader view, thereby maintaining essen- tial information flow across the influential reception regions of individual nodes.
(8) Node-centric MP
(b) Edge-centric MP
Figure 5: Illustration of Edge-centric MP.
5.2 DISTILLATION FROM DENSE GNNS
To effectively maintain information in the original graph, we employ the distillation phase by matching the logits of the representation learned on the entire graph (Hinton et al., 2015). our experience, we observe that the representation obtained from the entire graph plays an important role in model
generalization. Let Zdense and Z be the representation trained on the whole graph and the sparse subgraphs, respectively. Then, our final objective function would be mathematically
Lu = L(g, 0) + KLL Z Z/T). softmax Zoonse/T])
(6)
where KLLp, q) represents the KL-divergence between two (possibly empirical) distributions p(-) and (.). Further, Aue controls the strength of the distillation and t is a temperature parameter. For marginal hyperparameter tuning, use unit temperature 1 in practice.
5.3 PARAMETER SPARSIFICATION
The iterative nature of previous studies (Chen et al., 2021; You et al., 2022; Hui et al., 2023) on identifying sparse subnetworks necessitates an infeasible search space. The aforementioned studies require determining the number of pruning rounds and the per-round pruning ratio in advance to achieve target sparsity level. To alleviate such computational inefficiency, we prune the parameter connection within just single training with sparsity- -nduuity optimization algorithm; projected gradient descent (PGD) on lo ball. In optimization literature, the projected gradient descent can be regarded as special case of the proximal-type algorithm, which is known enjoy rich properties both theory and practice in the perspective of deep learning (Oymak, 2018; Yun et al., 2021a). Given target sparsity ratio po [0. 1] for the model parameter, the expected number of non-zero entries would be h == [(1 po pd]. Let C₁ == (O E Rdd OOllo h} be the to ball for h--parse parameter, then our parameter sparsification can be described only in single line
O proje, (o, Vo 0.)

---

Published as a conference paper at ICLR 2024
Algorithm 1 TEDDY: Trimming Edges with Degree-based Discrimination strateg
1: Input: Graph G = (A, ). GNN J(G θ), target sparsity ratio Pa- Pe E [0. 1]
2: Initialize: Initial model parameter Po, Oo E IR" for pretraining and sparse training respectively
3: procedure PRETRAINING ON ENTIRE GRAPH
4: for L 0,
T do
5: 4141 4 v C(g, +:) end for
7: Choose 2. E ( ) for best validation and get representation dause + f(g,
8: end procedure
9: procedure SEARCHING SUBGRAPH
10: A' < A and I <- Smallest [E] entries among edge index in Totge
Dr Eq. (5)
A'I 5- and obtain sparse subgraph g' +- [A'
12: end procedure
13: procedure SEARCHING SUBNETWORK
14:
C 10 ERR 1 = [(1 -podd]
b Eo ball for [(1 -sparre parameter
15:
fort=0,,,,.... 1
16:
Z. 1
(9' 0.) +- ((''' da Xx.KL Z.), soltmaxx Zoen))
D Eq. (6)
18:
e.+1 proje ( V/ Ld" (.)) end for
Eq. (7)
20:
Choose @' E (O), ... rr) for best validation and obtain sparse subnetwork fe
21:
end procedure
22:
Output: Graph lottery tickets Je
b Definition
where La is defined in Eq. (6). The main advantage of PGD-based sparsification lies in its ability to encourage the desired level of sparsity without iterative processes, which enables to rapidly identify graph lottery tickets. We summarize the detailed overall procedures in Algorithm and Figure illustrates framework.
EXPERIMENTS
In our empirical studies, we primarily focus on semi-supervised node classification tasks, most regularly considered in graph representation learning. We consider two sets of experiments: (i) small- and medium-sizz problems (Section 6.1) and (ii) large-scale experiments (Section 6.2). We compare TEDDY with original GNN performance (Vanilla), UGS (Chen et al., 2021) and WD-GLT (Hui et al., 2023) on regular-scale experiments (Section 6. Due to the computational time required for the Sinkhorn iterations in WD-GLT, the baseline WD-GGLT is inevitably excluded for large- scale experiments (Section 6.2). The GNN models, our proposed method, and the baselines are implemented upon PyTorch (Paszke al., 2019), PyTorch Geometric (Fey & Lenssen, 2019), and OGB (Hu et al., 2020). The detailed experimental configurations are provided in Appendix B.
6.1 SMALL- AND MEDIUM-SCALE TASKS
In alignment with experiments in UGS, we evaluate the performance of our TEDDY on three bench- mark datasets: Cora, Citeseer, and Pubmed (Sen al., 2008) on three representative GNN archi- tectures: GCN (Kipf & Welling, 2016), GIN (Xu et al., 2018a), and GAT (Veličković et al., 2017). Figure illustrates the performance comparison with varying level of graph sparsity.
Although the main goal is to preserve the performance of vanilla dense GNN, our method improves the original accuracy in more than half of the considered settings across all sparsity levels. In particular, GIN on the Citeseer dataset shows the outstanding result (refer to the second row and third column in Figure 6). In this setting, the best accuracy is observed as 73.20%, at the graph sparsity Pg = 43.12% achieving 5.4% improvement upon the vanilla performance. Moreover, our TEDDY consistently outperforms the baselines across all experimental settings with remarkable improvements in GAT. Note that. at the maximum graph sparsity, TEDDY enhances the performance in a range of 12.8% 20.4% compared to the optimal performances of the baselines. In addition, we highlight MACs MulttpplyAAccmullae operations) inference for GIN as showcase examples. In Figure
7

---

Published as a conference paper at ICLR 2024
0.81
0.31
0.01
0.81
Accuracy (GCN)
Accuracy (GAT)
Accuracy (GIN)
0.29
0.72
70.77
0.74
0:79
0:31
0.24
0.72
0.50
047
Graph Sparsity (Cora)
Graph Sparsity (Cora)
Graph Sparsity (Cora)
0.24
0.73
0.74
Accuracy (GCN)
PncuracyyGiin (GAT)
Accuracy (GiN)
0.20
0.54
0.70
0.99
Accuracy
0.00
0.63
0.65
LGS
0.51
LISS
Vinlls
064
J55
0.31
WE-G.T
HD
0.20
0.00 Graph Sparsity (Citeseer)
8.0
Graph Sparsity (Citeseer)
Graph Sparsity (Citeseer)
0187
0.87
0.80
Accuracy (GCN)
Accuracy (GAT)
Accuracy (GIN)
0.79
0.75
0.79
0.77
0.77
0:75
0.23
UES
Vanda
0.33
VanBaa LGS
0.74
JCS
Vanda
MD-.TT
WDD-LLT
WD.0LT
Dum
0.0
0.20
030
3400
2.00
0.90
6600
0.10
0.22
0.30
0.43
Graph Sparsity (Pubmed)
Graph Sparsity (Pubmed)
Graph Sparsity (Pubmed)
Figure 6: Experimental results training GCN/GAT/GIN Cora/Citeseer/ubmmed datasets.
0.75
0.81
0.62
2034
Arcuracy (GIN)
0.73
8.13M
(GIN)
-7.95M
3.1M
0.60
5. 1.M
3.88
0.77
0.7
2.67
0.76
0071
2.65
Vae
Sonal UCS Oun
wo GLT
GLT
0.63
Oue
0.75
Oum
0.64
6.60
06+000
2++00
Se-09
0.72 7e-00
2e-26
Se-00
0.62
2e+10
4e-11
I++11
MACs (Citeseer)
MACs (Pubmed)
MACs (Reddit)
Figure 7: MAC comparisons for (Left) GIN on Citeseer (Middle) GIN on Pubmed (Right) SAGE on Reddit (large-scale experiment) as showcase examples.
GLTs found by TEDDY achieve dramatic savings of MACs (about times smaller) on Citeseer and Pubmed, even with superior performance to the vanilla networks. Due the space constraints, our state-of-the-art performance concerning the weight sparsity is deferred to Appendix A.
Qualitative Analysis. To demonstrate that our method proficiently incorporates the degree in- formation inherent in the graph structure, we provide qualitative analysis concerning the av- erage degrees of pruned edges for our TEDDY and baselines. As illustrated in Figure 8, our method effectively targets edges with high de- grees across various graph sparsity levels. More- over, the average degree of TEDDY continues to decrease as the sparsity ratio increases, which underscores that TEDDY prioritizes edges display- ing low-degree information over multi-level adjacency considerations. On the contrary, the same phenomenon is not observed in UGS and WD-GLT, implying a lack of awareness of edge degrees.
21.
Dagar
Wc
en
Ang.
Graph Sporsity (Com. GCN)
Graph Sporsity (Citmeerr GCN)
Figure 8: Qualitative analysis.
8

---

Published as a conference paper at ICLR 2024
Armuney
110 138
Geaph Spinity (Arcir)
E-1
Graph Spuesity [Anis]
14 23n E30 14 EX3 3m0
Graph Spansty (Reddin)
Graph Sponsiy (Reddi)
o13 Ei0 Em
Figure 9: Experimental results on large-scale datasets, training GCN/SAGE Arxiv/Reddit.
Table I: Performance of proposed TEDDY (in percentage) on extremely sparse regimes, averaged over runs.
Simulations
Vanilla
20-th
25-th
30-th
35-th
40-th
GS(%)
0
64.14
72.25
78.53
83,38
87,14
WS(%)
64.15
72.26
78.54
83.39
87.15
Cora
76.34 +: 0.79
76.20 +: 0.69
76.64
0.76
77.38 1: 0.97
77.20
1.12
76.82 1: 1.00
Citeseer
68.10
71.16 0.66
70.58
1.43
71.54
0.52
71.42
0.56
71.12 +: 0.51
Pubmed
77.90 +: 0.14
79.70 +: 0.26
79.36 0.71
79.68 d: 0.37
80.48
0.50
80.98 +: 0.42
Quantitative Analysis. We expand our investigation to assess the efficacy of our proposed method under extreme sparsity conditions. Employing GIN base architecture, increase both the graph sparsity and the weight sparsity to a maximum of 87% and conduct the same pruning procedure across 5 runs. According to Table under harsh scenarios. Our method surpasses the original performance in all settings across all datasets except at graph sparsity and weight sparsity Py = pe 64% (refer to 20-th simulations in Table 1). Notably, the performance of TEDDY exhibits progressive improvement with the increment sparsity ratio, marking 3.08% advancement in comparison to the vanilla GIN on Pubmed.
TEDDY persists in enhancing classification accuracy even
6.2 LARGE- SCALE PROBLEMS
To further substantiate our analysis, extend our experiments for two large-scale datasets: ArXiv (Hu et al., 2020) and Reddit (Zeng et al., 2019). Unlike in Section 6.1, we choose GCN and GraphSAGE (SAGE, Hamilton al. (2017)) as backbone architectures since they are representative GNNs for these datasets. Displayed in Figure 9, TEDDY can relatively preserve the test accuracy compared to UGS. Specifically, in training SAGE on the Reddit, it apparent that our TEDDY even surpasses the original performance of vanilla SAGE up to graph sparsity P3 62.26% which indi- cates the significant elevation (refer to the second last sparsity). The best performance this setting is observed as 82. 72% at the graph sparsity Pg 40%. which shows 7.4% and 12.4% improvements upon vanilla SAGE and UGS respectively. Concurrently, TEDDY exhibits more advanced pruning performance upon UGS when it comes the Arxiv dataset as well. Our method succeeds in attaining the GLT up to the graph sparsity Py 33. 23.66% and P, = 45.96% 45.96% for GCN and SAGE, whereas UGS fails to discover GLT at this regime. Hence, these results imply that TEDDY advanced performance regardless of graph size, which underscores its high versatility. Moreover, we accentuate MACs savings in large-scale experiments with SAGE Reddit our spotlight example. As can be seen in Figure 7, our TEDDY achieves 5.5 times smaller models maintaining the original performance while UGS shows significant degradation in this regime.
identify GLT with
CONCLUSION
In this paper, we introduced TEDDY, the novel edge sparsification method that leverages structural information to preserve the integrity of principal information flow. Based on our observations on low-degree edges, we carefully designed an edge sparsification that effectively incorporates the graph structural information. After sparse subgraphs in hand, we efficiently induced the parameter sparsity via projected gradient descent on the ty ball with distillation. We also validated the superiority of TEDDY via extensive empirical studies and successfully identified sparser graph lottery tickets with significantly better generalization. As future work, we plan to investigate how to incorporate the node feature information into our TEDDY framework and explore the theoretical properties of TEDDY.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work was supported by Institute of Information & Communications Technology Planning & Evaluation (ITP)) grant NNo.2019-0-00077 Artificial Intelligence Graduate School Program (KAIST), No.2019-0-01371, Development of prain-inspired Al with human- -ilean-likeeaa intelligence. No. Artificial Intelligence Innovation Hub) and the National Research Foundation of Korea (NRF) grants (No.201 8R A5A 1059921) funded by the Korea government (MSIT). This work was also supported by Samsung Electronics Co., Ltd (N0.10201224408133-00))
REFERENCES
Scong Jin Ahn and MyoungHo Kim. Variational graph normalized autoencoders. In Proceedings of the 30th ACM international conference on information & knowledge management, pp. 2827-2831, 2021.
Luiz Emilio Allem, David Jacobs, and Vilmar Trevisan. Normalized laplacian energy change and edge deletion. MATCH Communications Mathematical and in Computer Chemistry, 75(2): 343-353, 2016.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023. URL
ew net/ forum? doy
Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In International Conference on Learning Representations, 2021. URL https: https: /ttp:::://ppeeeeeeee net/ forum?
Ad=uxpzitPEoou.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2022.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International conference on machine learning, pp. 1695-1706. PMLR, 2021.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gon An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 257-266, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL https:
// /pppereveeew.. net forum? iid:idd-rrdeee..
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. In NIPS Deep Learning and Representation Learning Workshop. 2015. URL http://axxiv org/ abs//////// / 5503... 02531
Zhenyu Hou, Xiao Liu, Yuxiao Dong, Chunjie Wang, Jie Tang, et al. Graphmae: Self-supervised masked graph autoencoders. arXiv preprint arXiv:2205.108% 2022.
Weihua Hu, Matthias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 11.2211--2133. 2020.
Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. In The Eleventh International Conference on Learning Representations, 2023. URL https: http:://ppeeeeeeeeee net forum? d= fi
10

---

Published as a conference paper at ICLR 2024
Wei Jin, Lingxiao Zhao, Shichang Zhang. Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2022. URL
https: http//pppneeeeeeeeeeeeeeeeeeeeee
forum -orummiid--NLLL333Jo.00...
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.
arXiv preprini 16Xiv:609..0 (.9900 2016.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1666-1674, 2018.
Jundong Li, Kewei Cheng, Liang Wu, and Huan Liu. Streaming link prediction on dynamic attributed networks. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 369-377, 2018.
Andreas Loukas. Graph reduction with spectral and cut guarantees. J. Mach. Learn, Res., 20(16)) 1-42, 2019.
Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International Conference Machine Learning, pp. 3237-3246. PMLR, 2018.
Samet Oymak. Learning compact neural networks with regularization. In International Conference on Machine Learning, pp. 3966-3973 3975. PMLR, 2018.
Joonhyung Park, Jaeyun Song, and Eunho Yang. Graphens: Neighbor- ego network synthesis for llaalaibalanceed node classification. In International Conference Learning Representations, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Veto,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- gigh--erfrrancce deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv: 10903, 2019.
Ryoma Sato. Graph neural networks can recover the hidden features solely from the graph structure. In International Conference on Machine Learning, ICML,, 2023.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Cliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-99) 93, 2008
Yunsheng Shi, Zhengjie Huang, Wenjin Wang. Hui Zhong. Shikun Feng, and Yu Sun. Masked label prediction: Unified massage passing model for supervipe classification. ArXiv, abs/2009.03510 003509 2020. URL https: / /app.. remanticschhen org/ Co rpruID: 221534325.
Si Si, Felix Yu, Ankit Singh Rawat, Cho-Jui Hsich, and Sanjiv Kumar. Serving graph compression for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. URL https: opw.revieneeeeeepeeeeeeeeee.eeee net forum? id--------- qVtA3pAxG.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1696-1705, 2022.
Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 33674-33719. PMLR, 23-29 Jul 2023. URL https: http::///o.oeeeeeeeeoeo iggs..gg..... mlr. www.smeess......emommmmmmmmmme.e / v222/222222//22222222 / tttg/anng2232 httmm.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1710. 10903, 2017.
11

---

Published as a conference paper at ICLR 2024
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 Interna- tional Conference Learning Representations, 2023. URL https:/ httts:://penneeiee..ees forum? i d=Dvs---------- a3ammPe.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 207-217, 2020. 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? arXiv preprint arXiv:1810.000 0082,, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks, In International conference on machine learning, pp. 5453-5462. PMLR, 2018b.
Haoran You, Zhihan Lu, Zijian Zhou, Yonggan Fu, and Yingyan Lin. Early-bird gens: Graph- network co-optimization towards more efficient gen training and inference via drawing early-bird lottery tickets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.
8910-8918, 2022.
Jihun Yun, Aurélie Lozano, and Eunho Yang. Adaptive proximal gradient methods for structured neural networks. Advances in Neural Information Processing Systems, 34:24365-244 -44478,, 2021a.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34:13683-13694 2021b.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv: (00,:0999700931/ 2019.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in neural information processing systems, 31, 2018.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 2222476-29490 2021.
12

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIALS
A FURTHER ANALYSES AND EXPERIMENTS
This section provides supplemental analyses and experiments to further validate the efficacy of TEDDY. We begin by examining the complexity of TEDDY in Section A.I, followed by an investigation of low-degree edges other GNN architectures in Section A.2. Subsequently, we discuss the pruning performance relative to weight sparsity Section A.3. Sections A.4 and A.5 extend our ovaluation TEDDY to include pruning on graph transformers and inductive node classification scenarios. A step-wise evaluation of our approach is detailed in Section A.6. Section A.7 focuses experiments investigating sole graph sparsification under dense weight conditions, specifically assessing TEDDY's 's edge pruning capabilities against baselines, including the random pruning method DropEdge (Rong et al., 2019). Finally, Sections A.8 and A.9 present a pairwise sparsity analysis and pruning time consumption metrics, respectively, to demonstrate the efficiency and effectiveness of TEDDY against comparative baselines.
A.I COMPLEXITY ANALYSIS
practice, the computation of edge-wise scores TEDDY requires O(N M) space complexity, since Tedge IR only computed for the existing edges. More preciscly, g(v) is first computed by the row- wise summation of the sparse adjacency matrix. Then we compute ②()) via sparse matrix multiplication between degree vector and the adjacency matrix. Following this, T is efficiently obtained by element-wiss multiplication between Ø(v) of nodes in and ğ(u) of nodes u in columns of the edge index. Hence, Tedge can efficiently obtained with a complexity linear in the number of nodes and edges.
A.2 LOW-DEGREE OBSERVATION ON OTHER GNN ARCHITECTURES
0.81
0.24
Accuracy (GCN)
Accuracy (GCN)
Accuragy (GCN)
0.79
0.70
0.79
0.27
8.77
0.74
0.56
0.72
0.34
Vanila
0.73
Vanda
0.69
High-dagaa Praning
High-dugea Prining
-ic-dague Pruning
0.67
0.2
D47
0.70
000
020
0.35
050
0.00
0.2
033
058
0.7
Graph Sparsity (Cora)
Graph Sparsity (Citescer)
Graph Sparsity (Pubmed)
0.80
0.25
0.77
Accuracy (GIN)
Accuracy (GIN)
Accuracy (GIN)
0.23
0.77
0.70
0.55
6.75
0.54
0.59
8.70
0.90
0.57
High
Pruning
0/2
0.3
aie
Graph Sparsity (Cora)
Graph Sparsity (Citeseer)
Graph Sparsity (Pubmed)
Figure 10: Low degree observations for GCN/GIN architectures on Cond/Cteseer/Pubmee datasets.
As an extension to Section 4, we compare the performance between the highest and the lowest degree edge elimination, leveraging GCN (Kipf & Welling, 2016) and GIN (Xu et al., 2018a). As depicted in Figure 10, removing low-degree edges consistently deteriorates the performance across all scenarios, especially for GIN trained on Cora dataset. The same trend is observed in the average performance of all configurations across multiple runs, shown in Table 2.
A.3 SPARSIFICATION PERFORMANCE RELATIVE TO WEIGHT SPARSITY
Here, we present the pruning performance of our TEDDY and baselines according the weight sparsity, displayed in Figure 11 and 12. Consistent with the results related to graph sparsity, our method shows predominant performance compared to baselines across all evaluated settings, independent of the graph sizes.
13

---

Published as a conference paper at ICLR 2024
Table 2: Performance on different edge degree pruning criteria (in percentage), averaged over 5 runs. deglow denotes low edge degree-baser based pruning, whereas degnigh refers to high edge begrre-basel pruning.
Simulations
5-th
10-th
15-th
GNNs
Dataset
deBue
deg
deBuo
deRaigh
deRue
destigh
deguve
deguigh
deguo
degagg
Cora
80.38 0.15
81.28 0.64
77.66 0.4.1
77.92 6.34
75.36 0:43
77.68 9.32
74.24 0.16
76.02
0.43
69,54 0.33
72.62 0.33
GCN
70.44 1:0
0.22
70.60
0.19
64.78 0.31
67.58
972
63.46
67.72
0.37
1:0.1
65.70 1.36
Pubmed
78.32 c.v
79.18 0.2
76.66 1.7M
77.66 8.27
77.52
0.26
77.32
0:1
77.72 1437
76.74 4.10
75,20 0.30
76.54 1.8
Cora
77.64 1.33
79.72 1.66
68.34 +
78.50 1.16
56.72
0.46
72.44
1.00
50.12
67.74 0.99
44,78 0:000
51.64 1.67
GAT
Ckeseer
69.48
66.86
RA3
42.68
2:1.4
59.74
1M
35.40
1.00
2:000
1.43
Pubmed
78.40
78.14
1:00
71.66 0.3M
76.32 9.55
58.48
u.30
74.52
0.56
49.52
1004
72.12
4.64
44.10
0.077
68.20 :: RA1
Cora
74,86
76,48
70,70 + 1.15
76.84 1.11
66:70
0:35
74.70
1:30
62.72
72.96
0.55
58.82
70.28 0.99
GIN
67.52 cow
a:
0:9
62.32
68.46
0.4x
60.60
65.64 1.89
Pubmed
75.64 2:072
77.96
0.16
75.12 1:0.0
77.38
9:27
73.68
1:20
77.44
8.3
70.74
1.39
74.88
4.62
70.88 2:72
73.30 0.31
A.4 TEDDY WITH GRAPH TRANSFORMERS
To demonstrate the versatility of method, we expand our experiments encompass recent Transformer-basee GNN architectures, UniMP (Shi et al., 2020), NAGphormer (Chen et al., 2022), and Specformer (Bo et al., 2023). Note that differentiable mask approach from baselines may prune edges more than pre-defined ratio, due to the possibility of multiple mask elements having the same value. Moreover, UGS (Chen et al., 2021) and WD-GLT (Hui et al., 2023) are infeasible to implement on Specformer and NAGphormer, since the differentiable mask for the adjacency matrix requires backpropagation through eigenvectors and eigenvalues utilized in these architectures, introducing practical challenge with high complexity of O(N*) per iteration.
As depicted in Figure 13 and 14, TEDDY accomplishes stable pruning performance, surpassing all baselines when equipped with UniMP as backbone. In particular, UGS and WD-GLT show significant degradation with severe unstability as the sparsity increases, whereas the performance of TEDDY is stable across all benchmark datasets. Our method also yields decent performance in NAGphormer and Specformer, notably in NAGphormer on the Cora dataset, with considerable performance enhancement over the original result. Overall, these results demonstrate TEDDY's versatility across diverse foundational architectures.
A.5 TEDDY ON INDUCTIVE SEMI-SUPERVISED SETTINGS
We present additional experiments to further evaluate TEDDY's 's adaptability on inductive semi-supervised node classification task, where the fraction of the validation and test set is unobserved and larger than that of the training set. We modificd the Cora, Citeseor, and Pubmed datasets (Sen et al., 2008) to a 20/40/40% split for training, validation, and testing phases, ensuring that the model had no prior exposure to the validation and test nodes during training.
The results, illustrated in Figure 15 and 16, demonstrate that TEDDY achieves prominent pruning performance on inductive setting as well. This is especially pronounced on the Cora and Pumbed datascts with GIN and, surpassing the accuracy of the vanilla GIN. Morcover, our method consistently achieves stable performance throughout all simulations on the Pubmed dataset, regardless of the base architectures. These findings strongly affirm TEdDY'S 's ability to effectively generalize from smaller to larger graphs.
A.6 ABLATION STUDY
To confirm that each component in our framework contributes individually to the cdge/parameter sparsification, we conduct comprehensive ablation studies. Towards this, we provide step-wise assessment result on Cora dataset, equipped with GAT (Veličković et al., 2017) as a base architecture. As illustrated in Figure 17, while integrating the distillation loss Las does improve the performance of the baselines, they still fail to match the performance of method, even ours without La. This highlights a significant impact of proposed edge-centric message passing with degree statisties. Furthermore, our approach, which considers multiple levels of degree information (specified as Ours), consistently outperforms methods that rely solely on degree information from direct node pairs (specified as l-hop Degree).
Further ablation studies were conducted to examine the impact of different components, as shown in Figure 18. These studies included: (1) TEDDY with all components, (2) TEDDY without distillation loss, (3) TEDDY with seanitude-based weight mask pruning, (4) UGS with all components, (5) UGS with distillation loss, (6) UGS with based projected gradient descent (PGD). Analogous to the previous findings, UGS enhanced with La. remains to be suboptimal compared to TEDDY without Lat across all benchmark datasets. Meanwhile, the performance of UGS degrades dramatically when incorporating &o PGD. Intriguingly, TEDDY maintains robust performance with magnitude- based weight pruning, highlighting its flexibility across varying weight
14

---

Published as a conference paper at ICLR 2024
0.80
0.00
Accuracy (GCN)
Accuracy (GAT)
2.77
Accuracy (GIN)
0.70
2.72
0.70
00.77
1.00
0,20
2.01
0.70
Veeis
065
2.00
UGS
Van
0.09
UGS
Van
0.72
VD-GLT
1.00
WD-GLT
WD-6LT
Our
00
0.3
0.50
G0T
0:33
1.00
1.0
80000
0.37
0.33
010
Weight Sparsity (Cora)
Weight Sparsity (Cora)
Weight Sparsity (Cora)
0.71
0.73
0.74
0.72
Accuracy (GCN)
Aecuracy [GAT)
Ascuracy (GIN)
0.70
0.04
0.70
0.59
0.60
0.87
0.5
0.00
0.65
Vards
0.5
UGS
0.64
USS
Vanil
AD-GIT
HENGLT
WV--LL
Oas
Dan
09633
3.17
0:33
350
0.57
0.5
100
0
0.3
0.00
06
68
130
00
0.7
1.35
0.50
1,67
033
1.00
Weight Sparsity (Citeseer)
Weight Sparsity (Citeseer)
Weight Sparsity (Citeseer)
0.00
2.70
Accuracy (GCN)
Accuracy (GAT)
Accuracy (GIN)
0.70
8:75
0.79
0.70
2.07
0.75
0.75
2.6
0.28
USD
0.72
WD-GLT
WD-GLT
IWD-GTT
0 80000
0.27
0.35
0.50
G5T
0.33
1.00
100
0.27
5.35
0.53
0.23
L10
1200
0.37
0.33
030
657
0.5
100
Weight Sparsity (Pubmed)
Weight Sparsity (Pubmed)
Weight Sparsity (Pubmed)
Figure 11: Additional experimental results in Section 6.1 with respect to the weight sparsity.
SAGE
(GCN)
Roursay (SACE)
Acurecy
Weight Sparity (Anci))
Waiht Sponityy (Amin)
Wright Sparsty (Reddit)
Waihtt Sparitty (Reddia)
Figure 12: Additional experimental results in Section 6.2 with respect to the weight sparsity.
sparsification strategies. Nevertheless, leveraging PGD offers optimal balance of efficiency and effectiveness. obviating the need for additional iterative training to obtain lottery tickets.
A.7 EXCLUSIVE EDGE SPARSIFICATION PERFORMANCE
this experiment, we focused exclusively on graph sparsification to directly compare the effects of various edge pruning techniques, including the random dropping strategy employed in DropEdge (Rong et al., 2019), with our TEDDY. The results, shown in Figure 19, indicate that TEDDY consistently outperforms existing baseline methods, including DropEdge. Notably, our approach not only maintains but also enhances the accuracy of vanilla GNNs on the Citeseer and Pubmed datasets across benchmarked GNNs. Furthermore, the figure highlights that the use of the DropEdge technique leads to suboptimal performance, emphasizing the importance of a more sophisticated pruning methodology.
A.8 PAIRWISE SPARSITY ANALYSIS
To demonstrate the stability of TEDDY, we present the results in Table I as heatmap in Figure 20. The performance in each heatmap element average performance of TEDDY not uniformly affected by increased sparsity. In the Cora dataset, our method demonstrates resilience to higher graph sparsity levels, surpassing the vanilla GIN's accuracy 76.34%. This suggests that a sparser graph generated from our method has a potential to mitigate overfitting achieve generalization. For the Citeseer dataset, the performance remains relatively stable across a range of weight sparsity levels, indicating degree of robustness parameter reduction. Furthermore, all configurations exceed the vanilla GIN's accuracy of 68.1 %
random seeds. Overall, the performance
15

---

Published as a conference paper at ICLR 2024
Accuracy (UniMP)
0.04
0.77
Accuracy UnnMPP)
0.74
0.60
Accuracy (UNIMP)
0.79
0.74
0.64
0.62
0.69
0.56
0.64
0.50
0.51
0.58
Wrill
0.45
Varilla
0.53
Vanila
0.43
0.00
0.10
0.30
0.50 0.60
0.70
0.00
0.10
6.30
0.50 0.60
0.70
0.00
0.10
0.20
0.30 0.40 0.50 0.70
Graph Sparsity (Cora)
Graph Sparsity (Citeseer)
Graph Sparsity (Pubmed)
0.84
Accuracy (UniMP)
Accuracy (UniMP)
Accuracy (UniMP)
0.71
0.57
00.50
0.51
0.44
0.45
Varilla
0.53
0.37
UGS
0:39
UGS
0.48
UGS
WI--LL
WO-GLT
WC-GIT
Ours
0.33
0.43
Ours
0.00
0.10
020
0.30
0
0.50
0.60
0.70
0.00
0.10
0.20 6.30 0.40 0.50 0.50 6.70
0.00
0.10
0.20
0.30
0.40 050 0.60 6.70
Weight Sparsity (Cora)
Weight Sparsity (Citeseer)
Weight Sparsity (Pubmed)
Figure 13: Average classification performance of training UniMP Cora/Citeseer/ubmmed datasets.
Accuracy (NGGshommn
[MCChhumee
Accursay Specfement
aayy Sspec (ormert
ACCUR may
Ouz
Gragh Sparsty (Coral
Grapth Sparsily (C (Cilesmer]
Graph Sparsty (Cora)
Graph Sparsity (Citesee))
(NAcphomee
Accurnry (MMcptoorme
Accuracy (Seedlrmm mem)
Ar Sucuuryy Uigae comme))
Dka
0.0
6.00
5.0
6.30
082
312
616
6.30
Sparsity
030
ase
6.00
222 332
303
511
[Cheseert
Figure 14: Average classification performance of training NAGphormer (left) /Specformer (right) on
Cora/Citeseer datasets.
strongly indicating the effectiveness of TEDDY across diverse sparsities. The similar efficacy is observed in the Pubmed dataset, where all elements surpasses the vanilla GIN's performance of 77.9%. Interestingly, observe trend in the Pubmed where the performance generally improves with increased sparsity, with the highest accuracy achieved under most extreme sparsity (Py = pe 85%).
A.9 COMPARISON OF PRUNING PROCESS DURATION
This subscction details wall-clock time analysis of (1) TEDDY with all components and (2) Projected Gradient Descent (PGD), the weight sparsification method TEDDY, to verify efficiency comparison to baselines. We reported the time consumption of our method and baselines for each distinct simulation. average over five runs. As demonstrated in Table 3, the results clearly substantiates that TEDDY consistently achieves significant reduction in pruning time relative the baselines. This especially pronounced in GIN the Pubmed dataset, where TEDDY outperforms WD-GLT by remarkable margin, displaying maximum time saving 220.72 seconds during the 15-th simulation. Similar trend is observed in the results in large-scale datasets, depicted in Table 4 and 5, where TEDDY's time consumption is nearly half that of UGS. The maximum duration gap is revealed in the Reddit dataset, with TEDDY concluding the last simulation 131.84 seconds quicker than UGS GCN. Note that the duration of WD-GLT reported N/A due prohibitable computational time for the Sinkhorn iteration.
Following the comparison of wall-clock times for the overall process, we further investigate how efficient our projected gradient descent on the ball is in terms of actual runtime compared to iterative approaches. For fair comparison, we the original dense adjacency matrix without graph sparsification while pruning only model parameters. Table 8 illustrate wall-clock time comparison for citation networks, Arxiv, and Reddit
16

---

Published as a conference paper at ICLR 2024
0.00
0..00
0/88
0.71
Accurayy (GCN)
(GIN)
Accuracy
0.74
0.25
0.50
0.20
0.54
Vania
0.78
0.6
079
Graph Sparsity (Cora)
Graph Spansity (Cora)
Graph Sparsity (Cora)
0.714
0.795
9710
0.704
0.700
Accurcyy (GCN)
Accuracy (GArT (GAT)
Accuracy (GIN)
0.90
0.90
0:67
0.98
0.001
0.5%8.0
130
0:40
3.0
0.5%
2.30
022
850
0.943
020
0.30
230
0.0
Graph Sporsity (Citesetr)
Graph Sparsity (Citeseer)
Graph Sparsity (Citeseer)
0.512
0.86
Accuracy (GCN)
Accuracy (GAT)
Accuracy (GIN)
0.854
0,203
0.842
2.34
0.34
0.33
0.343
Vania
Ouu
Dur
Ours
300
2.0
0.0
0.30
01:0
3.30
D82
30
2.30
520
0330
0.40
8.0
0.6
033
022
0.30
0.43
233
660
Graph Sparsity (Pubmed)
Graph Sparsity (Pubmed)
Graph Spansity (Pubmed)
Figure 15: Inductive experimental results on training GCNIGAT/GIN on Cora/Cinesee/uubmed datasets, with respect to the graph sparsity.
Acturacy (GCN)
M/V
Accuracy [GAT]
0.703
2:354
0.78
2:34
Accuracy
0.22
0.777
2710
0.739
Our
0700
Vacia
Oum
079
Vae
0770
6.0
837
0.2
550
061
683
1.0
10
0.7
833
0.0
0.5
100
079g
557
0.5
633
G37
623
1.00
Weight Sparsity (Cora)
Weight Spansity (Cora)
Weight Sparsity (Cora)
6.20
Accuracy (GCN)
Accuracy (GAT)
8.200
0.50
2.000
Accuracy
0.00
0.507
2.30
0.00
2.00
Durs
0.077
8.7
0.35
853
067
688
100
0.7
833
030
647
0.55
1.00
0.00
1.7
0.35
053
037
638
100
Weight Sparsity (Citeseer)
Weight Sparsity (Citeszer)
Weight Sparsity (Citeseer)
0.372
2.00
Accuraty (GCN)
0.302
Accurocy (GAT)
2.49
Accuracy (GIN)
0.05
2330
0.02
0.44
2337
0.t.
128
056
106
633
050
0x0g
0.30
683
Weight Sporsity (Pubmed)
Weight Sparsity (Pubmed)
Weight Sporsity (Pubmed)
Inductive experimental results on training GCNIGAT/GIN on Cora/Ciieseer/Pubmee datasets, with respect to the weight sparsity.
Figure 16:
datasets. As similar to the overall process depicted in Table 3 ~ 5, TEDDY consistently saves the actual time about more than 2 times upon baselines across most of the considered settings. More notably, for scale dataset Arxiv and Reddit, the wall-clock time gap become markedly pronounced. This is might be due to the fact that the iterative approaches additionally introduce larger number of learning parameters (for parameter
17

---

Published as a conference paper at ICLR 2024
0.80
0.80
Accuracy (GAT)
0.76
Accuracy (GAT)
0.78
0.68
0.68
UGS
UGS
0.64
WD-GLT
0.64
WD-GLT
UGS w/ Cor
UGS Co
0.56
WD-GLT w/ Co
0.56
WD-GLT w/ Ce
0.52
0.52
w/o
Ours w/o
1-hop Degree
1-hap Degres
0.4g
0.4g
0:30
0.67
0.83
Graph Sparsity (Cora)
Weight Sparsity (Cora)
Figure 17: Ablation study on GAT architectures trained on Cora dataset.
(GAT)
0.29
0.71
Accuracy (GAT)
Accuracy (GAT)
0.9
0.70
0.7
3.9
1355
0.9
UGS w/ PGD
UGS W/ To PG3
1e:
UGS wi PGD
ef Ca
0.50
Oara
Dara
0:66
Oun w/l wiile spar
0.5
Oar wil wagit 2011
Oar w/l waigh sow
313
670
333
6.0
35
660
0.000
0l0
0.00
36
0.n
0.0 Graph Sparsity (Pubmed)
0.00
0.0
0.0
6/0
Graph Sparsity (Cora)
Graph Sparsity (Citeseer)
0.0
0.88
081
Accuracy (GAT)
0:70
Accuracy (GAT)
Accuracy (GAT)
0.7 Tule
0.6
244
UGS
UGS Co
245- 24i
UKS sy Aa
USS w// Ca
PGD
UGS
237
0.0
Our wij Co
Ozn wio Co
Our
0.8
0.6
Weight Sparsity (Cora)
Weight Sparsity (Citeseer)
Weight Sparsity (Pubmed)
Figure 18: Ablation study on GAT trained on Cora/Citeseer/Pubmed dataset, across diverse configu- rations.
masks) particularly when dcaling with large-scale datasets. in overall pruning process, duration WD-GLT reported as N/A or OOM due to prohibitive computation incurred by Sinkhorn itcrations.
18

---

Published as a conference paper at ICLR 2024
0.83
Accuracy (GCN)
0.81
Accuracy (GAT)
0.79
Accuracy (GIN)
0.78
0.79
0.74
0.75
0.77
0.76
Verila
0.65
0.71
0.74
0.01
UGS
0.89
0.72
0.56
WE-GII
WD-GUT
Ours
Ours
Ours
9.78.00
0.10
0.20
0.30 0.40 0.50 0.60
6.00
0.10
0.20
0.30
0.40
0.50 0.60
0.06.30
0.30
0.20
0.30
0.40 0.50 0.60
Graph Sparsity (Cora)
Graph Sparsity (Cora)
Graph Sparsity (Cora)
0.75
0.73
0.74
Accuracy (GCN)
Accuracy (GAT)
0.67
Accuracy (GIN)
0.71
0.61
0.70
0.69
0.68
0.49
0.66
Random
ULS
0.2
Random
BUS
0.65
LGS
Random
0.64
WD-GUT
0.36
WD-GLT
0.63
WD-GUT
Durs
8.0000
0.60
0.30.0
0.10
0.20
0.00.00
0.20
Graph Sparsity (Citeseer)
Graph Sparsity (Citeseer)
Graph Sparsity (Citeseer)
0.82
Accuracy (GCN)
0.81
Accuracy (GAT)
Accuracy (GIN)
0.80
0.74
0.78
0.77
0.76
Varilla
0.87
Yenila
0.75
Venilla
Random
Bandom
Randomm
0.63
LGS
0.73
0.59
0.72
0,78.00
0.10
0.20 0.30 0.40 0.50 0.60
0.58.00
0.10
6220
0.30 0.40 0.50 0.60
0.78.50
0.30 0.40 0.50 0.60 Graph Sparsity (Pubmed)
0.10
0.20
Graph Sparsity (Pubmed)
Graph Sparsity (Pubmed)
Figure 19: Experimental results for a sole graph sparsification including DropEdge (represented as Random) on Cora/CiteseerPubmmed datasets, equipped with GCN/GAT/GIN.
Cora, (Vanilla: 76.34)
Citeseer, (Vanilla: 68.1)
Pubmed, (Vanilla: 77.9)
1
79.64
60.20
Graph Sparsity (%)
Graph Sparsity (%)
Graph Sparsity (%)
76 80
76.56
76.72
76.80
76.56
70.66
16
71.34
71.34
71.32
79.6 62
79.66
79.98
79.76
79.64
76
F7.02
77.10
77.00
77.18
70.98
71.58
71.60
71.50
71.56
79.82
79.90
79.90
79.84
80.16
80
77.04
77.00
77.00
77.30
77.28
g0
71.10
71.40
71.40
71.48
71.40
79.84 84
80.02
34
80.12
80.26
88
77.00
00
76.92
88
71.
80.
80.72
80
85
65
70
75
65
70
75
80
85
Weight Sparsity (%)
Weight Sparsity (%)
Weight Sparsity (%)
Figure 20: Performance on diverse extreme sparsity combinations (in percentage) of TEDDY with GIN, averaged over runs.
19

---

Published as a conference paper at ICLR 2024
Table Duration (sec) of the overall pruning process for each simulation on CoraCCieseerPubbeed datasets, averaged over runs. The comparison is conducted on the machine with NVIDIA Titan Xp and Intel(R) Xeo CPU E5-2630 v4 2.20GHz.
Cora
1-st
5-th
10-th
15-th
20-th
UGS
6,30 0.55
5.84 0.9
5.57 0,00
5.65 = 0.59
5.56 0.73
GCN
WD-GLT
54.11 1 a 1:2
53.61 0.99
53.59 o.1
53.52 0.3
53.77 4 0.7
TEDDY
2.12
2.15
2.09 -0.12
2.11
2.18 0.05
UGS
7.58 + 0.44
7.11 0.51
6.97 0.59
7.03 + 0.00
7.26 0.34
GAT
WD-GLT
83.81 # 10.00
79.98 8.00
80.76 6.30
80.84 # 620
79,40 # 481
TEDDY
3.00 a:0
2.96
3.04
2.93
3.01 0.88
UGS
4.38 0:301
4.11 0.29
4.11 0.25
4.06 +: 0.30
4.01 + 0.19
GIN
WD-GLT
68.55 = 10:15
72.43 1: 1991
70.76 1: 10445
72.04 1033
72.67 11:89
TEDDY
1.86 0.25
1.91
1.85 0.25
1.86
1.86 0.27
Citeseer
1-st
5-th
10-th
15-th
20-th
UGS
8.21 # 1.72
7.44 st 0.52
7.55 0.53
7.36 =: 0.55
7.33 0.42
GCN
WD-GLT
83.73
78.24
77.67
70.75
69.51
TEDDY
2.65 0.33
2.72 0.29
2.70 00.44
2.71 0.29
2.80 0.34
UGS
8.78 + 0.84
8.09 0.52
8.47 0.36
8.64 + 0.77
8.41 0.64
GAT
WD-GLT
93.96
86.23
89.55
89.03
86.74
TEDDY
3.21 0.3
3,35 0.46
3.51 0.50
3.55 =: 0.49
3.63 u.E
UGS
6.61 + 1.11
6,44 + 0.77
6.05 0.35
5.98 + 0.38
6.16 0,42
GIN
WD-GLT
108. 74
109.59
106.69
109.91
107.93 1
TEDDY
2.51 + 0.50
2.53 6.11
2.46 0.09
2.49 + 0.05
2.52 0.16
Pubmed
5-th
10-th
15-th
20-th
UGS
8.40 =
7.80 0.31
7.61 0.55
7.95 =
8.12
GCN
WD-GLT
176.48
16.00
161.88 31.51
160.96 34.56
141.58 1.9
142.68 12.39
TEDDY
3.23 + 0.20
3.27 0.13
3.16 0.14
3.14 + 0.21
3.08 0.12
UGS
9.85
9.35
9.16
9.61
9.41
GAT
WD-GLT
69.64 4.76
68.69 69 831
66.07 5.43
64.38 274
63.66 1.11
TEDDY
3.90 0.36
3.82 0.18
3.58 0.20
3.63 :: 0.21
3.50 0.30
UGS
7.42
7.17
7.11
7,03 +: 223.74 4:9
6.95 041
GIN
WD-GLT
218.87 6.80
214.61 1: 1.44
213.63 1:
216.23 1
TEDDY
3.20 + 0.15
3.12 0.13
3.06 0.10
3.02 + 0.0
2.97 0.12
Table 4: Duration of the overall pruning process Table 5: Duration of the overall pruning process for each simulation on Arxiv dataset, averaged for each simulation Reddit dataset, averaged over 5 runs. The comparison is conducted on the over runs. The comparison is conducted on the machine with NVIDIA GeForce RTX 3090 and machine with NVIDIA GeForce RTX 3090 and Intel(R) Xeon(R) Gold 5215 CPU
2.50GHz. Intel(R) Xeon(R) Gold 5215 CPU @ 2.50G
15-th
38th
LXG5
82.28 1..3
37.33 13.4
1239
13
71.50
1251
UCS
150.90-90.1 00.15
$16.15 631a
15590 153
156.12
158.5 BAM
6Cx
CCN
Tapuy
43-85 4002
39.70 k.3
33.35 680
31.16 100
47.60 4110
48.29 443
33.92 4/0
27.56
23.51 AAD
4.35
SAMI
WD-GLT
N0A
N7A
N0A
NIA
SAGE
WE+GULT
00M
0K0
00M
0UM
41.66 8.32
L182
20

---

Published as a conference paper at ICLR 2024
Table 6: Comparisons of duration (sec) of the parameter sparsification process for each method for each simulation on CoraaChteseer/uummee datasets, averaged over 5 runs. For fair comparison, we consider only the parameter sparsification with original dense graph (i.e. without graph sparsification). The comparison conducted on the machine with NVIDIA Titan Xp and Intel(R) Xeon(R) CPU ES-2630 v4 @ 2.20GHz.
Cora
1-st
5-th
10-th
15-th
20-th
UGS
6.09 1 usi
5,42 4 0.222
5.71 = 0.47
5.47 4:
5.51 0.2
GCN
WD-GLT
62.78 A sM6
60.89
A 0.6
61.38 0.9
61.82
4: 1:15
61.92 087
TEDDY
2.39
2,43
2.44
0.30
2,41
2.41
UGS
6.00
1.4
5.58
4: 0.34
5,60
0.29
5.50
+ 0.18
5.48 0.19
GAT
WD-GLT
61.95 à 3.22
61.45
de 2,13
61.40
d 1,90
59.99
A 1.48
60.27 2.2
TEDDY
2.43 uu
2.47
1: 109
2.50
=: 0.35
2.45
0.88
2.44 IJ8
UGS
4.33
4.15 +
4.05
3.99
3.87
GIN
WD-GLT
61.98 3.15
60.63
60.38 0.46
60.46
60.42 DA4
TEDDY
1.76 1 w83
1.80 1: 0.55
1.82 0.04
1.81 :: 0.02
1.81 amI
Citeseer
1-st
5-th
10-th
15-th
20-th
UGS
8.84 2:22
7.87 + 1.16
7.56 0,81
7.56 + 0.52
7.43 0.63
GCN
WD-GLT
56.97 2.45
56.05
55.96
1.35
55,38
55.29
TEDDY
3.27 1M
3.37
3.46
3,50 1: 6.1
3.60 aJs
UGS
8.42 1.17
7.95 + 0.58
7.91
0.00
7.89 + 0.49
7.77 0.58
GAT
WD-GLT
57.67 222
56.90
+ 0.57
56.47
0,50
57.30 + 1.17
56.51 0.57
TEDDY
3.35
3.39
3.50
3.55
3.66
UGS
8.28 1.00
8.37
8.18 0.54
8.16 0.96
7.81
GIN
WD-GLT
57.50 2022
56.
+ 0.26
56.19 0.54
56.88 1.40
56.38 0.71
TEDDY
3.42 nus
3.46 + 0,94
3.57 0.84
3.62 + 0.02
3.71 0.05
Pubmed
1-st
5-th
10-th
15-th
20-th
UGS
9.21
8,48 4
8.66
8.28
8.38
GCN
WD-GLT
202.28 1 198
201.13 1.54
200.82 1.08
201.07 1.5
201.16
TEDDY
3.91 + nus
+ 1uI7
3.90 = 0.11
3.89 0.10
3.91 = 0.12
UGS
13.69 :: 057
13.18
+: 0.23
13.05 0.24
13.07 2:022
13.12 0.14
GAT
WD-GLT
66.03
65.68
65.65
65.66
65.62
TEDDY
6.33 nus
6.32
1: 0ax
6.33 0.44
6.32 6.4
6.33 AM2
UGS
8.68 0.74
8.38 = 0.15
8.37 0.19
8.35 = 0.11
8.26 0.07
GIN
WD-GLT
157.18 + 0.48
157.03 1.12
156.43
= 0.98
157.75 0.99
157.88 +: 0.51
TEDDY
4.07
4.04
+
4.06
4.04
4.04
Table Duration of the parameter sparsification Table 8: Duration of the parameter sparsification process for each simulation Arxiv dataset, aver-proced for each simulation on Reddit dataset, aver- aged over runs. The comparison conducted on aged over 5 runs. The comparison is conducted on the machine with NVIDIA Titan Xp and Intel(R) the machine with NVIDIA Titan Xp and Intel(R) Xeon(R) CPU 256330 v4 2.20GHz.
Xeon(R) CPU E5- 2630 v4 @ 2.20GHz.
Reddll
1st
5thh
10-th
15th
20th
UGS
12000 15.3
125.75 133
125.00
113.4_ 11.6
11941
210.36
L-00
LK1
OCN
WD-C2.1
N0A
N0A
36A
30A
CCN
WD-OLT
0OM
00M
OUM
0CM
GOM
TEDOY
62.08
32.
$1.75 .037
47,55
1000
58.43 16.0
51.72
UGS
111.1
104.9 122
196.31 2.13
9.702.77
90.71
UGS
203.75
394.5%
185.22
191.35
182
TEDOY
6400-600
66.4
66.13
64.4 A0
TEDoY
8003 4422
78.21
67.93
63.11
$1.83
21

---

Published as a conference paper at ICLR 2024
B EXPERIMENTAL SETTINGS
B.1 DATASET STATISTICS
Table 9: Statistics of benchmark datasets.
Dataset
#Nodes
#Edges
#Classes
#Features
Split ratio
Cora 2,708
5,429
1,433
120/500/1000
Citeseer
3,327
4,732
3,703
140/500//00 1000
Pubmed
19,717
44,338
500
60/500/1000
Arxiv
169.343
1.166.243
128
54%/18%//2%%
Reddit
232,965
23,213,838
602
66%//10%/24%
Table 9 provides comprehensive statistics of the datasets used in our experiments, including the numher of nodes, edges, classes, and features.
B.2 IMPLEMENTATION DETAILS
We implement GNN models and our proposed TEDDY using PyTorch Paszke et (2019) and PyTorch Geometric Fey Lenssen (2019). The experiments are conducted on an RTX 2080 Ti (1IGB) and RTX 3090 (24GB) GPU machines. Following the experiments in UGS (Chen et al., 2021), we consider the same experiment settings Cora, Citeseer, and Pubmed dataset across all GNN architectures, except for GAT whose hidden dimension set 64 owing to suboptimal performance of vanilla GAT. Regarding the experiments on large-scale datasets, we employ three-layer and two-layer GNN on Arxiv and Reddit, respectivly, while fixing the hidden dimension as 256 across both GCN and SAGE. Analogous to the regular-scale experiment, we select the Adam optimizer with an initial learning rate of 0.01 and weight decay 0 uniformly across all lcrge settings. We adopted per-simulation pruning ratio Ps pa 0.05 and hyperparameter search space Las within the range [0.01, 200). The source code our experiments available at https: /ttttbitttbu./..g// con/ jonn//ynjiii 12 TEDDY.
B.3 IMPLEMENTATION DISCREPANCY OF BASELINES WITH GAT
During experiments, observe implementation discrepancy in the baselines (Chen al., 2021; Hui al., 2023) when interfaced with GAT. Specifically, at attention phase, the edge mask to climinate edges in the adjacency matrix is applied preceding the softmax operation on attention coefficients, yielding non-zero outputs even for pruned edges. In effect, the edges are not expected to be actually pruned. To rectify this inconsistency, we slightly revise the source code to guarantee the actual removal of designated edges during the forward pass of GAT.
B.4 REPRODUCING WD-GLT (HUI AL.,, 2023)
Since there is no official implementations in public, we reproduce the baseline results in Hui et al. (2023) by ourselves. In order for our paper to be self-contained we introduce the technique in Hui et al. (2023) in this scction. For better generalization of GLT, Hui et al. (2023) propose novel regularization based on Wasserstein distance (WD) between different classes. Toward this, Z f(G () be the representation obtained from GNN. Further, we define Zo and z as
= {z. E row(Z) argmax(z.) = c}, z x E row (Z): argmax(>>) + cJ
The authors maximize the Wasserstein distance between Z and 2e which is defined by
WD(Z", 2²)
x~I1(2= .2) - [|| =,|12]
inf
(8)
where 1I(2 2 is the set of all joint distributions T(Z., 2,) whose marginals are 2 and 2 respectively. The authors compute this WD for all classes c E = (1, ..., C,,, thus the regularization term would be
R(mg, me, θ) = Σ WD(Z", 2
(9)
The Wasserstein distance between empirical distributions can be estimated by solving the entropy-regularized Wasserstein distance with Sinkhorn iterations. Together with the loss function Eq. (2), WD-GLT consider the final objective C = f. XR with regularization coefficient A.
22

---

Published as a conference paper at ICLR 2024
Equipped with the objective Eq. (9), Hui et al. (2023) solve the minmax optimization problem for robustness formulated as
min max [(mg, ma, 4) @
(10)
The optimization has procedures: (i) adversarially perturbing the mask my via gradient ascent and (ii) minimizing the objective L. with respect my and via gradient descent. More precisely, the update rule would
mng
[++1)
p m + m Vn, [(my) m 19 e("!))
(11)
(141) (9) da Emm (( mg ( + Ommg 1++ Oms
ms mg
Vm, [(m, 1e+1) mm θ (t))
(12)
Implicit gradieas by (q.(1
(t+1), my 0 ( + 3m (1+1) -0(1) -ra (000))7(-(ea (To(VC(mm
3ml+1 (++1)
Vm, [(m (1+1)
m (())
(13)
00
Implicii gradient by (1)
where 7/ and fh2 are learning rates for my and (me; 2) respectively, and controls the strength the implicit gradient by chain rule. The projection operator onto [o, 1 ensures that each entry in the graph mask m has its value in the interval 1]. Hui al. (2023) report that 7/1 122 0.01 and 0.1 are used for experiments. The update rules can be also found Equation (9) (11) in Hui (2023).
We make several remarks on solving the minmax optimization Eq. (10) from our experiences.
In fact, the only case of a corresponds to the correct update rule for the minmax optimization in Eq. (10).
In terms of implementations, the cases for a and a 1 are easy to implement. For exam- ple, in PyTorch library, when solving the inner maximization problem, we only turn on off the create prratt option in loss bbackward() where a 0 corresponds False and 1 is for True. The other case # 0, might require non-trivial handling backpropagation with Sinkhorn iterations multiple times, which could computationally infeasible.
Hence, could not consider the case (2023). However, conisder the cases of
0.1 which is the reported hyperparameter in Hui et al. 1. For both cases of and
0 and values of each entry my, always tends increase, hence projection
a = 1, we observe operator projju.1jVx makes all the entries of m, by 1. Therefore, the magnitude-based graph edge sparsification could not select suitable coordinates to be pruned.
such reasons, we revise the optimization problem in Eq. (11)
min my 122
E(my, me, 2)
(14)
which just minimize the objective with respect to all trainable parameters (specifically, for updating my. we keep the projection operator proj o, x. Under the revised optimization, we only require just single Sinkhorn iterations for approximating Wasserstein distance and successfully reproduce the similar results in Hui et al. (2023).
23


Reviews:
[{"review_id": "V19p29WZnQ", "reviewer": "Reviewer_k6Ge", "summary": "This paper introduces several techniques to sparsify graph data and networks in order to build a sparse graph learning model. The important aspects are as follows:\n1) Degree-based graph sparsification to remove low-degree edges and make graphs sparse;\n2) Distillation by matching the classification logits of the model pre-trained on the whole graphs;\n3) Parameter sparsification by using a subset of parameters (i.e., Projected Gradient Descent).\n\nWhen applied to classical GNNs such as GCN/GAT/GIN, the experimental results validate the proposed method by showing some performance improvements.", "questions": "1. Conventional GNNs are empirically seen to suffer from limited expressivity. How do the latest transformer-based GNNs or more expressive models like GPS[1], Specformer[2], and PPGN[3] compare when applying the proposed techniques? These newer models have already surpassed the empirical performance of older baselines like GCN/GAT/GIN. Validating the proposed techniques on these latest methods rather than older models would make the arguments more convincing.\n\n2. About Figure 1: What is the precise step for removing high-degree or low-degree edges? Given a graph sparsity value, how exactly is the subgraph generated? Is random sampling involved in this process? If so, could you provide the results of multiple runs (e.g., mean and standard deviation) to separate the training-related noise?\n\n3. Ablation Studies: Could you provide detailed ablation studies on the effectiveness of the proposed three components? a) graph sparsification by removing edges; b) model distillation; c) parameter sparsification with projected gradient descent. It seems that these components could be applied separately to any of the baseline training methods (UGS/WD-GLT) in empirical studies.\nIn Figure 13, there are some comparisons made. Graph sparsification doesn’t seem to improve empirical performance at all. There are no curves representing UGS/WD-GLT without distillation loss. Although considering multi-hop subgraphs appears to be effective in a way, this concept is not new in graph learning literature (e.g., k-WL GNNs [4]).\n\n4. The theoretical analysis involving the upper bound of the symmetrically normalized adjacency matrix is somewhat unclear.\na) Concerning the mentioned analysis, how realistic is the assumption of the Lipschitz constant being present?\nb) If the aforementioned assumptions hold true for the specified models, how plausible is it that removing low-degree edges actually increases the term $\\\\frac{\\\\text{deg}\\_\\text{max} + 1}{\\\\text{deg}\\_\\text{min} + 1}$? This aspect may be specific to datasets and could possibly be numerically simulated.\nc) Conversely, removing high-degree edges appears to reduce the generalization gap by lowering $\\\\text{deg}\\_\\text{max}$, according to the preceding analysis. What is the reason this aspect is not emphasized or motivated more within the discussion?\n\n4. In Eq. (5), the edge score is always symmetric. How does this approach apply to directed graphs?\n\n5. How crucial is the distillation training? It appears to undermine the purpose of utilizing sparse graphs, as there is a necessity to initially train the model on the full graphs. This approach also seems to contradict the claim of \"a single training,\" a statement that is reiterated numerous times throughout the paper.\n\n6. The paper asserts that \"TEDDY significantly surpasses conventional iterative approaches in generalization.\" Could you provide more details to substantiate this claim? Which sections or aspects of the experiments corroborate this assertion regarding generalization?\n\n7. The paper claims that the employed PGD training saves computation time compared to the iterative approach. Could you provide additional results to validate this claim, such as comparing training hours using the same GPU hardware?\n\n[1] Recipe for a general, powerful, scalable graph transformer. NeurIPS 2022.\\\n[2] Specformer: Spectral Graph Neural Networks Meet Transformers. ICLR 2023.\\\n[3] Provably Powerful Graph Networks. NeurIPS 2019.\\\n[4] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. AAAI 2019.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed methods are generally straightforward and concise. They empirically improve performance compared to the baselines. The whole process is clearly stated in Algorithm 1.", "weaknesses": "1. Baseline GNN models are somewhat outdated. Traditional GNNs such as GCN/GAT/GIN are known to suffer from limited expressivity, resulting in restricted empirical performances in many cases. Several studies have done expressiveness analysis, to name a few references [3,4]. Later works, such as graph transformers and expressive GNNs [1,2,3], have proven to be more powerful and meaningful for empirical studies.\n\n2. Detailed ablation experiments are lacking, which are necessary to clearly validate the effectiveness of each component.\n\n3. The theoretical analysis concerning the motivation behind preserving low-degree edges seems somewhat disconnected from the main idea.\n\n4. Some claims regarding training efficiency and generalization performance appear to be misleading.\n\nThese points are detailed in the questions section below.\n\n\n\n[1] Recipe for a general, powerful, scalable graph transformer. NeurIPS 2022.\\\n[2] Specformer: Spectral Graph Neural Networks Meet Transformers. ICLR 2023.\\\n[3] Provably Powerful Graph Networks. NeurIPS 2019.\\\n[4] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. AAAI 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VaihFKWavb", "reviewer": "Reviewer_vxbf", "summary": "This paper proposes a one shot graph pruning algorithm to find Graph Lotttery Tickets (GLTs) by (i) deleting graph edges from nodes with higher degrees and (ii) sparsifying node parameters using $l_0$ regularization with Projected Gradient Descent.\nThe sparse networks obtained by the authors are shown to improve performance over existing Graph Lottery Ticket methods.", "questions": "1. The proposed method uses a pretraining strategy on the full graph before the pruning step. Are the parameters reinitialized at the end of the pruning stage like lottery tickets or does training continue after graph sparsification?\n\n2. The authors mention the use of multilevel degree information for the graph pruning criterion in Eq. 4. However, it is not clear if the number of hops considered is determined by the number or layers in the network or is a hyperparameter that is tuned?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method finds GLTs using a one shot training approach outperforming existing iterative graph pruning algorithms.", "weaknesses": "1. While the proposed idea of sparsifying the graph edges based on the degree information is simple and makes intuitive sense (as also shown empirically), why do the authors consider only the degree information as opposed to other metrics like spectral information of the graph or centrality which might convey more information about the graph. Is the degree information sufficient in this regard to obtain a sufficiently sparse graph in comparison with these other metrics? Recent work has shown randomly dropping graph edges can also help training, in comparison to the proposed idea in Yu et al.  [1], how does randomly pruning graph edges compare?\n\n2. The parameters sparsification method used is PGD with $l_0$ regularization. But there is no justification provided for using this particular method. There are other continuous sparsification schemes that have shown to achieve highly sparse networks in a single training run for feedforward networks like Kusupati et al. [2] and Louizos et al. [3].\n\n3. The authors use GATs and GCNs in their experiments. However, the structure of GATs allows them to inherit some degree information in the form of attention while GCNs do not. Does this difference change the performance of the proposed graph pruning criterion for either architectures?\n\n4. The results in Table 1 might be better visualized via a heatmap showing how much Graph sparsity and Weight sparsity can be achieved and if there is a tradeoff between the two.\n\n\n[1] Rong, Yu, et al. \"Dropedge: Towards deep graph convolutional networks on node classification.\" *arXiv preprint arXiv:1907.10903* (2019).\n\n[2] Kusupati, Aditya, et al. \"Soft threshold weight reparameterization for learnable sparsity.\" *International Conference on Machine Learning* 2020.\n\n[3] Louizos, Christos, Max Welling, and Diederik P. Kingma. \"Learning Sparse Neural Networks through L_0 Regularization.\" *International Conference on Learning Representations*. 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5m5ARul8jC", "reviewer": "Reviewer_mYP6", "summary": "The paper proposes TEDDY, a novel edge sparsification framework that considers the structural information of the graph. TEDDY sparsifies graph edges based on scores designed by utilizing edge degrees, and sparsifies parameters via projected gradient descent on $l_0$ ball. In particular, sparsification of both edges and parameters can be done in one-shot and the edge sparsification part does not to consider node features. Then the paper demonstrates the effectiveness of TEDDY over iterative GLT methods with comprehensive experiments.", "questions": "1. Have you evaluated the zero-shot performance of the proposed edge sparsification method (with dense weights)? Intuitively it seems that it might able to work in the zero-shot setting, and in this way, one can single out the effect of sparse subgraph on the boost of performance.\n2.\tWhat happens if the distillation term in (6) is removed (so one does not to try a dense network at first)? How significantly the performance would be affected? Could you provide an ablation study on this?\n3.\tWould TEDDY work if one trains on small graphs and then applies to large graphs?\n4.\tAny intuition why TEDDY is still able to improve the performance of vanilla GNNs under extreme sparsity?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is overall easy to follow.\n2.\tThe experiments are diverse and thorough.\n3.\tIt is an interesting observation that low-degree edges are important, which is supported both empirically and theoretically. The proposed method is thus principally designed.\n4.\tThe proposed method is one-shot and efficient (but seems still need to train a dense network first; see weaknesses).\n5.\tThe proposed method does more than just preserving the performance of vanilla dense GNNs---it actually improves the original performance in many settings. This is an impressive and interesting result.", "weaknesses": "1.\tThe main part of the proposed method and some discussion of the edge degrees are not clear and confusing. \n- It is not very clear to me how T in eq.(5) is actually used (just dropping the edges with the lowest scores)? Also it seems that T computes all scores for all node pairs. How to deal the case when there is no edge between two nodes?\n- Typo in eq.(5)? Should it not include specific node v instead?\n- The analysis of the effect of edge degree in Section 4 only applies for first-order degrees, yet the paper discusses why higher-order edge degrees need to be considered heuristically via a toy example and claims TEDDY is based on “multi-level consideration of degree information“ in section 5.1. Then in the experiments, it never touches upon higher-order edge degree information and only discusses about first-order edge degrees in Figure 8.\n2.\tThe loss objective involves distillation (6), meaning that one still needs to train a dense network on the entire graph first, weakening the efficiency of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QpLk8kCKEy", "reviewer": "Reviewer_SQ4D", "summary": "This paper observes the importance of low-degree edges in the graph and proposes a one-shot edge sparsification framework that leverages edge-degree to find graph lottery tickets (GLT). They achieve superior performances on diverse benchmark datasets.", "questions": "Could the authors compare the consumed time of the proposed method with other baselines to further emphasize the efficiency?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The graph lottery tickets problem is an important direction, and the solution proposed in this paper is simple and elegant by utilizing the low-degree edges. The experimental results are also convincing.", "weaknesses": "Could the authors compare the consumed time of the proposed method with other baselines to further emphasize the efficiency?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vEWdsvnJX5", "reviewer": "Reviewer_QTmY", "summary": "This paper introduces an intuitively derived graph sparsification technique based on edge degrees, and integrates network distillation techniques for weight sparsification. The pruning process is independent of IMP and operates in a one-shot manner.", "questions": "The baseline performance depicted in Fig 6 and 11 appears highly questionable, displaying a significant drop compared to the results reported in [4, 5], as well as my previous replications. Perhaps the authors should consider presenting a more rigorously established and fair baseline performance.\n\nThe references can be found in the weakness part.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. This work demonstrates that high degree edges are less important via empirical observations, which is  significant in LTH community.\n\nS2. Although many prior efforts have explored one-shot GLT; nevertheless, this paper seems to well strike the balance between efficiency and performance.", "weaknesses": "W1. The authors have avoided discussions concerning complexity, yet it appears that $T_{edge}$ might necessitate an $O(N^2)$ space complexity. Any comments on this?\n\nW2. This work appears to be a fusion of two research lines:\n- From the perspective of graph sparsification, there have already been efforts to prune edges based on edge properties and graph connectivity. The assertions made in \\cite{wang2022pruning} closely align with this study, suggesting that the removal of \"non-bridge\" edges (corresponding to the \"low-degree edges\") has minimal impact on graph information flow. Furthermore, it provides theoretical support and error bound analysis.\n- From the perspective of weight sparsification, [1, 2] have extensively explored the feasibility of using PGD for parameter pruning. I cannot see the substantial differences or new contributions in this paper.\n\nW3. While the innovations are intuitively appealing, they still lack theoretical substantiation. The assertion that high-degree edges should be pruned is not a trivial conclusion. I find the similar claim in [3], which examines graph connectivity, to be more appealing. \n\n[1] Zhou X, Zhang W, Xu H, et al. Effective sparsification of neural networks with global sparsity constraint[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021: 3599-3608.\n[2] Cai X, Yi J, Zhang F, et al. Adversarial structured neural network pruning[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019: 2433-2436.\n[3] Wang L, Huang W, Zhang M, et al. Pruning graph neural networks by evaluating edge properties[J]. Knowledge-Based Systems, 2022, 256: 109847.\n[4] Hui B, Yan D, Ma X, et al. Rethinking Graph Lottery Tickets: Graph Sparsity Matters[J]. arXiv preprint arXiv:2305.02190, 2023.\n[5] Chen T, Sui Y, Chen X, et al. A unified lottery ticket hypothesis for graph neural networks[C]//International conference on machine learning. PMLR, 2021: 1695-1706.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)