Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 118-125

1. ВВЕДЕНИЕ

Под влиянием успеха глубоких нейронных сетей на данных со структурой в виде сетки (изображения) стали появляться работы, посвященные поиску операции свертки для данных с графовой структурой. Такие данные представлены не только признаковыми описаниями объектов $X$, но и графом $G$, вершинами которого являются объекты выборки. Такие новые типы сверток были успешно применены к задачам распознавания и предсказания позы человека [1], задачам классификации вершин графов цитирований и социальных сетей [2]. Они имеют потенциал в обработке категориальных признаков [3] и в задаче многоклассовой классификации [4].

Существует лишь несколько работ, посвященных обучению графовых нейронных сетей на табличных данных, где признаки, как правило, имеют очень разную природу и масштаб. Методы, основанные на решающих деревьях, обычно обладают наилучшим качеством обработки таких данных. Недавно появился целый ряд новых методов, которые позволяют обучать ансамбли и бустинги решающих деревьев с помощью методов распространения меток и обратного распространения ошибки. Эти новые модели позволяют получить многослойное представление табличных данных, которое, согласно нашему предположению, может быть эффективно использовано в качестве входных данных для графовых сверток. Более того, вышеупомянутые модели и графовые нейронные сети могут быть обучены совместно и, таким образом, быть более эффективными. Мы изучаем эти подходы и предлагаем модификации для повышения их качества и вычислительной эффективности. Наш основной вклад заключается в следующем:

$ \bullet $ Мы обобщаем модель [7], делая бустинг многомерным. Затем мы изучаем влияние предобучения этого бустинга на общую производительность комбинированной модели. Мы также предлагаем процедуру предобучения для нашей обобщенной модели, которая позволяет ей быстрее сходиться к меньшим значениям функции потерь.

$ \bullet $ Предлагаем дистилляцию многомерного бустинга, которая позволяет контролировать потребление памяти и время итераций обучения без снижения качества.

$ \bullet $ Проводим эксперименты с совместным обучением графовой сверточной сети и ряда недавно предложенных дифференцируемых моделей на основе деревьев решений. Мы оцениваем полученные решения в задачах классификации вершин графа в индуктивных и трансдуктивных постановках.

2. ПРЕДЫДУЩИЕ РАБОТЫ

Работа [7] изучает проблему применения графовых нейронных сетей к разнородным табличным данным. Авторы совместно обучают градиентный бустинг (GBDT) и графовую нейронную сеть. Основная идея состоит в том, чтобы рассматривать графовую нейронную сеть как сложную функцию потерь для модели GBDT. Такой подход продемонстрировал значительный прирост качества и является нашим основным бейзлайном.

В работе [5] описано многослойное обобщение градиентного бустинга (MGBDT). Данная модель обучается не алгоритмом обратного распространения ошибки, а с помощью процедуры обратного распространения целевых переменных [11]. Данная процедура предполагает, что для каждого слоя обучается пара моделей (см. рис. 1). Модель ${{F}_{i}}$ учится предсказывать входы для следующего слоя $i + 1$ по выходам предшествующего ей $i - 1$, модель ${{G}_{i}}$ учит обратное ${{F}_{i}}$ отображение.

Модель MGBDT позволяет получать эффективные для решения задач векторные представления на основе табличных данных, превосходя по качеству полносвязные нейронные сети. Однако это решение имеет ряд недостатков. Одним из которых является низкая эффективность использования памяти, поскольку каждый выход слоя фактически является отдельной моделью GBDT. Другой проблемой является увеличение времени обучения с количеством итераций. Для обычной модели GBDT мы можем сохранить ее выходные данные и использовать их для быстрого и эффективного обновления целевой переменной. Но когда мы рассматриваем многослойную модель, эта схема становится невозможной, поскольку входные данные для всех слоев, кроме самого первого, меняются с каждой итерацией.

Модель NODE, описанная в [6], обучается на табличных данных с помощью обратного распространения ошибки и таким образом лишена основных недостатков многослойного бустинга. Каждый слой такой модели представлен дифференцируемой версией ансамбля решающих деревьев. Обычное решающее дерево невозможно оптимизировать с помощью градиентного спуска, так как выборы признака, порога для каждого решающего правила не являются дифференцируемыми операциями. Были предложены аналоги таких операций на основе entmax [12] – разряженной версии softmax.

Широко известные модели глубинного обучения показывают отличные результаты на объектах, представляющих собой последовательности или простые сетки (например изображения). В то же время существует множество данных, представленных в виде графов. Главные отличия таких данных в том, что у каждого объекта-вершины может быть произвольное количество связанных с ним объектов-вершин, и на этом множестве нет никакого порядка. Примером таких данных могут служить социальные сети, статьи или посты с цитированиями и ссылками, молекулы. Вышеупомянутые особенности не позволяют с легкостью применить одну из основных операций – свертку.

Существует два основных подхода к введению операции графовой свертки:

