OpenGSL: A Comprehensive Benchmark for Graph Structure Learning
Authors: Zhiyao Zhou
Sheng Zhou
Bochao Mao
Xuanyi Zhou
Jiawei Chen
Qiaoyu Tan
Daochen Zha
Yan Feng
Chun Chen
Can Wang
Venue: NeurIPS 2023 Datasets and Benchmarks Poster (2023)
Keywords: Graph Representation Learning
Graph Structure Learning
Benchmark
TL;DR: The progress in GSL field remains unclear due to inconsistent experimental protocols. We introduce OpenGSL, the first comprehensive benchmark for GSL to enable a fair comparison and provide helpful insights.

Abstract: Graph Neural Networks (GNNs) have emerged as the *de facto* standard for representation learning on graphs, owing to their ability to effectively integrate graph topology and node attributes. However, the inherent suboptimal nature of node connections, resulting from the complex and contingent formation process of graphs, presents significant challenges in modeling them effectively. To tackle this issue, Graph Structure Learning (GSL), a family of data-centric learning approaches, has garnered substantial attention in recent years. The core concept behind GSL is to jointly optimize the graph structure and the corresponding GNN models. Despite the proposal of numerous GSL methods, the progress in this field remains unclear due to inconsistent experimental protocols, including variations in datasets, data processing techniques, and splitting strategies. In this paper, we introduce OpenGSL, the first comprehensive benchmark for GSL, aimed at addressing this gap. OpenGSL enables a fair comparison among state-of-the-art GSL methods by evaluating them across various popular datasets using uniform data processing and splitting strategies. Through extensive experiments, we observe that existing GSL methods do not consistently outperform vanilla GNN counterparts. We also find that there is no significant correlation between the homophily of the learned structure and task performance, challenging the common belief. Moreover, we observe that the learned graph structure demonstrates a strong generalization ability across different GNN models, despite the high computational and space consumption. We hope that our open-sourced library will facilitate rapid and equitable evaluation and inspire further innovative research in this field. The code of the benchmark can be found in https://github.com/OpenGSL/OpenGSL.

OpenGSL: A Comprehensive Benchmark for Graph Structure Learning
Zhiyao Zhou', Sheng Zochaooochao
Bochao Mao', Xuanyi , Jiawei Chen'
Qiaoyu Tan", Daochen Zha', Yan Feng'. Chun Chen', Can Wang!
*College of Computer Science, Zhejiang University, Hangzhou, China Schooo of Software Technology, Zhejiang University, Ningbo, China NNew York University Shanghai *Rice University (zjucszzy, zhousheng_zj 2ju, bomao, zxy2004 sleepyhunt, fengyan, chenc, wcan]&zju. edu. qiaoyu. www.nyu.nnnncmmmmmmmm edu daochen. zha@rice edu
edu.
Abstract
Graph Neural Networks (GNNs) have emerged as the de facto standard for repre- sentation learning graphs, owing to their ability to effectively integrate graph topology and node attributes. However, the inherent suboptimal nature of node con- nections, resulting from the complex and contingent formation process of graphs, presents significant challenges in modeling them effectively. To tackle this issue, Graph Structure Learning (GSL), family of data-centric learning approaches, has garnered substantial attention in recent years. The core concept behind GSL is jointly optimize the graph structure and the corresponding GNN models. Despite the proposal of numerous GSL methods, the progress in this field remains unclear due inconsistent experimental protocols, including variations in datasets, data processing techniques. and splitting strategies. In this paper, we introduce OpenGSL, the first comprehensive benchmark for GSL, aimed addressing this gap. OpenGSL enables fair comparison among state-of-the-at GSL methods by evaluating them across various popular datasets using uniform data processing and splitting strategies. Through extensive experiments, we observe that existing GSL methods do not consistently outperform vanilla GNN counterparts. We also find that there is significant correlation between the homophily of the learned struc- ture and task performance, challenging the common belief. Moreover, we observe that the learned graph structure demonstrates strong generalization ability across different GNN models, despite the high computational and space consumption. We hope that open-sourced library will facilitate rapid and equitable evaluation and inspire further innovative research in this field. The code of the benchmark can be found in httph:ttt//// // /tt///gtttt h/t/ggttthb.... comm/ppennSLOOpennSS
Introduction
Graph Neural Networks (GNNs) 6 18 13
have emerged the dominant approach for learning on graph-structured data, thanks to their exceptional ability to leverage both the graph topology Considerable endeavors have been recently made enhance the performance of GNNs by refining the architectures of GNN models, such as neural message passing [41 46 45
structure and node attributes 44
I and transformer based methods [19 48 35). However, these model-centric methods overlook the potential flaws of the underlying graph structure, which can result in sub- optimal performance. Notably, extensive evidence from previous studies ( confirms that real-world
"Corresponding Author
37th Conference on Neural Information Processing Systems (NeurIPS 2023) Track on Datasets and Benchmarks.

---

GRCN Yu
Gaug dhao at
SLAPS Futeem st dl
Nodeformer Wu
LDS Franesciietal
Co-training
ProGNN An
IDGL
PTDNet 1so sl.
WSGNN
Chen
GSL
2019
2020
2021
2022
2023
Training Strategy
Whing
CoGSL
SEGSL
leaming
Iter-training
SUBLIME
Pre-training
(b) training
(c) Iter-training
Pre-training
STABLE
Jhan
Figure I: Timeline of GSL research. Existing GSL methods are categorized into three groups based on the training procedure. Bottom left corner illustrates the key difference the interaction between two components.
graphs often exhibit suboptimal characteristics, such the absence of valuable links and the presence of spurious connections among nodes.
To improve the graph quality, Graph Structure Learning (GSL) 58 family of data-centric graph learning methods [51 50 30), has recently attracted considerable research interest. These methods target optimizing the graph structure and the corresponding GNN representations jointly [26] (2 By refining the graph structure, GSL methods can potentially empower GNNs to learn better representations with improved performance. GSL has been successfully applied to disease analysis and protein structure prediction [7]]
16 9 42
Despite the plethora of GSL methods proposed in recent years, illustrated in Figure 1 there is no comprehensive benchmark for GSL,, which significantly impedes the understanding and progress of GSI. in several aspects. i) The use of different datasets, data processing approaches and data splitting strategies in previous works makes many of the results incomparable, üi) There a lack of understanding of the learned structure itself, particularly regarding its homophily and generalizability to GNN models other than GCN. iii Apart from accuracy, understanding each method's computation and memory costs is imperative, yet often overlooked in the literature.
To bridge this gap, we introduce OpenGSL, the first comprehensive benchmark for GSL. OpenGSL implements wide range of GSL algorithms through unified APIs, while also adopting consistent data processing and data splitting approaches for fair comparisons. Through benchmarking the existing GSL methods on various datasets, we make the following contributions:
Comprehensive benchmark. OpenGSL enables a fair comparison among thirteen hate-offthe art GSL methods by unifying the experimental settings characteristics. Surprisingly, the empirical results reveal that GSL methods do not consistently outperform the vanilla GNNs all datasets.
popular datasets of diverse
Multi-dimensional analysis. We conduct a systematic analysis of GSL methods from various dimensions, encompassing the homophily of the learned structure, the generalizability of the learned structure across GNN models, and the time and memory efficiency of the existing methods. Our key findings: Contrary the common belief in the homophily assumption, increasing the homophily of the structure does not necessarily translate into improved performance. ii) The learned structures by GSL methods exhibit strong generalizability. iii) Most GSL methods time- and memory- -nnfforrnnefffcceent. some of which require orders of magnitudes more resources than vanilla GNNs, highlighting the pressing need for more efficient GSL approaches.
Open-sourced benchmark library and future directions: We have made our benchmark library publicly available on GitHub, aiming to facilitate future research endeavors. We have also outlined potential future directions based on benchmark findings to inspire further investigations.

---

