Rethinking Structure Learning For Graph Neural Networks

## Abstract

Abstract To improve the performance of Graph Neural Networks (GNNs), Graph Structure Learning (GSL) has been extensively applied to reconstruct or refine original graph structures, effectively addressing issues like heterophily, over-squashing, and noisy structures. While GSL is generally thought to improve GNN performance, it often leads to longer training times and more hyperparameter tuning. Besides, the distinctions among current GSL methods remain ambiguous from the perspective of GNN training, and there is a lack of theoretical analysis to quantify their effectiveness. Recent studies further suggest that, under fair comparisons with the same hyperparameter tuning, GSL does not consistently outperform baseline GNNs. This motivates us to ask a critical question: is GSL really useful for GNNs? To address this question, this paper makes two key contributions. First, we propose a new GSL framework, which includes three steps: GSL base ( i.e., the representation used for GSL) construction, new structure construction, and view fusion, to better understand the effectiveness of GSL in GNNs. Second, after graph convolution, we analyze the differences in mutual information (MI) between node representations derived from the original topology and those from the newly constructed topology. Surprisingly, our empirical observations and theoretical analysis show that no matter which type of graph structure construction methods are used, after feeding the same GSL bases to the newly constructed graph, there is no MI gain compared to the original GSL bases. To fairly reassess the effectiveness of GSL, we conduct ablation experiments and find that it is the pretrained GSL bases that enhance GNN performance, and in most cases, GSL itself does not contribute to the improved performance. This finding encourages us to focus on exploring essential components, such as self-training and structural encoding, in GNN design rather than only relying on GSL.

## 1 Introduction

Graph Neural Networks (GNNs) (Kipf & Welling, ) are effective in capturing structural information from non-Euclidean data, which can be used in many applications such as recommendation (Wu et al., ; ), telecommunication (Lu et al., ), bio-informatics (Zhang et al., ; Kang et al., ; Hua et al., ), and social networks (Li et al., ; Luan et al., ). However, conventional GNNs suffer from issues including heterophily (Suresh et al., ; Yan et al., ; Lu et al., ; Luan et al., ), over-squashing (Brody et al., ), adversarial attacks (Jin et al., ; Liu et al., ; Li et al., ), and missing or noisy structures (Lao et al., ; Wu et al., ; Liu et al., ). To address these issues, Graph Structure Learning (GSL) has been widely used (Zhu et al., ), which reconstructs or refines the original graph structures to enhance the performance of GNNs. However, GSL brings more hyperparameters and adds plenty of computational cost in both the construction process and the learning process. In addition, recent studies (Luo et al., ; Platonov et al., ) have shown that GSL methods cannot consistently outperform traditional GNNs with the same hyperparameter tuning strategy. Therefore, an in-depth analysis of the effectiveness and necessity of GSL is highly needed.

First, to better understand GSL, we propose a comprehensive framework to carefully break down GSL into $3$ steps: GSL bases generation, new structure construction, and view fusion. More specifically, (1) GSL bases are the processed node embeddings used before constructing new structures, which are constructed by either graph-aware or graph-agnostic models with fixed or learnable parameters. (2) Based on the GSL bases, new structures are constructed with similarity-based (Pei et al., ; Jiang et al., ), structural-based (Zhao et al., ; Liu et al., ), or optimization-based approaches (Jin et al., ). Then, graph refinements are followed. (3) To preserve original graphs or combine multiples GSL graphs, several view fusion strategies are applied, e.g., late fusion (Wang et al., ), early fusion (Li et al., ), or separation (Liu et al., ). Compared with the existing categorization of GSL (Zhu et al., ; ; Kolbeck et al., ; Qiao et al., ) that mainly focuses on step (2), our proposed framework carefully disentangles each component in GSL, which enhances our understanding of GSL in GNNs.

Figure: Figure 1: Examples of GSL that use neighbor distribution as GSL bases. The left shows a case of successful GSL, where new connections between red nodes are constructed using their GSL bases 3 green nodes and 1 blue node. The right shows a case of unsuccessful GSL, because the GSL bases of intra-class nodes are not consistent, and nodes with different classes are connected.
Refer to caption: x1.png

With the above framework, we explore the effectiveness of GSL in GNNs. As examples shown in Figure 1, a GSL method creates new connections between nodes with similar GSL bases, which is denoted as the contextual information of the ego node and its neighbors in this case. When the GSL bases show high consistency with intra-class nodes, nodes within the same class are connected, which is beneficial for GNNs (Luan et al., ) and we denote it as successful GSL. Conversely, when the GSL bases show high consistency between inter-class nodes, nodes in different classes are likely to be connected, which is harmful to GNNs and we denote it as unsuccessful GSL. These examples highlight that the effectiveness of GSL is highly contingent on the quality of GSL bases. However, even if most GSL methods are supposed to be successful GSL, do we really need GSL in these cases? In this paper, our answer is ”No”. The prerequisite of successful GSL is that the GSL bases are highly consistent within intra-class nodes, which inherently ensures a high quality of node representations (Kothapalli et al., ). Therefore, even a successful GSL is unnecessary because the GSL bases are already informative enough to provide distinguishable node embeddings.

Based on the above example, we theoretically analyze the effectiveness of GSL by mutual information between node representations and labels. Our results show that the mutual information between GSL bases and labels acts as an upper bound for the mutual information between newly aggregated node representations (derived from the new graph structures by GSL) and the labels, indicating that GSL is unnecessary in most cases. We also explain why existing GSL sometimes outperform GNNs in certain scenarios of heterophily (Pei et al., ; Luan et al., ) or inconsistent neighbor distributions (Zheng et al., ; Ma et al., ), which is missing in the previous works. Under these circumstances, GSL may outperform GNNs but still upper bound by Multilayer Perceptrons (MLP) which only depends on GSL bases. This also explains why ego node separation (Zhu et al., ) is an important part of model design. Our experiments show that, under the same hyperparameter tuning settings, no matter adding GSL to $4$ baseline GNNs or deleting GSL in $8$ state-of-the-art (SOTA) GSL-based methods, there are no significant changes in model performance on node classification. In conclusion, our main contributions are as follows.

- •
We propose a new GSL framework with three steps, which is more comprehensive than the previous literature and helps better understand each component in GSL.
- •
Both of our empirical experiments and theoretical analysis prove that there is no information gained by applying graph convolution on GSL bases under GSL graphs, indicating that most GSL methods are unnecessary.
- •
We fairly re-evaluate the effectiveness of GSL by adding GSL to GNN baselines and removing GSL in SOTA GSL-based methods models. The results show that GSL cannot consistently improve GNN performance.

## 2 Preliminary

#### Graphs.

Suppose we have an undirected graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ with node set $\mathcal{V}$ and edge set $\mathcal{E}$. Let $\bm{Y}\in\mathbb{R}^{N\times C}$ denote the node labels and $\bm{X}\in\mathbb{R}^{N\times M}$ represent the node features, where $N$ is the number of nodes, $C$ is the number of classes, and $M$ is the number of features. The graph structure is represented by an adjacency matrix $\bm{A}$, where $\bm{A}_{u,v}=\bm{A}_{v,u}=1$ indicates the existence of an edge $e_{uv},e_{vu}\in\mathcal{E}$ between nodes $u$ and $v$. The normalized adjacency matrix is given by $\hat{\bm{A}}=\bm{\tilde{D}}^{-\frac{1}{2}}\bm{\tilde{A}}\bm{\tilde{D}}^{-\frac
{1}{2}}$, where $\bm{\tilde{D}}=\bm{D}+\bm{I_{n}}$ and $\bm{\tilde{A}}=\bm{A}+\bm{I_{n}}$ represent the degree matrix and adjacency matrix with added self-loops. The neighbors of node $u$ is denoted as $\mathcal{N}_{u}=\{v|e_{uv}\in\mathcal{E}\}$. Graph Structure Learning (GSL) generates a new graph topology $\bm{A}^{\prime}$, where the new neighbors of node $u$ is denoted as $\mathcal{N}_{u}^{\prime}$

#### Graph-aware models ℳ 𝒢 superscript ℳ 𝒢 \mathcal{M}^{\mathcal{G}} caligraphic_M start_POSTSUPERSCRIPT caligraphic_G end_POSTSUPERSCRIPT and graph-agnostic models ℳ ¬ 𝒢 superscript ℳ 𝒢 \mathcal{M}^{\neg\mathcal{G}} caligraphic_M start_POSTSUPERSCRIPT ¬ caligraphic_G end_POSTSUPERSCRIPT .

Graph-aware models $\mathcal{M}^{\mathcal{G}}$, such as Graph Convolutional Networks (GCN) (Kipf & Welling, ), Graph Attention Networks (GAT) (Velicković et al., ), and ChebNet (Kipf & Welling, ), utilize topological information in graphs through message aggregation or graph filters (Luan et al., ), incorporating both $\bm{X}$ and $\mathcal{G}$. In contrast, graph-agnostic models $\mathcal{M}^{\neg\mathcal{G}}$, such as Multilayer Perceptrons (MLP), only use $\bm{X}$ without considering $\mathcal{G}$.

For example, the updating process of node embeddings in GCN and MLP can be represented as:

$$ $\text{GCN}:\ \bm{H^{l}}=\sigma(\hat{\bm{A}}\bm{H^{l-1}}\bm{W^{l-1}}),\ \ \text {MLP}:\ \bm{H^{l}}=\sigma(\bm{H^{l-1}}\bm{W^{l-1}})$ (1) $$

where $\bm{H^{l}}$ and $\bm{W}^{l}$ are the node embeddings and weight matrix at the $l$-th layer, respectively, and $\sigma(\cdot)$ is an activation function.

#### Graph Homophily.

The concept of homophily originates from social network analysis and is defined as the tendency of individuals to connect with others who have similar characteristics (Khanam et al., ). A higher level of graph homophily makes the topological information of each node more informative, thereby improving the performance of graph-aware models $\mathcal{M}^{\mathcal{G}}$ (Luan et al., ; ; Zheng et al., ). Commonly used homophily metrics include edge homophily (Zhu et al., ; Abu-El-Haija et al., ) and node homophily (Pei et al., ):

$$ $\displaystyle\leavevmode\resizebox{422.77661pt}{}{$h_{\text{edge}}(\mathcal{G} ,\bm{Y})=\frac{\big{|}\{e_{uv}\mid e_{uv}\in\mathcal{E},Y_{u}=Y_{v}\}\big{|}}{ |\mathcal{E}|},\ h_{\text{node}}(\mathcal{G},\bm{Y})=\frac{1}{|\mathcal{V}|} \sum_{v\in\mathcal{V}}\frac{\big{|}\{u\mid u\in\mathcal{N}_{v},Y_{u}=Y_{v}\} \big{|}}{\big{|}\mathcal{N}_{v}\bigl{|}}$}$ (2) $$

#### Contextual Stochastic Block Models with Homophily (CSBM-H).

To study the behavior of GNNs, CSBM-H (Luan et al., ; Ma et al., ) have been proposed to create synthetic graphs with a controlled homophily degree. Specifically, in CSBM-H, for a node $u$ with label $y$, its features $\bm{X_{u}}\in\mathbb{R}^{M}$ are sampled from a class-wised Gaussian distribution $\bm{X}_{u}\sim\bm{N}_{Y_{u}}(\bm{\mu}_{Y_{u}},\bm{\Sigma}_{Y_{u}})$ with $\bm{\mu}_{Y_{u}}\in\mathbb{R}^{F}$ and $\bm{\Sigma}_{Y_{u}}\in\mathbb{R}^{F\times F}$, where each dimension of $\bm{X}_{u}$ is independent from each other, i.e.,$\bm{\Sigma}_{Y_{u}}=\text{diag}(\mathbb{R}^{n}_{\geq 0})$. Then, to generate graph structure $\mathcal{G}$ with given homophily degree $h$ with the range of $[0,1]$, the node $u$ has the probability $h$ to connect intra-class nodes and the probability $\frac{1-h}{C-1}$ to connect inter-class nodes. After applying neighbor sampling, both of the node homophily $h_{node}$ and edge homophily $h_{edge}$ in $\mathcal{G}$ are approximately equal to $h$.

#### Mutual Information.

Mutual Information quantifies the amount of information obtained about one random variable given another variable (mut, ). The mutual information between variable $X$ and $Y$ can be expressed as:

$$ $I(\bm{X};\bm{Y})=\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}}p(x,y)\ \log{ \frac{p(x,y)}{p(x)p(y)}}$ (3) $$

where $p(x,y)$ is joint probability, and $p(x)$ and $p(y)$ are marginal probability.

Mutual information could be used to analyze the quality of input features by measuring how much information the inputs $\bm{X}$ retain about the outputs $\bm{Y}$. However, in graphs under the task of node classification, the mutual information between a discrete variable $\bm{Y}$ and a continuous variable $\bm{X}$ cannot be directly measured by Eq. (3). Therefore, in this paper, we measure the mutual information $I(\bm{X};\bm{Y})$ based on entropy estimation from k-nearest neighbors distances following (Kraskov et al., ; Ross, ; Kozachenko & Leonenko, ).

## 3 Graph Structure Learning

This section introduces our proposed Graph Structure Learning (GSL) framework. Previous surveys (Zhu et al., ; ; Qiao et al., ) only focus on new structure construction, constituting one step in GNNs learning. To provide a comprehensive understanding of GSL with GNNs, as shown in Figure 2, our framework includes three steps: GSL bases generation, new structure construction, and view fusion. Then we describe the pipeline of the GSL framework: First, GSL bases $\bm{B}$ is constructed based on node features $\bm{X}$ (and input graphs $\mathcal{G}$). Then, new graph structures $\mathcal{G}^{\prime}$ are constructed with the GSL bases. Last, the information from new graph $\mathcal{G}^{\prime}$ (multiple views if possible) and original graph $\mathcal{G}$ are combined with different view fusion strategies for the training of GNNs. Please refer to Appendix A for a more detailed explanation of the representative GSL methods within our proposed GSL framework.

Figure: Figure 2: A framework of GSL.
Refer to caption: x2.png

### 3.1 GSL Bases

The GSL bases $\bm{B}$ is defined as the processed node embeddings used before constructing new structures. The quality of the GSL bases plays a crucial role in determining the performance of GNNs with GSL. For node classification tasks, an effective GSL bases $\bm{B}$ should exhibit consistency among intra-class nodes, as shown in the left part of Figure 1, is expected to be consistent among intra-class nodes. From the embedding training perspective, the construction of $\bm{B}$ can be categorized as either non-parametric approaches (Franceschi et al., ; Pei et al., ; Zou et al., ), which generate static $\bm{B}$, or parametric approaches (Jin et al., ; Chen et al., ; Yu et al., ), which updates $\bm{B}$ dynamically during training. From the perspective of information usage, the construction of $\bm{B}$ can be categorized into graph-agnostic approaches (Franceschi et al., ; Jin et al., ; Zou et al., ) or graph-aware approaches (Pei et al., ; Yu et al., ; Wang et al., ). Combining these two perspectives, in Figure 2, we show the diagrams of four types of of $\bm{B}$ construction: $\bm{B}=\bm{X}$, $\bm{B}=(\bm{A})^{k}\bm{X}$, $\bm{B}=\text{MLP}(\bm{X})$, and $\bm{B}=\text{GNN}(\bm{X},\bm{A})$.

### 3.2 New Structure Construction

The construction of the new structure $\mathcal{G}^{\prime}$, based on $\bm{B}$, is a key element of GSL. From the perspective of relation extraction, methods for constructing $\mathcal{G}^{\prime}$ can be categorized into similarity-based (Pei et al., ; Jiang et al., ; Li et al., ), structure-based (Zhao et al., ; Liu et al., ; Zou et al., ), and parametric optimization-based (Jin et al., ; Liu et al., ; Li et al., ) approaches. Similarity-based methods are the most prevalent, and the choice of similarity measurement, such as k-Nearest Neighbors (Franceschi et al., ), cosine similarity (Chen et al., ), or Minkowski distance (Liu et al., ), plays a critical role in the quality of the reconstructed graphs. However, the initial $\mathcal{G}^{\prime}$ produced by these methods often results in a coarse graph structure, which may not be optimal for GNN training. Thus, further refinements are often necessary, such as sampling (Zhao et al., ; Li et al., ; Liu et al., ), symmetrization (Yu et al., ; Fatemi et al., ; Liu et al., ), normalization (Zhao et al., ; Liu et al., ; Jiang et al., ), or applying graph regularization (Jin et al., ; Jiang et al., ; Li et al., ).

