Обзор машинного разучивания на графах

Основная информация

• ID статьи: 2310.02164
• Название: A Survey of Graph Unlearning
• Авторы: Anwar Said, Ngoc N. Tran, Yuying Zhao, Tyler Derr, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos
• Категория: cs.LG (Машинное обучение)
• Дата публикации: arXiv октябрь 2023 г. (последняя версия 14 октября 2025 г.)
• Ссылка на статью: https://arxiv.org/abs/2310.02164

Аннотация

Машинное разучивание на графах (Graph Unlearning) служит ключевой технологией в развитии ответственного искусственного интеллекта, предоставляя средства для удаления следов конфиденциальных данных из обученных моделей, тем самым обеспечивая реализацию "права на забвение". Учитывая чувствительность машинного обучения на графах к вопросам конфиденциальности данных и уязвимость перед состязательными атаками, применение методов разучивания на графах становится особенно необходимым для эффективного решения этих проблем. Данный обзорный труд впервые систематически рассматривает методы разучивания на графах, охватывая разнообразные методологические подходы и предоставляя детальную классификацию и обзор современной литературы, что облегчает работу новых исследователей в этой области. Для обеспечения ясности изложения статья предоставляет четкие объяснения фундаментальных концепций и метрик оценки в контексте разучивания на графах, ориентируясь на широкую аудиторию с различным уровнем подготовки.

Исследовательский контекст и мотивация

Проблемный контекст

1. Требования защиты конфиденциальности: С введением нормативных актов по защите данных (таких как GDPR, CCPA) люди имеют право требовать удаления своих данных из моделей машинного обучения
2. Сложность графовых данных: Взаимосвязь узлов и ребер в структурированных графовых данных делает простое удаление данных затруднительным, поскольку информация распространяется на удаленные узлы через механизмы передачи сообщений
3. Защита от состязательных атак: Необходимость удаления вредоносно внедренных данных из модели для сохранения целостности системы
4. Недостаточность существующих методов: Традиционные методы машинного разучивания не могут быть непосредственно применены к графовым структурированным данным

Значимость исследования

• Правовое соответствие: Выполнение требований нормативных актов по защите данных
• Защита конфиденциальности: Защита конфиденциальной информации от утечки через модель
• Защита безопасности: Противодействие состязательным атакам, таким как отравление данных
• Этичный ИИ: Содействие развитию ответственных систем искусственного интеллекта

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

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

Основные вклады

1. Первый систематический обзор: Предоставляет первый всеобъемлющий систематический обзор области разучивания на графах
2. Детальная классификация: Классифицирует методы разучивания на графах на две основные категории: точное разучивание (Exact Unlearning) и приблизительное разучивание (Approximate Unlearning)
3. Комплексный анализ приложений: Исследует применение разучивания на графах в социальных сетях, системах рекомендаций, медицинских сетях и других областях
4. Структура оценки: Предоставляет методы оценки полноты разучивания, эффективности и полезности модели
5. Направления будущих исследований: Указывает на несколько перспективных направлений исследований

Подробное описание методов

Определение задачи

Основные концепции

• Определение графа: G = (V, E, X, Xe), где V — множество узлов, E — множество ребер, X — матрица признаков узлов, Xe — матрица признаков ребер
• Множество разучивания: S ⊆ D, обозначающее подмножество данных, которое должно быть разучено
• Цель: Обновить параметры модели θ таким образом, чтобы результаты были эквивалентны переобучению на D\S

Определение (ε, δ)-разучивания

Для фиксированного набора данных D, множества разучивания S и случайного алгоритма обучения A, алгоритм разучивания U является (ε, δ)-разучиванием тогда и только тогда, когда для всех R ⊆ R:

Pr[A(D \ S) ∈ R] ≤ e^ε Pr[U(A(D), S, D) ∈ R] + δ
Pr[U(A(D), S, D) ∈ R] ≤ e^ε Pr[A(D \ S) ∈ R] + δ

Классификация типов разучивания на графах

1. Трансдуктивное разучивание (Transductive)

• Разучивание узлов: Удаление конкретного узла и всех его соединений
• Разучивание ребер: Удаление конкретного ребра при сохранении узлов
• Разучивание признаков узлов: Удаление конкретных признаков узла

2. Индуктивное разучивание (Inductive)

• Индуктивное разучивание узлов: Удаление множества узлов из нескольких графов
• Индуктивное разучивание ребер: Удаление множества ребер из нескольких графов
• Разучивание на уровне графа: Удаление целого экземпляра графа

Технические подходы

Методы точного разучивания