To summarize, in this paper, we aim to create a comprehensive benchmark that facilitates the fair evaluation of graph structure learning algorithms, encourages new research, and ultimately advances the progress of the field as a whole.
2 Formulations and Background
Notations. Let G = (V, be a graph, where V is the set of N nodes and A E RNNN is the adjacency matrix. & denotes the edge set and X E I Nxd represents the corresponding feature matrix with dimension d. Typically, GNN model is often parameterized by mapping function f: () + H E RNxi, which maps each node E V into a l-dimensional embedding vector h.. In the remi-supervisee setting, some nodes v; E Virain are often associated with labels yi to guide the training. Please note that in the traditional GNNs, the adjacent matrix A only serves as input and not updated along with the training of GNNs. the GSI. methods, gradually updated structure S E R is learned to replace the original structure A during training process. This is the major difference between traditional GNNs and GSL methods.
Timeline of GSL methods through the lens of training procedures. To provide a global under- standing of the literature, we provide a high-level overview of the existing GSL methods based on their training procedure. Specifically, we identify two key components in GSL methods: structure learning component and GNN component. Based on the interaction between these two components, we partition existing GSL methods into three categories, depicted in bottom left corner of Figure (a) pre-training, (b) co-training, and (c) iter-training. Pre-training involves two-stage learning process, where the structure is learned through pre-training and then used to train GNNs in downstream tasks 28 neural networks that generate the graph structure optimized together with GNNs. The iterative methods 42 59 38) involve training the two components iteratively; they learn the structure from predictions or representations generated by an optimized GNN and use it to train new GNN model for the subsequent iteration. A similar taxonomy can be found in [ Our taxonomy differs by introducing the pre- training category and combining two categories (named joint learning and adaptive learning in (I] into one named co-training.
[26] 22 [2]. In co-training methods [10]
Homophily and Heterophily. Homophily 3 and heterophily are two mutually exclusive measure- ments based on similarity between connected node pairs, where two nodes are considered similar if they share the same node label. The homophily of graph 9 can be formulated as:
homo
[ET ((v, 1y uz) E &, =
where |g] is the number of observed edges. Correspondingly, the heterophily of graph G is defined as 1 - homoog). The homophily of graphs has been widely assumed to be the key motivation for designing GNNs, while few recent works (2 27 have argued on it. Although some GSL methods 53 42 also claim to learn graph structure with high homophily, the homophily of the graph structure learned by GSL methods has not been studied.
3 Benchmark Design
We begin by introducing the datasets utilized in our benchmarking process, along with the algorithm implementations. Then, we outline the research questions that guide our benchmarking study.
3.1 Datasets and Implementations
Datasets. In order to provide a comprehensive evaluation of existing GSL methods, we collect 10 graph node classification datasets that have been widely used in the GSL literature. These selected datasets come from different domains and exhibit different characteristics, enabling us to evaluate the generalizability of existing methods across a range of scenarios. Specifically, we use three classic citation datasets (36). namely Cora, Citeseer, Pubmed, as well as two representative social network datasets BlogCatalog and Flickr [55. Additionally, we include five datasets that have been proposed recently in (34), due to their ability to overcome the drawbacks of the commonly used heterophilous datasets 32 Table T shows the statisties of these datasets, which are divided into two groups according to whether the edge homophily is higher than 0.5. Note that in the five homophilous graph
3

---

Table 1: Overview of the datasets used in this study.
group
Dataset
Nodes
# Edges
# Feat.
Avg. # degree
# Classes
# Homophily
homophilou
Cora
2,708
5,278
1,433
3.9
7
0.81
Citeseer
3,327
4,552
3,703
2.7
6
0.74
Pubmed
19,717
44,324
500
4.5
3
0.80
Questions
48,921
153,540
301
6.3
2
0.84
Minesweeper
10,000
39,402
7
7.9
2
0.68
heterophilious
BlogCatalog
5,196
171,743
8,189
66.1
6
0.40
Flickr
7,575
239,738
12,047
63.3
9
0.24
Amazon-ratings
24,492
93,050
5
0.38
Roman-empire 22,662
32,927
300
2.9
18
0.05
Wiki-conc 10,000
2,243,042
100
448.6
5
0.34
datasets, Questions and Minesweeper are binary classification datasets with highly imbalanced class distributions. We present more detailed introductions in Appendix [A.1] along with other common graph statistics and newly proposed metries [33 that can better capture the characteristics of graph datasets.
The data splitting methods in different GSL works are not consistent, bringing difficulties in conduct- ing fair comparisons. We investigate various GSL works and choose the data splits that are most commonly used. For three citation datasets, we use the classic split from 44 [8]. For BlogCatalog and Flickr, we follow the split in [5 53). For five datasets from 34 we follow the original split in
34
Implementations. We consider collection of state-of-the-art algorithms, including LDS [10].
ProGNN [16). IDGL (2). GRCN
49 GAug [53]. SLAPS [9. GEN (42), WSGNN [20]. Nodeformer
43). CoGSL (24). SUBLIME 26
STABLE [2]. and SEGSL [59]. We rigorously reproduced
all methods according to their papers and source codes. To ensure fair evaluation, we perform
hyperparameter tuning with the same search budget on the same dataset for all methods, More details
on these algorithms and implementations can be found in Appendix A.2
3.2 Research Questions
We carefully design the OpenGSL to systematically evaluate existing methods and inspire future research. Specifically, aim to answer the following research questions.
RQI: How much progress has been made by existing GSL methods?
Motivation. Previous research in GSL has been hindered by the use of different data preprocessing, and splits, which make difficult to fairly evaluate and compare performance of different methods. Given the fair comparison environment provided by OpenGSL, the first research question is revisit how much progress has been made by existing GSL methods. By answering this question, we aim to gain deeper understanding of the strengths and weaknesses of existing methods, and identify areas that offer potential for further enhancements.
Experiment Design. Following the experimental setting of most existing GSL methods, we conduct the node classification experiments on all the datasets. For each method and dataset, we report the mean performance and standard deviation of 10 runs. For binary classification datasets, we report ROC AUC metric, while for other datasets, we report accuracy metric. Since most of the implemented GSL methods have used GCN as backbone, we compare the performances of GSL methods with vanilla GCN verify the enhancement learning structures. Additional results using other backbones can be found in Appendix D.5)
RQ2: Does GSL benefit from learning graph structures with higher homophily?
The homophily assumption has been a fundamental motivation of modern GNNs designs, which has also been brought to the GSL scenarios. More specifically, GSL methods have attempted to learn the structure with higher homophily by introducing explicit
Motivation.
existing
*SLAPS does not use the original graph structure, thus being worse in most cases. Results of all methods without accessing the graph structure are provided in Appendix D.7

---

However, these claims are questionable since they have been evaluated only on limited set of toy datasets (42,, with little examination of their validity on real datasets. As researchers have started to question the homophily assumption on GNNs [29], it becomes imperative re-evaluate the significance of GSL, methods learning more homophilous graph structures.
cenophily-orientte objectives [53 42
Experiment Design. To answer this question, we first compare the homophily of the structure learned by GSL methods with the original one. Then we determine whether the reported performance improvements stem from a more homophilous graph structure by examining the correlation between the homophily and node classification performance.
RQ3: Can the learned structures generalize to other GNN models?
Motivation. Node classification tasks have been a popular means of evaluating GNNs jointly optimized with GSL methods, the quality of the learned graph structure, however, has not been thoroughly evaluated. While GSL has demonstrated improvements certain cases, it remains uncertain whether these improvements can be attributed to learning superior structures. Furthermore, is unclear whether the learned structures have the capability to generalize effectively to other GNN models. Therefore, it is crucial to conduct experiments to evaluate the generalizability of the learned graph structures.
Experiment Design. To answer this research question, we use the learned structure and original features to create new graph data g' (S, X), and train a new GNN method on the new graph. This differs from the setting in RQ1, as we treat each GSI. method as a pre-processing step and train GNN model from scratch using the learned structure, rather than using GNN jointly optimized with the structure. By comparing the performance on the original graph and the new graph, we can evaluate the generalizability
the learned structure. To further verify the effectiveness learned structure, we also include two non-GNN methods, Label Propagation [57 55 and LINK [54), that only take graph structure as input without using node features for node classification.
RQ4: Are existing GSL methods efficient in terms of time and space?
Motivation. As the GSL methods simultancously optimize the GNNs and graph structure, they naturally consume more computational complexity and space than the GNNs. However, the efficiency of GSL methods have been largely overlooked by existing methods. Although introducing the structure learning may benefit the GNNs, the extra computational consumption has posed significant requirements of trade-off between performance and efficiency. It is critical to understand the trade-off for deploying the GSL in the practical applications.
Experiment Design. To answer this research question, we evaluate the efficiency of each GSL method in terms of time and space. Specifically, we record the wall clock rumning time and peak GPU memory consumption during each method's 's training process. For fair comparison, all experiments in this part were conducted on a single NVIDIA A800 GPU.
4 Experiment Results and Analyses
4.1 Performance Comparison (RQ1)
We present the performance of all methods on 10 datasets in Table and and Table Below the key findings from these tables.
① For homophilous graphs, many GSL methods work well in datasets with balanced classes, while they cannot handle highly imbalanced situations. Table demonstrates that most GSL methods outperform vanilla GCN on balanced homophilous graphs such as Cora, Citeseer, and Pubmed. Out of the 12 methods tested, 7 methods exceeded GCN on at least two datasets, and methods outperformed GCN on at least one dataset. However, some methods were unable to surpass vanilla GCN, suggesting that structure learning might even degrade GNN performance. This result highlights the need to investigate the general effectiveness of GSL methods further. In contrast, the results were vastly different on datasets such as Questions and Minesweeper, where only a few methods show advantage over GCN. The imbalanced nature of these datasets limits the power of GSL, indicating that their effectiveness is constrained on such types of data. This fact suggests
In experiments we focus methods that learn unique structure for simplicity.
5

---

Table Node classification results on Cora, Citeseer, Pubmed, Questions and Minesweeper. Shown is the mean + s.d. of 10 runs with different random seeds. Highlighted are the top first, second, and third results. "_" denotes out memory or time limit of 24 hours exceeded.
Model
Cora
Citeseer
Pubmed
Questions
Minesweeper
GCN
81.95 + 0,62
71.34 + 0.48
78.98 + 0.35
75.80 + 0.51
78.28 + 0.44
LDS
84.13 + 0.52
75.16 0.43
ProGNN
80.27 # 0.48
0.42
7 0.29
$1.43 2.22
IDGL
84.19 0.61
73.26
82.78
0.44
50.00 = 0.00
50.00 = 0.00
GRCN
0.73
79.30 +
74.50 + 0.84
72.57 = 0.49
GAug
78.73 7
77.93 # 0.64
SLAPS
7
70.96 70.00
50.89 = 1.72
WSGNN
71.15 0.36
0.35
67.91 = 3.11
Nodeformer
7.22
70.39
78.38 1.94
72.61 + 2.29
77.29 # 1.71
GEN
0.96
0.62
7..99
79.56 # 1.09
CoGSL
8.84
0.79
7
SEGSL
81.04
71.57
7.676
SUBLIME
72,44 0.73
80.56 0
67.21 + 0.99
49.93 : 1.36
STABLE
83.25 0.86
70.99 + 1.19
0.78
70.78 0.27
Table 3: Node classification results BlogCatalog, Flickr, Amazon-ratings, Roman-empin and Wiki-cooc. Shown is the mean + s.d. of 10 runs with different random seeds. Highlighted are the top first, second, and third results. "_" denotes out of memory time limit of 24 hours exceeded.
Model
BlogCatalog
Flickr
Amazon-ratings
Roman-empire
Wiki-cooc
GCN
76.12 0.42
61.60 0.49
45.24 = 0.29
70.41 + 0.47
92.03 0.19
LDS
0.27
ProGNN
73.38 4: 0.30
52.88 + 0.76
56.21 + 0.58
89.07 + 5.59
IDGL
89.68 +
86.03
0.25
45.87 0.58
47.10 + 0.65
90.18 0.27
GRCN
76.08
50.06 0.38
44.41
90.59 + 0.37
GAug
61.98 0.34
48.42 0.39
52.74
91.30 0.23
SLAPS
91.73
0.69
40.97 = 0.45
65.35
89.09 + 0.54
WSGNN
0.33
89.90
42.36 1.06 1.03
$7.33
90.10 0.28
Nodeformer
22.63
6.714
41.33 1.25
56.54
54.83 + 4.43
GEN
0.99
8.884
0.68 0.68
91.15 0.49
CoGSL
0.54
7.410
40.82 =
4
SeGSL.
0.208
0.55
SUBLIME
95.29
0.274
44.49 = 0.30
63.93 + 0.27
76. 10 + 1.12
STABLE
0.556
51.36 1.24
48.36 = 0.21
41.00 + 1.18
80.46 + 2.44
that as many real-world graphs are imbalanced, evaluating the effectiveness of GSLs on imbalanced datasets should receive more attention in the future research.
GSL methods can be effective on specific heterophilous graphs. Table 3 reveals that some GSL methods, including IDGL, GAug, GEN, and SUBLIME, have the potential to exceed vanilla GCN on heterophilous graphs such as BlogCatalog, Flickr, and Amazon-ratings. This finding intriguing because homophily is not well-preserved these graphs, inspiring to investigate the correlation between homophily and structure learning. However, the results are different on Roman-empire and Wiki-cooc datasets, where none of the methods demonstrate an improvement over GCN. This observation suggests that some heterophilous datasets such as Roman-empire and Wiki-cooc may have informative structural patterns that current GSL methods targeting homophily undermine. For more in-depth analysis, please refer to Section 4.2
4.2 Homophily in Structure Learning (RQ2)
To analyze how different methods behave terms of homophily and whether the performance correlated with homophily of the learned structure, we plot the homophily of the learned structure and the node classification performance in the same figure. Figure 2 and Figure 3 show the results, from which we have the following observations:

---

1.0
90
eight OPTW
0.8
80
homophly
0.6
70
0.4
60
0.2
50
0.0
40
cora
otessee
pubmed
minesweeper
Figure 2: Homophily of learned structures and performances on homophilous datasets. The methods ordered by homophily.
1.0
100
0.8
90
homophily
60
0.2
50
0.0
40
blogcatalog
roman-empire
amazon-ratings
Figure 3: Homophily of learned structures and performances on heterophilous datasets. The methods are ordered by homophily.
Table Pearson's correlation coefficient between homophily learned structures and accuracy for different methods on various datasets.
Datasets
Cora
Citeseer
Pubmed
Minesweeper BlogCatalog
Flickr Roman-empire Amazon-ratings
Wiki-cone
Pearson
0.29
-0.50
0.62
0.50
0.86
0.87
-0.25
-0.11
-0.84
@ The homophily of the learned structures varies on homophilous and heterophilous datasets. The results presented Figure 2 are intriguing. They demonstrate that on homophilous datasets, the homophily of the learned structures is scarcely different from the original structure, and in some cases, even lower. This is counterintuitive, considering that methods like GEN explicitly aim to increase the homophily of the learned structures. However, on heterophilous datasets in Figure 3 the homophily of the learned structures is significantly improved in most cases. This distinction may be attributed to the starting level of graph homophily: As GSL methods are trained with limited supervision signals, the number of edges that can be recovered or removed by GSL is limited. Thus, on heterophilous datasets where most edges do not fit the homophily assumption, these limited edges are more likely to updated. the other hand, they are already satisfied on homophilous datasets, explaining the lack of improvement here.
Homophily is not always proper guidance for structure learning. As shown Figure 2 Figure 3 and Table 4 homophily is only significantly positively correlated with performance on two datasets, i.e., BlogCatalog and Flickr. In most cases, do observe positive correlation between the performance and the homophily. in some cases even negatively correlated (on Citeseer and Wiki-cooc). These findings suggest that homophily of structure is not proper guidance for GSL in all cases, which may break the common assumption and call for novel learning objective. This observation can be possibly explained by the viewpoint that certain heterophilous struetural patterns can be leveraged by GNNs (29 27 thereby guiding structure learning with homophily given limited supervision may not generate sufficiently homophilous structure, but break these patterns and leads to suboptimal results.

---

Table 5: Results on Cora. GNNs are trained on structures learned from different GSL methods.
Structure source
GCN
SGC
JKNet
APPNP
GPRGNN
LPA
LINK
Original Structure
81,95
80.00
80.40
83.33
83.51
60.30
50.06
ProGNN
82.58 (10.63)
82.10 (t2.10)
82.24 (11.84)
83.38 (10.05)
83.36 (10.15)
75.85 (+15.55)
78.64 (128.58)
IDGL
83.01 (11.06)
83,44 (13,44)
82.22 (11.82)
(4.34(11.01)
84.76
77.31 (117.01)
75.27 (125.21)
GRCN
83.98 (12.03)
84.66 (14.66) 84.09 (13.69)
83.35 (10.02)
84.41 (10.90)
79.03 (118.73)
81.83 (131.77)
GEN
81.74 (J0.21)
81.82 (11.82)
81.92 (11.52)
82.21 (U1.12)
82.16 (U1.35)
80.97 (120.67)
79.12 (129.06)
SUBLIME
(10.74)
82.32 (12.32)
81.98 (11.58)
82.79 (10.54)
83.59 (10.08)
78.42 (2)
81.25 (131.19)
Table 6: Results on Blogcatalog. GNNs are trained on structures learned from different GSL methods.
Structure source
GCN
SGC
JKNet
APPNP
GPRENN
LPA
LINK
Original Sirueture
76.12
75.37
74.17
93.72
93.82
57,53
64.47
ProGNN
71.73 (14.39)
(10.17))
73.73 (10.44)
93.71 (10.01)
94.70 (10.88)
53.66 (13.87)
66.00 (5153)
IDGL
89.35 (113.23)
75.20
89.77 (115.60)
(4.90(f1.18)
95.39 (f1.57)
13.84 (116.31)
81.25 (+16.78)
GRCN
75.69 (10.43)
74.77 (10.60)
75.62 (11.5)
93.45 (10.27)
93.53 (10.29)
59.68 (12.15)
66.76 (12.29)
GEN
90.01 (113.89)
89.31 (113.94)
90.23 (116.06)
90.37 (13.35)
90.40 (L3.42)
86.04 (+28.51)
86.29 (121.82)
SUBLIME
(118899
94.95 (119.58)
(10.4)
(1163)
(10.69)
89.04 (131,51)
86.45 (121.98)
4.3
Generalizability (RQ3)
We show the performance of several GNN models and simple non-GNN models on Cora and BlogCatalog using the structures learned by GSL methods inputs in Table 5 and 6 Results on other datasets can be found in Appendix D.2 We have the following observation based on the results:
& The structures learned by GSL methods exhibit strong generalizability. The results in Table 5 and [6 demonstrate that many GNN models show improved performance on the learned structure, marked in green, as compared to the original structure. This observation underscores the generalizability of the learned structure and its potential to enhance numerous GNN methods. Additionally, observed that the structures learned by GSL methods also help to improve the performance of two simple non-GNN methods LPA and LINK and in some instances, they outperform GNNs. The promising results strengthen the notion of the learned structure's 's generalizability, even without considering node features as input. In conclusion, the experimental results provide strong evidence for the generalizability of the learned structure and call for further exploration and applications of GSL methods.
4.4
Time and Memory Efficiency (RQ4)
85
85
GRRN
JDGL
GRC
JDGL
84
GAug SUBLIME
WSGNN
STABLE
84
WSGNN GAug
SUBLIME
Accuracye0)
83
83
STABLE
82
GEN
COGSI
82
COGSL
GEN
81
SEGSi.
GT
ProGNN
81
GT
SEGSL
80
80
ProGNN
79
Nodeformer
79
Nodeformer
102
10
10
10
'0
110
space(MB)
time(s)
Figure 4: Time and space consumption of different methods on Cora
The efficiency all methods on Cora are presented in Figure For complete statistics on other datasets, please refer to Appendix D.3
@ Most GSL methods have large time and space consumptions. Figure 4 clearly demonstrate that the current state-of-tha oft GSL methods is struggling to achieve a satisfactory balance between performance and efficiency. In particular, most existing GSL methods suffer from significant effi- ciency issues, with many taking up to ten times longer to run than the GCN method. According to the results, ProGNN the slowest, requiring 190 times longer than GCN. Likewise, most GSL. methods consume excessive amount of memory, with CoGSL consuming up to 66 times more.

---

The efficiency problem of GSL methods is especially pronounced on larger datasets, as discussed in Appendix D.3 According to Table several GSL methods run out of memory when performing graph structure learning on the Questions dataset. Given these findings, it is vital to address the efficiency problem to ensure that GSL methods can be deployed successfully in wide spectrum of real-world scenarios.
Future Direrctions
Drawing upon our empirical analyses, we point out some promising future directions for GSL.
Rethinking the necessity of homophily in GSL While current GSL methods commonly pursue homophily within the refined graph structure, observations @ and E suggest that performance improvements in GSL do not necessarily originate from increased homophily. Consequently, is essential rethink the necessity homophily in GSL and explore other factors contributing the effectiveness of GSL.
Designing adaptive GSL methods for diverse datasets. Observations ! and @ indicate that current GSL method do not universally work well across diverse datasets. Thus, there is an evident opportunity for creating innovative GSL methods that adapt to diverse datasets. To achieve this goal, two critical questions arise: 1) What characteristics should learned structures exhibit for disparate datasets? Our observation @ highlights that sole focus on homophily may lead to substantial improvements in certain datasets, suggesting the need to explore more reliable properties. 2) How can incorporate these characteristics into the structure learning? Some properties might be hard to evaluate or optimize, warranting further investigation.
Developing task-agnostic GSL methods. Existing research efforts GSL are mainly task- motivated. However, real-world scenarios often necessitate the refinement of graph structure without accessing the downstream task. Although there few preliminary works task-agnostic GSL 266 22] (22,. they exhibit certain limitations on preserving the naive characteristics such as proximity which is not sufficient in downstream tasks like graph clustering [12]. The challenge is to extract semantic information from the graph data and to define optimality of the structure in the absence of explicit labels.
Improving the efficiency of GSL methods. Observation exposes the issue of efficiency in GSL, requiring further attention in GSL research. Some GSL methods may run out of memory exceed the time limit, even though the datasets we use are fairly small by today's s standards [14]. The practical utility of current GSL methodologies is often hampered by these efficiency issues. Although some attempts have been made to address this problem, including limiting the weights on pre-existing edges [9] or employing anchor points [2), they commonly compromise the expressiveness of GSL. Drawing inspiration from the successful adoption of sampling strategies in Graph Neural Networks (GNNs) for acceleration [25). it would be promising to devise sophisticated sampling methodologies specifically tailored for GSL.
6 Conclusion and Future Work
This paper introduces comprehensive benchmark for graph structure learning (GSL), OpenGSL, by reimplementing and comparing thirteen cutting-edge methods across diverse set of datasets. The fair comparison and comprehensive analysis unearth several key findings on this promising research topic. Firstly, we observe that GSL methods not consistently outperform vanilla GNNs across diverse datasets. Secondly, we revisit the correlation between homophily and structure learning, encouraging innovative learning objectives other than homophily. Thirdly, we empirically demonstrate the generalizability of the learned structure. Lastly, we highlight the efficiency problem of the existing methods, emphasizing the need to develop scalable GSL methods. We believe that this benchmark will have positive impact on this emerging research domain. We have made our code publicly available and welcome further contributions of new datasets and methods.
We plan to further enhance OpenGSL in the following ways. To begin with, we plan to broaden our dataset coverage to ensure more comprehensive evaluation. Specifically, we will look into heterogeneous networks that are used widely in practical applications. In view of the efficiency limitations in current GSL, methods, we will explore ways to apply structure learning on large-scale datascts such OGB [14]. Lastly, in this study we only focus node classification, which is

---

widely adopted in existing GSL research. As there have been attempts to extend GSL to other tasks (e.g,, graph classification 39 clustering [22). we plan to expand the support of OpenGSL to other graph learning tasks for a more comprehensive coverage. We will update our repository to reflect all the potential new tasks, datasets, as well as any improvement or correction. We are also open to suggestions and welcome any comments to improve our benchmark and elevate its usability.
Acknowledge
This work supported by the Starry Night Science Fund of Zhejiang University Shanghai Institute for Advanced Study, China (Grant No: SN- 7JU-SIAS-00)), the National Natural Science Foundation of China (621062219, 62372399), Zhejiang Provincial Natural Science Foundation of China (Grant No: LTGG23F030005) Ningbo Natural Science Foundation (Grant No: 2022J183) and the advanced computing resources provided by the Supercomputing Center of Hangzhou City University.
References
[1] Y. Chen and Wu. Graph neural networks: Graph structure learning. L. Wu, Cui, Pei, and L. Zhao, editors, Gruph Neurul Networks: Foundations, Frontiers, and Applications, pages 297-321. Springer Singapore, Singapore, 2022.
[2] Y. Chen, L. Wu, and M. Zaki, Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33:19314-193221 2020.
[3] E. Chien, J. Peng. P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations.
[4] L. Cosmo, A. Kazi, S.-A. Ahmadi, N. Navab, and M. M. Bronstein. Latent patient network learning for automatic diagnosis. (2020). 2020.
[5] H. Dai, H. Li, Т. Tian, X. Huang, L. Wang, J. Zhu, and L. Song. Adversarial attack on graph structured data, In International conference machine learning, pages 1115-1124. PMLR, 2018.
[6] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Y. Deshpande, S. Sen, A. Montanari, and F. Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
[8] V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
[9] B. Fatemi, L. EI Asti, and S. M. Kazemi. Slaps: Self-supervision improves structure lcarning for graph neural networks. Advances in Neural Information Processing Systems, 34:22667-2233 -26611, 2021.
[10] L. Franceschi, M. Niepert, M. Pontil, and X. Hc. Learning discrete structures for graph neural networks. In International conference on machine learning, pages 1972-1982. PMLR, 2019.
[11] Gasteiger, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations.
[12] M. Gu, G. Yang. S. Zhou, N. Ma, J. Chen, Q Tan, M. Liu, and J. Bu. Homophily-enhancee structure learning for graph clustering. arXiv preprint arXiv:2308.0 05309, 2023.
[13] W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Proceedings the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc.
[14] W. Hu, M. Fey. M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine leamnigg on graphs. Advances in neural information processing systems, 53:22118- 22133, 2020.
[15] X. Huang. J. Li. and X. Hu. Label informed attributed network embedding. In Proceedings of the tenth ACM international conference on web search and data mining, pages 731-739, 2017.
[16] W. Jin, Y. Ma. X. Liu, X. Tang. S. Wang, and J. Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 66-74, 2020.
10

---

[17] J. Jumper. R. Evans. A. Pritzel, T. Green, M. Figurnov. O. Ronneberger, K. Tunyasuvunakool, R. Bates. A. Zídek, A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873) 2021.
[18] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations. 2017.
[19] D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-211 21622969,, 2021.
[20] D. Lao, X. Yang, Q. Wu, and J. Yan. Variational inference for training graph neural networks in low-data regime through joint structure-label estimation. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 824 834, 2022.
[21] Leskovee and Krevl. Snap datasets: Stanford large network dataset collection, 2014.
[22] Li, Y. Liu, X. Ao, Chi, J. Feng, H. Yang, and Q He. Reliable representations make a stronger defender: Unsupervised structure refinement for robust gnn. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 925-935, 2022.
[23] D. Lim, F. Hohne, X. Li, S. L. Huang, V. Gupta. O. Bhalerao, and S. N. Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-2200 20902, 2021.
[24] N. Liu, X. Wang. L. Wu, Y. Chen, X. Guo, and C. Shi. Compact graph structure learning via mutual information compression. In Proceedings of the ACM Web Conference 2022, pages 1601-1610, 2022.
[25] X. Liu, M. Yan, L. Deng, G. Li, X. Ye, and D. Fan. Sampling methods for efficient training of graph convolutional networks: A survey. IEEE/CAA Journal of Automatica Sinica, 9()):205-33,, 2021.
[26] Y. Liu, Y. Zheng. D. Zhang, H. Chen, H. Peng, and S. Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, pages 1392-1403, 2022.
[27] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.WW Chang, and D. Precup. Revisiting heterophily for graph neural networks. In Advances in Neural Information Processing Systems.
[28] D. Luo, W. Cheng, W. Yu, B. Zong, J. Ni, H. Chen, and X. Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining, pages 779-787, 2021.
[29] Y. Ma, X. Liu, N. Shah, and J. Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations.
[30] M. Mazumder, C. Banbury, X. Yao, B. Karlaš, W. G. Rojas, Diamos, G. Diamos, L. He, D. Kiela, D. Jurado, et al. Dataperf: Benchmarks for data-centric ai development. arXiv preprint arXiv:2207. 10062, 2022.
[31] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):115 444, 2001.
[32] H. Pei, B. Wei, K. C.-C Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations.
[33] O. Platonov, D. Kuznedelev, A. Babenko, and I.. Prokhorenkova. Characterizing graph datasets for node classification; Beyond homephily- dichotomy. arXiv preprint arX1v:2209.06177, 2022.
[34] O. Platonov. D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
[35] I.. Rampášek, M. Galkin, Dwivedi, A. T. Luu, G. Wolf, and D. Beaini, Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-14 2022.
[36] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[37] O. Shehur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop. NeurIPS 2018, 2018.
11

---

[38] Z. Song, Y. Zhang, and I. King. Towards an optimal asymmetric graph structure for robust semi-supervised node classification. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1656-1665, 2022.
[39] Q. Sun, J. Li, H. Peng, J. Wu, X. Fu, C. Ji, and S. Y. Philip. Graph structure learning with variational information bottleneck. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4165-41744 2022.
[40] L. Tang and H. Liu. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 817-826, 2009.
[41] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In
International Conference on Learning Representations.
[42] R. Wang, S. Mou, X. Wang, W. Xiao, Q. Ju, Shi, and X. Xic. Graph structure estimation neural networks. In Proceedings of the Web Conference 2021, pages 342-353, 2021.
[43] Q. Wu, W. Zhao, Z. Li, D. P. Wipt, and J. Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27400 2022.
[44] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
[45] K. Xu, W. Hu, Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations.
[46] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning graphs with jumping knowledge networks. International conference on machine learning, pages 5453-5462. PMLR, 2018.
[47] Z. Yang. W. Cohen, and R. Salakhudinov. Revisiting supe-supe learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[48] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888 2021.
[49] D. Yu, R. Zhang, Z. Jiang, Y. Wu, and Y. Yang. Graph-revised convolutional network. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part III. pages 378-393. Springer, 2021.
[50] D. Zha, Z. Bhat, K.-H. Lai, F. Yang, and Hu, Data-centric ai: Perspectives and challenges. In SDM, 2023.
[51] D. Zha, Z. P. Bhat, K.-H. Lai, F. Yang, Z. Jiang, S. Zhong, and X. Hu. Data-centric artificial intelligence: A survey, arXiv preprint arXiv:2303. 10158, 2023.
[52] J. Zhao, Q. Wen, M. Ju, C. Zhang, and Y. Ye. Self-supervised graph structure refinement for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 159-167, 2023.
[53] T. Zhao, Y. Liu. L. Neves, O. Woodford, M. Jiang, and N. Shah. Data augmentation for graph neural networks. In Proceedings of the aaii conference on artificial intelligence, volume 35, pages 11015-11023, 2021.
[54] F. Zheleva and I. Getoor. To join public and private user profiles. In Proceedings of the 18th international conference on World wide web. pages 531-540, 2009.
join: the illusion of privacy in social networks with mixed
[55] D. Zhou, O. Bousquet, T. Lal, Weston, and B. Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
[56] D. Zhu, Z. Zhang, P. Cui, and W. Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1399-1407, 2019.
[57] X. Zhu. Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
[58] Y. Zhu, W. Xu. J. Zhang, Q. Liu, S. Wu, and L. Wang. Deep graph structure learning for robust representations: A survey, arXiv preprint arXiv:2103.0300) 14, 2021.
12

---

[59] D. Zou, H. Peng, X. Huang, R. Yang. J. Li, J. Wu, C. Liu, and P. S. Yu. Se-gsl: A general and effective graph structure learning framework through structural entropy optimization. In Proceedings of the ACM Web Conference 2023. pages 499-510, 2023.
[60] D. Zügner and S. Günnemann. Adversarial attacks graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019. 2019.
13

---

A Additional Details on Benchmark
A.1
Datasets
Table 7: Statistics of the datasets used in the benchmark. CC₁ denotes average local clustering coefficient. CCg denotes global clustering coefficient. hedge denotes edge homophily. hadj and "LI" denotes adjusted homophily and label informativeness proposed in [33 respectively.
Nodes
Edges
Feat
Avg degree
Classes
CC
CCg
hedge
Radj
LI
Cora
2,708
5,278
1,433
3.9
7
0.24
0.09
0.81
0.77
0.59
Citeseer
3.327
4,552
3,703
2.7
6
0.14
0.13
0.74
0.67
0.45
Pubmed
19,717
44,324
500
4.5
3
0.06
0.05
0.80
0.69
0.41
Questions
48,921
153,540
301
6.3
2
0.06
0.02
0.84
0.02
0.00
Minesweeper
10,000
39,402
7
7.9
2
0.44
0.43
0.68
-0.05
0.00
BlogCatalog
5,196
171,743
8,189
66.1
6
0.12
0.40
0.27
0.09
Flickr
7,575
239,738
12,047
63.3
9
0.33
0.10
0.24
0.14
0.03
Amazon-ratings
24,492
93,050
300
7.6
5
0.58
0.32
0.38
0.14
0.04
Roman-empire
22,662
32,927
300
2.9
18
0.39
0.29
0.05
-0.05
0.11
Wiki-cooc
10,000
2,243,042
100
448.6
5
0.55
0.23
0.34
-0.03
0.02
Cora, Citeseer and Pubmed [36] three citation networks commonly used in prior GSL 43 26], with nodes representing papers and edges representing papers' ci- tation relationships. Node features bag-of-words feature vectors. The label of each node is its category of research topic.
works 16
BlogCatalog [15] is a social network created from an online community where bloggers can follow each other. The features associated with each user are generated based on the keywords in their blog description, while the labels are chosen from a set of predefined categories based on interests of bloggers.
Flickr 15) is platform for sharing images and videos where users can follow each other, forming social network. In this dataset, user-specified interest tags are used to generate features, with the groups they have joined serving as labels.
Five datasets from 34 are listed below.
Amazon-ratings is based on the Amazon product co-purchasing network dataset 21 this dataset, nodes represent products while edges connect products that are frequently bought together. Node features are the mean of FastTTxx embeddings for words present in the product description. The ratings of products are divided into five distinct classes as labels.
Roman-empire is based the Roman Empire article from English Wikipedia. In this dataset, each node corresponds to single word in the text. When two words are consecutive in the text or are connected by a dependency tree, an edge is created between them. Node features are FastText word embeddings. The label of a node is its syntactic role.
Questions is based users are connected if one user answered the other user's question during given time interval. Node features are the mean of FastText embeddings for words in the user's description. The label of node is whether the user remained active on the website. Notably, the dataset is highly imbalanced with 97% of users belonging to the active class.
question-answering website. In this dataset nodes represent users, and two
Minesweeper a synthetic dataset based on the Minesweeper game. Each node represents a square in 100 x 100 grid. Two nodes are connected if they adjacent in the grid. 20% of the nodes are randomly designated as mines for prediction. Node features are one-hot-ent -eneodee numbers of neighboring mines, while for 50% of the selected nodes the features set unknown to increase task difficulty, indicated by a separate binary feature. Notably, the dataset is also highly imbalanced.
Wiki-cooc is based on the English Wikipedia. In this dataset, nodes represent unique words and edges connect frequently co-occurring words. Node features are FastText word embeddings. The label of node is its part of speech.
14

---

A.2 Algorithms
Here we introduce all the GSL algorithms implemented in OpenGSL.
LDS [0] assumes the structure sampled from mutually independent Bernoulli distributions with a total of n parameters. This paper proposes bilevel optimization problem, where the inner problem optimizes GNN parameters on the training set, while the outer problem optimizes the structure parameters the validation set. A meta-learming-basee approach is adopted to optimize the structure parameters.
ProGNN [66 optimizes the adjacency matrix directly, which is set as X parameter matrix. Three properties, namely sparsity, low-rankness, and smoothness, are introduced to guide structure learning.
IDGL models the structure as a weighted cosine function of node representations. To increase efficiency for larger graphs, the paper proposes an anchor-based structure learning method.
incorporates two GNNs, node representations that are used to derive structure via a metric function. Both GNNs are optimized simultaneously to minimize the task loss.
GRCN 49
for node classification and the other for computing
GAug 553 shares a similar architecture with GRCN, differing that GAug employs graph auto- encoder to learn the structure, while structure learning is guided by edge-prediction loss in addition to the task loss.
SLAPS 9 explores the scenario where original structure is absent. It leverages a MLP to obtain node representations to generate structure through metric function. The overall architecture of SLAPS similar to GRCN, with an additional auto-denoising loss to guide structure learning. Specifically, the corrupted features and the learned structure are fed into another GNN, and the output is expected to reconstruct the original features.
assumes that the optimal structure is generated by an SBM model, and further assumes GEN 42
that the similarity matrices the node representations at different levels are observations of the optimal structure. The EM algorithm employed learn the expected optimal structure given well-optimized GNN. GEN performs structural learning and task learning in an iterative way.
Nodeformer 4 is model that allows for layer-wise edge reweighting on all node pairs by utilizing a kemnelized Gumbel-Softtax operator, which reduces complexity from quadratic to linear with respect to the number of nodes. To guide structure learning, extra edge-level regularization is implemented.
CoGSL (24] extracts two fundamental views from the original graph and refines them using view estimator. An adaptive fusion strategy employed to obtain the final view. CoGSL maintains performance of three views while reducing the mutual information between every two views to achieve a "minimal sufficient structure."
SUBLIME 226 presents an approach for unsupervised structure learning. It proposes structure bootstrapping contrastive learning framework, where an anchor structure set up to provide super- vision signals for the learner structure. Specifically, SUBLIME utilizes GNN-based encoder to obtain node representations from both views and optimizes the GNN encoder through node-level contrastive loss. During the training process, the anchor structure is updated every several epochs as interpolation between the anchor structure and the learner structure.
WSGNN 20 is probabilistic generative model that utilizes variational inference to jointly learn node labels and graph structure. employs a two-branch model architecture to collectively refine node embeddings and latent structure. A composite loss function is derived from the underlying data distribution, effectively capturing the interplay between observed data and missing data.
STABLE 22 obtains reliable node representations leveraging contrastive learning. The new structure is computed as the similarity matrix of node representations. In addition, advanced GCN is proposed to enhance the robustness of the ordinary GCN.
SEGSL 59 introduces the concept of graph structural entropy. It starts by enhancing the structure guided by the one-dimensional structural entropy maximization strategy. Then, an encoding tree constructed to capture the hicrarchical information of the graph structure. Finally, SEGSL reconstructs
15

---

Solver
encoder
motric
GraphLeamer
Mip
Coiane
encoder
metric
Atterivee
RGP
Dataset
transform
Tuse
Learned Structure
transform
fuse
ald
KW
Peplace
Mirppyy
Config
Performance
horirea
Adapiive
Figure 5: Code structure of OpenGSL. For specified dataset and configuration, a solver will return the learned structure and performance on the task. Solver serves foundational class that supports different implemented methods. It includes two main modules, GraphLearner and GNN, and controls the training and testing processes. GraphLearner consists of four components, each of which can be easily replaced (as shown on the right).
the graph structure from the encoding tree. The method performs structure learning and task learning in an iterative way.
A.3
Discussion on Related GNN Benchmarks
There have been considerable efforts benchmarking GNNs 37
To name few, Open Graph Benchmark (OGB) [14] released a diverse set of large-scale and challenging datasets covering various graph machine learning tasks. introduces collection of medium-sized datasets to quantify progress and support GNN research.
14 8 23
Our work differs from existing benchmarks in several aspects. Firstly, the best of our knowledge, we are the first to propose a benchmark tailored for Graph Structure Learning (GSL). We have made significant efforts carefully reimplement wide range cutting-edge GSL algorithms. OpenGSL provides a fair evaluation of these algorithms,, and a user-friendly platform for conducting experiments, which is not attainable with existing benchmarks. Secondly, we consider both homophilous and het- crophilious datasets when evaluating GSL-a dimension that has been largely overlooked in existing benchmarks for GNNs. Lastly, in addition node classification(Section 4.1. we include some exper- imental settings that are specific to GSL, such experiments on canoppiillyheerrohilyyStctii [422). generalizability of learned structures(Section 4.3), and results the absence of original struc- D.7). These experimental settings allow to delve deeper into GSL, based on which we have provided valuable insights and promising research directions. We believe that OpenGSL, as benchmark targetting GSL research, can have positive impact this emerging research field.
B Package
We have developed open-sourced package Open Graph Structure Learn- ing (OpenGSLI 0 which offers a comprehensive and unbiased platform for evaluating GSL algorithms and facilitating future research in this domain.
As shown in Figure 5 the code structure is well organized ensure fair experimental settings across algorithms, easy reproduction of the experimental results and convenient trials on flexibly assembled models. OpenGSL consists of the following key modules. The Conf module includes the files that define the necessary hyperparameters and settings. The Dataset module is used to load datasets. The Solver consisting of GraphLearner and GNN controls the process of training and evalu- ation, which serves as the base class for various reproduced methods. GraphLearner composed of four elements, each of which supports multiple design choices. Given
C OpenGSL
Figure 6: OpenGSL
16

---

Table Hlype-paramette search space of all implemented methods.
Algorithm
parame-e
Search Space
learning rale
Ie-1, 1e-2, 1e-3, le-4 Se-4, Se-S, Se-6, Se-7.
General Settings
weight decay
GCN 18
number layers
3,44 16, 32, 64, 128
hidden size
dropout
0.2, 0.5,
K for nearest neighbors
50,0 100, 200
GRCN 49
learning rate for graph learning rate of DAF dropout_adj
Ie-1, 1e-2, 1e-3, le-4
Te-2, le-3
SLAPS 9
0.25, 0.5
dropout_asd adj2
0.25, 0.5
nearest neighhors
10, 15, 20,
A
0.1, 1. 10, 100, 500
ratio
1,5,10 1,
nr
hidden size
16, 32, 64, 128
WSGNN 20
graph skip connection for model
0.6, 0.7, 0.8, 0.9 1,2, 6,
number heads in graph learner
Ir
le-1, le-2, le-3, le-4
CoGSL 24
ve dropout
0.5,
0.5, 0.8
0.2, 0.5, 0.8
0.1,
0, 0.2, 0.5,
number layers
3,
Nodeforner
43
hidden size number heads
16, 32, 64, 128
2,
dropout
0.2, 0.5, 0.8
number of samples for gumbel softmax sampling
10,
weight for edge loss
1,1.1 0.01
for nearest neighhors
7, 9, 10
GEN 42
tolerance for EM
le-2, Ie-3, le-4
threshold for adding edges
0.5, 0.6, 0.7,
K se
2, 3,
SEGSL 59
3,4
LDS 10
10, 15
ProGNN 16
lcarning rate for adj a for interpolation temperature
Ic-1, 1e-2, 1c-3, 1c-4
0, 0.3, 0.5, 0.7, 0.9, 0.3, 0.6, 0.9, 1.2
GAug 51
epochs warm up
10,
number of anchors
300, 500, 700
IDGL
number heads in structure learning
4,
X for interpolation
0.7, 0.8, 0.9
A for interpolation
0.2, 0.3
dropout rale for edge
0, 0.25, 0.5
SUBLIME 26
boolstrapping
0.99, 0.999, 0.9999
threshold for consine similarity
0.1. 0.2, 0.3
STABLE 2
nearest neighbors
1, 1.3,55
specific dataset and config file, solver will return the learned structure and the task performance. For more details and updated features, please refer to our Github repository.
C Additional Details on Experimental Settings
Running Experiments. Our experiments are mostly conducted on a Linux server with an Intel(R)
Xeon(R) Silver 4216 CPU 2.10GHz, 125 GB RAM, and NVIDIA GTX 2080 Ti GPU (12GB). However, some methods may exceed GPU memory, partial experiments (including all
17

---

experiments related to efficiency) on another Linux server with an Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz, 1008 GB RAM, and an NVIDIA A800 GPU (80GB).
General Experimental Settings. We strive to adhere to the original implementation of various GSL methods provided in their respective papers source codes. To achieve this, have integrated different options into a standardized framework as shown in Figure. We choose not to augment the models with LayerNorm as (34), since this technique has not been adopted by GSL algorithms. Consequently, there may be some discrepancies observed in the results for the five datasets from (44]
Hyperparamter. We conduct comprehensive hyperparameter tuning to ensure thorough and impartial evaluation of these GSL methods. When the paper and source code of a particular method do not provide information hyperparameter settings, we tune the corresponding hyperparameters. Hyperparameter tuning is conducted via bayesian search using NN The hyperparameter search spaces of all methods please refer to their original papers. More complete hyperparameter settings for all the methods can be found in our Github repository [6]
presented in Table 8 For detailed meanings of these hyperparameters
D Additional Results
D.1 Additional Results on the Properties of Learned Structure
In Section 4.2, we analyze the correlation between homophily and performance. The results show that homophily is not always positively correlated with performance and therefore not suitable guidance in all scenarios. Here, we present additional results on two new measures named "adjusted homophily" and "label informativeness" introduced by [33]
Adjusted homophily is proposed overcome the sensitivity of commonly used homophily measures to the number of classes and their balance. Specifically, the adjusted homophily of a graph G is defined as follows:
adj odi_h)mo(g)) homo
k= -EEIP(K) p(k)
Σ -b=1 P(A)2
where p(k) -x d(v))) (v.) is the degree of node u,
Label informativeness measures the overall informativeness neighbor's labels for central node's labels in graph. This metric, which goes beyond the homophily-heteropi dichotomy, can further describe the degree of regularity in the connectivity patterns of heterophilous graphs. The label informativeness of graph is defined as follows:
LI(G)= = Ee,or (2)
where p(c1, c2) [[w.]][ 01.2.mm0
2
The adjusted homophily and label informativeness of structures learned by GSL methods on various datasets presented in Figure and Figure respectively.
The figures reveal a similarity in the patterns of adjusted homophily, label informativeness and homophily for structures learned by GSL methods. Notably, adjusted homophily and label informa- tiveness show significant positive correlations with performance only on BlogCatalog and Flickr, which is the same homophily. These results imply that the newly proposed measures unable to effectively gauge structure quality and unsuitable for guiding structure learning on real data, despite that they are found to be effective on synthetic data 33 Further exploration is needed in this aspect.
still
'hups://githubbc "hanp://ithuu..co/minrnnn http:/hhhh..coo//mmmoooottt/////
18

---

1.0
90
agga
Prot perfrmanns
aduuted homophily
80
-70
0.0
60
-0.5
cara
citeseer
pubmed
mineswosper
Figure 7: Adjusted homophily of learned structures and performances homophilous datasets. The methods are ordered by homophily, Left to right on Minesweeper: ProGNN, original, SUBLIME, GEN, GRCN.
1.00
100
adjustnd homophity
60
0.25
40
0.00
-0.25
20
blogratalog
Flickr
roman: pmpire
amazon ratings
wiki cooc
Figure 8: Adjusted homophily of learned structures and performances heterophilous datasets. The methods are ordered by homophily. Left to right on Wiki-cooe: ProGNN, original, GRCN, GEN, SUBLIME.
labal Informativines
0.75
0.50
70
0.25
50
cora
citeseer
pubmed
minesweeper
Figure 9: Label informativeness of learned structures and performances on homophilous datasets. The methods are ordered by homophily. Left to right on Minesweeper: ProGNN, original, SUBLIME, GEN, GRCN.
1.0
100
0.8
90
label label Intommmttteeessss
80
70
0.2
60
0.0
50
-.2
40
blogcataing
flidkr
maazin
wiki-cooc
Figure 10: Label informativeness of learned structures and performances on heterophilous datasets. The methods ordered by homophily.
19

---

D.2 Additional Results on Generalizability
In addition Section 4.3, we also assessed the generalizability of structures learned by various GSL methods on other datasets where GSL methods have made progress. The results are presented in Tables
These additional results are consistent with the conclusions drawn in Section 4.3. In most cases, the learned structures exhibit strong generalizability. These learned structures frequently outperform the original structures and impart additional advantages to various GNN models.
Table 9: Generalizability on Citeseer. Improvements over the original structure are marked green.
Structure
GCN
SGC
JKNet
APPNP
GPRGNN
LPA
LINK
Original Structure
71.34
71.20
68.26
71.86
71.14
26.20
34,70
ProGNN
70.00 (31.34)
69.02 (12.18)
68.33 (10.07)
71.14 (10.72)
70.45 (10.69)
64.46
(13.66)))
57.12 (122.42)
IDGI.
73.03 (11.6))
73.20 (12.00)
72.21 (13.95)
73.82 (116
72.96 (+182)
64.17 (137.97)
64.87 (130.17)
GRCN
70.90 (10.44)
71.44 (10.24)
71.03 (12.77)
73.33 (11.47
73.25 (t2.11)
(144.23)
(134.40)
GEN
72.83 (11.9)
(t1.82)
72.67 (14.41)
73.24
73.27 (12.13)
65.55 (139.35)
68.20 (133.50)
SUBLIME
71.22 (J0.12)
70.76 (10.44)
68.17 (10.09)
72.60
71.64
(10.50)
(12.00))
55.00 (120.30)
Table 10: Generalizability on Pubmed. Improvements over the original structure are marked green.
Structure source
SGC
JKNet
GPRGNN
LINK
Original Structure
78.98
78.96
78.00
80.10
79.05
24.70
44.71
GEN
(10.52)
79.23 (10.27)
79.14 (11.14)
79.83 (10.27)
79.76 (10.71)
51.61 (126.91)
64.79 (120.08)
ProGNN
78.74 (10.24)
78.70 (J0.26)
76.97 (U1.03)
80.33 (10.23)
79 10 (10.05)
24.80 (?0.10)
44.23 (10.48)
GRCN
79.15 (10.17)
79.12 (10.16)
77.92 (10.08)
80.28 (8).18)
79.41 (10.36)
44.82 (120.12)
44.57 (.0.14)
SUBLIME
79.24 (10.26)
(10.71)
(10.90)
80.99 (10.89)
80.49 (11.44)
30.60 (15.90)
(14.87)))8)
Table 11: Generalizability on Flickr. Improvements over the original structure are marked green.
Structure source
GCN
SGC
JKNet
APPNP
GPRGNN
LPA
LINK
Original Structure
61.60
60.72
57.69
83.58
82.31
39.22
42.60
ProGNN
47.28 (J14.32)
60.79 (10.07)
61.63 (13.94)
84.16 (10.58)
86.
40.14 (10.92)
(17.55
GRCN
61.14 (10.46)
58.86 (L1.86)
60.52 (12.83)
83.14 (10.44)
82.11 (10.20)
44.95 (15,73)
50.79 (18.19)
IDGL
85.98 (124.38)
86.43 (125.71)
84.97 (127.28 28)
87.98 (14.40)
88.75 (16.44)
71.18 (?31.96)
80.69 (138.09)
GEN
85,94 (124.34)
85.93 (125.21)
85.86 (128.17)
84.16 (10.58)
85.92 (13.61)
84.15 (144.93)
84.47 (141.87)
SUBLIME
(127.05)
(127.48)
(130.31)
(15.97)
(17.24)
(138.52)
71.86 (129.26)
D.3 Addtional Results Efficiency
We record the efficiency of existing GSL methods on more datasets, and the results are displayed in Figures
15
Based on these results, is evident that the current GSL methods faces challenges in efficiency, and the problem is more severe on large-scale graphs. Henceforth, there is a pressing demand for the development of efficient GSL methods capable of processing large-scale graph data.
20

---

74
74
73
GEN
GAUg.
JDGL SUBLIME
COGSLL
73
GAUg
GRCN
COGSL
GEN
GRCN
72
71
GCN
Nodeformer
ProGNN
WSGNN STABLE
72
GCN
STABLE
WSGNN
Nodeformer
ProGNN
SLAPS
70
70
SLAPS
69
GT
69
68
10
10 68
10
10
10
space(MB)
time
Figure 11: Time and space consumption of different methods on Citeseer
83
83
1DGL
1DGL
82
STABLE
82
STABLE
81
SUBLIME
SUBUME
80
79
GCN
Noreformer
GRCN
ProGNN GAug
WSGNN
80
79-
GCN
Nodeformer
GRCN
WSGNN.
GAug
ProGNN
78
GT
GEN cOGSL"
78-
GT
COGSL
77
10a
10a
10
16a
10>
10a
10*
10
space(MB)
timels)
Figure 12: Time and space consumption of different methods Pubmed
100
SUBLIME
95
.GEN
WSGNN
SLAPS
95
WSGNN SLAPS
GEN
90
IDGL
90
IGLL
85
COGSL
COGSL
80
GCN
GRCN
80
GCN
GAog
GRCN
75
GT
ProGNN
STABLE
75
GT
STABLE
ProGNN
70
10a
10
10
space(MB)
Figure 13: Time and space consumption different methods on BlogCatalog
90
85
85
80
Nodeformer
GAug
GAug
Nodeformer
GEN
75
GRCN
STABLE
STABLE GRCN
70
70
65
WSGNN
WSGNN
60
60
55
50
SUBLIME IDG
COGSL
SLAPS
ProGNN
55 IDGL
COGSIe
SLAPS
SUBLIME
10a
10'
10
10a
10
10
spacelMB)
timels)
Figure 14: Time and space consumption of different methods Minesweeper
GRCN
GEN
GRCN
GEN
STABLE,
GT
GAug
GAUg
STABLE
47
46
JDGL
47
46
JDGL
45
SUBLIME
45
SUBLIME
43
WSGNN
WSGNN
41
42
COGSL
Nodeformer
SLAPS
41
42
COGSL
SLAPS
Nodefomer
40
10
10a
10
10
spacetMB)
timets)
Figure 15: Time and space consumption of different methods on Amazon-ratings
21

