Методы обучения графам трудно добавить к существующим конвейерам машинного обучения. Использование Correct&Smooth для уточнения существующих прогнозов путем «сглаживания» их по структуре графика.
Введение
Хотя графовые нейронные сети (GNN) в последнее время доминируют в академических тестах [3], они не получили сопоставимого внедрения в отраслевом машинном обучении. Структуры графовых данных и GNN трудно масштабировать для больших данных [1, 6] и они достаточно отличаются от стандартных наборов инструментов для контролируемого обучения, поэтому командам потребуется пройти трудоемкий и дорогостоящий процесс для их внедрения. В результате, даже если данные имеют четкую структуру графа, они часто игнорируются или включаются в виде настраиваемых вручную функций на уровне строк, таких как степень узла или графлеты [4].
Мы хотим перейти от функций узлов, созданных вручную на уровне строк, к общим методам обучения графам, внося минимальные изменения в наш рабочий процесс моделирования. Используя недавний алгоритм машинного обучения графов под названием Correct & Smooth (C&S) [1], мы можем конкурировать или превзойти GNN, используя модуль постобработки, который находится поверх вашего существующего контролируемого классификатора. Мы продемонстрируем метод на наборе данных LastFM Asia, где задача состоит в том, чтобы предсказать страну проживания пользователей в социальной сети. Работаем по порядку:
- Описать набор данных LastFM Asia и задачу классификации трансдуктивных узлов
- Реализовать C&S с нуля, используя PyTorch и PyG [5]
- Используйте C&S для повышения производительности готовой модели классификатора и сравнивайте ее с базовыми уровнями при различных абляциях данных. В наших экспериментах мы наблюдали увеличение точности на 20% при постобработке с помощью C&S по сравнению с базовым MLP.
Вы можете следить за кодом и результатами в Colab или установитьsimple correct&smooth напрямую в виде пакета Python:
pip install https://github.com/andrewk1/correctandsmooth/archive/refs/tags/v0.0.2.zipДавайте начнем!
Представляем наш набор данных и классификацию Transductive Node
LastFM Азия
LastFM Asia был представлен в [2] и состоит из 7 624 пользователей и 55 612 дружеских отношений. Для каждого пользователя у нас также есть 128-мерный вектор признаков, представляющий исполнителей, которые нравятся пользователю, и индекс, описывающий их родную страну из 18 классов. Цель состоит в том, чтобы предсказать, из какой родной страны пользователь, учитывая график и предпочтения исполнителя.
Мы используем вспомогательный класс набора данных из PyG для загрузки набора данных. Ребра хранятся в виде тензора пар индексов узлов. Никакой дополнительной обработки не требуется.
Вот как выглядит сеть (рис. 1) с расположением узлов, определенным с помощью метода Вороного из GraphViz.
Классификация трансдуктивных узлов
В стандартной настройке обучения с учителем мы классифицируем каждого пользователя, используя информацию об их любимых исполнителях. В трансдуктивной классификации узлов мы решаем ту же задачу классификации, но дополнительно знаем всю структуру графа во время обучения, включая расположение узлов проверки и тестового набора.
Визуально это выглядит следующим образом (рис. 2), где мы сделали случайные разбиения train/val/test для узлов. Мы видим всю сеть всегда, но маскируем классы зеленых (валидация) и красных (тест) узлов во время обучения.
Реализация C&S в PyTorch и PyG
C&S использует шаблон, согласно которому соседние узлы, как правило, имеют одинаковые метки и схожие функции, концепция, называемая гомофилией. Как только у нас есть предсказанное распределение вероятностей по классам от контролируемого ученика, C&S сначала исправляет ошибки на тестовых узлах, используя ошибки из прогнозов на обучающих узлах, а затем сглаживает прогнозы на тестовых данных, включая близлежащие наземные метки обучения. .
Мы реализуем C&S с нуля по бумаге, объясняя уравнения из бумаги кодом.
Шаг 1: Обучение базового предиктора
Первым шагом является получение базовой модели классификатора, которая может выводить распределение вероятностей по классам на выборку. Обучаем неглубокий MLP в PyTorch:
MLP достигает точности 0,696 при проверке и точности 0,726 на тестовом наборе. В то время как узлы в глубине каждого кластера класса согласованы, модель делает ошибки для пользователей с друзьями в разных странах (границы кластера).
Шаг 2: Правильно
Сначала мы формируем матрицу, каждая строка которой равна остаточной ошибке между метками (с горячим кодированием) и предсказанными распределениями классов только для обучающих узлов. Здесь «Lt», «Lv» и «U» — наборы train, val и test соответственно.
В коде это выглядит следующим образом:
Далее мы «сглаживаем» ошибку по графику. Из-за гомофилии мы ожидаем, что ошибки будут иметь положительную корреляцию для соседних узлов, поэтому для узлов проверки/тестирования ошибки на соседних обучающих узлах могут предсказывать реальную ошибку.
Корректировка вычисляется с помощью следующей рекурсии.S – нормализованная матрица смежности, поэтому SE установит новую ошибку для каждого узла как средневзвешенное значение ошибок соседних узлов, где узлы с более низкой степенью (меньше соседей) будут иметь более высокий вес (более подробное объяснение S см. в этой Math StackExchange thread). Здесь α (альфа) — гиперпараметр.
В коде это цикл while, в котором мы проверяем сходимость, используя норму L2 изменения E.
Визуализируем матрицы остаточных ошибок для правильного класса на первом и последнем шагах правильной фазы (чем ярче цвет, тем выше ошибка). Эмпирически мы видим, что правильная фаза уменьшит величину ошибки на некоторых узлах, хотя видимой разницы не так много.
После сглаживания ошибки C&S масштабирует размер новых ошибок, чтобы они соответствовали масштабу исходных ошибок обучения. Добавление остатков обратно к исходным прогнозам дает нам новый вектор прогноза Zr.
В коде мы берем среднюю норму L1 ошибок обучения на строку, а затем нормализуем и повторно масштабируем новые прогнозы.
Шаг 3: Гладкий
На этапе «Правильно» мы сгладили ошибки по соседним узлам. На этапе «Сглаживание» мы также будем сглаживать прогнозы по соседним узлам, следуя той же интуиции. Операция сглаживания идентична исправлению ошибок, на этот раз повторяя нашу матрицу наилучшего предположения G, инициализированную нашим вектором предсказания масштаба.
Код также почти идентичен правильному шагу:
Как только мы запустим этап сглаживания, у нас будут окончательные прогнозы! GIF ниже визуализирует наше лучшее предположение на каждой итерации процесса сглаживания. Мы можем видеть, что узлы, которые меняют свои прогнозы, чаще всего живут между кластерами классов, где предпочтения художника сами по себе не являются четким предиктором национальности.
Измерение производительности
Мы сравниваем производительность тестового набора на LastFM Asia между MLP и C&S, используя точность, включая развертку гиперпараметров по выбору alpha1 и alpha2 в проверочном наборе (оба они также были оптимизированы в статье).
С каждым шагом мы видим увеличение точности почти на 10%! Очевидно, что включение структуры графа в эту конкретную задачу прогнозирования дает огромные преимущества. Мы также видим важность двух переменных alpha для производительности шагов сглаживания — запустите проверку гиперпараметров, если вы решите реализовать этот метод.
Понимание C&S
Повышение точности на 20% заслуживает тщательного изучения — почему C&S работает здесь так хорошо? Мы думаем, что гомофилия может объяснить результаты, когда обучающие узлы рядом с тестовыми узлами могут информировать метки тестовых узлов. Давайте проведем простой эксперимент: запустим шаг сглаживания непосредственно над метками обучающего узла и используем результаты для прогнозирования меток проверки и тестирования:
Сглаживание обучающих меток при разделении 80/10/10%
Интересный результат — мы видим, что простое сглаживание обучающих меток по соседним тестовым узлам будет почти соответствовать производительности подхода C&S+MLP! Это подтверждает, что преимущества C&S зависят от обмена информацией об обучающем узле с соседними тестовыми узлами.
Для нашего выбора train/val/test = 80/10/10% у нас может быть просто доступ к множеству смежных обучающих узлов, что позволяет работать такому подходу, как сглаживание обучающих меток. Давайте попробуем уменьшить до 50/25/25% и повторить эксперимент. Мы могли бы ожидать, что C&S превзойдет здесь, потому что он может использовать преимущества лежащего в основе MLP для «заполнения» меток.
Сглаживание обучающих меток при разделении 50/25/25%
Даже в режиме низких обучающих данных чистое сглаживание работает очень хорошо, полностью превосходя C&S и другие подходы к обучению! Хотя мы уменьшили количество узлов в обучающей выборке, мы не коснулись количества соединений графа. Визуализируя разделение данных, это кажется разумным результатом из-за плотности соединений графа: большинство узлов по-прежнему имеют соединение с обучающим узлом!
Что, если мы проведем подвыборку ребер в графе и повторно запустим конвейер той же модели, удалив 70% ребер? Интуиция здесь такова, что мы не можем полагаться на чистую плотность графа, где у тестовых узлов будет много обучающих узлов, чтобы вывести метку. Наши модели должны будут более эффективно комбинировать отдельные узлы признаков и любые существующие соседи, чтобы сформировать прогноз.
Вот результаты этой абляции:
Обучение сглаживанию меток на разделении 80/10/10 % с 30 % краев
Результаты совпадают с нашей интуицией! C&S является здесь явным победителем, превосходя как MLP, так и базовые линии простого сглаживания с точностью 80% против 70% и 60% соответственно. Базовая линия сглаживания даже хуже, чем базовая линия MLP из-за недостаточной плотности краев. Тем не менее, комбинация двух сигналов (пользовательские функции и структура графика) с помощью C&S все же может привести к увеличению точности на 10% по сравнению с MLP.
Заключение
C&S — это надежный метод повышения производительности существующего классификатора графических данных с помощью двух быстрых и простых шагов постобработки. В очень плотных графиках вы должны попробовать просто применить шаг сглаживания к вашим обучающим меткам для получения сравнимого прироста точности. Когда ваши графики не такие плотные или ваш тестовый набор не имеет много общих ребер с вашими обучающими данными, C&S может дать большой толчок учащимся под наблюдением, чтобы использовать некоторые знания о структуре ребер. Фундаментальный код сглаживания очень похож для всех методов, поэтому стоит попробовать их все в своем следующем проекте!
Вы можете найти меня в Твиттере для получения дополнительной информации:)
Простой правильный и гладкий пакет и Colab
Упакованную версию модели можно найти здесь:
Весь код, результаты и визуализации из этого блога можно найти в этом Colab:
Цитаты
[1] Хуанг, Цянь и др. «Сочетание распространения меток и простых моделей превосходит графовые нейронные сети». препринт arXiv arXiv:2010.13993 (2020 г.).
[2] Роземберски, Бенедек и Рик Саркар. «Характеристические функции на графиках: одного поля ягоды, от статистических дескрипторов до параметрических моделей». Материалы 29-й Международной конференции ACM по управлению информацией и знаниями. 2020.
[3] https://ogb.stanford.edu/docs/leader_nodeprop/
[4] https://en.wikipedia.org/wiki/Graphlets
[5] Фей, Матиас и Ян Эрик Ленссен. «Быстрое изучение представления графа с помощью PyTorch Geometric». препринт arXiv arXiv:1903.02428 (2019 г.).
[6] Бойчевский, Александр и др. «Масштабирование графовых нейронных сетей с приблизительным рейтингом страницы». Материалы 26-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. 2020.
