Exploring Graph Properties and Their Role in Graph Neural Networks

This article builds upon the previous article which introduces Graph Machine Learning and foundations of GNNs. From our previous article, we recall that a graph enables us to visualize complex data structures between entities so we can understand the relationships between these entities. The main topics we will cover in this article are graph properties, graph concepts, and graph algorithms. So after reading this article, you be able to understand what are the different components of graphs, the different types of graphs, and foundational knowledge of how graph algorithms work.

What are the properties of a Graph?

A graph is composed of a set of objects known as vertices or nodes, and connected via edges which serve as links or relations. Graphs are commonly represented using the following notation

G = (V, E)

G is the Graph, V represents the set of vertices, and E is a set of edges. The nodes in a graph represent any objects and the edges are relationships between the nodes. Thus on the map of a country, the cities would be nodes and roads would be edges, for a social network people would represent nodes and their friendship status would be edges. Relationships between nodes define the flow of information from one node to another and to understand the connectivity of nodes via edges, this brings us to the concept of directed and undirected graphs.

Directed and Undirected Graphs

The directed graph also known as a digraph is when an edge connects one node to the other with a particular orientation where information flows from the source node to the destination node. This can be thought of as one-way streets in a city from High Street Center A to High Street Center B. Thus you can only travel from A to B in a car but not from B to A. This is similar to how information flows in a directed graph, in which there is a particular flow orientation of flow of information.

Fig. 1 Directed and Undirected graphs, Image credit simple snippet

Where as in an undirected graph the edge connects both edges with no particular direction, thus information flows in either direction and as result theres no order in which nodes are visited. In this case a two-way streets can be thought of as an undirected graph, in which cars can go in direction and this reflects the flow of information in undirected graphs.

Weighted Graphs

This property of the graph is fundamental in defining the strength of a relationship between nodes and thus is used to associate a cost to an edge between nodes. This can be used to represent factors such as distance between nodes, cost, relationship strength, or cost. In our previous illustration of a road network above this can be used to represent distance between cities. This is commonly associated with binary graphs in which there is an existence or nonexistence of relationships between nodes.

Figure 1.2 Un-weighted and Weighted graph, Image credit Simple snippet

Connected Graphs

A connected graph is formally defined as G if an only if for every pair of vertices U and V in G, there exists an edge from U to V. On the contrary a graph is disconnected if there is two vertices are not connected in the graph. This concept is fundamental in graph theory as it relates to a graph’s structure and function.

Types of graphs

1. Tree: A tree is a connected, undirected graph with no cycles. This means that there is only one path between any two nodes. An example of a tree is a family tree, where each person is connected to their ancestors and descendants, but there are no loops or cycles.
2. Rooted Tree: A rooted tree is a tree with a designated root node, where all other nodes are connected to it by a unique path. An example of a rooted tree is a company’s organizational chart, where the CEO is the root node, and all other employees are connected to the CEO through a unique chain of command.
3. Directed Acyclic Graph (DAG): A DAG is a directed graph with no cycles. This means that the edges can only be traversed in one direction, and there are no loops or cycles. An example of a DAG is a task dependency graph in project management, where each task depends on the completion of other tasks, but there are no circular dependencies.
4. Bipartite Graph: A bipartite graph is a graph where the vertices can be divided into two disjoint sets, such that all edges connect vertices in different sets. An example of a bipartite graph is a job placement graph, where one set of vertices represents job seekers, and the other set represents job openings, and edges represent job applications.
5. Complete Graph: A complete graph is a graph where every pair of vertices is connected by an edge. An example of a complete graph is a social network where everyone is friends with everyone else, and all possible connections are present. Another example is a fully connected computer network, where every device is connected to every other device.

Figure 2.1 Common type of graphs, Image credit Maxime L. (2023)

Fundamental Graph Concepts

Degree of a node (Node degree): This is the simplest node-level statistic to examine which represents the number of edges incident to a node V, and is usually denoted as deg(V). The concept of Node Degree differs between directed and undirected graphs.