---

D.4 Addtional Results on Robustness
GSL is capable of refining the original suboptimal graph structure, which theoretically gives superior robustness compared to GCN. We conduct experiments to evaluate the robustness of some GSL methods. Following [36 22]. we consider two types of attacks: Metattack and Random. In Metattack, we use GCN as the surrogate model and apply Metattack [60] to perturb the graph structure to varying degrees. In Random, we randomly add noisy edges to the graph structure to introduce varying degrees of homophily. The performances of various GSL methods under these two attacks are shown below. Figure [6 show that most GSL methods have a slower rate of decline than GCN, indicating their better robustness compared with GCN. Among them, SUBLIME demonstrates excellent robustness when facing different attacks.
cora
citeseer
85
70
75-
ProGMN
70
IDGL
Accuracy
65
GRCN
GRCN
- GAug
SAug
60
GEN
GEN
55
Ronelorme
COGSL
COGEL
Vodelomer
SUBLINE
SUBLIME
45
GEGSL
STASLE
40
SECSL
STABLE
40
WSGNN
WSGNN
GON
GON
0.15
0.2
0.25
0.05
0.1
0.15
0.2
0.25
Perturbation Rate
Perturbation Rate
Figure 16: Robustness of GSL methods on Cora and Citeseer under Metattack.
cora
citeseer
85
80
70
75
70
ProGMN
IDGL
DDGL
Accuraci
65
GREN
GRCN
60
GAug
50
GAug
55
Nadelorme Commer
GIN
SEN
Nodelsmer
CoOSL
40
COGSL
SUBLINE
SUBLIME
STABLE
STABLE
SEGSL
30
SECSL
WSGWN
WSSNN
0.7
0.6
0.5
0.4
0.3
0.7
0.5 homophily
0.3
0.2
hamophily
Figure 17: Robustness of GSL methods Cora and Citeseer under Random attack.
D.5 Additional Results on Different Backbones
The results presented in previous parts are all obtained from GSL methods using GCN as the backbone. Here, we consider two additional backbones, namely APPNP and GIN, and evaluate performance of GSL methods with these backhones. Figures 18 20 Cora, BlogCatalog, and Roman-empire.
show the experimental results on
The figures clearly illustrate that, when compared to vanilla GNN backbones, most GSL methods exhibit improvements on Cora and BlogCatalog, while do not work on Roman-empire regardless of the backbone used. This is consistent with the observations in Section 4.1. Moreover, when comparing the performance across different backbones, it is evident that GSL's performance can be further enhanced with more advanced backbones. These results indicate that GSL and GNN backbone, which are two parallel research fields, can benefit from each other.
22

---

90
GCN
APPNP
GIN
accuracy
80
75
70
ProGNN
GEN
GAug
GRCN
SUBLIME WSGNN
IDGL
Figure 18: GSL methods with different backbones on Cora. in the left stands for the vanilla backbones.
100
APPNP
GIN
accuracy
90
80
70
ProGNN
GEN
GAug
GRCN
SUBLIME WSGNN
IDGL
Figure 19: GSL. methods with different backbones BlogCatalog. '_' in the left stands for the vanilla backhones.
80
APPNP
70
accuracy
60
50
40
GAug
GRCN
WSGNN
Figure 20: GSL methods with different backbones on Roman-enu coman-emmire. in the left stands for the vanilla backbones. Some methods are not included due to OOM or exceeding time limit.
One clarification need make is the distinction between this experiment and the one conducted in Section 4.3. In both cases, we combine GSL with various GNNs. However, the difference lies in that the performances here obtained from GNNs that are jointly optimized with structure, while in the other setting, we treat each GSL method as pre-processing step and train GNN model from scratch using the learned structure. The purpose the former experiment to investigate the impact of the choices on backbones, while the latter aims to examine whether the improvement of GSL stems from learning superior structures.
23

---

D.6 Additional Results on Synthetic Graphs
In addition to the experiments conducted on real-world datasets, it is essential to include synthetic datasets as well. Synthetic datasets offer the ad advantage of enabling precise control over the homophily of the generated graph, facilitating more fine- ane-grained empirical studies. Here, we adopt the CSBM model to construct synthetic datasets [7]. Following [. we vary the connectivity probabilities to generate graph data with different structural patterns, while ensuring that the generated data satisfies the information-theorert threshold. In the generated dataset, structures with high homophily and low homophily are both informative, which is different from the setting described in Appx. C.4.
Figure 21 shows the performance of GSL methods on synthetic datasets with different levels of homophily. We observe that most methods perform well under high homophily conditions but poorly under low homophily conditions. However, some methods, such as SUBLIME and GEN, perform well even under low homophily. We can also see that the performance of some methods is better at 0.2 than at 0.4. These observations indicate that these methods capture informative heterophilious structures. Further exploration needed address real-world data, which is relatively more complex.
100
95
90
85
80
Accuracy
75
70
65
60
55
50
45
ProGNN
GRCN GAug
SLAPS GEN
Nodeformer SUBLIME
WSGNN
IDGL
0
GCN
0.2
0.4
0.6
0.8
homophily
Figure 21: GSL methods om synthetic data with varying homophily.
D.7 Additional Results without Original Structures
promising direction for GSL is to apply GNN models to data without graph structure, thereby enabling the use of GNNs for wider range of machine learning tasks. Traditional approaches involve using GNN on pre-defined KNN graph. Intuitively, GSL methods should better capture the relationships between samples through joint optimization of the structure and GNN model. In this context, we conduct some preliminary experiments. Specifically, we replace the original structure of graph datasets with an identity matrix the KNN matrix computed from node features, in which case the models have zero knowledge on the graph structures. The results are presented in Table T2
It is evident that most GSL methods exhibit improvements compared with GCN on Cora and BlogCatalog, demonstrating the potential GSL to extend to non-graph data. However, few methods surpass GCN on this regard.
Further exploration is required to gain deeper understanding in
24

---

Table 12: Performance GSL methods without knowledge on the structure. "T" denotes the use of the identity matrix, while "K denotes the use of the feature- based KNN matrix. denotes out of memory or time limit of 24 hours exceeded.
Model
Cora(I)
Cora(K)
BlogCatalog()
(logCotalog(()
Roman-empire()
Roman-empire(K)
GCN
59.00
54.79
$1.86 =
65.98 0.29
65.29
68,33 0.63
65,56 1.33
88.26# 0.49
86.72 0.31
ProGNN
53,06
53.50
85.45 #
$1.50 0.25
IDGL
66.54 1.13
61.38 0.53
91.21 + 0.29
87.85 + 0.29
64.85 + 0.35
55.17 + 9.54
GRCN
70.23 + 0.43
62.03 + 1.02
89.68 + 0.48
82.79 = 0.47
64.86 + 0.28
63.86 + 0.29
GAug
58.98 =
81.92 0.40
61.17 = 0,51
SLAPS
72.29 + 1.01
72.29 = 1.01
91.73 # 0.40
91.73 = 0.40
65.35 + 0.45
65.35 + 0.45
GEN
64.6
63.87 = 1.03
88,50 # 0.63
85.15 0.42
WSGNN
67.27 + 1.22
64.73 1.03
90.30 + 0.37
88.87 0.27
65.78 + 0.19
65.19 0.30
Nodeformer
51.38
57.73 1.72
53.43
39.60 12.26
51.18 + 3.12
53.76 + 1.89
CoGSL
59.68 1.44
0.92
83.68 0.19
85.07 0.45
63.94 + 0.14
63.49 = 0.10
SUBLIME
0.97 0.97
90.91 0.40
82.78 0.76
64.77 = 0.41
64.38 + 0.19
STABLE
2.12
2.57
74.93 0.93
84.08 0.26
SEGSL
58.82 0.76
0.92
86.07 + 0.45
0.16
E Reproducibility
All experimental results in OpenGSI. easily reproducible. We provide more detailed information on reproducibility in the following aspects.
Accessibility. All the datasets, algorithm implementations, and experimental configurations can be found in our open-sourced project at request.
wwtp://.....o./.aaaaeeeaa http://hhwwccccccpppppe/////eaaa without personal
Datasets. All the datasets are publicly available. Cora, Citeseer and Pubmed are publicly available online"] licensed under Creative Commons 4.0. BlogCatalog and Flickr were first released in [40] and further processed in [15), both to the best our knowledge without a license. Five datasets from [4 are available in their repository with the MIT license. All of the above datasets are consented by the authors for academic usage. None of these datasets contains personally identifiable information or offensive content.
Documentation and uses. We have made concerted effort to offer users documentation ensuring their seamless use of our library. We have also added necessary comments to ensure code readability. In addition, we provide the necessary files to reproduce the experimental results, while also serving as examples on how to use the library[") To run the code, the users simply need to run py files with specifies arguments such data, method and gpu.
License We use an MIT license for our open-sourced project.
Code maintenance. We committed continuously updating code while proactively ad- dressing user issues and feedback on a regular basis. Furthermore, we enthusiastically welcome contributions from the community to enhance our library and benchmark algorithms. Nonetheless, we will implement strict version control measures to ensure reproducibility during the maintenance.
"attps//lingg.orggdaasssss hhtps://gitub..co/yyymn http://hhh...mmmmmoeeeeeeee///tt
http:://ppnngg..aaaaccccocciiies html
25


Reviews:
[{"review_id": "nDynhFXcj7", "reviewer": "Reviewer_zkm3", "summary": "", "questions": "", "limitations": "Not applicable. ", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "- The paper gives a comprehensive overview of the GSL field\n- The authors made a great effort to reimplement SOTA GSL architectures carefully\n- The evaluation pipeline and protocol look meaningful and well-designed, and the experiments seem well-executed. Results are carefully analyzed and visualized. \n- I especially liked the detailed analysis with regard to homo- and heterophilic graphs\n- The paper is easy to follow\n\nIn my opinion, this is a good paper that carefully analyzes the current progress and shortcomings of the current SOTA in graph structure learning, i.e., it is a valuable contribution to this research field. ", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "xIia62CjbT", "reviewer": "Reviewer_Vfn3", "summary": "", "questions": "", "limitations": "See my previous section for details.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "+ Clear writing and the paper is easy to understand\n+ Wide coverage of GSL works", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "QTov9z7xUb", "reviewer": "Reviewer_cdzV", "summary": "", "questions": "", "limitations": "The considered graphs are fairly small by today's standards. The computational cost of GSL methods often prohibits the application to large graphs, which seems to be a major drawback compared to traditional GNNs. It would be a good idea to capture (and in turn encourage) scalability in a benchmark study to guide future work toward improving this aspect.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "- The proposed criteria for benchmarking the structure learning aspect are an important step towards better comparing different approaches\n- GSL methodologies vary significantly, which requires elaborate criteria that capture the quality of the learned graph structure, memory requirement and time consumption. This is addressed well by using several metrics that consider the relationship between accuracy and homophily, memory and time consumption.\n", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "qKq8bhJqCJ", "reviewer": "Reviewer_VFMG", "summary": "", "questions": "", "limitations": "I have no comments on this.", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "Besides the contributions mentioned. The paper is:\n1. Well written and well-structured.\n2. The implementation details are helpful to reproduce the results.\n3. The code in the GitHub Repo is easy to use.\n4. Documentation is well-written.\n5. The insights on the homophily and the generalization are helpful to the GSL research community.", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "j0KnWUzxe8", "reviewer": "Reviewer_idmy", "summary": "", "questions": "", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "1. This paper is in general clearly written and easy to follow. \n2. The benchmark is performed under a controlled and fair setting to compare the performances of these baselines. \n3. The observations made by this paper are interesting and may lead to future research problems. I specifically like the observations and experiments on homophily, which challenges a widely accepted assumption and sheds new lights on GSL. \n", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: The paper presents a benchmark for graph structure learning for graph neural networks. A total of three training strategies and 12 GSL models have been studied on 10 node classification datasets. Most reviewers generally agree that the evaluation pipeline and protocol look meaningful and well-designed, and the experiments seem well-executed. The paper also offers insights into the relations between homophily and graph structure learning performance. 

Some reviewers pointed out that the comparison is only made on the node classification task and that more tasks (e.g., graph classification) should be included. I also agree with this point. However, even without the comparison for the graph-level classification tasks, the paper seems still to have sufficient contributions to the field of GNNs by benchmarking the performance and providing sufficient insights on the node classification task.
Decision: Accept (Poster)