Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity

By Eliav Buchnik, Edith Cohen. 2017

20 citations recorded by the source corpus.

Graph-based semi-supervised learning (SSL) algorithms predict labels for all nodes based on provided labels of a small set of seed nodes. Classic methods capture the graph structure through some underlying diffusion process that propagates through the graph edges. Spectral diffusion, which includes personalized page rank and label propagation, propagates through random walks. Social diffusion propagates through shortest paths. A common ground to these diffusions is their {\em linearity}, which does not distinguish between contributions of few "strong" relations and many "weak" relations. Recently, non-linear methods such as node embeddings and graph convolutional networks (GCN) demonstrated a large gain in quality for SSL tasks. These methods introduce multiple components and greatly vary on how the graph structure, seed label information, and other features are used. We aim here to study the contribution of non-linearity, as an isolated ingredient, to the performance gain. To do so, we place classic linear graph diffusions in a self-training framework. Surprisingly, we observe that SSL using the resulting {\em bootstrapped diffusions} not only significantly improves over the respective non-bootstrapped baselines but also outperform state-of-the-art non-linear SSL methods. Moreover, since the self-training wrapper retains the scalability of the base method, we obtain both higher quality and better scalability.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Attention-based Graph Neural Network for Semi-supervised Learning (2018, methodology): “The classiﬁcation accuracy of all the baseline methods are collected from [46, 27, 38, 31, 11, 41].”
Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity (2018, background): “∗The full version of the paper is available in [7].”
Combining Label Propagation and Simple Models Out-performs Graph Neural Networks (2020, background): “…there are several recent approaches that incorporate nonlinearity into label propagation methods to compete with GNNs and achieve scalability (Eliav & Cohen, 2018; Ibrahim & Gle-ich, 2019; Tudisco et al., 2020), but these methods focus on settings of low label rates and don’t incorporate…”
Diffusion Improves Graph Learning (2019, background): “Graph diffusion and random walks have been extensively studied in classical graph learning [13, 14, 36, 37], especially for clustering [34], semi-supervised classification [12, 22], and recommendation systems [44].”
Bootstrapped Graph Diffusions (2018, background): “∗The full version of the paper is available in [7].”