Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Authors: Jincheng Huang
Yujie Mo
Xiaoshuang Shi
Lei Feng
Xiaofeng Zhu
Venue: ICML 2025 poster (2025)
Keywords: graph neural networks
semi-supervised learning
graph learning
Primary area: deep_learning->graph_neural_networks

Abstract: The message-passing mechanism of graph convolutional networks (i.e., GCNs) enables label information to reach more unlabeled neighbors, thereby increasing the utilization of labels. However, the additional label information does not always contribute positively to the GCN. To address this issue, we propose a new two-step framework called ELU-GCN. In the first stage,  ELU-GCN conducts graph learning to learn a new graph structure (i.e., ELU-graph), which allows the additional label information to positively influence the predictions of GCN. In the second stage, we design a new graph contrastive learning on the GCN framework for representation learning by exploring the consistency and mutually exclusive information between the learned ELU graph and the original graph.  Moreover, we theoretically demonstrate that the proposed method can ensure the generalization ability of GCNs. Extensive experiments validate the superiority of our method.

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Jincheng Huang'
Yujie Mo! Xiaoshuang Shi 12 Lei Feng²
Xiaofeng Zhu 14
Abstract
Dong al., 2021). Consequently, the framework of opti- mizing label utilization in GCNs (LU-GCN) has become an increasingly prominent research topic ( (Wang et al., 2021; Yue et al., 2022; Huang et al., 2024; Yu et al., 2022).
The message-passing mechanism of graph con- volutional networks (i.e,, GCNs) enables label information reach more unlabeled neighbors, thereby increasing the utilization of labels. How- ever, the additional label information does not al- ways contribute positively to the GCN. To address this issue, we propose new two-step framework called ELU-GGN. In the first stage, ELU-GCN conducts graph learning to learn new graph structure (i.e., ELU-graph) which allows the ad- ditional label information to positively influence the predictions of GCN. In the second stage, we design a new graph contrastive learning on the GCN framework for representation learning by exploring the consistency and mutually exclusive information between the learned ELU graph and the original graph. Moreover, demonstrate that the proposed method can ensure the generalization ability of GCNs. Extensive ex- periments validate the superiority of our method.
Previous LU-GCN can be partitioned into three categories, Le., self-training methods, combination methods, and graph learning methods. self-training methods (Dong et al., 2021; Li et al., 2018; Sun et al., 2020; Ji al., 2023) select un- labeled nodes with the highest classification probability by GCN as training data with pssudo-labels, thus adding the number of labels to improve the GCN. Combination meth- ods (Wang et al., 2021; Yue et al., 2022; Shi et al., 2021) regard the labels as the augmented features so that labels can be used for both representation learning and classification tasks. The feature propagation mechanism allows GCNs to use labels to supervise the representation of both the node itself (i.e.. traditional label utilization) and its unlabeled neighbors (i.e., neighboring label utilization). However, the two LU-GCN methods mentioned above primarily focus on optimizing traditional label utilization, neglecting the critical importance of neighboring label utilization in semi- supervised scenarios. Yet, due to noise in the original graph structure, GCNs often struggle to utilize the neighboring labels effectively. To address this issue, recent graph learn- ing methods (Zheng et al., 2020; Luo et al., 2021; Liu et al., 2022) are designed to improve the relationship of every node and its neighbors by updating the graph structure, and thus may potentially improve the neighboring label utilization. For example, Bi al. (2022) adopt the own and neighbors' label similarity to rewire the graph, which can make features propagate on the same category nodes as possible.
theoretically
1. Introduction
Graph Convolutional Networks (GCNs) (Kipf& & Welling, 2017: Gasteiger et al., 2018; Huang et al., 2023a; Xu al., 2018; Hamilton al., 2017) have demonstrated remarkable capabilities, primarily due to their ability propagate label information. This capability has driven their widespread applications in semi-supervised learning. To do this, GCN propagates the representations of unlabeled neighbors to labeled nodes by the message passing mechanism, thereby enabling label information to supervise not only the labeled nodes but also their unlabeled neighbors (Ji al., 2023:
A Although existing graph learning methods have achieved promising performance, there are still some limitations that need to be addressed. First, previous methods have used heuristic approaches to learn the graph structure, they have not explored what kind of graph structures can make GCNs efffectivlyy propagate the labeled nodes' information to un- labeled nodes. As a result, on the learned graph structure, the label information propagated via message passing may not always contribute positively to the predictions of GCNs. Second, existing graph learning methods fail to explore both the consistency information and the mutually exclusive in- formation between the new graph and the original graph,
School Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China Siihhan Artificial Intelligence Research Institute, Yibin, 644000, China School of Computer Science and Engineering, Southeast University, Nanjing, China "Hainan University, Haikou, China. Correspondence to: Xiaofeng Zhu <seanzhuxf@ maritluuuxt@gmiilcoomm gomi.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
where they have consistent information (i.e. consistency (Xu et al., 2024)); which helps recognize the node effec- tively, and every graph contains unique and useful informa- tion different from another graph, i.e, mutually exclusive information (Wang et al., 2017).
2. Related Works
This section briefly reviews the topics related to this work, including GCNs and LPA as well as graph structure learning.
2.1. GCNs and LPA
Based on the above observations, a possible solution to improving the effectiveness of GCNs is to define a graph structure that can maximize label utilization during the message-passileg process and efficiently combine the orig- inal graph. To achieve this, two crucial challenges must be solved, i.., (i) it is difficult to evaluate whether a graph structure enables GCN to use labels effectively. (ii) it is necessary to mine the consistency and mutually exclusive information between the original graph and the new graph.
GCNs are the most popular and commonly used model in the field of graph deep learning. Early work attempted to apply the successful convolutional neural network (CNN) to graph structures. For example, CheybNet (Defferrard et al., 2016) first proposes to transform the graph signal from the spatial domain to the spectral domain through the discrete Fourier transform, and then use polynomials to fit the filter shape (i.e., convolution). CheybNet laid the foundation for the development of spectral-domain graph neural networks. The popular GCN was proposed by Kipf et al. (Kipf & Welling, 2017), which is a simplified version of ChebyNet and has demonstrated strong efficiency and effectiveness, thereby promoting the development of the graph deep learning field.
In this paper, to address the above issues, different from pre- vious structure improvement methods, we investigate new framework, Le., Effectively Label-Utilizing GCN (ELU- GCN for brevity), to conduct effective GCN. To achieve this, we first analyze the influence of each class provided by labeled nodes on every unlabeled node. We then optimize the graph structure (i.e., the gr.Ugg by encouraging the label information propagated through the graph have positive impact on GCN's 's prediction results. This ensures that the GCN with the ELU-graph can effectively utilize the label information, thereby addressing challenge (i). More- over, we address challenge (ii) by designing contrasting constraints to bring the consistent information between two graph views (i.e., the original graph and the ELU-graph) closer and push the mutually exclusive information further apart. Finally, we theoretically analyze that the proposed ELU-graph can ensure GCN effectively utilizes labels and improve the generalization ability of the model. Compared with previous methods, our main contributions can be sum- marized as follows:
Recently, some works have focused on the combination of IPA and GCN. This is because LPA can characterize the distribution of labels spread on the graph, which can help GCN obtain more category information. Existing combined IPA and GCN methods can be classified into two cate- gories, ie.. pseudo label methods and masked label meth- ods. Pseudo-label methods let the output of LPA serve as the pseudo-labels to guide the representation learning. For example, PTA (Dong et al., 2021) first propagates the known labels along the graph to generate pseudo-labels for the un- labeled nodes, and second, trains normal neural network classifiers on the augmented pscudo-labeled data. GPL (Wu et al., 2024) uses the output of LPA to preserve the edges between nodes of the same class, thereby reducing the intra- class distance. The masked label methods employ LPA as regularization to assist the GCN update parameters or struc- tures. For example, UniMP (Shi et al., 2021) makes some percentage of input label information masked at random, and then predicts it for updating parameters. GCN-LPA (Wang & Leskovec, 2021) also randomly masked part of the labels and utilized the remaining label nodes to predict them in learning proper edge weights within labeled nodes. A Although the above methods achieve excellent results on various tasks, they all overlook whether the additional label information propagated through message passing effec- tively utilized by GCNs improve unlabeled nodes.
To the best of our knowledge, this is the first work to investigate the limitation of GCNs in effectively utilizing label information under the graph-based learn- ing paradigm. Moreover, we introduce a quantitative framework to analyze which unlabeled nodes struggle to benefit from label supervision by neighborhood.
We propose an adaptive and parameter- free construc- tion of the EL.U-graph to enhance GCNs' ability to uti- lize label information, particularly for unlabeled nodes. Furthermore, we design contrastive loss to exploit both the consistency and complementary differences between the EL.U-graph and the original graph.
2.2. Graph Structure Learning
We theoretically prove that the ELU-graph construc- tion provides generalization guarantees for GCNs. Em- pirical results on diverse benchmark datasets further validate the superior performance of our method over
Graph structure learning is an important technology in the graph field. It can improve the graph structure and infer new relationships between samples, thereby promoting the development of graph representation learning or other fields.
competitive baselines.
2

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Existing Graph structure learning methods can be classified into three categories, ie., traditional unsupervised graph structure learning methods, supervised graph structure learn- ing methods, and graph rewiring methods.
tation is denoted by the feature matrix X E Raxd where is the number of nodes and d is the number of features for each node. The label matrix is denoted by Y E _ with a total of classes. The first m points x,( S m) are labeled as Y,, and the remaining u points x; (m + 1 S i S n) are unlabeled. The sparse matrix A E ==*= is the adjacency matrix of G. Let D = diag(dı, da, ..,.......... .da) be the degree matrix, where de = EjeN; atj is the degree of node i, the symmetrie normalized adjacency matrix is represented as A D 3 ADD where A A + I, I is the identity matrix and D is the degree matrix of A.
Traditional unsupervised graph structure learning meth- ods aim to directly learn a graph structure from a set of data points in an unsupervised manner. Early works (Wang& & Zhang, 2006; Daitch et al.. 2009) ex- ploit the neighborhood information of each data point for graph construction by assuming that each data point can be optimally reconstructed using a linear combination of its neighbors (i.e., min ||A- - Similarly, (Daitch et al., 2009) introduce the weight Smoothness (Jiang et al., 2019) is another widely adopted as- sumption on natural graph signals; the smoothness of the graph signals is usually measured by the Dirichlet energy (i.e., mina 1 Eng Ai, |X,xxy] Xyl' and ming tr (x LX)). The above objective has inspired many advanced graph structure learning methods.
3.1. Motivation
(i.e., min Σ: D - -,,,,,,
Given classification function ff X + Raxe, the cross entropy losses of Deep Neural Network (DNN) and GCN are formulated by:
CNN = =CE(fo(X), Y))
E
(log fai)
SEVIKEE
(I)
2
LaCN CB(Afa(X), Y)
Σ
yiu (log
Σ agyfa)) JEN;
KEC
where 9 is the parameters of the function f. In Eq. (1), the cross entropy loss of DNN is one-to-one mapping between the feature space and the label space because every label yi (1 1,.....)) n) is only used to supervise the representation learning of one node U.. The mapping f efficiently captures the pattern and distribution of labeled nodes, but it overlooks unlabeled nodes that the generalization ability of unla- beled nodes is limited. In contrast, the cross entropy loss of the GCN is a one-to-many mapping because its message- passing mechanism can propagate the information from labeled nodes to their neighbors including labeled nodes and unlabeled nodes. As a result, every label y/i is used to supervise the representation learning of both labeled nodes and unlabeled nodes, shown in the second row of Eq. (1). Hence, unlabeled nodes in the GCN are able to use the label information of labeled nodes to improve the learning of their representations. Obviously, it is critical to ensure that the label information propagated to unlabeled nodes makes positive contribution to GCN. However, to the best of our knowledge, this issue has not yet received sufficient attention. A related work, GCN-LPA (Wang & Leskovec, 2021), investigates the influence of labeled nodes; however, it primarily focuses on reinforcing mutual influence among labeled nodes, while overlooking their impact on unlabeled nodes. To address this issue, we first quantify how much influence each class, through its labeled nodes, has on the unlabeled nodes.
Supervised graph structure learning methods aim to use the downstream task to supervise the structure learning, which can learn a suitable structure for the downstream task. For example, NeuralSparse (Zheng et al., 2020) and PTDNet (Luo et al., 2021) directly use the adjacency matrix of the graph as a parameter and update the adjacency ma- trix through the downstream task. SA-SGC (Huang et al., 2023b) learns a binary classifier by distinguishing the edges connecting nodes with the same label and the edges connect- ing nodes with different labels in the training set, thereby deleting the edges between nodes belonging to different categories in the test set. BAGCN (Zhang et al., 2024) uses metric learning to obtain new graph structures and learns suitable metric spaces through downstream tasks.
The goal of graph rewiring methods is prevent the over- squashing (Alon& & Yahav, 2021) problem. For example, FA (Alon& & Yahav, 2021) proposed to use a fully connected graph as the last layer of GCN to overcome over-squashing SDRF (Topping et al., 2022), SJLR (Giraldo et al., 2023), and BORF (Nguyen et al., 2023) aim to enhance the cur- vature of the neighborhood by rewiring connecting edges with small curvature. They increase local connectivity in the graph topology, indirectly expanding the influence range of labels. Despite their success, existing graph structure leam- ing methods fail to guarantee that the learned structures enable GNNs to propagate label information to unlabeled nodes effectively.
The recent study in (Xu et al., 2018) reveals that nodes follow the way of random walks to affect other nodes on the graph. Therefore, in this paper, we extend it to obtain the influence of every class of labeled nodes on the unla- beled node by Proposition 1. whose proof is provided in Appendix B.
3. Method
Notations. Given graph G = (V, Y), where V is the node set and E is the edge set. Original node represen-
3

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
(a) Label Influence
(b) Predicted to Orange
(c) Predicted to Blue
Class Influence I:
Prediction of GCN
V
Prediction of GCN
a
a
Figure 1. An illustration of effective label utilization. Sub-figure (a) wants to assign the label information to node a (gray node) by one unlabeled node (gray node) and two labeled nodes with different classes, i.e., one blue node and one orange node. Moreover, the LPA algorithm is employed to obtain the probability of cach labeled node to the node where the blue node has more influence (or higher probability) than orange node based on the histogram in the upper right of the sub-figure (a). If the GCN predicts orange color (as shown in sub-figure (b)). which is inconsistent with the class with most label information (i.e., blue). It indicates that the label information provided by the message passing of the GCN does not help classify the node a, and may even hinder its correct classification. On the contrary, if GCN predicts the node the blue color, iee. sub-figure (c), it implies that the label information provided by the message passing of the GCN helps to classify the node a.
node a as the
Proposition 3.1. Given an unlabeled node Us (i I,..., Tt), for an arbitrary category Ct (l 1,....... c), the inftuence of labeled nodes belong to C₁ on the i-th node vs propor- tional to the probability that node V, is classified as Ci by the Label Propagation Algorithm (LPA) in (Zhu, 2005), in the GCN framework.
labeled nodes in the graph. Figure 2 shows that not all un- labeled nodes effectively use label information in the GCN framework (iee. Figure (a)) and the classification accuracy of VNELU lower than that of VELU in the same datasets (i.e., Figure 2 (b)). Obviously, NELU nodes influence the effectiivnesss of the GCN. To address this issue, first, it is crucial to make unlabeled nodes effectively utilize label information. Since label information is propagated through the graph structure. As a result, the graph structure will be updated. Second, the original graph structures often contain noise influence the pessage-passiin mechanism. Hence, graph learning obviously feasible solution.
Based on Proposition 3.1, IPA can be used to estimate the class-wise probability for unlabeled nodes in the GCN framework. The class with the highest probability is re- garded as the most influential, as it contributes the most label information to the node. If this most influential class matches the GCN prediction, it indicates that the label infor- mation provided through message passing positively influ- ences the GCN's i classification for that node. In this way, the GCN is regarded having effectively utilized the label in- formation on this node. We provide a case study to illustrate this in Figure and give a formal definition as follows.
3.2. ELU Graph
Previous graph learning methods generally use either heuris- tic methods or downstream tasks conduct graph learning, i.e., updating the graph structure. For example, Pro-GNN (Jin et al., 2020) updates the graph structure through a heuris- tic approach to constrain the sparsity and smoothness of the graph. PTD-Net (Luo et al., 2021) updates the graph structure by the downstream task, such as the node classifi- cation task. However, heuristic methods rely on predefined rules, making it difficult for unlabeled nodes fully access lahel-related global information. Downstream task methods focus too much on the performance of labeled nodes, ne- glecting the role of unlabeled nodes in the graph structure. Therefore, these methods fail to guarantee that the GCN effectively leverages label information for unlabeled nodes. solve this issue, based on Definition 3.2, we investigate new graph learning methods that ensure unlabeled nodes effectively utilize label information.
Definition 3.2. (Effective label-utilization) The GCN ef- fectively utilizes label information if the prediction of the GCN is consistent with the output of LPA. This condition is defined at the node level:
VELU (VILPA(G) = GCN(G)),
(2)
where VELU and VNELU (i.e.. VNELU (VILPA(S) + GCN(G))) respectively, represent the sets of nodes which the GCN effectively and ineffectively utilizes label information, respectively.
In real applications, not all unlabeled nodes in GCN frame- works may effectively utilize the label information due to all kinds of reasons, including noise and the distribution of

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Cora
Citeseer
Pubmed
we can obtain the S through the optimization algorithm by minimizing the Eq. (5). However, there are some problems with the above objective function. First, it is impractical to solve the above problem directly, as it has a trivial solution: 8i.j = 0, Vi, Vj. Second, LPA generates the prediction for every labeled node to possibly revise the original labels, iee, the ground truth, adding noisy labels for representation learning. To overcome the above issues, We propose to iteratively update in two steps, i.e., update labels by LPA and update the graph structure S.
NELU
NELU
7%
39
31.3%6
4R.5%
NELU
EWU
60.4%
70.35
ELU
(a) Proportion
ELU NELU
80
In the first step, we calculate the result of LPA Q())
Accuracy
60
Le., Q = (( (2 = 1,.... A), where Q(0)
Y. As a result, Eq.(5) is changed as follows:
40
min 0 1a/l//0--sn -000sSH(p + Σ
s.t. Q Q = =,, (6)
20
where 3 is a non-negative parameter to trade off two terms, the second term can make the subsequent matrix inversion more stable. Eq. (6) holds the closed-form solution to
Cora
Citeseer
Pubmed
(b) Accuracy
address the first issue. The constraint term "s.t. Q, Yi" term solves the second issue.
Figure 2. Visualization of both ELU nodes and NELU nodes in three real datasets, i.e., Cora, Citerseer, and Pubmed. (a) every dataset contains NELU nodes and (b) the classification comparison between ELU nodes and NELU nodes, where ELU nodes have higher classification ability than NELU nodes.
In the second step, we can obtain its closed-form solution as follows:
c Q SH
+
Σ
i,j=1
Specifically, denoting the adjacency matrix S as the ELU graph can ensure the GCN effectively uses the label infor- mation. We use Proposition 3.1 to measure the influence of each class on every unlabeled node by the LPA:
SH) -Tr((Q -SH) (Q
SH) + 2,8
where Tr(.) indicates the trace of matrix. Then we have
ac
Q = =S,
(3)
2Q H" + 2SHH +
(8)
as
where the i-th row of Q E Rm (i.e., Q.,)) represents the influence of each class on node i. It is noteworthy that S in Eq. (3) can be the k-order of the graph structure. After that, the prediction of GCN with ELU graph can be written follows (Yang et al., 2023):
Let Eq. (8) equal to 0, we can obtain the closed-form solu- tion S(O) ie..
S = - H" (HH" + +IIN
(9)
where IN E Raxx is the identity matrix.
Y SH. s.t. H = MLP(X),
(4)
Finally, we iteratively optimize Eq. (9) and Q( =
S ((--)Q(-11) ((-1)) to obtain the ELU graph S
where MLP(-) denotes Multi Layer Perceptron. Note that the MLP pre-trained. Therefore, based on Definition 3.2, the ELU graph (i.e., S) can be obtained by minimizing the following objective function:
However, the calculation of ( in Eq. (9) with the time complexity of ((n²). ). In this paper, we use the Woodbury identity (Woodbury, 1950) to avoid calculating S(9 during
the iteration process by Q(1) Q(i-)) i...
min Q
min
min SY - 2 F-
(5)
In Eq. (5), the prediction of GCN and the influence of each class are encouraged to be consistent for every node. This item can make all nodes satisfy LPA(g) = GCN(G) in Eq. (2). ie., this objective function can ensure all nodes can effectively utilize label information by GCN, Therefore,
HT HT
IN
1 H g2
I
H
H
H
H
Qi--1)
8.1. Q = Y
(10)
5

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
NELU nodes. Obviously, in representation learning, the representations of ELU nodes in both S and À should be consistent for keeping common information related to the class, the representations of NELU nodes in A should be different from their representation in S" Based on Eq. (10), we obtain Q( (i = I,...,, from Q(--). After obtaining Q(A) we obtain the ELU graph S by calculating Eq. (9) only one time. To achieve effi- ciency, we employ the Woodbury identity to reduce the time complexity of calculating from cubic to quadratic, i.e.,
where I E Ieex is the identity matrix and the specific derivation process is listed in the Appendix B.3. Based the literature (Woodbury, 1950), we can obtain the time complexity of Eq. (10) is Oncc² + c²),, where c² < n. The details are provided in Appendix A.
To do this, we first propose to learn a projection head ps to map both the ELU graph representations and the original graph representations into the same latent space, i.e., P = Po(H) (H) and P = po (H), where H is the representation of the output layer of the GCN dominated by the original graph, and H is the representation of the output layer of the GCN dominated by the ELU graph, the output of the model is Y = Softmax((1 parameter. We then design a contrastive loss as follows:
S Q
1 H
1 H'H Ba
H
I. I
H'H
H
7) + ry),, where 1j is a hyper-
(11) The details of Eq. (11) are listed in Section A.2. The pscudocode of calculating Eq. (10) and S is presented in Algorithm 1. In the implementation, we make S sparse by assigning its element less than threshold zero, for achieving efficiency. We also use the pscudo labels of ELU nodes to expand the initial Y, for avoiding the issue of limited labels in semi-supervised learning.
Pos
1 n
Lcon = -lo Pos + Neg
Ii. log Di.
71
1=1
Pos
VILU exp(c((P. P.)/T) > i=w
VVLL
s.t.
Neg
Σ j=u
VNELU
exp(d(P, P. P/)/T)
|NNELU|
(12)
where d(.) is the distance function, 7 denotes the tempera- ture parameter, and Ji.j is the element in row i and column j in Y
Algorithm Pseudo code of calculating S*.
Input: Feature matrix X, label matrix Y, normalized adja- cency matrix A, and index of ELU nodes VELU; Output: ELU graph S*
In Eq. (12), the first term encourages minimizing the dis- tance between every ELU node in the ELU graph and its corresponding node in the original graph, while maximiz- ing the distance between every NELU node in the original graph and its corresponding node in the ELU graph. The second term encourages the decision boundary to be po- sitioned in low-density regions, enhancing the distinction between nodes and ensuring the underlying assumption of semi cemi-supervieed learning (Berthelot et al., 2019). As re- sult, Eq. (12) is available to extract the consistency and mutually exclusive information between the representations dominated by the ELU graph and the original graph.
1: H = MMP(XX;;
2: Expand initial labels by pseudo labels of ELU nodes;
3: for 1-+-10 1, k do
4: Calculate Q by Eq. (10);
5: 0 = Y2 in Eq. (10);
6: end for
7: Calculate S Eq. (11);
8: Return S
3.3. Contrastive Constraint
Given the ELU graph S* and the original graph A, previous graph learning methods often conduct a weighted fusion. For instance, SimP-GCN (Jin et al., 2021) employs hy- perparameter as weight to fuse the node representation from the original graph with those from the feature simi- larity graph. However, only performing the weighted sum method may result in incorporating undesirable information from the original graph into the ELU graph. For example, the representation of NELU node from the original graph might interfere with the learned representation of the corre- sponding node in the ELU graph. To solve this issue, in this paper, we propose a new contrastive learning paradigm to capture the consistency and mutually exclusive information between these two graphs.
Finally, the final objective function of our proposed method is obtained by integrating the contrastive loss with the su- pervised loss (i.e., cross entropy) follows:
L = CEY. Y) + XLoon
(13)
where À [o, 1] is hyperparameter to fuse the predicted results of two views and two objective functions.
3.4. Theoretical Analysis
The ELU graph has been shown to enable the GCN to effec- tively utilize label information, as demonstrated in Section 1. In this section, we theoretically analyze that the gener- alization ability of the GCN is related to the graph structure and the training labels by Theorem 3.3 (The proof can be found Appendix B.4):
In the ELU graph Sr, all nodes are theoretically ELU nodes. However, the original graph A includes ELU nodes and
6

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Theorem 3.3. Given a graph G with its adjacency matrix A, the label matrix in the training set Y and the label matrix of the ground truth wee. for any unlabeled nodes, if a graph structure makes the labels in training set be consistent to the ground truth, i.e., Y true= = AY, then the upper bound of the generalization ability of the GCN is optimal.
2021), NeuralSparse- GCN (Zheng al., 2020), PTDNet-
GCN (Luo et al., 2021). CoGSL (Liu al., 2022), Node- Former (Wu et al., 2022), GSR (Zhao et al., 2023) and BAGCN (Zhang et al., 2024).
4.1.3. EVALUATION PROTOCOL
To evaluate the effectiveness of the proposed method, we fol- low the commonly used setting. Specifically, for the citation network (i.e., Cora, Citeseer, and Pubmed), we use the pub- lic split recommended by (Kipf & Welling, 2017) with fixed 20 nodes per class for training. 500 nodes for validation, and 1000 nodes for testing. For Social networks (i.e., Caltech, UF, Hamilton, and Tulane), we randomly generate differ- ent data splits with an average train/val/test split ratio of 60%/20%/20%. For the Webpage network (i.e., Chameleon, Squirrel) and co- co-purchase networks (i.e., Computers, Photo), we use the public splits recommended in the original papers.
Based on Theorem 3.3, the graph structure A maximizes the generalization ability of the GCN if the following equa- tion holds, i.e., minA |AY - Y [|?-- Therefore, the graph structure can be used to measure if is suitable for GCN. However, the true labels Y true are fixed and unknown. Moreover, the original graph is also fixed so that it is diffi cult to achieve minA ||AY - Y Yreuellf il Hence, the original graph should be updated. We then present the following theorem. The proof is listed in Appendix B.5.
Theorem 3.4. The optimization Eq. (5) is equivalent to approximate optimization of minA ||AY- - Yurue II..
4.2. Effectiveness Analysis
Theorem 3.4 indicates that the ELU graph can ensure the generalization ability of the GCN.
We first evaluate the effectiveness of the proposed method by reporting the results of node classification in Table I and Appendix F, respectively. Obviously, the proposed method obtains better performance on seven datasets than comparison methods.
4. Experiments
In this section, we conduct experiments on eleven public datasets to evaluate the proposed method (including cita- tion networks, Amazon networks, social networks, and web page networks), compared to structure improvement meth- ods'. Detailed settings are shown in Appendix E. Additional experimental results are shown in Appendix F.
First, compared with traditional GNN methods and ad- vanced GNN methods. the proposed ELU-GCN outper- forms them by large margins on most datasets. For example, the proposed ELU-GGN on average improves by 4.05 %, compared to GCN, and improves by 3.26 % compared to the best advanced GCN method (i.e., PCNet), on all datasets. This demonstrates the superiority of graph structure learn- ing methods, as the label information cannot be effectively utilized for many nodes in the original graph.
4.1. Experimental Setup
1. DATASETS
The used datasets include three benchmark citation datasets (Sen et al., 2008) (i.e., Cora, Citeseer, and Pubmed), two co-purchase networks (Shchur et al., 2018) (i.e., Comput- ers and Photo), two web page networks (Pei et al., 2020) (i.e., Chameleon and Squirrel), which are heterophilic graph data), and four social network datasets (Traud et al., 2012) (i.e., Caltech, UF, Hamilton, and Tulane).
Second, compared to the improvement methods, the pro- posed ELU-GCN achieves the best results, followed by GSR, GCN-LPA, CoGSL, PTDNet-GCN, NeuralSparse- GCN, and NodeFormer. For example, our method on aver- age improves by 2.21% % compared to the best comparison method GSR on all seven datasets. This can be attributed to the fact that the proposed ELU-GGN, which can obtain a graph structure (i.e., the ELU graph) that is more suitable for the GCN model to effectively utilize the label infor- mation and efficiently mine the consistency and mutually exclusive information between the original graph and the newly obtained graph. In addition, the Webpage networks (i.c., Chameleon and Squirrel) are heterophilic graphs. As mentioned in the theoretical analysis section, the original graph is difficult guarantee the generalization ability of GCN, especially for heterophilic graphs. Experimental re- sults show that the proposed ELU-GCN outperforms the GCN using the original heterophilic graph by an average of 9.5%, confirming the results of our theoretical analysis.
4.1.2. COMPARISON METHODS
The comparison methods include three traditional GNN methods, two advanced GNN methods, and seven structure improvement- based GCN methods. Traditional GNN meth- ods include GCN (Kipf& & Welling, 2017), GAT (Velickovic et al., 2018), and APPNP (Gasteiger et al., 2018). The ad- vanced GNN methods include GPRGNN (Chien et al., 2021) and PCNet (Li et al., 2024). The structure improvement- based GCN methods include GCN-LPA (Wang& & Leskovec,
'The code is released https:// http://ttthubcccooo huanguC0429/1e4 luteellttiiiiii weetiiiieeiiiii ze-3CN SCN
7

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Table 1. Performance on node classification task.
The highest results are highlighted in bold. "OOM" denotes out of memory.
Method
Cora
Citeseer
pubmed
Computers
Photo
Chameleon
squirrel
GCN
81:61
70.35
=0.62
81,62+2.43
1.,44
2..8
43.43=2211
GAT
83.03
1.15
79. 10.38
78.01 119.1
85.71 2003
40.72:11.55
30.2612.50
APPNP
83.33+0062
71.80+0.84
80. 10
82.12:3311
83.63
16.36+1..3
46.53+2.18
GPRGNN
80.55
1.25
77.02
81.71 +2,84
91.23
16.85
31.61
PCNet
82.8111.55
19.92..0.0
80.01 1..88
81.32
89.63
59.74.11.43
48.53
GCN-LPA
83.13
02.60
18.64
83.54.1.41
10.13
50.26111.8
42.78
N.S.-GCN
12.
71.55
79. 14
11.16.1153
89.86.1..
55.37
46.864202
PTDNet-GCN
82.81 +0.23
72.73+0.18
78.81 =0.24
82.21
90.23+2.84
53,26+11.4
41.96++2.16
CoGSL
81.76 10.24
12.79
OOM
00M
89.63
52.23
39,96113.31
NodeFormer
80.28
+1.91
78.21
80.35
89.37
34.71+4.12
38.54+1.51
GSR
83.08 L0.48
72.10
78.0990.55
81.6
90.02
62.28
50.53
BAGCN
83.70+0.21
72.96+0.75
78.54=0.72
79.63+22.52
91.25
52.63
42.36+1153
ELU-GCN
84.29+0.39
74.23+00.2
00221
83.73+2.31
90.81 11.3
70.90
16.91
Consequently, the effectiveness of the proposed method is verified in node classification tasks.
importance of unlabeled nodes being affected by effectively labeled information in message passing.
We further evaluate the effectiveness of the proposed method on social network datasets and report the results of node classification in Appendix F.I. We can observe that the proposed method also achieves competitive results on the social network datasets compared to other baselines. For example, the proposed method outperforms the best baseline (i.e., GSR), almost all datasets.
4.4. Visualization
To provide an intuitive and clear understanding of the effec- tiveness of the learned ELU graph, we visualize the adja- cency matrix of the ELU graph in the heatmap on the Cora, Computers, Photo, and Chameleon datasets and report the results in Figure 3.
Specifically, the rows and columns of heatmaps are re- ordered by node labels. In the heatmaps, the lighter a pixel, the larger the value of the ELU graph matrix weight. From Figure 3, we observe that the heatmaps exhibit clear block diagonal structure, with each block corresponding gory. This indicates that the obtained ELU graph tends to increase the weight of connections between nodes of the same category and avoid noisy connections from different classes. As result, under the GCN framework, the training nodes are likely to propagate the label information to unla- beled nodes of the same category with high probability, thereby reducing intra-class variance and increasing inter- class distance. Especially on the Chameleon dataset, where the original graph tends to connect nodes with different la- bels with a high probability (i.e., heterophily). Fortunately, our method can still obtain a graph structure where nodes are connected with the same category, as shown by the ex- perimental results, demonstrating the universality of the proposed method.
4.3. Ablation Study
The proposed ELU-GCN framework investigates the ELU graph to enable the GCN to utilize label information effec- tively. Additionally, contrastive loss function (i.e. fcon) is introduced to efficiently minimize consistency and mutu- ally exclusive information between the original graph and the ELU graph. To verify the effectiveness of each compo- nent of the proposed method and the results are reported in Table 2.
cate-
According Table 2, we draw the following conclu- sions. First, our proposed method achieves the best per- formance when each component is present, indicating that each is essential. This demonstrates the importance of both learning the ELU graph and extracting information from the original graph, as they not only enable GCN to effectively utilize labels but also retain important information in the original graph.
Second, the ELU graph component provided the biggest improvement. For example, the ELU graph improves perfor- mance by an average of 2.9% compared to not considering it, and the Lcon term improves performance by an average of 1.3% compared to not considering it. This illustrates the
4.5. Analyze the Trade-off Between Running Time and Accuracy
The biggest limitation of graph structure learning methods is the need to query in O(n²) space when learning the adja-
8

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Table 2. Classification performance of each component in the proposed methad all datasets.
Method
Cora
Citeseer
pubmed
Computers
Photo
Chameleon
squirrel
GCN
+0.42
70.35=0:45
79.01
81.62+243
90.44
60.82+2.24
43.43+2.18
+ELU graph
83.4910..5
72.02
80.2510.7
82.5611.23
90.52.11.33
65.12.1143
54. 1.
Loon
84.29
7..23
80.51
83.73+2.31
9..3
1..90
16.91
2000
4000
2300
2000
5000
1003
1540
8000
4300
2502
10:00
0100
12000
2002
2530
5:0
1000
15c0
2002
2500
2003
1003
1003
2003
10000 12000
1000 2003 3000 4000
5000
7000
500
15:00
1,000
2000
(8) Cora
(b) Computers
(c) Photo
(d) Chameleon
Figure 3. Visualization of the adjacency matrix of the ELU graph Cora, Computers, Photo, and Chameleon datasets. The and columns are nodes that are reordered based on node labels, the lighter pixel, the larger the value of the ELU graph matrix weight.
cency matrix of graph structures. In our proposed method, we cleverly leverage the inverse matrix transformation trick to avoid the computational complexity of On²)) or even higher. Although we have previously analyzed that the com- plexity of the proposed algorithm in graph construction is (ne²) (c3 < n.). plus the final graph structure is O(n?) (only one calculation is required), we further test the overall actual running time and accuracy of the proposed ELU-GCN and compared with the commonly used baseline (i.e., GCN and GAT). The results are in Figure 4.
From Figure 4, we have the observations as follows. First, the overall running time of the proposed method is slightly inferior to GCN, but significantly ahead GAT. This indi- cates that the proposed ELU graph learning method does not incur too much time overhead and is comparable the basic GNN model. Second, the proposed method achieves the best classification performance. Combining the above two points, the proposed method achieves the optimal trade-off between running time and model performance.
5. Conclusion
In this paper, study the label utilization of GCN and re- veal that considerable number of unlabeled nodes cannot effectively utilize label information in the GCN framework. Furthermore, we propose a standard for determining which unlabeled nodes can effectively utilize label information in the GCN framework. To enable more unlabeled nodes to utilize label information effectively. We propose an effec- tive label-utilizing graph convolutional network framework. To do this, optimize the graph structure following the above standard, enabling every unlabeled node to effectively leverage label information. Moreover, we design novel contrastive loss to capture consistency or mutually exclu- sive information between the original graph and the ELU graph. Our theoretical analysis demonstrates that ELU-GCN provides superior generalization capabilities compared to conventional GCNs. Extensive experimental results further validate that our method consistently outperforms state-of- the-art methods.
84
82-
Accuracy
78
GCN
Cora:
Cora: Durs
Citeseer-GGC
74
Citeseer-GAT
Oltesear-Ours
Pubmed--GC
72
Pubmed-Gaa GAT
Pubmed Ours
10 20
30
35
40
Total training time (seconds)
Figure 4. Scatter plot showing the relationship between model time and accuracy, where the x-axis represents the runtime of different models different datasets and the y-axis represents their corresponding accuracy (%).
9

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Acknowledgement
Gasteiger, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personal- ized pagerank. In International Conference on Learning Representations, (ICLR), 2018.
Xiaofeng Zhu was supported in part by the National Key Research and Development Program of China under Grant (No.2022YFA 10041000, Xiaoshuang Shi was supported in part by the Sichuan Science and Technology Program under Grant (No. 2024YFH702688.
Giraldo, H., Skianis, K., Bouwmans, T., and Malliaros, F. D. On the trade-off between over-smoo and over- squashing in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Informa- tion and Knowledge Management( (CKM), pp. 566-576, 2023.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Gong, S., Zhou, J., Xie, C., and Xuan, Q. Neighborhood Nomophily-guiide graph convolutional network. In Pro- ceedings of the 32nd ACM International Conference on Information and Knowledge Management (CIKM), pp. 3908-3912, 2023.
References
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations((CLR, 2021.
Hamilton, W. L.., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In Advances in neural information processing systems(Neurips)) pp. 1035, 2017.
Berthelot, D., Carlini, N., Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C. A. Mixmatch: A holistic ap- proach semi-supervised learning. Advances neural information processing systems(NeurIPS), 32:5000- 2019.
Huang, J., Du, L., Chen, X., Fu, Q., Han, S., and Zhang, D. Robust mid-pass filtering graph convolutional networks. In Proceedings of the Web Conference( WWW), pp. 328- 338, 2023a.
Bi, W., Du, L., Fu, Q. Wang. Y., Han, S., and Zhang, D. Make heterophily graphs better gnn: graph rewiring approach. arXiv preprint arXiv:2209.0SS: 08264, 2022.
Huang, J., Li, P., Huang, R., Chen, N., and Zhang, A. Re- visiting the role of heterophily in graph representation learning: An edge classification perspective. ACM Trans- actions on Knowledge Discovery from Data(TKDD), 18: 13:1-13:17, 2023b.
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, (ICLR). OpenReview.net, 2021.
Huang, J., Shen, J., Shi, X., and Zhu, X. On which nodes does GCN fail? enhancing GCN from the node perspec- tive. In Forty-first International Conference on Machine Learning (ICML), 2024.
Daitch, S. I., Kelner, A., and Spielman, D. A. Fitting graph to vector data. In Proceedings of the 26th annual international conference on machine learning (ICML), pp. 201-208, 2009.
Ji, F., Lee, S. H., Meng, H., Zhao, K., Yang. J., and Tay, W. P. Leveraging label non-uniformity for node classification in graph neural networks. In International Conference on Machine Learning[ICML) pp.
Davies, D. L. and Bouldin, D. W. A cluster separation measure. IEEE transactions on pattern analysis and machine intelligenceTPPAMI), pp. 227,227, 1979.
2023.
Jiang, B., Zhang, Z., Lin, D., Tang, J., and Luo, B. Semi- supervised learning with graph networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11313- 11320, 2019.
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information pro- cessing systems(NeurIPS), volume 29, pp. 3837-3845, 2016.
Jin, W., Ma, Y., Liu, X., Tang. X., Wang, S., and Tang, J. Graph structure learning for robust graph neural net- works. In Proceedings of the 26th ACM SIGKDD interna- tional conference on knowledge discovery & data mining (SIGKDD), pp. 66 74, 2020.
Dong, H., Chen, J., Feng, F., He, X., Bi, S., Ding, Z., and Cui, P. On the equivalence of decoupled graph convolu- tion network and label propagation. In Proceedings of the Web Conference(WWW)), pp. 3651-3662, 2021.
10

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Jin, W., Der, T., Wang, Y., Ma, Y., Liu, Z., and Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM international conference on web search and data mining (WSDM), pp. 148-156, 2021.
Shi, Y., Huang, Z., Feng. S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceed- ings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 1548-1554, ijcai.org, 2021.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, (ICLR), 2017.
Sun, K., Lin, Z., and Zhu, Z. Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes. In Proceedings of the AAAI conference on artificial intelligence (AAAI), volume 34, pp. 5892- 5899, 2020.
Li, B., Pan, E., and Kang. Z. Pe-conv: and heterophily with two-fold filterin.. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 38, pp. 13437-13445, 2024.
Unifying homophily
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations/CCLR) 2022.
Li, Q., Han, Z., and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference artificial intelli- gence, volume 32, 2018
Traud, A. L.,, Mucha, P. J., and Porter, M. A. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, (91(16)44155-444
Liu, N., Wang. X., Wu, I.., Chen, Y., Guo, X., and Shi, C. Compact graph structure learning via mutual information compression. In Proceedings of the ACM Web Conference (WWW)), pp. 1601-1610, 2022.
2012.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, (ICLR). Open 2018.
Luo, D., Cheng, W., Yu, W., Zong, B., Ni, J., Chen, H., and Zhang, X. Learning drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining( WSDM), pp. 779-787, 2021.
Wang. F. and Zhang, C. Label propagation through linear neighborhoods. In Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 985-992, 2006.
Natekar, P. and Sharma, M. Representation based com- plexity measures for predicting generalization in deep learning. arXiv preprint ar 20Xiv:201..02775, 2020.
Wang, H. and Leskovee, J. Combining graph convolutional neural networks and label propagation. ACM Transac- tions Information Systems (TOIS), 40(4):1-27, 2021.
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. Exploring generalization in deep learning. Advances in neural information processing systems(NeurlP5), 30: 5947-5956, 2017.
Wang. X., Guo, X., Lei, Z., Zhang, C., and Li, S. Z. Exclusivity-cconiisenny regularized multi-view subspace clustering. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 923-931, 2017.
Nguyen, K., Hieu, N. M., Nguyen, V. D., Ho, N., Osher, S., and Nguyen, T. M. Revisiting over-smoo and over- squashing using ollivier-ricci curvature. In International Conference on Machine Learning( (CMMI), volume 202, pp. 25956-25979, 2023.
Wang. Y., Jin, J., Zhang, W., Yu, Y., Zhang, Z., and Wipf, D. Bag of tricks for node classification with graph neural networks, arXiv preprint arXiv:2103.13355, 2021.
Pei, H., Wei, B., Chang, K. C., Lei, Y., and Yang, B. Geom- gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations (ICLR), 2020.
Woodbury, M. A. Inverting modified matrices. Department of Statistics, Princeton University, 1950.
Wu, Q., Zhao, W., Li, Z., Wipf. D. P., and Yan, J. Node- former: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems (NeurIPS), 35:27387-2748 2022.
Sen, P., Namata, G., Bilgic, M., Getoor, I.., Galligher, B., and Eliassi-Rad, T. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Wu, Y., Yao, J., Han, B., Yao, L., and Liu, T. Unraveling the impact of heterophilic structures on graph positive- unlabeled learning. arXiv preprint arXiv:2405.199 2024.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 2021..5800 05866, 2018.

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Xu, J., Ren, Y., Wang, X., Feng, L.., Zhang. Z., Niu, G., and Zhu, X. Investigating and mitigating the side effects of noisy views for self-supervised clustering algorithms in practical multi-view scenarios. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 22957-22966, 2024.
Xu, K., Li. C.,, Tian, Y.. Sonobe, T., Kawarabayashi, K.- i., and Jegelka, S. Representation learning graphs with jumping knowledge networks. In International Con- ference on Machine Learning(ICML), pp. 5453-5462. PMLR, 2018.
Yang, C., Wu, Q., Wang, J., and Yan, J. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. In International Conference on Learning Representations(IILR)) 2023.
Yang, C., Yang, C., Shi, C., Li, Y., Zhang, 7.,, and Zhou, J. Calibrating graph neural networks from data-centric per- spective. In Proceedings of the ACM on Web Conference (WWW), pp. 745-755, 2024.
Yu, L., Sun, L., Du, B., Zhu, T., and Lv, W. Label-enhanced graph neural network for semi-supervised node classi- fication. IEEE Transactions on Knowledge and Data Engineering, 2022.
Yue, H., Zhang, C., Zhang, C., and Liu, H. Label-invariant augmentation for semi-supervised graph classification. In Advances in Neural Information Processing Systems (Neurips), volume 35, pp. 29350-29361, 2022.
Zhang, A., Huang, J., Li, P., and Zhang, K. Building short- cuts between distant nodes with biaffine mapping for graph convolutional networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 18(6):1-21, 2024.
Zhao, J., Wen, Q., Ju, M., Zhang, C., and Ye, Y. Self- supervised graph structure refinement for graph neural networks. In Proceedings of the Sixteenth ACM Inter- national Conference on Web Search and Data Mining (WSDM). pp. 159-167, 2023.
Zheng, C., Zong, B., Cheng, W., Song, D., Ni, J., Yu, W., Chen, H., and Wang, W. Robust graph representation learning via neural sparsification. In International Con- ference on Machine Learning, pp. 11458 11468. PMLR, 2020.
Zhu, X. Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
12

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
A. Complexity
A.1. Complexity of Eq.
As mentioned above, by changing the order of matrix multiplication, the time complexity can be reduced, the Eq. 10 is as follows:
H -1
Q = Q(
N
H
Ie +
H Q(1-1)
1a
(14)
H'H) -1 H H' Q(Q(-11)
H"
Y Le
H
We first let B H [L. 3 HH ("Q(1-1 and compute it from right to left. Specifically, the matrix inversion
operation on a matrix is (ce2). Therefore, the overall time complexity of S E Raxe is O(ne² + c²), where & Then we can compute Q B, likewise, we calculate it from right to left, this can reduce the time complexity from (nn'c) to (nnc). Therefore the overall time complexity of calculating Eq. 10 is O(nc² + c²) This significantly improves the model efficiency.
A.2. Complexity of Eq. 11
Calculating S" by eq.(9) will result in O(n²) computational cost, which leads to significant memory overhead on large datasets. Thus, we first use the Woodbury identity matrix transformation by Appendix B.3, then the Eq. 9 can be transformed as:
1 I- HHEH
1
s" " (HH + BINN
Q
H²
I.
H
H
H²
(15)
Then, we can transform the calculation order to reduce memory and time overhead as follows:
-1 H
S === ="
Ie
H²
B
(16)
Ie H'H) H Q H H"H
We first let P P J. HHT LI.
(I.+ H H and calculate H H, wich time complexity is O(nc²), then we can get
C.X X matrix H H. the time complexity of (I. (HT is O(e²), thus the overall complexity of P is O(nc² + c²).
Finally, the complexity of (p is Onn²c), since is the number of classes, it have Therefore, the complexity grows quadratically with the number of samples i.e., O(
B. Theoretical Proof
B.1. Proof for Proposition 3.1
Proof. We follow the proof idea of (Wang& & Leskovec, 2021), we first introduce a lemma to describe the influence of node on the other node:
Lemma B.1. (Xu et al., 2018) Assume that the activation function of GCN is ReLU. Let pa-b be path
(*),, 1) ... bl0) of length k from node to node Uh. where ((8) Va. (0)) Ub and ((--1) E &Nu for i = ..... ... 1. Then we have the inffuence of node vo on Ub is:
(vb. Uni k)) =
Σ
II
(17)
ph-s k
13

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
where ag ,609 the weight of the edge (u(() v(t-1)).
The total influence is to sum over all lengths of the path. From Lemma B.I, we can easily obtain the influence of all labeled nodes with label on va is
({0b =1)) = Σ Σ
II
oet 12,(0)
(18)
j=1 pb ba (=)
For LPA, is random walk algorithm starting from the label node, denote the classified probability of node va in the y1 dimension (i.e,, category) as Ya [y1]. It is clear that
Yo [y1]'
Ya [v1] EvEc Ya 1/6
s.t.,
Yo lui''
E
II
Bytt 1),(())
(19)
18-30 21
phrn (=)
Thus, we can get ya [y1] x (fvr: : yo = 313.vdl vo).
B.2. Closed-Form Solution
Given the objective function in Eq. 6, we let
Q SH
2
+
i/=1 8
Σ
(20)
Tr((Q()) - SH) - SSH) 23S
where Tr(-) indicates the trace of matrix. Then we have
OC = -2QQQ00 HT 2SHH + 23S
(21)
as
Let Eq. 21 equal to 0, we can obtain the closed-form solution ((0) iee.
s(0 = QH (HH" + BIN)
(22)
B.3. The Woodbury identity
Given four matrices i.e,, A RTx", U E Ro*k B E Rixk V kkx, We adopt variation commonly used by the Woodbury identity (Woodbury, 1950) is as follows:
(A + - A- VA -U)
VA-1
(23)
Without loss of generality, the matrix and can be replaced with the identity matrix, therefore, we further have
(I UV) I U-I+ VU)-Vv
(24)
We can replace the matrices U, V with the matrix H Eq. 24, thus, we have:
1 1/ 82
le + H'H -1
(HH" BIN)
H
H².
(25)
Therefore, based on Eq. 25, we can transform
Q( = 5(1-1) as:
Q ( ((-1))
1
1
(26)
Q(
IN
H
I. +
H H
H (ii-1)
32
14

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
B.4. Proof for Theorem 3.3
Theorem B.2. Given graph with adjacency matrix A, training node label Y and ground truth label Y true. For any unknown-label nodes, tme LP,(A, Y), then the upper bound of the GCN's generalization ability reaches optimal on graph G.
Proof. To prove the Theorem 3.3, We first introduce the Complexity Measure to help us understand the generalization ability of GCN. the current mainstream method to measure the generalization ability the model (Neyshabur et al., 2017), which describes the lower complexity measure means a better generalization ability. We follow (Natekar & Sharma, 2020) to adopt Consistency Representations as our Complexity Measure, which is designed based on the Davies-Bouldin Index (Davies & Bouldin, 1979). Formally, for given dataset and given layer of a model, the Davies-Bouldin Index can be written as follows:
1/p
ne no.
Sa
O
for 1...k
(27)
Na
Ma.b = Il Ho.llp for a, 1....;
(28)
where a, are two different classes, 0 is the GCN smoothed feature of node belonging to class Poo, is the cluster centroid of the representations of class a, here we set = 2, thus S. measures the intra-class distance of class a and Ma. is a measure of inter-class distance between class a and Then, we can define complexity measure based on the Davies-Bouldin Index as follows:
S. S. Ma.b
C
max agth
(29)
1=
We define Po as the probability that a node's neighbor belongs to the 'O-th" class, and 4g as the probability that the node itself belongs to the '0-th" class. Thus, we can calculate the cluster centroid after GCN smoothed features:
oo, E[O E[W JEN;
Σ X'I di
(30)
WT
To(1 - Po)
where X is the j-tth' node feature and μx; is the cluster centroid of the node features of class Likewise, have:
no, = w(hPiux - 11 Pi)
(31)
Then, the 1 can be computed by:
Mo.1 llMo. - Ho.
[W + +o(1 Po)lxx (IPPux, +1(11 P.)Dx.))
[| + TOUxx IoPoux, -IPIN TIMx + Ii Pi
(32)
(loPo + I,Pi) | W(ux 1I + 111OXx - -1pxol
S (JoPo + +.)) W(uxo - -xx)) + +11xx, + +1xxx111
Then S6 is calculated by:
S E 11000 no, 12] E < 0000 MO, 0000 11, >
(1(())) MX.) TWT - Mx.))l
(33)
+ +E|To(1 Po) P.) - ,x, W W(x -xx))
= =13P3E1IW(X, - -xx,) +1 Pb E -xx)
15

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Similarly, have:
of EE |10
- - no. 1E < < 10. μo, >
[[(UIP)(,,P(XII Ux, W
(34)
+ +1 - P1) Pi)(X, - xxx) W(Xo - Mx.))l
= =IPPEIIW(XX xxx + - P3) Mx.)lll
where < <..>> > is inner production. For simplicity, let o (X ux. and W -xx,) then the above equation can then be simplified to:
S = (loPo) (1o(1 Po)) 1 पंंी
(35)
/ + of
Similarly, we have:
- (fPP) + (1,(1 (1)
1 T
(36)
+ o
Then the complexity measure be represented as:
5 S 2So St
20 (Jo + I1)
C=
(37)
M0.1
Vog oo ((lo2' + (1P) W(ex. -x,)ll ||x, + I1xxxll)
Thus, we obtain a lower bound of complexity measure. Also this is the upper bound of the generalization ability. Notice that on and could not be zero, otherwise, the classification problem is meaningless. We observe the above equation for nodes with unknown labels and analysis the relationship between the distribution of label Jo, Iı and the lower bound of complexity measure, we find that the probability of their own label (i.e., Ig or I1) and the probability of their neighbors' labels (i.e., Po or P1) affect the upper bound on their generalization ability. Since To I1 1,, we analyze term (To + P1),
1 Σ Jo Po.: + P1;
(ToPo + [1))=
(38)
where Jo, E {0. 1} is the binary probability that the 'i-th' node label belongs to class O where T1, =1 1 To. and Po.i is the probability that the 'i-t'' node whose neighbor belongs to class O. In order to minimize the lower bound of complexity measure, ie., to maximize the upper bound of generalization ability, it is necessary to maximize (ToPo + I P1) here. Obviously, the maximum (ooPo + Pt) is obtained at fo, = argmar(Pi,tPo.))
Let's look the Label Propagation Algorithm(LPAA. For nodes with unknown labels,
Σ
(39)
de
JEN:
Then the probability that the LPA predicts that the 'i-th" node belongs to class O can be obtained:
To.; argmax 1 Σn=
1, 1
Σ
y 0) argmmar(Pi,,)))
(40)
d
JEN;
JEAS
Similarly, the probability of predicting the 'i-th' node belong to class 1 is:
h = (
Σ
y/
0,
Σ y: = 1) = argmarrPPo..p
(41)
d,
JEN;
JENG
Thus, the upper bound on the generalization ability is maximized when the labels of the unknown label set are distributed as A.A-gennrattd labels.
16

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
B.5. Proof for Theorem 3.4
Theorem B.3. The ELU graph can ensure the generalization ability of the GCN, potentially bringing it closer to optimal performance.
Proof. Recall our objective function (i.e., Eq. (5)) mins ||SY SHIP p. and we first pre-training a GCN (i.e., SH, where H -MLP(X) is trained in advance) to predict labels for all nodes (i.e., Y), thus our objective function can be rewritten as ming SY TIp which align with the form of min ||YY tr and Y is often used to estimate Yerue (Yang et al., 2024; Gong al., 2023). Therefore, the ELU graph (i.e., S) can ensure the GCN's generalization ability certain extent. Moreover, a better adjacency matrix S can further improve the GCN's predictions (i.e., Y), making Y increasingly closer to ground truth (i.e., time). Ultimately, we can obtain graph structure to ensure the GCN's generalization ability is closer to optimal performance.
C. Related Works
This section briefly reviews the topies related to this work, including graph convolutional networks, label propagation algorithms, and graph structure learning.
C.I. GCNs and LPA
Graph convolutional networks (GCNs) are the most popular and commonly used model in the field of graph deep learning. Early work attempted to apply the successful convolutional neural network (CNN) to graph structures. For example, CheybNet (Defferrard et al., 2016) first proposes to transform the graph signal from the spatial domain to the spectral domain through the discrete Fourier transform, and then use polynomials to fit the filter shape (i.e. convolution). CheybNet laid the foundation for the development of spectral-domain graph neural networks. The popular GCN was proposed by Kipf et al. (Kipf& & Welling, 2017), which is a simplified version of ChebyNet and has demonstrated strong efficiency and effectiveness, thereby promoting the development of the graph deep learning field.
Recently, some works have focused on the combination of LPA and GCN. This is because LPA can characterize the distribution of labels spread the graph, which can help GCN obtain more category information. Existing combined LPA and GCN methods can be classified into two categories, i.e., pseudo label methods and masked label methods. Pseudo-label methods let the output of LPA serve as the lseudo-labels to guide the representation learning. For example, PTA (Dong et al., 2021) first propagates the known labels along the graph to generate pseudo-labels for the unlaheled nodes, and second, trains normal neural network classifiers on the augmented pscudo-labeled data, GPL (Wu et al., 2024) uses the output of LPA to preserve the edges between nodes of the same class, thereby reducing the intra-class distance. The masked label methods employ LPA regularization assist the GCN update parameters or structures. For example, UniMP (Shi et al., 2021) makes some percentage of input label information masked at random, and then predicts it for updating parameters. GCN-LPA (Wang & Leskovec, 2021) also randomly masked part of the labels and utilized the remaining label nodes to predict them in learning proper edge weights within labeled nodes. Although the above methods achieve excellent results on various tasks, they fail to explore under what conditions the labels propagated by LPA can best enhance the representation learning of GCNs on unlabeled nodes.
C.2. Graph Structure Learning
Prior to the recent surge in Graph Neural Networks, the study of graph structure learning had already been extensively explored from multiple perspectives within traditional machine learning.
Graph structure learning an important technology in the graph field. It can improve the graph structure and infer new relationships between samples, thereby promoting the development of graph representation learning or other fields. Existing Graph structure learning methods can be classified into three categories, i.e., traditional unsupervised graph structure learning methods, supervised graph structure learning methods, and graph rewiring methods. Traditional unsupervised graph structure learning methods aim to directly learn a graph structure from set of data points in an unsupervised manner. Early works (Wang& & Zhang, 2006; Daitch et al., 2009) exploit the neighborhood information of each data point for graph construction by assuming that each data point can be optimally reconstructed using a linear combination of its neighbors
(i.e., minA AX - X ( Similarly, (Daitch et al., 2009) introduce the weight (i.e., min Σ, DD., - -,, A x, x ||?
17

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Smoothness (Jiang et al., 2019) is another widely adopted assumption on natural graph signals; the smoothness of the graph signals is usually measured by the Dirichlet energy (ie. min 1 Ei, Aii ||X; X, 12 minr, tr XXLX)) Until now, there have been lot of works based on the above objective function to learn graph structure. Supervised graph structure learning methods aim to use the downstream task to supervise the structure learning, which can learn suitable structure for the downstream task. For example, NeuralSparse (Zheng et al., 2020) and PTDNNet (Luo et al., 2021) directly use the adjacency matrix of the graph as a parameter and update the adjacency matrix through the downstream task. SA-SGC (Huang et al., 2023b) learns a binary classifier by distinguishing the edges connecting nodes with the same label and the edges connecting nodes with different labels in the training set, thereby deleting the edges between nodes belonging to different categories in the test set. BAGCN (Zhang al., 2024) uses metric learning obtain new graph structures and learns suitable metric spaces through downstream tasks. The goal of graph rewiring methods is to prevent the over-squashing (Alon& & Yahav, 2021) problem. For example, FA (Alon & Yahav, 2021) proposed to use a fully connected graph as the last layer of GCN to overcome over-squashing. SDRF (Topping et al., 2022), SJLR (Giraldo et al., 2023), and BORF (Nguyen et al., 2023) aim to enhance the curvature of the neighborhood by rewiring connecting edges with small curvature. They increase local connectivity in the graph topology, indirectly expanding the influence range of labels. Despite their success, existing graph structure learning methods cannot ensure that the learned graph structure effectively enables GNN models to leverage supervisory information for unlabeled nodes.
D. Model Detail
D.I. Pretaining MLP
As mentioned in the method section MLP has been trained in advance. Specifically, we employ the two-layer MLP and crosse-entropy to pre-train the MLP:
mmpp
min CE(OO ((2) Y)
(42)
0,082
where (1) and (2) are learnable parameters. After the above objective function converges by the gradient descent algorithm, we can get H as follows:
H = (()
(43)
D.2. Details of Sparse S and Initialize Y
Sparse S S* is a folly-connected adjacency matrix. will bring computationally expensive overhead in message passing, especially for large-scale graph datasets. To mitigate this, we set the elements with small absolute values to O: Specifically, Vi,j where | < 7), we set |S = O, while elements with |St, n remain unchanged, where r) is a non-negative parameter that we usually set to correspond to the top 10 percent of element values. The graph described by S is referred to as the effectively label-utilizing graph (ELU-graph) in this paper.
Initialize Y. Since the number of initial label information is very limited in a semi-supervised scenario, having too many rows of all zeros in Y can cause the algorithm to be unstable. Thus, we propose a label initialization strategy to expand the initial labels with high quality. Specifically, since ELU nodes can effectively utilize the label information and demonstrate high accuracy as shown in Figure 2 (b), we use the pseudo labels of ELU nodes to expand the initial Y.
E. Experiments Details
E.1. Datasets
The used datasets include three benchmark citation datasets (Sen et al., 2008) (i.e., Cora, Citeseer, Pubmed), two co-purchase networks (Shchur et al., 2018) (i.e., Computers, Photo), two web page networks (Pei et al., 2020) (i.e., Chameleon and Squirrel, note that these two datasets are heterophilic graph data), and four social network datascts (Traud et al., 2012) (i.e., Caltech, UF, Hamilton, and Tulane). Table 3 summarizes the data statisties. We list the details of the datasets as follows.
Citation networks include Cora, Citeseer, and Pubmed. They are composed of papers as nodes and their relationships such as citation relationships, and common authoring. Node feature is a one-hot vector that indicates whether word is present in that paper. Words with a frequency of less than 10 are removed.
Co-purchase networks include Photo and Computers, containing 7,487 and 13,752 products, respectively. Edges in
18

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
Table 3. The statistics of the datascts
Datasets
Nodes
Edges
Train/Valid/Pee Nodes
Features
Classes
Cora
2,708
5,429
140/500/1000
1,433
7
Citeseer
3,327
4,732
120/500/1,000
3,703
6
Pubmed
19,717
44,338
60/500/1,000
500
3
Amazon Computers
13,381
245,778
200/300/ 12,88
767
10
Amazon Photo
7,487
119,043
160/240/7 ,084
745
8
Chameleon
2,277
36,101
1,093/729/455
2,325
5
Squirrl
5,201
217,073
(449//1,665// 1,04
2,089
5
Caltech
13,882
763,868
6
6
UF
35,123
2,931,320
21,074/7 ,224/70024
21,07447,02447,02
6
6
Hamilton
2,314
192,788
1,388/463/463
6
6
Tulane
7,752
567,836
5.652/1,550/1,550
6
each dataset indicate that two products are frequently bought together. The feature of each product is bag-of-worde encoded product reviews. Products categorized into several classes by the product category.
Webpage networks include Squirrel and Chameleon, which are two subgraphs web pages in Wikipedia. Our task to classify nodes into five categories based on their average amounts of monthly traffic.
Social networks include Caltech, UF, Hamilton, and Tulane, each graph describes the social relationship in university. Each graph has categorical node attributes with practical meaning (e.g., gender, major, class year.). Moreover, nodes in each dataset belong to six different classes (a student/teacher status flag).
F. Additional Experiments
F.1. Node Classification on Social Networks
Model
Caltech
UP
Hamilton
Tulane
GCN
88.47
83.94
92.26+0.35
87.93
GAT
81.17
81.68+0.59
91.43+11.5
84.45=1145
APPNP
90.7611..88
83.07 10.54
93.2910047
88.52.10.4
GCN-LPA
19.12
83.78+0069
92.5640.87
88.32
GSR
90.23+2.41
84.01 +0063
92.45+0.84
88.75+1.01
Ours
91.93=10.9
85.62:00.3
93.65
89.30=0.77
We further evaluate the effectiveness of the proposed method on the social network datasets by reporting the results of node classification. Obviously, our method achieves the best effectiveness on node classification tasks.
Specifically, the proposed method achieves competitive results on the social network datasets compared to other baselines. For example, the proposed method on average improves by 1.27%, compared the best baseline (i.c., GSR), on almost all datasets. This demonstrates the universality of our method, which can achieve excellent results in most datasets.
F.2. Parameter Analysis
In the proposed method, we employ the non-negative parameters (i.e., X, T, and eta) to achieve trade-off between the supervised loss and the contrastive loss, the temperature control, and the fusion of the ELU graph and the original graph. To investigate the impact of X, and 1) with different settings, we conduct the node classification the Cora and Citeseer datasets by varying the value of X, r. and v in the range of 10.1, 1.0]. Note that the smaller the the closer the model brings the positive samples and the further apart the negative samples. The results are reported in Figure 5 and 6, respectively.
From Figure we have the following observations: First, the proposed method achieves significant performance when the parameter J is in the range of [0.1, 0.3] if values are too large (e.g., 7 > 0.3), the performance degrades. For 7, setting
19

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
to equivalent to using the temperature coefficient. The lower the temperature coefficient, the stronger the effect, indicating that is essential for the proposed method. Note that cannot be set to O because is the denominator. Second, when À is set in the range of [0.3, 0,6], the model can get higher performance, if the value of À is too high or too small (e.g., =0, the results shown in the Table 2), the performance degrades. This indicates that the proposed contrastive loss is necessary for the model.
From Figure 6, for the parameter 7j, the proposed method achieves the best results while the value of the parameter is set in the range of [0.1.0.5]. This further confirms the importance of both the ELU graph and the original graph.
550
345
835
6.
(a) Cora
(b) Citeseer
Figure 5. The classification performance of the proposed method at different parameter settings (f.e., т, A) on the Cora and Citeseer datasets.
F33. Analysis the Improve on VNELU
To better examine the effectiveness of the proposed ELU-GCN on VNELU, we further evaluate the model's improvement over GCN on VNELU on Cora, Citeseer, and Pubmed datasets. The results are shown in Figure 7.
Specifically, the proposed ELU-GCN shows particularly significant improvement on VNELU across the three datasets. For example, our method on average improves by 3.7 on VNELU and 2.1% on all test nodes compared to GCN on these three datasets. This can be attributed to the fact that the proposed ELU-GCN provides the ELU graph that make VNELU utilize the label information more effectively under the GCN framework, and this also indicates that the main improvement of the proposed ELU-GCN is on VNELU.
20

---

Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks
0.84
Dataset
Cora
0.82
Citeseer
0.80
Acc
0.78
0.76
0.74
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
n
Figure The classification performance the proposed method at different parameter settings (i.e, 77) on Cora and Citeseer datascts.
Ours
75
GCN
Ours
70
Ours
GCN
Accuracy
65
GCN
60
55
50
Cora
Citeseer
Pubmed
Figure 7. The accuracy ELU-GCN and GCN of VNELU Cora, Citeseer, and Pubmed datascts.
21


Reviews:
[{"review_id": "ehvqT1cK4j", "reviewer": "Reviewer_3mCS", "summary": "The paper proposes ELU-GCN, a two-stage method. First, it constructs the ELU graph, which enables the message passing in GCN to utilize label information more effectively. After that, a contrastive loss is designed to fuse information between the original graph and the ELU graph.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments. We are so encouraged and will try our best to address the concerns one by one. All changes here will be found in the final version.\n\n>Q1: Limitation on theoretical part: the $\\mathbf{Y} _{true}$ is actually unknown to us, thus this may limit the applicability of the theory.\n\nA1: It is true that $\\mathbf{Y} _{true}$ is unknown to us. However, we can approximate $\\mathbf{Y} _{true}$ using the pseudo-labels predicted by GCN, a common practice in many existing works [1]. This approximation allows us to learn an adjacency matrix \n $\\mathbf{A}$ that ensures strong generalization by Theorem 2.3. By then applying GCN to this learned  $\\mathbf{A}$, we can obtain higher-quality pseudo-labels that more closely approximate $\\mathbf{Y} _{true}$. Through this iterative process, the learned ELU graph progressively refines $\\mathbf{A}$ and pseudo-labels, approaching the optimal structure for generalization.\n\n[1] Calibrating graph neural networks from a data-centric perspective. WWW'24\n\n>Q2: When computing the ELU graph, the paper employs a variant of GCN in the form of Eq.4. However, it remains unclear whether the same form of GCN is also utilized during the contrastive learning phase. This aspect necessitates further clarification.\n\nA2: We ultimately use the standard GCN formulation (Kipf \\& Welling, 2017) in the contrastive learning phase. The variant of GCN in Eq. 4 is introduced solely to facilitate the optimization of the objective function in Eq. 5.\n\n>Q3: To validate the effectiveness of the ELU graph, the authors should compare it with alternative graph construction methods, such as the KNN-graph, by replacing the ELU graph in the ELU-GCN and reporting the corresponding results.\n\nA3: The effectiveness of the ELU graph is demonstrated by its ability to make unlabeled nodes use the label information more effectively while enhancing generalization. However, the KNN graph only considers the feature information, which ignores the impact of labels. To further validate this,  we have added an additional experiment where the ELU graph in ELU-GCN is replaced with the KNN graph for further validation. The results are shown in the table below.\n\n| Datasets | Cora             | Citeseer         | pubmed           | Computers        | Photo            | Chameleon        | squirrel         |\n|----------|------------------|------------------|------------------|------------------|------------------|------------------|------------------|\n| KNN-GCN  | 82.73±0.64       | 72.15±0.34       | 79.57±0.51       | 82.16±3.52       | 90.75±1.54       | 48.16±3.42       | 36.49±3.56       |\n| ELU-GCN  | ***84.29±0.39*** | ***74.23±0.62*** | ***80.51±0.21*** | ***83.73±2.31*** | ***90.81±1.33*** | ***70.90±1.76*** | ***56.91±1.81*** |\n\nIt is evident that replacing the ELU graph with the KNN graph leads to a significant performance drop. This confirms that the ELU graph effectively facilitates the utilization of label information by unlabeled nodes, whereas the KNN graph, which relies solely on feature similarity, fails to capture this crucial aspect.\n\n>Q4: The improvement of NELU nodes after using ELU-GCN should be reported.\n\nA4: We have already conducted this experiment, and the results are presented in Figure 7 of the appendix. This figure illustrates the improvement of NELU nodes after using ELU-GCN.\n\n>Q5: Why can't the two-stage framework proposed in the paper be designed as an end-to-end framework?\n\nA5: While our framework follows a two-stage design, the first stage—constructing the ELU graph—is a parameter-free process. Since this stage does not involve learnable parameters, it cannot be seamlessly integrated into an end-to-end framework. Overall, the ELU graph is firstly precomputed and then used to enhance GCN training in the second stage. This parameter-free approach ensures stability and efficiency in graph construction while keeping the model focused on learning meaningful representations during the second stage. In our future work, we plan to make our framework be an end-to-end one.", "claims_and_evidence": "The paper claims that ELU-GCN enhances label utilization in GCNs through adaptive graph construction and contrastive learning, with experimental results and the paper’s analysis generally supporting this claim.", "methods_and_evaluation_criteria": "The proposed method is based on mathematical derivations and effectively addresses complexity issues encountered in the process, making it a reasonable approach. The evaluation criteria are appropriate for studies in this field.", "theoretical_claims": "The paper provides interesting theoretical claims and the proofs appear sound, but there are still some limitations. For example, the $Y_{true}$ is actually unknown to us, thus this may limit the applicability of the theory.", "experimental_designs_or_analyses": "The experimental design is reasonable, validating the proposed model from the perspectives of effectiveness, ablation study, runtime analysis, etc. Notably, the visualization of the key ELU graph helps provide a clearer understanding of the ELU graph.", "relation_to_broader_scientific_literature": "The paper builds upon graph structure learning, further considering and enhancing the influence of label information on unlabeled nodes. Additionally, it introduces the new contrastive learning paradigm to improve the integration of learned graph structures with the original graph information.", "essential_references_not_discussed": "As far as I know, no essential references have been overlooked.", "other_strengths_and_weaknesses": "Strengths: \n\n1. The paper studies an interesting problem: promoting the positive impact of label information on unlabeled nodes. \n\n2. The proposed method is relatively novel and reasonable. \n\n3. Theoretical analysis enriches the foundation of this work.\n\nWeaknesses: \n\n1. When computing the ELU graph, the paper employs a variant of GCN in the form of Eq.4. However, it remains unclear whether the same form of GCN is also utilized during the contrastive learning phase. This aspect necessitates further clarification.\n\n2. To validate the effectiveness of the ELU graph, the authors should compare it with alternative graph construction methods, such as the KNN-graph, by replacing the ELU graph in the ELU-GCN and reporting the corresponding results. \n\n3. The improvement of NELU nodes after using ELU-GCN should be reported.", "other_comments_or_suggestions": "Please reply or modify according to the Weaknesses mentioned above.", "questions_for_authors": "Why can't the two-stage framework proposed in the paper be designed as an end-to-end framework?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LOZb4QWKQH", "reviewer": "Reviewer_vmVu", "summary": "This paper proposed a new GCN framework called ELU-GCN, which aims to better propagate the label information to unlabeled nodes. First, by analyzing which situation can achieve effective label utilization for unlabeled nodes, the authors proposed an objective function that can guide the GCN to effective label utilization. Then, a graph regularization is designed to capture the consistency and mutually exclusive information between the original and the ELU graphs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments. We are so encouraged and will try our best to address the concerns one by one. All\nchanges here will be found in the final version.\n\n>Q1: The real SOTA GNN mode such as GCNII[1] needs to be compared. [1] Chen M, Wei Z, Huang Z, et al. Simple and deep graph convolutional networks.ICML.\n\nA1: We have added a comparison with GCNII in the updated experiments as following table. The results show that, on the Cora dataset, GCNII performs a little bit better, but on the other six datasets, our method outperforms GCNII. We will include these results in the next version for further clarification.\n\n| Datasets | Cora           | Citeseer       | pubmed         | Computers      | Photo          | Chameleon      | squirrel       |\n|----------|----------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| GCNII    | **85.49±0.52** | 73.41±0.63     | 80.28±0.41     | 82.53±4.02     | 87.48±2.14     | 62.48±2.54     | 48.17±2.04     |\n| ELU-GCN  | 84.29±0.39     | **74.23±0.62** | **80.51±0.21** | **83.73±2.31** | **90.81±1.33** | **70.90±1.76** | **56.91±1.81** |\n\n>Q2: Figure 2 gives the experimental conclusion very abruptly. The specific experimental details of Figure 2 need to be supplemented.\n\nA2: Thank you for your suggestion. The experimental setup for Figure 2 follows the same configuration outlined in Section 3. The specific details of the experimental setup can be found in the appendix. We will enhance the explanation of this section in the next version to provide more clarity.\n\n>Q3: In Eq. 12, it is necessary to explain what specific distance function is used and why it is chosen.\n\nA3: In Eq. 12, various distance functions, such as Euclidean distance and inner product, can be considered. Based on experimental results, we found that Euclidean distance performed better in our case.\n\n>Q4: From Theorem 2.3, can this also be understood as: if an adjacency matrix A makes LPA (AY) perform better, then it would also be better for GCN? Would this inspire the use of a more lightweight and parameter-free LPA instead of GCN to find a better graph structure?\n\nA4: Yes, I agree with your opinion. Based on Theorem 2.3, if a graph structure $\\mathbf{A}$ enables LPA to achieve better performance, it means that GCN can achieve better generalization ability on this graph structure $\\mathbf{A}$. This suggests that a lightweight and parameter-free LPA can serve as a criterion for evaluating graph structures or even as an objective function in graph structure learning. In fact, our method can also be seen as optimizing the graph structure $\\mathbf{A}$ to improve LPA performance as much as possible.", "claims_and_evidence": "The majority of the claims are well-supported by empirical results and theoretical analysis.", "methods_and_evaluation_criteria": "The proposed ELU-GCN makes sense for the GNN field. The selected datasets include both homophilic and heterophilic graphs, making the evaluation relatively comprehensive.", "theoretical_claims": "This paper provides additional theoretical analysis, and the theoretical proof is complete and reasonable.", "experimental_designs_or_analyses": "I have reviewed the experimental design and analyses, and while they are generally sound, there are some areas that could be improved. For example, the real SOTA GNN mode such as GCNII[1] needs to be compared.\n[1] Chen M, Wei Z, Huang Z, et al. Simple and deep graph convolutional networks.ICML.", "relation_to_broader_scientific_literature": "GCN-LPA also studies the impact of labels, but the author claims the differences and Strengths of GCN-LPA in the paper.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths\n1. This paper is well-written and clearly structured.\n\n2. The proposed ELU-GCN is novel.\n\nWeaknesses:\n\n1. Figure 2 gives the experimental conclusion very abruptly. The specific experimental details of Figure 2 need to be supplemented.\n\n2. There are many hyperparameters in this paper. Although the author has analyzed the sensitivity of some hyperparameters, some important parameters have not been analyzed, such as the number of iterations used to calculate the ELU graph.\n\n3. In Eq. 12, it is necessary to explain what specific distance function is used and\nwhy it is chosen.", "other_comments_or_suggestions": "See weaknesses.", "questions_for_authors": "From Theorem 2.3, can this also be understood as: if an adjacency matrix A makes LPA (AY) perform better, then it would also be better for GCN? Would this inspire the use of a more lightweight and parameter-free LPA instead of GCN to find a better graph structure?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ryCrYvoHWN", "reviewer": "Reviewer_Dm6W", "summary": "This paper introduces ELU-GCN which enhances label utilization in GCNs. First, it constructs an ELU graph to optimize label influence on unlabeled nodes. Then, a contrastive loss is designed to enhance representation learning by integrating information from both the ELU graph and the original graph. The experiments on multiple datasets show its superiority over existing approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments. We are so encouraged and will try our best to address the concerns one by one. All changes here will be found in the final version.\n\n>Q1: The core idea is to ensure that the prediction of GCN is consistent with the output of LPA. However, this may be problematic—Why not constrain the GCN output to align with the LPA during training? Moreover, this approach does not seem to be effective.\n\nA1: First, we would like to clarify that our method does not simply force GCN predictions to align with LPA; rather, LPA outputs should also align with GCN predictions. Therefore, directly constraining the GCN output to match LPA is inappropriate. Instead, our approach aims to find a new graph structure that naturally ensures consistency between GCN and LPA outputs, allowing the prediction of GCN to utilize label information effectively (see Section 2.1).\n\n>Q2: Some details of the experimental settings are missing, such as learning rate, weight decay, number of hidden units, etc.\n\nA2: We set the weight decay to \n5e-4. The learning rate was selected from [0.01, 0.02] for all datasets, and the number of hidden units was chosen from [4, 8, 64, 128]. We will include these details in the revised version of the paper to ensure clarity and completeness.\n\n>Q3: The subscript notation of $\\mathbf{Y}$ is confusing. In Notation, $\\mathbf{Y}_{l}$ is defined as the training set label, and then $\\mathbf{Y}$ becomes in Eq. (13) and Theorem 2.3. Please check and unify.\n\nA3: Thank you for your careful observation. We acknowledge the inconsistency in the subscript notation of \n$\\mathbf{Y}$. In the notation section, \n$\\mathbf{Y} _{l}$ refers to the training set labels, and the same meaning should be maintained in Eq. (13) and Theorem 2.3. We will revise the notation to ensure consistency and clarity in the next version.\n\n>Q4: The $\\mathbf{S}^{*}$ calculated by Eq. (11) looks like a dense matrix (almost no zeros), so it consumes a lot of memory and time for subsequent matrix multiplication.\n\nA4: You are correct that \n$\\mathbf{S}^*$ computed from Eq. (11) is a dense matrix, which could lead to high memory and computational costs for subsequent matrix multiplications. However, we apply a sparsification process to  $\\mathbf{S}^*$ to mitigate this issue. Specifically, $ \\forall i,j$ where $ |\\mathbf{S}^* _{i,j} | < \\eta$, we set $|\\mathbf{S}^* _{i,j} | = 0$, while elements with $ |\\mathbf{S}^{*} _{i,j} | > \\eta$ remain unchanged, where $\\eta$ is a non-negative parameter that we usually set to correspond to the top 10 percent of element values. The details of this process are already provided in the appendix.\n\n>Q5: The authors mention heterophily graphs but do not give any definition.\n\nA5: We acknowledge the omission and will provide a clear definition of heterophily graphs in the revised version. Generally, heterophily graphs refer to graphs where connected nodes tend to have different labels, in contrast to homophily graphs where connected nodes are more likely to share the same label.\n\n>Q6: I would like to ask whether this framework can be used for GAT.\n\nA6: Although our method is specifically designed for GCN, we have added experiments applying the ELU graph to GAT. \n\n| Datasets | Cora           | Citeseer       | Pubmed         | Computers      | Photo          | Chameleon      | Squirrel       |\n|----------|----------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| GAT      | 83.03±0.71     | 71.54±1.12     | 79.17±0.38     | 78.01±19.1     | 85.71±20.3     | 40.72±1.55     | 30.26±2.50     |\n| ELU-GAT  | **84.89±0.39** | **74.53±0.49** | **80.23±0.41** | **80.36±5.36** | **88.43±1.85** | **60.17±2.14** | **50.47±1.04** |\n\n\nThe results show that the ELU graph also positively impacts GAT, demonstrating its effectiveness for GAT as well.", "claims_and_evidence": "The claims in the paper are supported by both experimental and theoretical evidence. The authors have validated the effectiveness of the proposed method on multiple datasets. However, some of the assumptions in the paper may be problematic. Specifically, the core idea is to ensure that the prediction of GCN is consistent with the output of LPA. However, this may be problematic—Why not constrain the GCN output to align with the LPA during training? Moreover, this approach does not seem to be effective.", "methods_and_evaluation_criteria": "The proposed method is feasible, and its effectiveness has been validated on a total of 11 datasets.", "theoretical_claims": "The proof of the theory seems to be sound.", "experimental_designs_or_analyses": "The authors verified the effectiveness of the method on multiple benchmark datasets and conducted detailed comparative experiments and statistical analysis. However, some details of the experimental settings are missing, such as learning rate, weight decay, number of hidden units, etc.", "relation_to_broader_scientific_literature": "The key contributions of the paper are closely related to the existing literature, such as GCN-LPA and graph contrastive learning. Building on a thorough citation of relevant research, the authors propose a new method that addresses the issue of label information not being effectively utilized by GCNs.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Besides the strengths and weaknesses mentioned above, the paper has the following additional strengths and weaknesses.\n\nOther Strengths:\n- The paper is well-written.\n- The experiment is quite sufficient.\n\nOther weaknesses:\n- The subscript notation of $\\mathbf{Y}$ is confusing. In Notation, $\\mathbf{Y}_{l}$ is defined as the training set label, and then becomes $\\mathbf{Y}$ in Eq. (13) and Theorem 2.3. Please check and unify.\n- The S* calculated by Eq. (11) looks like a dense matrix (almost no zeros), so it consumes a lot of memory and time for subsequent matrix multiplication.\n- The authors mention heterophily graphs but do not give any definition.", "other_comments_or_suggestions": "Please check the citation format and distinguish the use of \\cite and \\citet. For example, in the last sentence of the second paragraph of the Introduction, Bi et al should use \\citet instead of \\cite.", "questions_for_authors": "I would like to ask whether this framework can be used for GAT.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NO"}}, {"review_id": "kaRT0G6ECg", "reviewer": "Reviewer_sZPZ", "summary": "The paper focuses on the impact of labels on unlabeled nodes, the authors propose that the label information is not always effectively utilized in the traditional GCN framework. Thus, this paper proposes the ELU-GCN to solve this issue. First, the paper proposed a new objective function to ensure the graph structure effectively propagates label information under the GCN framework. Second, the paper proposes new contrastive learning to capture consistent and mutually exclusive information between the two graphs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments. We are so encouraged and will try our best to address the concerns one by one. All changes here will be found in the final version.\n\n>Q1: Lack of baselines. Since the authors designed a new contrastive learning method, it is necessary to compare it with the contrastive learning method.\n\nA1: We acknowledge the importance of comparing our method with existing contrastive learning methods. To address this, we compared the typical graph contrastive learning GRANCE[1] and the recent graph contrastive learning method (SGCL[2]). We can observe that our method consistently outperforms the two contrastive learning baselines across all datasets.\n\n[1] Deep graph contrastive representation learning. ICML'20 \n\n[2] Rethinking and Simplifying Bootstrapped Graph Latents. WSDM'24\n\n| Datasets | Cora           | Citeseer       | pubmed         | Computers      | Photo          | Chameleon      | squirrel       |\n|----------|----------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| GRACE    | 83.30±0.40     | 72.10±0.50     | 79.86±0.12     | 81.86±3.86     | 88.72±2.07     | 46.75±2.47     | 38.16±3.14     |\n| SGCL     | 83.54±0.40     | 72.58±0.25     | 80.09±0.53     | 81.67±2.59     | 89.07±2.45     | 55.36±1.28     | 42.34±1.47     |\n| ELU-GCN  | **84.29±0.39** | **74.23±0.62** | **80.51±0.21** | **83.73±2.31** | **90.81±1.33** | **70.90±1.76** | **56.91±1.81** |\n\n>Q2: The discussion on contrastive learning in graphs is somewhat lacking. The proposed Eq. (12) is a paradigm of contrastive learning. The author should further discuss its difference and connection with contrastive learning loss, such as InfoNCE.\n\nA2: A key difference is that in InfoNCE, the same node in different graph views is treated as a positive sample, while different nodes are treated as negative samples. In contrast, Eq. (12) distinguishes ELU nodes and NELU nodes, ensuring that ELU nodes maintain consistency across graphs while NELU nodes are pushed apart. This means that Eq. (12) incorporates structural information specific to label influence in GCNs, rather than relying solely on node (instance) discrimination as in InfoNCE. We will clarify this point in the revised version.\n\n>Q3: The proposed method seems a bit complicated, therefore I am concerned about its reproducibility.\n\nA3: In fact, our method is simple to implement in practice. The computation of the ELU-graph is a parameter-free process, and the Woodbury trick significantly accelerates matrix operations. Moreover, we have already provided the code link in the supplementary material and commit to open-sourcing it to ensure full reproducibility.\n\n>Comment: There are some minor errors that need to be carefully checked, such as whether the comma or period at the end of the formula is correct.\n\nThank you for your careful review. We will thoroughly check and correct any minor errors, including punctuation issues in the formulas.\n\n>Comment: The paper directly mentions LPA and GCN, but there is no introduction to them. The author should briefly introduce them in the notation or appendix.\n\nThank you for your suggestion. We will add brief introductions to LPA and GCN in the notation section or appendix to improve clarity.", "claims_and_evidence": "- The experimental results demonstrate that ELU-GCN outperforms existing methods on multiple datasets, particularly on heterophilic graphs like Chameleon.\n- The motivation is reasonable.\n- Theoretical proof is basically reasonable.", "methods_and_evaluation_criteria": "- The proposed two-stage method is clear and promising.\n- The Woodbury identity trick effectively reduces the computational complexity of ELU-graph, making the framework more efficient.\n- The paper uses 11 public datasets, covering both homophilic and heterophilic graphs, making the evaluation fairly comprehensive.", "theoretical_claims": "- The theoretical analysis appears mathematically sound.", "experimental_designs_or_analyses": "Strength: \n- The experimental setup and dataset selection are reasonable.\n\nWeakness: \n- Lack of baselines. Since the authors designed a new contrastive learning method, it is necessary to compare it with the contrastive learning method.", "relation_to_broader_scientific_literature": "Strength: \n- The paper provides a well-structured overview of LU-GCN and the differences and advantages over previous methods are also explained.\n\nWeakness: \n- The discussion on contrastive learning in graphs is somewhat lacking.", "essential_references_not_discussed": "- The essential references are discussed.", "other_strengths_and_weaknesses": "Other Strengths:\n- The issue the paper focuses on is interesting i.e., Enhancing the use of label information by unlabeled samples.\n- Overall, the paper is complete and inspiring.\n\nOther Weaknesses:\n- The proposed Eq. (12) is a paradigm of contrastive learning. The author should further discuss its difference and connection with contrastive learning loss such as InfoNCE.\n- The proposed method seems a bit complicated, therefore I am concerned about its reproducibility.", "other_comments_or_suggestions": "- There are some minor errors that need to be carefully checked, such as whether the comma or period at the end of the formula is correct.\n- The paper directly mentions LPA and GCN, but there is no introduction to them. The author should briefly introduce them in the notation or appendix.", "questions_for_authors": "See weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a two-step framework. ELU-GCN, to improve the effectiveness of labels. It learns a new graph structure and designs a new graph contrastive learning by exploring the relationship between the learned graph and the original graph. Theoretical and experimental justifications demonstrate its superiority in generalization ability. The claims are supported by clear and convincing evidence. The proposed method makes sense. Reviewers believe the proposed method is novel and that theoretical analysis is solid. After rebuttal, one reviewer increases his ratings. All reviewers agree to this paper.
Decision: Accept (poster)