qbiocode.apps.quvine.evaluation.link_prediction module

Link Prediction Evaluation Module

This module provides functions for evaluating node embeddings on link prediction tasks. Includes edge sampling strategies, edge feature computation, and comprehensive evaluation metrics.

Edge Sampling Strategies:

1. Random negative sampling

2. Hard negatives: 2-hop node pairs (common neighbors but no edge)

3. Same-community non-edges

4. Stratified sampling by node degree

Edge Feature Computation:

1. Hadamard product: u ⊙ v

2. Average: (u + v) / 2

3. L1 distance: |u - v|

4. L2 distance: ||u - v||₂

5. Concatenation: [u; v]

6. Inner product (dot product): u · v

7. Cosine similarity: (u · v) / (||u|| ||v||)

Evaluation Metrics:

• AUC-ROC, AUC-PR

• Precision@K, Recall@K

• Hit@K, MRR (Mean Reciprocal Rank)

Summary

Functions:

compute_edge_features	Compute edge features from node embeddings.
compute_structural_link_features	Compute structural features for edges (for baseline comparison).
evaluate_all_edge_feature_methods	Evaluate link prediction using all edge feature methods.
evaluate_link_prediction	Evaluate link prediction performance with no train-test leakage.
evaluate_link_prediction_cv	Evaluate link prediction with train-test split.
sample_negative_edges	Sample negative edges (non-existent edges) from the graph.
split_edges	Split graph edges into train/validation/test sets.
summarize_link_prediction_results	Summarize link prediction results across all edge feature methods.

Reference

sample_negative_edges(G, n_samples, existing_edges=None, strategy='random', seed=42)

Sample negative edges (non-existent edges) from the graph.

Parameters:

• G (Graph) – NetworkX graph

• n_samples (int) – Number of negative edges to sample

• existing_edges (Optional[Set[Tuple[int, int]]]) – Set of existing edges to avoid

• strategy (str) – Sampling strategy (‘random’, ‘hard_2hop’, ‘same_community’)

• seed (int) – Random seed

Return type:

List[Tuple[int, int]]

Returns:

List of negative edge tuples

split_edges(G, test_ratio=0.2, val_ratio=0.1, negative_sampling_strategy='random', seed=42)

Split graph edges into train/validation/test sets.

Parameters:

• G (Graph) – NetworkX graph

• test_ratio (float) – Fraction of edges for testing

• val_ratio (float) – Fraction of edges for validation

• negative_sampling_strategy (str) – Strategy for sampling negative edges

• seed (int) – Random seed

Return type:

Tuple[Graph, List[Tuple[int, int]], List[Tuple[int, int]], List[Tuple[int, int]]]

Returns:

Tuple of (train_graph, val_edges, test_edges, negative_edges)

compute_edge_features(embeddings, node_list, edges, method='hadamard')

Compute edge features from node embeddings.

Parameters:

• embeddings (ndarray) – Node embedding matrix (n_nodes x embedding_dim)

• node_list (List[int]) – List of node IDs corresponding to embedding rows

• edges (List[Tuple[int, int]]) – List of edge tuples

• method (str) – Feature computation method

Return type:

ndarray

Returns:

Edge feature matrix (n_edges x feature_dim)

evaluate_link_prediction(embeddings, node_list, positive_edges, negative_edges, edge_feature_method='hadamard', classifier='logistic', k_values=[10, 50, 100], test_size=0.3, random_state=42, train_positive_edges=None, train_negative_edges=None)

Evaluate link prediction performance with no train-test leakage.

When train_positive_edges and train_negative_edges are provided the classifier is trained on those edges and evaluated on positive_edges / negative_edges (the held-out test set). The StandardScaler is always fit exclusively on the training features so that test statistics are never seen during normalisation.

When train edges are omitted the function falls back to an internal stratified split controlled by test_size.

Parameters:

• embeddings (ndarray) – Node embedding matrix

• node_list (List[int]) – List of node IDs

• positive_edges (List[Tuple[int, int]]) – Test positive (existing) edges

• negative_edges (List[Tuple[int, int]]) – Test negative (non-existing) edges

• edge_feature_method (str) – Method for computing edge features

• classifier (str) – Classifier type (‘logistic’ or ‘random_forest’)

• k_values (List[int]) – K values for Precision@K and Recall@K

• test_size (float) – Fraction for internal test split (only used when train edges not provided)

• random_state (int) – Random seed

• train_positive_edges (Optional[List[Tuple[int, int]]]) – Training positive edges (prevents leakage)

• train_negative_edges (Optional[List[Tuple[int, int]]]) – Training negative edges (prevents leakage)

Return type:

Dict[str, float]

Returns:

Dictionary of evaluation metrics

evaluate_link_prediction_cv(G, embeddings, node_list, test_ratio=0.2, edge_feature_method='hadamard', negative_sampling_strategy='random', k_values=[10, 50, 100], random_state=42)

Evaluate link prediction with train-test split.

Parameters:

• G (Graph) – NetworkX graph

• embeddings (ndarray) – Node embedding matrix

• node_list (List[int]) – List of node IDs

• test_ratio (float) – Fraction of edges for testing

• edge_feature_method (str) – Method for computing edge features

• negative_sampling_strategy (str) – Strategy for negative sampling

• k_values (List[int]) – K values for metrics

• random_state (int) – Random seed

Return type:

Dict[str, float]

Returns:

Dictionary of evaluation metrics

evaluate_all_edge_feature_methods(embeddings, node_list, positive_edges, negative_edges, k_values=[10, 50, 100], random_state=42, train_positive_edges=None, train_negative_edges=None)

Evaluate link prediction using all edge feature methods.

Parameters:

• embeddings (ndarray) – Node embedding matrix

• node_list (List[int]) – List of node IDs

• positive_edges (List[Tuple[int, int]]) – Test positive edges

• negative_edges (List[Tuple[int, int]]) – Test negative edges

• k_values (List[int]) – K values for metrics

• random_state (int) – Random seed

• train_positive_edges (Optional[List[Tuple[int, int]]]) – Training positive edges (no leakage when provided)

• train_negative_edges (Optional[List[Tuple[int, int]]]) – Training negative edges (no leakage when provided)

Return type:

Dict[str, Dict[str, float]]

Returns:

Dictionary mapping method names to evaluation results

summarize_link_prediction_results(results)

Summarize link prediction results across all edge feature methods.

Parameters:

results (Dict[str, Dict[str, float]]) – Dictionary of results from evaluate_all_edge_feature_methods

Return type:

Dict[str, float]

Returns:

Dictionary of summary statistics

compute_structural_link_features(G, edges)

Compute structural features for edges (for baseline comparison).

Features: - Common neighbors - Jaccard coefficient - Adamic-Adar index - Preferential attachment

Parameters:

• G (Graph) – NetworkX graph

• edges (List[Tuple[int, int]]) – List of edge tuples

Return type:

ndarray

Returns:

Structural feature matrix (n_edges x 4)