griptomo.core.gpu_extract_features

  1from __future__ import annotations
  2
  3import time
  4from typing import TYPE_CHECKING
  5
  6import igraph as ig
  7
  8if TYPE_CHECKING:  # pragma: no cover - hints only evaluated by type-checkers.
  9    import cudf  # type: ignore
 10    import cugraph  # type: ignore
 11
 12try:  # pragma: no cover - GPU-only dependencies may be absent in CPU environments.
 13    import cugraph as cg  # type: ignore
 14    import cudf  # type: ignore
 15    import cupy as cp  # type: ignore
 16except ImportError as exc:  # pragma: no cover - exercised when RAPIDS is unavailable.
 17    cg = None  # type: ignore
 18    cudf = None  # type: ignore
 19    cp = None  # type: ignore
 20    _GPU_IMPORT_ERROR: Exception | None = exc
 21else:
 22    _GPU_IMPORT_ERROR = None
 23
 24
 25def cugraph_calc_graph_features(
 26    G_ig: ig.Graph, G_cg: "cugraph.Graph", skip_clique_num: bool = False
 27):
 28    """
 29    Calculate various graph features for a cugraph.Graph object.
 30
 31    Parameters
 32    ----------
 33    G_ig : igraph.Graph
 34        The input graph for which features are to be calculated.
 35    G_cg : cugraph.Graph
 36        The input graph for which features are to be calculated.
 37    skip_clique_num : bool, optional
 38        If True, the calculation of the largest clique number will be skipped. Default is False.
 39
 40    Returns
 41    -------
 42    dict
 43        A dictionary containing the calculated graph features:
 44        - "total n nodes": Total number of nodes in the graph.
 45        - "total n edges": Total number of edges in the graph.
 46        - "n nodes": Number of nodes in the largest connected component.
 47        - "n edges": Number of edges in the largest connected component.
 48        - "density": Density of the graph.
 49        - "diameter": Diameter of the graph.
 50        - "avg clustering": Average clustering coefficient of the graph.
 51        - "max closeness centrality": Maximum closeness centrality in the graph.
 52        - "max eigenvector centrality": Maximum eigenvector centrality in the graph.
 53        - "degree assortativity": Degree assortativity of the graph (normalized to [0, 1]).
 54        - "max clique number": Size of the largest clique in the graph.
 55        - "n communities": Number of communities detected using the louvian algorithm.
 56        - "avg path length": Average path length in the graph.
 57        - "max betweenness centrality": Maximum betweenness centrality in the graph, normalized by the number of possible node pairs.
 58
 59    Raises
 60    ------
 61    ValueError
 62        If the input is not a cugraph.Graph object.
 63
 64    Notes
 65    -----
 66    - The graph is assumed to be undirected and unweighted.
 67    - If the graph is not connected, the largest connected component is used for feature calculation.
 68    - The diameter is calculated using a 2-step BFS.
 69    - GPU implementations are used for all calculations except for clique_num, which is not supported on GPU.
 70    - n_communities is calculated using the Louvain algorithm instead of the fast greedy algorithm in igraph.
 71    """
 72    if cg is None or cudf is None or cp is None:
 73        raise RuntimeError(
 74            "cugraph, cudf, and cupy must be installed to use GPU feature extractors"
 75        ) from _GPU_IMPORT_ERROR
 76
 77    if not isinstance(G_cg, cg.Graph):
 78        raise ValueError("Input must be a cugraph.Graph object")
 79
 80    if not isinstance(G_ig, ig.Graph):
 81        raise ValueError("Input must be an igraph.Graph object")
 82
 83    G_feat = {}
 84    G_feat["total n nodes"] = G_cg.number_of_nodes()
 85    print("total n nodes", G_feat["total n nodes"])
 86    G_feat["total n edges"] = G_cg.number_of_edges()
 87    print("total n edges", G_feat["total n edges"])
 88
 89    connected_components_df = cg.weakly_connected_components(G_cg)
 90    if connected_components_df["labels"].nunique() > 1:
 91        largest_cc = connected_components_df["labels"].value_counts().idxmax()
 92        G_cg = cg.subgraph(G_cg, connected_components_df["labels"] == largest_cc)
 93        G_ig = G_ig.clusters().giant()
 94
 95    G_feat["n nodes"] = float(G_cg.number_of_nodes())
 96    print("n nodes", G_feat["n nodes"])
 97    G_feat["n edges"] = float(G_cg.number_of_edges())
 98    print("n edges", G_feat["n edges"])
 99    G_feat["density"] = (
100        2
101        * G_cg.number_of_edges()
102        / (G_cg.number_of_nodes() * (G_cg.number_of_nodes() - 1))
103    )
104    print("density", G_feat["density"])
105
106    # Perform 2-step BFS to calculate diameter
107    # Assumed graph is unweighted and undirected
108    first_vertex_id = G_cg.nodes().iloc[0]
109    print("first_vertex_id", first_vertex_id)
110    bfs_result = cg.bfs(G_cg, first_vertex_id, return_predecessors=False)
111    furthest_node = bfs_result["vertex"].iloc[
112        cp.argmax(cp.array(bfs_result["distance"]))
113    ]
114    bfs_result_from_furthest = cg.bfs(G_cg, furthest_node, return_predecessors=False)
115    G_feat["diameter"] = float(bfs_result_from_furthest["distance"].max())
116
117    # Avg clustering coefficient
118    edges_cudf = G_cg.edges()
119    src_indices = cp.array(edges_cudf["source"])
120    dst_indices = cp.array(edges_cudf["destination"])
121    # Don't count selfloops
122    not_selfloops = src_indices != dst_indices
123    src_indices = src_indices[not_selfloops]
124    dst_indices = dst_indices[not_selfloops]
125    if src_indices.size == 0:
126        G_feat["avg clustering"] = 0
127    else:
128        degrees = cp.bincount(src_indices, minlength=G_cg.number_of_nodes())
129        degrees += cp.bincount(dst_indices, minlength=G_cg.number_of_nodes())
130        triangles = cg.triangle_count(G_cg)
131        degrees = degrees[triangles["vertex"]]
132        counts = cp.array(triangles["counts"])
133        denominators = degrees * (degrees - 1)
134        clustering = 2 * counts / denominators
135        clustering = cp.where(denominators, clustering, 0)
136        assert clustering.ndim == 1
137        G_feat["avg clustering"] = float(clustering.mean())
138
139    # Max closeness centrality
140    max_centrality = 0
141    avg_shortest_path = 0
142    for vertex_id in G_cg.nodes().values_host:
143        shortest_paths = cg.bfs(G_cg, vertex_id)["distance"]
144        shortest_path_sum = cp.sum(shortest_paths)
145        avg_shortest_path += shortest_path_sum / (
146            G_cg.number_of_nodes() * (G_cg.number_of_nodes() - 1)
147        )
148        closeness = (G_cg.number_of_nodes() - 1) / shortest_path_sum
149        if closeness > max_centrality:
150            max_centrality = closeness
151    G_feat["max closeness centrality"] = max_centrality
152    G_feat["max eigenvector centrality"] = cg.eigenvector_centrality(G_cg)[
153        "eigenvector_centrality"
154    ].max()
155
156    # Degree assortativity
157    edges_cudf = G_cg.edges()
158    # print(edges_cudf)
159    degrees = G_cg.degree()
160    degrees_cudf = cudf.merge(
161        edges_cudf, degrees, left_on="source", right_on="vertex", how="left"
162    )
163    degrees_cudf.rename(columns={"degree": "degree_source"}, inplace=True)
164    degrees_cudf = cudf.merge(
165        degrees_cudf, degrees, left_on="destination", right_on="vertex", how="left"
166    )
167    degrees_cudf.rename(columns={"degree": "degree_destination"}, inplace=True)
168    print(edges_cudf)
169    print(degrees_cudf)
170    degree_assortativity = cp.corrcoef(
171        degrees_cudf["degree_source"], degrees_cudf["degree_destination"]
172    )[0, 1]
173    G_feat["degree assortativity"] = float((degree_assortativity + 1) / 2)
174
175    if not skip_clique_num:
176        raise NotImplementedError(
177            "Calculating the largest clique number is not supported on GPU"
178        )
179        # G_feat["max clique number"] = G_ig.clique_number()
180
181    G_feat["n communities"] = cg.louvain(G_cg)[0]["partition"].nunique()
182
183    G_feat["avg path length"] = avg_shortest_path
184    G_feat["max betweenness centrality"] = round(
185        cg.betweenness_centrality(G_cg)["betweenness_centrality"].max(), 15
186    )
187
188    return G_feat
189
190
191def cugraph_calc_graph_features_timed(
192    G_ig: ig.Graph, G_cg: "cugraph.Graph", skip_clique_num: bool = False
193):
194    """
195    Calculate various graph features and the time taken to compute each feature for a given cugraph.Graph object.
196
197    Parameters
198    ----------
199    G_ig : igraph.Graph
200        The input graph for which features are to be calculated.
201    G_cg : cugraph.Graph
202        The input graph for which features are to be calculated.
203    skip_clique_num : bool, optional
204        If True, the calculation of the largest clique number will be skipped. Default is False.
205
206    Returns
207    -------
208    tuple
209        A tuple containing two dictionaries:
210        - G_feat (dict): A dictionary with keys as feature names and values as the computed feature values.
211            Features include:
212            - "total n nodes": Total number of nodes in the graph.
213            - "total n edges": Total number of edges in the graph.
214            - "n nodes": Number of nodes in the largest connected component.
215            - "n edges": Number of edges in the largest connected component.
216            - "density": Density of the graph.
217            - "diameter": Diameter of the graph.
218            - "avg clustering": Average clustering coefficient of the graph.
219            - "max closeness centrality": Maximum closeness centrality in the graph.
220            - "max eigenvector centrality": Maximum eigenvector centrality in the graph.
221            - "degree assortativity": Degree assortativity of the graph (normalized to [0, 1]).
222            - "max clique number": Size of the largest clique in the graph.
223            - "n communities": Number of communities detected using the louvian algorithm.
224            - "avg path length": Average path length in the graph.
225            - "max betweenness centrality": Maximum betweenness centrality in the graph, normalized by the number of possible node pairs.
226
227        - G_time (dict): A dictionary with keys as feature names and values as the time, in seconds, taken to compute each feature.
228
229    Raises
230    ------
231    ValueError
232        If the input is not a cugraph.Graph object.
233
234    Notes
235    -----
236    - The graph is assumed to be undirected and unweighted.
237    - If the graph is not connected, the largest connected component is used for feature calculation.
238    - The diameter is calculated using a 2-step BFS.
239    - GPU implementations are used for all calculations except for clique_num, which is not supported on GPU.
240    - n_communities is calculated using the Louvain algorithm instead of the fast greedy algorithm in igraph.
241    """
242    if cg is None or cudf is None or cp is None:
243        raise RuntimeError(
244            "cugraph, cudf, and cupy must be installed to use GPU feature extractors"
245        ) from _GPU_IMPORT_ERROR
246
247    if not isinstance(G_cg, cg.Graph):
248        raise ValueError("Input must be a cugraph.Graph object")
249
250    if not isinstance(G_ig, ig.Graph):
251        raise ValueError("Input must be an igraph.Graph object")
252
253    G_feat = {}
254    G_time = {}
255    start_time = time.perf_counter()
256    G_feat["total n nodes"] = G_cg.number_of_nodes()
257    G_time["total n nodes"] = time.perf_counter() - start_time
258
259    start_time = time.perf_counter()
260    G_feat["total n edges"] = G_cg.number_of_edges()
261    G_time["total n edges"] = time.perf_counter() - start_time
262
263    connected_components_df = cg.weakly_connected_components(G_cg)
264    if connected_components_df["labels"].nunique() > 1:
265        start_time = time.perf_counter()
266        largest_cc = connected_components_df["labels"].value_counts().idxmax()
267        G_cg = cg.subgraph(G_cg, connected_components_df["labels"] == largest_cc)
268        G_time["connected component"] = time.perf_counter() - start_time
269        G_ig = G_ig.clusters().giant()
270    else:
271        G_time["connected component"] = 0
272
273    start_time = time.perf_counter()
274    G_feat["n nodes"] = float(G_cg.number_of_nodes())
275    G_time["n nodes"] = time.perf_counter() - start_time
276
277    start_time = time.perf_counter()
278    G_feat["n edges"] = float(G_cg.number_of_edges())
279    G_time["n edges"] = time.perf_counter() - start_time
280
281    start_time = time.perf_counter()
282    G_feat["density"] = (
283        2
284        * G_cg.number_of_edges()
285        / (G_cg.number_of_nodes() * (G_cg.number_of_nodes() - 1))
286    )
287    G_time["density"] = time.perf_counter() - start_time
288
289    start_time = time.perf_counter()
290    first_vertex_id = G_cg.nodes().iloc[0]
291    bfs_result = cg.bfs(G_cg, first_vertex_id, return_predecessors=False)
292    furthest_node = bfs_result["vertex"].iloc[
293        cp.argmax(cp.array(bfs_result["distance"]))
294    ]
295    bfs_result_from_furthest = cg.bfs(G_cg, furthest_node, return_predecessors=False)
296    G_feat["diameter"] = float(bfs_result_from_furthest["distance"].max())
297    G_time["diameter"] = time.perf_counter() - start_time
298
299    start_time = time.perf_counter()
300    edges_cudf = G_cg.edges()
301    src_indices = cp.array(edges_cudf["source"])
302    dst_indices = cp.array(edges_cudf["destination"])
303    # Don't count selfloops
304    not_selfloops = src_indices != dst_indices
305    src_indices = src_indices[not_selfloops]
306    dst_indices = dst_indices[not_selfloops]
307    if src_indices.size == 0:
308        G_feat["avg clustering"] = 0
309    else:
310        degrees = cp.bincount(src_indices, minlength=G_cg.number_of_nodes())
311        degrees += cp.bincount(dst_indices, minlength=G_cg.number_of_nodes())
312        triangles = cg.triangle_count(G_cg)
313        degrees = degrees[triangles["vertex"]]
314        counts = cp.array(triangles["counts"])
315        denominators = degrees * (degrees - 1)
316        clustering = 2 * counts / denominators
317        clustering = cp.where(denominators, clustering, 0)
318        assert clustering.ndim == 1
319        G_feat["avg clustering"] = float(clustering.mean())
320    G_time["avg clustering"] = time.perf_counter() - start_time
321
322    start_time = time.perf_counter()
323    max_centrality = 0
324    avg_shortest_path = 0
325    for vertex_id in G_cg.nodes().values_host:
326        shortest_paths = cg.bfs(G_cg, vertex_id)["distance"]
327        shortest_path_sum = cp.sum(shortest_paths)
328        avg_shortest_path += shortest_path_sum / (
329            G_cg.number_of_nodes() * (G_cg.number_of_nodes() - 1)
330        )
331        closeness = (G_cg.number_of_nodes() - 1) / shortest_path_sum
332        if closeness > max_centrality:
333            max_centrality = closeness
334    G_feat["max closeness centrality"] = max_centrality
335    G_time["max closeness centrality"] = time.perf_counter() - start_time
336
337    start_time = time.perf_counter()
338    G_feat["max eigenvector centrality"] = cg.eigenvector_centrality(G_cg)[
339        "eigenvector_centrality"
340    ].max()
341    G_time["max eigenvector centrality"] = time.perf_counter() - start_time
342
343    start_time = time.perf_counter()
344    edges_cudf = G_cg.edges()
345    degrees = G_cg.degree()
346    degrees_cudf = cudf.merge(
347        edges_cudf, degrees, left_on="source", right_on="vertex", how="left"
348    )
349    degrees_cudf.rename(columns={"degree": "degree_source"}, inplace=True)
350    degrees_cudf = cudf.merge(
351        degrees_cudf, degrees, left_on="destination", right_on="vertex", how="left"
352    )
353    degrees_cudf.rename(columns={"degree": "degree_destination"}, inplace=True)
354    degree_assortativity = cp.corrcoef(
355        degrees_cudf["degree_source"], degrees_cudf["degree_destination"]
356    )[0, 1]
357    G_feat["degree assortativity"] = float((degree_assortativity + 1) / 2)
358    G_time["degree assortativity"] = time.perf_counter() - start_time
359
360    if not skip_clique_num:
361        raise NotImplementedError(
362            "Calculating the largest clique number is not supported on GPU"
363        )
364        # G_feat["max clique number"] = G_ig.clique_number()
365        # G_time["max clique number"] = time.perf_counter() - start_time
366
367    start_time = time.perf_counter()
368    G_feat["n communities"] = cg.louvain(G_cg)[0]["partition"].nunique()
369    G_time["n communities"] = time.perf_counter() - start_time
370
371    start_time = time.perf_counter()
372    G_feat["avg path length"] = avg_shortest_path
373    G_time["avg path length"] = time.perf_counter() - start_time
374
375    start_time = time.perf_counter()
376    G_feat["max betweenness centrality"] = round(
377        cg.betweenness_centrality(G_cg)["betweenness_centrality"].max(), 15
378    )
379    G_time["max betweenness centrality"] = time.perf_counter() - start_time
380
381    return G_feat, G_time