### 3.3 View Fusion

In cases where the methods (Fatemi et al., ; Zou et al., ; Jiang et al., ) already implicitly fuse the information from $\mathcal{G}$ into $\mathcal{G}^{\prime}$, further view fusion is unnecessary. However, for other approaches, the fusion of information from the original graph structure $\mathcal{G}$ and the reconstructed structure $\mathcal{G}^{\prime}$ is crucial. Based on the fusion stage, methods can be classified as early fusion (Li et al., ; Lao et al., ; Liu et al., ), late fusion (Wang et al., ; Liu et al., ; Zheng et al., ), or separation (Liu et al., ). Early fusion, often seen as ”graph editing”, modifies $\mathcal{G}$ by adding or removing edges with $\mathcal{G}^{\prime}$ before training. Late fusion keeps both views as input, fusing node embeddings either at each layer or in the final layer. Separation methods, typically paired with contrastive learning, maintain multiple views without embedding fusion during GNN training. Additionally, view fusion methods can be further distinguished by whether they involve parameter sharing across layers during training.

### 3.4 Training Mode

In addition to the previous three steps, the training mode of $\mathcal{G}^{\prime}$ plays a crucial role in GSL and can be categorized into static, joint, and 2-stage approaches. Most methods (Jin et al., ; Li et al., ; Yan et al., ) use joint training where $\mathcal{G}^{\prime}$ and model parameters are optimized simultaneously. In contrast, some methods (Wang et al., ; Liu et al., ; Franceschi et al., ) follow a 2-stage mode, iteratively updating $\mathcal{G}^{\prime}$ and model parameters. While dynamic updates offer greater flexibility for learning complex structures through parameter optimization, they also significantly increase computational complexity, especially during the bases and graph construction steps. To address this, other methods (Zheng et al., ; Suresh et al., ; Li et al., ) opt for a static $\mathcal{G}^{\prime}$ during training. Although this fixed structure may limit performance, it avoids the time-consuming process of frequent graph updates.

## 4 Effectiveness of Graph Structure Learning

This section analyzes the impact of GSL on GNN performance with empirical observations in Section 4.1 and theoretical analysis in Section 4.2. Then, the time complexity of GSL is analyzed in Section 4.3.

### 4.1 Empirical Observations

Figure: (a) $\bm{B}=\bm{X}$
Refer to caption: x3.png

#### Setting

Based on CSBM-H, we generate synthetic graphs with $10$ random seeds for each homophily degree $h\in\{0,0.1,\dots,1.0\}$ to mitigate randomness effects. Each graph $\mathcal{G}$ contains $1000$ nodes, with each node characterized by $10$ features, $5$ balanced classes, and a degree sampled from the range $[2,10]$. Then, for the GSL, we apply k-Nearest-Neighbors algorithm on GSL bases $\bm{B}$ with $k=5$ to generate new graphs, i.e., $\mathcal{G}^{\prime}=\text{kNN}(\bm{B})$. To inspect the effectiveness of GSL, based on $\bm{B}$, $\mathcal{G}$, and $\mathcal{G}^{\prime}$, we can get several forms of node representation: $\bm{B}$, $\bm{H}=\text{GCN}(\bm{B},\mathcal{G})$, and $\bm{H}^{\prime}=\text{GCN}(\bm{B},\mathcal{G}^{\prime})$, corresponding to the node representation of MLP, GCN, GCN+GSL respectively. We assess the performance of these methods on node classification tasks using mutual information, $\text{MI}(\cdot)$, as a non-parametric measure, and accuracy, $\text{Acc}(\cdot)$, as a parametric measure.

To consider both the graph-agnostic bases and graph-aware bases as discussed in Section 3.1, the GSL bases is selected as $\bm{B}=\bm{X}$ and $\bm{B}=\bm{\hat{A}}\bm{X}$ as shown in Figure 3a and Figure 3b respectively. For example, on the left part of Figure 3a, the performance of MLP, GCN, GCN+GSL is shown as mutual information $I(\bm{B};\bm{Y})$, $I(\bm{H};\bm{Y})$, and $I(\bm{H}^{\prime};\bm{Y})$ respectively. Based on these results, we make several observations as follows:

Observation 1. Mutual information is an effective non-parametric measure of model performance. As shown in Figure 3a and Figure 3b, the trend of mutual information $I(\cdot)$ (left) closely mirrors the model accuracy $\text{ACC}(\cdot)$ (right). Additionally, mutual information effectively distinguishes performance differences between methods. Since mutual information is non-parametric, it offers a flexible and reliable measure, making it suitable for theoretical analysis in the next section.

Observation 2. MLP performs comparably to GCN+GSL under the same GSL bases. In Figure 3a, the mutual information $I(\bm{B};\bm{Y})$ and classification accuracy $\text{ACC}(\bm{B},\bm{Y})$ are close to $I(\bm{H^{\prime}};\bm{Y})$ and $\text{ACC}(\bm{H^{\prime}},\bm{Y})$, respectively, across both graph-agnostic and graph-aware GSL bases. This suggests that, contrary to the expectation that GSL might enhance performance, the results indicate that the model performance does not improve significantly after applying graph convolution on $\mathcal{G}^{\prime}$, reinforcing the GSL controversy discussed in Figure 1.

Observation 3. GCN+GSL sometimes outperforms GCN in heterophilous graphs. As shown in Figure 3a, the $I(\bm{B};\bm{Y})$ or $\text{ACC}(\bm{B},\bm{Y})$ increases with a higher homophily degree, while $I(\bm{H}^{\prime};\bm{Y})$ or $\text{ACC}(\bm{H}^{\prime},\bm{Y})$ remain stable across homophily degrees. In graphs with low homophily, the neighbors identified by GSL are more likely to share the same labels as the target node compared to the original graph neighbors, which causes GCN to underperform relative to GCN+GSL. However, this effect is observed only when $\bm{B}=\bm{X}$ (3a). When $\bm{B}=\bm{\hat{A}}\bm{X}$ (3b), the GSL bases does not exhibit consistency among intra-class nodes in low homophily settings, leading GCN+GSL to perform worse than GCN.

These observations highlight that even when GCN+GSL outperforms GCN, its performance remains close to MLP under the same GSL bases. Recent studies (Luo et al., ; Platonov et al., ) also indicate that under consistent hyperparameter tuning, GSL does not always consistently outperform classic GNN baselines. This leads us to reconsider the necessity of GSL. Thus, in addition to the empirical observations above, we proceed with a theoretical analysis of GSL’s effectiveness in the following section.

### 4.2 Theoretical Analysis

To explain the above empirical observations, in this section, we first prove that the mutual information $I(Y;H)$ of label $Y$ and aggregated features $H$ serve as a non-parametric measurement of the performance of graph convolution. Following this, we compare the mutual information between the node labels $\bm{Y}$ and either the original GSL bases $\bm{B}$ or the aggregated GSL bases $\bm{H}^{\prime}$ (on GSL graph $\mathcal{G}^{\prime}$), to highlight the impact of GSL on model performance.

- Theorem1.
Given a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ with node labels $\bm{Y}$ and node features $\bm{X}$, the accuracy of graph convolution on node classification is upper bounded by the mutual information of node label $Y$ and aggregated node features $H$:
$P_{A}\leq\frac{I(Y;H)+\log 2}{\log(C)}$
(4)

- Theorem2.
Given a reconstructed graph $\mathcal{G}^{\prime}=\{\mathcal{V},\mathcal{E}^{\prime}\}$ on a bases $\bm{B}$, the mutual information $I(Y;B^{\prime})$ of node label $Y$ and aggregated bases $B^{\prime}_{u}=\frac{1}{\left|\mathcal{N}_{u}\right|}\sum_{v\in\mathcal{N}_{u}
}B_{v}$ is upper bounded by $I(Y;B)$.

where the proofs are shown in Appendix B.

Theorem 1 shows that the mutual information $I(Y;H)$ provides an upper bound on the accuracy of graph convolution for node classification, which justifies why mutual information serves as an effective measure of model performance, as demonstrated in Observation 1.

Based on the conclusion of mutual information in Theorem 1, we analyze the effectiveness of GSL. Theorem 2 shows that the graph convolution on new graphs generated by GSL does not increase mutual information. This explains why MLP performs similarly to, or sightly better than, GCN+GSL in Observation 2 and the GSL controversy in Figure 1, because GSL doesn’t introduce additional information compared to the original GSL bases. (^1^11Admittedly, this theoretical analysis cannot be extended to optimization-based GSL due to the complexity of non-linear optimization problems. As such, the unnecessity of GSL in these methods is confirmed through our experiments.)

To further explain Observation 3 in Section 4.1, we refer again to Theorem 2. In conjunction with previous studies on graph homophily (Pei et al., ; Luan et al., ; Zheng et al., ), we know that the performance of GCN could be inferior to MLP on heterophilous graphs. Since GCN+GSL is upper bounded by the MLP on the same GSL bases, when MLP outperforms GCN, GCN+GSL may also outperform GCN, as seen in Figure 3a. However, even when GCN+GSL surpasses GCN in some cases, it still lags behind MLP, a much simpler model, on the same GSL bases. Therefore, we hypothesize that previous GSL improvements stem from the construction of the GSL bases or the introduction of additional model parameters. A fair comparison of GSL with other GNNs or MLP baselines should be conducted using the same GSL bases, as demonstrated in our experiments.

### 4.3 Complexity Analysis

After investigating the difference in the performance of GCN+GSL and GCN, we then analyze the time complexity of some representative methods of GSL, such as IDGL (Chen et al., ), GRCN (Yu et al., ), GAug (Zhao et al., ), and HOG-GCN (Wang et al., ), as shown in Table 3. Assume the dimension of node representation is $F$ for all the layers, the additional time complexity introduced by GSL generally includes: 1. Construction of GSL bases: $O(\left|\mathcal{E}\right|F+\left|\mathcal{V}\right|F^{2})$ for graph-aware bases or $O(\left|\mathcal{V}\right|F^{2})$ for graph-agnostic bases, 2. Graph construction: $O(\left|\mathcal{V}\right|^{2}F)$, 3. Graph refinement: $O(\left|\mathcal{V}\right|^{2})$, and 4: View Fusion $O(\left|\mathcal{V}\right|^{2})$. Apart from the complexity of the new graph construction in GSL, during the graph convolution, compared with GNNs without using GSL, the additional complexity is further introduced by single view GSL $O(\left|\mathcal{E}^{\prime}\right|F)$ or multiple view GSL $O((N_{\mathcal{G}}-1)(\left|\mathcal{E}\right|F+\left|\mathcal{V}\right|F^{2}))$, where $\left|\mathcal{E}^{\prime}\right|$ is the additional edges introduced in GSL and $N_{\mathcal{G}}$ is the number of views in GSL. Consider the fact that $\left|\mathcal{V}\right|^{2}\gg\left|\mathcal{E}\right|$, we have the total additional complexity of GSL by summing up all these terms: $O(\left|\mathcal{V}\right|^{2}F+\left|\mathcal{V}\right|F^{2})$. Compared with the complexity in normal GCN $O(\left|\mathcal{E}\right|F+\left|\mathcal{V}\right|F^{2})$ (Blakely et al., ), this additional complexity $O((\left|\mathcal{V}\right|^{2}-\left|\mathcal{E}\right|)F)$ adds tremendous training time and grows exponentially with the number of nodes in graphs, which is shown in our experiments.

## 5 Experiments

In this section, we evaluate the effectiveness of GSL by comparing the performance of baseline GNNs and GNNs augmented with GSL (GNN+GSL), as well as the performance of GSL-based state-of-the-art (SOTA) methods against their non-GSL counterparts (SOTA vs. SOTA-GSL) on node classification tasks. The results of these comparisons are presented in Section 5.1. Additionally, we analyze the quality of the newly constructed graphs generated by GSL in Section 5.2 and investigate how different components of GSL impact model performance in Section 5.3.

Settings. Our experiments include several baseline GNNs: GCN (Kipf & Welling, ), SGC (Wu et al., ), GraphSage (Hamilton et al., ), and GAT (Velicković et al., ), and GSL-based SOTA models: GAug (Zhao et al., ), GEN (Wang et al., ), GRCN (Yu et al., ), IDGL (Chen et al., ), NodeFormer (Wu et al., ), GloGNN (Li et al., ), WRGAT (Suresh et al., ), and WRGCN (Suresh et al., ). The datasets used in our experiments include heterophilous graphs: Squirrel, Chameleon, Actor, Texas, Cornell, and Wisconsin (Pei et al., ; Rozemberczki et al., ), homophilous graphs: Cora, PubMed, and Citeseer (Yang et al., ), and Minesweeper, Roman-empire, Amazon-ratings, Tolokers, and Questions (Platonov et al., ). We show more dataset details in Appendix C. The model performance is measured by accuracy for multi-class datasets or AUC-ROC for binary-class datasets on node classification tasks. For the data splits, we use $50\%/25\%/25\%$ in train/validation/test sets for GNN+GSL and follow the default splits in OpenGSL (Zhiyao et al., ) for each SOTA or SOTA-GSL method. Please refer to Appendix D for more implementation details.

### 5.1 Performance Comparison

GNN+GSL. We investigate the impact of GSL by comparing the performance of GNN and GNN+GSL. As GSL introduces significant variations in three key aspects, outlined in Table 3, we aim to comprehensively evaluate all possible GSL configurations through a combination of various GSL components, which include 1) GSL bases: original features $\bm{X}$, aggregated features $\bm{\hat{A}X}$, MLP-pretrained features $\text{MLP}(\bm{X})$, GCN-pretrained features $\text{GCN}(\bm{X},\bm{A})$, GCL(Graph Contrastive Learning)-pretrained features $\text{GCL}(\bm{X},\bm{A})$; 2) GSL Graph Construction: Graphs constructed via cosine similarity at the graph level (cos-graph), node level (cos-node), and k-nearest neighbors (kNN); and 3) View Fusion: early fusion $\{\mathcal{G}^{\prime}\}$, late fusion $\{\mathcal{G},\mathcal{G}^{\prime}\}$ with parameter sharing $\theta_{1}=\theta_{2}$ or not $\theta_{1}\neq\theta_{2}$. To ensure a fair comparison of the performance between GNN+GSL, GNN, and MLP, we consider $5$ GSL bases as input choices and train all models on each GSL bases. Detailed explanations of these GSL modules can be found in Appendix D.1.

