Это вторая из серии публикаций о функциях прогнозирования ссылок, которые недавно были добавлены в Библиотеку графических алгоритмов Neo4j.

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

В этом посте мы применим полученные знания к набору данных цитирования. Мы собираемся прогнозировать будущее соавторство с помощью scikit-learn и алгоритмов прогнозирования ссылок.

Эми Ходлер и я показали, как применять подходы, описанные в этом посте, на встрече Neo4j Online на прошлой неделе, так что вы также можете посмотреть видео.

Если вы хотите получить письменную версию, приступим!

Импортировать набор данных цитирования

Мы собираемся использовать данные из Сети цитирования DBLP, которая включает данные цитирования из различных академических источников. Я написал сообщение в блоге, объясняющее как импортировать полный набор данных, но в этом посте мы собираемся сосредоточиться на данных нескольких конференций по разработке программного обеспечения.

Мы можем импортировать это подмножество данных, выполнив следующие операторы Cypher. Вы можете запустить их все за один раз, если в браузере Neo4j включен редактор нескольких операторов:

// Create constraints
CREATE CONSTRAINT ON (a:Article) ASSERT a.index IS UNIQUE;
CREATE CONSTRAINT ON (a:Author) ASSERT a.name IS UNIQUE;
CREATE CONSTRAINT ON (v:Venue) ASSERT v.name IS UNIQUE;
// Import data from JSON files using the APOC library
CALL apoc.periodic.iterate(
  'UNWIND ["dblp-ref-0.json", "dblp-ref-1.json", "dblp-ref-2.json", "dblp-ref-3.json"] AS file
   CALL apoc.load.json("https://github.com/mneedham/link-prediction/raw/master/data/" + file)
   YIELD value WITH value
   RETURN value',
  'MERGE (a:Article {index:value.id})
   SET a += apoc.map.clean(value,["id","authors","references", "venue"],[0])
   WITH a, value.authors as authors, value.references AS citations, value.venue AS venue
   MERGE (v:Venue {name: venue})
   MERGE (a)-[:VENUE]->(v)
   FOREACH(author in authors | 
     MERGE (b:Author{name:author})
     MERGE (a)-[:AUTHOR]->(b))
   FOREACH(citation in citations | 
     MERGE (cited:Article {index:citation})
     MERGE (a)-[:CITED]->(cited))', 
   {batchSize: 1000, iterateList: true});

На следующей диаграмме показано, как выглядят данные после импорта в Neo4j:

Построение графа соавторов

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

Следующее утверждение Cypher создает отношенияCO_AUTHOR между авторами, которые сотрудничали по крайней мере над одной статьей:

MATCH (a1)<-[:AUTHOR]-(paper)-[:AUTHOR]->(a2:Author)
WITH a1, a2, paper
ORDER BY a1, paper.year
WITH a1, a2, collect(paper)[0].year AS year, 
     count(*) AS collaborations
MERGE (a1)-[coauthor:CO_AUTHOR {year: year}]-(a2)
SET coauthor.collaborations = collaborations;

Мы создаем только одну CO_AUTHOR связь между авторами, которые сотрудничали, даже если они работали над несколькими статьями. Мы создаем несколько свойств для этих отношений:

  • свойство year, указывающее год публикации первой статьи, над которой работали авторы.
  • свойство collaborations, которое указывает, сколько статей, над которыми работали авторы,

Теперь, когда у нас есть диаграмма соавторов, нам нужно выяснить, как мы собираемся прогнозировать будущее сотрудничество между авторами.

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

Наборы данных для обучения и тестирования

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

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

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

Но на какой год мы должны разделиться? Давайте посмотрим на распределение первого года сотрудничества соавторов:

Похоже, 2006 год будет хорошим годом для разделения данных, потому что он даст нам разумный объем данных для каждого из наших подграфов. Мы возьмем все соавторства с 2005 года и ранее в качестве нашего графика обучения, а все, начиная с 2006 года, в качестве тестового графика.

Давайте создадим явные отношения CO_AUTHOR_EARLY и CO_AUTHOR_LATE на нашем графике на основе этого года. Следующий код создаст для нас эти отношения:

Подграфик обучения

MATCH (a)-[r:CO_AUTHOR]->(b) 
WHERE r.year < 2006
MERGE (a)-[:CO_AUTHOR_EARLY {year: r.year}]-(b);

Тестовый подграф

MATCH (a)-[r:CO_AUTHOR]->(b) 
WHERE r.year >= 2006
MERGE (a)-[:CO_AUTHOR_LATE {year: r.year}]-(b);

