Function laplacian_lambda_max

python/dgl/transforms/functional.py:1426–1471

Return the largest eigenvalue of the normalized symmetric Laplacian of a graph. If the graph is batched from multiple graphs, return the list of the largest eigenvalue for each graph instead. Parameters ---------- g : DGLGraph The input graph, it must be a bi-directed h

(g)

def laplacian_lambda_max(g):
    """Return the largest eigenvalue of the normalized symmetric Laplacian of a graph.

    If the graph is batched from multiple graphs, return the list of the largest eigenvalue
    for each graph instead.

    Parameters
    ----------
    g : DGLGraph
        The input graph, it must be a bi-directed homogeneous graph, i.e., every edge
        should have an accompanied reverse edge in the graph.
        The graph can be batched from multiple graphs.

    Returns
    -------
    list[float]
        A list where the i-th item indicates the largest eigenvalue
        of i-th graph in :attr:`g`.

        In the case where the function takes a single graph, it will return a list
        consisting of a single element.

    Examples
    --------
    >>> import dgl
    >>> g = dgl.graph(([0, 1, 2, 3, 4, 0, 1, 2, 3, 4], [1, 2, 3, 4, 0, 4, 0, 1, 2, 3]))
    >>> dgl.laplacian_lambda_max(g)
    [1.809016994374948]
    """
    g_arr = batch.unbatch(g)
    rst = []
    for g_i in g_arr:
        n = g_i.num_nodes()
        adj = g_i.adj_external(
            transpose=True, scipy_fmt=g_i.formats()["created"][0]
        ).astype(float)
        norm = sparse.diags(
            F.asnumpy(g_i.in_degrees()).clip(1) ** -0.5, dtype=float
        )
        laplacian = sparse.eye(n) - norm * adj * norm
        rst.append(
            scipy.sparse.linalg.eigs(
                laplacian, 1, which="LM", return_eigenvectors=False
            )[0].real
        )
    return rst


def metapath_reachable_graph(g, metapath):