**Table 1: Performance of GNNs with GNN+GSL.**
| Model | Construct | Fusion | Param Sharing | Mines. | Roman. | Amazon. | Tolokers | Questions | Squirrel | Chameleon | Actor | Texas | Cornell | Wisconsin | Cora | CiteSeer | PubMed | Rank |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| MLP | None | - | - | 79.55$\pm$1.23 | 65.45$\pm$0.99 | 46.65$\pm$0.83 | 75.94$\pm$1.38 | 74.92$\pm$1.39 | 39.29$\pm$2.22 | 43.57$\pm$4.18 | 35.40$\pm$1.38 | 80.46$\pm$6.44 | 73.78$\pm$7.34 | 85.88$\pm$7.78 | 87.97$\pm$1.80 | 76.68$\pm$2.10 | 87.39$\pm$2.18 | 3.93 |
| GCN | None | - | - | 90.07$\pm$5.79 | 81.46$\pm$1.25 | 50.89$\pm$1.16 | 84.61$\pm$0.99 | 77.68$\pm$1.10 | 41.26$\pm$2.47 | 43.24$\pm$3.86 | 34.34$\pm$1.17 | 73.08$\pm$8.68 | 67.03$\pm$10.54 | 78.24$\pm$8.32 | 87.97$\pm$1.51 | 76.75$\pm$2.30 | 89.47$\pm$0.64 | 1.36 |
| GCN | cos-graph | $\{\mathcal{G}^{\prime}\}$ | - | 77.91$\pm$5.25 | 67.40$\pm$1.02 | 46.72$\pm$1.51 | 76.11$\pm$1.52 | 72.56$\pm$1.14 | 38.15$\pm$2.45 | 39.87$\pm$4.87 | 33.47$\pm$1.61 | 63.06$\pm$9.85 | 65.68$\pm$7.76 | 72.75$\pm$5.70 | 85.21$\pm$1.39 | 75.52$\pm$1.14 | 89.03$\pm$0.42 | 6.71 |
| GCN | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$6.45 | 62.57$\pm$0.81 | 41.29$\pm$1.61 | 74.22$\pm$1.79 | 69.63$\pm$1.52 | 37.62$\pm$1.74 | 39.78$\pm$4.00 | 32.74$\pm$0.92 | 57.88$\pm$8.75 | 66.49$\pm$9.12 | 73.14$\pm$5.92 | 64.68$\pm$1.61 | 67.32$\pm$1.89 | 86.43$\pm$0.76 | 9.32 |
| GCN | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 88.70$\pm$0.86 | 69.90$\pm$2.38 | 47.35$\pm$0.83 | 82.85$\pm$0.95 | 75.29$\pm$1.38 | 38.84$\pm$2.87 | 40.30$\pm$4.31 | 33.73$\pm$1.49 | 65.47$\pm$8.48 | 62.97$\pm$10.89 | 75.29$\pm$6.54 | 85.51$\pm$1.87 | 75.23$\pm$1.14 | 88.74$\pm$0.59 | 4.79 |
| GCN | cos-node | $\{\mathcal{G}^{\prime}\}$ | - | 85.57$\pm$6.63 | 68.24$\pm$2.49 | 47.56$\pm$1.32 | 77.26$\pm$1.44 | 74.16$\pm$1.80 | 38.14$\pm$2.40 | 40.16$\pm$3.13 | 34.04$\pm$1.66 | 61.13$\pm$8.19 | 61.08$\pm$8.16 | 71.18$\pm$6.98 | 86.06$\pm$1.95 | 75.76$\pm$1.39 | 88.92$\pm$0.50 | 5.93 |
| GCN | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$6.45 | 62.57$\pm$0.81 | 41.29$\pm$1.61 | 74.22$\pm$1.79 | 69.63$\pm$1.52 | 37.62$\pm$1.74 | 39.78$\pm$4.00 | 32.74$\pm$0.92 | 57.88$\pm$8.75 | 66.49$\pm$9.12 | 73.14$\pm$5.92 | 64.68$\pm$1.61 | 67.32$\pm$1.89 | 86.43$\pm$0.76 | 9.36 |
| GCN | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 89.17$\pm$0.68 | 72.63$\pm$1.45 | 48.31$\pm$0.96 | 82.91$\pm$0.97 | 75.56$\pm$1.05 | 38.41$\pm$2.32 | 39.94$\pm$4.49 | 34.10$\pm$1.53 | 64.68$\pm$8.85 | 63.24$\pm$9.47 | 73.92$\pm$7.51 | 85.69$\pm$1.73 | 75.49$\pm$1.42 | 88.72$\pm$0.71 | 4.29 |
| GCN | kNN | $\{\mathcal{G}^{\prime}\}$ | - | 82.89$\pm$6.66 | 68.44$\pm$0.83 | 47.13$\pm$1.00 | 78.92$\pm$1.79 | 73.90$\pm$1.73 | 38.15$\pm$2.02 | 40.22$\pm$3.82 | 33.94$\pm$1.24 | 63.03$\pm$8.53 | 61.35$\pm$9.28 | 72.16$\pm$7.41 | 86.08$\pm$1.62 | 75.56$\pm$1.42 | 88.59$\pm$0.58 | 5.93 |
| GCN | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$6.45 | 62.57$\pm$0.81 | 41.29$\pm$1.61 | 74.22$\pm$1.79 | 69.63$\pm$1.52 | 37.62$\pm$1.74 | 39.78$\pm$4.00 | 32.74$\pm$0.92 | 57.88$\pm$8.75 | 66.49$\pm$9.12 | 73.14$\pm$5.92 | 64.68$\pm$1.61 | 67.32$\pm$1.89 | 86.43$\pm$0.76 | 9.39 |
| GCN | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 88.96$\pm$0.73 | 72.44$\pm$1.61 | 47.06$\pm$0.83 | 83.10$\pm$0.80 | 75.61$\pm$1.19 | 37.63$\pm$1.93 | 40.18$\pm$4.76 | 33.84$\pm$1.94 | 63.87$\pm$9.68 | 62.16$\pm$9.77 | 75.49$\pm$7.29 | 85.82$\pm$1.55 | 75.50$\pm$1.30 | 88.54$\pm$0.55 | 5.00 |
| MLP | None | - | - | 79.55$\pm$1.23 | 65.45$\pm$0.99 | 46.65$\pm$0.83 | 75.94$\pm$1.38 | 74.92$\pm$1.39 | 39.29$\pm$2.22 | 43.57$\pm$4.18 | 35.40$\pm$1.38 | 80.46$\pm$6.44 | 73.78$\pm$7.34 | 85.88$\pm$7.78 | 87.97$\pm$1.80 | 76.68$\pm$2.10 | 87.39$\pm$2.18 | 3.71 |
| SGC | None | - | - | 83.45$\pm$4.47 | 78.04$\pm$0.69 | 51.38$\pm$0.68 | 84.88$\pm$1.13 | 77.39$\pm$1.23 | 41.18$\pm$2.73 | 42.35$\pm$4.10 | 34.05$\pm$1.41 | 73.63$\pm$6.94 | 70.27$\pm$9.91 | 80.59$\pm$5.13 | 88.10$\pm$1.89 | 77.52$\pm$2.20 | 89.39$\pm$0.62 | 1.57 |
| SGC | cos-graph | $\{\mathcal{G}^{\prime}\}$ | - | 73.76$\pm$4.46 | 67.17$\pm$0.81 | 47.15$\pm$0.88 | 76.28$\pm$1.63 | 73.93$\pm$2.66 | 38.66$\pm$2.53 | 40.07$\pm$4.39 | 33.87$\pm$1.45 | 71.19$\pm$7.38 | 67.57$\pm$9.19 | 77.65$\pm$6.08 | 86.95$\pm$2.01 | 76.12$\pm$1.29 | 89.10$\pm$0.43 | 5.79 |
| SGC | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$4.89 | 62.97$\pm$0.78 | 42.42$\pm$1.57 | 74.29$\pm$1.79 | 70.56$\pm$1.27 | 37.56$\pm$2.25 | 39.33$\pm$3.60 | 32.85$\pm$0.90 | 57.60$\pm$7.53 | 66.49$\pm$10.37 | 71.57$\pm$4.46 | 64.82$\pm$2.11 | 67.55$\pm$1.80 | 86.58$\pm$0.72 | 9.64 |
| SGC | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 79.70$\pm$1.21 | 62.02$\pm$2.06 | 47.24$\pm$0.93 | 83.22$\pm$1.52 | 77.19$\pm$0.99 | 38.32$\pm$1.80 | 40.85$\pm$4.61 | 33.51$\pm$1.50 | 70.34$\pm$7.31 | 64.86$\pm$9.01 | 75.29$\pm$6.82 | 87.47$\pm$1.70 | 75.70$\pm$1.28 | 88.65$\pm$0.49 | 6.14 |
| SGC | cos-node | $\{\mathcal{G}^{\prime}\}$ | - | 79.03$\pm$3.76 | 67.84$\pm$1.87 | 47.93$\pm$0.94 | 78.09$\pm$1.84 | 75.46$\pm$1.43 | 38.61$\pm$2.20 | 40.50$\pm$4.10 | 34.03$\pm$1.27 | 70.08$\pm$6.84 | 68.11$\pm$9.23 | 77.45$\pm$4.63 | 87.47$\pm$1.86 | 76.36$\pm$1.27 | 89.37$\pm$0.41 | 4.54 |
| SGC | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$4.89 | 62.97$\pm$0.78 | 42.42$\pm$1.57 | 74.29$\pm$1.79 | 70.56$\pm$1.27 | 37.56$\pm$2.25 | 39.33$\pm$3.60 | 32.85$\pm$0.90 | 57.60$\pm$7.53 | 66.49$\pm$10.37 | 71.57$\pm$4.46 | 64.82$\pm$2.11 | 67.55$\pm$1.80 | 86.58$\pm$0.72 | 9.57 |
| SGC | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 80.12$\pm$1.36 | 66.90$\pm$1.66 | 48.04$\pm$0.97 | 83.53$\pm$1.43 | 77.11$\pm$1.09 | 38.52$\pm$2.29 | 40.20$\pm$4.66 | 34.20$\pm$1.79 | 68.47$\pm$8.11 | 64.59$\pm$9.74 | 75.29$\pm$6.05 | 87.54$\pm$1.63 | 75.88$\pm$1.26 | 88.68$\pm$0.43 | 5.11 |
| SGC | kNN | $\{\mathcal{G}^{\prime}\}$ | - | 75.53$\pm$4.98 | 67.94$\pm$0.70 | 47.68$\pm$0.84 | 79.45$\pm$2.06 | 74.22$\pm$2.47 | 37.32$\pm$2.10 | 39.92$\pm$3.91 | 34.05$\pm$1.55 | 72.81$\pm$6.15 | 70.00$\pm$7.98 | 77.84$\pm$6.02 | 87.82$\pm$1.77 | 76.54$\pm$1.44 | 89.19$\pm$0.42 | 4.64 |
| SGC | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 52.53$\pm$4.89 | 62.97$\pm$0.78 | 42.42$\pm$1.57 | 74.29$\pm$1.79 | 70.56$\pm$1.27 | 37.56$\pm$2.25 | 39.33$\pm$3.60 | 32.85$\pm$0.90 | 57.60$\pm$7.53 | 66.49$\pm$10.37 | 71.57$\pm$4.46 | 64.82$\pm$2.11 | 67.55$\pm$1.80 | 86.58$\pm$0.72 | 9.50 |
| SGC | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 80.78$\pm$1.08 | 64.59$\pm$1.93 | 47.48$\pm$0.99 | 83.17$\pm$1.43 | 76.80$\pm$1.09 | 36.53$\pm$2.06 | 40.17$\pm$4.24 | 34.23$\pm$1.72 | 69.26$\pm$6.77 | 65.95$\pm$8.87 | 76.08$\pm$5.92 | 87.38$\pm$1.49 | 76.02$\pm$1.22 | 88.77$\pm$0.45 | 5.79 |
| MLP | None | - | - | 79.55$\pm$1.23 | 65.45$\pm$0.99 | 46.65$\pm$0.83 | 75.94$\pm$1.38 | 74.92$\pm$1.39 | 39.29$\pm$2.22 | 43.57$\pm$4.18 | 35.40$\pm$1.38 | 80.46$\pm$6.44 | 73.78$\pm$7.34 | 85.88$\pm$7.78 | 87.97$\pm$1.80 | 76.68$\pm$2.10 | 87.39$\pm$2.18 | 4.14 |
| SAGE | None | - | - | 90.66$\pm$0.88 | 85.02$\pm$0.97 | 52.93$\pm$0.83 | 83.31$\pm$1.12 | 75.95$\pm$1.41 | 40.43$\pm$2.64 | 42.95$\pm$5.37 | 34.83$\pm$1.20 | 80.17$\pm$6.90 | 75.68$\pm$7.52 | 86.27$\pm$6.67 | 88.13$\pm$1.77 | 76.65$\pm$2.00 | 89.18$\pm$0.65 | 1.71 |
| SAGE | cos-graph | $\{\mathcal{G}^{\prime}\}$ | - | 80.39$\pm$4.66 | 70.13$\pm$1.05 | 47.55$\pm$1.17 | 76.77$\pm$1.28 | 72.86$\pm$1.18 | 39.03$\pm$2.69 | 40.84$\pm$5.42 | 34.75$\pm$1.39 | 70.91$\pm$8.58 | 70.00$\pm$7.56 | 78.24$\pm$6.87 | 83.64$\pm$2.03 | 75.53$\pm$1.36 | 89.18$\pm$0.35 | 6.07 |
| SAGE | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.02$\pm$6.49 | 59.98$\pm$1.73 | 39.99$\pm$2.29 | 71.57$\pm$2.28 | 66.01$\pm$3.58 | 35.05$\pm$2.41 | 38.49$\pm$3.68 | 31.32$\pm$1.04 | 60.30$\pm$7.05 | 67.57$\pm$4.59 | 76.47$\pm$5.92 | 64.58$\pm$1.74 | 67.77$\pm$1.31 | 85.53$\pm$0.51 | 9.93 |
| SAGE | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 90.67$\pm$0.66 | 79.02$\pm$1.21 | 52.10$\pm$0.84 | 82.17$\pm$0.89 | 75.38$\pm$0.96 | 39.36$\pm$2.14 | 40.64$\pm$6.06 | 35.14$\pm$1.08 | 76.08$\pm$6.30 | 70.27$\pm$6.62 | 79.41$\pm$5.71 | 83.60$\pm$1.78 | 74.39$\pm$1.35 | 88.88$\pm$0.50 | 3.86 |
| SAGE | cos-node | $\{\mathcal{G}^{\prime}\}$ | - | 85.26$\pm$4.64 | 71.25$\pm$1.76 | 48.96$\pm$0.87 | 78.39$\pm$1.75 | 73.01$\pm$1.11 | 38.68$\pm$2.75 | 40.81$\pm$4.51 | 35.10$\pm$1.26 | 71.47$\pm$9.47 | 68.11$\pm$7.87 | 75.49$\pm$6.32 | 84.88$\pm$1.90 | 75.58$\pm$1.04 | 89.17$\pm$0.35 | 5.64 |
| SAGE | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.02$\pm$6.49 | 59.98$\pm$1.73 | 39.99$\pm$2.29 | 71.59$\pm$2.28 | 66.01$\pm$3.58 | 35.05$\pm$2.41 | 38.49$\pm$3.68 | 31.32$\pm$1.04 | 60.30$\pm$7.05 | 67.57$\pm$4.59 | 76.47$\pm$5.92 | 64.58$\pm$1.74 | 67.77$\pm$1.31 | 85.53$\pm$0.51 | 9.79 |
| SAGE | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 90.64$\pm$0.65 | 78.60$\pm$0.98 | 52.08$\pm$0.90 | 82.02$\pm$0.88 | 75.31$\pm$1.12 | 39.18$\pm$2.54 | 40.86$\pm$6.17 | 35.18$\pm$1.24 | 74.71$\pm$5.65 | 69.73$\pm$7.43 | 80.00$\pm$5.68 | 83.96$\pm$1.65 | 74.63$\pm$1.26 | 88.93$\pm$0.64 | 3.93 |
| SAGE | kNN | $\{\mathcal{G}^{\prime}\}$ | - | 82.86$\pm$3.14 | 70.74$\pm$0.80 | 48.40$\pm$1.01 | 78.12$\pm$2.17 | 72.70$\pm$1.15 | 38.93$\pm$2.84 | 39.68$\pm$5.40 | 35.09$\pm$1.14 | 70.91$\pm$9.05 | 68.92$\pm$6.88 | 75.69$\pm$6.73 | 84.40$\pm$1.75 | 75.68$\pm$1.43 | 88.86$\pm$0.44 | 6.50 |
| SAGE | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.02$\pm$6.49 | 59.98$\pm$1.73 | 39.99$\pm$2.29 | 71.59$\pm$2.28 | 66.01$\pm$3.58 | 35.05$\pm$2.41 | 38.49$\pm$3.68 | 31.32$\pm$1.04 | 60.30$\pm$7.05 | 67.57$\pm$4.59 | 76.47$\pm$5.92 | 64.58$\pm$1.74 | 67.77$\pm$1.31 | 85.53$\pm$0.51 | 9.86 |
| SAGE | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 90.61$\pm$0.63 | 79.16$\pm$1.15 | 51.56$\pm$1.07 | 81.66$\pm$0.87 | 75.22$\pm$0.97 | 39.20$\pm$2.39 | 40.44$\pm$5.82 | 35.13$\pm$1.38 | 74.17$\pm$6.31 | 70.54$\pm$7.32 | 79.61$\pm$6.61 | 84.05$\pm$1.63 | 74.59$\pm$1.25 | 88.67$\pm$0.55 | 4.57 |
| MLP | None | - | - | 79.55$\pm$1.23 | 65.45$\pm$0.99 | 46.65$\pm$0.83 | 75.94$\pm$1.38 | 74.92$\pm$1.39 | 39.29$\pm$2.22 | 43.57$\pm$4.18 | 35.40$\pm$1.38 | 80.46$\pm$6.44 | 73.78$\pm$7.34 | 85.88$\pm$7.78 | 87.97$\pm$1.80 | 76.68$\pm$2.10 | 87.39$\pm$2.18 | 3.86 |
| GAT | None | - | - | 90.41$\pm$1.34 | 84.51$\pm$0.84 | 52.00$\pm$2.84 | 84.37$\pm$0.96 | 77.78$\pm$1.27 | 41.67$\pm$2.51 | 43.83$\pm$3.66 | 33.73$\pm$1.77 | 75.28$\pm$8.12 | 65.41$\pm$12.14 | 77.84$\pm$7.41 | 88.02$\pm$1.92 | 76.77$\pm$2.02 | 89.21$\pm$0.67 | 2.04 |
| GAT | cos-graph | $\{\mathcal{G}^{\prime}\}$ | - | 80.78$\pm$8.24 | 67.68$\pm$1.25 | 45.79$\pm$1.10 | 74.84$\pm$1.84 | 72.34$\pm$1.49 | 38.74$\pm$2.54 | 40.21$\pm$3.53 | 33.37$\pm$1.10 | 62.73$\pm$9.06 | 67.57$\pm$7.03 | 77.06$\pm$7.29 | 86.03$\pm$1.85 | 75.46$\pm$1.49 | 88.63$\pm$0.59 | 6.29 |
| GAT | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.16$\pm$7.93 | 63.67$\pm$1.08 | 44.83$\pm$2.04 | 73.46$\pm$1.07 | 68.92$\pm$1.53 | 37.14$\pm$2.13 | 39.85$\pm$2.87 | 32.06$\pm$1.12 | 57.03$\pm$8.70 | 67.30$\pm$4.67 | 75.10$\pm$5.85 | 64.84$\pm$1.45 | 67.82$\pm$0.62 | 86.47$\pm$0.66 | 9.46 |
| GAT | cos-graph | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 89.97$\pm$0.80 | 76.08$\pm$1.70 | 49.61$\pm$0.73 | 82.75$\pm$0.90 | 77.13$\pm$1.20 | 39.21$\pm$2.81 | 40.40$\pm$3.30 | 33.05$\pm$1.20 | 70.66$\pm$7.77 | 66.76$\pm$7.23 | 78.82$\pm$6.76 | 86.60$\pm$1.75 | 75.05$\pm$1.36 | 87.85$\pm$0.72 | 4.71 |
| GAT | cos-node | $\{\mathcal{G}^{\prime}\}$ | - | 87.64$\pm$8.40 | 68.80$\pm$2.39 | 46.37$\pm$1.06 | 77.77$\pm$1.86 | 73.65$\pm$1.47 | 38.65$\pm$2.46 | 40.33$\pm$3.25 | 33.43$\pm$0.94 | 64.64$\pm$9.09 | 65.41$\pm$8.48 | 75.10$\pm$6.13 | 87.08$\pm$1.66 | 75.59$\pm$1.49 | 88.59$\pm$0.49 | 5.82 |
| GAT | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.16$\pm$7.93 | 63.67$\pm$1.08 | 44.83$\pm$2.04 | 73.46$\pm$1.07 | 68.92$\pm$1.53 | 37.14$\pm$2.13 | 39.85$\pm$2.87 | 32.06$\pm$1.12 | 57.03$\pm$8.70 | 67.30$\pm$4.67 | 75.10$\pm$5.85 | 64.84$\pm$1.45 | 67.82$\pm$0.62 | 86.47$\pm$0.66 | 9.46 |
| GAT | cos-node | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 90.03$\pm$0.78 | 77.56$\pm$2.75 | 50.36$\pm$0.70 | 82.72$\pm$1.16 | 76.83$\pm$1.16 | 38.97$\pm$3.12 | 40.56$\pm$3.77 | 33.49$\pm$1.35 | 70.39$\pm$7.34 | 65.95$\pm$6.77 | 78.63$\pm$6.59 | 86.64$\pm$1.78 | 75.32$\pm$1.04 | 87.87$\pm$0.61 | 4.21 |
| GAT | kNN | $\{\mathcal{G}^{\prime}\}$ | - | 84.27$\pm$5.25 | 68.73$\pm$1.47 | 46.05$\pm$0.90 | 77.57$\pm$1.75 | 71.58$\pm$1.62 | 38.82$\pm$2.33 | 40.12$\pm$3.69 | 33.84$\pm$1.07 | 61.68$\pm$8.71 | 62.97$\pm$7.43 | 74.90$\pm$5.86 | 86.77$\pm$1.90 | 75.64$\pm$1.45 | 88.29$\pm$0.48 | 6.50 |
| GAT | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}=\theta_{2}$ | 53.16$\pm$7.93 | 63.67$\pm$1.08 | 44.83$\pm$2.04 | 73.46$\pm$1.07 | 68.92$\pm$1.53 | 37.14$\pm$2.13 | 39.85$\pm$2.87 | 32.06$\pm$1.12 | 57.03$\pm$8.70 | 67.30$\pm$4.67 | 75.10$\pm$5.85 | 64.84$\pm$1.45 | 67.82$\pm$0.62 | 86.47$\pm$0.66 | 9.46 |
| GAT | kNN | $\{\mathcal{G},\mathcal{G}^{\prime}\}$ | $\theta_{1}\neq\theta_{2}$ | 89.96$\pm$0.79 | 77.23$\pm$1.63 | 49.79$\pm$0.72 | 82.78$\pm$0.95 | 76.67$\pm$1.13 | 39.65$\pm$2.76 | 41.11$\pm$3.92 | 33.54$\pm$1.36 | 70.38$\pm$7.22 | 65.95$\pm$6.52 | 77.84$\pm$7.23 | 86.97$\pm$1.75 | 75.20$\pm$1.55 | 87.97$\pm$0.51 | 4.18 |