1. Структура SISA: Разделение обучающих данных на фрагменты, требующее переобучения только затронутых фрагментов
2. Переобучение параметров: Сохранение исторических параметров и переобучение с момента первого появления удаляемых данных
3. Закрытые решения: Например, GraphEditor, преобразующий обучение GNN в аналитически разрешимую задачу

Методы приблизительного разучивания

1. Методы в выпуклых условиях:
   • Использование матрицы Гессиана для обновления параметров
   • Оценка влияния данных через функции влияния
   • Предоставление теоретических гарантий
2. Методы в невыпуклых условиях:
   • Разучивание ребер на основе функций влияния (CEU)
   • Иерархические операции удаления (GNNDelete)
   • Методы дистилляции знаний (GUKD, D2DGN)

Экспериментальная установка

Измерения оценки

1. Полнота разучивания

• Атаки вывода членства: Оценка возможности обнаружения разученных данных
• Различие в предсказаниях: Сравнение выходных данных разученной модели и переобученной модели
• Различие в параметрах: Сравнение евклидова расстояния между параметрами модели

2. Эффективность разучивания

• Временная сложность: Большинство методов имеют линейную сложность относительно количества слоев и квадратичную относительно размерности признаков
• Эмпирическое время выполнения: Фактическое время, необходимое для операции разучивания

3. Полезность модели

• Производительность на нижестоящих задачах: F1-оценка, точность, AUROC и другие метрики
• Сравнение с базовыми показателями: Обычно сравнивается с производительностью переобученной модели с нуля

Наборы данных

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

• Данные социальных сетей
• Сети цитирования
• Молекулярные графы
• Данные систем рекомендаций

Результаты экспериментов

Основные выводы

Методы точного и приблизительного разучивания

• Точные методы: Обеспечивают совершенные гарантии разучивания, но требуют больших вычислительных затрат
• Приблизительные методы: Достигают баланса между эффективностью и качеством разучивания

Компромиссы в производительности

• Существует фундаментальный компромисс между полнотой разучивания и вычислительной эффективностью
• Взаимосвязанность графа приводит к тому, что локальное разучивание влияет на глобальную производительность
• Различные типы разучивания (узлы/ребра/признаки) имеют различную сложность

Сравнение методов

Согласно сводке в таблице II:

• Методы типа SISA демонстрируют отличную производительность в точности
• Методы на основе функций влияния относительно эффективны при приблизительном разучивании
• Методы дистилляции знаний показывают преимущества в сохранении полезности модели

Эффективность приложений

• Системы рекомендаций: Методы типа RecEraser эффективно обрабатывают разучивание взаимодействий пользователь-элемент
• Социальные сети: GraphEraser достигает эффективного разучивания через фрагментацию графа
• Защита от состязательных атак: Методы разучивания эффективно удаляют вредоносно внедренные данные

Связанные работы

Традиционное машинное разучивание

• Основное внимание уделяется независимо и одинаково распределенным данным
• Не может быть непосредственно применено к графовым структурированным данным
• Не учитывает зависимости между данными

Машинное обучение на графах

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

Защита конфиденциальности

• Применение дифференциальной конфиденциальности к графовым данным
• Объединение федеративного обучения с графовыми нейронными сетями
• Атаки вывода членства и защита от них

Заключение и обсуждение

Основные выводы

1. Разучивание на графах является ключевой технологией ответственного ИИ
2. Методы точного и приблизительного разучивания имеют свои преимущества и должны выбираться в зависимости от требований приложения
3. Стандарты оценки требуют дальнейшего совершенствования и стандартизации
4. Межотраслевые приложения демонстрируют огромный потенциал

Ограничения

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

Направления будущих исследований

1. Технологическое развитие

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

2. Расширение приложений

• Разучивание базовых моделей: Адаптация к требованиям разучивания крупномасштабных графовых базовых моделей
• Взаимодействие между несколькими пользователями: Решение этических проблем разучивания данных взаимодействия между пользователями
• Среды периферийных вычислений: Эффективное разучивание в условиях ограниченных ресурсов

3. Совершенствование теории

• Методы сертифицированного удаления: Предоставление более сильных теоретических гарантий
• Стандартизация оценки: Установление надежной структуры оценки разучивания
• Количественная оценка конфиденциальности: Более точные методы количественной оценки утечки конфиденциальности

Глубокая оценка

Преимущества

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

Недостатки

1. Ограниченный эмпирический анализ: Как обзорная статья, не содержит новых экспериментальных проверок
2. Глубина методов: Описание технических деталей некоторых сложных методов может быть более подробным
3. Отсутствие эталонов: Отсутствуют единые тесты и стандарты сравнения
4. Теоретический анализ: Анализ теоретической сложности различных методов может быть более детальным

Влияние

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

Применимые сценарии

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

Библиография

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

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