Это разделение оставляет у нас 81 096 отношений на раннем графике и 74 128 на последнем. Это 52–48 человек. Это более высокий процент значений, чем обычно в нашем тестовом графике, но это должно быть нормально.

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

Как это часто бывает в задачах прогнозирования ссылок, отрицательных примеров гораздо больше, чем положительных. Максимальное количество отрицательных примеров равно:

# negative examples = (# nodes)² - (# relationships) - (# nodes)

то есть количество узлов в квадрате минус отношения, которые имеет граф, минус отношения между собой.

Вместо того, чтобы использовать почти все возможные пары, мы будем использовать пары узлов, которые находятся на расстоянии 2–3 прыжков друг от друга. Это даст нам гораздо более управляемый объем данных для работы.

Мы можем сгенерировать эти пары, выполнив следующий запрос:

MATCH (author:Author)
WHERE (author)-[:CO_AUTHOR_EARLY]-()
MATCH (author)-[:CO_AUTHOR_EARLY*2..3]-(other)
WHERE not((author)-[:CO_AUTHOR_EARLY]-(other))
RETURN id(author) AS node1, id(other) AS node2

Этот запрос возвращает 4 389 478 отрицательных примеров по сравнению с 81 096 положительных примеров, что означает, что у нас в 54 раза больше отрицательных примеров.

Таким образом, у нас все еще есть большой дисбаланс классов, что означает, что модель, предсказывающая, что каждая пара узлов не будет иметь связи, будет очень точной.

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

py2neo, панды, scikit-learn

В оставшейся части поста мы будем работать на Python с библиотеками py2neo, pandas и scikit-learn.

Драйвер py2neo позволяет специалистам по обработке данных легко интегрировать Neo4j с инструментами в экосистеме Python Data Science. Мы будем использовать эту библиотеку для выполнения запросов Cypher к Neo4j.

pandas - это библиотека с открытым исходным кодом под лицензией BSD, предоставляющая высокопроизводительные, простые в использовании структуры данных и инструменты анализа данных для языка программирования Python.

scikit-learn - популярная библиотека машинного обучения. Мы будем использовать эту библиотеку для построения нашей модели машинного обучения.

Мы можем установить эти библиотеки из PyPi:

pip install py2neo==4.1.3 pandas sklearn

После установки этих библиотек мы импортируем необходимые пакеты и создадим соединение с базой данных:

from py2neo import Graph
import pandas as pd
graph = Graph("bolt://localhost", auth=("neo4j", "neo4jPassword"))

Сборка обучающего и тестового наборов

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

# Find positive examples
train_existing_links = graph.run("""
MATCH (author:Author)-[:CO_AUTHOR_EARLY]->(other:Author)
RETURN id(author) AS node1, id(other) AS node2, 1 AS label
""").to_data_frame()
# Find negative examples
train_missing_links = graph.run("""
MATCH (author:Author)
WHERE (author)-[:CO_AUTHOR_EARLY]-()
MATCH (author)-[:CO_AUTHOR_EARLY*2..3]-(other)
WHERE not((author)-[:CO_AUTHOR_EARLY]-(other))
RETURN id(author) AS node1, id(other) AS node2, 0 AS label
""").to_data_frame()
# Remove duplicates
train_missing_links = train_missing_links.drop_duplicates()
# Down sample negative examples
train_missing_links = train_missing_links.sample(
    n=len(train_existing_links))
# Create DataFrame from positive and negative examples
training_df = train_missing_links.append(
    train_existing_links, ignore_index=True)
training_df['label'] = training_df['label'].astype('category')

А теперь мы сделаем то же самое, чтобы создать тестовый DataFrame, но на этот раз мы рассмотрим только отношения на позднем графике:

# Find positive examples
test_existing_links = graph.run("""
MATCH (author:Author)-[:CO_AUTHOR_LATE]->(other:Author)
RETURN id(author) AS node1, id(other) AS node2, 1 AS label
""").to_data_frame()
# Find negative examples
test_missing_links = graph.run("""
MATCH (author:Author)
WHERE (author)-[:CO_AUTHOR_LATE]-()
MATCH (author)-[:CO_AUTHOR_LATE*2..3]-(other)
WHERE not((author)-[:CO_AUTHOR_LATE]-(other))
RETURN id(author) AS node1, id(other) AS node2, 0 AS label
""").to_data_frame()
# Remove duplicates 
test_missing_links = test_missing_links.drop_duplicates()
# Down sample negative examples
test_missing_links = test_missing_links.sample(n=len(test_existing_links))
# Create DataFrame from positive and negative examples
test_df = test_missing_links.append(
    test_existing_links, ignore_index=True)