• For undirected graphs, the number of edges that are connected to a node represents the degree of the vertex denoted deg(V), and if the node is connected to itself also known as a self-loop this adds two degrees.
• A directed graph is composed of indegree and outdegree. The indegree of a node is the number of edges that point towards it, while the outdegree is the number of edges that start from it. In this case, a self-loop adds one to both the indegree and outdegree. The concept of indegree and out-degree is important in analyzing the flow of information within a directed graph.

Node neighbors: The neighbor of a node is closely related to node degree, as it measures how many neighbors a node has. Though these measures provide us with relative information about the importance of a node in a network, it is thus not sufficient to determine the importance of a node in a network. When two nodes share at least one common neighbor this is referred to as adjacent, which can be combined with neighbors to determine a path between nodes or to identify clusters in a network.

We use degrees and paths to calculate a measure known as centrality which in simple terms is the importance of a node in a network.

Graph measures

As observed above centrality is an important measure that informs us of the importance of a node in a network and is useful in identifying key nodes, and how their connectivity influences the flow of information in a network. Let’s examine the different measures of centrality.

• Degree centrality is defined as the degree of the node, thus a high degree of centrality indicates that a node has more connections to other nodes in the graph and as a result yields more influences in a graph.
• Closeness Centrality is a measure of the proximity of a node to all other nodes in the graph. Thus this translates to the average length of the shortest path between the target node and all other nodes in the graph. This can be thought of as the node in the network which can reach all other nodes in the network faster. For example, if you live in London and use the Tube, you can think of the station that can reach all other stations quicker as the closeness centrality.
• Betweenness centrality is a count of the number of times a node lies on the shortest path between pairs of nodes in a graph. Thus in an arts brokerage network of buyers and sellers, the auction house connects more buyers and sellers with the shortest sale period can be thought of as the bridge between different parts of the graph.

Graph representations

Adjacency Matrix

The adjacency matrix is a common way to represent edges in a graph, using a square matrix where each square represents a row and column a node in the graph. The cell intersection of row i and column j denoted (i, j) indicates if there exists an edge between node i and node j represented by 1, and 0 if there’s no edge. In an unweighted graph, the value of the cell is represented as either 1 (if there exists an edge) or 0 (if there is no edge), while in a weighted graph, the value in the cell can be represented by the weight or cost of the edge between nodes.

An adjacency matrix is a common way to represent a graph in computer science and mathematics. It is a square matrix where each row and column corresponds to a node in the graph, and the value in the cell at the intersection of row i and column j indicates whether there is an edge between node i and node j.

In an unweighted graph, the value in the cell is typically either 1 (if there is an edge) or 0 (if there is no edge). In a weighted graph, the value in the cell can represent the weight or cost of the edge between the nodes.

Figure 2.2 Adjacency Matrix, Undirected and Directed, Image credit Source.com

Advantages of using an adjacency matrix representation:

1. Easy to implement: An adjacency matrix can be easily implemented using a two-dimensional array or a list of lists.
2. Constant time edge queries: Once the matrix is constructed, checking whether there is an edge between two nodes can be done in constant time by simply looking up the corresponding cell in the matrix.
3. Easy to represent weighted graphs: The weight or cost of an edge can be easily represented by storing its value in the corresponding cell of the matrix.

Disadvantages of using an adjacency matrix representation:

1. Space complexity: For a graph with n nodes, an adjacency matrix requires O(n²) space, which can be prohibitive for large graphs.
2. Inefficient for sparse graphs: An adjacency matrix can be inefficient for representing sparse graphs, where the number of edges is much smaller than the number of possible edges. In such cases, most of the cells in the matrix will be empty, leading to wasted space.
3. Slow for adding or removing vertices: Adding or removing a vertex from the graph requires adding or removing a row and column from the matrix, which can be a slow operation for large matrices.

The adjacency matrix representation is a good choice for small to medium-sized graphs where constant time edge queries and easy weight representation are important.

Edge list

An edge list is another way to represent a graph, where a list of pairs of nodes represents an edge between the two nodes.

In an unweighted graph, each pair simply contains the two nodes that are connected by the edge. In a weighted graph, each pair can also include the weight or cost of the edge.

Advantages of using an edge list representation:

1. Space efficiency: For sparse graphs, an edge list can be a more space-efficient representation than an adjacency matrix, as it only stores information about the edges that exist in the graph.
2. Easy to add or remove edges: Adding or removing an edge from the graph can be done simply by adding or removing a pair from the list.
3. Easy to represent weighted graphs: The weight or cost of an edge can be easily represented by storing its value along with the pair of nodes.

Disadvantages of using an edge list representation:

1. Slow edge queries: Checking whether there is an edge between two nodes requires searching through the entire list, which can be slow for large graphs.
2. Difficult to represent certain types of graphs: An edge list is not well-suited for representing certain types of graphs, such as directed graphs with self-loops or multigraphs with multiple edges between the same pair of nodes.
3. Less intuitive: An edge list may be less intuitive to work with than an adjacency matrix, as it does not provide a visual representation of the graph.

An edge list can be a good choice for sparse graphs where space efficiency and ease of adding or removing edges are important.

Adjacency List

An adjacency list is a common way to represent a graph with a collection of lists or arrays using a dictionary, where each list corresponds to a node in the graph as a key and contains the nodes that are adjacent to it as the values in a list.

In an unweighted graph, each list simply contains the nodes that are connected to the corresponding node. In a weighted graph, each list can also include the weight or cost of the edge between the nodes.

Advantages of using an adjacency list representation:

1. Space efficiency: For sparse graphs, an adjacency list can be a more space-efficient representation than an adjacency matrix, as it only stores information about the edges that exist in the graph.
2. Fast edge queries: Checking whether there is an edge between two nodes can be done quickly by simply checking whether one node is in the other node’s list.
3. Easy to add or remove edges: Adding or removing an edge from the graph can be done simply by adding or removing a node from the appropriate list.

Disadvantages of using an adjacency list representation:

1. Difficult to represent weighted graphs: While an adjacency list can represent a weighted graph by including the weight or cost of the edge along with the node in the list, this can make the representation more complex and less intuitive to work with.
2. Difficult to represent certain types of graphs: An adjacency list is not well-suited for representing certain types of graphs, such as directed graphs with self-loops or multigraphs with multiple edges between the same pair of nodes.
3. Less intuitive: An adjacency list may be less intuitive to work with than an adjacency matrix, as it does not provide a visual representation of the graph.

Overall, the choice of graph representation depends on the specific needs of the application. An adjacency list can be a good choice for sparse graphs where fast edge queries and ease of adding or removing edges are important. However, for dense graphs or graphs where ease of representation is important, other representations such as an adjacency matrix or edge list may be more appropriate.

Graph Algorithms

Let’s proceed to explore two fundamental graph traversal algorithms critical in GNNs because they provide a way to traverse and explore the graph structure, which is crucial for many GNN algorithms and would enable us to develop effective and efficient GNN architectures.

Breadth-first Search

BFS provides an efficient way to explore graph structure in a way that the algorithm starts at a root node and ensures that all nodes at a particular level or distance are visited before moving on to nodes at a greater distance. This is important for GNN algorithms that rely on aggregating information from neighboring nodes in a graph, as it ensures that information is propagated evenly across the graph.

The BFS uses a Queue data structure and works by keeping track of visited nodes in a queue of visited nodes by marking them as visited. The algorithm then dequeues the next node in the queue and explores all its neighbors, adding them to the queue if they haven’t been visited yet.

In the context of a mail delivery agent distributing mail in a 3-floor apartment building with 4 apartments on each floor, BFS can be used to find the shortest path from the building entrance to each apartment. The algorithm starts at the entrance and explores all the apartments on the ground floor before moving on to the next floor, using a queue to keep track of the next set of apartments to visit. By exploring the building level by level, BFS ensures that the delivery agent takes the shortest possible route to deliver mail to every apartment.

Fig 1.2 Breadth-first Search (BFS) and Depth-first Search (DFS). Image credit Geeks for Geeks

BFS is important in finding the shortest path between two nodes in an unweighted graph and verifying if a graph is connected. Applications of BFS can be found in web crawlers, social network analysis, and finding the shortest path in a network.

The time complexity of the Breadth-First Search (BFS) algorithm is O(|V| + |E|), where |V| is the number of vertices (or nodes) in the graph and |E| is the number of edges.