Table 1 shows the performance of MLP, GNN baselines, and GNN+GSL across $8$ datasets, using the best-performing GSL bases. For each GNN backbone, the best-performing method is highlighted in red, while the second-best method is highlighted in blue. Notably, under fair comparison conditions, all $4$ baseline GNNs outperform their GNN+GSL counterparts. This suggests that incorporating GSL into these GNN baselines does not consistently yield performance improvements and leads to worse results in many instances. However, these results alone are insufficient to conclusively determine the effectiveness of GSL, as the method may require specific training procedures or more complex model designs. Therefore, we further examine the performance of state-of-the-art (SOTA) GSL approaches to more fairly evaluate GSL’s potential within GNNs.

SOTA-GSL. To fairly reassess the impact of GSL in state-of-the-art (SOTA) methods, we compare the performance of SOTA models with their SOTA-GSL counterparts within the same hyperparameter search space. Corresponding to the analysis of GCN and MLP in Section 4.1, the SOTA-GSL methods include two variants: (1) SOTA, $\mathcal{G}^{\prime}=\mathcal{G}$, which replaces the GSL graph $\mathcal{G}^{\prime}$ with the original graph $\mathcal{G}$; and (2) SOTA, $\mathcal{G}^{\prime}=\text{MLP}$, which substitutes the graph convolution layers of GSL $\mathcal{G}^{\prime}$ with MLP layers. The results are presented in Table 2, where ”OOM” denotes out-of-memory. It is evident that removing GSL does not diminish model performance; in fact, it is often comparable to or even exceeds the original results. Furthermore, GSL-based SOTA methods require significantly more GPU memory and longer running times compared to their non-GSL counterparts. Based on these findings, we conclude that GSL not only fails to enhance performance across most datasets but also increases model complexity. In conjunction with the results in Table 1, we assert that GSL is unnecessary for effective GNN design in most cases.

**Table 2: Model Performance and training time per epoch of SOTA methods and SOTA-GSL. The results for methods marked with “*” are reported in Zhiyao et al. ().**
|  | Questions | Minesweeper | Roman-empire | Amazon-ratings | Tolokers | Cora | Pubmed | Citeseer |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Model | AUC | Time | AUC | Time | Acc | Time | Acc | Time | AUC | Time | Acc | Time | Acc | Time | Acc | Time |
| GAug* | OOM | - | 77.93$\pm$0.64 | - | 52.74$\pm$0.48 | - | 48.42$\pm$0.39 | - | OOM | - | 82.48$\pm$0.66 | 7s | 78.73$\pm$0.77 | 20s | 71.66$\pm$1.14 | 10s |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | OOM | - | 80.56$\pm$0.36 | 11s | OOM | - | 48.45$\pm$0.37 | 12s | OOM | - | 81.73$\pm$0.38 | 1s | 79.17$\pm$0.23 | 6s | 72.34$\pm$0.18 | 2s |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | OOM | - | 64.31$\pm$1.40 | 4.8s | OOM | - | 48.05$\pm$0.66 | 37s | OOM | - | 78.90$\pm$0.00 | 3.2s | 77.40$\pm$0.00 | 8.1s | 72.40$\pm$0.00 | 9s |
| GEN* | OOM | - | 79.56$\pm$1.09 | 260s | OOM | - | 49.17$\pm$0.68 | - | 77.25$\pm$0.25 | - | 81.66$\pm$0.91 | 214s | 80.40$\pm$1.85 | 1384s | 73.21$\pm$0.62 | 470s |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | OOM | - | 80.81$\pm$0.23 | 75s | OOM | - | 50.08$\pm$0.30 | 130s | OOM | - | 82.16$\pm$0.37 | 39s | 80.49$\pm$0.13 | 114s | 71.52$\pm$0.34 | 25s |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | OOM | - | 71.81$\pm$0.98 | 12s | OOM | - | 49.29$\pm$0.65 | 49s | OOM | - | 80.20$\pm$0.00 | 140s | 66.80$\pm$0.00 | 1592s | 73.50$\pm$0.00 | 310s |
| GRCN* | 74.50$\pm$0.84 | - | 72.57$\pm$0.49 | 60s | 44.31$\pm$0.34 | 180s | 50.13$\pm$0.31 | 220s | 71.27$\pm$0.42 | 37s | 83.82$\pm$0.25 | 13s | 78.84$\pm$0.32 | 17s | 72.45$\pm$0.70 | 20s |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 75.69$\pm$0.52 | 8s | 71.15$\pm$0.05 | 10s | 45.84$\pm$0.52 | 8s | 46.07$\pm$1.02 | 10s | 71.73$\pm$0.42 | 10s | 81.66$\pm$1.10 | 2s | 79.12$\pm$0.26 | 3s | 69.55$\pm$1.28 | 2s |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 63.59$\pm$2.35 | 3.9s | 72.18$\pm$1.09 | 2s | 45.89$\pm$0.83 | 7.5s | 48.77$\pm$0.60 | 8.1s | 70.45$\pm$1.39 | 8s | 79.40$\pm$0.00 | 1.3s | 78.10$\pm$0.00 | 5s | 71.40$\pm$0.00 | 4.2s |
| IDGL* | OOM | - | 50.00$\pm$0.00 | 157s | 44.38$\pm$0.75 | 186s | 45.87$\pm$0.58 | - | 50.00$\pm$0.00 | 279s | 84.40$\pm$0.49 | 123s | 76.63$\pm$1.55 | 146s | 72.88$\pm$0.59 | 332s |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | OOM | - | 50.00$\pm$0.00 | 51s | 41.24$\pm$0.86 | 42s | OOM | - | 50.00$\pm$0.00 | 52s | 82.43$\pm$0.45 | 13s | 73.50$\pm$1.85 | 23s | 73.13$\pm$0.49 | 36s |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | OOM | - | 79.56$\pm$1.26 | 13.7s | 50.35$\pm$0.36 | 35s | 39.93$\pm$0.88 | 15s | 71.55$\pm$1.08 | 11s | 83.20$\pm$0.00 | 6.6s | 79.20$\pm$0.00 | 13s | 72.60$\pm$0.00 | 13.9s |
| NodeFormer* | OOM | - | 77.29$\pm$1.71 | - | 56.54$\pm$3.73 | - | 41.33$\pm$1.25 | - | OOM | - | 78.81$\pm$1.21 | 213s | 78.38$\pm$1.94 | - | 70.39$\pm$2.04 | 219s |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | OOM | - | 80.66$\pm$0.82 | 215s | 68.37$\pm$1.95 | 236s | OOM | - | OOM | - | 77.01$\pm$1.99 | 152s | OOM | - | 70.82$\pm$0.13 | 139s |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | OOM | - | 80.04$\pm$1.42 | 21s | 53.08$\pm$2.37 | 7.2s | 71.55$\pm$1.08 | 26s | OOM | - | 78.82$\pm$0.00 | 8s | 76.30$\pm$0.00 | 127s | 72.80$\pm$0.00 | 15s |
| GloGNN | 68.67$\pm$1.07 | 66.6s | 52.45$\pm$0.30 | 13.0s | 66.21$\pm$0.17 | 26.1s | 50.72$\pm$0.88 | 31.1s | 79.81$\pm$0.20 | 47.4s | 78.07$\pm$1.66 | 6.6s | 87.88$\pm$0.26 | 18.2s | 71.95$\pm$1.90 | 21.8s |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 68.32$\pm$1.23 | 49.4s | 52.30$\pm$0.21 | 3.6s | 66.03$\pm$0.14 | 15.3s | 50.23$\pm$0.83 | 21.7s | 80.02$\pm$0.16 | 25.1s | 73.49$\pm$2.01 | 5.1s | 87.62$\pm$0.20 | 14.4s | 72.27$\pm$2.08 | 21.2s |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 69.69$\pm$0.22 | 25.7s | 52.30$\pm$0.20 | 2.1s | 66.49$\pm$0.16 | 12.4s | 49.56$\pm$0.73 | 12.3s | 74.85$\pm$0.12 | 2.8s | 73.93$\pm$1.81 | 3.2s | 87.64$\pm$0.27 | 10.2s | 72.09$\pm$1.81 | 13.8s |
| WRGAT | OOM | - | 90.22$\pm$0.64 | 168.0s | OOM | - | OOM | - | 78.69$\pm$1.21 | 153.0s | 84.28$\pm$1.52 | 19.5s | 88.82$\pm$0.50 | 421.6s | 73.50$\pm$1.41 | 22.1s |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 74.67$\pm$0.95 | 64.1s | 89.79$\pm$0.37 | 18.6s | OOM | - | 50.41$\pm$0.53 | 49.9s | 78.81$\pm$0.89 | 47.0s | 83.48$\pm$1.48 | 3.4s | 88.92$\pm$0.43 | 26.5s | 73.22$\pm$1.90 | 4.7s |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 68.07$\pm$2.62 | 75.8s | 87.08$\pm$2.11 | 16.2s | OOM | - | 41.38$\pm$1.46 | 24.4s | 76.41$\pm$1.25 | 37.7s | 76.99$\pm$1.10 | 2.9s | 80.27$\pm$6.23 | 23.9s | 65.28$\pm$2.11 | 4.5s |
| WRGCN | 74.70$\pm$1.71 | 358.3s | 90.63$\pm$0.64 | 40.9s | OOM | - | 52.76$\pm$0.95 | 508.4s | 82.68$\pm$0.82 | 52.3s | 88.30$\pm$1.46 | 23.7s | OOM | - | 73.74$\pm$1.60 | 54.2s |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 75.91$\pm$1.30 | 43.3s | 90.65$\pm$0.49 | 5.5s | OOM | - | 52.54$\pm$0.56 | 50.1s | 82.65$\pm$0.86 | 15.6s | 88.32$\pm$0.79 | 3.9s | 89.26$\pm$0.45 | 19.4s | 74.45$\pm$1.51 | 10.5s |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 64.59$\pm$1.48 | 23.1s | 70.66$\pm$1.37 | 7.7s | OOM | - | 37.05$\pm$0.46 | 8.0s | 69.10$\pm$0.91 | 12.2s | 70.00$\pm$3.59 | 2.2s | 67.29$\pm$2.49 | 9.9s | 70.84$\pm$1.36 | 4.1s |

