# 1.1 Some Basic Definitions about Graphs (Graphs 101)ΒΆ

A graph \(G=(V, E)\) is a structure used to represent entities and their relations. It consists of
two sets β the set of nodes \(V\) (also called vertices) and the set of edges \(E\) (also called
arcs). An edge \((u, v) \in E\) connecting a pair of nodes \(u\) and \(v\) indicates that there is a
relation between them. The relation can either be undirected, e.g., capturing symmetric
relations between nodes, or directed, capturing asymmetric relations. For example, if a
graph is used to model the friendships relations of people in a social network, then the edges
will be undirected as friendship is mutual; however, if the graph is used to model how people
follow each other on Twitter, then the edges are directed. Depending on the edgesβ
directionality, a graph can be *directed* or *undirected*.

Graphs can be *weighted* or *unweighted*. In a weighted graph, each edge is associated with a
scalar weight. For example, such weights might represent lengths or connectivity strengths.

Graphs can also be either *homogeneous* or *heterogeneous*. In a homogeneous graph, all
the nodes represent instances of the same type and all the edges represent relations of the
same type. For instance, a social network is a graph consisting of people and their
connections, representing the same entity type.

In contrast, in a heterogeneous graph, the nodes and edges can be of different types. For instance, the graph encoding a marketplace will have buyer, seller, and product nodes that are connected via wants-to-buy, has-bought, is-customer-of, and is-selling edges. The bipartite graph is a special, commonly-used type of heterogeneous graph, where edges exist between nodes of two different types. For example, in a recommender system, one can use a bipartite graph to represent the interactions between users and items. For working with heterogeneous graphs in DGL, see 1.5 Heterogeneous Graphs.

Multigraphs are graphs that can have multiple (directed) edges between the same pair of nodes, including self loops. For instance, two authors can coauthor a paper in different years, resulting in edges with different features.