Can I read Strongly Local P-norm-cut Algorithms for Semi-supervised Learning and Local Graph Clustering on EtoBox?

Strongly Local P-norm-cut Algorithms for Semi-supervised Learning and Local Graph Clustering by Liu, Meng; Gleich, David F. is a scholarly article available to read on EtoBox.

What is Strongly Local P-norm-cut Algorithms for Semi-supervised Learning and Local Graph Clustering about?

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

Author

Liu, Meng; Gleich, David F.

Published

2020

Language

EN