Label Propagation with Weak Supervision
Authors: Rattana Pukdee
Dylan Sam
Pradeep Kumar Ravikumar
Nina Balcan
Venue: ICLR 2023 poster (2023)
Keywords: Semi-supervised learning
Weakly supervised learning
Label propagation

Abstract: Semi-supervised learning and weakly supervised learning are important paradigms that aim to reduce the growing demand for labeled data in current machine learning applications. In this paper, we introduce a novel analysis of the classical label propagation algorithm (LPA) (Zhu & Ghahramani, 2002) that moreover takes advantage of useful prior information, specifically probabilistic hypothesized labels on the unlabeled data. We provide an error bound that exploits both the local geometric properties of the underlying graph and the quality of the prior information. We also propose a framework to incorporate multiple sources of noisy information. In particular, we consider the setting of weak supervision, where our sources of information are weak labelers. We demonstrate the ability of our approach on multiple benchmark weakly supervised classification tasks, showing improvements upon existing semi-supervised and weakly supervised methods. 

Published as a conference paper at ICLR 2023
LABEL PROPAGATION WITH WEAK SUPERVISION
Rattana Pukdee", Dylan Sam', Maria- Balcan, Pradeep Ravikumar Machine Learning Department Carnegie Mellon University
Pittsburgh, USA
frpukdee dylansam]2cs. cmu. cmu.edu
ABSTRACT
Semi-supervised learning and weakly supervised learning are important paradigms that aim to reduce the growing demand for labeled data in current machine learning applications. In this paper, we introduce novel analysis of the classical label prop- agation algorithm (LPA) (Zhu & Ghahramani, 2002) that moreover takes advantage of useful prior information, specifically probabilistic hypothesized labels on the unlabeled data. We provide an error bound that exploits both the local geometric properties of the underlying graph and the quality of the prior information. We also propose framework to incorporate multiple sources of noisy information. In particular, we consider the setting of weak supervision, where our sources of information are weak labelers. We demonstrate the ability of our approach on multiple benchmark weakly supervised classification tasks, showing improvements upon existing semi-supervised and weakly supervised methods.
INTRODUCTION
High- digeensimeniin machine learning models require large labeled datasets for good performance and generalization. In the paradigm of semi-supervised learning, we look to overcome the bottleneck of labeled data by leveraging large amounts of unlabeled data and assumptions on how the target predictor behaves over the unlabeled samples. In this work, we focus on the classical semi-supervised approach of label propagation (LPA) (Zhu & Ghahramani, 2002: Zhou al., 2003). This method propagates labels from labeled to unlabeled samples, under the assumption that the target predictor is smooth with respect to graph over the samples (that is frequently defined by a euclidean distance threshold or nearest neighbors). However, in practice, to satisfy this strong assumption, the graph can be highly disconnected. In these cases, I.A performs well locally on regions connected to labeled points, but has low overall coverage as it cannot propagate to points beyond these connected regions.
In practice, we also have additional side-information beyond such smoothness of the target predictor. One concrete example of side information comes from the field of weakly supervised learning (WSL) (Ratner et al., 2016; 2017), which considers learning predictors from domain knowledge that takes the form of hand-engineered weak labelers. These weak labelers weak labels per unlabeled sample, and the focus in WSL is to aggregate these weak labels to produce noisy pseudolabels for each unlabeled sample. In practice, weak labelers are typically not designed to be smooth with respect to a graph, even though the underlying target predictor might be. For example, weak labelers are commonly defined as hard, binary predictions, with an ability abstain from predicting. We thus see that LPA and WSL have compiementary sources of information, as smoothing via LPA can improve the quality of weak labelers. By encouraging smoothness, predictions near multiple abstentions can be made more uncertain, and abstentions can be converted into predictions by confident nearby predictions.
heuristics that provide multiple
In this paper, we first bolster the theoretical foundations of LPA in the presence of side information. While L.A has a strong theoretical motivation of leveraging smoothness of the target predictor, there is limited theory on how accurate the propagated labels actually are. As key contribution of this paper, we provide a "fine-grained" theory of LPA when used with any general prior on the target classes of the unlabeled samples. We provide novel error bound for LPA, which depends on key
"Equal contribution

---

Published as a conference paper at ICLR 2023
local geometric properties of the graph, such underlying smoothness of the target predictor over the graph, and the flow of edges from labeled points, as well as the accuracy of our prior. Our bound provides intuition prioritize using prior information. We provide a comparison of our error bound to an existing spectral bound (Belkin & Niyogi, 2004) and demonstrate that our bound is preferable in some examples.
when LPA should prioritize propagating label information or when it should
Next, we propose a framework for incorporating multiple sources of noisy information to LPA by extending framework from Zhu et al. (2003). We construct additional "dongle" nodes in the graph that correspond to individual noisy labels. With these additional nodes, we connect them to unlabeled points that receive noisy predictions and perform label propagation on this new graph as usual. We study multiple different techniques for determining the weight on these additional edges.
Finally, we focus on the specific case when our side information comes from WSL. We provide ex- perimental results on standard weakly supervised benchmark tasks (Zhang et al., 2021) to support our theoretical claims and to compare our methods to standard LPA, other semi-supervised methods, and existing weakly supervised baselines. Our experiments demonstrate that incorporating smoothness via LPA in the standard weakly supervised pipeline leads to better performance, outperforming many existing WSL algorithms. This supports that there are significant benefits to combining LPA and WSL, and we believe that this intersection is a fertile ground for future research.
1.1 RELATED WORK
Label propagation Many papers have studied LPA from a theoretical standpoint. LPA has various connections to random walks, spectral clustering (Zhu et al., 2003), manifold learning (Belkin & Niyogi, 2004; Belkin al., 2006) and network generative models (Yamaguchi & Hayashi, 2017), graph conductance (Talukdar & Cohen, 2014). Another line of research in LPA proposes using prior information at the initialization of LPA (Yamaguchi et al., 2016; Zhou et al., 2018), with applications in image segmentation (Vernaza & Chandraker, 2017). distant supervision (Bing et al., 2015), and domain adaptation (Cai et al., 2021; Wei et al., 2020). Finally, as the graph has a large impact on the performance of LPA, another line of work studies how optimize the construction of the graph with linear- based (Wang & Zhang, 2007) methods, manifold maseedd-bbsed (Karasuyama & Mamitsuka, 2013) methods, deep leaming based methods (Liu et al., 2018; 2019).
Weakly supervised learning The field of (programmatic) weakly supervised learning provides a framework for creating and combining hand-engineered weak labelers (Ratner et al., 2016; 2017; 2019; Fu et al., 2020) to pseudolabel unlabeled data and train a downstream model. Recent advances in weakly supervised learning extend the setting to include small of labeled data. One recent line of work has considered constraining the space of possible pseudolabels via weak labeler accuracies (Arachie & Huang, 2019; Mazzetto al., 202la;;; Arachie & Huang, 2021; 2022). Other works improve the aggregation scheme (Xu et al., 2021) or the weak labelers (Awasthi et al., 2020). We note that only one method incorporates any notion of smoothness into the weakly supervised pipeline (Chen et al., 2022). This work leverages the smoothness of pretrained embeddings in clustering. While clustering and IPA have similar intuitions, they result fundamentally different notions of smoothness. We also remark that this paper does not consider the semi-supervised setting.
Semi-supervised learning Many other methods in semi-supervised learning look to induce smooth- ness in a learnt model. These include consistency regularization (Bachman al., 2014; Sajjadi et al., 2016; Samuli & Timo, 2017: Sohn et al., 2020) and co-training (Blum & Mitchell, 1998; Balcan et al., 2004; Han et al., 2018). In addition, Graph Neural Networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Gilmer et al., 2017; Scarselli et al., 2008; Gori et al., 2005; Henaff et al., 2015) is class of deep learning based methods that also operate over graphs. Some recent works (Huang et al., 2020; Wang & Leskovee, 2020; Dong et al., 2021) have made connections between graph neural networks and LPA. While all these methods focus on similar goal of learning a smooth function, they do not address the weakly supervised setting.
2 PRELIMINARIES
We consider binary classification setting where we want to learn a classifier f X' + {0. 1}. We observe small set of labeled data L {(xaa y: J= and a much larger set of unlabeled data U {2y 1n+m LPA relies on the assumption that nearby data points have similar labels. This is
2

---

