От Науки о Данных
автор:Tobias Skovgaard Jepsen
Сборник "Сердце машины"
принимать участие:Компьютерщик ИИ, Дорога
Поскольку структура графа очень сложна и информативна, машинное обучение на графах — сложная задача. В этой статье описывается, как использоватьГраф сверточных сетейDeep Learning on Graphs (GCN) — мощная нейронная сеть, которая воздействует непосредственно на графы и использует их структурную информацию.
В этой статье будут представлены GCN и использованы примеры кода, чтобы проиллюстрировать, как информация распространяется через скрытые слои GCN. Читатели увидят, как GCN агрегируют информацию из предыдущих уровней и как этот механизм может генерировать полезные представления функций узлов в графе.
Что такое графовая сверточная сеть?
GCN — это очень мощный класс архитектур нейронных сетей для графических данных. Фактически, он настолько мощен, что даже случайно инициализированный двухуровневый GCN может генерировать полезные представления функций узлов в графовой сети. На рисунке ниже показано 2D-представление каждого узла, сгенерированного этой двухслойной GCN. Обратите внимание, что эти 2D-представления способны сохранять относительную близость узлов в графе даже без какого-либо обучения.
Более формально сверточная сеть графа (GCN) — это нейронная сеть, которая работает с данными графа. Учитывая граф G = (V, E), вход в GCN:
-
Матрица признаков X входного размера N × F⁰, где N — количество узлов в сети графа, а F⁰ — количество входных признаков на узел.
-
Матричное представление размерности N × N структуры графа, такое как матрица смежности A графа G. [1]
Следовательно, скрытый слой в GCN можно записать как Hⁱ = f(Hⁱ⁻¹, A)). где H⁰ = X, а f — правило распространения [1]. Каждый скрытый слой Hⁱ соответствует матрице признаков размером N × Fⁱ, и каждая строка в матрице является представлением признаков узла. На каждом уровне GCN агрегирует эту информацию, используя правило распространения f, чтобы сформировать признаки следующего уровня. Таким образом, функции становятся все более и более абстрактными в каждом последующем слое. В рамках этой схемы различные варианты GCN отличаются только выбором правила распространения f [1].
Простой пример правила распространения
Ниже в этой статье будет приведен пример простейшего правила распространения [1]:
f (Hⁱ, A) = σ (AHⁱWⁱ)
где Wⁱ — весовая матрица i-го слоя, а σ — нелинейная функция активации (например,ReLUфункция). Размер матрицы весов равен Fⁱ × Fⁱ⁺¹, то есть размер второго измерения матрицы весов определяет количество признаков в следующем слое. Если вы знакомы со сверточными нейронными сетями, вы обнаружите, что эта операция похожа на операцию фильтрации ядра свертки, поскольку эти веса распределяются между узлами в графе.
упрощать
Далее изучаем правила распространения на простейшем уровне. сделать:
-
я = 1, (ограничение f является функцией на матрице входных признаков)
-
σ - тождественная функция
-
Выберите веса (ограничения: AH⁰W⁰ =AXW⁰ = AX)
Другими словами, f(X, A) = AX. Это правило распространения может быть слишком упрощенным, и недостающие части будут добавлены позже в этой статье. Кроме того, AX эквивалентенМногослойный персептронвходной слой.
Пример простой диаграммы
Мы будем использовать приведенную ниже диаграмму в качестве простого примера:
Простой ориентированный граф.
Представление матрицы смежности указанного выше ориентированного графа, написанного в numpy, выглядит следующим образом:
A = np.matrix([ [0, 1, 0, 0], [0, 0, 1, 1], [0, 1, 0, 0], [1, 0, 1, 0]], dtype=float)скопировать кодДалее нам нужно извлечь функции! Мы генерируем два целочисленных признака для каждого узла на основе его индекса, что упрощает ручную проверку матричных операций позже в этой статье.
In [3]: X = np.matrix([ [i, -i] for i in range(A.shape[0]) ], dtype=float) XOut[3]: matrix([ [ 0., 0.], [ 1., -1.], [ 2., -2.], [ 3., -3.] ])скопировать кодПрименить правила распространения
Теперь мы построили граф с матрицей смежности A и набором входных признаков X. Давайте посмотрим, что произойдет, когда мы применим к нему правило распространения:
In [6]: A * XOut[6]: matrix([ [ 1., -1.], [ 5., -5.], [ 1., -1.], [ 2., -2.]]скопировать кодПредставление каждого узла (каждой строки) теперь представляет собой сумму характеристик его соседей! Другими словами, сверточные слои графа представляют каждый узел как совокупность его соседей. Вы можете проверить этот процесс расчета самостоятельно. Обратите внимание, что в этом случае узел n является соседом узла v, если существует ребро от v до n.
проблема
Возможно, вы заметили проблему:
-
Агрегированное представление узла не содержит собственных признаков! Представление представляет собой агрегацию признаков соседних узлов, поэтому только узлы с самопетлями будут включать свои собственные признаки в эту агрегацию [1].
-
Узел с большой степенью будет иметь большее значение в представлении признаков, а узел с малой степенью будет иметь меньшее значение. Это может привести к исчезновению градиентов или взрыву градиентов [1, 2], а также влияет на алгоритмы стохастического градиентного спуска (алгоритмы стохастического градиентного спуска часто используются для обучения таких чувствительных).
Далее в данной статье эти вопросы будут обсуждаться отдельно.
увеличить петлю
Чтобы решить первую проблему, мы можем напрямую добавить цикл [1, 2] к каждому узлу. В частности, это может быть достигнуто добавлением матрицы смежности A к единичной матрице I перед применением правила распространения.
In [4]: I = np.matrix(np.eye(A.shape[0])) IOut[4]: matrix([ [1., 0., 0., 0.], [0., 1., 0., 0.], [0., 0., 1., 0.], [0., 0., 0., 1.] ])In [8]: A_hat = A + I A_hat * XOut[8]: matrix([ [ 1., -1.], [ 6., -6.], [ 3., -3.], [ 5., -5.]])скопировать кодТеперь, поскольку каждый узел является своим собственным соседом, каждый узел также включает свои собственные признаки в процессе суммирования признаков соседних узлов!
Нормализуйте представление объекта
Представление признаков нормализуется по степени узлов путем преобразования матрицы смежности A путем умножения ее на обратную матрицу степени D. Поэтому наши упрощенные правила распространения таковы:
f(X, А) = D⁻¹AX
Давайте посмотрим, что произошло. Сначала мы вычисляем матрицу степеней узлов.
In [9]: D = np.array(np.sum(A, axis=0))[0] D = np.matrix(np.diag(D)) DOut[9]: matrix([ [1., 0., 0., 0.], [0., 2., 0., 0.], [0., 0., 2., 0.], [0., 0., 0., 1.] ])скопировать кодПрежде чем применять правило распространения, давайте посмотрим, что произойдет, когда мы преобразуем матрицу смежности.
до трансформации
A = np.matrix([ [0, 1, 0, 0], [0, 0, 1, 1], [0, 1, 0, 0], [1, 0, 1, 0]], dtype=float)скопировать кодпосле преобразования
In [10]: D**-1 * AOut[10]: matrix([ [0. , 1. , 0. , 0. ], [0. , 0. , 0.5, 0.5], [0. , 0.5, 0. , 0. ], [0.5, 0. , 0.5, 0. ]])скопировать кодМожно заметить, что вес (значение) каждой строки в матрице смежности делится на степень узла, соответствующего этой строке. Затем мы применяем правило распространения к преобразованной матрице смежности:
In [11]: D**-1 * A * XOut[11]: matrix([ [ 1. , -1. ], [ 2.5, -2.5], [ 0.5, -0.5], [ 2. , -2. ] ])скопировать кодПолучите представление узла, соответствующее среднему признаку соседних узлов. Это связано с тем, что веса (преобразованной) матрицы смежности соответствуют весам взвешенной суммы признаков соседних узлов. Вы можете проверить этот результат самостоятельно.
Интегрировать
Теперь мы объединим трюки с циклом и нормализацией. Кроме того, мы повторно введем соответствующие веса ифункция активацииоперация.
добавить вес
Первое, что нужно сделать, это применить веса. Обратите внимание, что здесь D_hat — это матрица степеней, соответствующая A_hat = A + I, то есть матрица степеней матрицы A с вынужденными петлями.
In [45]: W = np.matrix([ [1, -1], [-1, 1] ]) D_hat**-1 * A_hat * X * WOut[45]: matrix([ [ 1., -1.], [ 4., -4.], [ 2., -2.], [ 5., -5.] ])скопировать кодЕсли мы хотим уменьшить размер представления выходных признаков, мы можем уменьшить размер весовой матрицы W:
In [46]: W = np.matrix([ [1], [-1] ]) D_hat**-1 * A_hat * X * WOut[46]: matrix([[1.], [4.], [2.], [5.]])скопировать кодДобавить функцию активации
В этой статье принято решение сохранить размер представления функции и применить функцию активации ReLU.
In [51]: W = np.matrix([ [1, -1], [-1, 1] ]) relu(D_hat**-1 * A_hat * X * W)Out[51]: matrix([[1., 0.], [4., 0.], [2., 0.], [5., 0.]])скопировать кодЭто полный скрытый слой с матрицей смежности, входными функциями, весами и функцией активации!
Применение в реальных сценариях
Наконец, мы применяем сверточную сеть графа к реальному графу. Эта статья покажет читателю, как генерировать представления функций, упомянутые выше.
Закари Каратэ Клуб
Zachary Karate Club — это широко используемая социальная сеть, в которой узлы представляют членов клуба карате, а ребра представляют отношения между членами. Когда в том году Закари исследовал клуб карате, конфликт между администраторами и инструкторами привел к тому, что клуб разделился на две части. На рисунке ниже показано графическое представление сети, где узлы помечены в соответствии с тем, к какой части клуба принадлежит узел, где «A» и «I» представляют узлы, принадлежащие лагерям администратора и преподавателей соответственно.
Zachary Karate Club Figure Network
Создать контекстную сеть
Далее мы построим графовую сверточную сеть. На самом деле мы не обучаем сеть, а просто инициализируем ее случайным образом, что приводит к представлениям функций, которые мы видели в начале этой статьи. Мы будем использовать networkx, у которого есть графическое представление Zachary's Karate Club, которое можно легко реализовать. Затем мы вычислим матрицы A_hat и D_hat.
from networkx import to_numpy_matrixzkc = karate_club_graph()order = sorted(list(zkc.nodes()))A = to_numpy_matrix(zkc, nodelist=order)I = np.eye(zkc.number_of_nodes())A_hat = A + ID_hat = np.array(np.sum(A_hat, axis=0))[0]D_hat = np.matrix(np.diag(D_hat))скопировать кодДалее мы случайным образом инициализируем веса.
W_1 = np.random.normal( loc=0, scale=1, size=(zkc.number_of_nodes(), 4))W_2 = np.random.normal( loc=0, size=(W_1.shape[1], 2))скопировать кодДалее мы сложим слои GCN. Здесь мы используем только единичную матрицу в качестве представления признаков, т. е. каждый узел представлен как категориальная переменная с горячим кодированием.
def gcn_layer(A_hat, D_hat, X, W): return relu(D_hat**-1 * A_hat * X * W)H_1 = gcn_layer(A_hat, D_hat, I, W_1)H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)output = H_2скопировать кодДалее мы извлекаем представления признаков.
feature_representations = { node: np.array(output)[node] for node in zkc.nodes()}скопировать кодВидите ли, такая характеристика может прекрасно разделить два сообщества Zachary Karate Club. На данный момент мы даже не начали обучать модель!
Характерное представление узлов в графовой сети Zachary Karate Club.
Следует отметить, что веса, инициализированные случайным образом по оси x или оси y, скорее всего, будут равны 0 в этом примере из-за функции ReLU, поэтому для создания приведенного выше графика требуется несколько итераций случайной инициализации.
Эпилог
В этой статье представлено общее введение в графовые сверточные сети и показано, как представление признаков каждого узла уровня в GCN строится на основе агрегации его соседних узлов. Читатели могут узнать, как создавать эти сети с помощью numpy и насколько они эффективны: даже случайно инициализированный GCN может разделить сообщества в сети Zachary Karate Club.
использованная литература
[1] Blog post on graph convolutional networks by Thomas Kipf.
[2] Paper called Semi-Supervised Classification with Graph Convolutional Networks by Thomas Kipf and Max Welling.
Исходная ссылка: https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780
Эта статья составлена для сердца машины,Для перепечатки, пожалуйста, свяжитесь с этим официальным аккаунтом для авторизации .
✄------------------------------------------------
Присоединяйтесь к сердцу машины (штатный репортер/стажер): hr@jiqizhixin.com
Чтобы внести свой вклад или получить покрытие:content@jiqizhixin.com
Реклама и деловое сотрудничество: bd@jiqizhixin.com