Feature prediction

• Feature prediction: to predict the original node features by decoding low-dimensional representations
• Feature denoising: to add (generally continuous, e.g. isotropic Gaussian) noises to the original features and try to reconstruct them
• Masked feature prediction: a special, discrete case of feature denoising, which predicts the original features of masked nodes by representations of unmasked ones. It is "autoregressive" if the predicted nodes are generated one-by-one

Discrimination (contrastive)

• Node instance discrimination: to minimize/maximize the distance between pairs of positive/negative node representations. Jenson-Shannon (JS), InfoNCE (incl. NT-Xent), Triplet margin, and Bootstrapping are all estimators of mutual information (MI) between nodes. Other contrastive losses:
  • MSE stands for the mean squared error ($\ell_2$ loss)
  • SP stands for the population spectral contrastive loss
  • BPR stands for Bayesian Personalized Ranking loss, mostly used in recommendation
  • Other stands for other, literally not belonging to any of the above
• Dimension discrimination: to minimize/maximize the mutual information (MI) between pairs of positive/negative representation dimensions. Could be either intra-sample or inter-sample

• Property prediction: a regression task to predict the property of a node, e.g. degree/clustering coefficient
• Centrality ranking: to estimate whether the centrality score of a node is greater/lower than that of another node
• Node order matching: to match the output node order with the input order
• Property-based discrimination: to perform contrastive learning in which positive/negative samples are selected based on node properties, e.g. nodes with the same/different degrees

• Link prediction: a generally binary classification task that predicts if two nodes are connected by a link. For heterogeneous graphs, link prediction is based on meta-paths. For hypergraphs, link prediction searchs for the missing node given other nodes in a hyperedge
• Link denoising: to add (generally continuous) noises to the original edge set and try to reconstruct it
• Masked link prediction: to predict the masked links by node representations propagated on the unmasked graph. It is "autoregressive" if the predicted links are generated one-by-one
• (Masked) edge feature prediction: to predict the original (masked) edge features by node representations
• Edge discrimination: to perform contrastive learning between edge features / representations

• Context discrimination: to distinguish between contextual nodes and non-contextual nodes. LE stands for Laplacian Eigenmaps objective
• Contextual subgraph discrimination: to distinguish between representations aggregated from different contextual subgraphs (maybe from different receptive fields). CE stands for cross-entropy
• Context feature prediction: node feature prediction but to reconstruct the features of k-hop neighbors instead
• Contextual property prediction: to predict the properties of contextual subgraphs (e.g. node / edge types contained, total node / edge counts, structural coefficient)

• Similarity prediction: to predict a similarity matrix between nodes. The pairwise similarity can be defined by shortest path distance, PageRank similarity, Katz index, Jaccard coefficient, $\ell_2$ distance & cosine similarity between output representations / input-output, etc
• Similarity-based discrimination: instance discrimination that is node similarity-aware
• Similarity graph alignment: to construct an additional similarity graph based on pairwise similarities of node features or graph topology, and minimize the distance of representation distributions between them (the original and similarity graph, or two different similarity graphs)

• Motif prediction: to assign each node (or supernode in the fragment graph) a motif pseudo-label given by unsupervised motif discovery algorithms (e.g. RDKit) and learn to predict them. It is "autoregressive" if the predicted supernodes are generated one-by-one
• Motif-based masked feature prediction: similar to masked feature prediction, but the features are masked in motifs
• Motif-based discrimination: to perform contrast between the original graph view and the fragment graph view

