Semi-Supervised Learning on Graphs through Reach and Distance Diffusion
Semi-supervised learning (SSL) is an indispensable tool when there are few labeled entities and many unlabeled entities for which we want to predict labels. With graph-based methods, entities correspond to nodes in a graph and edges represent strong relations. At the heart of SSL algorithms is the specification of a dense {\em kernel} of pairwise affinity values from the graph structure. A learning algorithm is then trained on the kernel together with labeled entities. The most popular kernels are {\em spectral} and include the highly scalable "symmetric" Laplacian methods, that compute a soft labels using Jacobi iterations, and "asymmetric" methods including Personalized Page Rank (PPR) which use short random walks and apply with directed relations, such as like, follow, or hyperlinks. We introduce {\em Reach diffusion} and {\em Distance diffusion} kernels that build on powerful social and economic models of centrality and influence in networks and capture the directed pairwise relations that underline social influence. Inspired by the success of social influence as an alternative to spectral centrality such as Page Rank, we explore SSL with our kernels and develop highly scalable algorithms for parameter setting, label learning, and sampling. We perform preliminary experiments that demonstrate the properties and potential of our kernels.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Pairwise Teacher-Student Network for Semi-Supervised Hashing
Hashing method maps similar high-dimensional data to binary hashcodes with smaller hamming distance, and it has received broad attention due to its low storage cost and fast retrieval speed. Pairwise similarity is easily…
RetrievalHamilton-Jacobi equations on graphs with applications to semi-supervised learning and data depth
Shortest path graph distances are widely used in data science and machine learning, since they can approximate the underlying geodesic distance on the data manifold. However, the shortest path distance is highly sensitiv…
Wasserstein Soft Label Propagation on Hypergraphs: Algorithm and Generalization Error Bounds
Inspired by recent interests of developing machine learning and data mining algorithms on hypergraphs, we investigate in this paper the semi-supervised learning algorithm of propagating "soft labels" (e.g. probability di…
PAC learningDynamical Distance Learning for Semi-Supervised and Unsupervised Skill Discovery
Reinforcement learning requires manual specification of a reward function to learn a task. While in principle this reward function only needs to specify the task goal, in practice reinforcement learning can be very time-…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Multi-Task Hypergraphs for Semi-supervised Learning using Earth Observations
There are many ways of interpreting the world and they are highly interdependent. We exploit such complex dependencies and introduce a powerful multi-task hypergraph, in which every node is a task and different paths thr…
Earth Observation