### 5.2 Quality of GSL Graphs

Previous studies (Li et al., ; Zheng et al., ) suggest that GSL constructs graphs with properties that improve intra-class node connectivity, which can be measured by homophily. This improvement can be visualized by inspecting graph structures with nodes sorted by their class labels. A graph that appears closer to a block diagonal matrix indicates stronger intra-class connectivity. However, this enhancement may not always be essential and can be achieved through non-GSL methods as well. In Figure 4, we visualize the original and reconstructed structures of a heterophilous graph from the Wisconsin dataset. The GSL graphs are constructed using various bases: $\mathbf{X}$, $\mathbf{\hat{A}}\mathbf{X}$, $\text{MLP}(\mathbf{X})$, $\text{GCN}(\mathbf{X},\mathbf{A})$, and $\text{GCL}(\mathbf{X},\mathbf{A})$. We also include reconstructed graphs using a simple method that samples edges between nodes of the same class based on label predictions, i.e., $\mathbf{\hat{Y}}=\text{GCN}(\mathbf{X},\mathbf{A})$ or $\mathbf{\hat{Y}}=\text{MLP}(\mathbf{X},\mathbf{A})$. Figure 4 demonstrates that, although GSL improves intra-class connectivity, the improvement is not as substantial as that achieved by non-GSL methods, as seen in the last two subfigures. Thus, the improvement in homophily within GSL graphs is unnecessary, as it can be easily achieved through simple methods.

Figure: (a)
Refer to caption: x5.png

### 5.3 GSL Components

Since the performance of GNN and GNN+GSL models is comparable under the same GSL bases, as shown in Table 1, we further investigate how different types of GSL bases influence GNNs. As illustrated in Figure 5, the original node features are not always the optimal input for GCN and MLP, which explains why prior comparisons of GNNs are unfair. Pretrained node representations, such as $\text{MLP}(\mathbf{X})$ and $\text{GCN}(\mathbf{X},\mathbf{A})$, significantly enhance model performance on several datasets, including Texas, Cornell, and Wisconsin. This improvement stems from self-training, a key component in many GSL approaches. As a result, incorporating self-training methods may be more advantageous for future GNN designs compared to GSL. For more results and analysis of GSL modules, please refer to Appendix E.

Figure: (a)
Refer to caption: x13.png

## 6 Conclusion

In this paper, we revisit the role of Graph Structure Learning (GSL) in Graph Neural Networks (GNNs) with our proposed GSL framework. Motivated by the controversy of GSL, we demonstrate that graph convolution over GSL-constructed graphs does not improve mutual information, as confirmed by both empirical observations and theoretical analysis. By either adding GSL to baseline GNNs or removing it from state-of-the-art (SOTA) methods, we find that GSL does not enhance GNN performance when evaluated under the same GSL bases and hyperparameter tuning. These results suggest that the improvements attributed to GSL may stem from components other than GSL. Our findings contribute to a better understanding of GSL and offer insights into re-evaluating the essential components in future GNN design.

## Appendix A Taxonomy of Graph Structure Learning Methods

We present several representative GSL-based GNNs within our proposed GSL framework in Table 3. Below, we provide a detailed description of each method.

**Table 3: Representative GSL methods under our proposed GSL framework**
| Method | Bases | Construct | Refinement | View Fusion | Training Mode |
| --- | --- | --- | --- | --- | --- |
| LDS (Franceschi et al., ) | $\bm{X}$ | $\{\mathcal{E}^{\prime}=kNN(\bm{B})\}$ +Opt. | Bernoulli($\mathcal{E}^{\prime}$) | Late Fusion, $\{\mathcal{G}^{\prime}_{1},\mathcal{G}^{\prime}_{2},\dots,\mathcal{G}^{\prime}<br>_{m}\}$,<br>$\theta_{1}=\theta_{2}$ | 2-stage |
| Geom-GCN (Pei et al., ) | Isomap/Poincare/<br>$\text{Struc2vec}(\bm{X},\bm{A})$ | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\left|\bm{B}_{i}-\bm{B}_{j}\right|\}$ | $\text{threshold}(\mathcal{E}^{\prime})$ | Late Fusion, $\{\mathcal{G},\mathcal{G}^{\prime}\}$,<br>$\theta_{1}\neq\theta_{2}$ | Static |
| ProGNN (Jin et al., ) | $\bm{\epsilon}$ | $\{\mathcal{E}^{\prime}=\text{Opt}(\bm{\epsilon})\}$ | Low Rank+Sparsity<br>+Original | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Joint |
| IDGL (Chen et al., ) | MLP($\bm{X}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\text{cos}(\bm{B}_{i}$,$\bm{B}_{j})\}$ | topk($\mathcal{E}^{\prime}$) | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Joint |
| GRCN (Yu et al., ) | GCN($\bm{X}$,$\bm{A}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\sigma(\bm{B}_{i}\bm{B}_{j}^{T})\}$ | topk($\mathcal{E}^{\prime}$), sym($\mathcal{E}^{\prime}$) | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Joint |
| GAug-M (Zhao et al., ) | $\text{GCN}^{(2)}$($\bm{X}$,$\bm{A}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\sigma(\bm{B}_{i}\bm{B}_{j}^{T})\}$ | $\mathcal{G}^{\prime}_{+}=\text{topk}(\mathcal{E}^{\prime})$,<br>$\mathcal{G}^{\prime}_{-}=\text{bottom}(\mathcal{E}^{\prime})$ | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}_{+}-\mathcal{G}^{\prime}_{-}\}$ | Joint |
| GAug-O (Zhao et al., ) | $\bm{X}$ | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=p(e_{ij}|\text{GAE}(\bm{B},\bm{A}))\}$ | Gumbel($\mathcal{E}^{\prime}$) | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Joint |
| SLAPS (Fatemi et al., ) | $\text{MLP}(\bm{X})$ | $\{\mathcal{E}^{\prime}=kNN(\bm{B})\}$ | norm($\mathcal{E}^{\prime}$),sym($\mathcal{E}^{\prime}$) | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Joint |
| CoGSL (Liu et al., ) | $\text{GCN}(\bm{X},\{\bm{A},\text{kNN}(\bm{X}),$<br>$\text{PPR}(\bm{X}),\text{Subgraph}(\bm{X})\})$ | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=p(e_{ij}|\text{MLP}(\bm{B},\bm{A}))\}$ | - | Early Fusion, $\{\mathcal{G}^{*}|\min{\mathcal{L}_{\text{CL}}(\mathcal{G},\mathcal{G}^{\prime<br>})}\}$,<br>$\theta_{1}\neq\theta_{2}$ | 2-stage |
| GEN (Wang et al., ) | $\text{GCN}(\bm{X},\bm{A})$ | $\{\mathcal{E}^{\prime}=kNN(\bm{B})\}$ | - | Late Fusion, $\{\mathcal{G}^{\prime}_{1},\mathcal{G}^{\prime}_{2},\dots,\mathcal{G}^{\prime}<br>_{m}\}$ ,<br>$\theta_{1}\neq\theta_{2}$ | 2-stage |
| STABLE (Li et al., ) | $\text{GCL}(\bm{X},\bm{A})$ | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\text{cos}(\bm{B}_{i}$,$\bm{B}_{j})$<br>or $\text{cos}(\bm{B}_{i}$,$\bm{B}_{j})\}$ | $\mathcal{G}^{\prime}_{+}=\text{topk}(\mathcal{E}^{\prime})$,<br>$\mathcal{G}^{\prime}_{-}=\text{threshod}(\mathcal{E}^{\prime})$ | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}_{+}-\mathcal{G}^{\prime}_{-}\}$ | Joint |
| SEGSL (Zou et al., ) | $\bm{X}$ | $\{\mathcal{E}^{\prime}|\min{\mathcal{H}_{S}},$<br>$e_{ij}^{\prime}\in\text{EncTree}(\text{kNN}(\bm{B}))\}$ | - | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Joint |
| SUBLIME (Liu et al., ) | $\text{GCN}(\bm{X},\bm{A})$ | $\{\mathcal{E}^{\prime}=\text{Opt}(\bm{\epsilon})\}$ or<br>$\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\text{cos}/\text{Minkowski}(\bm{B}_{i}$,$\bm{B}_{j})\}$ | topk($\mathcal{E}^{\prime}$),sym($\mathcal{E}^{\prime}$),norm($\mathcal{E}^{\prime}$) | Separation, $\{\mathcal{G},\mathcal{G}^{\prime}\}$,<br>$\theta_{1}=\theta_{2}$ | Joint |
| BM-GCN (He et al., ) | $\hat{\bm{Y}}=\text{MLP}(\bm{X})$,<br>$\min\mathcal{L}_{\text{CE}}(\hat{\bm{Y}},\bm{Y})$ | $\{\mathcal{E}^{\prime}=\bm{BQB}^{T}\}$ | norm($\mathcal{E}^{\prime}$) | Early Fusion, $\{\mathcal{G}\odot\mathcal{G}^{\prime}\}$ | Joint |
| WSGNN (Lao et al., ) | MLP($\bm{X}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=cos(\bm{B}_{i},\bm{B}_{j})\}$ | - | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Joint |
| GLCN (Jiang et al., ) | $\bm{X}$ | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\phi(\left|\bm{B}_{i}-\bm{B}_{j}\right|)\}$ | norm($\mathcal{E}^{\prime}$), Original<br>+Sparsity+Smoothness | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Joint |
| ASC (Li et al., ) | SpectralCluster($\bm{X}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\left\lVert\bm{B}_{i}-\bm{B}_{j}\right\rVert\}$ | $\text{topk}(\mathcal{E}^{\prime})$ | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Static |
| WRGAT (Suresh et al., ) | GCN($\bm{X}$, $\bm{A}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}\cdot Opt(\bm{B})\}$ | Sparsity + MultiHop | Early Fusion $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Static |
| HOG-GCN (Wang et al., ) | GCN($\bm{X}$, $\bm{A}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\sigma(\bm{B_{i}}\bm{B_{j}}^{T})\}$ | Sparsity + Smoothness | No Fusion $\{\mathcal{G}^{\prime}\}$ | Joint |
| GGCN (Yan et al., ) | MLP($\bm{X}$) | $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\text{cos}(\bm{B_{i}},\bm{B_{j}})\}$ | Low Rank + Sparsity | Early Fusion, $\{\mathcal{G}+\mathcal{G}^{\prime}\}$ | Joint |
| GloGNN (Li et al., ) | $\text{MLP}(\bm{X})$ | $\{\mathcal{E}^{\prime}=\text{Opt}(\bm{B})\}$ | Sparsity+MultiHop | No Fusion, $\{\mathcal{G}^{\prime}\}$ | Joint |
| HiGNN (Zheng et al., ) | $\hat{\bm{Y}}=\text{GCN}(\bm{X},\bm{A})$,<br>$\min\mathcal{L}_{CE}(\hat{\bm{Y}},\bm{Y})$ | $\{\mathcal{E}^{\prime}=e_{ij}^{\prime}=\text{cos}(\bm{B_{i}},\bm{B_{j}}))\}$ | topk($\mathcal{E}^{\prime}$), sym($\mathcal{E}^{\prime}$) | Late Fusion, $\{\mathcal{G},\mathcal{G}^{\prime}\}$, $\theta_{1}\neq\theta_{2}$ | Static |

LDS (Franceschi et al., ). The GSL bases in LDS is constructed as node features $\bm{X}$ and the GSL graph $\mathcal{G}^{\prime}$ is initialized using a k-Nearest-Neighbors algorithm based on $\bm{B}$. Then, $\mathcal{G}^{\prime}$ is updated with a loss function of node classification. Then multiple graphs are sampled based on $\mathcal{G}^{\prime}$ with a Bernoulli function and used to update the model parameters. The $\mathcal{G}^{\prime}$ construction and model parameters are updated as a 2-stage mode.

Geom-GCN (Pei et al., ). Geom-GCN constructs the GSL bases from several graph-aware node embedding strategies using both of the $\bm{X}$ and $\bm{A}$: Isomap , Poincare , and struc2vec . Then, new graphs are constructed by filtering node pairs with a higher similarity measured by Euclidean distance $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\left|\bm{B}_{i}-\bm{B}_{j}\right|<\delta\}$ where $\delta$ is a threshold. Finally, both of the aggregated message from $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are fused after applying graph convolution layers with no parameter sharing. The $\mathcal{G}^{\prime}$ is not updated through the training process.

ProGNN (Jin et al., ). The $\mathcal{G}^{\prime}$ in ProGNN is purely learned by optimization without GSL bases. It optimizes the $\mathcal{G}^{\prime}$ using low rank, sparsity, and similarity with the original graphs $\mathcal{G}$. It outputs a single graph $\mathcal{G}^{\prime}$ without fusion and updates the $\mathcal{G}^{\prime}$ together with model parameters.

IDGL (Chen et al., ). The GSL bases in LDS is constructed by linear transformation of node features $\text{MLP}(\bm{X})$. Then, a GSL graph $\mathcal{G}^{\prime}$ is constructed using cosine similarity with topk threshold refinement. The early fusion is applied by fusing GSL graph $\mathcal{G}^{\prime}$ with original graph $\mathcal{G}$ before training. The GSL graph $\mathcal{G}^{\prime}$ is trained with model parameters jointly.

GRCN (Yu et al., ). GRCN constructs GSL bases by node embeddings of graph convolution $\text{GCN}(\bm{X},\bm{A})$. Then, the GSL graph $\mathcal{G}^{\prime}$ is constructed by a kernel function with topk and symmetrization refinement $\{\mathcal{E}^{\prime}|e_{ij}^{\prime}=\sigma(\bm{B}_{i}\bm{B}_{j})>\delta\}$. The final graph is obtained by early fusion and the GSL graph $\mathcal{G}^{\prime}$ is updated together with model parameters.

GAug-M and GAug-O (Zhao et al., ). GAug-M constructs GSL bases using a 2-layer graph convolution $\text{GCN}^{(2)}(\bm{X},\bm{A})$. Then, the GSL graph $\mathcal{G}^{\prime}$ is constructed by a kernel function. The final graph is obtained by adding some edges with highest probabilities and removing some edges with lowest probabilities on $\mathcal{G}$. GAug-O selects node features as GSL bases $\bm{X}$, then trains a Graph Auto-Encoder to predict edges as $\mathcal{G}^{\prime}$. Then, after gumbel sampling, the GSL graph $\mathcal{G}^{\prime}$ is fused with original graph $\mathcal{G}$ before training. The $\mathcal{G}^{\prime}$ in both of the GAug-M and GAug-O is updated together with model parameters.

SLAPS (Fatemi et al., ). SLAPS constructs the GSL bases by applying MLP(X) followed by a k-nearest neighbors (kNN) algorithm based on node feature similarities. The GSL graph $\mathcal{G}^{\prime}$ is then processed by an adjacency processor that symmetrizes and normalizes the adjacency matrix to ensure non-negativity and symmetry. The final graph is obtained of the generated graph $\mathcal{G}^{\prime}$ with the node features without fusion. Additionally, a self-supervised denoising autoencoder $L_{DAE}=L(X_{i},GNN_{DAE}(\hat{X}_{i};\theta_{GNN_{DAE}}))$ is introduced to address the supervision starvation problem, updating $\mathcal{G}^{\prime}$ together with the model parameters.

