Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering
Graph based semi-supervised learning is the problem of learning a labeling function for the graph nodes given a few example nodes, often called seeds, usually under the assumption that the graph's edges indicate similarity of labels. This is closely related to the local graph clustering or community detection problem of finding a cluster or community of nodes around a given seed. For this problem, we propose a novel generalization of random walk, diffusion, or smooth function methods in the literature to a convex p-norm cut function. The need for our p-norm methods is that, in our study of existing methods, we find those principled methods based on eigenvector, spectral, random walk, or linear system often have difficulty capturing the correct boundary of a target label or target cluster. In contrast, 1-norm or maxflow-mincut based methods capture the boundary, but cannot grow from small seed set; hybrid procedures that use both have many hard to set parameters. In this paper, we propose a generalization of the objective function behind these methods involving p-norms. To solve the p-norm cut problem we give a strongly local algorithm -- one whose runtime depends on the size of the output rather than the size of the graph. Our method can be thought as a nonlinear generalization of the Anderson-Chung-Lang push procedure to approximate a personalized PageRank vector efficiently. Our procedure is general and can solve other types of nonlinear objective functions, such as p-norm variants of Huber losses. We provide a theoretical analysis of finding planted target clusters with our method and show that the p-norm cut functions improve on the standard Cheeger inequalities for random walk and spectral methods. Finally, we demonstrate the speed and accuracy of our new method in synthetic and real world datasets. Our code is available at http://github.com/MengLiuPurdue/SLQ.
Code (1)
Tasks
ClusteringCommunity DetectionGraph ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Semi-supervised anomaly detection algorithm based on KL divergence (SAD-KL)
The unlabeled data are generally assumed to be normal data in detecting abnormal data via semisupervised learning. This assumption, however, causes inevitable detection error when distribution of unlabeled data is differ…
Anomaly DetectionSemi-supervised Anomaly DetectionSupervised Anomaly DetectionSemi-Supervised Deep Learning for Abnormality Classification in Retinal Images
Supervised deep learning algorithms have enabled significant performance gains in medical image classification tasks. But these methods rely on large labeled datasets that require resource-intensive expert annotation. Se…
Deep LearningGeneral ClassificationGenerative Adversarial Networkimage-classification+2Joint Weakly and Semi-Supervised Deep Learning for Localization and Classification of Masses in Breast Ultrasound Images
We propose a framework for localization and classification of masses in breast ultrasound (BUS) images. We have experimentally found that training convolutional neural network based mass detectors with large, weakly anno…
General ClassificationRegularized Boost for Semi-Supervised Learning
Semi-supervised inductive learning concerns how to learn a decision rule from a data set containing both labeled and unlabeled data. Several boosting algorithms have been extended to semi-supervised learning with various…
Ensemble LearningInductive LearningTangent-Normal Adversarial Regularization for Semi-supervised Learning
Compared with standard supervised learning, the key difficulty in semi-supervised learning is how to make full use of the unlabeled data. A recently proposed method, virtual adversarial training (VAT), smartly performs a…
TAR