CS224W-Machine Learning with Graph-Snap

PRODIGY: Enabling In-context Learning Over Graphs

Formulation

Graph Learning Tasks

• Node Classification

• Link Prediction

• Graph Classification

In-context Learning Over Graphs: Link Prediction Example

How to achieve this? Two challenges

• How to represent the few-shot prompt for different graph tasks in the same input format, so that it can be consumed by one shared model?
  • Prompt Graph: represent each few-shot prompt over graph as a meta hierarchical graph

• How to pretrain a model that can solve any task in this format?
  • PGPretraining: Pretrain a message passing model over self-supervised tasks in PromptGraph format with diverse underlying structures.

Prompt Graph

Prompt Graph is a unified representation of few-shot prompts over graph for diverse tasks

Step 1: Data Graph - Link Prediction

Data Graph contextualizes each input $x$ in the graph $G$ (e.g., by subgraph extraction)

Data Graphs - Node Classification

Data Graphs - Graph Classification

Step 1: DataGraph Construction

DataGraph unifies input format:

• Use text feature to unify features over different datasets.

• Use different input node set for different classification over different levels (nodes vs edge vs graph)

Step 2: Task Graph

Task Graph interconnects inputs and labels across examples to form context for queries.

Prompt examples: bidirectional edges between data nodes and all label nodes.

Queries: single directed edges from each label to each data node.

Task Graph - Node Classification

Task Graph - Graph Classification

Flexibility of Task Graph

Task Graph unifies classification task format:

• Different number of classes are represented as different number of label nodes.

• Different number of prompt examples (i.e, shots) and queries are represented as different number of data nodes as well as how they connect with label nodes.

PromptGraph Inference - In context prediction GNN

In context prediction GNN

Hierarchical Message passing over PromptGraph

• Data Graph Encoder

• Message Passing over Task Graph

• Compute Logits

PRODIGY Pretraining

Reliable Graph Learning with Guaranteed Uncertainty Estimates

• How to evaluate if an uncertainty estimation method is good?
  • What is reliability mathematically?

• How to produce uncertainty estimates with reliability guarantees?
  • Introduction to conformal prediction

• How to produce reliable uncertainty estimates for graphs?
  • State-of-the-art: conformalized GNNs