A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning
The task of semi-supervised classification aims at assigning labels to all nodes of a graph based on the labels known for a few nodes, called the seeds. One of the most popular algorithms relies on the principle of heat diffusion, where the labels of the seeds are spread by thermoconductance and the temperature of each node at equilibrium is used as a score function for each label. In this paper, we prove that this algorithm is not consistent unless the temperatures of the nodes at equilibrium are centered before scoring. This crucial step does not only make the algorithm provably consistent on a block model but brings significant performance gains on real graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph LearningSimilar Papers 제목 키워드 기반
A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs
Semi-supervised classification on graphs aims at assigning labels to all nodes of a graph based on the labels known for a few nodes, called the seeds. The most popular algorithm relies on the principle of heat diffusion,…
General ClassificationRegularizing Semi-supervised Graph Convolutional Networks with a Manifold Smoothness Loss
Existing graph convolutional networks focus on the neighborhood aggregation scheme. When applied to semi-supervised learning, they often suffer from the overfitting problem as the networks are trained with the cross-entr…
Context-guided diffusion for label propagation on graphs
Existing approaches for diffusion on graphs, e.g., for label propagation, are mainly focused on isotropic diffusion, which is induced by the commonly-used graph Laplacian regularizer. Inspired by the success of diffusivi…
A nonlinear diffusion method for semi-supervised learning on hypergraphs
Hypergraphs are a common model for multiway relationships in data, and hypergraph semi-supervised learning is the problem of assigning labels to all nodes in a hypergraph, given labels on just a few nodes. Diffusions and…
Iterative Graph Self-Distillation
Recently, there has been increasing interest in the challenge of how to discriminatively vectorize graphs. To address this, we propose a method called Iterative Graph Self-Distillation (IGSD) which learns graph-level rep…
Contrastive LearningGraph LearningKnowledge Distillation