Variance-enlarged Poisson Learning for Graph-based Semi-Supervised Learning with Extremely Sparse Labeled Data
Authors: Xiong Zhou
Xianming Liu
Hao Yu
Jialiang Wang
Zeke Xie
Junjun Jiang
Xiangyang Ji
Venue: ICLR 2024 poster (2024)
Keywords: Semi-Supervised Learning
Poisson Learning
Extremely Sparse Labled Data
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose a simple yet powerful framework to address the issue of nearly constant label functions for graph-based semi-supervised learning

Abstract: Graph-based semi-supervised learning, particularly in the context of extremely sparse labeled data, often suffers from degenerate solutions where label functions tend to be nearly constant across unlabeled data. In this paper, we introduce Variance-enlarged Poisson Learning (VPL), a simple yet powerful framework tailored to alleviate the issues arising from the presence of degenerate solutions. VPL incorporates a variance-enlarged regularization term, which induces a Poisson equation specifically for unlabeled data. This intuitive approach increases the dispersion of labels from their average mean, effectively reducing the likelihood of degenerate solutions characterized by nearly constant label functions. We subsequently introduce two streamlined algorithms, V-Laplace and V-Poisson, each intricately designed to enhance Laplace and Poisson learning, respectively. Furthermore, we broaden the scope of VPL to encompass graph neural networks, introducing Variance-enlarged Graph Poisson Networks (V-GPN) to facilitate improved label propagation. To achieve a deeper understanding of VPL's behavior, we conduct a comprehensive theoretical exploration in both discrete and variational cases. Our findings elucidate that VPL inherently amplifies the importance of connections within the same class while concurrently tempering those between different classes. We support our claims with extensive experiments, demonstrating the effectiveness of VPL and showcasing its superiority over existing methods. The code is available at https://github.com/hitcszx/VPL.

Published as a conference paper at ICLR 2024
VARIANCE-ENLARGEN POISSON LEARNING FOR GRAPH-BASED SEMI-SUPERVISED LEARNING WITH EXTREMELY SPARSE LABELED DATA
Xiong Zhou', Xianming Liu'; Hao Yu², Jialiang Wang', Zeke Xie Junjun Jiang', Xiangyang Jiº
Harbin Institute of Technology "Tsinghua University
BBaidu Research
ABSTRACT
Graph-based semi-supervised learning, particularly in the context of extremely sparse labeled data, often suffers from trivial solutions where label functions tend to be nearly constant across unlabeled data. In this paper, we introduce Variance-enlarged Poisson Learning (VPL), simple yet powerful framework tailored to alleviate the issues arising from the presence of trivial solutions. VPI. incorporates a variance-enlarged regularization term, which induces a Poisson equation specifically for unlabeled data. This intuitive approach increases the dispersion of labels from their average mean, effectively reducing the likelihood of trivial solutions characterized by nearly constant label functions. We subsequently introduce two streamlined algorithms, V-Laplace and V-Poisson, each intricately designed to enhance Laplace and Poisson learning, respectively. Furthermore, we broaden the scope of VPL to encompass graph neural networks, introducing Variance-enlarged Graph Poisson Networks (V-GPN) to facilitate improved label propagation. To achieve a deeper understanding of VPL's behavior, we conduct a comprehensive theoretical exploration in both discrete and variational cases. Our findings elucidate that VPL inherently amplifies the importance of connections within the same class while concurrently tempering those between different classes. We support our claims with extensive experiments, demonstrating the effectiveness of VPL and showcasing its superiority over existing methods. The code is available at https://githuub.co//tttt///////
INTRODUCTION
Semi-supervised learning (SSL) is a classical machine learning paradigm, which is driven by the desire to harness the vast amount of unlabeled data that exists in the real world, alongside the limited availability of labeled data (Fralick, 1967; Vapnik & Chervonenkis, 1974; Blum & Mitchell, 1998; Berthelot al., 2019). Traditional supervised learning methods heavily rely on labeled examples for training, which can be costly and tine-consuning to obtain, especially for complex tasks in domains like computer vision, natural language processing, and healthcare. Semi-supervised learning seeks to bridge this gap by leveraging both labeled and unlabeled data to improve model performance and generalization. By incorporating the vast pool of unlabeled data, cemi-supervised learning algorithms aim to extract more meaningful and robust representations, thereby enhancing the scalability, efficiency, and accuracy of machine learning models (Sohn et al., 2020). The emphasis of this paper is on scenarios where the labeled data is exceptionally scarce. This situation is common in many real-world applications, such as medical diagnosis, where obtaining labeled data can be expensive time-consuming, The challenge lies in effectively utilizing this limited labeled information to improve model performance.
Graph-based methods provide powerful framework for leveraging the underlying structure or relationships within the data (Zhu, 2006; Anis et al., 2018; Song et al., 2022). By constructing a graph where nodes represent data points and edges denote relationships similarities, information can be propagated across the graph to make predictions on unlabeled data. This approach is particularly advantageous in scenarios where data points not independent, but rather have dependencies or
"Correspondence Xianming Liu <esxm @ hit.ccu..c>>

---

Published as a conference paper at ICLR 2024
connections that can be exploited for learning. In the realm of graph-based SSL, the following optimization problem is considered:
min (u) -
Σ wis (u(zz),
(1.1)
with some specific constraints applied to labeled points. Herein, Wij denotes the edge weight between vertices æ; and vij, and L is the measure of distance between two labels. When L takes on the form of Ep distance and the labeled points adhere the boundary conditions u(z4) = y, for i E [4], the problem above is referred as p-Laplace learning (Zhou & Schölkopf. 2005; Bühler & Hein, 2009). This appellation originates from that at 2 it is initially known as Laplace learning or label propagation (Zhu et al., 2003). When L(u(z;), 2xx;)) w |lu((z)) u(xz))] the problem in Eq. 1.1 under certain regularity assumptions follows that the limit of the (unique) minimizers of I (as p grows to infinity) is the lex-minimizer for Lipschitz learning (Egger & Huotari, 1990; Aronsson et al., 2004; Kyng et al., 2015). Moreover, many variants of Laplace learning have been proposed with various types of soft label constraints in place of hard constraints (Zhou et al., 2003; Belkin et al., 2004b;a; Kang et al., 2006; Wang et al., 2013; Gong et al., 2016).
However, it is found that, in the context of large graphs scenarios with extremely sparse labeled data, distances based on graph Laplacians do not conform to the intuition that nodes within the same clusters can be interconnected via many paths of high probability (Nadler et al., 2005). Instead, they tend to converge to non-informative functions, which results in degenerate solutions that take the form of an almost everywhere constant label function, thereby significantly deteriorating the accuracy performance (Nadler et al., 2009; EI Alaoui et al., 2016; Calder et al., 2020). This undesirable property usually attributed to the fact that long random walks tend to forget their starting position, leading to the mixing of random walks (Lovász& & Simonovits, 1990). Several alternative methods have been proposed to address this issue, including higher order graph Laplacian distances (Alamgir Luxburg, 2011 1; Zhou & Belkin, 2011; Bridle & Zhu, 2013; Kyng et al., 2015; Rios et al., 2019). More recently, Calder et al. (2020) proposed Poisson learning as different approach to handling labeled data. This method replaces the original boundary conditions in the Laplace equation with the source term in a graph Poisson equation. However, Poisson learning still treats unlabeled data in the form of Laplace equations, which retains the characteristic of a smooth combination primarily influenced by the unlabeled portion, potentially risking convergence towards non-in -oniinformeeive predictions.
In this work, we propose a simple yet effective framework, variance-enlarged Poisson learning (VPL), to address the presence of degenerate solutions that tend to be almost constant for unlabeled points. Specifically, introduce variance-enlarged regularization term that increases the dispersion of labels away from the mean or average label by enlarging the variance of labels. This leads to the Poisson equation for unlabeled data. Based on the variance-enlarged framework, we propose two specific algorithms. V-Laplace and V-Poisson, to enhance Laplace learning and Poisson learning, respectively. These algorithms are efficient and simple implement (see Sec. 3.2). We also incorporate VPI. into the propagation in graph neural networks and propose variance-enlarged graph Poisson networks (V-GPN), which can improve label propagation at very low label rates. Furthermore, we provide theoretical analysis in both discrete (finite data) and variational (infinite data) cases. In the discrete case, we demonstrate that VPL is equivalent to reducing edge weights and prove that under mild conditions, it amplifies the importance of edge weights connecting vertices within the same class while diminishing the importance of those connecting vertices from different classes. In the variational case, we provide variational characterization of the performance of VPL with more general objective incorporating the l, distance (p 2 2). The theoretical analysis is formulated in the asymptotic limit as the number of unlabeled data grows infinity while the number of labeled data stays constant. We derive the condition under which the inclusion of the variance-enlarge regularization in VPL guarantees the convexity of the variational objective. We prove that the associated optimality conditions result in partial differential equation for the estimate of labeling functions, referred to as the weighted p-Poisson equation. We conduct extensive experiments to demonstrate the effectiveness of VPL, showcasing its superior performance over the state-of- fate-off-hhe-rtss
The main contributions of our work are summarized as follows:
We present variance-enlargee Poisson learning, a simple yet effective framework for tackling the challenges associated with extremely sparse labeled data in graph-based based semi- cemi-supervised learning. Our extensive experimental results demonstrate the effectiveness and superior performance of over existing methods.
2

---