$ \bullet $ Спектральный подход – изначально был основан на спектральном разложении матрицы Лапласа графа [21]. Такое разложение служит аналогом разложения Фурье, из которого по теореме о свертке следует и определение такой операции на графе.

$ \bullet $ Пространственные подходы вводят операцию свертки следующим образом:

здесь $x_{v}^{t}$ – скрытое представление вершины $v$ на слое t, ${\text{COMBIN}}{{{\text{E}}}^{t}}$, ${\text{AGGREGAT}}{{{\text{E}}}^{t}}$ – дифференцируемые операции, $E$ – множество ребер графа.

В данной работе нас больше интересует второй подход, так как он позволяет проводить стохастическое обучение. В частности, в наших экспериментах мы используем модель GAT (Graph Attention Network) [14]. В этом случае указанные операции принимают следующий вид:

здесь ${{\alpha }_{{i.j}}}$ – коэффициенты, полученные с помощью механизма self-attention [22]. Еще одно преимущество пространственного подхода – это возможность обучения по подграфам [13]. Операция сэмплирования окрестностей вершин является регуляризатором при индуктивном обучении, позволяющем модели лучше адаптироваться к меняющимся во времени графовым структурам.

3. ПРЕДЛОЖЕННЫЙ МЕТОД

В нашей работе мы пытаемся улучшить алгоритм, описанный в [7].Один из наших экспериментов (табл. 2, 3, 4) показал, что качество улучшается, когда графовая сеть принимает только выходы GBDT без исходных представлений. Мы предполагаем, что необработанные табличные данные (даже нормализованные) являются плохими входами для оператора свертки графа. С другой стороны, графовая модель, которая опирается только на приближение целевой переменной, немного наивна и может быть дополнена более сложным скрытыми представлениями вершин графа.

Мы сосредоточимся на использовании моделей [5, 6], чтобы обучить отображение табличных данных в пространство, в котором работает графовая свертка. Чтобы снизить вычислительную сложность и ускорить процесс обучения, мы предложили процедуры предобучения и дистилляции.

Один из важных аспектов модели BGNN [7] –это предобучение бустинга. Первые несколько итераций алгоритм учится предсказывать целевую переменную, затем выходы бустинга подаются на вход графовой сети и в дальнейшем обучении напрямую с целевой переменной никак не связаны. Для модели MGBDT [5] мы также изучаем влияние предобучения на качество финального предсказания. Однако в нашем алгоритме мы желаем отказаться от ограничения на размерность пространства, над которым действует графовая свертка. В таком случае мы сравниваем два варианта предобучения:

1. Добавление полносвязного слоя, который позволил бы модели учиться на целевую переменную.

2. Добавление к выходу размерности, которая приближает целевую переменную.

Ограничениями модели MGBDT, как уже говорилось, являются использование большого количества памяти и все время увеличивающееся время обучения. Наш подход, который мы называем дистилляцией, заключается в периодическом обновлении модели: новая модель инициализируется так, чтобы как можно лучше приближать предшествующую, при этом новая модель легче – в ней меньше регрессионных деревьев. Так как отображение из табличных данных постепенно обновляется, старые регрессионные деревья с первых итераций обучения уже не вносят ощутимый вклад в предсказание. Новые деревья исправляют ошибку старых регрессоров, адаптируя их выходы под постоянно меняющиеся представления вершин графа, над которыми работает графовая свертка.

Наш подход устраняет эту неэффективность, появляющуюся из-за постоянного изменения целевых переменных градиентного бустинга. Новая модель сходится к сравнимым результатам за меньшее время и без неограниченного потребления памяти.

4. ЭКСПЕРИМЕНТЫ

Эксперименты проводятся на нескольких наборах данных¹¹:

1. House [8] – набор данных, в котором каждая вершина – это недвижимость, ребра соединяют находящиеся рядом элементы недвижимости, целевая переменная – цена недвижимости.

2. County [9] – данные о выборных округах. Каждая вершина – это округ, ребрами соединены такие округи, которые имеют общую границу. Целевая переменная – уровень безработицы.

3. VK [10] – данные социальной сети. Целевая переменная – возраст пользователей.

В каждом нашем эксперименте мы оцениваем метрику качества – среднеквадратичную ошибку регрессии RMSE на кросс-валидации с помощью выборочных среднеквадратичного отклонения и матожидания, подсчитанных на 5 подвыборках каждого набора данных. Все графики мы строим на первой валидационной подвыборке.

Из табл. 1 следует, что характеристики графов рассмотренных наборов данных сильно различаются. Особенно сильно отличается распределение степеней вершин. Это может сильно отразиться на результатах обучения с сэмплированием подграфа.

Для начала мы изучаем влияние добавления ко входам графовой свертки необработанных табличных данных. Мы использовали несколько видов графовых нейронных сетей, чтобы убедиться, что эффект не зависит от архитектуры: AGNN (графовая сеть с механизмом внимания) [16], APPNP (архитектура, берущая за основу персонализированный алгоритм случайного блуждания) [17], GAT (еще один подход на основе механизма внимания) [14], GCN (графовая сверточная сеть) [18].

