Вложения — это представления данных в векторном пространстве. С появлением глубокого обучения они стали де-факто этапом предварительной обработки в большинстве приложений машинного обучения. То же самое справедливо и для графиков. Нам нужно встроить вершины графов в низкоразмерное векторное пространство, прежде чем мы сможем использовать их в моделях глубокого обучения.

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

Так какой же самый простой способввстроить неориентированный граф G(V, E), где V — набор вершин, а E = {(u, v) : u, v ∈ V} установлено ли ребро? Оказывается, простой градиентный спуск может завести нас очень далеко (эти идеи очень похожи на идеи, используемые для завершения матрицы).

Вот алгоритм:

  • Выберите размерность вложения m = O(log(|V|))
  • Произвольно инициализируйте записи встраивания x(u), используя i.i.d. нулевое среднее гауссово распределение дисперсии 1/m
  • Наложите следующие ограничения на встраивание, используя набор ребер E:

  • Наложите дополнительное ограничение, согласно которому норма x(u) = 1 для всех u в V

Это приводит к следующему простому алгоритму: мы предполагаем, что вершины графа представлены целыми числами от 0 до |V| - 1.

import numpy as np
# load edges
edges = [(u, v) for all edges in E]
# number of vertices
n = max(max(u, v) for u, v in edges) + 1

Задайте параметры алгоритма встраивания:

alpha = 0.05 # step size
num_epochs = 10 # number of epochs
m = 40 # dimensionality of the embedding

Сгенерируйте вложение, используя градиентный спуск, минимизировав следующую функцию стоимости:

Давайте определим вспомогательную функцию update(u, v, target) для выполнения градиентного спуска:

def update_impl(u, v, residual):
    # gradient descent with step size alpha
    embed[u, :] -= 2 * alpha * residual * embed[v, :]
    # ensure that the norm of embed[u, :] is 1
    embed[u, :] /= np.linalg.norm(embed[u, :])

def update(u, v, target):
    cosine_similarity = embed[u, :].dot(embed[v, :])
    residual = cosine_similarity - target
    update_impl(u, v, residual)
    update_impl(v, u, residual)

С помощью приведенной выше вспомогательной функции алгоритм выглядит следующим образом:

# random initial guess of embedding
embed = np.random.randn(n, m) / np.sqrt(m)
# train embedding
for epoch in range(num_epochs):
    for u, v in edge_list:
        update(u, v, 1)
        # random node in graph
        k = np.random.randint(0, n, 1)[0]
        update(u, k, 0)
        update(v, k, 0)

Вот и все! Простая модификация состоит в том, чтобы изменить функцию стоимости так, чтобы случайная вершина выбиралась с вероятностью, пропорциональной степени узла. Этого можно добиться путем выборки случайного ребра и использования одной из двух вершин, соответствующих этому ребру, в качестве вершины k.

# random initial guess of embedding
embed = np.random.randn(n, m) / np.sqrt(m)
# train embedding
for epoch in range(num_epochs):
    for u, v in edge_list:
        update(u, v, 1)
        # pick random edge from the graph
        p = np.random.randint(0, len(edge_list), 1)[0]
        r, l = edge_list[p]
        # pick one of the vertices of the random edge
        k = r if np.random.randn(1) < 0 else l
        # use as negative sample
        update(u, k, 0)
        update(v, k, 0)

В некотором смысле, это основная идея статьи Node2Vec. В этой статье вместо простой функции стоимости, основанной на косинусном сходстве, как здесь, авторы оптимизируют другую функцию стоимости. Они также используют случайный переход к выборке (u, v) пар, которые не обязательно находятся в списке ребер E, но очень близки по график. Это расширение случайного блуждания также применимо к простому методу, представленному выше.

Для тех, кто интересуется линейной алгеброй, есть другие способы получения хороших вложений графов, основанные на Анализе главных компонентов (АПК).Алгоритм, который намного быстрее, чем АПК для больших графики — FastEmbed [python] [spark].