Function edge_label_informativeness

python/dgl/label_informativeness.py:22–110

r"""Label informativeness (:math:`\mathrm{LI}`) is a characteristic of labeled graphs proposed in the `Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond `__ Label informativeness shows how much informa

(graph, y, eps=1e-8)

def edge_label_informativeness(graph, y, eps=1e-8):
    r"""Label informativeness (:math:`\mathrm{LI}`) is a characteristic of
    labeled graphs proposed in the `Characterizing Graph Datasets for Node
    Classification: Homophily-Heterophily Dichotomy and Beyond
    <https://arxiv.org/abs/2209.06177>`__

    Label informativeness shows how much information about a node&#x27;s label we
    get from knowing its neighbor&#x27;s label. Formally, assume that we sample an
    edge :math:`(\xi,\eta) \in E`. The class labels of nodes :math:`\xi` and
    :math:`\eta` are then random variables :math:`y_\xi` and :math:`y_\eta`.
    We want to measure the amount of knowledge the label :math:`y_\eta` gives
    for predicting :math:`y_\xi`. The entropy :math:`H(y_\xi)` measures the
    `hardness&#x27; of predicting the label of :math:`\xi` without knowing
    :math:`y_\eta`. Given :math:`y_\eta`, this value is reduced to the
    conditional entropy :math:`H(y_\xi|y_\eta)`. In other words, :math:`y_\eta`
    reveals :math:`I(y_\xi,y_\eta) = H(y_\xi) - H(y_\xi|y_\eta)` information
    about the label. To make the obtained quantity comparable across different
    datasets, label informativeness is defined as the normalized mutual
    information of :math:`y_{\xi}` and :math:`y_{\eta}`:

    .. math::
      \mathrm{LI} = \frac{I(y_\xi,y_\eta)}{H(y_\xi)}

    Depending on the distribution used for sampling an edge
    :math:`(\xi, \eta)`, several variants of label informativeness can be
    obtained. Two of them are particularly intuitive: in edge label
    informativeness (:math:`\mathrm{LI}_{edge}`), edges are sampled uniformly
    at random, and in node label informativeness (:math:`\mathrm{LI}_{node}`),
    first a node is sampled uniformly at random and then an edge incident to it
    is sampled uniformly at random. These two versions of label informativeness
    differ in how they weight high/low-degree nodes. In edge label
    informativeness, averaging is over the edges, thus high-degree nodes are
    given more weight. In node label informativeness, averaging is over the
    nodes, so all nodes are weighted equally.

    This function computes edge label informativeness.

    Parameters
    ----------
    graph : DGLGraph
        The graph.
    y : torch.Tensor
        The node labels, which is a tensor of shape (|V|).
    eps : float, optional
        A small constant for numerical stability. (default: 1e-8)

    Returns
    -------
    float
        The edge label informativeness value.

    Examples
    --------
    >>> import dgl
    >>> import torch

    >>> graph = dgl.graph(([0, 1, 2, 2, 3, 4], [1, 2, 0, 3, 4, 5]))
    >>> y = torch.tensor([0, 0, 0, 0, 1, 1])