Результаты можно увидеть в табл. 2, 3, 4. Очевидно, что графовая свертка не способна хорошо обрабатывать табличные данные и на самом деле лучшее качество получается на единственном признаке: предсказании модели, основанной на решающих деревьях.

Таблица 5 и рис. 2 показывают, что предобучение оказывает большое влияние на сходимость обеих моделей. Результаты обеих процедур предобучения продемонстрировали сопоставимый эффект, хотя предобучение одного из выходных параметров в среднем имеет несколько меньшее значение функции потерь в среднем. Мы предполагаем, что графовой модели может потребоваться больше информации о соседних вершинах графа, чем просто целевая метка, и эта информация фиксируется остальными выходами. Предобучение с помощью дополнительного линейного слоя накладывает ограничение на выходы модели GBDT: они фиксируют только информацию о целевых метках.

Таблица 6 содержит значения RMSE как для дистиллированной, так и для обычной версий модели MGBDT. Дистилляция происходит каждые 10 эпох. Рисунок 3 показывает, что процедура дистилляции практически не влияет на вид кривой функции потерь.

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

5. РЕЗУЛЬТАТЫ

В данной работе мы проводим эксперименты для двух сценариев практического применения:

1. Индуктивная постановка предполагает, что графовые структуры на обучающей и тестовой выборке отличны. Это значит, что во время обучения в операции графовой свертки участвует не вся окрестность вершины, а только те вершины, которые присутствуют в тренировочной выборке.

2. Трансдуктивная, наоборот, предполагает наличие общей структуры, для обеих выборок. То есть во время обучения модель использует все вершины графа в операции свертки.

В индуктивной постановке мы также рассматриваем обучение с регуляризацией – сэмплированием подграфов. Модель с NODE обучается таким алгоритмом во всех экспериментах, так как иначе требуется слишком много вычислительных ресурсов.

Для каждой модели мы подбираем гиперпараметры по сетке:

$ \bullet $ размерности: [4, 8]

$ \bullet $ количество слоев: [1, 2]

$ \bullet $ вероятность зануления весов: [0, 0.2]

Глубина²² деревьев для всех моделей равна 6, для модели NODE число деревьев на каждом слое берем равным 128, а размерность листового вектора 3.

Решения на основе градиентного бустинга в целом показали сравнимые результаты. К сожалению обучение модели NODE слишком ресурсоемко, и мы ограничили ее обучение 200 эпох вместо 5000 как для полносвязной сети. По характеру сходимости кривой обучения (рис. 4) алгоритм ведет себя скорее как полносвязная нейросеть, чем метод, основанный на решающих деревьях. Однако можно заметить, что даже с учетом того что модель NODE учится на подграфах, она сходится гораздо быстрее, чем другие полностью дифференцируемые методы (GAT, FCNN, FCNN-GNN).

По итогам обоих экспериментов, среди MGBDT моделей, лучше всего себя показали однослойные. Однако результаты из табл. 6 говорят, что многослойные модели потенциально могут показать еще лучшее качество при увеличении размерности слоев. Важно заметить, что каждый слой в MGBDT, кроме первого, имеет ограничение в виде необходимости учить обратимое отображение. Таким образом и можно объяснить худший по сравнению с однослойными моделями результат. При усложнении таких отображений, увеличении размерностей слоев, качество работы модели улучшается, а дистилляция помогает разумно ограничить необходимые вычислительные ресурсы.

На рис. 6 цветом показаны значения целевой переменной и того выхода скрытого слоя моделей MGBDT и BGNN, по которому шло предобучение. Хотя мы увеличили размеры выходного слоя и никак не ограничивали значения предобученной размерности в дальнейшем процессе настройки модели, тем не менее, как и в работе [7], предобученная размерность может быть интерпретирована как сглаженная версия целевой переменной. Координаты (x, y) в каждом случае равны результату работы алгоритма t-SNE [15], над выходами предпоследнего слоя графовой сети.

6. ЗАКЛЮЧЕНИЕ

В этой работе мы предложили новые модели для обучения на табличных данных. Наши решения используют преимущества совместного обучения решающих деревьев и графовых нейронных сетей. В отличие от [7], мы используем многослойные представления табличных данных высокой размерности и предлагаем эффективные с точки зрения вычислений способы их получения. Эксперименты на [8–10] показали, что наши алгоритмы достигают результатов, сопоставимых с последними современными моделями. Мы хотим провести дальнейшие исследования в направлении сокращения вычислительных ресурсов путем дистиллирования решающих деревьев с помощью полносвязных сетей. Это помогло бы контролировать потребление памяти без периодической реинициализации. Мы также считаем, что наш подход более перспективен в отношении трансферного обучения, поскольку его размерность не сильно зависит от целевой переменной для текущей задачи, но необходимы дальнейшие исследования, чтобы доказать это.