Published as a conference paper at ICLR 2024
We propose two specific algorithms, V-Laplace and V-Poisson, which are efficient and simple to implement and achieve better performance than the original Laplace learning and Poisson learning with extremely sparse labeled data. We also consider the problem of classifying nodes in graph-structured data and propose variance-enlarged graph Poisson networks to enlarge the variance of labels in the propagation.
We provide theoretical analysis in both discrete (finite data) and variational (infinite data) cases. In the discrete case, we show that VPL is equivalent to reducing edge weights, which implicitly amplifies the importance of edge weights within the same class. In the variational case, we characterize the performance of VPL in the asymptotic limit as the number of data grows to infinity. The associated optimality conditions lead the weighted p-Poisson equation.
2 PRELIMINARY
Let (zx) be underlying distribution compact space Z C R with smooth boundary. Let w: Ω + y/ be the unknown function we wish to estimate. For classification problems, we let y = (e1,-.., )+} (k: 2 2)', where 6 denotes the one-hot vector whose i-th element is 1, For the standard (transductive) semi-supervised learning problem, we have / labeled examples {(z), 31): ... (Iz, 9t) and n unlabeled examples {51+1, .... Jn with all examples x; sampled i.i.d from p(z). We let X = {_1, ) denote the vertices of a symmetric graph with edge weights Way 2 0 that indicate the similarity between 2; and Ty. The degree of vertex z; is denoted by d; ΣE= Waj. The goal of graph-based sune-sueeeeiee learning construct estimate of labels for all unlabeled examples by leveraging pairwise similarities in the graph.
Laplace Learning and Poisson Learning. The main difference between Laplace learning and Poisson learning emerges from their distinct approaches to handling labeled data. In Laplace learning, labeled data is incorporated as boundary conditions, taking the form u(x;) = yy for 1 S i S 1, while Poisson learning replaces the given labels with the assignment of sources and sinks like flow in the
graph, thus resulting in the Poisson equation (xx))) y/ y (with y Σ 8j) for S S I. On the other hand, both methods treat unlabeled data in the same way as follows:
Lu(xx) 0, for + sis n,
(2.1)
where L is the unnormalized graph Laplacian given by Lu(x;) Σラ= miy(u(x;) - u(zz)).
METHODOLOGY
In this section, we present in detail the auriance-enlarged framework and two specific algorithms from this framework, namely V-Laplace and V-Poisson. We also propose the variance- variance-enlarged graph Poisson network (V-GPN) for semi-supervised node classification with graph-structured data.
3.1 VARIANCE-ENLARGEE POISSON LEARNING
We explore the concept of enlarging the variance on labels, aiming to increase the dispersion of labels from their mean or average labels. This approach intuitively alleviates the presence of degenerate solutions that tend to be almost constant for unlabeled points. More precisely, we focus on the optimization objective as follows:
Wiy [u((xs) u(x;)) - X Var(u),
(3.1)
where Var(u) denotes the variance of these labels. Here, for brevity, we choose not to introduce constraints on the labeled data. In the subsequent sections, we will specifically incorporate the constraints associated with Laplace learning and Poisson learning with respect to labeled data into our framework, while the inclusion of other constraints is also a viable alternative.
For binary classification, we usually set y [+1,-11)
3

---

Published as a conference paper at ICLR 2024
For the specific form of variance, there two approaches available: a direct calculation of variance across all data or a weighted formulation based on certain criteria. In this paper, we adopt the latter one that takes into account the degrees of each point, i.c. Var[u] Σ qe [[](xx;;))) ull where define र7 Ei= (z((z;) and qi
Σラ=
When L(u(xe), u(x;)) = 1 [1l((x)) u(x;))l compared with Laplace learning and Poisson learning, the variance-enlarged objective induces the Poisson equation for unlabeled data as follows:
Cu(x;)= = Xq (u(x+) w) for S S n,
(3.2)
Formally, our proposed approach remains aligned with the principles of Poisson learning, leading us to designate it as Variance- Entarged Poisson Learning.
Remark.
Variance- Variance-enlarged regularization is somewhat similar to entropy minimization (Grandvalet & Bengio, 2004), as entropy minimization assumes prior that prefers minimal class overlap and helps enlarge the variance of labels. However, variance-enlarged Poisson learning suited for conducting an optimization algorithm than entropy minimization due to its quadratic nature, making it practical choice for certain scenarios with more concise iterations (cf. Sec. 3.2).
be better
3.2 V-LAPLACE AND V-POISSON
V-Laplace Learning. We consider the boundary conditions of labeled points in Laplace Learning, which is equivalent solving the problem:
{ Lu(x:)) = (q(((xx) - ifl siinn u(xx)) = yt:
(3.3)
f
In Algorithm 1, we provide an algorithm to solve the V-Laplace problem Eq. 3.3, where we clamp the labels for labeled data and only update predictions for unlabeled data.
Algorithm Variance-enlarged Laplace Learning (V-Laplace)
Input: The label matrix Y, E R the weight matrix W, and timesteps T, and the trade-off
parameter A.
2: Output: E Buuk (where Uz denotes the predicted matrix restricted to labeled rows).
3: D < diag( W1)
4: L +
W
5: U <- zeros(n. k)
6: for = 1 to T do
7:
U D U
DU
1 DD
8:
LU)
9: Y₁
end for
V-Poisson Learning. We consider the Poisson equation for the labeled points in Poisson Learning, which is equivalent to solving the problem:
Lu(xz)) = )q((u(zs) u)
1 sisi
(3.4)
Lu(x;) = yi 7 (q;(((x;) - T), if irlsis,
satisfying Ei. diu(z;) O, where y Σ Vi is the average label vector.
Unlike V-Laplace, which directly adopts constraints on labeled data in Laplace learning, V-Poisson in Algorithm 2 takes slightly different way to handle labeled data from standard Poisson learning. Here, we also introduce modifications to the labeled data, since it a crucial step to ensure that the identity Σi= Lu(x;) 0 always holds. In the following, of variance-enlarged Poisson learning through the random walk perspective.
gives the foundation for convergence
Theorem 3.1. If < mini 9a9s q (q), (q1.-.,9u) ..) connected and the Markov chain induced by the random walk is aperiodic,
waz the graph G with the weight matrix W = W >qq (where
4

---

Published as a conference paper at ICLR 2024
have: (1) For the iterations w1+1(2;) (2;) = ur( +d; (Aq:(ur( urr Lur of V-Laplace
learning in Algorithm 1, ur converges to the solution of the problem in Eq. 3.3; (2) For the iterations
WT+1(2;) = ur(=;) + d, (2,= (J/ - T) = j) + (q.(ur(;)) wy) (u)(( of V-Poisson
learning in Algorithm 2, then ur - as T 7 xc, where is the solution of Poisson equation 3.4
satisfying > dru(x;)= 0.
Algorithm 2 Variance-enlarged Poisson Learning (V-Poisson)
Input: The label matrix Y, E Biik the weight matrix W, and timesteps T, and the trade-off parameter A.
2: Output: The predicted matrix U R
3: D < diag( (1)
4: L +--1
W
5: y YY1
6: B <<- [Y,- y,,zerosuu, k)]
7: U < zeros(n. k)
8: for i 1 to T do
9:
U D
U 1 D1
T DU
10: U+ U U D- 1-U -
-U + XU)
11: end for
3.3 VARIANCE-ENLARGED GRAPH POISSON NETWORKS
In this subsection, consider the problem of classifying nodes in graph- strucurr data (Kipf & Welling, 2017; Veličković et al., 2018), where the graph structure is encoded with neural network model and trained supervised loss for extremely small set of labels.
Inspired by graph attention networks (GAT) (Veličković et al., 2018), we propose variance-enlarged graph Poisson networks (V-GPN) to adaptively capture the importance of the neighbors exerting to the target node via attention mechanism. In this way, the graph information can be gradually refined via network training. To be specific, we calculate the attention coefficients azj between nodes and Ty as ai H Hr,), where h constitutes trainable weight vector and H is trainable weight matrix. Subsequently, these attention coefficient diy are normalized using a softmax function to compute the edge weight matrix W that is further optimized via network training, that is, exp(as))
Why Σxer, exp(a;)) where N₁ some neighborhood of node To enlarge the variance of labels in the propagation, obtain the output of our proposed V-GPN by the following iterations:
U + U0- + D- (Xu (XU" ((U--))-L(--))) -LU(-
(3.5)
where (t-1) is defined in Algorithms I and 2, D and L represent the diagonal matrix of degrees and Laplacian matrix based on the iitention-based weight matrix W, respectively. Owing to the specifics of the attention calculation, D simplifies to an identity matrix. Consequently, we can
streamline the iteration process more succinetly as U(t) (U(+-1) AU (1-)
To incorporate the structural information arising from node features, we follow the approach in (Wan al., 2021), employing feature transformation module frT composed of single perception layer to predict labels based on node features. This module modifies the output at (T -)- iteration, giving rise to UT-3 <- UT-3 fET (X), where T denotes the number of iterations.
4 THEORETICAL UNDERSTANDING AND INSIGHTS
In this section, we theoretically investigate variance-en euraaeee-nnlarged Poisson learning, covering both the discrete (finite data) and variational (infinite data) cases. All proofs be found in Appendix A.
5

---

Published as a conference paper at ICLR 2024
4.1 THE DISCRETE CASE
For the discrete case with finite data, let us recall the Laplace equation: Lu(x;)) = O, which yields the expression u(xr)) 2.+ Σك= Wiju(zy) 전, Σラ=ı w)yu(rz)) + 2, Eه=1+1 Way (x))( This reveals that u(x;)) results from a smooth combination involving all labels and predictions. Consequently, when labeled data is extremely sparse, the result of u(x;) is primarily shaped by the unlabeled portion a. -ー Wizu(zz)) potentially leading convergence toward non-informative predictions. To mitigate the mixing of label propagation, several studies have focused re- re-weighting the graph more heavily near labels (Shi et al., 2017; Calder & Slepčev, 2020), thus increasing the influence of labeled data and implicitly foighteig the importance of unlabeled data.
We establish that variance-enlarged Poisson learning, under mild conditions, implicitly amplifies the importance of edge weights connecting vertices within the same class, while simultaneously diminishing the importance of those connecting vertices from different classes. We demonstrate that the inclusion of Var ui in Eq. 1.1 is equivalent to explicitly reducing all edge weights:
Lemma 4.1. The solution of the Poisson equation in Eq. 3.2 is equivalent to the minimizer of the objective 2 Ei=1 Σ==1( (way >q:9;)llu(zz) - u(zz)) l2 which indicates the optimal condition:
Σ>mm j=l w;yu(x,)) - Aq = d:
u(x;)= = d;- Aq:
(wis N4:g5)u((3))
(4.1)
This theorem offers a clear and straightforward understanding of the significance of the variance- enlarged regularization term. Moreover, implies that defining the parameter range X S ming Way is essential for preserving the convexity of the optimization objective.
9:9)
To better illustrate the implication of reducing edge weights as indicated in Eq. 4.1, we introduce a reasonable and intuitively meaningful assumption as follows:
Assumption 4.2. For each vertex 2; with its label yo, let 8Tr En Kyy Ex [yy=k) (where I is the identity function), we assume that s (yx) > maNk sT (k) and ((())) max s(()).
Assumption 4.2 consists of two statements for each vertex (1) The average of edge weights between r and vertices within the same class should exceed the average of edge weights between a and vertices of any other individual class; (2) The average of edge weights between and labeled vertices within the same class should exceed the average of edge weights between æ and labeled vertices of any other individual class. This assumption resembles the commonly-used manifold assumption in which samples located near each other on low-dimensional manifold are expected to share similar labels, but differs its emphasis on a description with a more global notion of class.
Together with Theorem 4.1 and Assumption 4.2, we can easily derive the following proposition:
Proposition 4.3. Under Assumptioo 4.2, let 6T" (k) Σ I(2, [k)==))ao iffor E (l,n} and k E V we have X < minij ":0,'
Ex kk (gz) (vc) (K) (R)
wis
(y:) < (k)), then *! (2:)
(1)
Remark. This proposition provide the insight that a reduction in edge weights can help give wider influence of vertices within the same class, thus forcing the solution of predictions with larger <²)))) ADE (yr)
within-class similaritics, i.e., (R) XDP (R)
Wk + ys On the other hand, the incquality [T]
(x) 3((6) (A) > A(.) Vk # y, indicates that the reduction also amplifies the importance of edge *((K]
weights connecting labeled vertices within the same class while diminishing the importance of those labeled vertices from different classes. To better illustrate the role of variance-enlarger regularization, consider the edge weights that satisfy wij 1.0 if y/4 YA and waj 0.1 if y4 + yj. with setting Xq:9; = 0.1. In this scenario, we have s (tx) \b (y:) = 0.9 and (14) >b; (v.) = O. Vm E {n, 1} k # y/- This suggests that the solutions will be weighted combination of vertices within the same class and eliminate the negative contributions from other classes, especially in the presence of large number of unlabeled data.

---

Published as a conference paper at ICLR 2024
Vlaplace 0.0g
Lagices 0.0
Vilgdace (A 23
Waagiaee = 0.000
0.79
Waapaas 77)
0.55
Viagiess =A= 0,001
0.00
0.50
14 Ppiase (3 (:09))
0.00
-0.20
09.2
-0.55
-100
-1.00
(a) ja is uniform on [-2,2]
(b) j mixture of two Gaussians
Figure 1: Behavior of the V-Laplace solutions with different À values under change of input density (x)), where two labeled points at -2 and 2 are given with label -1 and 1, respectively. (a) The solutions of 1-dimension problem with μ being uniform U 2]. (b) The solutions of I-dimension problem with y being mixture of two 1-dimension Gaussians (-2,, 1) and (22, 1).
4.2 THE VARIATIONAL CASE
We further techniques and ideas from PDE theory yield deeper understanding of the behavior of variance-enlare Poisson learning in the context of a more general objective incorporating the é distance (p 2) (Oberman, 2013).
Our analysis focused on the formulations in the asymptotic limit as the graph size goes to infinity (i.e., n oo) and the bandwidth of the edge weight Way = ip [=:=zill goes to zero (i.e., h 0)
(Nadler et al., 2009; El Alaoui et al., 2016). In particular, consider the problem
lim lim nanotae, Jp(u) A Var[u],
(4.2)
where Jp(u) = Eij wo (u(z)) ll Var[u] = E qill((r;)) - Ej (, and Cp = 207 ||=1 (11=112))dd is constant.
When + and h + 0, follow the asymptotic behavior of the objective Jp(u) in (Nadler et al., 2009; EI Alaoui et al.. 2016), we have lim lim, nhie uc, Jp(u) [[ (z) (z)dz for even p (please Theorem in (El Alaoui et al., 2016)). Thus, the functional with respect to u(x) formulated as
[ (l(()) (1(())))(())d
(u) = (VV)==IVV(==01111 (x)dxx
(4.3)
where the variance term is described as limm--o lim Varlu] fll((=]lB((xddr I u(z))(=))dz))) and ((x) is the weight assigned to x for calculating the variance.
Additionally, (=x) somewhat restricted to ensure that (zx) together with a sufficiently small À can guarantee the convexity of Eq. 4.3. Our first result characterizes the range of X as follows:
Theorem 4.4. For p 2 2, there exists a constant C depending on Ω q(x) and such that, when p.l. (V(x)))],,,"'" the functional in Eq. 4.3 shows convexity with respect to u. C"a(æ))
< inf inf
As can be seen, when p 2. the range can be simplified as À S infaen (at(a)) which depends on <(x) and u(x). Our next main result characterizes the solutions the optimization problem inf,, T(u) in terms of PDE referred to as the (weighted) p-Poisson equation.
2x²(x)
Theorem 4.5. Suppose the density P. bounded and continuously differentiable. X < inf inf p-IIu(()) 2x²²( then any twice- diice-diffrrentialle minimizer u Rdd - IR' of the func- (Pq(z))
tional in Eq. 4.3 must satisfy the Euler-Lagrang, equation
>q(x)
[ ((())u(x))d u(x)
div
(4.4)
p
7

---

Published as a conference paper at ICLR 2024
Table 1: Classification accuracy (%) of different methods MNIST with several labels per class 2,1, 4,5)). The results described as "mean (std)" are run over 100 trials. Results achieved by V-Laplace and V-Poisson that outperform their original ones are boldfaced and the the best results are underlined.
# LABELS PER CLASS
1
2
LAPLACE/LP (ZHU 2003)
16.7 (8.0)
30.8 (12.8)
(15.0)
61.9
76.2 (10.3)
NEAREST NEIGHBOR
(4.9
66.3 (3.8)
70.2 (2.6)
(2.7)
(2.5)
RANDOM WALK (ZhoU SCHÖLKOPE, 2004)
(4.0
(2.5)
91.7
(1.9
(0.5
MBO (GARCIA-CARDONA BT AL., 2014)
(9.4
29.3 (6.9)
40.2
(0.7
(9.0
WNLL (SHI RT Al., 2017)
(1..
(5.8)
(2.6
(1.2
(0.7)
CENTERED KERNEL (MAI & COUILLET, 2018)
(5.0)
90.8
91.5
93.9(1.2)
94.7 (0.9)
SPARSE LP (JUNG ET AL.. 2016)
(5.5
(4.0)
(4.0)
(8.9
16.2 (4.2)
P-LAPLACE (RiOS
2019)
72.7 (4.8)
82.7 (3.4)
86.1 (2.3)
(1.7
89.7 (1.3)
POISSON (CALDER FT Al.,, 2020)
91.3 (4.2)
94.3 (1.7)
(1.1)
(0.7)
95.8 (0.6)
V-LAPLACE V-POISSON
92.0 (4.3)
95.3 (1.5)
95.9 (0.8)
96.2 (0.5)
96.3 (0.5)
93.6 (3.9)
95.7 (1.5)
96.1 (0.6)
96.4 (0.4)
96.4 (0.4)
Table 2: Classification accuracy (%) of different methods on FashionMNIST with several labels per class 2, 3, 4, 5.)).. The results described as "mean (std)" are run over 100 trials. Results achieved by V-Laplace and V-Poisson that outperform their original ones are boldfaced and the the best results underlined.
LABELS CLASS
2
3
LAPLACE/LP ET AL., 2003)
(6.6)
(10.0)
(2.9)
(5.7)
NEAREST NEIGHBOR
(4.3)
49.6 (3.3)
52.7
(2.4
56.9 (2.7)
RANDOM WALK (ZHOU & SCHÖLKOPE, 2004)
(4.8)
63.1 (4.0)
(6.3(2.8)
62.5
70.1 (2.2)
MBO (GARCIA-CARDONA
AL., 2014)
15.7
20.1
(4.7)
34.7
34.8 (4.3)
WNLL (SHI AL.., 2017)
(7.6
(5.6
63.0
(3.4)
62.6
CENTERED KERNEL (MAT COUILLET, 2018)
(4.6
(4.4)
$3.9
58.4
(3.4)
SPARSE LP (JUNG ET AL., 2016)
(5.5)
(4.0
14,5
(8.0
16,2 (4.2)
P-LAPLACE
AL., 2019)
POISSON (CALDER ET AL., 2020)
60.4
66.3 (4.0)
68.9
70.7 (2.4)
(2.2)
V-LAPLACE
60.6)
66.3
(2.8)
71.0 (2.8)
(2.3)
V-POISSON
61.3
67.1 (4.2)
69.7 (2.8)
71.3
72.9 (2.3)
where div = (E En diag (VV .... (z) Furthermore, if the distribution μ has full support, then this equation can be solved equivalently by addressing
Σi 02, fx) for F. + R and Dp(Vu) Cf 8 f2
>g(x))
div(Vu(z))+ + 2V)((() Vog m(x) + (
(p( fu(x) ((()==())) = 0, (4.5)
(x)
and [u())((())) O, where A = Vu Vu, Vi Vuz Vu,j Vuz Vus
Va Vu Vue Vuulll
Viuil
and p = better show the behavior of dza. and Eq. 4.5 reduces to the second order ODE: 24²(x)u"( + 44(x)) (x) {q(z)u(z)) 0. If we further let be the uniform distribution and ((x) = p(x), we have u"(x) Au(x)
Remark. Here, we specialize to the case d
enlarging variance, then Ax = div(Vu) = d'a
As illustrated Fig. 1(a), the solution of Laplace equation (X' = 0) is straight line which is the shortest distance between two labeled points boundary. This behavior arises from fact that the solutions Laplace equation are harmonic functions that have no local maxima or minima. The existence of variance-enlarged regularization change this point, while it makes the confidence of prediction becomes higher as increases. Particularly noteworthy in Fig. 1(b), when μ mixture of two Gaussian, VPL mitigates the occurrence of spikes of labeled points and non-informative predictions for unlabeled points. This partially explains the effectiveness of enlarging variance for low label rate problems.
5 EXPERIMENTS
In this section, we provide extensive experiments to validate the effectiveness of variance-enlarged Poisson learning with extremely sparse labeled data (where the number of label per class is taken in
We easily derive that u(x) cos V + Co sin Va.
8

---

Published as a conference paper at ICLR 2024
Table 3: Classification accuracy (%) of different methods on CIFAR-10 with several labels per class (f1, 2,3, 4, 5)) The results described "mean (std)" are over 100 trials. Results achieved by V-Laplace and V-Poisson that outperform their original ones are boldfaced and the the best results underlined.
N LABELS CLASS
4
LAPLACE/LP (ZHU AL., 2003)
10.3 (1.2)
(1.7
11.8 (2.7)
(4.0)
13.1 (3.4)
NEAREST NEIGHBOR
23.9)
(3.3
35.1 (2.9)
36.4
(2.4)
RANDOM WALK (ZHOU& SCHOLKOPF, 2004)
(5.5)
44.6(3.5)
(3.7
51.1
52.8 (2.8)
MBO (GARCIA-CARDONA CARDONA
2014)
(4.2
24.3 (9.2)
28.5
(3.5
WNLL (SHI ET AL.,, 2017)
(4.8)
(6.9
(6.7
(8.0
(5.5
CENTERED KERNEL (MAl & COUNLET, 2018)
(5.4)
(5.7
(3.0
(3.6
50. (2.7)
SPARSE LP (JUNG ET AL.. 2016)
(2.4)
(2.3
(1.3
(4.5
11.0 (2.9)
P-LAPLACE (RIOS AL., 2019)
(4.7)
(3.5
(2.2)
48.8 (2.8)
POISSON (CALDER AL., 2020)
39.1 (5.4)
(3.9)
(3.6)
(3.0
52.9 (2.8)
V-I.PLACE
33.9 (5.6)
40.5
(4.9)
46.6 (4.8)
47.8 (4.3)
V-POISSON
41.4 (5.4)
48.5 (4.1)
51.7 (3.7)
54.7 (3.1)
56.3 (2.8)
Table 4: Classification accuracy with different label rates on Cora and CiteSeer. The best resutls are boldfaced.
#DATASET
LABELS & PER CLASS
3
GCN (KIPF & WELLING, 2017)
(5.9)
61.1 (3.6)
65.6 (5.5)
(1.2
(3,2)
GAT (VELIČKOVIĆ BT ML., 2018)
(3.4)
(4.1)
63.1 (6.8)
(1.9)
(3.7)
CORA
GPN (WAN V-GPN
2021)
(8.2
(4.3)
63.5 (7.2)
64.1 (5.3)
65.8 (6.5)
(7.3)
64.1 (5.00
(7.6
70.5 (2.4)
72.8 (1.7)
GCN (KIPF & WELLING, 2017)
(6.1)
(4.4
(5.7)
(4.9)
(2.2)
CITESBER
GAT (VOLIčKOVIĆ BT AL., 2018)
(3.6)
51.1 (4.6)
(3.5(1.5)
(8.0
(3.9)
GPN (WAN 2021)
(9.8)
(9.5
47.4 (6.4)
(5.0)
(8.9
V-GPN
(4.5)
55.4 (5.6)
$7.6 (2.2)
62.1 (2.0)
63.2 (2.4)
(1,2,3,455) on tasks: graph-based semi-supervised learning MNIST (LeCun et al., 1998),
FashionMNIST (Xiao et al., 2017), and CIFAR-10 (Krizhevsky & Hinton, 2009), and semi-supervised node classification with GNNs on the citation network datasets and CiteSeer (Sen al., 2008).
More experimental results and details can be found in the Appendix B.
Results on Graph-based Semi-supervised Learning. Tables 2 and 3 report the average accuracy and deviation while randomly selecting extremely sparse labeled data points on MNIST, Fashion- MNIST, and CIFAR-10, respectively. These results show that V-Laplace learning and V-Poisson learning have achieved very prominent results compared with Laplace learning and Poisson learning, which demonstrates the effectiveness of VPI. Notably, V-Poisson consistently outperforms other methods by an obvious margin across all cases. We also provide results on SimSiam (Chen & He, 2021) pretrained features on CIFAR-10, 10, where the details can be found in Appendix B.
Results on Semi-supervised Node Classification with GNNs. The experimental results Cora and CiteSeer are shown Table 4. As can be seen, our proposed V-GPN achieves substantial performance gains at different label rates when compared with the baselines GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018) and GPN (Wan et al., 2021). In particular, the margin between our proposed framework and the best baseline method can exceed 5% on Cora and CiteSeer datasets given one labeled node per class, which demonstrates that V-GPNs could effectively enhance the learning performance of GNNs with extremely sparse labeled data.
6 CONCLUSION
In this study, to address the challenges associated with sparse labeled data in graph- semi- supervised learning, we introduced Variance-enlarger Poisson Learning (VPL) to enlarge the variance of labels, which intuitively increases the dispersion of labels away from their average value. Based on this variance-enlarged framework, we present two efficient algorithms, namely V-Laplace and V-Poisson, which are tailored for improving Laplace learning and Poisson learning, respectively. Additionally, we extend VPL to enhance semi-supervised node classification with graph neural networks, introducing Variation cariation-enlarged Graph Poisson Networks. Furthermore, we conduct a theoretical exploration of VPL in both finite and infinite data cases, yielding deeper insights into understanding the behavior of VPL. Through extensive experiments, we demonstrate the effectiveness and superior performance of VPI. in scenarios characterized by extremely sparse labeled data.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGE
This work was supported in part by National Natural Science Foundation of China under Grants 92270116, 62071 155 and 623B2031, and in part by the Fundamental Research Funds for the Central Universities (Grant No.HIT..CCE::2233043 and HIT.DZZJ.2023075))
REFERENCES
Morteza Alamgir and Ulrike Luxburg. Phase transition in the family of p-resistances. Advances in neural information processing systems, 24, 2011.
Aamir Anis, Aly Gamal, Salman Avestimehr, and Antonio Ortega. sampling theory perspective of graph-based based semi-supervised learning. IEEF Transactions on Information Theory, 65(4):2322- 2342, 2018.
Gunnar Aronsson, Michael Crandall, and Petri Juutinen. A tour of the theory of absolutely minimizing functions. Bulletin of the American mathematical society, 41(4):439-50 505, 2004.
Mikhail Belkin. Irina Matveeva, and Partha Niyogi. Regularization and semi-supervised learning on large graphs. In Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff. Canada, July 1-4, 2004. Proceedings 17, pp. 624-638. Springer, 2004a.
Mikhail Belkin, Irina Matveeva, and Partha Niyogi. Tikhonov regularization and semi-supervised learning on large graphs. In 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 3, pp. 100-1000. IEEE, 2004b.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: A holistic approach to semi- superviee learning. Advances in neural information processing systems, 32, 2019.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceed- ings of the eleventh annual conference on Computational learning theory, pp. 92-100, 1998.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Nick Bridle and Xiaojin Zhu, p-voltages: Laplacian regularization for semi-supervised learning on nigh-dimensional data. In Eleventh Workshop on Mining and Learning with Graphs (MLG2013), 2013.
Thomas Bühler and Matthias Hein. Spectral clustering based on the graph p-laplacian. In Proceedings of the 26th annual international conference on machine learning. pp. 81-88, 2009.
Jeff Calder and Dejan Slepčev. Properly-weighted graph laplacian for semi-supervised learning. Applied mathematics & optimization, 82:1111-1155 2020.
Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. Poisson learning: Graph based semi-supervised learning at very low label rates. In International Conference on Machine Learning. pp. 1316--136. PMLR, 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the JEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 15750-15758, 2021.
Alan Egger and Robert Huotari. Rate of convergence of the discrete polya algorithm. Journal of approximation theory, 60(1):24-30 1990.
Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J Wainwright, and Michael I Jordan. Asymptotic behavior of f based laplacian regularization in semi-supereised learning. In Confer- ence on Learning Theory, pp. 879-9066 PMLR, 2016.
Fralick. Learning to recognize patterns without a teacher. IEEE Transactions on Information Theory, 13(1):57-64, 1967.
10

---

Published as a conference paper at ICLR 2024
Cristina Carria, Ekaterina Merkurjev, Andrea L Bertozzi, Arjuna Flenner, and Allon G Percus. Multiclass data segmentation using diffuse interface methods on graphs. IEEE transactions pattern analysis and machine intelligence, 36(8): 1000-1000011313 2014.
Chen Gong, Dacheng Tao, Wei Liu, Liu Liu, and Jie Yang. Label propagation via teaching-to- learn and seaminggto--eechhe IEEE transactions on neural networks and learning systems, 28(6): 1452 1465, 2016.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances in neural information processing systems, 17, 2004.
Alexander Jung, Alfred Hero III. Alexandru Mara, and Saeed Jahromi. Semi-supervised learning via sparse label propagation. arXiv preprint arXiv: 2/..0./..444... 2016.
Feng Kang, Rong Jin, and Rahul Sukthankar. Correlated label propagation with application to multi-label learning. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), volume pp. 1719-1726. IEEE, 2006.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint
arXiv: 1312.61 14, 2013.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL net / forum? i SJUJAAyyY
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, Tech. Rep, 01 2009.
Rasmus Kyng, Anup Rao, Sushant Sachdeva, and Daniel A Spielman. Algorithms for lipschitz learning on graphs. In Conference on Learning Theory, pp. 1 1223. PMLR, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. tradient-based learning applied to 232422224, 1998.
document recognition. Proceedings of the IEEE,
László Lovász and Miklós Simonovits. The mixing rate of markov chains, an isoperimetric inequality. and computing the volume. In Proceedings [1990] 31st annual symposium on foundations of computer science, pp. 346-354. IEEE, 1990.
Xiaoyi Mai and Romain Couillet. Random matrix-inspiree improved semi semi-supervised learning graphs. In International Conference on Machine Learning, 2018
Boaz Nadler, Stephane Lafon, Ioannis Kevrekidis, and Ronald Coifman. Diffusion maps, spec- tral clustering and eigenfunctions of fokker-planck operators. Advances in neural information processing systems, 18, 2005.
Boaz Nadler, Nathan Srebro, and Xueyuan Zhou. Semi-supervised learning with the graph laplacian: The limit of infinite unlabelled data. Advances in neural information processing systems, 22: 1330-1338, 2009.
Adam M Oberman. Finite difference methods for the infinity laplace and p-laplace equations. Journal of Computational and Applied Mathematics, 254:65-80. 2013.
Mauricio Flores Rios, Jeff Calder, and Gilad Lerman. Algorithms for Ip- la-based semi-supervised learning on graphs. arXiv preprint 3x0iv/900100000 pp. 1-3, 2019.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Re Collective classification in network data. Al magazine, 29(3):93 93, 2008
Zuoqiang Shi, Stanley Osher, and Wei Zhu. Weighted nonlocal laplacian interpolation from sparse data. Journal of Scientific Computing. 73:1164-1177, 2017.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in neural information processing systems, 33:596-608, 2020.
11

---

Published as a conference paper at ICLR 2024
Zixing Song, Xiangli Yang, Zenglin Xu, and Irwin King. traph-based semi-supervised learning: A comprehensive review. IEEE Transactions on Neural Networks and Learning Systems, 2022.
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition [in Russian]. Nauka, Moscow, 1974.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Sheng Wan, Yibing Zhan, Liu Liu, Baosheng Yu, Shirui Pan, and Chen Gong, Contrastive graph poisson networks: Semi-supervised learning with extremely limited labels. Advances in Neural Information Processing Systems, 34:6316-633 6327, 2021.
Bo Wang, Zhuowen Tu, and John K Tsotsos. Dynamic label propagation for semi-supervised multi- class multi-label classification. In Proceedings of the IEEE international conference on computer vision, pp. 425-432, 2013.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Dengyong Zhou and Bernhard Schölkopf. Learning from labeled and unlabeled data using random walks. In Joins Pattern Recognition Symposium, pp. 237-244. Springer, 2004.
Dengyong Zhou and Bernhard Schölkopf. Regularization on discrete spaces. In Joint Pattern Recognition Symposium, pp. 361-368. Springer, 2005.
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
Xueyuan Zhou and Mikhail Belkin. Semi-supervised learning by higher order regularization. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 892-900 JMLR Workshop and Conference Proceedings, 2011.
Xiaojin Zhu. Semi-supervised learning literature survey. Semi-Supervised Learning Literature Survey, Technical report, Computer Sciences, University of Misconsin-Maadisne 2006.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.
12

---

Published as a conference paper at ICLR 2024
Appendix for "Variance-enlarged Poisson Learning"
A PROOFS OF LEMMAS AND THEOREMS
A.1 PROOF OF THEOREM 3.1
Way the graph G with the weight matrix W W >xqq (where Theorem 3.1 If X S minij q:;""
q= (q...,, ) connected and the Markov chain induced by the random walk is aperiodic,
(oq((ur(z)) (I,) Wr) Lur (x:)) V-Laplace learning in Algorithm I, wT converges to the solution of the problem in Eq. 3.3; (2) For the iterations (24) = (x + d, (E}=(v; D) i = j) )q.(ur(z;))
have: (1) For the iterations (x+1( ur ur(xx)) di (Aq:
Tr) Cur (rx)) of V-Poisson learning in Algorithm 2, then UT + as T + 0o, where is the solution of Poisson equation 3.4 satisfying Σx=1dt d,((x;) O.
Proof. In this proof, we first perform analysis of the quadratic property of V-Laplace and then show the convergence in Algorithm that conforms to the gradient descent algorithm. For the convergence of V-poisson, identity Σi=1 duu((;;)= 0.
proof depends the characterization of the iterations, such the
(1) For the V-Laplace learning, the optimization problem be formulated minimizing E -ー=1 (wij )q:g;)]l((;;) - u(z;)1l _ in accordance with Lemma 4.1. Since the iterations
in Algorithm follows the GD sequence with the learning rate 1j J d.-xq know that Algorithm will converge to condition Cu(a;) = >gi (u(()))) - u) for + sisn.
(2) For the V-Poisson learning, the iteration in Algorithm shows that
(uT+11())) ur (x:)) + Lur(x;) )g.(ur(x;)) - -Tr) +
Σ j=1
(1) Di = j)-
(A.1)
Summing both sides over 1,... ni we have
n
1
ddur+1 (2;) = Σ duu((x)) = Σ
duuo(z;) O,
(A.2)
because uo(r;) is initialized as zero in Algorithm 2. Let be the solution of the Poisson equation
Lu(x;) = E(us - T)I((i = =) Aq((u(z;) 7))
(A.3)
1=1
satisfying En= dru(x;;= = 0. Define vr(xx)) = (ur)((())())) - u(xx)), Eq. A.3, we obtain
combining Eq. A.l and
(r(x)) Σ
Wij Aq.a, (r-2(;3);
(A.4)
d Aq
and Σj=1 uT(2)) = 0. Since the graph G with the weight matrix W - Aqq connected and the Markov chain induced by the corresponding random walk is aperiodic, we have limr- ut (xx) 4-2g E vo(2,) = 0, i.e., ur + u as T - oo, which completes the proof.d Ea
A.2 PROOF OF LEMMA 4.1
Lemma 4.1. The solution of the Poisson equation in Eq. 3.2 equivalent to the minimizer of the objective Σi_ E (wig -xq:g))lu(xxs) ul.,))11.
13

---

Published as a conference paper at ICLR 2024
Proof.
When L(u, v) ||u 1212. we have
wsy((u(x;), u(x;)) - X Var[u]
m - u(
qe (1(( 2212
qi
u(<s))
gj (
(A.5)
12
n
-
u(xx
Σ
a 1111((1))12
4. (u((
j=1
(wyy - (xg (oag- u(2z)]1
2=1
which completes the proof.
A.3 PROOF OF THEOREM 4.4
Theorem 4.4 For 2 2, there exists a constant C, depending Ω and d, such that, when infzen,ees p.l 2 the functional in Eq. 4.3 shows convexity with respect to C²q(2)
Proof. Without any loss of generality, one can assume in Eq. 4.3 u is scalar function. It is well known that function f on finite or infinite dimensional space J is convex if and only if for any u, U. [(u + (v) a one dimensional convex function (Boyd & Vandenberghe, 2004). So given any JF and small
0, define that
Ip(u + ev) = / [ + ev)(x)
/ f (o)+)))()))) - // ( (o)))))(())))
(A.6)
2
We can derive the second-order deviate of I with respect to as follows
[" + ev) =pl 2) / (o)(v= ((Vu, (o)(x) + v=([v(())11)) / (x)dx
+ ( + (z)dr
(A.7)
(z) + + ((=))())dm)²
As aforementioned, a convex function on u if and only if ev) 2 for any v, leading us to investigate
I' ev) 2p / ( ec) "IV (x)
(A.8)
/ / (()))(()) + (A u(z))(=)d=)²
On one hand, by Poincaré- Wirtinngr inequality on the weighted Sobolev space W W.1-P(0 ((2) satisfying (S [V 1/p oo, there exists constant C 0 depending on d and g. such that
[ (olo) (v(o)-/((a)aooaaa) a(x)dx
cc ( ((IVoce)BB(ladd))
1/2
(A.9)
14

---

Published as a conference paper at ICLR 2024
On the other hand, by mean value theorem, there exists &. such that
J co\))) (x) (V
[IV(u + ( / (Vo()))
((E)
(A.10)
Together with Eq. A.9 and Eq. A. it immediately implies that when A S C2
P-lVV((e) [ " pe ( (c)
infZeR,EE
is a convex function on u.
(2q(z)
A.4 PROOF OF THEOREM 4.5
Theorem 4.5. Suppose the density is bounded and continuously differentiable. If X S infEERNET V-l)V 1.p'"" then any wwice-differentiabee minimizer u R - Ik of the func- C+g(z)
tional in Eq. 4.3 must satisfy the Euler-Lagrange equation
d-v (I"(r) + Au(x)((2) - -)o(a)))))((aa) / (())u(=)dx O.
(A.11)
S2 f2... Ei Sx) for f : + R* and D, Dp( diag (IV (z)1 (V22(z)) - |V (x))3 112-)) If moreover the distribution μ has full
where div(Vf) (Ei S, Σ 0
support, then this equation is equivalent to
div(Vu(z)) + 2o + (1- 2(z)) + Ag(x) and [((())(())d= 0, where u Vu, Vu. Vui V
px²(x) (p((u))-u(z)) = 0, (A.12)
Vu, Vi
Vu Fuuuuuy Vuull
Proof. Without any loss of generality, one can assume in Eq. 4.3 is a scalar function, since we can analyze each component u independently. Let (p(u) = [[
((())) (ʃ ((=))(=)) The function u is a minimizer the functional Ip if for all test functions h and all-sufficient small real numbers e > we have Ip(u + eh) Ip(u). Moreover, by Taylor series expansion, we have
Ip(u + ch) =Ip(u) + pc (Vu(s)) (Vu(z).Vh(x)) vh(z)) [Vu(())l 222
(A.13)
(f (((a))Movala)dr- f f / [())(()))) +0())
where the O(2)) term is non-negative by convexity of Ip. Hence, the function is a minimizer if and only if
0 = (Vu(t), vh(x)) 2 - A u(=))(=)((+)dd
(A.14)
+ + (())(())))
/ Mz)g(1)dz
for all testing functions h. By integrating by parts and choosing h to vanish on the boundary of S the integration by parts formula shows that the above quantity is equal to
/ (Vu(z), Vh(a)) [[Vu()) 2 (x)dkr = - div d ( Vu(()) h(x)dr,
(A.15)
where div(V/) = &2 for f R
This expression has to vanish for all test functions h (that vanish on the boundary), which implies the Euler-Lagrange equation
p Vu((x) + Au(z)q(z) >a(x)) / [((x)(=)ddr = 0.
(A.16)
15

---

Published as a conference paper at ICLR 2024
We now further manipulate this equation to obtain the p-Poisson equation. In particular, some straightforward computations yield
0z. "ut
u(x),
(A.17)
and 02 V (x) =(0,, - V[(=)))((
(A.18)
(x) 2)
Σ Sene (IVu())
Now summing these terms yield
div (="(=)\ Vu(z)) + +*2 V=) A2u(())
+ 21-
Σ
Oz.f f. Denee 0z,f (x)
(1==1
=,((=\\VV(=>II== (Aau(a) + p(x)
(Vu(x), Vu(x)) + (p- - 2) 2))
where 425 = Tr(V2)) is the usual 2-Laplacian operator, while A (VVV is the co-Laplacian operator, which is defined to be zero when Vf = O.
(VIN))
From the derivation above, let v(x)
u(x) I (()))())dr have then the Euler-
div (e<)) equation in Eq. A.16 is equivalent to
div (
p. n ( 2, (22(()) 2(Vn(x), Vr(x)) + (p (00=)))m((r)) + >g(x))(()) O,
((x)
that is
Azu(1) + 2(V 2(V ((x), Vu(z)) (p 2) A g(z)o(x)
0, (A.19)
Vo(x)\11
and f ((())(()) = O, which completes the proof.
B MORE EXPERIMENTAL DETAILS AND RESULTS
B.1 EXPERIMENTS FOR V-LAPLACE AND V-POISSON
Datasets. We assess V-Laplace and V-Poisson on three datasets: MNIST (LeCun et al., 1998). FaShionMNIST (Xiao al., 2017), and CIFAR-I0 (Krizhevsky & Hinton, 2009). We follow the setting in Calder et al. (2020), where variational autoencoders with 3 fully connected layers of sizes (784,400.20) and (784, 400. 30) are used, respectively, followed by symmetrically defined decoder. The autoencoder is trained for 100 epochs each dataset. The autoencoder architecture, loss, and training, are similar to (Kingma Welling, 2013).
For each dataset, we create graph in the latent feature space using all available data, resulting in n = 70, 000 nodes for MNIST and FashionMNIST, and n = 60, 000 nodes for CIFAR-10 10. The graph is constructed as K-nearest neighbor graph with Gaussian-like weights, calculated as Wi = cxp(-4|ja - 2, / (zx)²) + e, where 2; represents the latent variables for example i, dx (zx) is the distance in the latent space between 2; and its K-th nearest neighbor, and 2 0. We set K = 10 and e = across all experiments. The weight matrices are symmetrized by replacing W with W WT_ For simplicity, we directly utilize the off-the-self distance matrices available
16

---

Published as a conference paper at ICLR 2024
Table 5: MNIST: Average accuracy scores 100 trials with standard deviation in brackets.
# LABELS
LAPLACE/LP (ZItU ET AL., 2003)
16.7 (8.0)
30.8 (12.8)
47.0 (15.0)
64.9 (13.3)
76.2 (10.3)
NEAREST NEIGHBOR
56.2 (4.9)
(3.8)
(2.6)
(2.7)
(2.2)
RANDOM WALK (ZHOU SCHOLKOPE, 2004)
(4.0
(2.5)
91.7
93.9(1.1)
94.5 (0.8)
MRO
2014)
(6.2)
(6.9)
(7.4
(0.7
(6.0)
WNLL BT AL., 2017)
(14.3)
(5.8)
(2.5
91.4
(0.7)
CENTERED
(MAI COUILEE,, 2018)
(5.0)
(2.5)
92.5(1.8)
(1.9(
94.7 (0.9)
SPARSE LP (JUNG Al.,, 2016)
(5.5)
(4.0)
(4.5
(8.0
16.2 (4.2)
P-LAPLACE (RIOS ET AL.. 2019)
(4.8)
82.7 (3.4)
(2.3)
81.7
89.7 (1.3)
POISSON (CALDER AL., 2020)
(4.3
(1.7
(1.1
95.5
95.8 (0.6)
V-LAPLACK (A- 0.001)
(4.9
(1.8)
94.7 (1.))
(0.7)
95.7 (0.6)
V-LAPLACR (A 0.002)
89.1 (4.6)
93.9 (1.8)
94.8 (1.1)
95.5 (0.7)
95.8 (0.6)
V-LAPLACE (A = 0.005)
89.7
94.1 (1.7)
(1.1
95.6 (0.6)
95.8 (0.6)
V-LAPLACE (A 0.01)
90.5 (4.44
94.5
(1.0
95.7 (0.6)
95.9 (0.6)
V-LAPLACK LA 0.02)
(1.3
94.9
(0.9)
93.9 (0.5)
96.1 (0.5)
V-LAPLACR (A 0.05)
91.6
95.2 (1.8)
95.8 (0.9)
96.2 (0.5)
96.3 (0.9)
V-LAPLACE (A- = 0.1)
91.2 (4.9)
(2.3)
(1.)
96.2 (0.7)
96.3 (1.0)
V-LAPLACR (A 0.2)
(L.0
96.3 (0.5)
96.3 (1.0)
V-LAPLACE (A 0.5)
(4.3)
95.3 (1.5)
95.9 (0.8)
96.2 (0.5)
96.3 (0.5)
V-LAPLACE (A- = 1.0)
91.7 (4.0)
95.0 (1.4)
95.6 (0.9)
96.0 (0.6)
96.2 (0.5)
V-POISSON (A= 0.001)
91.4
(1.6)
(L.1
95.6 (0.7)
95.8 (0.6)
V-POISSON 0.002)
(1.6)
(1.0)
(0.7)
(0.5)
V-POISSON (A= 0.005)
91.8 (4.1)
94.6 (1.6)
(1.0)
95.7 (0.6)
95.9 (0.5)
V-POISSON -0.0))
92.2 (4.1)
94.8 (1.5)
(1.0)
95.8 (0.6)
96.0 (0.5)
V-POISSON 0.02))
92.8 (4.0)
(1.2
(0.9)
96.0 (0.6)
96.2 (0.5)
V-POISSON (A- 0.05)
(3.9)
(1.4)
96.0 (9.7)
96.3 (0.5)
96.4 (0.4)
V-POISSON 0.1)
93.5
95.7 (1.5)
96.1 (0.7)
96.4 (0.4)
96.4 (0.5)
V-POISSON (A= 0.2)
93,6 (3.9)
(1.5)
96.1 (0.6)
96.4 (0.4)
96.4 (0.4)
V-POISSON (A- 0.5)
93.4 (3.9) (3.9)
95.6
96.0 (9.7)
96.3 (0.5)
96.4 (0.4)
V-POISSON
(0.9)
(0.6)
In term of the total number of iterations, we employ the trick by Calder et al. (2020). Specifically, add the iteration step P++1 WD WD-1pp in the algorithms of V-Laplace and V-Poisson, where pa is initialized as a vector with ones at the positions of all labeled vertices and zeros elsewhere. The iterations for V-Laplace and V-Poisson are terminated once llp: - loo < + is achieved, just before reaching the mixing time. Herein, Pxx W1/(1 W1) represents the invariant distribution.
Comparisons. We conduct a comparative evaluation of V-Laplace and V-Poisson against various graph-based semi-supervised learning methodologies, including Laplace learning (Zhu et al., 2003), lazy random walks (Zhou et al., 2003; Zhou & Schölkopf, 2004), multiclass MBO (Garcia-Cardona al., 2014), weighted nonlocal Laplacian (Shi et al., 2017), Centered Kernel Method (Mai & Couillet, 2018), sparse label propagation (Jung et al., 2016), p-Laplace learning (Rios et al., 2019), and Poisson learning (Calder et al., 2020). For the @elumesoonstrriieee MBO method, we set the temperature = 0.1. In the case of the Centered Kernel Method, we selected to be 5% larger than the spectral norm of the centered weight matrix. Throughout our experiments, we ran 100 trials, varying the random seed from 0 to 99. It's worth noting that the results for MBO and Sparse Laplace Propagation are adopted from Calder et al. (2020).
Prrpe--arrametes. Our proposed V-Laplace and V-Poisson have only one dyper-paramest À to control the strength of enlarging variance. In order to better illustrate its sensitivity, we provide more results in Table Table 6, and Table For the results of V-Laplace in Table 1, Table 2 and Table 3, we set À = 0.5, x = 1.0 and = 0.05, respectively. For the results of V-Poisson in Table 1 and Table we À 0.2, À 1.0, respectively. For V-Poisson learning on CIFAR-10, we directly use Poisson learning on the weight matrix which we subtract the elements greater than 0 from their minimum value.
Experiments on Self-Supervised Learned Representations on CIFAR-10. Self-supervised mod- els do currently exhibit promising properties in learning representations, and achieving relatively high linear probes. However, when the number of labels is particularly scarce, for instance, with only one label per class, self-supervised models possess good representations but struggle to learn effective classifiers. To illustrate this point, we refer to the open-source code and model parameters associated
17

---

Published as a conference paper at ICLR 2024
Table 6: FashionMNIST: Average accuracy scores over 100 trials with standard deviation brackets.
LABELS PER CLASS
2
LAPLACE/LP (ZII ET Al., 2003)
17.0
31.7 (10.0)
43.3 (8.4)
(6.9
59.3 (5.7)
NEIGHBOR
(4.9
43.6
(2.0)
(2.4
56.9 (2.7)
RANDOM WALK (ZHOU & SCHOLKOPE, 2004)
(4.8)
(4.0
(2.8
68.5
70. (2.2)
MBO GGARCIA-CARDONE ET AL., 2014)
(4.1)
(4.6)
24.7
30.7
34.8 (4.3)
WNLL (SHI AL., 2017)
(3.6
(5.6
63.0
67.1
62.6
CENTERED KERNEL (MAI COUILEE,, 2018)
(4.6
(4.4)
53.5
58.4
(3.4
SPARSE I.P (JUNG RT 2016)
14.0
(4.0)
(4.0
(8.0
(4.2)
1-LAPLACE (RiOS BT AL., 2019)
(4.8)
(3.7)
(3.0)
66.0 (4.3
(CALDER AL., 2020)
(4.7)
(2.7)
72.2 (2.2)
V-LAPLACE 0.001)
(5.1)
65.1 (4.2)
68.3 (2.7)
70.2 (2.6)
71.8 (2.2)
V-LAPLACE 0.002)
(5.0)
(4.2)
68.4
(2.6)
71.9 (2.2)
V-LAPLACE (A 0.005)
(5.0)
65.4 (4.2)
68.5 (2.7)
70.4 (2.6)
(2.2)
V-LAPLACE
(5.0)
70.5
(2.3)
V-LAPLACE (A 0.02)
59.7
65.9 (4.3)
68.8 (3.0)
72.7
(2.4)
Y-LAPLACE 0.05)
(5.9)
(4.7)
68.3 (3.9)
(3.4)
72.1 (2.9)
Y-LAPLACE 0.1)
58.9 (6.0)
(4.7)
(4.9)
69.6
71.7 (3.1)
Y-LAPLACE 0.2)
59.2
65.3 (4.7)
68.0 (3.8)
(3.4(3..)
71.7 (3.0)
V-LAPLACE 0.5)
60.1
65.9
68.7
70.4
(2.66
V-LAPLACE (A= 1.0)
60.6 (5.0)
66.3 (4.2)
69.2 (2.8)
71.0 (2.8)
(2.3)
V-POISSON (A 0.001)
60.5 (4.7)
66.3 (4.0)
68.9 (2.7)
70.8 (2.4)
(2.2)
V-POISSON AA 0.002)
60.6 (4.7)
66.4 (4.0)
68.9 (2.7)
70.8 (2.4)
72.3 (2.2)
V-POISSON (A 0.005)
60.7 (4.7)
66.5
70.9 (2.4)
(2.2)
V-POISSON (A = 0.01)
60.9 (4.9)
66.7 (4.1)
69.2 (2.7)
71.0 (2.4)
72.5 (2.2)
A 0.02))
(2.3)
V-POISSON (A 0.05)
(0.5)
66.7 (4.5)
69.2
70.7 (3.4)
72.6 (2.8)
V-POISSON (A = 0.1)
60.5 (5.5)
(4.5)
(3.6
(3.5)
(2.9)
V-POISSON FA 0.2)
60.7 (5.4)
(4.4)
(3.4)
(3.3
72.2 (2.7)
V-POISSON (A 0.5)
61.2 (5.1)
67.0 (4.3)
63.5
(2.9)
72.7 (2.5)
V-POISSON (A
61.3 67.1
69.7
71.3 71.3
(2.3)
with an exemplary linear probe achievement of 91.9% on CIFAR-10. The source code and model 1---op--acc-oo------
10, which utilizes the SimSiam framework (Chen & He, 2021). Building upon the pretrained model, we conduct two experiments underscore the effectiveness of graph-
parameters are available at
supervupee learning in scenarios of label scarcity: (i) We utilize the SimSiam pretrained model to extract features from the entire CIFAR- 10 dataset and construct (O-nearest-neighhee
graph on these representations. We then randomly choosing which data points are labeled, and predict unlabeled data for all data points using different graph-baser semi-supervised learning approaches; (ii) For comparison, we directly several randomly chosen labeled data to obtain linear classifier, and finally use this classifier to evaluate the classification accuracy of all samples.
The experimental results are summarized in Table 8. It is evident that the linear classifier, trained solely on labeled data, outperforms Laplace in scenarios with extremely sparse data. However, is crucial to note that linear classification exhibits significantly lower performance compared to other methods, particularly when compared to our proposed V-Laplace and V-Poisson methods.
B.2 EXPERIMENTS FOR V-GPN ON SEMI-SUPERVISED NODE CLASSIFICATION
The experiments are conducted on two commonly-usee used citation network datasets (Sen et al., 2008). In the citation networks, the nodes represent documents and their links refer to citations between documents, where each node is associated with a bag-of wordds feature vector and a label. Moreover, exp(s-f(ary)) for the labeled node (r, y). we use the CE loss with a scale parameter 8, i.e., - logg E f(ar)
The parae-parameters, such as learning rate n, weight decay wd, the scale parameter s and the variance-enlarged parameter À are determined by grid search. Concretely, v E {0.1, 0.05, 0.01 }. wdd (le 2, 5e - 3, le 3, 5,5e-4p 44, E (1,5, 10} and 0.5,, which can also be found in the code of supplement materials.
18

---

Published as a conference paper at ICLR 2024
Table Classification accuracy (%) of different methods on CIFAR-10 with several labels per class 2,3, 4, 5}). The results described as "mean (std)" are run over 100 trials. Results achieved by V-Laplace and V-Poisson that outperform their original ones are boldfaced and the the best results are underlined.
# LABELS PER CLASS
1
3
4
5
LAPLACE/LP (ZHU 2003)
(1.2)
(1.7
11.8
(4.0
13.1 (3.4)
NEAREST NEIGHBOR
(3.9)
(3.3)
35.1 (2.9)
(2.3
37.4
(2.4)
2004)
MBO (GARCIA CARDONA ET AL., 2014)
(4.1
(9.2
(5.6)
(5.6)
(3.7)
(SHI ET Al., 2017)
(4.8)
26.9
33.2
38.4
(5.5)
CENTERED KERNEL (MAI & COUILLET, 2018)
(5.4)
(5.4
(3.0
43.6
(2.7)
SPARSE LP (JUNG ET AL.. 2016)
(2.4
(2.4
(3.3)
(4.4
(2.9)
P-LAPLACE (Rios
2019)
(4.7)
(3.5
(3.6)
(2.2)
48.8 (2.8)
POISSON (CALDER ET Al.,, 2020)
39.1 (5.4)
(3.9)
(3.6)
51.2 (3.0)
$2.9 (2.8)
V-LAPLACE (A 0.001)
31.1 (6.0)
38.7 (4.7)
43.1 (5.3)
45.7 (5.0)
47.6 (4.3)
V-LAPLACE (A 0.002)
31.2 (5.9)
38.8 (4.6)
43.2 (5.3)
(5.0)
47.7 (4.3)
V-LAPLACE (A 0.005)
31.6 (S.9)
39.1 (4.6)
(5.2)
(4.9)
47.8 (4.2)
V-LAPLACE (A 0.01)
32.1 (5.9)
(4.5)
43.7 (5.1)
46.3 (4.9)
48.0 (4.2)
V-LAPLACE (A 0.05)
33.9 (5.6)
(4.3
44.0
(4.8
47.8 (4.3)
V-LAPLACE (A 0.1)
(4.6)
44.6 (4.9)
V-LAPLACE (A 0.2)
31,7 (5.5)
36.4 (4.5)
38.9
40.3 (5.4)
41.2 (5.0)
V-LAPLACE A 0.5)
33.1 (5.4)
38.1 (4.5)
40.5 (4.6)
(2.2)
43.1
V-LAPLACE (A 1.0)
35.2 (5.7)
41.4 (4.3)
44,2 (4.7)
46.6 (4.8)
47.3
V-POISSON 0.005)
(5.4)
(3.8)
(2.7)
V-POISSON (A 0.01)
39.2 (5.4)
(3.9)
49.3 (3.5)
$2.3 (2.8)
54,0 (2.7)
V-POISSON 0.05)
39.6 (5.5)
46.7 (3.9)
49.8 (3.5)
52.7 (2.8)
54.4 (2.7)
V-POISSON 0.1)
40,0 (5.5)
47.0
50.2 (3.5)
(3.8
54.9 (2.7)
V-POISSON 0.2)
40.3 (5.6)
47.1 (3.9)
50.8 (3.6)
53.9 (2.9)
$5.5 (2.7)
V-POISSON (A 1.0)
41.4 (5.4)
48.5
$1.7 (3.7)
54.7 (3.1)
56.3 (2.8)
Table 8: Classification accuracy (%) different methods for self-supervised representations on CIFAR-10 with several labels per class (11, 2, 3, 4, 4)). The results described "mean (std)" run over 100 trials. Results achieved by V-Laplace and V-Poisson that outperform their original ones are boldfaced and the the best results underlined.
LABELS PER
5
(ZHU AL.. 2003)
(7.0)
33.4
RANDOM WALK (ZIOU & SCHÖLKOPT, 2004)
(6.6
76.7 (3.5)
(3.4)
(2.2
82.2 (1.9)
WNLL (SHI ET AL., 2017)
52.6
(5.0)
78.7 (4.2)
82.5
(1.9)
CENTERED KERNEL (MAI COUILLET, 2018)
(5.2
56.1 (4.9)
63.1 (4.9)
67.6 (4.3)
70.5 (3.1)
POISSON (CALDER ET AI.,, 2020)
(6.9
80.4 (3.0)
82.7 (2.7)
84.0
84.8 (1.6)
LINEAR CLASSIFIER
(4.3)
53.9
60.8 (3.2)
(3.3)
68.8 (2.7)
V-LAPLACE
74.6 (5.7)
(2.7)
83.1 (3.0)
84.3 (2.0)
84.8 (1.8)
V-POISSON
75.6 (5.8)
81.7 (2.8)
83.8 (2.4)
84.8 (1.8)
85.5 (1.6)
19


Reviews:
[{"review_id": "Gs5NSnG2pW", "reviewer": "Reviewer_HipA", "summary": "Semi-supervised learning (SSL) aims to leverage a vast amount of freely available unlabeled data alongside a small sample of expensive labeled data to improve the classification performance of a learnt model. Graph SSL techniques are a popular class of approaches where by constructing a graph with data points nodes and relationship edges, information can be propagated across the graph to make predictions on unlabeled data. A well-recognized limitation of typical Graph SSL techniques is the problem of degenerate solutions where, when the labeled sample is sparse, the nodes far away from any labeled sample can converge to a constant and uninformative value.\n\nThis paper proposes a simple and intuitive fix to degeneracy issue by regularizing the node values to be different from one another through a term that increases the variance between node values. Clear theoretical insights have been provided to show that, when the graph edges connect same class nodes more often than others, variance enlargement can amplify the importance of edge weights connecting vertices within the same class, while simultaneously diminishing the importance of those connecting vertices from different classes, thus leading to improved solutions.\n\nExperimental results show salient gains due to variance enlargement regularize on a variety of datasets.", "questions": "Can variance enlargement help with other Graph SSL approaches besides GPN? If so, a discussion on where and why it helps and does not help, can be useful and interesting.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* SSL is an important problem and the paper addresses the crucial issue of node degeneracy in Graph SSL. As such, the problem is well-motivated\n* The solution is simple and intuitive and theoretical connections are provided to explain the inner workings of the proposed technique\n* Experiments are conducted on a wide range of datasets and show significant gains which demonstrates the utility of the technique", "weaknesses": "* Many variants of Graph SSL have been proposed in the literature. It will be interesting to discuss the effect of variance enlargement on those also beyond V-GPN that the paper explores.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ORCQPGsVEL", "reviewer": "Reviewer_CApx", "summary": "This paper addresses the issue of traditional graph-based semi-supervised learning leading to degenerate solutions when labeled data is extremely sparse. It introduces VPL, which mitigates this problem by increasing the variance of predictions for unlabeled data. Furthermore, based on classical Laplace learning and Poisson learning, the paper proposes V-Laplace and V-Poisson as improvements. Extensive experiments have demonstrated the effectiveness of these approaches.", "questions": "I hope the authors can answer the last point in Weaknesses, and I am glad to raise my score if my concern can be addressed.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides an overview of classical graph-based semi-supervised learning tasks, and the proposed idea, while simple, is highly effective. Its parameter-free nature makes it more appealing.\n- The writing in this paper is of excellent quality, and the motivation and introduction of the proposed method are presented in a clear and easily understandable manner.\n- This paper provides a thorough and reliable theoretical analysis.\n- In addition to the general graph-based SSL methods like Laplace Learning, this paper also extends to GNN-based method and proposes V-GPN.", "weaknesses": "- Disclaimer: I am familiar with GNN-based semi-supervised learning and have knowledge of Laplace Learning and Poisson Learning, but I am not familiar with their applications in non-graph structured data. I noticed that the experiments primarily focus on datasets like (Fashion) MNIST and CIFAR-10. It would be beneficial to expand the experiments to larger datasets, such as ImageNet.\n- Typos: e.g., lambda in the caption of Figure 1.\n\nMy other concern is the practical value of such graph-based (parameter-free) semi-supervised learning methods. As shown in Table 2 and Table 3, despite significant improvements over the baselines, the accuracy of the proposed method still falls short of being satisfactory. To my knowledge, parameterized models like ResNet and ViT-based self-supervised learning methods tend to perform better in cases of label sparsity. Therefore, in resource-abundant scenarios, it seems that having a parameter-free model with relatively poorer performance may not be very meaningful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HMrdZW3bvw", "reviewer": "Reviewer_JXpL", "summary": "The paper introduces a graph-based transductive semi-supervised learning method, which modifies Laplace and Poisson learning techniques by incorporating a variance-enlarged term for regularization. The authors present algorithms for these 'variance-enlarged' learning methods. Additionally, they propose a novel message passing layer with attention for Graph Neural Networks (GNNs) to enhance label variance, based on the 'label propagation' step of their algorithms. These contributions are tested in scenarios with limited labeled data and compare favorably against other methods.\n\nOn the theoretical front, the paper explores both discrete and variational cases. In the discrete case, the variance enlarged approach corresponds to a reduction of the edge-weights, which, under certain conditions, strengthens connections between nodes of the same class and weakens those between nodes of different classes. In the variational case, the minimizer of theoptimization problem is expressed as the solution of a PDE.", "questions": "1. **Iterative vs. Linear Solution:**\n   \n   - In Algorithm 1, you've chosen an iterative approach for solving V-Laplace Learning. However, the conventional Laplace learning approach can be solved directly through a linear system ([1,2]). I'm curious if your method could also utilize a linear system solution. Is there a specific reason for the iterative approach? Is it faster?\n\n2. **Relation to Previous Work:**\n   \n   - In [2], Laplace learning was associated with the probability of sampling a spanning forest that separates the seeds. Do you think your approach could also have a similar interpretation in this context?\n\n3. **Consideration of Directed Graphs:**\n   \n   - As far as I understand, your approach does not consider directed graphs. Does your approach and the theoretical insights extend to the directed case as well?\n\n4. **Convergence Dependency on Parameters:**\n   \n   - I'm interested in understanding how the convergence of your algorithms is influenced by the value of $\\lambda$. Could you shed some light on this relationship?\n\n5. **Clarification on Lemma 4.1:**\n   \n   - In the final step of Lemma 4.1, it seems that the sum of $q_j$ is factored out of the norm. However, this step isn't clear to me. Could you provide a more explicit explanation of how this is done? To illustrate, if I consider $(u_1,u_2)=(0.5,1)$, $(q_1,q_2)=(0.5,0.5)$, $\\lambda=1$ and $w_{12}=w_{21}=1$, the equation doesn't seem to balance. The right term of the inequality is equal to \n$\\sum_i^n\\sum_j^n(w_{ij}-\\lambda q_iq_j)||u(x_i)-u(x_j)||_2^2=$ \n\n$=2\\left((w_{12}-\\lambda q_1q_2)(u_1-u_2)^2\\right)=2\\left((1-0.5^2)(0.5-1)^2\\right)=0.375$\n\nWhile the left term is equal to\n\n$\\sum_i^n\\sum_j^n(w_{ij})||u(x_i)-u(x_j)||_2^2-\\lambda\\sum_i^nq_i\\left|\\left|u(x_i)-\\sum_j^nq_ju(x_j)\\right|\\right|^2_2=$\n\n$=2\\left(w_{12}(u_1-u_2)^2\\right)-\\left(q_1\\left(u_1-\\left(q_1u_1+q_2u_2\\right)\\right)^2+q_2\\left(u_2-\\left(q_1u_1+q_2u_2\\right)\\right)^2\\right)=$\n$=2\\cdot0.5^2-\\left(0.5\\left(0.5-\\left(0.5\\cdot0.5+0.5\\cdot 1\\right)\\right)^2+0.5\\left(1-\\left(0.5\\cdot0.5+0.5\\cdot 1\\right)\\right)^2\\right)\\\\\n     =0.4375$\n\nThis clarification is crucial as Theorem 3.1 and Proposition 4.3 depend on this Lemma.\n\n6. **Typos**:\n   \n   - In proposition 4.3 references Theorem 4.1. It should be Lemma 4.1.\n   \n   - Table 7  does not contain the accuracies for the V-Poisson method. \n   \n   - Table 5 and 6 do not contain any clarification regarding the meaning of the bold values.\n\n[1] Grady, \"Random Walks for Image Segmentation\" (2006)\n\n[2] Fita Sanmartin et al. “Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning” (2019)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written.\n  \n- The paper presents a variety of contributions of theoretical and practical nature.\n  \n- The proposed algorithms are simple yet effective as shown in the experiments section.", "weaknesses": "I suspect Lemma 4.1 could have an error and therefore all proofs that derive from it. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ThITRFsJdu", "reviewer": "Reviewer_cv8h", "summary": "This paper proposes effective graph-based semi-supervised learning approaches for sparsely labeled data. To improve the accuracy, the proposed approach adds a term of the label variance to the objective function of graph-based semi-supervised learning. The paper conducted experiments to show the effectiveness of the proposed approach.", "questions": "The paper compares V-Laplace and V-Poisson to other graph-based approaches in the experiment. However, the compared approaches are somewhat old; the most recent one was published in 2020 (POISSON). Similarly, it compares V-GPN to other GNN approaches. However, they are not state-of-the-art, although GNN is a well-studied technique. Is the proposed approach more accurate than recent approaches?\n\nAlthough k-NN graphs were used in the experiment, the detailed experimental settings are unclear from the descriptions of the paper. k-NN graphs are used in the experiment? What is the number of edges from each node? How do you set edge weight? Is the proposed approach used even if other graph structures are used besides k-NN graphs?\n\nIn the datasets used in the experiment, it seems that labels evenly exist. Could you tell me whether the proposed approach is useful for labels of screwed distribution? Please tell me whether the proposed approach is more accurate than other approaches even if labels do not sparsely exist (i.e., we have plenty of labels)? In addition, how do you determine the number of iterations in the proposed approach?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Graph-based semi-supervised learning is an important research problem in the field. \n- The proposed approach is simple and intuitive. \n- The theoretical properties of the proposed approach are well discussed in the paper.", "weaknesses": "- The compared approaches in the experiment are somewhat old.\n- Graph structures used in the experiment are unclear from the description of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)