test_df['label'] = test_df['label'].astype('category')

Пришло время создать нашу модель машинного обучения.

Выбор алгоритма машинного обучения

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

Мы можем создать эту модель с помощью следующего кода:

from sklearn.ensemble import RandomForestClassifier
classifier = RandomForestClassifier(n_estimators=30, max_depth=10, 
                                    random_state=0)

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

Извлечение признаков - это способ преобразовать большие объемы данных и атрибутов в набор репрезентативных числовых значений, то есть характеристик ». Затем они используются в качестве входных данных, чтобы мы могли различать категории / значения для учебных задач.

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

Создание функций прогнозирования ссылок

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

def apply_graphy_features(data, rel_type):
    query = """
    UNWIND $pairs AS pair
    MATCH (p1) WHERE id(p1) = pair.node1
    MATCH (p2) WHERE id(p2) = pair.node2
    RETURN pair.node1 AS node1,
           pair.node2 AS node2,
           algo.linkprediction.commonNeighbors(
               p1, p2, {relationshipQuery: $relType}) AS cn,
           algo.linkprediction.preferentialAttachment(
               p1, p2, {relationshipQuery: $relType}) AS pa,
           algo.linkprediction.totalNeighbors(
               p1, p2, {relationshipQuery: $relType}) AS tn
    """
    pairs = [{"node1": pair[0], "node2": pair[1]}  
             for pair in data[["node1", "node2"]].values.tolist()]
    params = {"pairs": pairs, "relType": rel_type}
    
    features = graph.run(query, params).to_data_frame()
    return pd.merge(data, features, on = ["node1", "node2"])

Эта функция выполняет запрос, который берет каждую пару узлов из предоставленного DataFrame и вычисляет:

  • общие соседи (сп)
  • предпочтительная привязанность (па), и
  • общее количество соседей (тн)

для каждой из этих пар. Эти меры определены в первом посте.

Мы можем применить его к нашему поезду и протестировать DataFrames следующим образом:

training_df = apply_graphy_features(training_df, "CO_AUTHOR_EARLY")
test_df = apply_graphy_features(test_df, "CO_AUTHOR")

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

Мы по-прежнему можем использовать весь график для вычисления этих характеристик, поскольку развитие графика зависит от того, как он выглядит во все времена, а не только от того, что произошло в 2006 году и позже.

Теперь мы готовы обучать нашу модель. Мы можем сделать это с помощью следующего кода:

columns = ["cn", "pa", "tn"]
X = training_df[columns]
y = training_df["label"]
classifier.fit(X, y)

Наша модель теперь обучена, но нам нужно ее оценить.

Оценка нашей модели

Мы собираемся вычислить его точность, точность и отзывчивость. На приведенной ниже диаграмме, взятой из Книги алгоритмов графов О’Рейли, объясняется, как вычисляется каждый из этих показателей.

scikit-learn имеет встроенные функции, которые мы можем использовать для этого. Мы также можем вернуть важность каждой функции, используемой в нашей модели.

В этом помогут следующие функции:

from sklearn.metrics import recall_score
from sklearn.metrics import precision_score
from sklearn.metrics import accuracy_score
def evaluate_model(predictions, actual):
    accuracy = accuracy_score(actual, predictions)
    precision = precision_score(actual, predictions)
    recall = recall_score(actual, predictions)
    
    metrics = ["accuracy", "precision", "recall"]
    values = [accuracy, precision, recall]    
    return pd.DataFrame(data={'metric': metrics, 'value': values})
def feature_importance(columns, classifier):        
    features = list(zip(columns, classifier.feature_importances_))
    sorted_features = sorted(features, key = lambda x: x[1]*-1)
    
    keys = [value[0] for value in sorted_features]
    values = [value[1] for value in sorted_features]
    return pd.DataFrame(data={'feature': keys, 'value': values})

Мы можем оценить нашу модель, запустив следующий код:

predictions = classifier.predict(test_df[columns])
y_test = test_df["label"]
evaluate_model(predictions, y_test)

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

feature_importance(columns, classifier)

Выше мы видим, что общие соседи (cn) являются доминирующей чертой в нашей модели. Общие соседи возвращают нам количество незакрытых треугольников соавторов, которые есть у автора, так что это, возможно, не так уж удивительно.

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

Треугольники и коэффициент кластеризации

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

Мы можем запустить следующие запросы Cypher в браузере Neo4j, чтобы запустить этот алгоритм на нашем графике поездов:

CALL algo.triangleCount('Author', 'CO_AUTHOR_EARLY', { 
  write:true,
  writeProperty:'trianglesTrain', 
  clusteringCoefficientProperty:'coefficientTrain'});

И следующий запрос Cypher, чтобы запустить его на тестовом графике:

CALL algo.triangleCount('Author', 'CO_AUTHOR', { 
  write:true,
  writeProperty:'trianglesTest', 
  clusteringCoefficientProperty:'coefficientTest'});

Теперь у нас есть 4 новых свойства на наших узлах: trianglesTrain, coefficTrain, trianglesTest и coefficTest. Теперь давайте добавим их к нашему обучению и тестированию DataFrames с помощью следующей функции:

def apply_triangles_features(data,triangles_prop,coefficient_prop):
    query = """
    UNWIND $pairs AS pair
    MATCH (p1) WHERE id(p1) = pair.node1
    MATCH (p2) WHERE id(p2) = pair.node2
    RETURN pair.node1 AS node1,
    pair.node2 AS node2,
    apoc.coll.min([p1[$triangles], p2[$triangles]]) AS minTriangles,
    apoc.coll.max([p1[$triangles], p2[$triangles]]) AS maxTriangles,
    apoc.coll.min([p1[$coefficient], p2[$coefficient]]) AS minCoeff,
    apoc.coll.max([p1[$coefficient], p2[$coefficient]]) AS maxCoeff
    """
    
    pairs = [{"node1": pair[0], "node2": pair[1]}  
          for pair in data[["node1", "node2"]].values.tolist()]
    params = {"pairs": pairs,
              "triangles": triangles_prop,
              "coefficient": coefficient_prop}
    
    features = graph.run(query, params).to_data_frame()
    return pd.merge(data, features, on = ["node1", "node2"])

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

Мы не можем просто добавить эти значения в наш DataFrame как node1Triangles или node1Coeff, потому что у нас нет никаких гарантий относительно порядка узлов в паре. Нам нужно найти подход, не зависящий от порядка.

Мы можем сделать это, взяв среднее значение значений, произведение значений или вычислив минимальное и максимальное значение, как мы это делаем здесь.

Мы можем применить эту функцию к DataFrame следующим образом:

training_df = apply_triangles_features(training_df, 
  "trianglesTrain", "coefficientTrain")
test_df = apply_triangles_features(test_df, 
  "trianglesTest", "coefficientTest")

И теперь мы можем тренировать и оценивать:

columns = [
    "cn", "pa", "tn", 
    "minTriangles", "maxTriangles", "minCoeff", "maxCoeff"
]
X = training_df[columns]
y = training_df["label"]
classifier.fit(X, y)
predictions = classifier.predict(test_df[columns])
y_test = test_df["label"]
display(evaluate_model(predictions, y_test))

Эти функции были полезны! Каждый из наших показателей улучшился примерно на 4% по сравнению с исходной моделью. Какие функции наиболее важны?

display(feature_importance(columns, classifier))

Общие соседи по-прежнему являются наиболее влиятельными, но особенности треугольников также добавляют некоторую ценность.

В итоге

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

Разработка дополнительных функций

Можете ли вы придумать какие-либо другие функции, которые мы могли бы добавить, которые могли бы помочь нам создать модель с еще более высокой точностью? Возможно, могут помочь другие алгоритмы обнаружения сообществ или даже алгоритмы центральности?

Расширение поддержки прогнозов ссылок

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

Мы планируем добавить версии алгоритмов прогнозирования ссылок, которые работают на других графиках. Если у вас есть какие-то конкретные из них, которые вы хотели бы увидеть, дайте нам знать о проблемах с GitHub.

Что дальше?

Если вы нашли этот пост в блоге интересным, возможно, вам понравится Книга алгоритмов графов О’Рейли, над которой мы с Эми Ходлер работали последние 9 месяцев. Мы находимся на заключительном этапе проверки, и он должен быть доступен в ближайшие несколько недель.

Вы можете зарегистрироваться, чтобы получить бесплатную цифровую копию на веб-сайте Neo4j по адресу: neo4j.com/graph-algorithms-book

Мы с Уиллом Лайоном также работаем над новым онлайн-курсом обучения Data Science с Neo4j, так что следите за подробностями на странице Онлайн-обучение.