Optimal Block-wise Asymmetric Graph Construction for Graph-based Semi-supervised Learning
Authors: Zixing Song
Yifei Zhang
Irwin King
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph-based Semi-supervised Learning
Affinity Graph Construction

Abstract: Graph-based semi-supervised learning (GSSL) serves as a powerful tool to model the underlying manifold structures of samples in high-dimensional spaces. It involves two phases: constructing an affinity graph from available data and inferring labels for unlabeled nodes on this graph. While numerous algorithms have been developed for label inference, the crucial graph construction phase has received comparatively less attention, despite its significant influence on the subsequent phase. In this paper, we present an optimal asymmetric graph structure for the label inference phase with theoretical motivations. Unlike existing graph construction methods, we differentiate the distinct roles that labeled nodes and unlabeled nodes could play. Accordingly, we design an efficient block-wise graph learning algorithm with a global convergence guarantee. Other benefits induced by our method, such as enhanced robustness to noisy node features, are explored as well. Finally, we perform extensive experiments on synthetic and real-world datasets to demonstrate its superiority to the state-of-the-art graph construction methods in GSSL.

Optimal Block-wise Asymmetric Graph Construction for Graph-based Semi-supervised Learning
Zixing Song
Yifei Zhang
The Chinese University of Hong Kong New Territories, Hong Kong SAR zxsongâcse. cuhk. edu. hk
The Chinese University of Hong Kong New Territories, Hong Kong SAR yfzhang@cse cuhk. edu cdu.hk
Irwin King
The Chinese University of Hong Kong New Territories, Hong Kong SAR kingdcse. cuhk. edu. hk
Abstract
Graph-based semi-supervised learning (GSSL) serves as powerful tool to model the underlying manifold structures of samples high-dimensional spaces. involves two phases: constructing affinity graph from available data and inferring labels for unlabeled nodes on this graph. While numerous algorithms have been developed for label inference, the crucial graph construction phase has received comparatively less attention, despite its significant influence on the subsequent phase. In this paper, we present optimal asymmetric graph structure for the lahel inference phase with theoretical motivations. Unlike existing graph construction methods, differentiate the distinct roles that labeled nodes and unlabeled nodes could play. Accordingly, we design an efficient block-wise graph learning algorithm with a global convergence guarantee. Other benefits induced by our method, such as enhanced robustness to noisy node features, are explored as well. Finally, we perform extensive experiments synthetic and real-world datasets demonstrate its superiority to the state-of ofte----theearr graph construction methods in GSSL.
Introduction
Braph-based semi-supervised learning (GSSL) is a burgeoning research field [52, 9, 14, 63, 65, 62). As a subclass of semi-super learning (SSL), GSSL exhibits promise since it encapsulates the smoothness or manifold assumption, where samples with similar features are likely to share the same label. GSSL methods begin by constructing affinity graph, wherein nodes represent samples, and weighted edges denote similarity between pairs of nodes. This process aligns with the manifold assumption, implying that nodes connected by edges with large weights tend to have the same label. Upon obtaining the affinity graph, various label inference algorithms such as label propagation [85, 82, 25, 65] can be executed to predict labels for the unlabeled nodes.
Preliminary empirical studies [16] suggest that the quality of the affinity graph significantly influences label prediction performance. However, the graph construction phase in GSSL has received less scrutiny compared to the subsequent label inference phase. Constructing a high-quality graph presents challenge its quality only be assessed indirectly through postmortem verification via label inference performance. Classic solutions such as the Radial Basis Function (RBF) Kernel [85], kNN graph [17], and b-matching [26), while simple, may exhibit low robustness against noise due their simplicity. More recent and complex methods, typically framed as optimization problems to find
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the optimal graph under the smoothness assumption, suffer from inefficient optimization techniques without fast convergence guarantees [18, 29, 63] or lack a solid theoretical foundation [58, 14, 23).
Consequently, a series of research questions arise: 1) What is the optimal graph structure for label inference algorithms in GSSL? 2) How can we optimize this optimal graph efficiently? 3) What kinds of benefits can this optimal graph bring?
Most existing GSSL graph construction methods treat all nodes equally, disregarding label infor- mation, which results a symmetric, undirected graph. However, we contend that an asymmetric, directed graph structure might be more beneficial for subsequent label inference due to the distinct roles labeled and unlabeled nodes can play. Intuitively, edges from labeled to unlabeled nodes would naturally facilitate supervision information propagation, while edges from unlabeled to labeled nodes may introduce inconsistency, potentially undermining the prediction accuracy for the labeled nodes.
Motivated by this key observation, we revisit unified optimization framework that encompasses most label inference algorithms, assuming the affinity graph is already constructed. We then fix the downstream label inference result and position the graph weight matrix (or adjacency matrix) as the optimization variable. This shift allows us to define optimality in the graph construction step of GSSL concisely, addressing our first research question. We subsequently present tailored optimal solution featuring an asymmetric graph structure that aligns with our proposed intuition. In response, we introduce the Block wise Affinity Graph Learning (BAGL) algorithm by leveraging duality and the fast proximal gradient method, addressing our second research question. Finally, we demonstrate that BAGL ensures sub-linear global convergence rate of O(1/k) and can alleviate issues of noisy node features, addressing our third research question.
In summary, this work offers four main contributions. First, we provide a succinet definition of the optimality of the affinity graph in GSSL, and through rigorous derivation, propose an ad-hoc solution with an asymmetric structure. Second, we design block-wise graph learning framework, BAGL, to infer the weights in the optimal graph structure. Third, we prove that a global sub-linear convergence rate is guaranteed for BAGL and analyze other benefits. Fourth, we perform extensive experiments on synthetic and real-world datasets to demonstrate the effectiveness and efficiency of BAGL.
2 Preliminary
2.1 Problem Formulation
We present a formulation for the GSSL problem, comprising two steps: graph construction and label inference [52]. Our study primarily investigates the optimal construction of the affinity graph in the first phase to facilitate enhanced performance in the second label inference phase.
Given a set of data points (=:) where each æ; Rd is sampled from a d dimensional feature space. In this paper, we interchangeably use the terms node, point, and sample to refer to 22 Each sample an has label y: No. where N, = {i E N+ 1 < S c} with e being the number of classes. Given the labels of the ( samples {z,) as {y: 1_ the ultimate goal of general transductive SSL infer the labels {ur ) for the remaining u unlabeled samples { (-+41 (n [+ u). As subcategory of general SSL. GSSL methods first construct a graph g = (V, E, W) based on all the training samples {x. ) and partially given labels {ur Y Here, V is the node set with [
Each node represents each sample x., is the edge set in which each edge (i, ) is assigned with weight Wij (the i-th row, j-th column entry in W E R=xm) reflect the affinity
similarity
between the sample pair (I,, xy)) Generally, a larger weight indicates a higher level of similarity. Wi = 0 indicates no edge between node i and node j. Therefore, the key challenge in the first graph construction step is to generate W based on {x and {v,) that the underlying manifold of the data is properly encoded. In the second step, various label inference algorithms can he performed on g to propagate the given labels {ur and make predictions fu for unlabeled nodes.
However, the performance of the label inference step is significantly contingent on the quality of the weight matrix W from the first graph construction step. This paper aims to address three critical research questions pertaining to the graph construction step in GSSL. First, what constitutes the overall structure of the optimal weight matrix, W*? (Sect. 3.1.. We define the optimal weight matrix, W* as the one that gives the best prediction results when used with the same label inference method

---

across different graphs W. Second, how to find an efficient method for optimizing the entries in W*? (Sect. 3.2). Third, what kinds of benefits can W bring from the theoretical perspective? (Sect. 3.3)
2.2 Recap on the Unified Framework for Label Inference Step in GSSL
Before we delve into the proposed structure for the optimal affinity graph, we first revisit the unified framework of the label inference step, allowing for seamless definition of the optimal affinity graph.
we assume the affinity graph has been constructed, then numerous influential label inference methods [85, 82, 83, 4, 5, 9] can be performed over this graph to infer the labels for the unlabeled nodes. However, the majority of them can be incorporated into the following framework.
We first define the node feature matrix X E Baxd as X = [T), ... :T,] and the predicted soft label matrix F E Raxe as F [f 1................... fal T with f. E ( Sis n). Ground-truth label matrix is given as Y y -.al E (0. 1jaxe with y, E 1) (1 sis n). Here, for the labeled nodes { y; is a one-hot vector in which Y otherwise. For the unlabeled nodes {æ; ( D; is an all-zero vector for initialization.
if æ; belongs to class j (y/ j), and Yi 0,
Driven by the geometry of the affinity graph, we can unify these label inference algorithms minimizer of the optimization problem as Problem (I).
F= arg min (F)) = arg min (Tr (FTSF) + TI ((F ((F-((F))))) Y)TA(F -)).
(I)
Note that the loss function (F) consists of a quadratic variation term Tr (FTSF) the graph smoothness regularizer, and a quadratic Frobenius error norm | Y (F(( (FFF-Y-YFYY) both of which should ideally be small subject
off parameter A between them. Here the smoothing matrix S = s( (W) E S in the first term, with s: R=x= - S is positive semidefinite and determined by the weight matrix W of the graph to ensure the adjacent nodes share similar predictions. The second term measures the distance between predicted results and initial assignments, and restricts the output for labeled nodes from deviating too much compared with the ground-truth. is a diagonal matrix with Au 2 O and S + A must be invertible to avoid trivial solutions.
By the first-order optimality condition, we can easily obtain the optimal solution for Problem (1).
F" = (S + - AY = (s(W) + A)- AY.
(2)
Based the optimal soft label matrix F", the final predicted label for each node is given as Ú: = =(f,) = arg sajee F It is worth noting that the unified optimization framework in Problem (1) admit most of the mainstream GSSL methods. For instance, if we set the smoothing
matrix as the normalized graph Laplacian matrix S = L = s(W) = D à (D W)D and A- AI, can easily recover one of the most popular label inference methods for GSSL,
Local and Global Consistency (LGC) [82], as F = arg min p Ei to. VD W
f,
EE y 111)). Here, E ST is defined as L D LD- where the combinatorial Laplacian matrix L St is given L D W, and the degree matrix D Raxx is diagonal matrix defined D.. Σラ= Waz. We summarize several representative works under this unified framework Table with explicit forms S (or s(W) and A in Appendix B.2.
3 Methodology
3.1 Motivation: Optimal Affinity Graph Structure
3.1.1
Definition of the Optimality of the Affinity Graph
If we perform the same label inference algorithm from the above-mentionel generalized framework on all possible affinity graphs W, the optimal graph W' will enable the label inference step to obtain the most accurate predictions. Under the above-mentioned unified framework for label inference (Problem (1)), the weight matrix W is fixed while the soft label matrix F is the optimization variable. This is due to our goal of executing label inference to attain the optimal F" given the affinity graph W. Similarly, when we want to construct the optimal graph W* given the label inference framework.
3

---

we consider the weight matrix W as the optimization variable, keeping the soft label matrix F fixed as the solution in Eq. (2). The form of Q(-) remains unchanged
related to the generalization bound for GSSL that would be discussed in Appendix D.2. This approach aids in identifying the "optimall" affinity graph for the label inference algorithms under the unified framework.
Definition 1 (Optimality of the Affinity Graph), The affinity graph G is optimal for label inference under the unified GSSL framework if its weight matrix W is the minimizer of Problem (3).
min (Tr(FF&(W)DD) WERnXm
Tr ()TA(F Y))
s.L. F= (s())
AY, (3)
Although the optimization Problem (3) is intractable in general due to the various forms of s ()) in the constraint, we can present an ad-hoc optimal structure of W* that is independent of s (W),
which motivates our proposed method in Sect. 3.2 from a theoretical perspective.
3.1.2 Structure of the Optimal Affinity Graph
We then present equivalent proposition in Theorem 1, which provides a necessary and sufficient condition for the optimality of W in Problem (3). Motivated by some classic graph sharpening techniques [47, 15, 46), Theorem 1 helps to eircumvent the challenges of directly dealing with Problem (3) and holds regardless of the forms of s(W) (Appendix E.1).
Theorem 1. W obtained by Definition is optimal if and only if YY = Fi holds. Yi E (0, 1 Fi E RIxe are the ground-truth label matrix, and the soft label matrix for labeled nodes.
To put it in a simpler way. Theorem tells us that if the affinity graph is optimal, then after we perform the label inference algorithm for GSSL, the predicted soft label for the labeled nodes would coincide with the ground truth precisely. The converse of this observation also holds true. Unfortunately, it remains an open question to solve Y; F, by listing all possible classes of solutions due to the complex interconnection of F and W. However, we can provide a simple ad-hoc solution for Y = Fi in Proposition 1. For one thing, this asymmetric graph structure, in the theoretical sense, conforms to the intuition of the better affinity graph we discussed earlier. For another, also sheds some light the proposed optimization framework to infer the weights in this graph structure later. Proposition 1. If W can be expressed as (4), W is an optimal solution given by (3) in Definition 1.
0
0
W = W
W
where W.. at E Ruxi and W., uu E Ruu can be non-zero submatrices with arbitrary entries.
Proposition 1 provides an ad-hoc solution to Problem (3) (Appendix E.2). If the constructed graph is asymmetrical with edges from unlabeled nodes to labeled nodes only, then it is optimal by Definition 1. This asymmetrical optimal graph structure answers the first research question in Sect. 2.1.
The optimal asymmetric graph structure presented in Proposition I offers meaningful interpretations and notable advantages. It effectively eliminates the influence from unlabeled nodes to labeled nodes by enforeing Wi a and Wi. to be zero matrices. This aligns with the intuition that label information should be propagated from labeled nodes to unlabeled nodes in the GSSL methods, rather than the other way around. More technically, when applying the classic label inference algorithm LGC [82] on this optimal graph structure, the soft label matrix for unlabeled nodes now becomes F. u (I - pW uu) - - W Y with some constant 0 < μu < This formulation indicates that the LGC algorithm spreads supervision information from labeled nodes to unlabeled nodes once through W W,,Y,, followed by propagating this information solely among unlabeled By Theorem 1, this optimal
nodes through (I ,W -w--- I + wW uu + w22 au asymmetric graph guarantees zero empirical risk on the labeled nodes. Moreover, many existing graph construction methods in GSSL primarily focus on node features while disregarding label information. Consequently, these methods may produce heterophilous edges that connect nodes with similar features but different labels. Such edges violate the manifold assumption in GSSL, where nodes with the same label tend to be linked. During the label inference step, the label information of these nodes connected by heterophilous edges confuses each other during propagation, resulting in misleading predictions. By setting W 0, our method eliminates these heterophilous edges completely. As result, increases the edge homophily ratio of the constructed graph and enhances the robustness of subsequent label inference algorithms, validated in Appendix D.I.

---

3.2 Implementation: Block-wise Graph Learning Algorithm
3.2.1 Framework
By differentiating the roles that labeled and unlabeled nodes would play, we arrive at an optimal structure for the affinity graph in Proposition 1. However, efficient algorithm infer the exact weights or entries for blocks in Eq. (4) is still in demand. Motivated by previous works [29, 30, 19), make the following reasonable restrictions or assumptions on W obtain more meaningful graph for GSSL. First, the features for two directly connected nodes should not vary too much, no matter whether they are labeled or not. This agrees with the manifold assumption in GSSL, where links tend to form between similar nodes. Violation of this fundamental assumption usually causes significant performance drop in the label inference step. Second, the constructed graph should be well-connected in terms of both W and W au to ensure the supervision information could propagate freely among all nodes. Otherwise, some disconnected nodes may never receive any label information. Third, it is desirable to control the sparsity of the graph, avoiding an overly sparse or overly dense graph. We will empirically demonstrate the effects of the sparsity control later. We propose two similar optimization frameworks for W at and W a. in Eq. (4) as Problem (5) and (6).
lall W min W at Zuilla 01 1 log W 1) 01 1 log WT w 1) B1 W We
s.t. W ol 0. (5)
min | un Zuulli 0z 1 log( W ...1 a:2 1 log( WT an W.. sm
1) + 32 W wwulliee ww S. au 0. (6)
Zu
ZT
Here, we define the pairwise distance matrix Z
E R with Zij 20, 2
Z.c
Z
Zun
@ is the Hadamard product and log(-) is the element-wise logarithm operator. Since Problem (5) and (6) share the same form, we will only focus on Problem (5) as an example. The first term | ut @ Zuill1 Eisiga,isjst Waylla,- æ; 11 encourages similar nodes to be connected with larger weights, meeting the manifold assumption. The second and third logarithmic barrier term act on the out-degree and in-degree vectors to make sure that each unlabeled node is connected by at least one labeled node and vice versa, improving the overall connectivity of the graph. The last Frobenius norm term measures the sparsity of the graph. The parameters a1, a2 81, 32 are positive.
3.2.2 Optimization
For convenience of presentation, we view the entries in W.. al (W... u.) as a new vector w = vec W ai] Ry. Similarly, we have vee zul Ryl Accordingly, a linear mapping ma- trix T, E {0, 1) uxuu transforms the edge weights the corresponding out-degree vector (i.e. Tiw = W w.. Similarly, we have T2w = WT w for the in-degree vector. Further, if we let TT = (TI,TT TT) E [0,1]nxut a = 01 = 02 and 9 = 31 we can easily transform Problem (5) into Problem (7) (primal) in a more compact way with an extra linear constraint.
min u.
f(w) + g(v) s.t. Tw,
with f(w) = wTz + +1 + (w20)) g(b) = - T log(v).
The state-of-the-art method [61] applies the linearized alternating direction method of multipliers (ADMM) algorithm [8] directly to the primal problem with a similar structure in Problem (7), which lacks the theoretical guarantee on its convergence rate since the objective function in Problem (7) has no Lipschitz gradient. Motivated by the recent work [45], we circumvent this critical issue by applying the FISTA algorithm [2], a proximal gradient method, the dual problem of (7) instead. Motivated by recent advances [3, 61], we can now provide a better convergence rate with rigorous theoretical analysis that our proposed graph construction method is much more efficient with guarantees.
Dual Problem Formation We construct the Lagrangian function by introducing the Lagrangian multipliers À E R" L(w, A) = f(w) + g(v) (A, Tw v). We establish the corresponding dual problem as Problem (8) by introducing the conjugate functions f*.g" for simpler notation (Appendix E.3).
min F(A)+G(A)
(8)
5

---

with = - holds as long as a resides in the range of T. Therefore, the optimal values for Problem (7) and (8) are identical, and the optimal solution for Problem (8) can be attained. Consequently, we can apply the FISTA algorithm to the dual problem to generate the dual sequence that converges to the optimal solution, and construct the corresponding optimal solution back for the primal problem.
= (
By Slater's condition, we know that strong duality
Dual Problem with FISTA It not hard to show that F()) is differentiable and VF(A)= Txx where x arg max,, ((TT((()))) [()) (Appendix E.4). Therefore, the dual problem minimizes the sum of differentiable convex function F and closed proper convex function G. This structure of the dual Problem (8) immediately paves the way for applying proximal gradient methods. Here, for the sake of better convergence rate, we apply the FISTA algorithm with fixed step size to the dual Problem (8), and the following iteration schemes are performed. We first choose any A = X 20 Henceforth, k 1,2, .., we repeat the following two steps as
and fix the step size as t = Ita"
0 2 h ++1 (A R-1 2 (u* (LV(F((()))
"²
(9)
k = proxig
(10)
Hence, based on the above- mentioned properties of VF((")) we have VF(μ²) Tw with w set / arg max {(T
(TT) T w f(w)] TT 4 (Appendx E.5).
23
Let pd = 1² t By the extended Moreau decomposition [43], prox,1(2) proox--1-- (z/7) = 2, Vz. We have (roxxc((") = pt -t prox, -6- (t p²) μ -tT )²)
Here, u prox,-1g (Tw -t 'x²). Note that g(v) = -a1 lolllog(v) (v) and by the definition of
proximal mapping, it is easy to prove that (ro { + Vu v + 4at-l11 Therefore, we can simplify the updating step (10) the following three steps (Appendix E.6).
TT 4 =
w
(11)
2B
1 2 A 4² t(Tw" -u²),
u (Tw -t -t
(T - w+) o (Tw - ptt + 4at
(12)
2
(13)
Finally, we arrive Procedure GWBI, where the optimal graph weights are inferred for one block like W um in the optimal graph structure suggested in Proposition 1. Here, instead of directly optimizing the primal variable of the block graph weight vector uz we consider its corresponding dual variable À for better convergence rate. In each iteration step, we first find extrapolated point μ based on the points À from two previous steps (line 3). We then perform the proximal gradient update on this extrapolated point (lines 4-6) to obtain À for the next iteration. Note that lines 4-6 are the detailed instantiation of Eq. (10). Finally, we can convert the dual variable back to the desired primal variable based on line 4 after its convergence. With this procedure in hand, we plug it into the proposed Algorithm 1, Block-wise Affinity Graph Leamingg (BAGL) algorithm, in Appendix C.
3.3 Theoretical Analysis
We prove that our proposed optimization method for Problem (7) in Procedure GWBI enjoys the guarantee of the global convergence rate, where the generated primal sequence converges to the global optimal solution at a rate of ((+) with a fixed step size. To begin with, it is well known that the FISTA algorithm enjoys the global convergence rate of 0 (z4 [2]. For simplicity, we focus on the results when optimizing Problem (5), which can be viewed
general case of Problem (6) when
I * u. Therefore, Q(x) F(A) + G(X) converges to the dual optimal value Q(X") at a rate of
0 due this well- well-known fact [2], which yields Theorem 2.
Theorem 2. Let {2*} be the dual sequence generated by Procedure GWBI, then
1
-(a*)-Q00 <
3(k - 1)3 || 111
(14)

---

Procedure GraplWWighDDokkiieeneeeaaaaa..
Input: Distance vector 2, linear mapping matrix T, balancing parameters and B, step size 4
eπror tolerance parameter
Output: Block graph weight vector w.
Initialize 2 x at random and set 1;
2 do
1 A k-1
k-2
2);
kti
T u²
23
u } (Tw t- [tt) +
(Tw -- -t1 ④ (Tw -t-l ) 4at 11
A 4* +(Tw" u²);;
h + k + 1;
while | * X k--1 11000
8
return "
We then consider the corresponding primal sequence {w"} and its convergence rate. Since the strong duality holds and dual optimal solution X exists, any primal optimal point (w* v²) is also minimizer of L(w (w A*) This motivates dual sequence (X*) as w² arg min,, L(w, v, X²) ) arg max ((TT) X w) f(w)). Thanks
construct the primal sequence {w*) based on the
to Theorem 3, this primal sequence {w") is guaranteed to converge to the optimal primal solution w" of Problem (7) at the rate of (
Theorem 3. Let w arg max (TT w) - f(w) with the dual sequence (>*} given by Procedure GBBI. w and X are the optimal solution of Problem (7) and the optimal solution of Problem (8), respectively. have,
VI+ 8(k + | | 121
1 w0 20'12
(15)
Motivated by [45], Theorem 3 establishes that the proposed method exhibits a sub-linear convergence rate, which represents a state-of-thee thrt result for optimization-batt accompanied by a global convergence guarantee. This improved convergence rate is primarily attributed to the utilization of the FISTA algorithm applied to the dual problem. Time complexity analysis is included in Appendix G.5. More results regarding the robustness of our method are discussed in Appendix D.
graph construction methods,
Experiments
In this section, we conduct numerical experiments on both synthetic and real-world datasets to demonstrate the advantages of our proposed BAGI method in terms of efficacy and convergence. Robustness analysis (Appendix G.3) and more experimental results are included in Appendix G.
4.1 Baseline Models
We choose the following graph construction methods in GSSL for comparison, Radial basis function kernel (RBF) [85] and KNN graph [17] are two classic methods. Smooth graph learning (SGL) [29] a popular method in the graph signal processing domain. RGCLI [7] is another label-informed graph construction method, Anchor Graph Regularization (AGR) [40] deals with large-scale graph construction. GraphEBM [14] and BCAN [63] are two state-of-the methods. The former exploits the energy energy-based based model while the latter constructs bipartite graph.
the hyper-parameters are fine-tuned with the grid search method. We repeat the experiment 20 times for each case and report the average result with optimal parameter setting in the efficacy analysis. Unless otherwise specified, the default label inference algorithm LGC,, and the label rate ten labeled samples per class. More details the experimental settings can be found in Appendix F.

---

1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0.0
0.2
0.4
0.6
0.8
1.0
0.0.0
0.2
0.4
0.6
0.8
1.0
(a) Synthetic datuset
(b) RBF
(c) BAGL (Ours)
Figure 1: Visualization of classification results on the synthetic dataset.
Table Description of datasets
accuracy
Datasct
#Samples a
#Features
#Classes e
3MG GraphEBM
RDCLI
ORHD
5,620
USPS
9,298
256
SCAN
RSF
COIL110
7,200
1,024
100
Figure 2: Comparison of BAGL against baseline models with the Bonferroni- Dunn test. CD=2.154 at 0.05 significance level.
TDT2
9,394
36,771
30
MNIST
70,000
784
EMNIST Letters
145,600
784
4.2 Synthetic Dataset
We generate synthetic dataset shown in Fig. (a). The constructed dataset contains two clusters, a dense Gaussian cluster surrounded by a sparse ring-like cluster. With only one labeled sample given in each cluster, we compare the result of our proposed BAGL method (Fig. I (c)) with the result of the most popular method RBF (Fig. (b)). We use the coordinates as the node feature and set the width in the RBF kernel 0.7. For visualization purposes, yellow line segments connecting the node pairs the weight associated with the edge is greater than 0.5 after normalization. The direction of the edge is ignored in Fig. 1 (c). For fair comparison, we perform label propagation [85] on both constructed affinity graphs. We can see that BAGL can recover ground-truth clusters much better. Unlike RBF, BAGL improve the connectivity by the logarithm penalty term and reduce the inter-cluster links by the block-wise design.
show the adjacency matrix with
4.3 Real-world Datasets
Classification tasks are implemented to assess the performance of BAGL against all graph construction baseline methods on six real-world datasets, listed Table ORHD (Optical Recognition of Handwritten Digits Data Set), USPS, MNIST, and EMNIST Letters are four popular digits image datasets. COIL100 is an object image dataset. TDT2 is a text dataset. We fix the number anchor nodes as 1000 in four datasets (COIL100, USPS, ORHD and TDT2), while for the two datasets (MNIST, EMNIST-Leetees)) the number of anchors fixed as 2000. We perform tf-idf and principal component analysis (PCA) the pre- peeprocessiin step TDT2 dataset. The default label inference algorithm is LGC, with ten labels per class. Further details can be found Appendix F.I.
4.3.1 Efficacy
We fix the number of labeled samples per class and select three label inference methods for the second phase GSSL. We report average results by performing 20 trials for each algorithm over all the settings in Table Our algorithm outperforms all methods in the USPS, TDT2, and EMNIST- Letters datasets, indicating that BAGL can learn an optimal graph for label inference algorithms in the unified framework. Moreover, perform the Friedman test with the Bonferroni-Deee Dunn post hoc test for statistical significance analysis. Fig. 2 illustrates the critical difference (CD) diagram on the accuracy, where the average rank is marked along the axis with lower (better) ranks to the left. If the average rank difference between two models is greater than one CD, the relative performance is believed to be different. Accordingly, BAGL significantly outperforms margin. We also conduct experiments under low label rates with L.G fixed as the label inference method. Fig. 3 (a) and (b) demonstrate that BAGL performs relatively well with low label rates. This phenomenon can be attributed to the utilization of label information in BAGL. (Appendix G.1)
other baselines by large

---

Table 2: Classification accuracy and standard deviation (%) on real-world datasets.
RBF
KNN
SGL.
RGCLI
AGR
GraphFBM
BCAN
BAGL,
GRF
90,36.0.33
86.59 ..26
94,68
88.24.13.11
97,63
95.1310.41
97.49.0.47
97.8810.40
ORHD
LGC
97.56:1.229
87.6112.30
95.7520.74
89.32442.58
96.90:0.47
95.7810.53
97.2720.63
98.0410.71
GCN
98.11
90.64.1..54
90.80
89.37.1..02
98.02 10.44
10.5210.50
98.08.0.70
98. 98.15.10.62
94.51+0.65
81,42+0.88
N7.67-0.40
94.26+0.36
93.98=0.60
90.56+0093
USPS
LGC
94.75.0..4
85.13.11.18
86.44.1..51
84.86.1663
95.92
94.3010.300
95.07.10.75
96.77.1.666
94.98+0.21
86.204-2.03
90.31++0.22
86. 86.09-11.72
95.81+0.488
95.79-0..5
GRF
94,40=0.19
81.24+1.64 64
02.65=00822
87,48+2.30 30
86.54=0.44 40
85 25.22-0.57
$4,31=0.59
0.,78=0.53
COTL100
95.13-00.37
83.66++1.38
93.27-41.00 1.03
87.79422.47
87.81-0.57
88.50++0.47
87.06-+0.63
94.93+00.55
GCN 04,31=0,25
87.64+1.72
93.52=00911
89.30+11.6 65
94.63+0.51
90.15=00.9
90.02=0048
94.99=0.88
GRF 89.22=0.79
80.09=2.69
92.13=00.99
86.51:33.42
94.47=20.99
93.642:0.74
95.95 60
96.01=:.91
TDT2
LGC
89.67.10.46
82.35.13.04
9..96.11.24
87.60.12.84
94.1510.67
93.97110.11
94.1310.799
95.42.10.71
GCN
92.89=0.68
85.7742.41
94,39=00.83
89.9413.15
95.36=0.85
94.7820069
96,30=0077
96.33:10.85
GRF 83.60.10,24
64.011882
9500310.77
87.6512.07
91.02.0.31
35.331
92.4110.47
13.40
MNIST
LGC 84.12-40.17
68.86+-163
94. 94.40-00.52
88.22442.366
94.79-40.37
95,43+-0.47
33.55+00.58
95.42-40.51
GCN 67.03
7..731.777
95.18
90.47.12.11
95.30.10.21
95.51 10.40
94.84
95.47.10.43
GRF 50.7440.16
41.85+135
62.34-0.58
F1.441192
64.38
65.0340:227
67.69-0.39
EMNIST
LGC 54.35=0.22
59
63.02=00441
57, 18422.0
66.49-0449
66.67+0.23
68.92-0.44 46
69.03-20.44
Letters
GCN 59.28-
5148+-1
66.51-+0.37
58.82411.7
67.21-40.1
68.56++0.19
68.97-0.50
69.14400447
2/
140.
(1)
12
MWN
RDF
ACR CHannEEM
CrapREEM
ACA
1yt
12
121
Number aiteeet parppespe
Sumver oflaneed
200
630
(a) ORHID
(b) USPS
(c) COIL100
(d) TDT2
Figure 3: (a) (b) Classification results and (c) (d) convergence results on real-world datasets.
4.3.2 Convergence
As essential part of the overhead for BAGL, Procedure GWBI needs to be efficient for practice. Compared with two other optimization-base methods sharing a similar objective, SGL. and its accelerated version by ADMM [61], BAGL enjoys the fastest convergence rate both datasets. We sample 1% nodes in each dataset for the convenience of presentation in Fig. 3 (c) and (d). Its outstanding performance confirms the theoretical analysis in Theorem (Appendix G.2).
4.3.3 Ablation Study
To obtain a better understanding of why the proposed BAGL works, we perform some ablation studies empirically show how the key design of BAGL will potentially affect performance. We create three variants based on the original version of BAGL. First, to demonstrate the significance of the optimal asymmetric structure, let any graph structure be the potential optimal structure without the constraints of W Ve = O and W uu = O. We call this variant BAGL w/o optimal structure. Second, reveal the importance of the connectivity regularization term, we set a = O in Procedure GWBI to remove the connectivity consideration. This variant is termed BAGL w/o connectivity. Third, to investigate the effects of sparsity control, we set 3 = 10c - 5 ~ 0 in Procedure GWBI to allow the sparsity of the constructed graph to vary arbitrarily. The last variant of BAGL abbreviated as BAGL w/o sparsity. We conduct the experiments on the ORHD dataset with the same setting as Table 2 and report the classification accuracy results Table 3. The proposed optimal asymmetric graph structure contributes most to the success of BAGL. The connectivity regularization term and the sparsity control term also matter since they together encourage a more sparse graph (the latter) but without disconnected components (the former), which is a more favorable graph for the second label inference step.
now do not differentiate labeled nodes and unlabeled nodes, and

---

Table 3: Ablation study of BAGL on the ORHD dataset.
BAGL w/o
BAGL w/o connectivity
BAGL w/o
BAGL
optimal structure
sparsity
GRF
95.71+0.84
96.71-0.62
96.05=0.73
97.8810.40
ORHD
LGC
96.3410.06
96.60=0.57
19.044
98.0410.71
GCN
97.2910.59
97.89-0.64
97.7410.53
98.15:10.62
5
Conclusion
In this paper, we propose novel approach to graph construction for graph-based bashd semi-supervised learning. Building upon the optimal asymmetric graph structure derived from theoretical insights, we develop an efficient block-wise graph construction method that guarantees faster convergence. Our approach combines thcoretical insights with practical considcrations to provide a more effective and reliable framework for the graph construction step in graph-based semi-supervised learning.
6 Limitations
BAGL is an optimization-based method for the graph construction step in graph-based semi- supervised learning. Graph Neural Networks (GNNs) excel in learning representations for graph- structured data [64, 54, 12, 49, 39, 78, 41, 75, 13, 53, 77, 51, 73, 52, 50, 38, 76, 11]. More recent graph structure learning methods aim to learn clean graph structure from the given noisy graph so that the subsequent GNNs trained on this learned clean graph can obtain better performance. In GSSL, however, there no given graph structure, and we need to learn the graph structure based on the node features only. Therefore, it is more challenging task compared to graph structure learning. Therefore, we do not compare our method with other graph structure learning methods since their settings and goals are slightly different. We leave the investigation of graph structure learning for GSSL as future work since it is currently out of the scope this work.
The other limitation of BAGL is it is only suitable for the transductive setting. If we have nodes or samples unseen in the training set, we have to construct the affinity graph again by executing BAGL again to infer their labels, which is often time-consuming and troublesome regarding efficiency. This not desirable in real-world applications since we often come across new training samples after we build the affinity graph. We also leave the investigation of the inductive extension of BAGL as future work since this lack of inductive generalization a well-known challenge in graph-based semi-supervised learning.
Even though BAGL quite efficient in terms of convergence rate, it may still have computational issues when dealing with extremely large-scale datasets with billions of samples because the time spent on finishing one iteration during the optimization would increase dramatically when the number of training samples is extremely large. We leave the exploration of graph construction methods for extremely large-scale datasets as future work. Other potential applications of our method can be explored in the hyperbolic space [67, 70, 68, 71, 69, 66, 72] or in the natural language processing domain [32, 34, 33, 21, 20, 55, 42, 80, 81, 79].
Acknowledgements
The work described in this paper partially supported by the National Key Research and Devel- opment Program of China (No. 201 (018AA00102004) and RGC General Research Funding Scheme (GRF) 14222922 (CUHK 2151185).
References
[1] Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, and Michael T. Jordan. Asymptotic behavior of by-based laplacian regularization semi-supervised learning. CoRR, 2016.
[2] Amir Beck and Mare Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(1):183-202, 2009.
10

---

[3] Amir Beck and Mare Teboulle. A fast dual proximal gradient algorithm for convex minimization and applications. Operations Research Letters, 42(1):1-6, 2014.
[4] Mikhail Belkin, Irina Matveeva, and Partha Niyogi. Tikhonov regularization and semi- supervised learning on large graphs. In ICASSP (3), pages 1000-1003. IEEE, 2004.
[5] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 7:2399-
2434, 2006.
[6] Lilian Berton and Alneu de Andrade Lopes. Graph construction based on labeled instances for semi-supervised learning. In ICPR, pages 2477-2482. IEEE Computer Society, 2014.
[7] Lilian Berton, Thiago de Paulo Faleiros, Alan Valejo, Jorge Carlos Valverde-Rebaza, and Alneu de Andrade Lopes. RGCLI: robust graph that considers labeled instances for semi-supervised learning. Neurocomputingg 226:238 248, 2017.
[8] Stephen P. Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn.. 3(1):1-122, 2011.
[9] Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. Poisson learning: Graph based semi-supervised learning at very low label rates. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 1306-1316 PMLR, 2020.
[10] Hongxu Chen, Hongzhi Yin, Tong Chen, Quoc Viet Hung Nguyen, Wen-Chih Peng, and Xue Li. Exploiting centrality information with graph convolutions for network representation learning. In ICDE, pages 590-601. IEEE, 2019.
[11] Yankai Chen, Yixiang Fang, Yifei Zhang, and Irwin King. Bipartite graph convolutional hashing for effective and efficient top-n search in hamming space. arXiv preprint 2023.
[12] Yankai Chen, Yifei Zhang, Menglin Yang, Zixing Song, Chen Ma, and Irwin King. WSFE: wasserstein sub-graph feature encoder for effective user segmentation in collaborative filtering. CoRR, fbbs/2305.04410/ 2023.
[13] Yankai Chen, Yifei Zhang, Menglin Yang, Zixing Song, Chen Ma, and Irwin King. WSFE: wasserstein sub-graph feature encoder for effective user segmentation collaborative filtering. In SIGIR, pages 2521-2525. ACM, 2023.
[14] Zhijie Chen, Hongtai Cao, and Kevin construction for semi-supervieed learning. In ICDM, pages 62-71. IEEE, 2020.
Chang. Graphebm: Energy-based graph
[15] Inae Choi and Hyunjung Shin. Semi-supervised learning with ensemble learning and graph sharpening. In IDEAL, volume 5326 of Lecture Notes in Computer Science, pages 172-179. Springer, 2008
[16] Celso André R. de Sousa, Solange O. Rezende, and Gustavo E. A. P. A. Batista. Influence of graph construction semi-supervised learning. In ECML/PKDD (3), volume 8190 of Lecture Notes in Computer Science, pages 160-175. Springer, 2013.
[17] Cheng-Hao Deng and Wan-Lei Zhao. Fast k-means based on k-nn graph. In ICDE, pages 1220-1223, IEEE Computer Society, 2018
[18] Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Laplacian matrix learning for smooth graph signal representation. In ICASSP, pages 3736-3740. IEEE, 2015.
[19] Xiaowen Dong, Dorina Thanou, Michael G. Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Process. Mag., 36(3):44 63, 2019.
[20] Yifan Gao, Jingjing Li, Michael Lyu, and Irwin King. Open-retrieval conversational machine reading. arXiv preprint arXiv:2102.08633 2021.

---

[21] Yifan Gao, Chien-Sheng Wu, Jingjing Li, Shafiq Joty, Steven CH Hoi, Caiming Xiong, Irwin King, and Michael Lyu. Discemn: Discourse-awar entailment reasoning network for conver- sational machine reading. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2439-2449, 2020.
[22] Advitya Gemawat. Graphgem: Optimized scalable system for graph convolutional networks. In SIGMOD Conference, pages 2920- 29200222..222 ACM, 2021.
[23] Fang He, Feiping Nie. Rong Wang, Haojie Hu, Weimin Jia, and Xuelong Li. Fast semi- supervised learning with optimal bipartite graph. IEEE Trans. Knowl. Data Eng., 33(9):2245- 3257, 2021.
[24] Fang He, Feiping Nie, Rong Wang, Xuelong Li, and Weimin Jia. Fast semisupervised learning with bipartite graph for large-scale data. IEEE Transactions on Neural Networks and Learning Systems, 31(2):6266638 2020.
[25] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks. In ICLR. OpenReview.nec, 2021.
[26] Tony Jebara, Jun Wang, and Shih-Fu Chang. Graph construction and b-matching for semi- supervised learning. In ICML, volume 382 of ACM International Conference Proceeding Series, pages 441 441-448. ACM, 2009.
[27] Junteng Jia and Austin R. Benson. A unifying generative model for graph learning algorithms: Label propagation, graph convolutions, and combinations. SIAM Journal Mathematics of Data Science, 4(1):100-125, 2022.
[28] Rie Johnson and Tong Zhang. On the effectiveness of laplacian normalization for graph semi-supervised learning. J. Mach. Learn. Res., 1:44 2007.
[29] Vassilis Kalofolias. How to learn graph from smooth signals. In AISTATS, volume 51 of JMLR Workshop and Conference Proceedings, pages 920-929. JMLR.org, 2016.
[30] Vassilis Kalofolias and Nathanaël Perraudin. Large scale graph learning from smooth signals.
In ICLR (Poster). OpenReview.net, 2019.
[31] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net. 2017.
[32] Jingjing Li, Yifan Gao, Lidong Bing, Irwin King, and Michael R Lyu. Improving question generation with to the point context. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3216-3223 2019.
[33] Jingjing Li, Zichao Li, Tao Ge, Irwin King, and Michael R Lyu. Text revision by on-the-fly representation optimization. pages 10956-10964, 2022.
[34] Jingjing Li, Zichao Li, Lili Mou, Xin Jiang, Michael Lyu, and Irwin King. Unsupervised text generation by learning from search. Advances in Neural Information Processing Systems, 33:10820-10831, 2020.
[35] Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi-supervised learning via graph filtering. In CVPR, pages 9582-9591. Computer Vision Foundation IEBE, 2019.
[36] Yu-Feng Li, Shao-Bo Bo Wang, and Zhi-Hua Zhou. Graph quality judgement: A large margin expedition. In IJCAL, pages 1731. ICAA/AAAI Press, 2016.
[37] Jiye Liang, Junbiao Cui, Jie Wang, and Wei Wei. Graph-based semi semi-supervised Icarning via improving the quality of the graph dynamically. Mach. Learn., 1 11066) 2021.
[38] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye. Tackling long-tailed distribution issue graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, pages 1-11,200 2023.
12

---

[39] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, and Jieping Ye. Resnorm: Tack- ling long-tailes degree distribution issue in graph neural networks via normalization. CoRR, abs/2206.0818) 2022.
[40] Wei Liu, Junfeng He, and Shih-Fu Chang. Large graph construction for scalable semi semi-supervised learning. In ICML, pages 379-686. Omnipress, 2010.
[41] Yueen Ma, Zixing Song. Xuming Hu, Jingjing Li, Yifei Zhang, and Irwin King. Graph component contrastive learning for concept relatedness estimation. In AAAI, pages 13362- 13370. AAAI Press, 2023.
[42] Yueen Ma, Zixing Song. Xuming Hu, Jingjing Li, Yifei Zhang, and Irwin King. Graph component contrastive learning for concept relatedness estimation. Proceedings of the AAAI Conference on Artificial Intelligence, 37(11):13362-133 Jun. 2023.
[43] Neal Parikh and Stephen Boyd. Proximal algorithms. Found. Trends Optim., 13)):127-23, 2014.
[44] Michael G. Rabbat. Inferring sparse graphs from smooth signals with theoretical guarantees. In ICASSP, pages 6533-6537. IEEE, 2017.
[45] Seyed Saman Saboksayr and Gonzalo Mateos. Accelerated graph learning from smooth signals. IEEE Signal Process. Lett., 28:2192-21966 2021.
[46] Hyunjung Shin, N. Jeremy Hill, Andreas Martin Lisewski, and Joon-Sama Park. Graph sharpen- ing. Expert Syst. Appl., 37(12);7870-7877 2010.
[47] Hyunjung Shin, N. Jeremy Hill, and Gunnar Rätsch. Graph based semi- cumi-supervised learning with sharper edges. In ECML, volume 4212 of Lecture Notes in Computer Science, pages 401-412. Springer, 2006.
[48] Anthony Man-Cho So. Moment inequalities for sums of random matrices and their applications in optimization. Math. Program., 132551155-- 2011.
[49] Zixing Song and Irwin King. Hierarchical heterogeneous graph attention network for syntax- aware summarization. In AAAI, pages 1 11340-11345 AAAI Press, 2022.
[50] Zixing Song. Yueen Ma, and Irwin King. Individual faimess dynamic financial networks. In NewrlPS 2022 Workshop: New Frontiers in Graph Learning, 2022.
[51] Zixing Song, Ziqiao Meng. Yifei Zhang, and Irwin King. Semi Semi-supervised multi-label learning for graph-structured data. In CIKM, pages 1723 1733. ACM, 2021.
[52] Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King. Graph-based semi-supervised learning: A comprehensive review. IEEE Transactions on Neural Networks and Learning Systems, pages 1 1-21, 2022.
[53] Zixing Song. Yifei Zhang, and Irwin King. Towards an optimal asymmetric graph structure for robust semi-supervised node classification. In KDD, pages 1656-1665. ACM, 2022.
[54] Zixing Song, Yuji Zhang, and Irwin King. Towards fair financial services for all: A temporal GNN approach for individual fairness on transaction networks. In CIKM, pages 2331-2341. ACM, 2023.
[55] Xin Sun, Tao Ge, Shuming Ma, Jingjing Li, Furu Wei, and Houfeng Wang. A unified strategy for multilingual grammatical error correction with pre-trained cross-lingual language model. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, IJCAI-22, pages 4367-4374. International Joint Conferences on Artificial Intelligence Organization, 2022. Main Track.
[56] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[57] Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. In ICMI., volume 148 of ACM International Conference Proceeding Series, pages 985-992. ACM, 2006.
13

---

[58] Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. IEEE Trans. Knowl. Data Eng., 20(1):55-61 67, 2008.
[59] Hongwei Wang and Jure Leskovec. Combining graph convolutional neural networks and label propagation. ACM Trans. Inf. 40(4), nov 2021.
[60] Xiaolu Wang, Yuen-Man Pun, and Anthony Man-Cho So. Distributionally robust graph learning from smooth signals under moment uncertainty. IEEE Trans. Signal Process., 10:6216-6231, 2022.
[61] Xiaolu Wang, Chaorui Yao, Haoyu Lei, and Anthony Man-Cho So. An efficient alternating direction method for graph learning from smooth signals. In ICASSP, pages 5380-5384. IEEE, 2021.
[62] Yiwei Wang, Wei Wang, Yuxuan Liang. Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In KDD, pages 207-217. ACM, 2020.
[63] Zhen Wang, Long Zhang, Rong Wang, Feiping Nie, and Xuelong Li. Semi-supervised learning via bipartite graph construction with adaptive neighbors. IEEE Transactions on Knowledge and Data Engineering, pages 1-1, 2022.
[64] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn Syst., 32(1):4-24, 2021.
[65] Tian Xie, Bin Wang, and C.-C. Jay Kuo. Graphhop: An enhanced label propagation method for node classification. IEEE Transactions on Neural Networks and Learning Systems, pages 1-15, 2022.
[66] Menglin Yang, Zhihao Li, Min Zhou, Jiahong Liu, and Irwin King. Hicf: Hyperbolic informative collaborative filtering. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Datu Mining, pages 2212-2221, 2022.
[67] Menglin Yang, Ziqiao Meng, and Irwin King. FeatureNorm: L.2 feature normalization for dynamic graph embedding. In 2020 IEEE International Conference on Data Mining (ICDM), pages 731 731-740. IEEE, 2020.
[68] Menglin Yang. Min Zhou. Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete- time temporal network embedding via implicit hierarchical learning in hyperbolic space. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining,
pages 1975-1985 2021.
[69] Menglin Yang, Min Zhou, Jiahong Liu, Defu Lian, and Irwin King. Href: Enhancing col- laborative filtering via hyperbolic geometric regularization. In Proceedings of the ACM Web Conference 2022 pages 2462-2471, 2022.
[70] Menglin Yang, Min Zhou, Lujia Pan, and Irwin King. khgen: Tree-likeness modeling via con- tinuous and discrete curvature learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages
2023.
[71] Menglin Yang, Min Zhou, Hui Xiong, and Irwin King. Hyperbolic temporal network embedding. IEEE Transactions on Knowledge and Data Engineering, 2022.
[72] Menglin Yang. Min Zhou, Rex Ying, Yankai Chen, and Irwin King. Hyperbolic representation learning: Revisiting and advancing. arXiv preprint 2rXiv:2306.00/ 18, 2023.
[73] Xiangli Yang, Zixing Song, Irwin King, and Zenglin Xu. A survey on deep semi-supereised learning, IEEE Transactions Knowledge and Data Engineering, pages 1-20, 2022.
[74] Yuan Yuan, Xin Li, Qi Wang, and Feiping Nie. A semi-supervised learning algorithm via adaptive laplacian graph. Neurocomputing. 426: 162-13,,7 2021.
[75] Yifei Zhang, Yankai Chen, Zixing Song, and Irwin King. Contrastive cross-scale graph knowledge synergy. In KDD, pages 3422-3433. ACM, 2023.
14

---

[76] Yifei Zhang, Hao Zhu, Ziqiao Meng, Piotr Koniusz, and Irwin King. Graph-adaptive rectified linear unit for graph neural networks. In Proceedings of the ACM Web Conference 2022, 2022.
[77] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. COSTA: covariance- preserving feature augmentation for graph contrastive learning. In KDD, pages 2524-2534. ACM, 2022.
[78] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmen- tation for graph contrastive learning and beyond. In AAAI, pages 11289- 10---112777 AAAI Press, 2023.
[79] Yuji Zhang and Jing Li. Time will change things: An empirical study on dynamic language understanding in social media classification. arXiv e-prints, pages arXiv-2210, 2022.
[80] Yuji Zhang, Jing Li, and Wenjie Li. Vibe: Topic-driven temporal adaptation for twitter classi- fication. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP), Singapore, December 2023, Association for Computational Linguistics.
[81] Yuji Zhang, Yubo Zhang, Chunpu Xu, Jing Li, Ziyan Jiang, and Baolin Peng. Learning user hashtagging preferences via personalized topic atten- tion. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7811-7820 Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
THowYYuTagTweee
[82] Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In NIPS, pages 321-328. MIT Press, 2003.
[83] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning from labeled and unlabeled data directed graph. In Proceedings of the 22nd International Conference Machine Learning, ICML. '05, page 1036-1043, New York, NY, USA, 2005. Association for Computing Machinery.
[84] Dengyong Zhou, Bernhard Schölkopf. and Thomas Hofmann. Semi-supervised learning directed graphs. In NIPS, pages 1633-1640, 2004.
[85] Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912-919. AAAI Press, 2003.
[86] Liansheng Zhuang, Zihan Zhou, Shenghua Gao, Jingwen Yin, Zhouchen Lin, and Yi Ma. Label information guided graph construction for semi-supervised learning. IEEE Trans. Image Process., 26(9):4182 4192, 2017.
15


Reviews:
[{"review_id": "i5JXhRRMid", "reviewer": "Reviewer_7nqE", "summary": "The authors proposes to solve graph-based semi-supervised learning (GSSL) problems by first finding the \"optimal graph\" for SSL. The optimal graph has edges only from labeled to unlabeled nodes, or between unlabeled nodes. These edge weights are computed through FISTA algorithm in the dual space, and theoretical guarantees are provided for sub-linear convergence rates. Experiments are conducted using both synthetic and real-world datasets.", "questions": "1. When comparing methods such as RBF and KNN to BAGL, were RBF and KNN used to also generate asymmetric (and not symmetric) graphs? This is not made immediately clear in the text, and I'm wondering if the superior performance mainly comes from keeping $W_{lu}, W_{ll}$ all zero matrices.\n \n2. Figure 1 c is visually appealing, but I'm having trouble understanding why that solution is any better or more probable than the RBF solution in 1b. \n\n3. There's a mismatch between appendix section labels and their references in the main text. This should be fixed since the appendix includes important time complexity and runtime analysis.\n\n4. How does BAGL react to class imbalance, either in the labeled nodes or in the entire classification problem?", "limitations": "Yes, in the appendix.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is very well written and nicely presented. The clear writing made it easy to follow.\n\nI did not carefully read through the proofs in the appendix, but the motivation for the framework and derivation of the algorithm seem correct. I appreciate that this paper did solid work on all aspects - problem formulation, clever optimization algorithm, theoretical convergence analysis, and numerical experiments. ", "weaknesses": "Please see the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very thoughtful and constructive review. We appreciate the recognition of our optimal graph construction approach in GSSL. We are glad to know that you find our paper solid in all aspects - problem formulation, clever optimization algorithm, theoretical convergence analysis, and numerical experiments. We would also like to thank you for your suggestions for improvement and have addressed each of your points below. We hope these responses will address your concerns appropriately.\n\n\n## 1.  Keeping $W_{lu}$ and $W_{ll}$ zero matrices.\n\nThis suggestion is quite interesting and valuable! In fact, when comparing existing graph construction methods like kNN or RBF with our proposed method BAGL (Table 2), we still stick to the original symmetric graph structure in these baselines and do not change the constructed graphs in these baselines into the same optimal asymmetric graph structure as the one used in our proposed method BAGL. **We choose not to do so, mainly because we strictly follow the original graph structures used in these baselines, which are all symmetric graphs, for a fair comparison with our method.** Regarding the question of whether the superior performance mainly comes from keeping $W_{lu}, W_{ll}$ all zero matrices, **we actually did an ablation study to investigate the influence of keeping $W_{lu}, W_{ll}$ all zero matrices for the proposed BAGL method in Table 3 in Sec. 4.3.3**. If we remove the constraints of $W_{lu} = \\mathbf{O}, W_{ll} = \\mathbf{O}$, we find that there is a most significant performance drop compared with other variants of BAGL in Table 3. **This result shows that the proposed optimal asymmetric graph structure contributes most to the success of BAGL.** However, we agree that this proposed asymmetric optimal graph structure can be easily incorporated into existing graph construction methods like kNN and RBF. Therefore, we add another experiment where we also convert the graphs constructed by existing baselines into the same proposed asymmetric optimal graph structure via setting $W_{lu} = \\mathbf{O}, W_{ll} = \\mathbf{O}$. The results are as follows.\n\n|                                  |  RBF  |  kNN  |  SGL  | RGCLI |  AGR  | GraphEBM |  BAGL |\n|:--------------------------------:|:-----:|:-----:|:-----:|:-----:|:-----:|:--------:|:-----:|\n| w/o $W_{lu},W_{ll} = \\mathbf{O}$ | 97.46 | 86.59 | 94.68 | 88.24 | 97.63 |   95.13  | 95.71 |\n|  w/ $W_{lu},W_{ll} = \\mathbf{O}$ | 97.51 | 87.66 | 96.72 | 89.31 | 95.40 |   95.21  | 97.88 |\n|          improvement (%)         |  0.05 |  1.23 |  2.15 |  1.21 | -2.28 |   0.08   |  2.26 |\n\nWe can have some observations from this table. The proposed optimal asymmetric graph structure via setting $W_{lu},W_{ll} = \\mathbf{O}$ does have some positive effects on almost all graph construction methods in GSSL. These empirical findings also support the theoretical motivations in Sec 3.1.2. Also, some optimization-based methods like SGL and BAGL seem to benefit more from this optimal asymmetric graph structure compared to some other baselines like kNN. Maybe this is because these methods tend to handle the optimization problem in Eq.(3) from the optimization perspective directly or indirectly, aligned with the merits of the derivation of why we set $W_{lu},W_{ll} = \\mathbf{O}$ in Proposition 1. Besides, we have to say that this optimal asymmetric is not a universal positive strategy for all graph construction baselines. It has negative effects on AGR. We suspect setting $W_{lu},W_{ll} = \\mathbf{O}$ may break the anchor node connections in AGR, thus leading to sub-optimal performance. **In summary, even though the proposed optimal structure is quite simple and may be incorporated into many existing graph construction baselines, we can only get the most significant performance improvement when used in optimization-based methods like our proposed method BAGL.**\n\n\n\n## 2. Figure 1.\n\nA simple but not quite accurate intuition for the superiority of BAGL over RBF (Figure 1) is as follows. BAGL inexplicitly uses the label information via the optimal graph structure (setting $W_{lu},W_{ll} = \\mathbf{O}$). Therefore, it is easier for BAGL to learn that the given red and the green labeled point (Figure 1a) are from two different classes or clusters (one is a ring-like cluster, and the other is a dense one). But RBF is only based on the distance of the points without any label information; thus, its performance is worse.\n\n\n## 3. Mismatch between main and appendix.\n\nThanks for spotting this mismatch. We will fix this issue.\n\n\n## 4. Class imbalance\n\nWe handcraft a label-imbalanced version of the ORHD dataset, where the labeled nodes are sampled until the overall imbalance ratio (max(#labeled class nodes)/ min(#labeled class nodes)) reaches 20. The results of BAGL with different subsequent label inference algorithms are as follows.\n\n|                          |  GRF  |  LGC  |  GCN  |\n|:------------------------:|:-----:|:-----:|:-----:|\n|  Balanced dataset (Acc)  | 97.88 | 98.04 | 98.15 |\n| Imbalanced dataset (Acc) | 94.75 | 95.30 | 96.28 |\n|   Performance Drop (%)   |  3.19 |  2.79 |  1.90 |\n\n**We can see that the imbalance in label classes can lead to a great performance drop in BAGL. Because BAGL only uses the information of whether the node is labeled or not in the graph construction step, instead of the information of the exact label of the node. This makes the BAGL unaware of the labeled class imbalance issue during training.** We will add this limitation of BAGL. However, from the results, we can see that the subsequent label inference algorithms also react to the labeled class imbalance case differently (say, GCN is more robust.) Therefore, we leave the investigation of graph construction methods that are also robust to label class imbalance as future work since it is out of the scope of this work. Thanks for your insights on this future direction. We will continue to conduct research on this new problem setting.\n\n\n\n\n\n"}, {"review_id": "EzFSMQ5caB", "reviewer": "Reviewer_CLLx", "summary": "This paper proposes a novel methodology for graph-based semi-supervised learning by leveraging a asymetric graph construction technique. The main contribution of the paper is the design of a block-wise graph learning framework to estimate the weights of a graph.", "questions": "- I am not convinced regarding the novelty of the framework. Can the authors elaborate how the development of section 3.2 is different from the work of [23] apart from the well-known application of the FISTA step?", "limitations": "The authors properly addressed the limitations of their proposed framework.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The main strengths of the paper are:\n- The derivation of the structure of the optimal affinity graph\n- The derivation of an optimization algorithm for the implementation of the block-wise graph learning algorithm\n- The thorough experimental evaluation to assess the performance of the proposed algorithm in different scenarios\n", "weaknesses": "- While the derivation of the optimal affinity graph is novel, the optimization algorithm for learning the graph weights are heavily influenced by prior works, and therefore not much novel.\n\n- The plots (c) and (d) in Figure 3 are not as helpful as the x-axis represent number of iterations where instead the authors should use computational time. Therefore, from Figures 3c and 3d we cannot conclude much about the computational efficiency of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n\nThanks for your detailed review. We appreciate the recognition of our derivation of the optimal affinity graph with thorough experimental evaluation. We would like to thank you for your suggestions for improvement and have addressed each of your points below. We hope these responses will address your concerns appropriately.\n\n\n\n## 1. **Novelty**\n\nWe appreciate your recognition of the novelty in the derivation of the optimal affinity graph in our method, confirmed by other reviewers as well. We also fully understand your concerns regarding the novelty of the optimization part or implementation of the proposed BAGL algorithm. **We agree that the optimization algorithm for learning the graph weights is built on top of the phenomenal work [1]. However, according to NeurIPS 2023 reviewer guidelines [2], work that uses a novel combination of well-known techniques can be valuable! (Review Form -> Strengths and Weaknesses -> Originality) Therefore, we believe using the existing well-known method like [1] in our method can also have its originality based on the following new insights or contributions to the GSSL domain.**\n\n\nFirst, **[1] builds a symmetric graph without differentiating the labeled and unlabeled nodes, while ours builds an asymmetric graph that takes the different roles labeled and unlabeled nodes play, following the proposed optimal graph structure.** This key difference between [1] and our method directly leads to superior empirical performance in ours compared to [1]. Table 2 supports this claim, and **our method BAGL outperforms the method SGL used in [1] by large margins.**\n\nSecond, even though the formulated optimization problems in [1] and our method (when focusing on one block) are similar (Eq.(5)(6) v.s. Eq.(17) in [1]), **the optimization algorithms used to solve the respective problems are totally different.** [1] uses the off-the-shelf primal-dual algorithm, while ours cleverly applies the FISTA algorithm to the dual formulation of the original problem. This key difference leads to the next different properties of the two methods.\n\nThird, **[1] does not even have a convergence rate guarantee, while ours enjoys the global sub-linear convergence rate guarantee, which is the SOTA result in the GSSL domain.** The key difference comes from the optimization algorithm we use, which is also novel, utilizing the power of the FISTA algorithm.\n\nFourth, **we also give the interpretation of our method from the aspect of robustness (Appendix D.1) and generalization bound(Appendix D.2), while [1] does not have these theoretical interpretations.** All these interpretation of our method is also novel and show the theoretical advantages of our method.\n\nTo sum up, we believe that our method has novel contributions to the GSSL field even though it is partially developed based on [1].\n\n[1] Kalofolias, Vassilis. \"How to learn a graph from smooth signals.\" Artificial intelligence and statistics. PMLR, 2016. \n\n[2] https://neurips.cc/Conferences/2023/ReviewerGuidelines\n\n\n\nFurther, **other reviewers also appreciate the novelty of our work**. Reviewer HpMF says, \"The paper presents a novel approach to constructing affinity graphs in GSSL, with a focus on the distinct roles of labeled and unlabeled nodes.\"  Reviewer 1FFQ comments, \"Even though this method is based on the well-known FISTA optimization algorithm, it is applied to the dual problem, which is also new since the convergence rate will be affected compared to the one applied to the primal problem directly.\"\n\n\n**We sincerely hope that the reviewer can re-evaluate the novelty of our work based on our response.**\n\n\n\n## 2. **Regarding Figure 3**\n\nWe understand your concerns related to Figure 3. In fact, **Figure 3 is not for the computational efficiency comparison of different methods but for the convergence rate comparison of different methods. We do not cover computational efficiency in Sec. 4.3.2, and we only focus on the convergence rate here.**\n\nIn fact, when we compare the convergence rates of different algorithms in the optimization domain, we usually set the x-axis as the number of iterations, instead of the actual running time. In this way, we can easily spot how quickly each algorithm approaches its limits. One of the most direct ways to measure this is by observing how the solution improves (e.g., how the $l_2$ distance between the current solution and the limit solution decreases) with each successive iteration. Please refer to the axes of Figure 3(c)(d) for details. In this way, **setting the x-axis as the number of iterations can better align with the definition of convergence rate**. It's easy to see that fewer iterations to achieve a similar error is generally better.\n\n\nHowever, it's important to note that the computational cost of one iteration can differ dramatically between algorithms. Therefore, it may not always be a direct measure of the computational effort. Therefore, your suggestion for computational time comparison is insightful.\n\n\nIn fact, **we have already included a computational efficiency comparison in Appendix G.5.2** titled  \"Running time comparison.\" Now in this section, we indeed compare the actual running time of each method. **Table 7 shows that our method is quite efficient compared with other optimization-based graph construction methods**.\n\n\n## 3. **Final remarks**\n\nWe sincerely respect and appreciate the time and effort you have dedicated to reviewing our work. We understand that every work should undergo meticulous scrutiny to ensure the highest standards, and we truly value your feedback. However, **we humbly hope you can reconsider certain aspects of our work that we believe it possesses significant novelty and includes computational time comparison in Appendix.** If there are specific areas of ambiguity or contention, we are willing to address them with further clarification. We kindly ask for an opportunity to emphasize the potential impact our work can bring to the broader this community.\n"}, {"review_id": "FQbLouidQz", "reviewer": "Reviewer_HpMF", "summary": "This paper proposes an efficient and effective method for constructing affinity graphs in Graph-based Semi-supervised Learning (GSSL), with a focus on the distinct roles of labeled and unlabeled nodes. The authors present a formulation for the GSSL problem, comprising two steps: graph construction and label inference. They investigate the optimal construction of the affinity graph in the first phase to facilitate enhanced performance in the second label inference phase. The paper offers four main contributions: a succinct definition of the optimality of the affinity graph in GSSL, a block-wise graph learning framework to infer the weights in the optimal graph structure, proof of a global sub-linear convergence rate for the proposed method, and extensive experiments on synthetic and real-world datasets to demonstrate the effectiveness and efficiency of the proposed method.", "questions": "Questions:\n How does the proposed method compare to more recent state-of-the-art methods in GSSL?\n Can you provide more guidance on when to use the proposed method versus other methods?\n Can you provide examples of how the proposed method could be applied in real-world scenarios?\n\nSuggestions:\n1. Consider comparing the proposed method with more recent state-of-the-art methods in GSSL to provide a more comprehensive evaluation.\n2. Provide more discussion of the limitations of the proposed method and when it may not be effective.\n3. Provide examples of how the proposed method could be applied in real-world scenarios to demonstrate its potential impact and relevance.\n4. Consider including a discussion of the computational complexity of the proposed method and how it compares to other methods.\n5. Consider including a more detailed explanation of the block-wise graph learning framework used in the proposed method to help readers better understand the approach.", "limitations": "The paper does not explicitly discuss the limitations and potential negative societal impact of the proposed method. While the paper does discuss the benefits of the proposed method, it does not provide a comprehensive discussion of its limitations or potential negative consequences. \n\nIt is important for authors to consider the potential limitations and negative consequences of their work, as this can help to ensure that the benefits of the work outweigh any potential negative impacts. In particular, authors should consider the ethical implications of their work and how it may impact society as a whole.\n\nTherefore, it can be said that the authors have not adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThe paper presents a novel approach to constructing affinity graphs in GSSL, with a focus on the distinct roles of labeled and unlabeled nodes. The proposed method is based on an asymmetric structure and a block-wise graph learning framework, which are different from existing methods. The paper also offers a succinct definition of the optimality of the affinity graph in GSSL, which is a unique contribution to the field. Overall, the paper is highly original in its approach to graph construction in GSSL.\n\nQuality:\nThe paper is well-written and presents a rigorous derivation of the proposed method. The authors provide a clear explanation of the problem formulation and the proposed solution, as well as a detailed analysis of the benefits of the proposed method. The experiments are extensive and well-designed, with results that demonstrate the effectiveness and efficiency of the proposed method. The paper also includes a thorough review of related work, which adds to the quality of the paper. Overall, the paper is of high quality.\n\nClarity:\nThe paper is well-organized and easy to follow. The authors provide clear explanations of the concepts and methods used in the paper, and the figures and tables are well-designed and easy to understand. The paper also includes a summary of the contributions and a conclusion that summarizes the main findings. Overall, the paper is highly clear and well-presented.\n\nSignificance:\nThe paper makes a significant contribution to the field of GSSL by proposing an efficient and effective method for constructing affinity graphs. The proposed method is based on an asymmetric structure and a block-wise graph learning framework, which are different from existing methods. The paper also offers a succinct definition of the optimality of the affinity graph in GSSL, which is a unique contribution to the field. The experiments demonstrate the effectiveness and efficiency of the proposed method, which has the potential to improve the performance of GSSL algorithms in a wide range of applications. Overall, the paper is highly significant in its contribution to the field of GSSL.", "weaknesses": "1. Lack of comparison with more recent state-of-the-art methods: While the paper compares the proposed method with several existing methods, some of these methods are relatively old and may not represent the current state-of-the-art in GSSL. It would be useful to compare the proposed method with more recent methods to provide a more comprehensive evaluation.\n\n2. Limited discussion of the limitations of the proposed method: While the paper discusses the benefits of the proposed method, there is limited discussion of its limitations. It would be useful to discuss the situations in which the proposed method may not be effective and to provide guidance on when to use the proposed method versus other methods.\n\n3. Lack of real-world applications: While the paper includes experiments on synthetic and real-world datasets, there is limited discussion of real-world applications of the proposed method. It would be useful to provide examples of how the proposed method could be applied in real-world scenarios and to discuss the potential impact of the proposed method on these applications.\n\nOverall, while the paper presents a novel approach to constructing affinity graphs in GSSL, there are some weaknesses that could be addressed to improve the paper's impact and relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your very thoughtful and constructive review. We appreciate the recognition of our optimal graph construction approach in GSSL. We are glad to know that you find our paper novel, well-written, rigorous, well-organized, and making a significant contribution to the field of GSSL. We would also like to thank you for your suggestions for improvement and have addressed each of your points below. We hope these responses will address your concerns appropriately.\n\n\n\n\n## 1. **SOTA methods comparison**\n\nThanks for your suggestion. **We chose some old graph construction methods in GSSL, like kNN and RBF, mainly because they are still the most simple yet quite effective methods, and they are included in relevant baseline papers as well.** The investigation of the graph construction step in GSSL has been overlooked for quite a long time, and this is why only a few recent SOTA methods are coming out in the past few years. However, **we do include GraphEBM [1], published in 2020, and BCAN [2], published in 2022, as the most recent SOTA methods as baselines.** We believe most of the recent important SOTA methods on graph construction methods in GSSL are covered in our experiments. We also welcome suggestions on other SOTA methods on graph construction steps for GSSL in recent years with references.\n\n\n\n[1] Zhijie Chen, Hongtai Cao, and Kevin Chen-Chuan Chang. Graphebm: Energy-based graph 371 construction for semi-supervised learning. In ICDM, pages 62–71. IEEE, 2020.\n\n[2] Zhen Wang, Long Zhang, Rong Wang, Feiping Nie, and Xuelong Li. Semi-supervised learning 445 via bipartite graph construction with adaptive neighbors. IEEE Transactions on Knowledge and 446 Data Engineering, pages 1–1, 2022.\n\n\n\n\n## 2. **Discussion of the limitations**\n\nThanks for your suggestion. **We actually include the discussions of the limitations in Appendix H.** For instance, one limitation of BAGL is it is only suitable for the transductive setting, and it may still have computational issues when dealing with extremely large-scale datasets with billions of samples. We leave the investigation of these issues as future work since it is out of the scope of this paper. We will add more discussion of limitations in the main body.\n\n\n\n\n## 3. **Lack of real-world applications**\n\n\nThanks for your suggestion. In fact, **we indeed run the experiments on some open real-world datasets, and the task is image classification. We assume this is an example of a real-world application.** Please refer to Appendix F.1 for the details of the real-world datasets. The experimental results show how the proposed method could be applied in this real-world scenario. **The potential impact of the proposed method can be found in Appendix I, with a focus on social benefits**. \n\n\n\n## 4. **A discussion of the computational complexity**\n\nThanks for your suggestion. **Appendix G.5.1 gives a formal analysis of the time complexity, and Appendix G.5.2 presents a running time comparison with other baselines.** These results show our proposed method is efficient.\n\n\n## 5. **A more detailed explanation of the proposed method**\n\nThanks for your suggestion. For the block-wise graph learning framework,  we build on top of the well-known method [1]. We learn each block in the optimal graph structure via a similar method in [1] but with quite different optimization algorithms. We apply the FISTA algorithm to the dual formulation of the proposed learning framework. **We will polish the text to make the paper easier to understand.**\n\n\n[1] Kalofolias, Vassilis. \"How to learn a graph from smooth signals.\" Artificial intelligence and statistics. PMLR, 2016. "}, {"review_id": "KTU07rb3dX", "reviewer": "Reviewer_n8ra", "summary": "The paper proposes a method for graph construction stage of graph based semi-supervised learning. They further evaluate their method with experimental results. ", "questions": "NA", "limitations": "No ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors present strong theoretical results. ", "weaknesses": "The experimental results for the proposed method in Table 2 are only marginally better than the baselines. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your recognition of our work! We highly appreciate your feedback!\n\n**We did a statistical significance test in the experiment section**. Specifically, we perform the Friedman test with the Bonferroni-Dunn post hoc test for statistical significance analysis. Figure 2 illustrates the critical difference (CD) diagram on accuracy, where the average rank is marked along the axis with lower (better) ranks to the left. If the average rank difference between two models is greater than one CD, the relative performance is believed to be different. **Accordingly, our proposed method BAGL significantly outperforms all other baselines by a large margin.** Please refer to Figure 2 for more details.\n\n\n"}, {"review_id": "LdWaNfgKIC", "reviewer": "Reviewer_1FFQ", "summary": "The paper presents an optimal asymmetric graph structure for the label inference phase in graph-based semi-supervised learning (GSSL). The key motivation or intuition proposed by the authors is that we need to differentiate the roles of labeled and unlabeled nodes. Therefore, the authors design an efficient block-wise graph learning algorithm with a global convergence guarantee. The proposed method is shown to be superior to SOTA graph construction methods in GSSL through extensive experiments on synthetic and real-world datasets. The paper addresses the challenge of constructing a high-quality graph, which significantly influences label prediction performance, and proposes a solution with theoretical motivations and benefits, such as enhanced robustness to noisy node features. ", "questions": "1.\tWhile the paper provides a detailed explanation of the block-wise graph learning algorithm, it would be beneficial to have a more explicit discussion on the computational complexity of the algorithm. How does the algorithm scale with the size of the dataset? What are the implications of using this algorithm on large-scale datasets?\n2.\tThe paper could benefit from a discussion on potential real-world applications of the proposed method. In what specific domains or scenarios would this method be particularly useful?\n3.\tIt would be interesting to hear the authors' perspectives on the limitations of their proposed method and how they plan to address these in future work. Are there any specific challenges or difficulties that arose during the development of the method?\n4.\tThe paper mentions that the proposed method enhances the robustness of subsequent label inference algorithms. Could the authors elaborate on this? How does the method handle noise? Some theoretical analysis may be provided.\n", "limitations": "Please refer to the weaknesses and questions sections.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tQuality: The work is of high quality, with rigorous theoretical motivations and comprehensive experiments. First, the motivation is strongly supported by some theoretical analysis. The proposed asymmetric optimal graph structure is deduced from Definition 1 rigorously. The authors provide a comprehensive explanation of the optimization problem and the structure of the optimal affinity graph. Second, they also present a detailed implementation of the block-wise graph learning algorithm BAGL. The paper is well-referenced, indicating a thorough understanding of the existing literature. Third, the provided convergence analysis on BAGL is also rigorous. The global sublinear convergence rate in Theorem 3 makes sense to the reviewer. Forth, the experiments are comprehensive, including several comparisons from the aspects of prediction accuracy, efficiency, and convergence rate. \n2.\tClarity: The paper is well-structured and clear, with each section logically leading to the next. The authors provide clear definitions and explanations of complex concepts, making the paper accessible to readers with varying levels of expertise in the field. However, some parts of the appendix are suggested to move to the main body to give more background context on graph-based semi-supervised learning. The use of mathematical notation and diagrams further enhances the clarity of the paper.\n3.\tSignificance: The reviewer thinks the work makes some significant contributions to the GSSL field. First, the investigated problem is significant since most GSSL literature only focuses on the label inference step. This paper focuses on the neglected graph construction step instead, as the quality of the graph affects the subsequent step a lot. Second, the proposed method achieves the SOTA global convergence rate, contributing to the GSSL field significantly.\n", "weaknesses": "There are several potential improvements in this paper.\n1.\tThe background knowledge of the unified label inference framework can be elaborated. The details behind Eq.(1) should be provided to give readers without GSSL backgrounds more context. For example, Appendix B.2 should be added to the main body. Table 5 is very informative.\n\n2.\tThe recent graph structure learning method should be discussed or compared since the goal of GSL is also similar to the task investigated in this paper.\n\n3.\tThe conclusion part is short. More future work can be added.\n\n4.\tOther comments in questions section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very thoughtful review with constructive suggestions. We appreciate the recognition of our optimal graph construction approach in GSSL. We are glad to know that you find our paper novel, high-quality, rigorous with solid theoretical insights, well-organized with good writing, and contributing to the GSSL field. We would also like to thank you for your suggestions for improvement and have addressed each of your points below. We hope these responses will address your concerns appropriately.\n\n\n## 1. **Background knowledge of the unified label inference framework**\n\nThanks for your suggestion. **The relevant background knowledge of the unified label inference framework can be found in Appendix B.2**. We will consider moving some text and Table 5 into the main body for better presentation.\n\n## 2. **Graph structure learning**\n\nMore recent graph structure learning methods aim to learn a clean graph structure from the given noisy graph so that the subsequent GNNs trained on this learned clean graph can obtain better performance. In GSSL, however, there is no given graph structure, and we need to learn the graph structure based on the node features only. Therefore, it is a more challenging task compared to graph structure learning. **Therefore, we do not compare our method with other graph structure learning methods since their settings and goals are slightly different. We leave the investigation of graph structure learning for GSSL as future work since it is currently out of the scope of this work.**\n\n\n## 3. **Short conclusion**\n\nWe will elaborate on the conclusion section. More future work discussion in Appendix H will be added.\n\n\n## 4. **Discussion on the computational complexity**\n\nThanks for your suggestion. **Appendix G.5.1 gives a formal analysis of the time complexity, and Appendix G.5.2 presents a running time comparison with other baselines.** These results show our proposed method is efficient.\n\n\n## 5. **A discussion on potential real-world applications**\n\nThanks for your suggestion.  **The potential impact of the proposed method with some real-world applications, like social media and web services, can be found in Appendix I.**\n\n\n## 6. **Limitations of the proposed method**\n\nThanks for your suggestion. **We discuss some limitations of the proposed method with future work in Appendix H**. For instance, even though BAGL is quite efficient in terms of convergence rate, it may still have computational issues when dealing with extremely large-scale datasets with billions of samples. We plan to reduce the time spent on finishing one iteration during the optimization to solve this issue in future work.\n\n\n## 7. **Robustness analysis of the proposed method**\n\nThanks for your suggestion. **We include a theoretical analysis of the proposed method in terms of the robustness interpretation in Appendix D.1.** Intuitively speaking, the proposed BAGL method can guarantee that the hidden ground-truth distribution of the sample feature will be contained in an introduced ambiguity set. Even if there exists some noise in the observed features, we can still recover the ground-truth distribution as long as the number of node feature channels is sufficiently large.\n\n\n"}]

Author rebuttal:

Meta-review: The majority of the reviewers recommend accepting the paper with average score 6. 
I recommend accepting the paper as a poster.
Decision: Accept (poster)