Variance-enlarged Poisson Learning for Graph-based Semi-Supervised Learning with Extremely Sparse Labeled Data

We thank the reviewer for the constructive comments and insightful suggestions.

Comment 1: 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?

Response: Thank you for your valuable comment. We will offer more experimental comparison with recent approaches in the final version. The primary contribution of this work lies in the introduction of a simple yet theoretically sound framework, Variance-Enlarged Poisson Learning (VPL). This framework is designed to tackle the issue of degenerate solutions, which tend to be nearly constant for unlabeled points. Our work is poised to offer significant value to the ICLR community by providing novel and impactful insights. Additionally, we present two specific algorithms, namely V-Laplace and V-Poisson. As they are advanced versions of the original Laplace learning and Poisson learning, we choose to demonstrate their superiority through experimental comparisons with variants of Laplace learning and Poisson learning.

Comment 2: "Graph structures used in the experiment are unclear from the description of the paper." and "Although 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?"

Response: Thank you for your kind comment. Due to page limitations, we present detailed information on k-NN graph construction in Appendix B. Specifically, for each dataset, we generate a 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. The graph is constructed as a $K$-nearest neighbor graph with edge weights calculated using the formula $w_{ij}=\exp(-4\lVert x_i-x_j\Vert^2/d_K(x_i)^2)+\epsilon$, where $x_i$ denotes the latent variables for sample $i$, $d_K(x_i)$ represents the distance in the latent space between $x_i$ and its K-th nearest neighbor, and $\epsilon\ge 0$.

Comment 3: In 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?

Response: Thank you for your insightful comments and inquiries. We have taken them into careful consideration and conducted additional experiments to address your concerns.

About labels with screwed distribution To assess the effectiveness of our proposed approach on labels with skewed distribution, we conduct experiments specifically on labeled data characterized by a long-tailed distribution. In this scenario, the distribution of labels follows a long-tailed pattern, with the first class having $n_1$ labels and subsequent classes having progressively more labels, that is, the $i$-th class is randomly assigned $n_i=\lfloor {n_1}/{\eta^{\frac{i-1}{k-1}}}\rfloor$ labels, where $k$ represents the number of classes, and $\eta$ denotes the imbalance factor. The experimental results on MNIST with imbalance ratios $\eta\in{0.1, 0.2, 0.5}$ are summarized in the tables below. These results demonstrate the effectiveness of our proposed approaches, V-Laplace and V-Poisson, in achieving higher accuracy compared to other methods when dealing with labels of skewed distribution.

Imbalance Ratio=0.1

About Iteration Termination Regarding the determination of the number of iterations in our proposed approach, we employ a technique inspired by Calder et al. (2020). Specifically, we incorporate the iteration step $p_{t+1}=WD^{-1}p_t$ in the algorithms of V-Laplace and V-Poisson. The initial vector $p_0$ is initialized with ones at the positions of all labeled vertices and zeros elsewhere. The iterations for V-Laplace and V-Poisson are terminated once the infinity norm of the difference between $p_t$ and $p_{\infty}$, i.e., $\Vert p_t-p_{\infty}\Vert_{\infty}$, is less than or equal to $\frac{1}{n}$. This termination criterion is chosen just before reaching the mixing time. Herein, $p_{\infty}=W1 \frac{1}{1^\top W1}$.

Imbalance Ratio=0.2

Imbalance Ratio=0.5

About more labels

In response to your query regarding experiments with more labels, we have conducted experiments to investigate the performance of our proposed V-Laplace and V-Poisson in scenarios where the number of labels is increased. The results, presented in the table below, indicate that as the number of labels increases, the performance gain of our proposed methods diminishes and becomes weaker compared to Laplace and Random Walk methods, but it is still slightly better than Poisson learning.

MNIST

FashionMNIST

Dear reviewer cv8h,

Thanks again for your valuable time and insightful comments. As the deadline for the Author/Reviewer discussion is approaching, it would be nice of you to let us know whether our answers have solved your concerns so that we can better improve our work. We are looking forward to your feedback.

Best regards,

Authors of Paper 221

About Convergence Dependency on Parameters

Comment: 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?

Response: Thanks for your valuable comment. We would like to provide analysis about the influence of $\lambda$ to convergence. In term of the total number of iterations, we employ the trick by Calder et al. (2020). Specifically, we add the iteration step $p_{t+1}=WD^{-1}p_t$ in the algorithms of V-Laplace and V-Poisson, where $p_0$ 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 $\Vert p_t-p_{\infty}\Vert_{\infty}\le \frac{1}{n}$ is achieved, just before reaching the mixing time. Herein, $p_{\infty}=W 1/(1^\top W1)$. Therefore, the algorithm's iteration is solely tied to the specific graph and remains independent of $\lambda$.

About Clarification on Lemma 4.1

Comment: I suspect Lemma 4.1 could have an error and therefore all proofs that derive from it. See questions.