• Synthetic graph discrimination: binary classification between two synthetic graphs with different synthesizers (Erdős-Rényi generator / SBM generator)
• Node clustering: to assign each node a cluster centroid (prototype) and - i) minimize the distance between nodes and their corresponding centroids in the latent space; or ii) minimize the distance between the learned centroids and the ground-truth centroids given by unsupervised feature clustering algorithms (e.g. K-means, DeepCluster)
• Graph partitioning: to assign each node a cluster centroid (prototype) and - i) predict the quality of the learned partitions evaluated by some metrics, e.g. maximizing modularity or minimizing the normalized edge weights of a graph cut (spectral clustering); or ii) predict the cluster membership of each node given by unsupervised graph partitioning algorithms (structure-based, e.g. METIS, Louvain)
• Cluster/partition-based instance discrimination: instance discrimination that is aware of graph clustering/partitioning memberships
• Cluster/partition-conditioned link prediction: to maximize the log-likelihood of existing links, but conditioned by the graph cluster/partition distributions

• Graph instance discrimination: to discriminate between global representations of different graph views (generally for small-scale graphs)
• Graph dimension discrimination: dimension discrimination of different graph representations
• Node-graph discrimination: instance discrimination between the representation of each node and a global representation vector, usually aggregated from the whole graph by a readout function
• Group discrimination: a simplified node-graph discrimination that binarily classifies if a node belongs to the original or the perturbed graph
• Graph similarity prediction: to predict various kinds of similarity functions between pairs of graphs, e.g. graph kernels (graphlet kernel, random walk kernel, graph edit distance kernel, etc)
• Half-graph matching: to divide each graph into two halves and predict if two halves are from the same original graph

• Cross-manifold discrimination: to perform instance discrimination between different manifolds (e.g. Euclidean vs. Hyperbolic)
• Hyperbolic masked prediction: to perform masked feature/link prediction in hyperbolic space
• Hyperbolic angle prediction: to pool representations to 2-dimensional angle vectors in a unit hyperbola. These vectors serve as pseudo-labels for regression

• Multi-task learning: to combine a set of different pre-training tasks with bespoke algorithms/architectures

• Fine-tuning: to jointly learn downstream branches as well as the original pre-trained model. Parameter-efficient fine-tuning (PEFT) only updates part of the pre-trained model, e.g. adapter layers or pruned networks
• Prompting: to construct task-specific prompts as model input for downstream tuning/prompting

• Autoregressive language modeling (AR): to predict the next token in a sequence based on previous tokens
• Masked language modeling (MLM): to predicts masked tokens based on the context
• Node-text discrimination: to discriminate between textual and graph representations
• Graph-instruction matching: to reorder the list of node text to match the corresponding textual representations
• Label-free node classification: node classification with LLM-generated node pseudo-labels
• SFT: various kinds of supervised fine-tuning strategies, incl. task-specific instruction tuning

Note: :spider_web: graph model (GNN/GT/...); :robot: language model (LM/LLM); :chart_with_upwards_trend: parameter-efficient fine-tuning module (adapter); :memo: pure prompting without any parameter update

" :train: Training" refers to the self-supervised pre-training phase, mostly for LLMs or other large model components. An empty "Training strategy" mostly indicates that pre-trained LLMs are used and kept frozen. Alternatively, " :notes: Tuning" can refer to all kinds of post-training processes, including fine-tuning/instruction tuning/training of some smaller, auxiliary modules, both supervised and self-supervised.

Example 1: training of TAPE can be divided into 3 phases:

• LLM pre-training (" :robot::train: Training"): a pre-trained GPT-3.5 is directly utilized
• LM fine-tuning (" :robot::notes: Tuning"): a pre-trained DeBERTa is fine-tuned with LLM-generated explanations
• Downstream GNN training (" :spider_web::notes: Tuning"): a RevGAT is trained using the enhanced textual features

Example 2: training of GraphAdapter can also be divided into 3 phases:

• LM pre-training (" :robot::train: Training"): a pre-trained BERT/RoBERTa/GPT-2/LLaMA 2 is directly utilized

• GNN adapter "pre-training" (" :spider_web::notes: Tuning"): a GraphSAGE and a MLP fusion module are trained with LM frozen

  ( :warning: Side note: "GNN adapters" are considered as part of LLM+GNN architectures instead of a PEFT component.)

• Instruction tuning (" :spider_web::notes: Tuning"): the GraphSAGE and fusion module are fine-tuned by task-specific prompts