Варианты использования, позволяющие максимально эффективно использовать луч, расчет графика

Сегодня я хотел бы оставить базовую структуру ray и рассмотреть некоторые приложения. Одним из них является вычисление графов.

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

(📹: https://www.youtube.com/watch?v=7tMntN9kQbA)

1–1. Что такое вычисление графа?

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

1–2. Пример вычисления графа: встраивание графа

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

Важность внедрения графов:

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

1–3. Deepwalk и егораспределенная природа

Знаешь ли ты Дипуок? Это алгоритм, который использует случайные блуждания для исследования графов. Случайное блуждание — это процесс, в котором вы начинаете с определенного узла графа и неоднократно случайным образом перемещаетесь к соседним узлам. Этот процесс проявляет определенные распределенные свойства. Вот краткое описание алгоритма Deepwalk.

Шаг 1: Генерация случайных блужданий

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

Шаг 2: Генерация последовательности

Получите последовательности узлов, сгенерированные случайными блужданиями. Каждое случайное блуждание представляется как последовательность узлов, и эти последовательности используются в качестве обучающих данных.

Шаг 3. Обучение модели Skip-gram

Используйте полученные последовательности узлов для обучения модели нейронной сети под названием Skip-gram. Модель Skip-gram выполняет задачу прогнозирования окружающих узлов данного узла. Этот процесс приводит к изучению вложений узлов.

Шаг 4: Получение вложений

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

1–3–1. Независимость:

Каждое случайное блуждание независимо, то есть одно случайное блуждание не влияет на другие. Это математическое свойство, указывающее вероятностную независимость. С математической точки зрения, рассмотрим набор узлов V (набор узлов в графе) и подумаем о случайном блуждании, начинающемся с определенного узла v. Это случайное блуждание моделируется как случайный процесс, в котором вы случайным образом выбираете следующий узел. Этот случайный процесс известен как цепь Маркова и представлен матрицей перехода P, которая описывает вероятности перехода от одного узла к другому.

Вот несколько примеров уравнений для матрицы перехода P:

  1. P(i, j) — вероятность перехода из вершины i в вершину j
  2. P(i, j) ≥ 0: вероятности перехода неотрицательны.
  3. Σ_j P(i, j) = 1: сумма вероятностей в каждой строке равна 1.

Эти уравнения показывают, что движение от одного узла к другому является вероятностным и независимым.

1–3–2. Параллелизм

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

2–1. Пример реализации Deepwalk с Ray

Вот пример фрагмента кода, который демонстрирует, как использовать DeepWalk с Ray для распределения обучения по нескольким узлам:

import ray
import numpy as np
from deepwalk import DeepWalk

# Initialize Ray
ray.init()

# Load graph data
graph_data = load_graph_data()

# Number of graph nodes
num_nodes = len(graph_data)

# Distribute data to Ray Object store
graph_data_refs = ray.put(graph_data)

# Train the DeepWalk model
@ray.remote
def train_deepwalk(graph_data_ref):
    deepwalk_model = DeepWalk()
    deepwalk_model.fit(graph_data_ref)
    return deepwalk_model

# Train models with multiple worker node in parallel.
num_workers = 4
models = ray.get([train_deepwalk.remote(graph_data_refs) for _ in range(num_workers)])

# integrate the models
final_model = aggregate_models(models)

Я хотел бы позже сравнить скорость вычислений в случаях с Рэем и без Рэя.