What is Graph

#Graph #Basics

Graph

A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$,

$$ \mathcal G = ( \mathcal V, \mathcal E). $$

Edges

Edges are relations between nodes. For $u\in \mathcal V$ and $v\in \mathcal V$, if there is an edge between them, then $(u, v)\in \mathcal E$.

Representations of Graph

There are different representations of a graph.

Adjacency Matrix

A adjacency matrix of a graph represents the nodes using row and column indices and edges using elements of the matrix.

For simple graph, the adjacency matrix is rank two and dimension $\lvert \mathcal V \rvert \times \lvert \mathcal V \rvert$. For edge $(u, v)\in \mathcal E$, it is represented by the matrix element $\mathbf A[u,v]=1$.

See Sanchez-Lengeling, 2021 for an interactive example1.

Laplacians

Laplacians are transformations of the adjacency matrix but provides a lot more convenience for analysis.

Multi-Relational Graph

A graph may have different types of edges, $\tau\in \mathcal R$, where $R$ is a set of types of relations. A multi-relational graph is then

$$ \begin{align} u &\in \mathcal V \\ v &\in \mathcal V \\ \tau &\in \mathcal R \\ (u, \tau, v) &\in \mathcal E. \end{align} $$

Adjacency Matrix for Multi-relation Graph

For multi-relational graph, it can have more ranks and the dimension can be $\lvert \mathcal V \rvert \times \lvert \mathcal V \rvert \times \lvert \mathcal R\rvert$, where $\mathcal R$ represents the types of relations.

type adjacency matrix
$\tau=\tau_1$ $A_{\tau=\tau_1}$
$\tau=\tau_2$ $A_{\tau=\tau_2}$
$\cdots$ $\cdots$

Two popular examples:

  • heterogeneous
    • multipartite
  • multiplex

Heterogeneous

Nodes are subsets without intersections, $\mathcal V = \mathcal V_1\cup \mathcal V_2 \cdots \mathcal V_k$ and $\mathcal V_i \cap \mathcal V_j = \emptyset$ for $\forall i\neq j$.

Heterogeneous graph example. A visualization of the example in Hamilton2020.

Heterogeneous graph example. A visualization of the example in Hamilton2020.

The famous multi-partite graph is an example of heterogeneous graph.

Movie and User Bi-partite Graph

For a website that hosts a movie database and a user database, the relation about which user watched which movie is a bi-partite graph.

Mutiplex

The edges represent different

Multiplex graph example.

Multiplex graph example.


  1. Sanchez-Lengeling2021 Sanchez-Lengeling B, Reif E, Pearce A, Wiltschko AB. A Gentle Introduction to Graph Neural Networks. Distill. 2021;6. doi:10.23915/distill.00033  ↩︎

Published: by ;

L Ma (2021). 'What is Graph', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/what-is-graph/.

Current Ref:

  • wiki/graph/basics/what-is-graph.md