This is because, in BFS, each vertex and edge are visited exactly once. During the traversal, each vertex is enqueued and dequeued once, which takes O(|V|) time. Additionally, for each edge, we check if the adjacent vertex has been visited before or not, which takes O(|E|) time. Since we are doing a constant amount of work for each vertex and edge, the total time complexity of BFS is O(|V| + |E|).

Depth-first Search

Depth-first Search (DFS) is a graph traversal algorithm that explores the graph by going as deep as possible along each branch before backtracking. The algorithm starts at a root node and explores each edge to reach a new node, then recursively applies the same process to the new node until it reaches a dead end, at which point it backtracks to explore the next edge.

Here’s a step-by-step breakdown of the DFS algorithm:

1. Choose a starting node (root node) and mark it as visited.
2. Explore one of its unvisited adjacent nodes, mark it as visited, and push it onto a stack.
3. Repeat step 2 until we reach a node that has no unvisited adjacent nodes.
4. If the stack is not empty, pop the top node from the stack and repeat step 2 for that node.
5. If the stack is empty, the algorithm terminates.

DFS can be implemented using either recursion or a stack data structure. The recursive implementation involves making a recursive call for each unvisited adjacent node, while the iterative implementation uses a stack to keep track of the nodes to be explored.

DFS is useful for a variety of graph-related problems, such as finding connected components, detecting cycles, and topological sorting. It has a time complexity of O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges in the graph. This is because each vertex and edge is visited exactly once during the traversal.

Hands-on implementation in Python for BFS and DFS

Requirements; Python > 3.8, NetworkX

Install NetworkX library

pip install networkx

Instantiate a Graph

# Using NetworkX to create a graph
graph = nx.Graph()
graph.add_edges_from([(0, 1), (0, 2), (1, 2), (1, 3), (2, 4)])  # Sample graph edges

print("Breadth-First Search:")
bfs(graph, 0)

print("\nDepth-First Search:")
dfs(graph, 0)

BFS implementation and step-by-step explanation

1. Initialization: Sets up the visited set and the queue.
2. Iteration: While the queue has nodes:

• Remove the first node from the queue.
• Process the node (in this case, print it).
• Add unvisited neighbors to the queue and mark them as visited.

def bfs(graph, start_node):
  """
  Performs Breadth-First Search on a NetworkX graph.

  Args:
    graph: The NetworkX graph to search.
    start_node: The starting node for the search.

  Returns:
    An ordered list of nodes visited in BFS order.
  """  
  visited = set()
  queue = []
  visited.add(start_node)
  queue.append(start_node)

  while queue:
    current_node = queue.pop(0)
    print(current_node, end=" ")

    for neighbor in graph.neighbors(current_node):
      if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

DFS implementation and step by step explanation

1. Initialization Sets up the visited set and the stack.
2. Iteration: While the stack has nodes:

• Remove the last node from the stack.
• Process the node (print it in this case).
• Add unvisited neighbors to the stack and mark them as visited

def dfs(graph, start_node):
  """
  Performs Depth-First Search on a NetworkX graph.

  Args:
    graph: The NetworkX graph to search.
    start_node: The starting node for the search.

  Returns:
    An ordered list of nodes visited in DFS order.
  """  
  visited = set()
  stack = []
  visited.add(start_node)
  stack.append(start_node)

  while stack:
    current_node = stack.pop()
    print(current_node, end=" ")

    for neighbor in graph.neighbors(current_node):
      if neighbor not in visited:
        visited.add(neighbor)
        stack.append(neighbor)

OK guys that’s all for now see you in the next episode where we go through a pioneer ML algorithm on Graphs, called DeepWalk. I can’t help but think that Micheal Jackson’s Moonwalk also inspired ML enthusiasts at the time.

References:

1. Maxime L. (2023) Hands-on Graph Neural Networks Using Python, Chapter 2: Graph Theory for Neural Neural Networks,
2. Geek for Geeks (2021), Breath for search and depth for Search, https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/
3. Simple Snippets (2021), WHat is a graph Data Structure, https://simplesnippets.tech/what-is-a-graph-data-structure-important-graph-terms-properties/
4. Study (2023), Representation of graphs, https://study.com/academy/lesson/adjacency-representations-of-graphs-in-discrete-math.html