"""Utils for tracking graph homophily and heterophily"""
# pylint: disable=W0611
from . import function as fn, to_bidirected
try:
import torch
except ImportError:
HAS_TORCH = False
else:
HAS_TORCH = True
__all__ = [
"node_homophily",
"edge_homophily",
"linkx_homophily",
"adjusted_homophily",
]
def check_pytorch():
"""Check if PyTorch is the backend."""
if HAS_TORCH is False:
raise ModuleNotFoundError(
"This function requires PyTorch to be the backend."
)
def get_long_edges(graph):
"""Internal function for getting the edges of a graph as long tensors."""
src, dst = graph.edges()
return src.long(), dst.long()
[docs]def node_homophily(graph, y):
r"""Homophily measure from `Geom-GCN: Geometric Graph Convolutional
Networks <https://arxiv.org/abs/2002.05287>`__
We follow the practice of a later paper `Large Scale Learning on
Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
<https://arxiv.org/abs/2110.14446>`__ to call it node homophily.
Mathematically it is defined as follows:
.. math::
\frac{1}{|\mathcal{V}|} \sum_{v \in \mathcal{V}} \frac{ | \{u
\in \mathcal{N}(v): y_v = y_u \} | } { |\mathcal{N}(v)| },
where :math:`\mathcal{V}` is the set of nodes, :math:`\mathcal{N}(v)` is
the predecessors of node :math:`v`, and :math:`y_v` is the class of node
:math:`v`.
Parameters
----------
graph : DGLGraph
The graph.
y : torch.Tensor
The node labels, which is a tensor of shape (|V|).
Returns
-------
float
The node homophily value.
Examples
--------
>>> import dgl
>>> import torch
>>> graph = dgl.graph(([1, 2, 0, 4], [0, 1, 2, 3]))
>>> y = torch.tensor([0, 0, 0, 0, 1])
>>> dgl.node_homophily(graph, y)
0.6000000238418579
"""
check_pytorch()
with graph.local_scope():
# Handle the case where graph is of dtype int32.
src, dst = get_long_edges(graph)
# Compute y_v = y_u for all edges.
graph.edata["same_class"] = (y[src] == y[dst]).float()
graph.update_all(
fn.copy_e("same_class", "m"), fn.mean("m", "same_class_deg")
)
return graph.ndata["same_class_deg"].mean(dim=0).item()
[docs]def edge_homophily(graph, y):
r"""Homophily measure from `Beyond Homophily in Graph Neural Networks:
Current Limitations and Effective Designs
<https://arxiv.org/abs/2006.11468>`__
Mathematically it is defined as follows:
.. math::
\frac{| \{ (u,v) : (u,v) \in \mathcal{E} \wedge y_u = y_v \} | }
{|\mathcal{E}|},
where :math:`\mathcal{E}` is the set of edges, and :math:`y_u` is the class
of node :math:`u`.
Parameters
----------
graph : DGLGraph
The graph.
y : torch.Tensor
The node labels, which is a tensor of shape (|V|).
Returns
-------
float
The edge homophily ratio value.
Examples
--------
>>> import dgl
>>> import torch
>>> graph = dgl.graph(([1, 2, 0, 4], [0, 1, 2, 3]))
>>> y = torch.tensor([0, 0, 0, 0, 1])
>>> dgl.edge_homophily(graph, y)
0.75
"""
check_pytorch()
with graph.local_scope():
# Handle the case where graph is of dtype int32.
src, dst = get_long_edges(graph)
# Compute y_v = y_u for all edges.
edge_indicator = (y[src] == y[dst]).float()
return edge_indicator.mean(dim=0).item()
[docs]def linkx_homophily(graph, y):
r"""Homophily measure from `Large Scale Learning on Non-Homophilous Graphs:
New Benchmarks and Strong Simple Methods
<https://arxiv.org/abs/2110.14446>`__
Mathematically it is defined as follows:
.. math::
\frac{1}{C-1} \sum_{k=1}^{C} \max \left(0, \frac{\sum_{v\in C_k}|\{u\in
\mathcal{N}(v): y_v = y_u \}|}{\sum_{v\in C_k}|\mathcal{N}(v)|} -
\frac{|\mathcal{C}_k|}{|\mathcal{V}|} \right),
where :math:`C` is the number of node classes, :math:`C_k` is the set of
nodes that belong to class k, :math:`\mathcal{N}(v)` are the predecessors
of node :math:`v`, :math:`y_v` is the class of node :math:`v`, and
:math:`\mathcal{V}` is the set of nodes.
Parameters
----------
graph : DGLGraph
The graph.
y : torch.Tensor
The node labels, which is a tensor of shape (|V|).
Returns
-------
float
The homophily value.
Examples
--------
>>> import dgl
>>> import torch
>>> graph = dgl.graph(([0, 1, 2, 3], [1, 2, 0, 4]))
>>> y = torch.tensor([0, 0, 0, 0, 1])
>>> dgl.linkx_homophily(graph, y)
0.19999998807907104
"""
check_pytorch()
with graph.local_scope():
# Compute |{u\in N(v): y_v = y_u}| for each node v.
# Handle the case where graph is of dtype int32.
src, dst = get_long_edges(graph)
# Compute y_v = y_u for all edges.
graph.edata["same_class"] = (y[src] == y[dst]).float()
graph.update_all(
fn.copy_e("same_class", "m"), fn.sum("m", "same_class_deg")
)
deg = graph.in_degrees().float()
num_nodes = graph.num_nodes()
num_classes = y.max(dim=0).values.item() + 1
value = torch.tensor(0.0).to(graph.device)
for k in range(num_classes):
# Get the nodes that belong to class k.
class_mask = y == k
same_class_deg_k = graph.ndata["same_class_deg"][class_mask].sum()
deg_k = deg[class_mask].sum()
num_nodes_k = class_mask.sum()
value += max(0, same_class_deg_k / deg_k - num_nodes_k / num_nodes)
return value.item() / (num_classes - 1)
[docs]def adjusted_homophily(graph, y):
r"""Homophily measure recommended in `Characterizing Graph Datasets for
Node Classification: Homophily-Heterophily Dichotomy and Beyond
<https://arxiv.org/abs/2209.06177>`__
Adjusted homophily is edge homophily adjusted for the expected number of
edges connecting nodes with the same class label (taking into account the
number of classes, their sizes, and the distribution of node degrees among
them).
Mathematically it is defined as follows:
.. math::
\frac{h_{edge} - \sum_{k=1}^C \bar{p}(k)^2}
{1 - \sum_{k=1}^C \bar{p}(k)^2},
where :math:`h_{edge}` denotes edge homophily, :math:`C` denotes the
number of classes, and :math:`\bar{p}(\cdot)` is the empirical
degree-weighted distribution of classes:
:math:`\bar{p}(k) = \frac{\sum_{v\,:\,y_v = k} d(v)}{2|E|}`,
where :math:`d(v)` is the degree of node :math:`v`.
It has been shown that adjusted homophily satisifes more desirable
properties than other homophily measures, which makes it appropriate for
comparing the levels of homophily across datasets with different number
of classes, different class sizes, andd different degree distributions
among classes.
Adjusted homophily can be negative. If adjusted homophily is zero, then
the edge pattern in the graph is independent of node class labels. If it
is positive, then the nodes in the graph tend to connect to nodes of the
same class more often, and if it is negative, than the nodes in the graph
tend to connect to nodes of different classes more often (compared to the
null model where edges are independent of node class labels).
Parameters
----------
graph : DGLGraph
The graph.
y : torch.Tensor
The node labels, which is a tensor of shape (|V|).
Returns
-------
float
The adjusted homophily value.
Examples
--------
>>> import dgl
>>> import torch
>>> graph = dgl.graph(([1, 2, 0, 4], [0, 1, 2, 3]))
>>> y = torch.tensor([0, 0, 0, 0, 1])
>>> dgl.adjusted_homophily(graph, y)
-0.1428571492433548
"""
check_pytorch()
graph = to_bidirected(graph.cpu()).to(y.device)
h_edge = edge_homophily(graph, y)
degrees = graph.in_degrees().float()
num_classes = y.max().item() + 1
degree_sums = torch.zeros(num_classes).to(y.device)
degree_sums.index_add_(dim=0, index=y, source=degrees)
adjust = (degree_sums**2).sum() / graph.num_edges() ** 2
h_adj = (h_edge - adjust) / (1 - adjust)
return h_adj.item()