Skip to content

Graph Algorithms

Graph Algorithms

WIP: These classes are currently actively being developed and are subject to change in both API and functionality over time.

Graph Algorithms

Docs TBD

Build a NetworkX graph from a Proximity instance.

proximity_graph(prox, n_neighbors=5, min_edges=2, min_weight=0.8)

Build a NetworkX graph from a Proximity instance.

Nodes carry all columns of the proximity DataFrame; edges carry a weight (similarity, or distance normalized to [0, 1] for distance-based backends).

Parameters:

Name Type Description Default
prox Proximity

An instance of a Proximity class.

 required
n_neighbors int

Number of neighbors to retrieve per node (default: 5).

 5
min_edges int

Minimum edges per node (default: 2).

 2
min_weight float

Weight threshold for additional edges beyond min_edges (default: 0.8).

 0.8

Returns:

Type Description
Graph

nx.Graph: The proximity graph.
Source code in src/workbench/algorithms/graph/light/proximity_graph.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def proximity_graph(prox: Proximity, n_neighbors: int = 5, min_edges: int = 2, min_weight: float = 0.8) -> nx.Graph:
    """Build a NetworkX graph from a Proximity instance.

    Nodes carry all columns of the proximity DataFrame; edges carry a `weight`
    (similarity, or distance normalized to [0, 1] for distance-based backends).

    Args:
        prox (Proximity): An instance of a Proximity class.
        n_neighbors (int): Number of neighbors to retrieve per node (default: 5).
        min_edges (int): Minimum edges per node (default: 2).
        min_weight (float): Weight threshold for additional edges beyond min_edges (default: 0.8).

    Returns:
        nx.Graph: The proximity graph.
    """
    node_df = prox.df
    id_column = prox.id_column

    # Get all neighbor pairs
    log.info("Retrieving all neighbors...")
    all_ids = node_df[id_column].tolist()
    neighbors_df = prox.neighbors(all_ids, n_neighbors=n_neighbors, include_self=False)

    # Handle duplicate IDs
    if not node_df[id_column].is_unique:
        log.warning(f"Column '{id_column}' contains duplicate values. Using first occurrence.")
        node_df = node_df.drop_duplicates(subset=[id_column], keep="first")

    log.info("Adding nodes to the proximity graph...")
    graph = nx.Graph()
    graph.add_nodes_from(node_df.set_index(id_column, drop=False).to_dict("index").items())

    # Compute edge weights (handle both distance-based and similarity-based proximity)
    if "similarity" in neighbors_df.columns:
        neighbors_df["weight"] = neighbors_df["similarity"]
    else:
        max_distance = neighbors_df["distance"].max()
        neighbors_df["weight"] = 1.0 - neighbors_df["distance"] / max_distance if max_distance > 0 else 1.0

    # Add edges: guarantee min_edges per node, plus any above min_weight
    log.info("Adding edges to the graph...")
    neighbors_df = neighbors_df.sort_values([id_column, "weight"], ascending=[True, False])
    rank = neighbors_df.groupby(id_column).cumcount()
    edges = neighbors_df[(rank < min_edges) | (neighbors_df["weight"] > min_weight)]
    graph.add_edges_from(zip(edges[id_column], edges["neighbor_id"], ({"weight": w} for w in edges["weight"])))

    return graph

Questions?

The SuperCowPowers team is happy to answer any questions you may have about AWS and Workbench. Please contact us at workbench@supercowpowers.com or on chat us up on Discord