Распространение меток в сочетании с простыми моделями может превзойти графовые нейронные сети

Оригинальный адрес:Eat020031308.GitHub.IO/papers/2020…

1. Алгоритмы на основе диффузии также полезны для задач классификации трансдуктивных узлов, но не ценятся.
   • Опыт:набор данных ogbn-arxiv, простая классификация узлов по большинству классов в домене дает точность 61%.
2. Остатки классификации и предсказания на соседних узлах положительно коррелируют

Correct and Smooth (C&S)

1. Базовый прогноз: классифицируйте узлы с помощью простой модели, отличной от GNN (например, MLP на основе функций узла или вложений).
2. Исправление: смоделируйте разницу между реальным результатом и результатом предыдущего шага с помощью метода GNN.
3. Smooth: сглаживание результата предыдущего шага с помощью алгоритма Label Propagation (2015).

Label Propagation

Обратите внимание на нормализованную матрицу смежности$S = D^{-1/2} A D^{-1/2}$, результирующая матрица узлов (одна строка на узел) равна Y, и алгоритм LP выполняет итерацию$Y = (1 - \alpha) Y + \alpha S Y$Распространение результатов на обучающем наборе на полный граф до сходимости.

сходящееся решение$\hat Y$сделаю$\text{tr}(\hat Y^T (I - S) \hat Y) + (\frac1\alpha - 1) ||\hat Y - Y ||^2$минимизировать. Минимизация первой части гарантирует, что оценки будут гладкими, а вторая часть гарантирует, что предполагаемые результаты будут максимально приближены к фактическим результатам.

Правильная информация о реализации

В процессе C&S, за исключением того, что ссылка Smooth явно использует LP, алгоритмы двух других частей могут быть заменены.

В этой статье правильная ссылка также использует алгоритм LP для распространения остатков на обучающем наборе на полное изображение.$E = (1 - \alpha) E + \alpha S E$

Но в итеративном процессе остаток будет становиться все меньше и меньше.$||(1 - \alpha) E + \alpha S E||_2 \le (1 - \alpha) ||E||_2 + \alpha ||S||_2 ||E||_2 = ||E||_2$Так что надо исправлять

1. Автомасштабирование, Умножает остаточную оценку вне тренировочного набора на коэффициент, чтобы его абсолютное среднее значение равнялось тренировочному набору.
2. Scaled Fixed Diffusion (FDiff-scale) Другой алгоритм диффузии:$E = D^{-1}AE$не меняя невязок на обучающей выборке (где$D^{-1}A$Думайте об этом как о матрице перехода)

Результаты экспериментов

Количество параметров очень мало или даже не требует изучения параметров для обеспечения хорошей производительности, а обучение происходит быстро.
Эффект классификации превосходит SotA для нескольких наборов данных и в настоящее время находится в стадии разработки.Список задач классификации узлов OGBВходит в число лучших по нескольким задачам.