Published as a conference paper at ICLR 2023
Ches
N2
On (1)
N₂
L
N
N1
N2.
Con = Ci (2)
N2
N1
N3
(a) Diagram of edges flow
(b) "In" "Out"
(c) "In" "Out
Figure I: A diagram of edges flow between neighborhoods of L. Color on each edge implies that the edge contributes which flows (In, Between, Out) (left). Examples of graphs with different structure, where colored points represent labeled points (middle, right).
expressed in terms of smoothness with respect to undirected graph G = (V, E), with V nodes representing each point x E L U, and with an adjacency matrix W = (w)).. LPA then leverages the assumption that adjacent points in this graph have similar labels, by propagating label information from to U. Specifically, learns f X + by solving the following optimization problem:
mm n-tm
min FER
Wiy(S: f,) s.t. 34 for
where f E Ru+m is the prediction vector and, abusing notation, f: = fa;)). The method generalizes to the multi-class setting by replacing with one-hot-encoding vector, and predicting score vector at each node. Zhu al. (2003) provides a quick iterative method solve this optimization problem.
3 LABEL PROPAGATION WITH PRIOR INFORMATION
We analyze LPA with initial noisy predictions h(x): + [0, 1]. by solving the following objective:
min SER
+
(fe ((zx)) s.t. f. y. for S
1=1
where y E IR determines how much the solution is regularized to be close to h. In the standard LPA, we have no prior information on the unlabeled points, which can be seen as the case when h 0.5 and μ + O. In our theory, h can be any general prior.
3.1 ERROR BOUND OF LPA WITH PRIOR INFORMATION
Similar to the standard LPA, there exists a closed form optimal solution Equation 1, which discussed in Appendix A. We know that, for the optimal solution of Equation 1, we can bound the error of point é ([fr yel) by the error of its neighbors and terms corresponding to the smoothness of the true labels and the prior information accuracy; we formally state this in Appendix B (Lemma 2). Because the error on laheled points are zero, we can bound the error in terms of the distance of a point to the nearest labeled point. For set of labeled data L, let (LL) be set of reachable points where there is at least one path from a point in L. Define a set of neighbors k-hops away from L as of points whose shortest path point in L is length k). Let be the number of hops required to cover N(L), Then, we have
NG (L) (i.e,
N(L) = LU NRLL.
k=

---

Published as a conference paper at ICLR 2023
For simplicity. we denote N& (L) and Ng as L. We now define terms that are fundamental to our enror bound. First, we introduce notions In-flow, Between-flow, and Out-flow, which represent the fraction of edges that flow in, between, and out of (Lx)..
Definition 1. For graph G with adjacency matrix W = (w)is and a set of k-hop neighbors No.
we define the In-flow, Between-flow and Out-flow of N₂ as
(k)
Σ
Wijs
(k)
E
Waj.
SENN.JEN,
iEN..ENN.
Σ
Wij
iENE.JENEIL
These terms are related to the notion of conductance, which measures the fraction of out-going edges from any subset of nodes. We can write the Dirichlet conductance (HaoChen et al., 2021) of neighborhood Ng follows
Cin(k) + (km ((N)) Cin(k: + Cha(k) Cour
Definition 2. (Ratio between Out-flow and In-flow)
(ku
+in(k)
Th a proportion of the Out-flow and In-flow edges of neighborhood (see Figure for graphs with different flow). Next, we define the smoothness of Nkx prior information enror, and average error.
Definition 3. (Smoothness of neighborhood) For s k I I, we define the smoothness of true labels of points in N2 with respect the graph as
Σ Wiyl Wirly; - yal-
Sk
iEN
Definition 4. (Prior information error) For $ k let the average error of the prior in N₁. be
ΣIEN, 1h, Vel
OK
W
Definition 5. (Average error) We define the average error the No.
Ev ΣIEN. 1sT vsl
Theorem 1. (Informal version of Theorem 3) Let f be the optimal solution of the optimization problem of Equation 1, under Assumption I which assume that average error of a fraction of points that has "Out" connections from neighborhood No of a constant factor of the average error in Ngg (refer to Appendix B), the error of f in each neighborhood N2 is given by
Es 50
Σ
de
where
5k 11) N1 J.Naay Iak
ds =
Cln(k) + NNN2
j=b
Proof. (Sketch) The key idea of our proof is to upper bound each E, for i E [1,..., the insight that we can bound the average error of set N; (points that are hops away from labeled points) with the average errors of its neighbors N and Not1 by using Lemma 2. We first bound E, with Eg and Eg, then we bound Eg with E, and Eg, and so on. See Appendix B for the full version of our proof.
|} by exploiting
4

---

Published as a conference paper at ICLR 2023
Figure 2: Example of graphs G1, G2, G3 (left, mid, right) to compare our bound to existing bounds. The background color represents the true label class, and colored points represents labeled points.
C is a combination of smoothness & and the prior accuracy Ogk, and ja controls the trade-off between using information from the graph the initialization. When μ without any prior. On the other hand, / + oo is equivalent to only using the initial predictions.
recover the standard LPA
de is a linear combination of c for h < i S where the coefficient of each is given by IT Yo representing the influence from N₁. When "j < 1 ("In" "Out"), the influence is exponentially small while when % > ("Out" "In") the influence can be exponentially large. This aligns with our intuition that when we have more "In" than "Out", we will have a better guarantee. We remark that if Ck = 0, regardless of the product II, 7/. Cj will make contribution to the bound.
To tighten this upper bound, we have to reduce both Cj and In doing so, the value of μ is important; larger value of μ reduces both cg and ? by increasing their denominators. Thus, given similar levels of smoothness and prior accuracy (C. arg), it is better to use a larger value of μ., that is we should rely more the prior information.
The number of hops (k) from labeled points L also plays a key role the bound. The upper bound on Eg is given by linear combination of & terms, points that closer to L will have smaller k and a better guarantee. This encourages us to have a more connected graph, requiring fewer hops to reach all points. However, adding noisy edges may potentially decrease the smoothness of the graph.
3.2 COMPARISON WITH PRIOR (SPECTRAL) BOUNDS
We compare our bound with an existing bound that relies on spectral analysis (Belkin & Niyogi, 2004). This bound is for LPA with soft constraint, given by the problem
min 4
Wig(i: fj)2 + Σ (Ji y1)
(2)
i5n
We define the empirical error and generalization eтror as:
n t
R₂ = n Σ (J+ vi) R() n + m
Σ (})-)))
As we do not have hard constraint (J: = for i S n), the empirical error is not necessary zero. Theorem 2. (Generalization performance of graph regularization (simplified version)) Let f be the optimal solution of Equation 2, n 2 4 be the number of randomly sampled labeled points from some graph G and X be the second smallest eigenvalue of the Laplacian matrix of G. With probability 1 5, we have
2log(2/0)
[Ra()) - R()) 8
(n,3 + 4)
n
where
37/² Vn
4n
(A1 1)
A1
The original version of this bound as in (Belkin & Niyogi, 2004) is in Appendix C. We consider graphs G1, G2, G3 in Figure to compare the bounds. Here u(G refers to the value of parameter u for graph G.
First, we note that this bounds the difference between the empirical error and the generalization error, while our bound is for the generalization emor itself. The spectral bound assumes that we have
5

---

Published as a conference paper at ICLR 2023
Add dongle nodes
Figure 3: One can turn the label propagation with multiple sources of information into standard label propagation problem by augmenting the graph G (left) with dongle nodes (right). The colored point represents labeled point. The points without the shade are dongle nodes.
randomly sampled initial labeled points, and thus the bound only depend on the number of labeled points. For example, G2 and G3 have the same underlying graph and the same number of labeled points, so they have the same spectral bound of generalization error, which relies on the empirical error. In contrast, our bound takes the position of labeled points into account to provide explicit explanation why LPA performs better on G2 than G3. We can see this since G2 is smoother than G3 1).
(g(Ga) (c2(G2) 0, (G3) C.(2)(C)))
The spectral bound depends the second smallest eigenvalue Å₁. If the graph is well clustered, d will be small. For example, A (G1) ) = 2, A (G2) = 0.53. Belkin & Niyogi (2004) suggests that when A is small, optimize the objective separately. Our bound works for any graph, in fact, our bound is also tight on G2 where LPA achieves zero error (as C1 (G2) c2 0). Also, as r + oc, the objective of Equation is equivalent to Equation 1. The, the spectral bound takes on value 3 - 3 3 4, which implies that it does not depend on the geometry of the graph (A1) anymore. Finally, the spectral
should cut the graph in two, using the eigenvector corresponding Å1, and
bound does not use any prior information, while our bound captures the interplay between the quality of graph and the quality of prior information.
LABEL PROPAGATION WITH MULTIPLE SOURCES OF INFORMATION
We now consider the setting where observe multiple sources of prior information and provide a framework to incorporate them into LPA. Assume that we have multiple initial noisy predictions ha(x) : X [0, 1] for 1,2,..., k. A natural extension of the LPA objective is given by
k
ΣΣ wisli f,)
Σ (fi hz(2z))
such that f; Ys for i S The first term encourages our prediction to be smooth with respect to graph while the second term encourage our prediction to also close to the initial predictions. The function o; X + [0, xx), which we need to learn, controls how close we want our final prediction to be to each initial prediction hj. We can turn this into a standard label propagation problem for which we have an efficient iterative method to solve by augmenting the graph G with dongle nodes (Appendix D). Given a fixed aj for each j = 1..... k, we can also show that there exists an initial prediction h where the solution of Equation 3 is equivalent to solution of LPA with single initial prediction h for which our analysis applies (Appendix E).
A key question is for this framework is "how to choose aj ?" In the ideal setting, set (x, 0 when h; makes an incorrect prediction for point x; and set (2;)) = when hy makes a correct prediction,
(x())) = (x1( > 0.5] w.l
However, this is not applicable in a practical setting knowing when h, is correct incorrect at point x; is equivalent to knowing the corresponding true label y; of that point. We now investigate different approaches select the function o.j.

---

Published as a conference paper at ICLR 2023
4.1 ESTIMATED ACCURACY
Although we do not know whether hj will make correct prediction at each point 2ú, we can still approximate its accuracy over the entire dataset. We use techniques from crowd-soureing literature or weak supervision literature to approximate the accuracy of each noisy labeler. Then, we can set aj as the estimated accuracy of a h2.
a3(,))) = (( (x) > 0.5] = y) - Pj-
We also consider setting 0j = In
Ps I-py
as in the boosting literature (in Appendix F.1).
4.2 PROBABILISTIC APPROACH
We can also consider probabilistic approach to select the function 0j. Let each hy be sampled from a Gaussian distribution
hy ~ Nyy (z))²
and let f follow the Gaussian field as in Zhu & Ghahramani (2002), where
pa(f) exp(-BE(f)), B(f) 1 n+m n+
Σ
wiy f3)2
Then, the log-likelihood is given by
n+m & -
n+m
n+m
I(f) = constant
20 (h)(ma) - -1)
i=1 =1 21 (x,
Σ
Σ
Win(s: ff= 85)²
:=1
j=1
This resembles the objective of Equation and suggests that we should set our function 0j as
(x)) (I.))
where or (x;)² is the variance of hy at point z4. With access to small set of labeled data points. we can estimate aj (a;) through heteroscedastic regression (Wasserman, 2006), which is further discussed in Appendix F.2. We note that this function a; changes over values of æ as it is computed through regression, while the accuracy-based weighting has a constant value for aj-
5 EXPERIMENTS
We connect LPA and the field of weak supervision by using weak labelers as our source of prior information. Formally, a set of weak labelers is given by X (A, As {0, 1, 3) and 0 denotes an abstention. Here, we consider LPA with a single source of prior information h(x)= hx (x) is an aggregation of weak labelers, which we refer to LPA+WL. For this method, we use Snorkel MeTaL (Ratner et al., 2019) as our aggregation scheme. We also consider our extensions of LPA with multiple sources of prior information when set h, A, for each weak labeler. We refer to our extensions of LPA that incorporate weak labelers through dongle nodes as LPAD (A) and LPAD (P), where the last letter denotes techniques to estimate the weighted edges of these dongle nodes (accuracy, and probabilistic approach). For methods that require accuracies, we use accuracies estimated via Snorkel McTaL. We note that LPAD (A) and LPA+WL are both using the Snorkel estimated accuracy, we provide a discussion on their difference in Appendix E. For LPA + WL, set μ 1. Further experimental details for our methods and the baselines are in Appendix G.
where each X; X -
We compare our approaches existing weak supervision methods, standard LPA, and other semi- supervised baselines on 4 binary classification datasets from the WRENCH benchmark (Zhang al., 2021). The features from these text and image datasets are extracted from BERT (Kenton Toutanova, 2019) and ResNet (He et al., 201 6b) respectively. On each dataset, we balance the training data to have equal class proportions. To generate a small set labeled data, we randomly sample 100 points from the training data. The remaining data serves as our unlabeled training data. For all graph-based methods, we construct a graph G with average degree t, which is a hyperparameter of method, and with edges that have value 1. More information about t and other hyperparameters of all approaches are in Appendix G.2. Code to replicate our experiments can found here!.
hhtpp://gituh..om////////////// propagation weak supervision
7

---

Published as a conference paper at ICLR 2023
Method
Youtube
SMS
Basketball
CDR
LPA
82.00 + 1.37
94.32 0.45
78.71 + 2.41
67.41 + 0.82
GCN
84.16 + 0.95
94.32 + 1.02
61.34 + 1.16
65.42 + 1.00
Snorkel + L
87.44 + 0.47
96.24 + 0.32
82.08 + 0.83
68.03 + 0.28
FS +L
87.76 + 0.51
94.84 0.43
70.23 + 1.20
67.70 + 0.29
CLL
88.56 0.80
94.56 0.73
77.02 3.96
68.52 + 0.58
Liger +L
88.72 + 0.58
96.08 + 0.38
80.98 + 1.71
67.33 = 0.18
LPA + WL
88.32 0.50
96.80 0.36
83.13 + 1.43
67.61 + 0.19
LPAD (A)
90.32 + 0.43
96.32 + 0.52
83.06 + 0.74
68.13 + 0.74
LPAD (P)
87.84 + 0.53
96.64 + 0.39
82.01 + 2.96
68.97 + 0.51
Table I: We report accuracy (# s.e.) on a held-out test dataset for training an endmodel on pseudolabeled training data, when averaged over 5 seeds. We highlight the best performing method in red and the second best performing method in blue.
5.1 BASELINES
We compare our methods against various remi-supervised and existing weakly supervised learning approaches. We use ground truth labels instead of pseudolabels on the 100 labeled points methods denoted with (+I.). In all these approaches, we train an inductive endmodel on the pseudolabeled training data, is standard WSL. literature.
Label Propagation (LPA): The standard label propagation baseline (Zhu & Ghahramani, 2002) on graph G. This does not take into account weak labeler information.
Graph Convolutional Network (GCN): We provide results for standard graph convolutional net- work (Kipf Welling, 2017). This method also does not take into account weak labeler information.
Snorkel L: A weakly supervised learning aggregation scheme, Snorkel McTaL (Ratner et al., 2017; 2019), which produces pseudolabels through graphical model.
FlyingSquid L (FS + L): Another weakly supervised method that estimates parameters of graphical model via triplet method (Fu al., 2020).
Constrained Label Learning (CLL): A method that produces an labeling contained within feasible space constrained by the error rates weak labelers (Arachic & Huang, 2021). We use the small set of labeled data generate the error rates of the weak labelers.
Liger + A method that extends weak labelers using the smoothness of pretrained models and develops cluster-level aggregations (Chen et al., 2022). This method uses FS (Fu et al., 2020) base aggregation scheme.
5.2 RESULTS
We provide results for test accuracy of training an endmodel on pseudolabels generated by the baselines and our methods in Table 1. Our results demonstrate that incorporating weak labels into label propagation improves upon the performance of LPA across all datasets (LPA + WL > LPA). In addition, in almost every dataset, using IPA to incorporate smoothness improves upon the prior aggregation of weak labels (L.PA + WL Snorkel + L.). Our methods also outperform other weakly supervised aggregation methods, in most cases. The best performing baseline we compare to is Liger or CLL, which each only marginally outperforms some our methods on one dataset. We note that there is not clear best weighting scheme between (A) and (P), although they outperform most baselines on almost all tasks. In addition, one of our methods is the best performing approach on all datasets.
We also report the accuracy of standard LPA and our methods on the labeled and unlabeled training data in Table 2 (i.e, evaluating pseudolabel accuracies). We measure the accuracy of particular
8

---

Published as a conference paper at ICLR 2023
YouTube
SMS
CDR
Method
Accuracy
Coverage
Accuracy
Coverage
Accuracy
Coverage
Snorkel L
75.96 + 0.13
89.75 + 0.08
70.40 0.34
48.31 0.52
70.64 0.12
92.41 0.11
LPA
55.98 + 0.08
11.97 + 0.16
54.71 +: 0.01
9.42 = 0.03
50.79 1 0.00
1.58 1 0.00
Liger + I.
81.06 + 0.47
99.98 + 0.01
78.62 + 0.23
96.01 + 0.20
50.56 + 0.13
81.79 + 10.72
LPA + WL
76.02 + 0.12
89.81 + 0.08
70.75 + 0.35
49.03 + 0.52
70.64 + 0.12
92.41 + 0.11
LPAD (A)
84.03 = 0.15
89.81 + 0.08
70.80 + 0.26
49.00 0.51
72.87 0.08
91.66 0.49
LPAD (P)
89.52 + 0.13 89.75 + 0.08
70.98 0.27
49.03 0.52 71.91 0.25
92.22 0.11
Table We report accuracy and coverage s.e.) of the various label propagation methods on the full partially labeled training data (i.e, pseudolabel accuracies), when averaged over 5 seeds. We also add Liger + L as looks improve coverage by extending weak labelers. We bold the best performing method (in terms of Accuracy) on each dataset.
approach on abstained datapoints as 50% (i.e, random guessing on binary data) on all abstained points as the method has no information on these points. Results for additional datasets are deferred to Appendix 3; on these datasets, the weak labeler coverage is almost 100% of the data, so coverage roughly the same across our methods and the baselines. We observe that coverage drastically increases when using our weakly supervised prior (Table 2) over the standard I.PA and slightly over that of Snorkel. We also observe that our method improves upon the base aggregation method of Snorkel on almost all datasets, improving both overall accuracy and coverage due to the propagation of information to nearby points. We note that Liger has much higher coverage on YouTube and SMS, although the accuracy on this larger set is much worse (see Table 3 in the Appendix).
DISCUSSION
We provide a novel theoretical perspective on LPA that takes advantage of useful prior information. Our bound differs significantly from existing spectral bounds, and provides insight into how to best incorporate priors into LPA. We note that our analysis is general and works with any initialization h. We also provide a framework to handle multiple sources side information and empirical results for the setting of weak supervision. Further work can incorporate other types of prior information into LPA, such as the recent line of work of learning with past predictions (Mitzenmacher & Vassilvitskii, 2021; Khodak et al., 2022). In addition, our connections of LPA with weakly supervised learning illustrate (both theoretically and empirically) that these methods benefit each other. As a whole, our results support adding smoothness the standard WSL pipeline and can encourage further connections between semi-supervised learning algorithms and WSL. We note a few limitations of our method; our bound depends on several parameters, smoothness sg. prior information accuracy og; in general, we may need to approximate these values through labeled data. It remains an open question of how do this effectively. addition, we assume uniformity assumption that the average error of points with "Out" connections from Nú: is of constant factor of the average error in Mi. Relaxing the bound beyond this assumption is also an open question.
We remark that our approach bridges the gap between classical label propagation and modern deep learning by incorporating information from pretrained models to construct our graph G. Since we construct G' through Euclidean distance, our work uses notions of smoothness in the learnt embeddings, which is also noted in Chen et al. (2022). As we gain access to more powerful pretrained models, approach will also benefit through better graph G. This method also provides natural framework to combine information from large pretrained models (via our graph G) and rules provided by domain experts (through our prior predictions h1,...,uu hg)-

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work was supported part by NSF grants IIS- IIS-1909816, IIS-1955532, IIS-221 1907, CCF- 1910321 and DARPA under cooperative agreement HIRO012202000 and funding from Bosch Center for Artificial Intelligence and the ARCS Foundation.
REFERENCES
Chidubem Arachie and Bert Huang. Stochastic generalized adversarial label learning. arXiv preprint arXiv:1906.0m 000000 2019.
Chidubem Arachie and Bert Huang. Constrained labeling for weakly supervised learning. In Uncertainty in Artificial Intelligence, pp. 236-246. PMLR, 2021.
Chidubem Arachic and Bert Huang. Data consistency for weakly supervised learning. arXiv preprint arXiv:2202.03997, 2022.
Abhijeet Awasthi, Sabyasachi Ghosh, Rasna Goyal, and Sunita Sarawagi. Learning from rules generalizing labeled exemplars. In International Conference on Learning Representations, 2020.
Philip Bachman, Ouais Alsharif, and Doina Precup. Learning with pseudo-ensembles. Advances in neural information processing systems, 27, 2014.
Maria-Florina Balcan, Avrim Blum, and Ke Yang. Co-training and expansion: Towards bridging theory and practice. Advances in neural information processing systems, 17, 2004.
Mikhail Belkin and Partha Niyogi. Semi-supervised learning on riemannian manifolds. Machine Learning, 56:209-239, 2004.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 7 (11), 2006.
Lidong Bing. Sneha Chaudhari, Richard C Wang, and William Cohen. Improving distant supervision for information extraction using label propagation through lists. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 524-529, 2015.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceed- ings of the eleventh annual conference Computational learning theory, pp. 92 100 1998.
Tianle Cai, Ruiqi Gao, Jason Lee, and Qi Lei. theory of label propagation for subpopulation shift. In International Conference on Machine Learning, pp. 1 1170-1182. PMLR, 2021.
Mayee F Chen, Daniel Y Fu, Dyah Adila, Michael Zhang, Frederic Sala. Kayvon Fatahalian, and Christopher Ré. Shoring up the foundations: Fusing model embeddings and weak supervision. arXiv preprint arXiv:2203. 2ot.22223..3..,. 2022.
Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan Hc, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence decoupled graph convolution network and label propagation. In Proceedings of the Web Conference 2021, pp. 3651-3662, 2021.
Yoav Freund and Robert E. Schapire. A theeoeii- generalization of on-line learning and ap- plication to boosting. Journal of Computer and System Sciences, 55(1):119-139, 1997. ISSN 0022- 0000. doi: http://ddii.ong//00.006//.c.... 1504. URL https: www. sciencedirect. com/
Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In International Conference Machine Learning, pp. 3280-3291. PMLR, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp.
1263-1272. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2023
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2, pp. 729-734, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in neural information processing systems, 31, 2018.
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 201 6a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016b.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data (2015). arXiv preprint
2015.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2020.
Masayuki Karasuyama and Hiroshi Mamitsuka. Manifold- similarity adaptation for label propagation. Advances neural information processing systems, 26, 2013.
Jacob Devlin ling-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HIT, pp. 4171- 4186, 2019.
Mikhail Khodak, Maria-Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning pre- dictions for algorithms with predictions. Advances in Neural Information Processing Systems, 2022.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, 2017. URL https:: http:://pppeeeieeeee net forum? id=$SU4ayYg1.
Bin Liu, Zhirong Wu, Han Hu, and Stephen Lin. Deep metric transfer for label propagation with limited annotated data. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pp. 0-0, 2019.
Yanbin Liu, Juho Lee, Minseop Park. Saehoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for few-shot learning. In Interna- tional Conference on Learning Representations, 2018.
Alessio Mazzetto, Cyrus Cousins, Dylan Sam, Stephen H Bach, and Eli Upfal. Adversarial multi class learning under weak supervision with performance guarantees. In International Conference on Machine Learning, pp. 7534-7543. PMLR, 2021a.
Alessio Mazzetto, Dylan Sam, Andrew Park, Eli Upfal, and Stephen H. Bach. Semi-supervised aggregation of dependent weak supervision sources with performance guarantees. In Artificial Intelligence and Statistics (AISTATS), 2021b.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden (ed.), Beyond the worst-case analysis of algorithms, chapter 30. Cambridge University Press, 2021.

---

Published as a conference paper at ICLR 2023
Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. Proceedings of the VLDB Endowment, 11(3):269-22) 222))229922,,20 2017.
Alexander Ratner, Braden Hancock, Jared Dunnmon, Frederic Sala, Shreyash Pandey, and Christopher Ré. Training complex models with multi-task weak supervision. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01) (5(01):476347711 Jul. 2019.
Alexander J Ratner, Christopher M De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. Data programming: Creating large training sets, quickly. Advances in neural information processing systems, 29, 2016.
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep semi-supervised learning. Advances in neural information processing systems, 29, 2016.
Laine Samuli and Aila Timo. Temporal ensembling for semi-supervised learning. In International Conference on Learning Representations, volume 4, pp. 6, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20( 20(1):61-80, 2008.
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 umi--suerrvieed learning with consistency and confidence. Advances in Neural Information Processing Systems, 33:596-608, 2020.
Partha Talukdar and William Cohen. Scaling graph-based semi supervised learning large number of labels using count-min sketch. In Artificial Intelligence and Statistics, pp. PMLR, 2014.
Paul Vernaza and Manmohan Chandraker. Learning random-walk label propagation for weakly- supervised semantic segmentation. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 7158-7166, 2017.
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. IEEE Transactions Knowledge and Data Engineering, 20(1):55-67, 2007.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propaga- tion. ArXiv, abs/2002.06755,, 2020.
Larry Wasserman. All of nonparametric statistics. Springer Science & Business Media, 2006.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. International Conference on Learning Representations, 2020.
Yi Xu, Jiandong Ding, Lu Zhang, and Shuigeng Zhou. DP-SSL: Towards robust semi-supervised learning with a few labeled samples. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview net/ forum? dd=NNLyLLBBi101.1
Yuto Yamaguchi and Kohei Hayashi. When does label propagation fail? view from network gen- erative model. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 3224 3230. 2017.
Yuto Yamaguchi, Christos Faloutsos, and Hiroyuki Kitagawa. Camlp: Confidence-awee aware modulated label propagation. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 513-521. SIAM, 2016.
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang. Mao Yang, and Alexander Ratner. WRENCH: A comprehensive benchmark for weak supervision. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
12

---

Published as a conference paper at ICLR 2023
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.
Kuang Zhou, Arnaud Martin, Quan Pan, and Zhunga Liu. Selp: Semi-supervised evidential label propagation algorithm for graph data clustering. International Journal Approximate Reasoning, 92:139-154, 2018.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. Tech. Rep., Technical Report SMU-CALD-02-107, Carnegie Mellon University, 2002.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference Machine learning, pp. 912-919, 2003.
13

---

Published as a conference paper at ICLR 2023
A CLOSED FORM SOLUTION OF LPA
We provide closed form solution of the following optimization problem.
min fER
Way(Fi fz)² + wllff h112) s.t. f. = for i S n.
Here abuse notation h vector (h( ...., ( )) and h; h((x)). For simplicity we refer i L as 1 <is n and i E U as n
+ < S + m. First, note that
Wiy(fs - fz)²= 2 JEL
Wiy(Fi f,)
Σ
Σ
wir(fi - fz)²
2
RET
ΣΣ iU
Wis(Si -)))²
The first term a constant as === ys for E Denote fr. E IRth is column vector with entry fi for i L and fy E Ih is column vector with entry fj for j E U. We sometimes refer Wij to Waj- For the second term we have
ΣΣ JEU
Wiy(Se 1,)²
ΣΣ JEL
win
- + +5)
Σ iEL jEU
w
Σ JEU
wig -2 -
Σ fawiff
İEL
iEL JEU
E DuLfo
21, W Lu
constant
where DUL E Rmxm is diagonal matrix with (DUL)ss EiEl wri++n and WLU Rnxm is matrix with entry (WLu)ij Wiitnn For the third term, have
wiylFi - -,) - ΣΣ
(f. - 2fifs f3)
2
2
iEU JEU
IEU JEU
Σ wiy) - -E NE JEU
fowiffs
iEU JEU
f Duvfu Woufe
where Dou Rmxm is a diagonal matrix with (Deu)jj = Eiev Wijtn and Woo Rmxm is matrix with entry (Wou)is = Witnjtn- Therefore, the overall objective is given by
min constant + (DuL + Doo - Wou)fr - 2 WLUfe + ~ h12 fo
Differentiating with respect to fy and setting equal to 0, we have
2(DuL DUu Woo You 2W 2p(Fu ho) = fu (DUL + Doc Woo +uaa) (nhe (
when by E R with (he)) = hytn. We can also extend this to the case when f Rm where we have a different value of μ4 for each i. The optimization objective is given by
Σ wig(S 12)2 Eucls hw))) s.t. Ss Di for S
min fERnomm
We can write the regularization term for U as
Σm(h h2) (fu 1a--hor TD - hv)
IEU
when D2 E m is a diagonal matrix with entry (Du)gs = Hjtn- We can write the optimization
objective as
min constant + (D(DDL + DUu Woe - WL. + (fu - DD,(ff - hy)- fm
Differentiating with respect to fo and setting equal to 0, we have
2(Dur. + Duu Wr 2W + (f, hv) =
fr (DUL. + Deo + D, Wor) ( WLufL.
14

---

Published as a conference paper at ICLR 2023
B THEORETICAL RESULTS
First, we analyze the closed form solution the LPA in Lemma 1.
Lemma 1. Let I be the optimal solution of the optimization problem of Equation I then for 72 + Si Sisi n m,
E, Wijff + ph:
f7 Eg Wij + 1
Proof. For each i S n, we must have f = to satisfy the hard constraints. For each n - isis + m, we differentiate the objective with respect ft and equal to O, resulting
Σ wry(ft f)) + pls h₂)
Rearranging this and setting fg fj. have the lemma.
Next, will analyze the error Js: Vel. which is the difference between the optimal solution and the true label. Note that If: - yal < 0.5 implies that we have a correct soft label fi
Lemma 2. Let f be the optimal solution of the optimization problem of Equation Then, for + 1 S i m. have
1 - Val Egwislf - Usl + Ej Way 18/5 Vil + p//2;- V/
Eg Wij +
Proof. From lemma 1,
Σ WEsJÿ + 11l
Ift
Mel
Ej Wiy + 4t
Ej Wii Wij(sī - -y:) + p(hss - yi)
Ej Wsg + 4
Σ, Wii - -y5) + Eg wir(Us - yi) + +u(1ie - yi
E3 Wii +
E, Weyls - -Usl 1 + E, whil 1ys - yil + pa/hs - 3/l
Σ, wij + 1
Lemma 2 says that we can bound the error of point i, l yi by the error of its neighbors |5ž Mj and terms corresponding
the smoothness of the true labels and the prior information accuracy. Because we know that the error on labeled points are zero, this lemma motivates us to bound the error term of the distance our points from the labeled points.
Next, in addition to the average error defined in Definition 5, we define the In-error, Between-error and Out-error for each Ng--
Definition 6. For graph G with adjacency matrix W = (w)sg, set of k--hop neighbors Ng. and a prediction f g=++m, we define the In-error, Between-error and Out-error of No. as
Erra(f.y,k) LieNisEN, w yel
(in(k)
ErrbelJ.yy, EiENusEN, Wirlfs Mil (ker EieNu WiylJe vil Comu
Erroua (FromnS. (f.y,
For simplicity, we will write (k), (ke(k) EEmu(k) for Err .f. Errou( y, respectively.
Errhai "f k).
15

---

Published as a conference paper at ICLR 2023
We will use Lemma 2, to derive relationship between errors in N₂ and its neighbors. We make of the fact that the Out-flow M the same as the In-flow No+1-
Lemma 3. For 0 E k -
Cou (k) = Cin(k +)
Lemma 4. (Error difference inequality For S k S 1, we have
(I)(k)( Eou 1))
Σ
M Vil S (E) + Eou(k)) + sn + 14/Va lan
VENL
where 85 is the smoothness of true labels and og is the prior information error over No.
Proof. From lemma have
Σ wisls Vil + plftt - Vil $ Σ wiylff - -y5l + Σ wislys - Val + 11/s Vel.
We take summation over i E NE.
Σ Σ iENz
waylst vsl + wls7 vil
Whyl [J yj Σ wiyly; Del + plhs yil)-
KEV
From the definition of the In-error, Between-error, Out-error, smoothness 8g. and weak label error ak, we have
LHS
(k)( Cba
+ Coul ( (k)) ( (k)
Σ u V/l
iEN
RHS = Coul (k: Euu (k - 1) + Cbe ( (k:) + Cm + 1m + 1) + 8h + MNVilax
From lemma 3, we know that
(k) = Cm 1),
(4)
so we can rearrange the inequality as
Cin (Bin Eoun (A: 1)) + Σ
uIST Vil S Cour(k) 1) Eour (k:) + 84 + pNNaloss
SEAL
Lemma 5. (Error difference inequality ks = 1)
(I) Eaur(1 1)) + Σ
Mlfi - vil $ M|Nios
iEN1
Proof.
Similar to lemma 4, we have
Σ wills - yil wIft yel
Wigl
V3 + Σ Wiylys
Del + m/h; - vsl)
KEM
SEMi
Because, Mi is the last neighborhood, there is no edge out from Mf and
LHS (I) Ener())
Σ ulft - wil
iEN
RHS Cout(l - 1) 1) + Chei Erer + 51 u|Nilan
and rearrange
Cin (I) - Eour - 1)) + Σ uIst - Dil S 8: + m\Nila4-
iENi
L
We can see that this inequality contains different notions of error. We now define the proportion between In-error and Out-error.
16

---

Published as a conference paper at ICLR 2023
Definition 7. Let aks by be the proportion of the In-error and Out-error with the average error,
(in(k)
Ein Em(())
bk
Ek
Ex
when
EiENs 15; Vsl
Ex
Will
Assumption 1. (Uniformity of error) We assume that the In-error and Out-error are roughly the same the average error in each neighborhood.
4x = 0(1,,br = O(), by
0(1)
For example, any graph G that has points in neighborhood N with the same number of edges that go into and out from that point, has the property that aę = by 1. In particular, assume that we have 2 points in Ns. the first point has edges from N and edges to N while the second point has 2 edges from N and edge to Na-1, this graph still has dg by 1. In general, we expect the proportion bu to be close to 1. Next, we will substitute ax, by in Lemma 4. de
Corollary 1. For 15
L, we have
(ayEx bk-1Ex-1) S Cm((k) + W|/W (ak+1ER+1 bxEx) + 8k + p|N Cmn(k) + u|Ni
(k) (k)
Proof. From lemma 4
(())((() Four 1)) + Σ
Mlst yel (B) + 1) Eou(( + 8h + 14//a lo
iENz
We let (k) Eg and Evur (k) Ey and ΣieNs 18/ Vil =\NaBBR.
(a be- 1k-1 + W EE S Com (k) bbFa)) + 88 + 14//V lou byEa) Sk plNVala
(a) bk-1Bk-1) (Ex Bg-1) Cou(
we know that EX-1 O. Then, simplifying yields that
(Cin(k) (a by 1 S Cout (A) byEx,) 33 MlNala (agEa - be- BR-1) S
Cour
+ M|Nalax
(ks) N4/N (0R+1EE41 bx + (1:) M
Corollary 2.
We have
MLNilar (a. b 1( S Cin MNTl
The corollary implies that the difference between the error between neighborhood can't 't be too large. We introduce the next two lemma to help deriving the bound.
Lemma 6. For di, d2...., di that satisfies the following inequalities,
dy S 7k + Cs
for S ks 51 and
S c.
We have
dy - Σ
t=
j=k
17

---

Published as a conference paper at ICLR 2023
Proof. The main idea is that we use the upper bound on di, di d......... .... dk+1 to find the upper bound of dg. First, we start with dj-1
di-1 S n-10h + -a-1
S 7--10 C--1
Next, we continue with d1-2,
d1-2 S 7-201-1 + C--2
S 57-2(71-19 + q-1) + Q-2-
= -97-171-2 + 9-17 + Q-2
and so on. With this idea, we can show by induction that
dx
j=k
We sum these inequalities up to have the lemma.
Lemma 7. For æ1, .2,..., that satisfies the following inequalities,
a bk-1Ik-1 dj
for 1 S k S I, when ag, bu, du positive constant. We have
1
8g J.ro
aj
a
j=1
when
bj
6, aj
Proof. We divide both side of the inequality by ax, for each 1 S k S I, we have
b dy
Ik
rk-1
ak
We recursively apply this inequality,
by
by
di
dk
Ik
2k-2
ag
Q
0k-1
0k
bk-1
1
be-200
x
dk- + dx)
-
(Ōx
bb
2 2 11-1d1-11 + dl.
Uk-3 26
+ dx-2) + - + d4)
<
(6k-
2b
Ok
ak
(ōx
1p-2bb- 30
02-10 - + dR)
dk
h-1
A 1
a1
d
8,))
8 rro
aj
Now, ready derive the error bound of I.PA.
18

---

Published as a conference paper at ICLR 2023
Theorem 3. Let f be the optimal solution of the optimization problem of Equation the envor of f in each neighborhood is given by
1
Es
5
6,))
0
j=
when
bj
65
dx =
G 79)
Dj
t=
j=k
and
Sk + Na
Cour
(in(k) + NN\a''
7k
Cm((k) + 1
Under assumption I, we have
k de)
Eg S 0
i=1
Proof. From corollary 1, 2 we have
Cour (k)
8k + 1 (k)) + 11 Wi
(agEx bk-1Bx-1) S
(ak+ Ex411 bx
(kn(k) + u|Na
and
81 + N|Nilan
(apB2 - - S
(In MNNi
Let
Sk + pLN2
Co 7 (kn( + 14/Na]
dy = axExx - -
Ck
(k) + /1 WNal
By lemma 6, we have
EgEa b dx $ Σ
ca II
j
By lemma 7, we have
k
k- 1
k-
Eg S
dp
Q1
8, Fo
1=1
1=1
(,))
1=1
when
bj
6,
aj
The last equality is true because the error Eg = 0. With the assumption 1, by
O(1, we have
as
k
Eg A 0
de)
1=1
19

---

Published as a conference paper at ICLR 2023
C SPECTRAL BOUND
The following is the original version of the spectral generalization bound found in Belkin & Niyogi (2004), where they assume that we can have repeated labeled points (at most u times).
Theorem 4. (Generalization performance of graph regularization) Let f be the optimal solution of Equation 2, n. 2 4 be the number of randomly sampled labeled points from some distribution where each vertex occurs no more than u times, together with values y1..... Yn- [ysl S M. Let X1 be the second smallest eigenvalue of the Laplacian matrix of G. Assuming that Vx [f(x)) S K, we have with probability
(conditional on the multiplicity being no greater than 1),
2 21og(2/8)
R. R(f) S B
(n3 + (K+
+ M)3)
n
where
3n un
4m
8
(A1
nu)²
A1 mju
We can set M, 1,K = 1 to achieve the simplified version (Theorem 2).
D DONGLE NODES
We can change label propagation problem with multiple initial predictions into standard label propagation by augmenting a graph with dongle nodes (Zhu et al., 2003). Without loss of generality,
we assume that each initial prediction has 3 possible outputs h; X + {6, O, 1} for j I...., However, this method also works for a general case when h X + [0, 1j. We augment the original graph G with the following nodes and edges,
1. For each weak labeler h,. we add 2 nodes to the graph G with vertices Un+m+j tn+m+ This represents a prediction of class 0 or from the weak labeler j.
2. For each x; that (x:)) 0, draw weighted edge between u, (the corresponding vertex of æ;)) and Un+m+j with weight (x;))
3. For each z; that (x:)) 1, we draw a weighted edge between ü; (the corresponding vertex of v;) and Ux4m4444j with weight (x.).
4. For each x; that (x:))) 0. do not draw any edge.
Let G' be the new graph with a weighted adjacency matrix (nr(y) then solving the objective of Equation 3 is equivalent to solving
R++m+22 n m-2k
min fm
Σ
(f(-f)))
(5)
such that
1. f, = y; for S n.
2. f, = for n + m +
3. f, = for n + m + + < n
m m
2k.
We see initial predictions as dongle nodes and encode the parameter ay (x;)) as weight of an edge connecting the corresponding dongle node of predictor j to the node of r;. With direct calculation, we can see that the objective of Equation the same as the original objective.
nto mmm
ntm &
Σ
Σ w
Σ
M (f+ -- hy(x)))aa((z))
such that /a ys for i < n. With this procedure, we add 2k nodes and at most (n m)k edges G.
20

---

Published as a conference paper at ICLR 2023
E CONNECTION BETWEEN LPA WITH MULTIPLE AND SINGLE INITIAL PREDICTIONS
We analyze the closed form solution the optimization objective Equation 3. By differentiating with respect to ft. we know that the optimal solution f; satisfies the following
a+ 2wig 17) Σ 2 - (1)
mutm j=l Wijfj + ش az (z(2))/ mu Wij + Σ5 أ-ر (z:)
From Lemma I, recall that the optimal solution of LPA with initial prediction (objective of Equation 1) is given by
f7 Eg WijJÿ ph(zz)
En wij a
We can see that if we set
h(xa) Σe=1 (y(2))/((zz) Σ5= 03 (I;)
k (t))))
u(x;))
the solution LPA with multiple initial predictions is equivalent LPA with the initial prediction which could be seen weighted average prediction. The objective is given by
min
wi f,)²
Σ p(z:((fi - h(x.))²) s.t. f: y/ for i S
SEB
note that now parameter y is now depends on each instance 24. When we have
[a((z)= =
==1
a constant for all T; then will have the same setting in the objective of Equation However, our analysis still works in this case when ((xx) is not constant.
E. DIFFERENCE BETWEEN LPA+ WL AND LPAD(A)
We note that LPAD (A) uses Snorkel to estimated accuracies aj. From above, LPAD (A) is equivalent to LPA with initial prediction
25h E
Max))
p(x;) Σ oj.
We observe that h is exactly the prior information for LPA+WL. However, the key difference is that for LPA WL. we have a fixed μ for all data points, while in LPAD(A), the value u(x:)) depends on J; To illustrate this, we consider 2 scenarios. First, we assume that we have 3 weak labelers h1 h2, and hs. all with estimated accuracy 0.8. We consider a point # with h (x1) = I, h2(21) 1, hz(21)) = and with hi (x2) 1, (x(2) = 0, (z())) 0, where 0 is abstention. We can observe that
1. h(x1)= = h((22) = 1 2. u(x1) = 2.4, u(x2) = 0.8
Here in LPA WL, I1. T2 have the same prior information and regularization parameter μ. In LPAD(A), we put much more weight the regularization parameter μ(x1) than ((z2). This is intuitive as we should more confident about our prior information when a higher number weak labelers agree.
21

---

Published as a conference paper at ICLR 2023
F METHODS FOR SELECTING ALPHA
F.1 BOOSTING APPROACH
From boosting literature (Freund & Schapire, 1997), given many weak learners h2 - {0, for j = 1,2,.... k, an optimal way to combine these weak learner (corresponding to an exponential loss upper bound) weighted average
Ej- E)=
Ph (z)
h
(
Instead of accuracy, we could set a; in this fashion suggested by the boosting literature. We show that this value of oy minimizes the upper bound on the error [ - yEl. Recall that the optimal solution of Equation 3 satisfies
Entm Wiiff + Σj- a (z,)),((zz)) E/tm Waj + a5=10
We can bound the error of point i, 15+ Vil by the error of its neighbor |fz M55- Observe that n+ winSi + Σド= (2(())))))())
Vi 2j=1
y1
Σj= Wij + Σ و== 0ry (2:4)
En Wij (f} yj + V) V1) + E/=1 (x v1)
ft V1
~nt Wij + Σ ag(x;))
Σj wiylfj Vr Eラ=1" w/y 1y/ V/ E (zx)) v1)l
1sr vol <
2j=1 wi + a
matm
The first term represents errors of neighbor points |fj y5 and the second term represents the smoothness of the true labels on the graph G and the third term represents the accuracy of the weighted prediction. We can improve the upper bound by selecting appropriate value of az (x;) and wij to minimize
((() v.)
( v.))
Σ/ a5
Dj=1 Wij + Σラ= (x;)
Consider the following lemma,
Lemma 8. Given k classifier h; X + (-1,1) for i .... Let h(x) = achi(x) be the weighted average among the classifiers. Assume that the prediction of hy(x) are independent between different i. The optimal a,, that minimize the risk when the loss is exponential loss of h(x),,
C(,, x. v) = expl-yh(x))
given by
0 2 In ((),(x)) = v) 1(),() = v)
Proof. The risk given by
EE(Ch,, 8)) (((exp(-yh(z)))
= E(exp(- (a))(=)))
k
Blexp(-vashx(=)))
ps exp(pxoc + (1 ps) exp(as)
22

---

Published as a conference paper at ICLR 2023
when P. = (x) y). It is sufficient to choose a; that maximize
p4 exp(=oss + - pb) exp(as).
Differentiate with respect to (; and set to zero, we have
Ps ax;( + (1 pı) exp(a;; = (1-p;) exp(a;) = exp( -a;)
pi
cap((2x:)
1 - pi
1
Pi
a, In
p
Note that exponential loss is an upper bound of our hinge loss and Lemma 8 suggests that minimize the exponential loss upper bound, we should set
Pi
In
F.2
HETEROSCEDASTIC REGRESSION
Recall that we model
h ~ (Ny(o00(((3)
so that we can write
(z,),) = y(x;) + to (z())
when -N 1). We want regress 0 (x)) Rearraging have,
hy(x)) - y(z;) = az(z;)e
(hy(2;) v(x;)) o²(
log (og((h)(2z) y(x)))²)
loog(o, + log(=")
On labeled data, we can regress function gj (2x) to match log (1) - y(Ix))3) then we set
ay(z;) (x:))
G ADDITIONAL EXPERIMENTAL DETAILS
We use the default splits from the WRENCH benchmark (Zhang et al., 2021) for each of our binary classification dataset. This benchmark has Apache-2.0 license. For each text classification dataset (Youtube, SMS, CDR), we use pretrained BERT embeddings (Kenton & Toutanova, 2019). For our image classification tasks (Basketball), each task, we balance the datasets and randomly sample 100 labeled datapoints. We balance the datasets to make sure that the overall sample of labeled data contains roughly the same amount of points from each class.
pretrained ResNet embeddings (He et al., 2016a). For
We cluster compute resources to produce our empirical results. We use single GPU (NVIDIA GeForce RTX 2080Ti) to run our methods and each of the baselines.
G.1 WEAK LABEL SOURCES
We use the standard weak labels contained within the WRENCH benchmark (Zhang et al., 202 I). These are standard in programmatic weak supervision literature and primarily consist of simple land-engineered rules. For example, on the YouTube dataset (or a spam classification task), examples of weak labels are functions that check for the presence of words in sentence (Figure 4). We defer interested readers to the benchmark (Zhang et al., 2021) and other papers in weak supervision (Ratner al., 2017) for more details.
23

---

Published as a conference paper at ICLR 2023
from enorkel.labeling import labeling_funce functinnooooionnn
Elabeling function()
def ch)ck(x):
return "check" x.text, ..teex.ooeer(
slabeling Functioo()
def check_oute outok_outtee (x) retura "check out" in text. lower else ABSTII
Figure 4: Examples of weak labels on the YouTube dataset
G.2 HYPERPARAMETER OPTIMIZATION
We perform hyperparameter optimization of all methods, selecting the best of parameters on the validation set. We optimize over the following parameters for all methods' endmodels:
learning rate: [0.01, 0.001, 0.0001]
number of epochs: [20, 30, 40, 50]
weight decay: [O, 0.01, 0.001]
In each experiment, we have a fixed batch size of 100 and a fixed architecture of 2 layer neural network with hidden dimension of 64 and ReLU activation function. For all graph-based methods, we have an additional parameter
[1, 2,5, 10, 100]. controls the average degree of nodes in the value N and
G. Let N be the number of nodes in G, our euclidean distance threshold graph. In essence, we add an edge between two points when the Euclidean distance between them less than the & percentile of all N2 pairwise distances. The motivation for this is that N node corresponds N2 edges, so adding f edges leads resulting graph with average degree f.
threshold percentile for
For GCN baseline, construct graph G in the same manner all other LPA-based methods. The GCN architecture is 2 layer neural network with hidden dimension of 16 and ReLU activations. Consequently, we train an endmodel on the pseudolabeled data, which is the same architecture as all other methods. For our Liger + L baseline, we optimizer over fixed threshold value for their cosine similarity as some & for each weak labeler. We note that this baseline is highly sensitive the value of k; for BERT embeddings, we select values of & E [0.995, 0.9975, 1] points are much less distinguished the embedding space comparison the larger foundation models (GPT-3, CLIP) in the original paper (Chen et al., 2022). We use 2 clusters for all tasks.
H COMPLETE VERSION OF TABLES
We present our results for both training/pseudolaeell performance (Table 3) and test/endmodel performance (Table 4) in more detail and with additional comparisons.
In our pseudolabel performance table, we provide the Non-Abstain accuracy (i.e, only considering accuracy on points on which the model makes a vote). We define abstaining as having a maximum logit (across either class) that within e 0.001 of 0.5. We observe a fundamental tradeoff: balancing high accuracy and little coverage against lower accuracy and higher coverage. We also observe that LPA performs well locally on regions connected labeled points with non-abstain accuracy close to 100 percents, but has low overall coverage.
For our endmodel results, we additionally compare against fully supervised approach that uses all of the training data and their labels. We remark that some datasets in the WRENCH benchmark have noisy labels, leading to imperfect fully supervised performance. For example, we also add evaluations on the Tennis dataset, which only achieves 88% fully supervised performance, and all methods seem to match this performance. We also add some additional variations of our dongle- based approach. We add comparison to a boosting (Appendix F.1) to determine a, which we refer to LPAD (B). We also compare against a method that uses the unosberved ground truth accuracies for a (LPAD (O)) and another method that sets 1, Ya (LPAD (1)). We note that LPAD (O) is unfair comparison
24

---

Published as a conference paper at ICLR 2023
YouTube
SMS
CDR
Method
Ace
Cov
NA Ace
Acc
Cov
NA Ace
Aec
Cov
NA Ace
Snorkal +
15.96 - 0.13
89.75
0.08
78,93 + 0.14
70.40 + 0.34
48.31
0.52
92.20 1000-00 0.29
70.64 0.12
92.41 + 0.11
72.33 + 0.15
LPA
55.98
= 0.08
11.97
0.16
100.00 a 0.00
54.71 4: 0.01
9.42
4: 0.03
100.00 = 0.00
50.79 0.00
1,58 = 0.00
100.00 4: 0.00
Liger L
81.06
= 0.47
99.88
0.01
81.07 4 0:47
78.62 1: 0.23
96.01
0.20
79.81
= 0.18
50.56 0.13
81.79
10.72
50.98 0.46
IPA WL
0.12
89.81
78,97
70.75 0.35
49.03
0.52
92.32
70.64
92.41 + 0.11
72.33 0.15
(A)
0.15
49.00
92.45
74,95
94.03
19.03
71.91
92.22
73.75
LPAD
0.14
48.93
70:40
91.64-1
72.27
LPAD (O)
89.36 = 0.08
89.81
0.08
93.8
0.10
71,52
0.30
49.00
93.91
0.19
73.91
0.07
92.23 + 0.09
75,93 0.09
LPAD (1)
83.11 0.07
76.97 0.11
93.03 0.07
70.88 0.26
48.61 0.51
92.93 0.09
71.39
75.00 0.11
78.52 0.09
Basketball
Tennis
Method
Ace
Cov
NA Acc
Ace
Cov
NA Ace
Snoekel
69.09 1::9::000 0.02
100.00 =
69.09 0.02
86.10 0.06
100.00 0.0
86 0.06
0.02
+ 0.05
97.12
70.60
Liger
100.00
74.09
86,91
0.15
(A)
69.75 0.33
99.95 0.03
69.76 0.33
87.15
99.94 0.03
87.17 0.06
LPAD (P)
52.46 0.19
90.42
0.32
85.89
0.19
87.69
99.98 0.01
87.70 0.12
LPAD (B)
74,26 1: 0.30
99.95 1: 0.02
74,28
0.30
87,20 0,08
99.97 1 0.01
87.21 :: 0.08
LPAD (O)
74,02 0.33
99.99 1: 0.01
74,03 0.33
87.23
0.09
100.00 1 0.00
87.23 1: 0.09
(I)
75.87 0.20
69.97 + 0.23
86.97 0.24
87,46 + 0.17
99.38 0.04
87,70 0.17
Table 3: We report accuracy, coverage, and non-abstaining accuracy (NA Acc) of the baselines and variants of LPA on the training data (i.e, pseudolabel statistics), when averaged over 5 seeds.
Method
Youtube
SMS
Basketball
CDR
Tennis
Snorkel L
87.44 1: 0.47
96.24 1 0.32
82.08 0.83
68.03 0.28
88.51 + 0.04
FS L
87.76 : 0.51
94.84 = 0.43
70.23 + 1.20
67.70 = 0.29
88.56 = 0.02
CL..
88.56 0.80
94.56 + 0.73
77.02 3.96
68.52 0.58
88.78 0.13
LPA
82.00 =:: 1.37
94.32 +: 0.45
78.71 2,41
67.41 = 0.82
83.35 +:2 3,30
GCN
84.16 + 0.95
94.32 + 1.02
61.34 1.16
65.42 + 1.00
88.63 + 0.14
Liger
88.72 0.58
96.08 1:: 0.38
80.98 1.71
67.33 0.18
86.43 1 0.87
LPA WL
88.32 # 0.50
96.80 + 0.36
83.13 1.43
67.61 0.19
88.51 + 0.04
LPAD (A)
90.32 + 0.43
96.32 + 0.52
83.06 0.74
68.13 = 0.74
88.56 + 0.02
LPAD (P)
87.84 1: 0.53
96.64 -: 0.39
82.01 2.96
68.91 0.51
88.60 1 0.04
LPAD (B)
88.64 = 0.37
96.56 + 0.33
76.58 + 2.20
67.0 0.43
88.56 = 0.02
LPAD (0)
90.16 1: 0.50
96.40 - 0.50
81.10 4: 1.43
69.06 1: 0.59
88.58 + 0.02
LPAD (1)
83.20 1.15
94.32 1 0.35
78.61 1.95
67.76 0.21
88.43 0.16
Fully Supervised
89,92 + 1.45
98.04 + 0.38
86.04 + 2.02
73.71 + 0.85
88.43 + 1.06
Table 4: We report accuracy test data for training an endmodel on pseudolabeled training data, when averaged over seeds. We bold baselines when they outperform both of our methods. We bold methods when they outperform all baselines.
all other methods as it accesses ground truth accuracies that other methods do not use; we add this comparison to describe the best potential performance of LPAD.
I HYPERPARAMETER ABLATION
We provide an ablation study on hyperparameter t. We report accuracy on the test data of an endmodel that is trained on pseudolabels from baselines and our methods with particular values of t to determine the construction of G. We observe that all graph-based methods are sensitive to the choice of t, which controls the sparsity of edges in the (Euclidean) graph G. We remark that this finding is intuitive most graph-based semi-supervised algorithms leverage properties of this graph achieve better
25

---

Published as a conference paper at ICLR 2023
performance. We common trend among all methods where when is large, the end-model accuracy tends to decrease. We note that Snorkel + does not leverage any graph information, but still add it here for comparison.
YouTube
Method
t ==
t =
5
t 10
100
Snorkel L
87.04 + 0.47
85,44 + 0.9
86.4 0.78
86.4 + 0.78
87.04 + 0.47
LPA
79.76 1.99
81.6 + 1.15
82.0 + 1.37
82.64 + 1.62
75.68 + 1.51
LPA WL
86.24 + 0.75
86.56 + 0.81
86.16 + 0.71
88.32 + 0.5
83.12 + 1.2
LPAD (A)
89.12 0.5
88.96 + 1.04
89.04 + 0.68
90.32 0.43
84.0 + 0.54
LPAD (B)
8
86.24 + 1.22
87.12 = 0.69
88.64 - 0.37
83.84 + 0.27
LPAD (P)
87.76 + 0.79
0.79
87.84 + 0.53
89.2 0.31 89.92 + 0.53
82.8 + 1.03
Table 5: We report accuracy test data for training an endmodel pseudolabeled training data from various label propagation methods when using different hyperparameter and averaged over seeds.
SMS
Method
t
t = 2
5
t= 10
100
Snorkel + L
95.04 + 0.46
96.08 + 0.48
96.24 + 0.32
96.24 + 0.32
95.04 + 0.46
LPA
94.32 0.45
94.52 + 0.26
95.24 0.38
92.2 + 1.08
80.76 + 3.51
LPA WL
94.88 + 0.67
96.44 + 0.26
96.8 0.36
95.36 0.6
85.12 +
LPAD (A)
95.6 = 0.28
96.8 + 0.33
96.32 + 0.52
95.96 0.41
86.12
LPAD (B)
96.04 = 0.19
96.68 = 0.32
96.56 + 0.33
1.112
82.64 + 4.36
LPAD (P)
95.8 = 0.46 95.64 + 0.36 96.64 = 0.39 96.16 - 0.48
84.32 + 2.82
Table 6: We report accuracy on test data for training an endmodel on pseudolabeled training data from various label propagation methods when using different hyperparameter and averaged over seeds.
CDR
Method
t ==
t= 2
5
t= 10
100
Snorkel L
67.87 + 0.25
68.03 + 0.28
68.24 +: 0.72
68.24
0.72
67.87 + 0.25
LPA
67.01 + 0.82
65.17 + 1.09
63.19 + 1.18
59.33 + 1.8
44.39 + 2.69
LPA WL
67.87 + 0.25
67.61 + 0.19
67.16 + 0.84
65.8 + 0.82
49.66 + 1.8
LPAD (A)
68.13 0.74
67.68 1.1
68.65
0.53
67.56
0.38
61.28 + 3.21
LPAD (B)
66.44 1.23
67.01 + 0.43
65.98 + 0.92
66.26 1.15
54.06 + 2.78
LPAD (P)
68.97 + 0.51
67.27 + 1.05 65.48
0.36 64.93 1.8
58.34 + 3.71
Table We report accuracy on test data for training an endmodel on pseudolabeled training data from various label propagation methods when using different hyperparameter and averaged over seeds.
26

---

Published as a conference paper at ICLR 2023
Basketball
Method
t
t t= 2
5
t ==
100
Snorkel + L
81.62 + 1.07
83.62 + 0.8
82.08 + 0.83
82.08 + 0.83
81.62 + 1.07
LPA
75.56 + 0.55
79.36 + 1.49
75.12
1.26
78.71
2.41
66.02 + 1.19
LPA WL
83.13 1.43
80.87 + 0.64
79.95
1.56
80.11 1.75
73.45 + 1.09
LPAD (A)
80.44 + 0.83
78.9 + 1.53
81.64 + 1.35
83.06 + 0.75
74.83 + 1.49
LPAD (B)
75.81 + 3.47
72.75 + 2.11
76.58 + 2.2
78.0 + 4.34
69.36 + 1.03
LPAD (P)
82.01 2.96
74.6 + 2.05
73.31 + 5.25
68.71 + 4.41 67.18 = 3.64
Table 8: We report accuracy on test data for training an endmodel on pseudolabeled training data from various label propagation methods when using different hyperparameter and averaged over seeds.
27


Reviews:
[{"review_id": "tWXvEOadAO", "reviewer": "Reviewer_Rb84", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "They propose a novel analysis of the classical label propagation algorithm with an error bound. They also propose a framework to incorporate multiple sources of noisy information.", "summary_of_the_review": "In a word, the idea of the proposed model is useful to obtain a better performance, and the related theoretical support is sufficient. However, several detail issues are not clear in the proposed model, and some mistakes should be avoided.", "strength_and_weaknesses": "This paper provides some interesting results, but there are some questions needed to be answered.\n1.\tDefinition 1 is confused in this paper, the subset S?\n2.\tWhat is the relationship between Theorem 1 and Theorem 2? \n3.\tIn Theorem 2, you should give more details to introduce the generalization performance of the proposed method. \n4.\tIn your experimental settings, the setting of 𝜆 should be more clear. \n5.\tSeveral mistakes need to be corrected. For example, \na.\t“Proof. (Sketch) The key idea of our proof is to upper bound each E_i for ...”, and there is an error in mathematical notation in this sentence. \nb.\t“We note that this function…” This sentence also includes errors.\nTherefore, I suggest that you should check your paper carefully to avoid similar mistakes. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NspwOwQS6e", "reviewer": "Reviewer_s6EM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides a \"fine-grained\" theory for the label propagation algorithm (LPA) in the presence of prior information. Unlike the existing theory, the new error bound takes into account the local geometric properties of the graph. The new error bound enables us to discriminate two geometrically different graphs with the same number of labeled nodes, while the existing bound cannot discriminate them. In addition to the new error bound, the existing framework for the LPA is extended to the setting where multiple sources of prior information are available. Finally, the superior performance of the proposed LPA with weak supervision was shown through numerical experiments.", "summary_of_the_review": "This paper introduced the novel error bound for the label propagation algorithm. The difference between the existing and new bounds is clearly explained. The experimental results showed the empirical superiority of the new framework for LPA. The reproducibility seems high.\n", "strength_and_weaknesses": "##### Strengths\n- The error bound that takes into account the geometric properties of the graph is novel.\n- The proposed LPA with weak supervision allows us to use prior information from multiple sources.\n- The effectiveness of the proposed method was demonstrated on various datasets.\n\n##### Weaknesses\n- The error bound depends on several parameters which need to be approximated in practice, as discussed in Section 6.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FP7LxeE2SHk", "reviewer": "Reviewer_H2Ah", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The topic of the paper is label propagation with an additional weak supervision that provides noisy predictions for all unlabeled points. The main contributions are two-folded: 1) providing a novel theoretical error bound of label propagation, and 2) proposing a multiple source extension. For 1), the analysis provides more detailed insight about the test error bound, compared with existing studies, and 2) proposes combining a set of different weak supervisions by adaptively weighting them based on their estimated accuracy. Performance superiority is empirically shown on four benchmark datasets.", "summary_of_the_review": "For me, the paper is on the borderline, but I currently lean toward rejection. The theoretical analysis is interesting as written in 'strength', but it is only for the single supervision setting. On the other hand, the main methodological proposal of this paper is for the multiple information source setting. Nevertheless, the empirical results do not show clear performance superiority of the multiple source extension.", "strength_and_weaknesses": "Strength:\n- As the authors claim, the theoretical analysis provides a novel insight for label propagation. Differences from conventional analysis (Belkin & Niyoki 2004) described in Sec3.2 are interesting (e.g., conventional analysis does not reflect label positions in the graph). Overall, I think this analysis is valuable.\n- The paper is easy to follow, and the proposed method is easy to implement. Relations with wide range of existing studies are discussed.\n- Empirical evaluation shows good performance, compared with other recent weakly supervised models for the same setting.\n\nWeaknesses:\n- Theoretical justification of the choice of alpha_j in the multiple source extension is not fully clear (the main theoretical analysis is only for single weak supervision, and for multiple source setting, for which a novel model is proposed in this paper, a full theoretical analysis that includes the effect of the alpha estimation is not provided). In particular, the probabilistic model in Sec4.2 is a bit strange for me. Since y is binary label and h(x) is first defined as a map from X to [0,1], an interpretation of the model h_j \\sim N(y,\\sigma(x)) is unclear. \n- The formulation of the proposed multiple source framework (3) itself is a bit straightforward. It is reasonable, but the technical novelty of this extension is not particularly strong. Further, compared with LPA+WL (single weak supervision), effectiveness of the multiple source extension is slight, empirically shown in Table1. The methodology of LPA+WL does not have particular novelty in my understanding (the objective function for the single supervision setting (1) is straightforward). In this sense, the performance superiority of the model newly proposed in this paper is not fully demonstrated.\n- Although theoretical analysis is interesting, it is not reflected to the learning model and the algorithm, throughout the paper. Practical benefit of the theorem is not fully revealed.\n\nMinor comments: \n- 'set alpha_j(x_i) = 0 when h_j makes a correct prediction' should be 'alpha_j(x_i) = 1'?\n- 'h_j \\sim N(y,sigma(x))' should be 'h_j \\sim N(y,sigma_j(x))'? The former definition seems to have a common variance across all h_j. \n- Why w_ij does not exist in l(f) in Sec4.2?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3d-JrSCF-4z", "reviewer": "Reviewer_xkhm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides a new error bound of LPA with prior information and compares it with the conventional spectral bound. Then it proposes two strategies to design the prior information. The paper also conducts experiments, which compares with some weakly supervised methods and semi-supervised methods. The experimental results demonstrate the effectiveness of the proposed strategies.", "summary_of_the_review": "Due to the strengths listed above, I recommend for Accept.", "strength_and_weaknesses": "Strengths:\n1. The paper proposes a new error bound for LPA, and provides an example to show its superiority compared with conventional spectral bound.\n2. The paper is technically sound.\n3. The experimental results are good. The authors also provide their codes of experiments.\n\nWeaknesses and questions:\n1. I'm a little confused about its weaklly supervised learning setting. To my knowledge, there are many kinds of weaklly supervised learning setting. For exmple, in some settings, only coarse-grained labels are given for the training data; in some settings, the given labels are sometimes not correct for the training data. What is the specific setting of this paper? From the experiments, it seems that the labels (or psuedolabels) of some data are not correct? If so, what is the difference between it and learning with noisy data? And maybe it needs to compare with such learning methods with noisy data.\n2. The paper compares its bound with spectral bound and gives a case study to show its superiority, which is good. Since the form of the two bounds are quite different, I think it's hard to say which is tighter in general. It may be interesting if you could provide the cases when the proposed bounds fail or at least worse than the conventional one. It can tell the readers when should we use the proposed bound and when should not.\n3. Why does Table 2 not report the results of GCN, CLL and so on?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster