Skip to content
Назад к результатам поиска

Предсказание связей — Вывод отсутствующих и будущих ребер в сетях

Год
2003
Тип
Network inference task

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Предсказание связей — это задача сетевого анализа, которая оценивает, какие ребра отсутствуют в наблюдаемом графе или какие ребра, вероятно, образуются в будущем.

Формализованная Liben-Nowell и Kleinberg (2003, 2007), она охватывает спектр подходов — от простых индексов структурного сходства, таких как Общие соседи, коэффициент Жаккара и Адамик-Адар, до методов матричной факторизации и графовых нейронных сетей (GNN) — и оценивается с помощью AUC и Средней точности для учета сильно несбалансированного соотношения реальных и несуществующих ребер.

Интуиция метода

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

История

Задача была формально определена Liben-Nowell и Kleinberg в статье SODA 2003 года и ее расширенной версии JASIST 2007 года, где они сравнили простые индексы структурного сходства на сетях соавторства и показали, что одна только топология несет сильный предсказательный сигнал. Последующие работы расширили задачу на матричную факторизацию и вероятностные генеративные модели. Область была существенно продвинута Zhang и Chen (2018), которые предложили фреймворк Seal — извлечение локальных охватывающих подграфов и их классификацию с помощью GNN — продемонстрировав, что выученные структурные признаки последовательно превосходят разработанные вручную индексы сходства на различных эталонных сетях.

Когда применять

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

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Охватывает широкий диапазон сложности — простые индексы Жаккара или Адамика-Адара не требуют обучения и работают непосредственно с топологией графа, в то время как методы на основе GNN изучают сложные структурные закономерности.
  • Свободные от моделей индексы сходства быстры, интерпретируемы и надежны на разреженных графах с ограниченным обучающим сигналом.
  • Подходы GNN хорошо обобщаются на различные области (социальные, биологические, графы знаний) и улавливают топологию более высокого порядка.
  • Структура оценки AUC/AP устойчива к сильному дисбалансу классов между реальными и несуществующими ребрами.

Применение

  • Рекомендация друзей или контактов в социальных сетях (Facebook People You May Know, LinkedIn).
  • Предсказание будущих научных коллабораций или цитирований в академических сетях.
  • Вывод пропущенных белковых взаимодействий в биологических сетях на основе частичных экспериментальных данных.
  • Завершение графов знаний путем предсказания отношений между сущностями.
  • Предсказание взаимодействия лекарств и мишеней в фармакологических сетях.

Как это работает

Как это работает

1

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

2

Поскольку подавляющее большинство пар узлов не связаны, оценка каждой отсутствующей пары непрактична. Стратегия отрицательной выборки выбирает набор несуществующих ребер для использования в качестве отрицательных примеров. Размер и стратегия выборки (случайная, сложная отрицательная, сбалансированная по степени) существенно влияют на измеряемую производительность и должны быть указаны вместе с результатами.

3

Каждой кандидатной паре присваивается оценка вероятности. Структурные индексы вычисляют оценку на основе наблюдаемой топологии графа — Общие соседи подсчитывают общих соседей, Жаккар нормализует этот подсчет по объединению, а Адамик-Адар взвешивает общих соседей обратным логарифмом их степени. Методы матричной факторизации разлагают матрицу смежности на скрытые факторы, скалярное произведение которых аппроксимирует вероятность ребра. Методы на основе GNN, в первую очередь фреймворк Seal от Zhang и Chen (2018), извлекают локальные подграфы вокруг каждой кандидатной пары и обучают классификатор графа отличать реальные ребра от ложных, улавливая структурные закономерности более высокого порядка, которые упускают простые индексы.

4

Предсказания ранжируются по оценке и сравниваются с отложенными положительными и отрицательными ребрами. AUC-ROC измеряет вероятность того, что случайная положительная пара будет ранжирована выше случайной отрицательной пары. Средняя точность (AP) обобщает точность по всему ранжированию и более информативна, когда положительных примеров мало. Обе метрики должны быть указаны; одна только точность вводит в заблуждение при сильном дисбалансе классов.

Частые ошибки

  • Включение будущих ребер в обучающий граф — всегда используйте временные или строго случайные разделения и проверяйте, что ни одно тестовое ребро не появляется в обучающей матрице смежности.
  • Указание только точности; поскольку несуществующих ребер намного больше, чем истинных, точность почти бессмысленна — всегда указывайте AUC и AP.
  • Игнорирование стратегии отрицательной выборки при сравнении методов; изменение выборки может изменить порядок моделей.
  • Применение предсказания связей к графам с менее чем 20 узлами — при таком малом количестве узлов структурные закономерности слишком разрежены, чтобы дать надежные предсказания; вместо этого предпочтите анализ центральности.
  • Рассмотрение смещенного наблюдаемого графа как репрезентативной выборки — если наблюдаемые ребра систематически пропускают определенные типы узлов, предсказания будут наследовать этот сдвиг.

Часто задаваемые вопросы

Какой подход выбрать — индекс сходства или GNN?

Индексы сходства (Общие соседи, Жаккар, Адамик-Адар) — хорошая отправная точка: они не требуют обучения, интерпретируемы и удивительно хорошо работают на разреженных графах. Методы на основе GNN, такие как Seal, превосходят индексы на сетях со сложной структурой более высокого порядка, но требуют достаточного количества размеченных ребер и больше вычислительных ресурсов. Когда данных ограничено или важна интерпретируемость, начните с индексов.

Как разделить граф для оценки без утечки информации?

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

Почему AUC предпочтительнее точности?

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

Можно ли применять предсказание связей к ориентированным или взвешенным графам?

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

Похожие методы

Источники

  1. Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.

    Открыть ссылку DOI
    Скопировано.
  2. Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.

    Открыть ссылку на публикацию
    Скопировано.