Response: Thanks very much for your kind reminding! We appreciate your careful review. We have carefully examined Lemma 4.1 and made revision about it in the manuscript. Please refer to the highlighted part in the updated Lemma 4.1.

The corrected expression for the distance measure is $L(u(x_i),u(x_j))=\frac{1}{2}\Vert u(x_i)-u(x_j)\Vert_2^2$ in Eq. 3.2. Consequently, the equivalent objective should be $\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n (w_{ij}-\lambda q_iq_j)\Vert u(x_i)-u(x_j)\Vert_2^2$ since we have

$

\begin{aligned} \mathrm{Var}[u]=&\sum_{i=1}^n q_i\Vert u(x_i)-\overline{u}\Vert_2^2\\ =&\sum_{i=1}^n q_i\Vert u(x_i)\Vert_2^2-\sum_{i=1}^n\sum_{j=1}^n q_iq_j\langle u(x_i),u(x_j)\rangle\\ =&\frac{1}{2} \sum_{i=1}^n\sum_{j=1}^n q_iq_j(\Vert u(x_i)\Vert_2+\Vert u(x_j)\Vert_2^2) - \sum_{i=1}^n\sum_{j=1}^n q_iq_j\langle u(x_i),u(x_j)\rangle\\ =&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n q_iq_j \Vert u(x_i)-u(x_j)\Vert_2^2. \end{aligned}

$

Concerning the provided illustration, we have $\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n (w_{ij}-\lambda q_i q_j)\Vert u(x_i)-u(x_j)\Vert_2^2=0.1875$ and $\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n w_{ij}\Vert u(x_i)-u(x_j)\Vert_2^2-\lambda \mathrm{Var}[u]=0.5^2-0.0625=0.1875$. It's important to note that the correction made to $L$ does not alter the corresponding conclusions in Theorem 3.1 and Proposition 4.3 based on this lemma.

We thank the reviewer for the constructive comments and insightful suggestions.

About Iterative vs. Linear Solution

Comment: 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?

Response: Thank you for your insightful comment. In Section 3.2, we introduce V-Laplace (Eq. 3.3) and V-Poisson (Eq. 3.4) with linear equations. Indeed, as suggested by the reviewer, these equations can be solved using classical methods for linear systems. However, it is crucial to highlight that solving V-Laplace and V-Poisson through direct methods entails high complexity. This involves the inverse or pseudoinverse process of a dense matrix associated with $W' = W - \lambda qq^\top \in \mathbb{R}^{n \times n}$ (where $n=70000$ for MNIST and Fashion MNIST, and $n=60000$ for CIFAR datasets), resulting in a computational complexity of $O(n^3)$.

Therefore, we adopt an iterative approach that involves only matrix multiplication, offering a lower computational complexity of $O(Tn^2)$, where $T$ usually takes between 100 and 200. Additionally, for the sake of efficiency, we do not directly use the dense matrix $W'$ to compute the Laplacian matrix during iterations. This is motivated by the sparsity of $W$ in our experiments, involving k-NN graphs and masked attention maps, enabling us to leverage sparse matrix multiplication for substantial computational speedup. The overall iteration time is about 1-3 seconds.

About Relation to Previous Work

Comment: 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?

Response: Thank you for providing additional insights into the connection between our approach and Laplace learning. We appreciate your thoughtful comment and the reference to Section 3.1 of [2], where Laplace learning is associated with the probability of sampling a spanning forest that separates the seeds.

Upon further consideration, we acknowledge that while our approach may not have a directly similar interpretation to the probability of sampling spanning forests as in Laplace learning, but there is a potential connection through the introduction of variance enlargement. Specifically, Lemma 4.1 in our work introduces variance enlargement, which, akin to Laplace learning, has the effect of reducing the edge weights in the graph. In this context, the reduction of edge weights can be seen as a way of decreasing the weight $w(f)$ of a forest in the graph, thus amplifying the importance of forests with large weights (similar to Proposition 4.3 in our work). This somewhat coincides with that the lower energy can give the 2-forests of lowest cost more probability mass $p(f)$.

About Consideration of Directed Graphs

Comment: 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?

Response: Thank you for your thoughtful comment. Our proposed algorithms, V-Laplace and V-Poisson, can be effectively applied to directed graphs. This versatility arises from the fact that the Poisson equations in Eq. 3.2 and Eq. 3.3 do not mandate the weight matrix $W$ to be symmetric. It is noteworthy that when working with directed graphs, considerations may arise regarding whether to utilize the in-degree matrix or out-degree matrix when defining the Laplacian matrix.

The variational analysis detailed in Section 4.2 cannot be extended to the directed case, because the theoretical results in this section are established under the assumption of asymptotic limits, particularly as the bandwidth of the symmetric edge weight $w_{ij}=\psi\left(\frac{\Vert x_i-x_j\Vert_2^2}{h}\right)$ tends to zero.