CoGSL (Liu et al., ). CoGSL constructs GSL bases using two views, one of them is the Origin graph. Another is selected from the Adjacency matrix $A$, Diffusion matrix $PPR(X)$, the KNN graph $KNN(X)$ and the Subgraph of the Origin. GCNs are applied to these views to obtain node embeddings. The GSL graph is constructed by applying a linear transformation to the node embeddings of each node pair to estimate the connection probability between them. This connection probability is then added to the original view to finalize the graph. The refinement $\mathcal{E}^{\prime}|e_{ij}^{\prime}=p(e_{ij}|\text{MLP}(\mathbf{B},\mathbf{A}))$ step involves maximizing the mutual information between the two selected views and the newly constructed graph. InfoNCE loss is used to optimize the connection probability, where the same node serves as a positive sample, and different nodes serve as negative samples. The final graph $\mathcal{G}^{\prime}$ is obtained via early fusion of the selected views, and the GSL graph is updated with model parameters.

GEN (Wang et al., ). GEN constructs the GSL bases by generating kNN graphs though several GCN layer, utilizing node representations from different layers. These kNN graphs are then combined using a Stochastic Block Model (SBM) to create a new graph $\mathcal{G}^{\prime}$. The GSL graph $\mathcal{G}^{\prime}$ is refined iteratively through Bayesian inference to maximize posterior probabilities $P(G,\alpha,\beta|O,Z,Y_{l})=\frac{P(O|G,\alpha,\beta)P(G,\alpha,\beta)P(O,Z,Y_
{l})}{P(O,Z,Y_{l})}$, considering both the original graph and node embeddings. The final graph is obtained by feeding the graph $Q$ back into the GCN for further optimization. The iterative process updates both the GSL graph and GCN parameters as a 2-stage mode, providing mutual reinforcement between the graph estimation and model learning.

STABLE (Li et al., ). STABLE constructs the GSL bases by generating augmentations based on node similarity through kNN graph and perturbing edges to simulate adversarial attacks. The GSL graph $\mathcal{G}^{\prime}$ is constructed by refining the structure using contrastive learning between positive samples (slightly perturbed graphs) and negative samples (undesirable views generated by feature shuffling). The refinement step applies a top-k filtering strategy on the node similarity matrix to retain helpful edges while removing adversarial ones. The final graph is obtained through early fusion, and the GSL graph $\mathcal{G}^{\prime}$ is updated together with model parameters during joint training

SE-GSL (Zou et al., ). SE-GSL constructs the GSL bases using a kNN graph fused with the original graph. The GSL graph $\mathcal{G}^{\prime}$ is constructed through a structural entropy minimization process that extracts hierarchical community structures in the form of an encoding tree. The final graph is optimized by sampling node pairs from the encoding tree and generating new edges based on the minimized entropy structure. The refined graph is then used for downstream tasks, and the GSL graph $\mathcal{G}^{\prime}$ is updated jointly with model parameters during training.

SUBLIME (Liu et al., ). SUBLIME constructs the GSL bases using both an anchor view (original graph) and a learner view (new graph). The new graph is initialized through kNN and further optimized either by parameter-based methods (using models like MLP, GCN, or GAT) or by non-parameter-based approaches (using cosine similarity or Minkowski distance). After obtaining the new graph, post-processing operations such as top-k filtering, symmetrization, and degree-based regularization are applied to ensure the graph’s sparsity and structure. The GSL graph $\mathcal{G}^{\prime}$ is refined by applying contrastive learning between the anchor and learner views, incorporating edge drop and feature masking to generate node embeddings. The final graph is used in downstream tasks, and both views are updated together with model parameters in a joint training process.

BM-GCN (He et al., ). BM-GCN constructs the GSL bases by introducing soft labels for nodes enbedding $\mathbf{B}=softmax(\sigma(MLP(X)))$ via a multilayer perceptron $\mathcal{L}_{MLP}=\sum_{v_{i}\in\mathcal{V}}f(B_{i},Y_{i})$. These soft labels are then used to compute a block matrix (H) , which models the connection probabilities between different node classes. The GSL graph $\mathcal{G}^{\prime}$ is constructed by creating a block similarity matrix $Q=HH^{T}$ from the block matrix $Y_{s}={Y_{i},B_{i}|\forall v_{i}\in\mathcal{T}_{y},\forall v_{j}\notin\mathcal
{T}_{y}},H=(Y_{s}^{T}AY_{s})\circ(Y_{s}^{T}AE)$, reflecting similarities between classes. The new graph is optimized using $BQB^{T}$ and further fused with the original graph $A+\beta I$ for downstream tasks. The final graph is obtained by optimizing $\mathcal{G}^{\prime}$ through degree-based regularization and top-k filtering. The GSL graph $\mathcal{G}^{\prime}$ is updated together with model parameters during joint training.

WSGNN (Lao et al., ). WSGNN introduces a two-branch graph structure learning method, where each branch operates on different aspects of the graph: Branch AZ learns node labels from the new graph structure, while Branch ZA learns the new graph structure from the labels. The GSL bases is constructed using the observed graph $A_{obs}$ and node features $X$. The new graph $A^{\prime}$ is inferred via cosine similarity between node embeddings. After constructing two separate views from each branch, the final graph is obtained by averaging the graphs from both branches. The refinement process ensures sparsity through cosine-based edge calculation $\mathcal{E}^{\prime}|e_{ij}^{\prime}=cos(\mathbf{B}_{i},\mathbf{B}_{j})$. Finally, both views undergo early fusion, with graph structure and node labels optimized jointly using a composite loss function that includes ELBO for structure prediction and cross-entropy loss for label prediction. The final GSL graph $\mathcal{G}^{\prime}$ is updated during joint training.

GLCN (Jiang et al., ). GLCN constructs the GSL bases by computing pairwise distances between node features and passing them through an MLP to obtain a block similarity score. This score is then processed with a softmax function to generate an $n\times n$ probability matrix that serves as the learned graph structure. The graph is refined using regularization techniques to ensure sparsity and feature smoothness $L_{GL}=\sum_{i,j=1}^{n}||x_{i}-x_{j}||_{2}^{2}S_{ij}+\gamma||S||_{F}^{2}+\beta
||S-A||_{F}^{2}$. The learned graph is then used for downstream graph tasks, where the task loss and the graph regularization loss are jointly optimized during joint training

ASC (Li et al., ). ASC constructs the GSL bases is formed by using pseudo-eigenvectors from spectral clustering. They divide the Laplacian spectrum into slices, with each slice corresponding to an embedding matrix. The GSL graph $\mathcal{G}^{\prime}$ is constructed by adaptive spectral clustering, where pseudo-eigenvectors are weighted based on alignment with node labels Where $f^{\mathcal{Z}}_{i}$. For refinement, they apply top-K edge selection by minimizing node embedding distance and maximizing homophily $\underset{\mathcal{Z}}{\text{argmin}}\sum_{i,j\in V_{Y}}(d(f^{Z}_{i},f^{Z}_{j}
),1(y_{i},y_{j}))$. This final restructured graph is training without fusion. Finally, the GSL graph is updated together with the model parameters.

WRGAT (Suresh et al., ). WRGAT constructs the GSL bases using the node features and a weighted relational GNN (WRGNN) framework that fuses structural and proximity information. A multi-relational graph is built by assigning different types of edges based on the structural equivalence of nodes at various neighborhood levels. This framework adapts to both assortative and disassortative mixing patterns, which helps improve node classification tasks. The GSL graph $\mathcal{G}^{\prime}$ is refined through attention-based message passing across these relational edges, and early fusion of proximity and structural features is used. The GSL graph $\mathcal{G}^{\prime}$ is trained jointly with the model parameters to optimize the node classification task.

HOG-GCN (Wang et al., ). HOG-GCN constructs the GSL bases by incorporating both topological information and node attributes to estimate a homophily degree matrix $S=BB^{T},B=softmax(Z_{m}),Z_{m}^{(l)}=\sigma(Z_{m}^{(l-1)W_{m}^{(l)}})$. The GSL graph $\mathcal{G}^{\prime}$ is constructed using a homophily-guided propagation mechanism, which adapts the feature propagation weights between neighborhoods based on the homophily degree matrix $Z^{(l)}=\sigma(\mu Z^{(l-1)}W_{e}^{(l)}+\xi\hat{D}^{(-1)}A_{k}\odot HZ^{(l-1)}
W^{(l)}_{n})$. For refinement, the graph incorporates both k-order structures and class-aware information to model the homophily and heterophily relationships between nodes. The final graph is obtained through joint fusion of topological and attribute-based homophily degrees, and both graph structure and model parameters are updated during joint training.

GGCN (Yan et al., ). GGCN constructs the GSL bases using node features and structural properties such as node-level homophily $h_{i}$ and relative degree $\bar{r_{i}}$. It incorporates structure-based edge correction by learning new edge weights derived from structural properties like node degree, and feature-based edge correction by learning signed edge weights from node features, allowing for positive and negative influences between neighbors. The GSL graph $\mathcal{G}^{\prime}$ is constructed by combining signed and unsigned edge information, aiming to capture both homophily and heterophily. The refinement process uses edge correction and decaying aggregation to mitigate oversmoothing and heterophily problems. The final graph is updated with early fusion, and the GSL graph $\mathcal{G}^{\prime}$ is optimized during joint training

GloGNN (Li et al., ). GloGNN constructs its GSL bases using node embeddings derived from MLP, combining both low-pass and high-pass convolutional filters. A coefficient matrix $Z^{(l)}$ is used to characterize the relationship between nodes and is optimized to capture both feature and structural similarities $H_{X}^{(0)}=(1-\alpha)H_{X}^{(0)}+\alpha H_{A}^{(0)}$. Refinement is achieved via top-k selection based on the multi-hop adjacency matrix, and the matrix is symmetrized. The final graph is obtained through global aggregation of nodes, capturing both local and distant homophilous nodes. This graph is then used in downstream tasks, where the GSL graph $\mathcal{G}^{\prime}$ is jointly optimized with the model parameters.

HiGNN (Zheng et al., ). HiGNN constructs its GSL bases by utilizing heterophilous information as node neighbor distributions, which represent the likelihood of neighboring nodes belonging to different classes $\mathcal{H}_{u}=[p_{1},p_{2},...,p_{c}],where\ p_{i}=\frac{|{v|v\in\mathcal{N}
_{u},y_{v}=i}|}{|\mathcal{N}_{u}|}$. A new graph structure $\mathcal{G}^{\prime}$ is constructed by linking nodes with similar heterophilous distributions using cosine similarity. The refinement involves selecting top-k edges based on the similarity score and applying symmetrization. The final graph is fused with the original adjacency matrix $A$ and the newly constructed adjacency matrix $A^{\prime}$ via late fusion during message passing, where the node embeddings from both $A$ and $A^{\prime}$ are combined with a balance parameter $\lambda$. The graph $\mathcal{G}^{\prime}$ and node embeddings are updated during static training.

## Appendix B Proof of Theorem

- Theorem1.
Given a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ with node labels $\mathbf{Y}$ and node features $\mathbf{X}$, the accuracy of graph convolution in node classification is upper bounded by the mutual information between the node label $Y$ and the aggregated node features $H$:
$P_{A}\leq\frac{I(Y;H)+\log 2}{\log(C)}$
(5)

Proof. For an arbitrary node $u$, the aggregated node features can be derived as $H_{u}=\frac{1}{|\mathcal{N}_{u}|}\sum_{v\in\mathcal{N}_{u}}X_{v}$ following the graph convolution operation. For a classifier predicting labels based on $H_{u}$, we have $\hat{Y}_{u}=\text{cls}(H_{u})$. Consequently, the Markov chain $Y\to H\to\hat{Y}$ holds. By applying Fano’s inequality , we obtain

$$ $H(Y|H)\leq H_{b}(P_{E})+P_{E}\log(C-1)$ (6) $$

where $P_{E}$ represents the error rate and $H_{b}(\cdot)$ is the binary entropy function. Rearranging this inequality gives us a lower bound on $P_{E}$:

$$ $P_{E}\geq\frac{H(Y|H)-H_{b}(P_{E})}{\log(C-1)}$ (7) $$

Since $H(Y|H)=H(Y)-I(Y;H)=\log(C)-I(Y;H)$ and $H_{b}(P_{E})\leq\log 2$, we can substitute these terms into the equation:

$$ $P_{E}\geq 1-\frac{I(Y;H)+\log 2}{\log(C)}$ (8) $$

Finally, by expressing the accuracy rate $P_{A}$, we find:

$$ $P_{A}=1-P_{E}\leq\frac{I(Y;H)+\log 2}{\log(C)}$ (9) $$

This concludes the proof of Theorem 1.

- Theorem2.
Given a new graph $\mathcal{G}^{\prime}=\{\mathcal{V},\mathcal{E}^{\prime}\}$ constructed by a non-parametric graph structure learning method on bases $B$, the mutual information $I(Y;B^{\prime})$ between node label $Y$ and aggregated bases $B^{\prime}_{u}=\frac{1}{\left|\mathcal{N}_{u}\right|}\sum_{v\in\mathcal{N}_{u}
}B_{v}$ is upper bounded by $I(Y;B)$.

Proof. For node in class $k$, we can get its GSL bases $B_{k}$ using node features $X_{k}$ and topological information $\mathcal{N}_{k}$ (if possible), which follows a class-wised distribution $B_{u}\sim p_{B}(y)$. Then, for a non-parametric GSL method, we have the probability that class $k$ connects with class $j$ as:

$$ $p_{k,j}=\frac{g(B_{k},B_{j})}{\sum_{i\in\mathcal{N}_{k}}g(B_{k},B_{i})}$ (10) $$

where $g(\cdot)$ is a non-parametric measurement of the probability of new connections, such as cosine similarity or Minkowski Distance. Then, we can get an aggregated bases from the new graph by the operation of graph convolution (Ma et al., ; Luan et al., ):

$$ $B_{k}^{\prime}=\sum_{j=1}^{C}p_{k,j}B_{j}$ (11) $$

Therefore, the Markow chain $Y\to B\to B^{\prime}$ holds. From data processing inequality (Beaudry & Renner, ), we have

$$ $I(Y;B^{\prime})\leq I(Y,B)$ (12) $$

This concludes the proof of Theorem 2.

## Appendix C Dataset Details

The datasets used in our experiments include heterophilous graphs: Squirrel, Chameleon, Actor, Texas, Cornell, and Wisconsin (Pei et al., ; Rozemberczki et al., ), homophilous graphs: Cora, PubMed, and Citeseer (Yang et al., ), and Minesweeper, Roman-empire, Amazon-ratings, Tolokers, and Questions (Platonov et al., ). The dataset statistics are shown in 4. The descriptions of all the datasets are given below:

**Table 4: Dataset Statistics**
| Dataset | #Nodes | #Edges | #Classes | #Features | Edge Homophily |
| --- | --- | --- | --- | --- | --- |
| Cora | 2,708 | 5,278 | 7 | 1,433 | 0.81 |
| Pubmed | 19,717 | 44,324 | 3 | 500 | 0.80 |
| Citeseer | 3,327 | 4,552 | 6 | 3,703 | 0.74 |
| Roman-empire | 22,662 | 32,927 | 18 | 300 | 0.05 |
| Amazon-ratings | 24,492 | 93,050 | 5 | 300 | 0.38 |
| Minesweeper | 10,000 | 39,402 | 2 | 7 | 0.68 |
| Tolokers | 11,758 | 529,000 | 2 | 10 | 0.59 |
| Questions | 48,921 | 153,540 | 2 | 301 | 0.84 |
| Cornell | 183 | 295 | 5 | 1,703 | 0.30 |
| Chameleon | 2,277 | 36,101 | 5 | 2,325 | 0.23 |
| Wisconsin | 251 | 466 | 5 | 1,703 | 0.21 |
| Texas | 183 | 309 | 5 | 1,703 | 0.11 |
| Squirrel | 5,201 | 216,933 | 5 | 2,089 | 0.22 |
| Actor | 7,600 | 33,544 | 5 | 931 | 0.22 |

Cora, Citeseer, and Pubmed datasets are widely used citation networks in graph structure learning research. In each dataset, nodes represent academic papers, while edges capture citation relationships between them. The node features are bag-of-words vectors derived from the paper’s content, and each node is assigned a label based on its research topic. These datasets offer a structured framework to evaluate GNN models on classification tasks within citation networks.

