2025-11-18T15:58:13.889736

A Survey of Graph Unlearning

Said, Tran, Zhao et al.
Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the \textit{right to be forgotten}. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effectively. In this comprehensive survey paper, we present the first systematic review of graph unlearning approaches, encompassing a diverse array of methodologies and offering a detailed taxonomy and up-to-date literature overview to facilitate the understanding of researchers new to this field. To ensure clarity, we provide lucid explanations of the fundamental concepts and evaluation measures used in graph unlearning, catering to a broader audience with varying levels of expertise. Delving into potential applications, we explore the versatility of graph unlearning across various domains, including but not limited to social networks, adversarial settings, recommender systems, and resource-constrained environments like the Internet of Things, illustrating its potential impact in safeguarding data privacy and enhancing AI systems' robustness. Finally, we shed light on promising research directions, encouraging further progress and innovation within the domain of graph unlearning. By laying a solid foundation and fostering continued progress, this survey seeks to inspire researchers to further advance the field of graph unlearning, thereby instilling confidence in the ethical growth of AI systems and reinforcing the responsible application of machine learning techniques in various domains.
academic

그래프 언러닝 조사

기본 정보

  • 논문 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년 10월 (최신 버전 2025년 10월 14일)
  • 논문 링크: https://arxiv.org/abs/2310.02164

초록

그래프 머신러닝 언러닝(Graph Unlearning)은 책임감 있는 AI 개발의 핵심 기술로서, 학습된 모델에서 민감한 데이터의 흔적을 제거하여 "잊혀질 권리"를 보장하는 수단을 제공합니다. 그래프 머신러닝이 데이터 프라이버시 및 대적 공격에 민감한 점을 감안할 때, 그래프 언러닝 기술을 적용하여 이러한 문제를 효과적으로 해결하는 것이 특히 필요합니다. 본 종합 조사 논문은 그래프 언러닝 방법을 처음으로 체계적으로 검토하며, 다양한 방법론을 포괄하고 상세한 분류법 및 최신 문헌 개요를 제공하여 해당 분야의 신규 연구자들을 지원합니다. 명확성을 보장하기 위해 본 논문은 그래프 언러닝의 기본 개념 및 평가 지표에 대한 명확한 설명을 제공하며, 다양한 전문 수준의 광범위한 독자층을 대상으로 합니다.

연구 배경 및 동기

문제 배경

  1. 프라이버시 보호 필요성: GDPR, CCPA 등 데이터 프라이버시 규정의 시행으로 개인은 머신러닝 모델에서 자신의 데이터 삭제를 요청할 권리를 가짐
  2. 그래프 데이터의 복잡성: 그래프 구조 데이터의 노드와 엣지 간 상호 연관성으로 인해 단순 데이터 삭제가 어려우며, 메시지 전달 메커니즘을 통해 정보가 원격 노드로 전파됨
  3. 대적 공격 방어: 악의적으로 주입된 데이터를 모델에서 제거하여 시스템 무결성 유지 필요
  4. 기존 방법의 부족: 전통적 머신러닝 언러닝 방법은 그래프 구조 데이터에 직접 적용될 수 없음

연구의 중요성

  • 법적 준수: 데이터 보호 규정 요구사항 충족
  • 프라이버시 보호: 개인 민감 정보가 모델에 의해 유출되지 않도록 보호
  • 보안 방어: 데이터 중독 등 대적 공격에 대한 저항
  • 윤리적 AI: 책임감 있는 AI 시스템 발전 촉진

기존 한계

  • 체계적인 그래프 언러닝 방법 종합 조사 부재
  • 그래프 데이터의 상호 연결 특성으로 인한 완전 언러닝의 복잡성
  • 효율성과 완전성 간의 어려운 균형 조정
  • 통일된 평가 기준 부재

핵심 기여

  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. 볼록 설정 하의 방법:
    • Hessian 행렬을 이용한 매개변수 업데이트
    • 영향 함수를 통한 데이터 영향 추정
    • 이론적 보장 제공
  2. 비볼록 설정 하의 방법:
    • 영향 함수 기반 엣지 언러닝(CEU)
    • 계층적 삭제 작업(GNNDelete)
    • 지식 증류 방법(GUKD, D2DGN)

실험 설정

평가 차원

1. 언러닝 완전성

  • 멤버십 추론 공격: 언러닝된 데이터가 여전히 감지될 수 있는지 평가
  • 예측 차이: 언러닝 모델과 재학습 모델의 출력 차이 비교
  • 매개변수 차이: 모델 매개변수의 유클리드 거리 비교

2. 언러닝 효율성

  • 시간 복잡도: 대부분의 방법은 층 수에 대해 선형, 특성 차원에 대해 제곱 복잡도
  • 실제 실행 시간: 실제 언러닝 작업에 필요한 시간

3. 모델 효용성

  • 다운스트림 작업 성능: F1 점수, 정확도, AUROC 등
  • 기준과의 비교: 일반적으로 처음부터 재학습한 성능과 비교

데이터셋

논문에서 언급한 방법은 다양한 그래프 데이터셋에서 평가됨:

  • 소셜 네트워크 데이터
  • 인용 네트워크
  • 분자 그래프 데이터
  • 추천 시스템 데이터

실험 결과

주요 발견

정확 대 근사 방법

  • 정확 방법: 완벽한 언러닝 보장을 제공하지만 계산 오버헤드가 큼
  • 근사 방법: 효율성과 언러닝 품질 간의 균형 달성

성능 트레이드오프

  • 언러닝 완전성과 계산 효율성 간의 근본적 트레이드오프 존재
  • 그래프의 상호 연결성으로 인해 국소적 언러닝이 전역 성능에 영향
  • 서로 다른 언러닝 유형(노드/엣지/특성)은 서로 다른 복잡도를 가짐

방법 비교

표 II의 요약에 따르면:

  • SISA 유형 방법은 정확성에서 우수한 성능 발휘
  • 영향 함수 방법은 근사 언러닝에서 상대적으로 효율적
  • 지식 증류 방법은 모델 효용성 유지 측면에서 장점 보유

응용 효과

  • 추천 시스템: RecEraser 등의 방법이 사용자-항목 상호작용 언러닝을 효과적으로 처리
  • 소셜 네트워크: GraphEraser가 그래프 분할을 통해 효율적인 언러닝 구현
  • 대적 방어: 언러닝 방법이 악의적으로 주입된 데이터를 효과적으로 제거

관련 연구

전통적 머신러닝 언러닝

  • 주로 독립동일분포 데이터에 초점
  • 그래프 구조 데이터에 직접 적용 불가
  • 데이터 간 의존성 고려 부족

그래프 머신러닝

  • 노드 분류, 링크 예측, 그래프 분류 등의 작업
  • 메시지 전달 메커니즘으로 인한 정보 전파의 복잡성
  • 특화된 언러닝 기술 필요

프라이버시 보호

  • 그래프 데이터에 대한 차분 프라이버시 적용
  • 연합 학습과 그래프 신경망의 결합
  • 멤버십 추론 공격 및 방어

결론 및 논의

주요 결론

  1. 그래프 언러닝은 책임감 있는 AI의 핵심 기술
  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개의 관련 문헌을 인용하여 독자에게 포괄적인 문헌 기초를 제공합니다.

종합 평가: 이는 고품질의 종합 조사 논문으로, 그래프 언러닝이라는 신흥 분야의 연구 현황을 체계적으로 정리하며 해당 분야의 발전을 위한 중요한 기초를 마련합니다. 논문은 조직이 명확하고 내용이 포괄적이며, 책임감 있는 AI 발전 추진에 중요한 의미를 가집니다.