Evaluation of Unlearning and Graph Unlearning Part 2

Summary

What Graph Unlearning Is Used For

Graph unlearning removes selected information from a model trained on graph-structured data. Graphs represent entities as nodes and their relationships as edges. Examples include healthcare and biological networks, social and financial networks, transportation systems, collaborations, and networks of connected devices.

Background: GCNs and Message Passing

A graph convolutional network (GCN) extends ideas from convolutional neural networks to graph data. A GCN layer uses node representations and features, an adjacency matrix (including self-loops), a degree matrix, trainable parameters, and an activation function.

The key intuition is message passing: a node’s updated representation can incorporate information from its neighbors. A message-passing neural network uses message and update functions, with an aggregation operation such as sum, mean, or max. Since nodes can have different numbers of neighbors, the aggregation should be permutation-invariant.

Updated node representations can support tasks such as:

• Node classification: Predicting a label for a node.
• Graph classification: Predicting a label for an entire graph.
• Edge prediction (link prediction): Estimating whether two nodes are or will be connected.

Three Types of Graph Unlearning

• Node-feature unlearning: Remove or forget a feature associated with a node while retaining the node and its connections.
• Node unlearning: Remove a node from the graph.
• Edge unlearning: Remove a connection between two nodes.

These types correspond to different real-world requests and require different unlearning capabilities.

Methods Discussed

• GraphEraser

  • Supports node and edge unlearning, but not node-feature unlearning.
  • Uses sharding or partitioning.

• GUIDE

  • Supports node unlearning, but not edge or feature unlearning.
  • Focuses on partitioning and graph-aggregation methods; the lecture also associates it with sharding.

• Projector

  • Supports feature unlearning by projecting weight parameters associated with features to be forgotten or considered irrelevant.
  • Works only with a linear GNN, according to the lecture.

• GraphEditor

  • Supports node, edge, and feature unlearning.
  • Uses a closed-form solution to remove the effect of deleted nodes, then updates their effects on neighboring nodes.

• GNNDelete

  • Supports all three types of removal.
  • Uses shared weight matrices across nodes and a layer-wise deletion operator to update the model.
  • According to the lecture, it cannot handle unlearning requests in a continued-learning setting.

• MEU (Mutual Evolution graph unlearning)

  • Supports all three types of removal.
  • Uses adaptive, high-level influence-neighborhood selection and a custom loss to determine which neighbors contribute messages.
  • The lecturer identified no disadvantages in the material discussed.

Open Challenges and Research Questions

Unlearning should remove the requested information without unnecessarily damaging performance on information that should be retained. Graph methods may over-forget, so their impact on retained information is an important concern.

Other open questions include:

• Can a model continue training after an unlearning request?
• Does the method genuinely forget the targeted information?
• Is the resulting performance good enough for real-world deployment?
• How should these properties be tested and measured reliably?

The lecturer presents these questions as active research opportunities.

Suggested Activity

Students are asked to explore the eight methods for evaluating robust unlearning in LLMs mentioned in the course material. They should try reproducing attacks using the Hugging Face checkpoint associated with the Harry Potter unlearning example, then report what they tried, what results they obtained, and anything interesting they observed.

The deadline is Saturday. Submissions should use “activity #unlearning” in the subject line.

Speakers and Sources Featured

• Speaker: One unnamed lecturer or instructor; no other speakers are evident in the subtitles.
• Methods and concepts: GCNs, message-passing neural networks, GraphEraser, GUIDE, Projector, GraphEditor, GNNDelete, and MEU.
• Tools and examples: Hugging Face and the Harry Potter unlearning checkpoint. The lecturer also refers to a paper and a list of method summaries, but their details are unclear in the subtitles.