Предсказание связей — Вывод отсутствующих и будущих ребер в сетях
- Год
- 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).
- Предсказание будущих научных коллабораций или цитирований в академических сетях.
- Вывод пропущенных белковых взаимодействий в биологических сетях на основе частичных экспериментальных данных.
- Завершение графов знаний путем предсказания отношений между сущностями.
- Предсказание взаимодействия лекарств и мишеней в фармакологических сетях.
Как это работает
Как это работает
Сеть собирается из наблюдаемых ребер и разбивается на обучающий и тестовый наборы с использованием временного или случайного разделения. Временное разделение предпочтительнее, когда доступны временные метки, поскольку оно предотвращает утечку информации: будущие ребра не должны информировать модель о прошлых. Обучающий граф — единственный граф, который метод оценки может наблюдать.
Поскольку подавляющее большинство пар узлов не связаны, оценка каждой отсутствующей пары непрактична. Стратегия отрицательной выборки выбирает набор несуществующих ребер для использования в качестве отрицательных примеров. Размер и стратегия выборки (случайная, сложная отрицательная, сбалансированная по степени) существенно влияют на измеряемую производительность и должны быть указаны вместе с результатами.
Каждой кандидатной паре присваивается оценка вероятности. Структурные индексы вычисляют оценку на основе наблюдаемой топологии графа — Общие соседи подсчитывают общих соседей, Жаккар нормализует этот подсчет по объединению, а Адамик-Адар взвешивает общих соседей обратным логарифмом их степени. Методы матричной факторизации разлагают матрицу смежности на скрытые факторы, скалярное произведение которых аппроксимирует вероятность ребра. Методы на основе GNN, в первую очередь фреймворк Seal от Zhang и Chen (2018), извлекают локальные подграфы вокруг каждой кандидатной пары и обучают классификатор графа отличать реальные ребра от ложных, улавливая структурные закономерности более высокого порядка, которые упускают простые индексы.
Предсказания ранжируются по оценке и сравниваются с отложенными положительными и отрицательными ребрами. AUC-ROC измеряет вероятность того, что случайная положительная пара будет ранжирована выше случайной отрицательной пары. Средняя точность (AP) обобщает точность по всему ранжированию и более информативна, когда положительных примеров мало. Обе метрики должны быть указаны; одна только точность вводит в заблуждение при сильном дисбалансе классов.
Частые ошибки
- Включение будущих ребер в обучающий граф — всегда используйте временные или строго случайные разделения и проверяйте, что ни одно тестовое ребро не появляется в обучающей матрице смежности.
- Указание только точности; поскольку несуществующих ребер намного больше, чем истинных, точность почти бессмысленна — всегда указывайте AUC и AP.
- Игнорирование стратегии отрицательной выборки при сравнении методов; изменение выборки может изменить порядок моделей.
- Применение предсказания связей к графам с менее чем 20 узлами — при таком малом количестве узлов структурные закономерности слишком разрежены, чтобы дать надежные предсказания; вместо этого предпочтите анализ центральности.
- Рассмотрение смещенного наблюдаемого графа как репрезентативной выборки — если наблюдаемые ребра систематически пропускают определенные типы узлов, предсказания будут наследовать этот сдвиг.
Часто задаваемые вопросы
Какой подход выбрать — индекс сходства или GNN?
Индексы сходства (Общие соседи, Жаккар, Адамик-Адар) — хорошая отправная точка: они не требуют обучения, интерпретируемы и удивительно хорошо работают на разреженных графах. Методы на основе GNN, такие как Seal, превосходят индексы на сетях со сложной структурой более высокого порядка, но требуют достаточного количества размеченных ребер и больше вычислительных ресурсов. Когда данных ограничено или важна интерпретируемость, начните с индексов.
Как разделить граф для оценки без утечки информации?
Если ваши ребра имеют временные метки, используйте временное разделение: обучайтесь на ребрах, наблюдаемых до определенного момента времени, и тестируйтесь на ребрах, образовавшихся после него. Без временных меток отложите случайную долю ребер в качестве положительных и выберите равное или фиксированное количество несуществующих ребер в качестве отрицательных, убедившись, что ни одно отложенное ребро не появляется в обучающей матрице смежности.
Почему AUC предпочтительнее точности?
В любой реальной сети количество отсутствующих ребер значительно превышает количество присутствующих — часто на несколько порядков. Тривиальная модель, которая предсказывает 'нет ребра' для каждой пары, достигает почти идеальной точности, но не дает полезных предсказаний. AUC-ROC и Средняя точность — это метрики, основанные на ранжировании, которые нечувствительны к этому дисбалансу и напрямую измеряют качество ранжирования.
Можно ли применять предсказание связей к ориентированным или взвешенным графам?
Да. Для ориентированных графов оценки могут вычисляться отдельно в каждом направлении, и некоторые фреймворки GNN нативно обрабатывают ориентированную смежность. Для взвешенных графов индексы сходства могут учитывать веса ребер при вычислении соседства, а методы GNN могут использовать признаки ребер. Однако большинство эталонных исследований проводится на невзвешенных неориентированных графах, поэтому при адаптации методов требуется дополнительная осторожность.
Похожие методы
Источники
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Скопировано.Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
Открыть ссылку на публикациюСкопировано.