DOCSEARCHbyAlgolia
Submit Docs

cuGraph - RAPIDS GPU Graph Analytics

repository·main·Indexed 24 days ago

https://github.com/rapidsai/cugraph

A suite of GPU-accelerated graph analytics libraries within the RAPIDS ecosystem. cuGraph provides high-performance graph algorithms and manipulation capabilities, integrating with cuDF and cuML for GPU data science pipelines. It supports single-GPU and multi-GPU (SNMG and MNMG) execution, including C++ API access via libcugraph for algorithms like PageRank and Louvain community detection, and provides comprehensive benchmarking tools using pytest and Dask.

Tokens
40.6K
Snippets
104
Records
209
Agent score
79%

What's inside cuGraph

  1. Overview of cuGraph

    main

    cuGraph is a collection of GPU-accelerated graph analytics packages. It enables the creation and manipulation of graphs followed by the execution of scalable, fast graph algorithms.

    At the Python layer, cuGraph operates on cuDF GPU DataFrames, allowing seamless data transfer between ETL tasks (cuDF) and machine learning tasks (cuML). The API is designed to be familiar to users of Pandas and NetworkX, supporting data in formats like Pandas DataFrames and NetworkX Graph Objects to minimize porting effort.

  2. Overview of cuGraph Link Analysis Algorithms

    main

    cuGraph provides link analysis algorithms to rank the importance of individual vertices within a graph. The two primary algorithms available are:

    1. PageRank: Determines the importance (centrality) of all vertices based on the relative importance of their neighbors. It is generally more efficient and has lower query times than HITS.
    2. HITS (Hyperlink-Induced Topic Search): Identifies 'hubs' and 'authoritative sources' within the graph. It was originally designed to evaluate citations and reference lists in web pages.

    Note: These notebooks focus on the algorithms themselves; data manipulation before or after the graph analytics is not covered in this specific collection.

  4. Available cuGraph analytics notebooks

    main

    This repository provides Jupyter Notebook examples for various graph analytics categories. Note that these notebooks focus on running the specific algorithm and do not cover general data science preprocessing or post-processing workflows.

    Centrality

    • Centrality: Compute and compare multiple centrality scores.
    • Katz: Compute Katz centrality for every vertex.
    • Betweenness: Compute Edge and Vertex Betweenness centrality.
    • Degree: Compute Degree Centrality for each vertex.
    • Eigenvector: Compute Eigenvector for every vertex.

    Community

    • Louvain and Leiden: Identify clusters using Louvain and Leiden algorithms.
    • ECG: Identify clusters using Ensemble Clustering for Graph.
    • K-Truss: Extract the K-Truss cluster.
    • Spectral-Clustering: Identify clusters using Spectral Clustering (Balanced Cut or Modularity).
    • Induced Subgraph: Compute a subgraph including only specified vertices.
    • Triangle Counting: Count the number of triangles in a graph.

    Components

    • Connected Components: Find weakly and strongly connected components.

    Core

    • K-Core: Extract the K-core cluster.
    • Core Number: Compute the Core number for each vertex.

    Link Analysis

    • Pagerank: Compute PageRank for every vertex.
    • HITS: Compute HITS' Hub and Authority scores.

    Link Prediction

    • Jaccard Similarity: Compute vertex similarity using Jaccard and Weighted Jaccard.
    • Overlap Similarity: Compute vertex similarity using the Overlap Coefficient.

    Sampling

    • Random Walk: Compute Random Walks for various seeds and path lengths.

    Traversal

    • BFS: Compute Breadth First Search paths from a starting vertex.
    • SSSP: Compute Single Source Shortest Path.

    Structure

    • Renumbering: Renumber vertex IDs.
    • Symmetrize: Symmetrize the edges in a graph.

  5. Explore vertex similarity metrics in cuGraph

    main

    cuGraph provides several metrics to measure the similarity between two vertices in a graph. These metrics can be applied to neighboring vertices (default) or second-hop neighbors.

    Supported similarity metrics include:

    • Jaccard Similarity (also called the Jaccard Index): Uses the ratio of the volume of vertex intersection divided by the volume of union.
    • Jaccard Weighted Similarity: An extension of Jaccard Similarity that incorporates edge weights.
    • Overlap Coefficient: Evaluates the neighborhood of vertex pairs by looking at the number of common neighbors (set comparison of neighbor lists).

  7. Explore cuGraph community detection algorithms

    main

    cuGraph provides several algorithms to identify related groups of nodes (communities) or connectivity metrics within a graph. These are categorized by their mathematical approach:

    Clustering Algorithms

    Used to identify tightly connected vertices or clusters:

    • Louvain and Leiden: Identify clusters using modularity-based approaches.
    • Ensemble Clustering (ECG): Uses Louvain and consensus clustering to identify clusters.
    • Spectral Clustering: Uses eigenvalues and the graph Laplacian. This can be implemented via Balanced Cut or Modularity Maximization.

    Clique and Connectivity Algorithms

    • K-Truss: A configurable algorithm that identifies vertices in nearly fully connected cliques (relaxed cliques).
    • Triangle Counting: Quantifies overall graph connectivity by counting the number of size-three cliques (fully connected triples).

    Subgraph Operations

    • Induced Subgraph: Extracts a new subgraph formed by a specific set of vertices, returning only the edges that exist between those vertices.

  8. Explore cuGraph Centrality algorithms

    main

    cuGraph provides several centrality algorithms to identify and quantify the importance of vertices within a graph structure. These algorithms help answer questions regarding vertex degree, path efficiency, and connectivity between important nodes.

    Available centrality measures include:

    • Degree Centrality: Measures importance based on the count of direct connections for each vertex.
    • Betweenness Centrality: Measures the number of shortest paths that pass through a vertex.
    • Eigenvector Centrality: An influence measure that quantifies connectivity to other important vertices.
    • Katz Centrality: Similar to Eigenvector centrality, but adjusted to better measure weakly connected graphs.
    • Pagerank: A link analysis and centrality measure that quantifies incoming links from other central vertices.

  9. Identify connected subgraphs using cuGraph Components Algorithms

    main

    cuGraph provides algorithms to identify connected subgraphs within a graph. These are primarily categorized into two types:

    1. Weakly Connected Components: Finds the largest connected components in a graph by considering both directed and non-directed paths.
    2. Strongly Connected Components: Finds connected components in a graph by considering directed paths only.

    Detailed implementations and demonstrations for these algorithms can be found in the ConnectedComponents.ipynb notebook. Note that these notebooks focus on the graph analytics themselves; data manipulation before or after the analysis is not covered in this specific component set.

  10. Available cuGraph Traversal Algorithms

    main

    cuGraph provides implementations for common graph traversal tasks. The primary algorithms available in the traversal suite are:

    • Breadth First Search (BFS): Traverses all vertices reachable from a seed vertex by exploring one hop at a time.
    • Single Source Shortest Path (SSSP): Computes the shortest path from a single seed vertex to all reachable vertices in the graph.

  11. Organize code using cuGraph namespaces

    main

    To maintain proper visibility and prevent symbol collisions, follow these namespace conventions:

    • Public APIs: All public cuGraph APIs must be placed in the cugraph namespace.
    • Internal (Multi-file): Functions or objects used across multiple translation units should be placed in the cugraph::detail namespace and exposed in an internal header.
    • Internal (Single-file): Functions or objects used only within a single translation unit should be placed in an anonymous namespace within the .cpp file.

    Warning: Never use anonymous namespaces in a header file.

    // Public API
namespace cugraph{
   void public_function(...);
}

// Internal utility used across multiple files
namespace cugraph{
namespace detail{
void reusable_helper_function(...);
} // namespace detail
} // namespace cugraph

// Internal utility used in one file
namespace{
void isolated_helper_function(...);
} // anonymous namespace

  12. Available cuGraph Packages

    main

    cuGraph is composed of several packages catering to different integration needs:

    • cuGraph Python: The high-level API for data scientists, operating on cuDF DataFrames.
    • pylibcugraph: A Python API intended for applications requiring tighter integration with cuGraph at the Python layer with fewer dependencies.
    • libcugraph (C/C++/CUDA): Low-level libraries for integration outside of Python.
    • nx-cugraph: A backend that allows NetworkX to use cuGraph for acceleration.