We thank the reviewer for the constructive comments and insightful suggestions.

Comment 1: 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.

Response: Thanks very much for your kind comment. Your suggestion to extend our experiments to include larger datasets, particularly ImageNet, is certainly noteworthy. However, it is imperative to acknowledge the inherent challenges associated with such an expansion, especially given the extensive scale of ImageNet-1K. The graph structure within ImageNet-1K is notably vast, boasting a node count of 1.2 million. Furthermore, the intricacies introduced by the graph weight matrix, with dimensions on the order of $10^6\times 10^6$, pose formidable computational and methodological challenges. Addressing such challenges requires careful consideration and exploration of alternative strategies. While the direct application of our methods to ImageNet-1K may pose difficulties, we are actively exploring avenues to enhance scalability and extend the applicability to larger datasets.

Comment 2: My 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.

Response: Thank you for your insightful comment. The focus of our paper is classification, a task where two components play a crucial role in determining the overall performance: representation learning and classifier learning. Although self-supervised learning has demonstrated promising results in representation learning, it encounters challenges in effectively learning classifiers, especially in scenarios marked by severely restricted labeled data, such as situations where there is only one label per class.

To illustrate this point, we refer to the open-source code and model parameters associated with an exemplary linear probe achievement of 91.9% on CIFAR-10. The source code and model parameters are available at SimSiam-on-CIFAR10, which utilizes the SimSiam framework. Building upon the pretrained model, we conduct two experiments to underscore the effectiveness of graph-based semi-supervised learning in scenarios of label scarcity: (i) We utilize the SimSiam pretrained model to extract features from the entire CIFAR-10 dataset and construct a 10-nearest-neighbors graph on these representations. We then randomly choose which data points are labeled, and predict unlabeled data for all data points using different graph-based semi-supervised learning approaches; (ii) For comparison, we directly use several randomly chosen labeled data to obtain a linear classifier, and finally use this classifier to evaluate the classification accuracy of all samples.

The experimental results are summarized in the table below. It is evident that the linear classifier, trained solely on labeled data, outperforms Laplace learning in scenarios with extremely sparse data. However, it 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. Also, it is worth noting that V-Poisson only needs 5 labels to achieve a good result of 85.5 (1.6). This demonstrates the effectiveness and potential of graph-based semi-supervised learning. Many thanks to the reviewers for their thoughts about self-supervised learning and this work, we have added the experiments to the newly revised version.

Comment 3: Typos: e.g., lambda in the caption of Figure 1.

Response: Thank you for your careful review. We have rectified the mentioned typos and address some other potential errors.

Dear reviewer CApx,

Thanks again for your valuable time and insightful comments. As the deadline for the Author/Reviewer discussion is approaching, it would be nice of you to let us know whether our answers have solved your concerns so that we can better improve our work. We are looking forward to your feedback.

Best regards,

Authors of Paper 221

We thank the reviewer for the constructive comments and insightful suggestions.

Comment: "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." and "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."

Response: Thank you for your insightful comment. We appreciate the opportunity to consider the broader applicability of variance enlargement to other Graph SSL approaches. Upon a careful examination of Algorithm 1 and Algorithm 2, it becomes evident that variance enlargement corresponds to a straightforward step—specifically, the incorporation of $\lambda\overline{U}$ into the message passing process. To illustrate, within the framework of Graph Convolutional Networks (GCN), the layer-wise propagation rule is typically defined as $H^{(l+1)}=\sigma(D^{-1/2}AD^{-1/2} H^{(l)}W^{(l)})$, where $D^{-1/2}AD^{-1/2} (H^{(l)}W^{(l)})$ indicates the propagation of the message $H^{(l)}W^{(l)}$. Analogous to V-Laplace and V-Poisson, the incorporation of variance enlargement directly enlarges the variance of $H^{(l)}W^{(l)}$ into the graph convolutions:

where $\overline{U}=\overline{H^{(l)}W^{(l)}}$ denotes the (weighted) zero-mean normalization of $H^{(l)}W^{(l)}$. This incorporation can be generalized to various Graph SSL approaches, as we can treat variance enlargement as a step in the aggregation process of message-passing neural networks [1], thereby enhancing the dispersion of messages.

Thanks again for your kind suggestion, which has inspired us to delve into the application of variance enlargement across a spectrum of Graph SSL approaches, extending beyond V-GPN. In our forthcoming research, we aim to broaden our investigation, providing a thorough discussion on the nuanced aspects of where and why variance enlargement demonstrates its effectiveness or limitations within diverse Graph SSL methodologies. This endeavor is intended to offer a comprehensive understanding of the implications of variance enlargement, contributing valuable insights to the field and fostering a deeper comprehension of its applicability and impact across a diverse range of Graph SSL frameworks.

[1] Xu K, Hu W, Leskovec J, et al. How Powerful are Graph Neural Networks?[C]//International Conference on Learning Representations. 2018.