Roman-Empire is constructed from the Roman Empire Wikipedia article, with nodes representing words and edges formed by either word adjacency or dependency relations. It contains 22.7K nodes and 32.9K edges. The task is to classify words by their syntactic roles, and node features are fastText embeddings. The graph is chain-like, with an average degree of 2.9 and a large diameter of 6824. Adjusted homophily is low ($h_{adj}$ = -0.05), making it useful for GNN evaluation under low homophily and sparse connectivity.

Amazon-Ratings is based on Amazon’s product co-purchasing network, this dataset includes nodes as products (books, CDs, DVDs, etc.) and edges linking frequently co-purchased items. It consists of the largest connected component of the graph’s 5-core. The goal is to predict product ratings grouped into five classes.

Minesweeper is a synthetic dataset resembling the Minesweeper game, nodes in a 100x100 grid represent cells, with edges connecting adjacent cells. The task is to identify mines (20% of nodes). Node features indicate neighboring mine counts, with 50% of features missing. The average degree is 7.88, and the graph has near-zero homophily due to random mine placement.

Tolokers is derived from the Toloka crowdsourcing platform, where nodes represent workers connected by shared tasks. The graph has 11.8K nodes and an average degree of 88.28. The task is to predict which workers have been banned, using profile and task performance features. The graph is much denser than others in the benchmark.

Questions is based on user interactions from Yandex Q, this dataset focuses on users interested in medicine. Nodes are users, and edges represent questions answered between users. It contains 48.9K nodes with an average degree of 6.28. The task is to predict user activity at the end of a one-year period, with fastText embeddings from user descriptions as features. The graph is highly imbalanced (97% active users).

Texas, Wisconsin, Cornell are part of the WebKB project, representing web pages from university computer science departments. Nodes correspond to web pages, and edges represent hyperlinks between them. The node features are bag-of-words vectors from the web page content, and the labels classify each page into one of five categories: student, project, course, staff, and faculty.

Chameleon, Squirrel are page-page networks based on specific topics from Wikipedia. Nodes represent web pages, and edges correspond to mutual links between them. Node features are derived from the page content, and the classification task is based on average monthly traffic. These datasets are characterized by high heterophily, making them challenging for traditional GNN models.

Actor is an induced subgraph from a film-director-actor-writer network. Nodes represent actors, and edges are created when two actors co-occur on the same Wikipedia page. The task is to classify actors into five categories based on the keywords associated with their Wikipedia pages.

## Appendix D Implementation Details

All the experiments are conducted on a linux server(Operation system: Ubuntu 16.04.7 LTS) with one NVIDIA Tesla V100 card.

### D.1 GNN+GSL

We implement GSL on $4$ baseline GNNs with a variety of GSL approaches from the perspective of GSL bases, GSL graph construction, and view fusion. The baseline GNNs include:

- •
GCN (Kipf & Welling, ) performs layer-wise propagation of node features and aggregates information from neighboring nodes to capture local graph structures. Each layer applies a convolution operation to update node embeddings, combining the node’s features with its neighbors.
- •
GAT (Velicković et al., ) employs self-attention to learn dynamic attention coefficients between nodes and their neighbors. These coefficients are normalized using softmax, and the final node representation is computed as a weighted sum of the neighbor features. Multi-head attention is used to enhance stability and expressiveness, with the number of attention heads set to $8$ by default in our experiments.
- •
SAGE (Hamilton et al., ) uses an inductive framework to aggregate features from a node’s local neighborhood, allowing it to generalize to unseen nodes. The aggregation function, set to mean in our experiments, efficiently combines neighbor information at each layer.
- •
SGC (Wu et al., ) simplifies the GCN model by removing non-linear activations and collapsing multiple layers into a single linear transformation. This reduction in complexity accelerates training. Node features are propagated using precomputed matrices, making the model faster and more efficient. In our experiments, the number of k-hops in SGC is set to 2 by default.

The GSL bases $\bm{B}$ includes the following options:

- •
$\bm{B}=\bm{X}$: The original node features are used as the GSL bases.
- •
$\bm{B}=\bm{\hat{A}X}$: Aggregated node features from 1-hop neighbors, normalized by node degree, are used as the GSL bases.
- •
$\bm{B}=\text{MLP}(\bm{X})$: Pretrained MLP embeddings are used as the GSL bases. A 2-layer MLP is trained using node features and labels on the training set for 1000 epochs per run. The hidden layer size is set to 128, the learning rate to $1e^{-2}$, the dropout rate to 0.5, and the weight decay to $5e^{-4}$. All parameters are optimized with Adam. After training, node embeddings are extracted from the last hidden layer, with a dimension of 128, prior to classifier input.
- •
$\bm{B}=\text{GCN}(\bm{X},\bm{A})$: Pretrained node embeddings are obtained from a 2-layer GCN model, following the same training procedure as for the MLP embeddings.
- •
$\bm{B}=\text{GCL}(\bm{X},\bm{A})$: Pretrained node embeddings are derived from a Graph Contrastive Learning (GCL) model without supervision, following the same training process as the MLP embeddings. GRACE (Zhu et al., ) is used as the GCL model, with 2 views and 2 layers. The edge and feature dropout rates in each view are set to 0.2.

The approaches for the construction of GSL graph $\mathcal{G}^{\prime}$ includes:

- •
Cos-graph: $\mathcal{G}^{\prime}=\{e_{ij}|\text{cos}(\bm{B_{i}},\bm{B_{j}})>\delta,i\in
\mathcal{V},j\in\mathcal{V}\}$. This method calculates the cosine similarity between all node pairs in the original graph $\mathcal{G}$. Node pairs with a similarity higher than the threshold $\delta$ are selected as the edge set for the GSL graph $\mathcal{G}^{\prime}$.
- •
Cos-node: $\mathcal{G}^{\prime}=\bigcup_{i\in\mathcal{V}}\{\{e_{i}j\}|\text{cos}(\bm{B_{i
}},\bm{B_{j}})>\delta_{i},j\in\mathcal{N}_{i}\}$. Unlike Cos-graph, which operates at the graph level, Cos-node constructs $\mathcal{G}^{\prime}$ at the node level. To prevent nodes from being left without neighbors (which may occur in Cos-graph), Cos-node selects neighbors based on node-level cosine similarity, ensuring each node has sufficient connections.
- •
kNN: $\mathcal{G}^{\prime}=\text{kNN}(\bm{B})$. This method constructs a kNN graph using the k-Nearest Neighbors algorithm based on the GSL bases $\bm{B}$.

The view fusion in GSL includes:

- •
$\{\mathcal{G}^{\prime}\}$: This approach uses only the GSL graph $\mathcal{G}^{\prime}$ for subsequent GNN training, completely ignoring the original graph $\mathcal{G}$.
- •
$\{\mathcal{G},\mathcal{G}^{\prime}\},\theta_{1}=\theta_{2}$. Both the GSL graph $\mathcal{G}^{\prime}$ and the original graph $\mathcal{G}$ are used for GNN training, with parameter sharing across each layer of the GNN.
- •
$\{\mathcal{G},\mathcal{G}^{\prime}\},\theta_{1}\neq\theta_{2}$. Both the GSL graph $\mathcal{G}^{\prime}$ and the original graph $\mathcal{G}$ are used for GNN training, but with separate model parameters for each graph.

Especially, for graphs with two views, the fusion stage in GSL includes:

- •
Early Fusion: $\mathcal{G}+\mathcal{G}^{\prime}$.Combine the two graphs, $\mathcal{G}$ and $\mathcal{G}^{\prime}$, into a single new graph prior to GNN training.
- •
Late Fusion: $\bm{H}+\bm{H}^{\prime}$. After training the GNN on the original graph $\mathcal{G}$ and the GSL graph $\mathcal{G}^{\prime}$, merge the node embeddings, $\mathbf{H}$ and $\mathbf{H}^{\prime}$, before passing them to the classifiers.

In addition to the original models based on $4$ baseline GNNs, we implement GNN+GSL (GSL-augmented GNNs) by combining the aforementioned GSL modules, resulting in multiple variants for each type of GNN. For all models, we explore hyperparameters including hidden dimensions from the set $\{64,128,256\}$, learning rates from {1e-2, 1e-3, 1e-4}, weight decay values from {0, 1e-5, 1e-3}, the number of layers from $\{2,3\}$, and dropout rates from $\{0.2,0.4,0.6,0.8\}$.

For GSL graph generation, we also search for additional hyperparameters to ensure the performance quality of the GSL-augmented GNN. Specifically, for Cos-graph and Cos-node, we control the parameter $\delta$ to vary the ratio of the number of edges in $\mathcal{G}^{\prime}$ to the number of edges in $\mathcal{G}$ across the set $\{0.1,0.5,1,5\}$. For kNN, we investigate the number of neighbors from the set $\{2,3,5,10\}$..

### D.2 SOTA-GSL

To fairly re-evaluate the effectiveness of GSL in state-of-the-art (SOTA) models, two methods are employed to compare performance within the same search space. The first method (SOTA, $\mathcal{G}^{\prime}=\mathcal{G}$) replaces the GSL graph with the original graph. The second method (SOTA, $\mathcal{G}^{\prime}=\text{MLP}$) substitutes the GSL graph with a linear transformation, connecting it to the subsequent model structures and ensuring the continuity of channels within the original network structure. We train each model for 1000 epochs and search the hidden dimensions from the set {16, 32, 64, 128, 256, 512}, learning rate from {1e-1, 1e-2, 1e-3, 1e-4, 1e-5}, weight decay values from {5e-4, 5e-5, 5e-6, 5e-7, 0}, the number of layers from {1, 2, 3}, and dropout rates from {0.2, 0.4, 0.6, 0.8}. The model-specific hyperparameters are shown as follows:

In GRCN, the hyperparameter K determines the number of nearest neighbors used to create a sparse graph from a dense similarity graph which helps balance efficiency and accuracy.We set the k as 5.

In GAug, the alpha is a hyperparameter that regulates the influence of the edge predictor on the original graph. We set the alpha as 0.1.

In IDGL, The parameter graph_learn_num_pers defines the number of perspectives for evaluating node similarities in the graph learning process. The parameter num_anchors specifies the number of anchor points used to reduce computational complexity and improve scalability in graph structure learning. The graph_skip_conn parameter controls the proportion of skip connections, preserving information from the original graph during new graph structure learning. The update_adj_ratio parameter determines the proportion of the adjacency matrix updated at each iteration, influencing the dynamic adjustment of the graph structure. We set the graph_learn_num_pers as 6, num_anchors as 500, graph_skip_conn as 0.7, and update_adj_ratio as 0.3.

In NodeFormer, The parameter k determines the number of neighbors considered for each node in constructing the local graph structure, influencing the strength of node connections and the propagation of features. The parameter tolerance controls the degree of error tolerance during optimization. A larger tolerance allows more flexibility in the search space near local optima, while a smaller one results in stricter convergence. The number of attention heads in a graph attention network (GAT). Multi-head attention enables the model to focus on different subspace representations simultaneously, enhancing the diversity and stability of the representations. We set the k as 10, lambda as 0.01, and n_heads as 4.

In GEN,the parameter K in KNN refers to the number of nearest neighbors used to construct the graph structure, determining how many adjacent nodes are selected. The parameter tolerance defines the acceptable range of error during optimization, controlling the convergence criteria of the model. The parameter threshold determines the edge weight threshold in the graph, deciding which edges to retain in the graph structure.We set the k as 10, tolerance as 0.01, and threshold as 0.5.

In GloGNN, we set the Delta as 0.9, Gamma as 0.8, alpha as 0.5, beta as 2000, and orders as 5. Delta adjusts the balance between local and global node embeddings. Gamma controls the significance of global aggregation versus local information. Alpha balances the contributions of node features and graph structure. Beta regularizes the model, preventing overfitting. Order defines how many layers of neighbors are considered.

In WRGAT, we set the number of attention heads as 2 and the negative slope as 0.2. The number of attention heads determines how many attention mechanisms are used. The negative slope modifies the LeakyReLU activation.

The tables below show the best combination of hyperparameters based on the accuracy of test set.

**Table 5: Hyperparameters for SOTA-GSL on Cora.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Cora | GAug | 1e-4 | 5e-7 | 0.8 | 512 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-4 | 5e-7 | 0.8 | 512 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-4 | 5e-7 | 0.8 | 512 | 2 |  |
| GEN | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GRCN | 1e-3 | 5e-3 | 0.5 | 256 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-3 | 0.5 | 256 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-3 | 0.5 | 256 | 2 |  |
| IDGL | 1e-2 | 5e-4 | 0.5 | 512 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 512 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 512 | 2 |  |
| NodeFormer | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| GloGNN | 1e-2 | 5e-5 | 0.5 | 64 | 1 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 64 | 1 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 64 | 1 |  |
| WRGAT | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |
| WRGCN | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |

**Table 6: Hyperparameters for SOTA-GSL on PubMed.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| PubMed | GAug | 1e-2 | 5e-4 | 0.5 | 128 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 128 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 128 | 2 |  |
| GEN | 1e-3 | 5e-4 | 0.2 | 32 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-4 | 0.2 | 32 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-4 | 0.2 | 32 | 2 |  |
| GRCN | 1e-3 | 5e-3 | 0.5 | 32 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-3 | 0.5 | 32 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-3 | 0.5 | 32 | 2 |  |
| IDGL | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| NodeFormer | 1e-3 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-4 | 0.2 | 32 | 2 |  |
| GloGNN | 1e-3 | 5e-5 | 0.7 | 64 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-5 | 0.7 | 64 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-5 | 0.7 | 64 | 3 |  |
| WRGAT | 1e-2 | 5e-5 | 0.5 | 64 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 1e-5 | 0.5 | 64 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 64 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.5 | 64 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 64 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 64 | 2 |  |

**Table 7: Hyperparameters for SOTA-GSL on Citeseer.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Citeseer | GAug | 1e-4 | 5e-7 | 0.8 | 512 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-4 | 5e-7 | 0.8 | 512 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-4 | 5e-7 | 0.8 | 512 | 2 |  |
| GEN | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 16 | 2 |  |
| GRCN | 1e-3 | 5e-3 | 0.8 | 512 | 3 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-3 | 0.8 | 512 | 3 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-3 | 0.5 | 256 | 3 |  |
| IDGL | 1e-2 | 5e-4 | 0.5 | 32 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-4 | 0.5 | 16 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-4 | 0.5 | 16 | 2 |  |
| NodeFormer | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| GloGNN | 1e-2 | 1e-5 | 0.7 | 64 | 2 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 1e-5 | 0.7 | 64 | 2 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.7 | 64 | 2 |  |
| WRGAT | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.3 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.5 | 128 | 1 |  |

**Table 8: Hyperparameters for SOTA-GSL on Minesweeper.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Minesweeper | GAug | 1e-3 | 5e-6 | 0.8 | 256 | 3 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-6 | 0.8 | 256 | 3 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-6 | 0.8 | 256 | 3 |  |
| GEN | 1e-4 | 5e-6 | 0.8 | 256 | 3 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-4 | 5e-6 | 0.8 | 256 | 3 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-4 | 5e-6 | 0.8 | 256 | 3 |  |
| GRCN | 1e-3 | 5e-7 | 0.2 | 128 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-6 | 0.2 | 128 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-6 | 0.2 | 128 | 2 |  |
| IDGL | 1e-1 | 5e-6 | 0.2 | 128 | 3 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-1 | 5e-6 | 0.2 | 128 | 3 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-1 | 5e-6 | 0.2 | 128 | 3 |  |
| NodeFormer | 1e-2 | 5e-4 | 0.8 | 32 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.8 | 32 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.8 | 32 | 2 |  |
| GloGNN | 1e-2 | 5e-4 | 0.5 | 512 | 5 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 512 | 5 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 512 | 5 |  |
| WRGAT | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |

**Table 9: Hyperparameters for SOTA-GSL on Roman-Empire.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Roman-empire | GAug | 1e-1 | 5e-5 | 0.5 | 32 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-1 | 5e-5 | 0.5 | 32 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-1 | 5e-5 | 0.5 | 32 | 2 |  |
| GEN | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GRCN | 1e-3 | 5e-5 | 0.5 | 128 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| IDGL | 1e-1 | 5e-5 | 0.5 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-1 | 5e-5 | 0.5 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-1 | 5e-5 | 0.5 | 128 | 2 |  |
| NodeFormer | 1e-3 | 5e-6 | 0.2 | 128 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-3 | 5e-6 | 0.2 | 128 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-3 | 5e-5 | 0.8 | 128 | 3 |  |
| GloGNN | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| WRGAT | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |

