Большинство современных нейросетей построены на основе графовых данных. Однако чтобы спроектировать на их основе сложную систему, ML-модель должна уметь эти данные векторизировать, а это далеко не тривиальная задача.
Мы задали ее командам-участникам хакатона «Цифровой прорыв в ЦФО», который прошел в сентябре в московском офисе VK. И сейчас покажем три, на наш взгляд, лучших решения и подхода к созданию моделей на основе графов.
Задача и условия
Для хакатона VK подготовил задачу бинарной классификации. Цель — создать ML-модель, которая среди широкой аудитории будет определять пользователей, склонных к благотворительности. Мы предложили кейс с благотворительностью, поскольку сами решаем подобные задачи в социальных проектах VK: Добро.Mail.ru, Благотворительность ВКонтакте, Социальные проекты ОК.
С одной стороны, нам интересно было увидеть новые подходы и нестандартные решения. С другой — поделиться этими идеями с другими компаниями и командами, которые развивают социальные проекты или работают с графовыми данными. Как обычно, решения участников хакатона находятся в открытом доступе и могут быть полезны всем, кто создает ML-модели и обогащает их графами.
Участникам предстояло обработать большой массив данных: последовательности пользовательских состояний, наборы вещественных признаков и топ близких пользователей с тем же признаковым описанием. Теоретически с такими данными можно работать в любом формате. Но в рамках этого кейса важно было применить математические методы обработки сущностей, связанных графовыми представлениями.
На разработку отводилось только 48 часов. В распоряжении команд были ресурсы Cloud ML Platform от VK Cloud для проведения экспериментов с данными и обучения ML-моделей и платформа All Cups, на которой участники могли видеть Score на части своей выборки.
В чем особенность графов и почему они стали основой задачи
Графы — это структурные единицы представления данных. Их можно считать одним из самых естественных представлений сложных данных: в обычной жизни мы часто определяем предметы и системы с точки зрения их взаимосвязи с другими объектами и вещами.
Самый простой пример графа — карта метро
Графы можно использовать для построения ML-моделей в различных областях: естествознании, физике, общественных системах. Один из известных примеров — сервис «Рекомендуемые друзья в соцсетях». В его основе лежит рекомендательная система, которая представляет поиск любого случайного человека как математическую задачу. Есть пользователь-объект, имеющий устойчивые связи с другими людьми, которые, в свою очередь, также имеют связи с новыми пользователями. Цель — найти кратчайший путь к целевому человеку через эти связи.
Объединив всех пользователей в единую сеть, можно получить большой граф, агрегировать средние признаки друзей: образование, местоположение, возраст — и «проложить маршрут» к нужному человеку. Так в аккаунте появляются рекомендации добавить в друзья конкретного пользователя: система предполагает, что вы могли вместе учиться, работать или отдыхать в одной компании.
За пределами соцсетей графы также позволяют получать признаки с высокой информативностью, а значит, строить высокоэффективные ML-модели для любых целей. Именно этим и занимались команды на хакатоне: создавали модель, которая на основе большого количества неструктурированных данных сможет точно определить пользователей с конкретными характеристиками, в частности со склонностью к благотворительности.
Разбираем решения
Подход №1: нестареющая классика
Решение представляет собой последовательную работу с тремя доменами данных: последовательностью пользовательских состояний, графами социальных связей и табличными данными.
При работе с табличными данными команда пошла по классическому пути и отправила все признаки в бустинг. Также построила дополнительные признаки, например агрегаты по группам. Эмпирически объединила некоторые фичи в группы, — например, брала все признаки, связанные с u1, и строила на них агрегаты.
Некоторые признаки — четность или нечетность i-фичей — команда сгенерировала самостоятельно, исходя из инсайтов данных. В конце смешала все признаки с помощью фреймворка LightAutoML, который умеет строить внутри различные стакинги, модели Catboost, линейные модели, что в целом положительно сказывается на итоговом качестве модели.
При работе с графами социальных связей для клиентов команда использовала два подхода:
- Для социального окружения оставила признаки по топу feature_importance, взяла агрегаты этих фичей по друзьям: min, max, mean.
- Получила эмбеддинги юзеров через SVD, нашла ближайших соседей, построила агрегаты на расстояниях и таргеты.
При работе с последовательностями также использовались два подхода:
- Последовательности воспринимались как текст: на них команда строила TF-DF, снижала размерность через SVD, а полученные эмбеддинги добавляла в качестве признаков в финальную модель.
- Команда строила эмбеддинги с помощью библиотеки фреймворков Pytorch-lifestream, которая позволяет строить эмбеддинги yf на последовательностях данных без учителя, и добавляла эти эмбеддинги в модель.
Комментарий Максима Кулаева, руководителя команды разработки CRM-моделей, VK Predict:
«Это решение команды „Лаборатория", и оно прекрасно своей простотой. В отличие от других команд, пытавшихся создать сложные нейросети и тяжелые модели, здесь классическое базовое решение, которое тем не менее отлично сработало.
Среди отдельных находок стоит отметить работу с каждым признаковым набором в отдельности. Аккуратный подход к отбору признаков: брали не все агрегаты, а только часть в зависимости от важности признаков. Векторизацию последовательностей графовых данных выполняли по переходам по доменам. И наконец, решение выявить нечто вроде среднего портрета друга каждого человека, посчитав агрегаты по всем друзьям каждого человека.
Все это помогло получить дополнительный прирост. И несмотря на то что общий Score у команды чуть ниже, они стали победителями благодаря простоте и проработанности решения».
Подход №2: визуализация графов и отбор лучшей конфигурации
В рамках анализа исходных данных команда отобрала по 200 самых популярных хешей и элементов из таблицы вещественных признаков. Посмотрели на графики их распределения у target 1 и target 0. Выяснили, какие признаки, отсутствующие у отрицательного класса, присутствуют у положительного, и наоборот. Однозначного распределения или прироста к Score это не дало, зато позволило определить, с какими именно данными ведется работа.
На этапе визуализации графов стала проявляться связь. Так, на одном графе длина была равна связи между хешами в соответствии с последовательностями. Команда взяла 10 самых популярных последовательностей, чтобы сократить время обучения модели. Нарисовала графы, но из-за небольшого количества хешей не стала отправлять их в модель.
На этапе разметки данных команда извлекла из последовательности пользователей 200 самых популярных хешей, добавила к ним самые популярные вещественные признаки и вещественные признаки среднего друга. Добавила количество друзей — это дало хороший прирост — и проанализировала признаки и связи между хешами в графах.
На этапе выбора модели проверили три варианта: Logistic Regression, CatBoost и XGB. На одинаковых данных CatBoost продемонстрировал лучший результат, поэтому команда выбрала его.
Финальный этап — подбор признаков, Loss-функций для выбора оптимальной конфигурации. В этой таблице все показатели по каждой модели:
Комментарий Максима Кулаева, руководителя команды разработки CRM-моделей, VK Predict:
«Команда LoLTeX взяла серебро благодаря внимательному отбору признаков: в домене их было много, но в работу пошли не все. Здесь также посчитали агрегаты, воспользовались CatBoost.
В отличие от первой команды, презентация была не настолько подробная. Зато есть отличная таблица с использованными методами, признаками и глубиной в зависимости от добавления функций. Она в том числе помогла команде найти лучшую конфигурацию: они просто методично записывали методы и полученное качество, а затем сравнили и выбрали лучшее решение.
Единственное, что вызвало вопросы, — использование стороннего решения Wolfram Alpha. C точки зрения соревнования это спорный ход. У команд разная экспертиза, именно поэтому приветствуются решения на общем для всех Python. Wolfram Alpha позволил получить хороший прирост, но LoLTeX использовала именно этот инструмент, потому что умела с ним работать, и это дало им определенное преимущество».
Подход № 3: матрица инцидентности и GNN
В качестве Baseline-решения команда обучила Catboost на фичах пользователя. Сделала Feature Selection, чтобы проанализировать зависимости доли объясненной дисперсии от количества признаков данных. Оказалось, что 200 признаков хорошо объясняют 80% дисперсии, поэтому оставили только их, тем самым снизив размерность дата-сетов.
В рамках Baseline команда добавила к признакам клиента усредненные признаки его друзей, что также улучшило Score.
При работе с графовыми данными построили граф для клиента на основе матрицы инцидентности состояний. В него команда добавила информацию о друзьях клиентов. Из матрицы инцидентности получила матрицу смежности, избавилась от мультиграфа, висячих ребер и мусора в данных.
На этапе построения графовой нейросети к GCN добавили Attention-блоки для правильной агрегации смежных вершин с текущей вершиной. Команда обучила GNN отдавать Non Classification, получила признаки и совместила их с признаками клиентов на Feature Selection, после чего обучили Catboost.
На следующем этапе команда взяла Sequence Matrix, где есть соответствие клиента и последовательности, матрицу клиента этого соответствия, и на их основе обучила TF-DF.
Снизила размерность TF-DF с помощью Truncated SVD и совместила полученные признаки с признаками Feature Selection. Использовала результат, чтобы обучить Catboost.
В итоге получилось три базовых алгоритма: Baseline, Catboost+GNN, Catboost+TF-DF. Признаки из них агрегируются. Полученный Score составил 62,5%. У алгоритмов, составлявших агрегацию, он равнялся приблизительно 60–61% — иначе говоря, агрегация позволила на 1,5% увеличить итоговую метрику.
Комментарий Максима Кулаева, руководителя команды разработки CRM-моделей, VK Predict:
«Это решение команды Kian. Главное отличие от других подходов — в использовании матрицы инцидентности и GNN, графовой нейронной сети. В остальном подход похож на предыдущие: аккуратный отбор признаков, использование TF-DF и SVD.
Отдельно стоит отметить, что на распределение мест на хакатоне влиял не только итоговый Score, но и качество презентации. Оба показателя у команд-лидеров были практически одинаковыми, разница составляла сотые доли. Так что с уверенностью можно сказать, что все три подхода с технической точки зрения являются успешными. Остальные факторы — это умение озвучить позицию и донести инновационность решения до членов жюри».
Что будет дальше с решениями: практическое применение
У каждого из предложенных решений большой потенциал развития. Их можно использовать в любой сложной системе, позволяющей хранить и получать доступ к знаниям о взаимодействующих объектах.
В проектах, прямо связанных с темой благотворительности, обогащение графами позволит повысить эффективность социальных кампаний. Можно создавать модели, которые помогут таргетировать рекламу и информационные объявления на конкретных пользователей — тех, кто с большей вероятностью готов участвовать в проекте. Это поможет увеличить отдачу от каждой акции и помочь большему числу людей.
Мы надеемся, что решения участников помогут вам создавать более сложные и интересные модели. Экспериментируйте, изучайте графы и приходите строить свои модели в Cloud ML Platform от VK Cloud. На платформе есть все для полного цикла работы с ML-моделями, а компоненты JupyterHub и MLflow предварительно настроены и интегрированы. Поэтому эксперименты можно начать очень быстро.
