Исследователи представили алгоритм, решающий задачу полуобученного обучения (SSL) на графах с использованием p-Лапласиана за почти линейное время. Метод преодолевает ограничения стандартного квадратичного подхода, который при нехватке размеченных данных стремится к константным значениям, и позволяет эффективно масштабировать обучение на графах с большим количеством неразмеченных узлов, сохраняя высокую точность классификации.

Традиционные методы SSL, основанные на минимизации энергии Дирихле при p=2, часто теряют эффективность в условиях дефицита разметки, так как решение вырождается в константу при увеличении объема неразмеченных данных. Новый подход использует технику продолжения по параметру p, что позволяет плавно переходить от хорошо изученного случая p=2 к более сложным нелинейным задачам, где p > 2. Это обеспечивает более устойчивую работу модели в условиях разреженных данных.

Разработанный солвер демонстрирует вычислительную сложность, близкую к линейной, что делает его пригодным для обработки графов с миллионами узлов. Алгоритм эффективно находит баланс между локальной структурой данных и глобальной связностью графа, что критически важно для задач классификации в сложных сетях, где информация о метках крайне ограничена.

Ключевые факты

  • Алгоритм обеспечивает решение задачи p-Лапласиана за почти линейное время относительно количества ребер в графе.
  • Метод решает проблему вырождения оценок в константные функции, характерную для стандартных методов при p=2.
  • Техника продолжения по параметру p позволяет итеративно уточнять решение, начиная с классического квадратичного случая.
  • Подход значительно повышает качество обучения в сценариях с крайне малым количеством размеченных примеров (few-shot learning на графах).