**Table 10: Hyperparameters for SOTA-GSL on Amazon-ratings.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Amazon-ratings | GAug | 1e-2 | 5e-7 | 0.2 | 128 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GEN | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| GRCN | 1e-3 | 5e-7 | 0.2 | 128 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 64 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| IDGL | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| NodeFormer | 1e-4 | 5e-5 | 0.5 | 128 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-4 | 5e-5 | 0.5 | 64 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-4 | 5e-5 | 0.5 | 64 | 3 |  |
| GloGNN | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| WRGAT | 1e-2 | 5e-5 | 0.3 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 1e-5 | 0.3 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.3 | 128 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 1e-5 | 0.7 | 128 | 3 |  |

**Table 11: Hyperparameters for SOTA-GSL on Questions.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Questions | GAug | 1e-2 | 5e-4 | 0.5 | 64 | 3 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 64 | 3 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 64 | 3 |  |
| GEN | 1e-2 | 5e-7 | 0.2 | 256 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 256 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 256 | 2 |  |
| GRCN | 1e-2 | 5e-6 | 0.5 | 64 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-6 | 0.5 | 64 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-6 | 0.5 | 64 | 2 |  |
| IDGL | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-7 | 0.2 | 128 | 2 |  |
| NodeFormer | 1e-4 | 5e-3 | 0.5 | 128 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-4 | 5e-3 | 0.5 | 64 | 3 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-4 | 5e-3 | 0.5 | 64 | 3 |  |
| GloGNN | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.7 | 128 | 3 |  |
| WRGAT | 5e-3 | 5e-5 | 0.3 | 64 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 5e-3 | 1e-5 | 0.3 | 64 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 5e-3 | 5e-5 | 0.3 | 64 | 2 |  |
| WRGCN | 5e-3 | 5e-5 | 0.7 | 64 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 5e-3 | 5e-5 | 0.7 | 64 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 5e-3 | 1e-5 | 0.7 | 64 | 2 |  |

**Table 12: Hyperparameters for SOTA-GSL on Tolokers.**
| Dataset | Model | Learning Rate | Weight Decay | Dropout | Hidden Dim | Num of Layers |
| --- | --- | --- | --- | --- | --- | --- |
| Tolokers | GAug | 1e-1 | 5e-5 | 0.5 | 32 | 2 |
| GAug, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-1 | 5e-5 | 0.5 | 32 | 2 |  |
| GAug, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-1 | 5e-5 | 0.5 | 32 | 2 |  |
| GEN | 1e-2 | 5e-5 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-6 | 0.2 | 128 | 2 |  |
| GEN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-6 | 0.2 | 128 | 2 |  |
| GRCN | 1e-2 | 5e-5 | 0.5 | 32 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-6 | 0.5 | 32 | 2 |  |
| GRCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-1 | 5e-6 | 0.5 | 64 | 2 |  |
| IDGL | 1e-2 | 5e-4 | 0.5 | 64 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.5 | 64 | 2 |  |
| IDGL, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.5 | 64 | 2 |  |
| NodeFormer | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| NodeFormer, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-4 | 0.2 | 64 | 2 |  |
| GloGNN | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| GloGNN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.3 | 128 | 3 |  |
| WRGAT | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 1e-5 | 0.5 | 128 | 2 |  |
| WRGAT, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN | 1e-2 | 5e-5 | 0.5 | 128 | 1 |  |
| WRGCN, $\mathcal{G}^{\prime}=\mathcal{G}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |
| WRGCN, $\mathcal{G}^{\prime}=\text{MLP}$ | 1e-2 | 5e-5 | 0.5 | 128 | 2 |  |

## Appendix E Additional Experiment Results

In this section, we examine the impact of different GSL modules on GNN models. The GSL modules include graph bases, GSL graph generation, view fusion methods, and fusion stages, with details provided in Appendix D.1.

### E.1 GSL Bases

In addition to the analysis of the impact of GSL bases shown in Figure 5, Figure 6 presents further results on the performance of various GSL bases ($\mathbf{X}$, $\mathbf{\hat{A}}\mathbf{X}$, $MLP(\mathbf{X})$, $GCN(\mathbf{X},\mathbf{A})$, $GCL(\mathbf{X},\mathbf{A})$) across GAT, SGC, and GraphSAGE. The results are consistent with those observed in GCN and MLP, where the original node features do not always yield the best input. Some pretrained features, such as $MLP(\mathbf{X})$ on the Texas, Cornell, and Wisconsin datasets, demonstrate significant improvement compared to the original features $\mathbf{X}$, highlighting the necessity of self-training. Since many GSL methods (Zheng et al., ; Suresh et al., ) utilize self-training during the training process, a fair comparison of these GSL methods and baseline GNNs should be conducted in the context of self-training, such as by using pretrained node features as input, as shown in Table 1.

### E.2 GSL Graph Generation

Figure 7 compares the Cos-graph, Cos-node, and kNN methods for GSL graph generation. Across most datasets, the performance differences among these methods are minimal. In certain datasets, such as Roman-empire and Pubmed, the models exhibit comparable performance regardless of the graph generation technique employed. This suggests that variations in graph generation have a limited effect on overall performance.

### E.3 View Fusion

Figure 8 illustrates the impact of different view fusion approaches, comparing the use of only the GSL graph $\mathcal{G}^{\prime}$, the combination of the original graph $\mathcal{G}$ with $\mathcal{G}^{\prime}$ using shared parameters $\theta_{1}=\theta_{2}$, and the use of separate parameters $\theta_{1}\neq\theta_{2}$. Notably, using only the GSL graph $\mathcal{G}^{\prime}$ underperforms compared to employing both graph views with separate model parameters. This indicates that incorporating information from the original graph $\mathcal{G}$ is beneficial for maximizing GNN+GSL performance. Furthermore, for the two graph views, parameter sharing significantly underperforms parameter separation. We speculate that the messages aggregated under $\mathcal{G}$ and $\mathcal{G}^{\prime}$ differ considerably, suggesting that different graphs should be treated with distinct model parameters.

### E.4 Fusion Stage

Figure 9 compares early fusion and late fusion for GNN+GSL with multiple graph views. The performance difference between the two fusion states is often minimal. While early fusion tends to perform slightly better on complex datasets like Actor and Pubmed, the overall impact of switching between early and late fusion is limited across most datasets. For simpler datasets like Minesweeper and Amazon, both fusion methods yield nearly identical performance, indicating that the choice of fusion state does not drastically alter the model’s outcome in most cases.

Figure: (a)
Refer to caption: x15.png

Figure: (a)
Refer to caption: x18.png

Figure: (a)
Refer to caption: x22.png

Figure: (a)
Refer to caption: x26.png

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 5
presentation: 2
questions: * How did you calculate the mutual information? It seems that one must integrate over the input space.
soundness: 3
strengths: * It is nice to know this summary [do not induce any edges!]
* The paper's arguments are easy to follow [though writing can be improved]
summary: Paper summarizes the utility of Graph Structured Learning (GSL): Does inferring edges among nodes (when some edges or no edges are given) help classification tasks? For instance, given many examples, one can develop an MLP that can infer on all examples in parallel. Alternatively, one can induce edges among example pairs, and run a GNN on the features+induced graphs.

Authors show that: there are no cases where GSL is useful. In summary, either run an MLP or a GNN on the original graph. If edges are homophonous, then just use GNN on the real edges (no induced edges). If the edges are heterophilous, just ignore the edges altogether and just run an MLP.
weaknesses: The mean weakness of the paper (reason for my rejection) is:

* The arguments are too general: GSL does not add information
* The construction is too-specific.

From reading the paper, I can only remove some generality from the main argument:

* GSL is not useful for **classification** settings where the graph construction function is set to non-learnable KNN.

Crucially, their edge function is the kNN graph. Their GNN is similar to GCN [Kipf&Welling], i.e., one that averages node features with their neighbors, at every layer. Using kNN edges and GCN should work well if neighbor nodes (i.e. k-nearest) have the same class as the center node. This assumption is not met for heterophilous graphs.

None of the findings seem to be surprising. I will make a few notes

* Why use GCN if you are connecting on-purpose heterophilous edges? Why not use something like MixHop which (promises to) handle heterophilous edges?

* Why use untrainable kNN?

Many methods show that graph structure is indeed useful for their application, including https://arxiv.org/abs/2007.12002 or https://arxiv.org/abs/1711.04043 -- the first has more sophisticated edge-creation function and the second is trainable

# Final note

I do like the paper, but I think it can be greatly simplified to one small argument: dont induce kNN graph use in a GCN, instead use MLP -- noting that kNN+GCN is one instantiation of GSL.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See waeknesses
soundness: 3
strengths: 1. This paper approaches GSL from an interesting perspective of information gain.
2. This paper reevaluated GSL methods using the same GSL bases and show the GSL can not consistently improve the performance of GNNs.
3. The paper is overall well written.
summary: This paper analyzes the graph structure learning methods from the perspectives of mutual information. The analysis suggests that no matter which type of GSL methods are used, after feeding the same GSL bases to the newly constructed graph, there is no mutual information gain compared to the original GSL bases. The paper then re-evaluates the graph structure learning using the same GSL bases. The results verify the the analysis.
weaknesses: 1. While this paper presents an interesting observation of GSL. It is not clear how this observation could help move GSL forward. The key observation is that GSL may not be the major contributor of model performance improvment but rather some other components are. This is a huge claim that tries to deny the previous efforts in GSL. I wonder if there is any certain scenario where GSL is still helpful?
2. In Table 2, there is a difference between the result of the current paper and result from Zhiyao et al. (2024). Is there an explanation for this?

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Does the conclusion hold for large-scale graphs, such as ogbn-arxiv?

2. Does the conclusion hold for GNNs with GSL for graph-level learning tasks, such as those in [1]? 

3. Does the conclusion hold for node classification when the graph structure, node features, or class labels are adversarially perturbed as the settings in [1, 2]? 

4. How does the label ratio impact the effectiveness of GSL methods? Can you make the same conclusion when fewer nodes are labeled?

[1] Li, Zhixun, et al. "GSLB: the graph structure learning benchmark." NeurIPS 2023.

[2] Zhiyao, Zhou, et al. "Opengsl: A comprehensive benchmark for graph structure learning." NeurIPS 2023.
soundness: 2
strengths: 1. The paper is clearly written and is generally easy to follow.

2. The paper conducts extensive empirical evaluations.

3. The paper conducts theoretical analysis, which leads to a similar conclusion as the empirical evaluations.

4. The conclusion obtained is interesting and can be helpful in designing efficient graph neural networks.
summary: This paper summarizes the designs of graph structure learning (GSL) methods in graph neural networks (GNNs) using the proposed GSL framework. The author proposes to theoretically assess the effectiveness of the GSL methods by using mutual information. Both the empirical experiment results and the theoretical analysis conducted in this paper suggest that GSL methods do not enhance GNN performance when evaluated under the same GSL bases, that is, the representation used for GSL and hyperparameter tuning.
weaknesses: 1. Only the node-level learning task, i.e., node classification, is studied in this work. However, GSL is also widely used for graph-level learning tasks, such as graph classification.

2. Only small-scale datasets are studied in this work. 

3. GSL methods are also widely used to improve the robustness of GNNs by purifying the perturbed graph structures. It would be interesting to see whether the observation and conclusion hold on adversarially perturbed graphs.

4. Existing works suggest GSL algorithms achieve the best results in scenarios with fewer labels available [1]. However, this work only studied the setting of splitting 50%/25%/25% of the nodes in train/validation/test sets. This data split setting differs from what is used in some of the GSL papers evaluated. I would suggest the author study the impact of label ratio on the effectiveness of the GSL methods.

[1] Li, Zhixun, et al. "GSLB: the graph structure learning benchmark." NeurIPS 2023.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Novelty of the Main Contribution: Can the authors elaborate more on the novelty of their key conclusions, especially regarding the second point in the contribution list? The observation that a strong GNN model might diminish the need for GSL methods feels intuitive and not surprising. How does this work differentiate itself from previous studies in this area? Are there specific aspects of GSL not yet addressed by prior research that the authors are tackling?

2. Theoretical Analysis vs. Derivation: In the introduction, the authors reference a theoretical analysis presented in Appendix B. However, the analysis appears to be more of a mathematical derivation rather than a comprehensive theoretical insight. Could the authors clarify why they classify it as a theoretical analysis? How does this analysis provide deeper understanding beyond the mere derivation of terms?
soundness: 3
strengths: 1. The authors present a GSL framework, which is a valuable contribution. It provides a common terminology and aligns the community on the same page, facilitating clearer communication. Additionally, a unified framework benefits the subsequent empirical comparisons and discussions.

2. The empirical findings are solid. The observations in Section 4.1, particularly Observations 1-3, offer clear takeaways for practitioners. Furthermore, the empirical comparisons in Section 5.1 are thorough and comprehensive.
summary: This study examines critically on the role of Graph Structure Learning (GSL) in improving Graph Neural Networks (GNNs). 
Although GSL has been used to improve GNN performance by capturing semantically similar nodes, the authors claim that there is insufficient theoretical and empirical evidence to support its necessity. The authors also show GSL's training times and the need for extensive hyperparameter tuning.

the paper proposes a new framework for categorizing GSL methods into three components: GSL base generation, new structure construction, and view fusion, which provides a better understanding of GSL's elements.
According to the authors' empirical analysis, GSL does not consistently outperform standard GNN approaches. 
Their findings show that GSL fails to provide more mutual information gain than traditional methods. 
Finally, the authors conclude that non-optimization-based GSL methods are frequently unnecessary because the quality of the original GSL bases guarantees informative node representations. 
This calls into question the prevailing assumptions about GSL's role in effective GNN performance and suggests reassessing its importance in future GNN designs.
weaknesses: 1. The primary weakness of this work is its lack of novelty. The key conclusion (especially the second point in the contribution list) seems rather obvious, at least to those familiar with GSL methods. Even for those who haven't empirically tested GSL methods, the result isn't surprising. If one assumes that the GNN model is sufficiently strong, it logically follows that the GSL method would be redundant. GSL appears more like an intermediate tool, and a good GNN model should outperform or make GSL unnecessary in an end-to-end training/inference.

2. In the last paragraph of the Introduction, the mentioned "theoretical analysis" (Appendix B) feels more like a derivation than a true theoretical analysis. Moreover, the analysis is too coarse-grained and offers little insight. In line 83, the claim that "GSL bases serve as the upper bound" is poorly framed. The GSL bases in this context refer to features, while the upper bound is a scalar term derived from these bases. The way this upper bound argued is a non-professional theoretical claim.

Meta-review: This paper studies Graph Structured Learning from the perspective of mutual information. The authors provided theoretical analysis and empirical results. The authors’ experimental results reveal that GSL methods fail to provide additional mutual information gain than the baselines. 

**Strengths:**

1. The paper is well-written with clear takeaway messages and is overall easy to follow
2. It provides terminology for discussion and presents a framework for comparing GSL/GNN methods.
3. The paper provides empirical evaluations and theoretical analysis.

**Weaknesses:**

1. The authors present a too huge (or general) claim “GSL does not provide any additional performance gain”  but the authors studied only a limited setting, classification and KNN graphs. More advanced graph structure learning methods need to be studied. Also, the claim needs to be verified across a wide range of tasks, including graph-level tasks. 
2. The main claim is inconsistent with recent efforts that demonstrate the benefits of GSL. 
3. Empirical results are provided only for small-scale datasets.
4. More thorough theoretical analysis is needed to support the main claim.

In sum, this paper studies the benefits of GSL from the perspective of mutual information and claims that GSL does not provide any additional performance gain. However, this claim is inconsistent with recent results, and the claim needs to be verified in more diverse settings, including advanced GSL methods, graph-level tasks, and larger datasets.

Decision: Reject