A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning

Thomas Bonald, Nathan de Lara
11/13/2023
cs.LGcs.SI

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Diffusion Probabilistic Models for Structured Node Classification

82% match2023

Diffusion Probabilistic Models for Structured Node Classification

82% match2023

Diffusion on Graph: Augmentation of Graph Structure for Node Classification

82% match1 repo82025

From Graph Diffusion to Graph Classification

82% match2024

ProtoGuide: Prototype-Driven Guidance for Class-Conditional Graph Generation

81% match2026

Diffusion Maps for Signal Filtering in Graph Learning

80% match2023

Cite this paper

@article{bonald2023consistent,
  title  = {A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning},
  author = {Thomas Bonald and Nathan de Lara},
  year   = {2023},
  eprint = {2311.07627},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2311.07627v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2311.07627.svg)](https://codeofpaper.com/paper/2311.07627)

Discussion