The recent artificial intelligence (AI) revolution is the tip of the iceberg of a megatrend that has been impacting the computing industry for decades now. Over time, computing performance has increased exponentially against power consumed and cost; information storage costs have also decreased exponentially. To put this into perspective, while a terabyte of data can be stored in a disk costing around 100 US dollars in 2024, it would have taken more than a million dollars in the early 1990s!

Using computers and their derivative products, such as software, web applications, games, and multimedia content, has become deeply tied to our normal lifestyle. This dependence led to the need for understanding the behavior of all the interacting entities: humans, computer hardware, software such as web applications, and even organizations as a whole. The end goal was to find ways to make interactions more efficient, which could lead to unprecedented business opportunities...

Graphs are a very popular concept in mathematics. In this domain, a common terminology is well accepted. Let’s take a closer look.

Definition and semantics

With the argument being made for graph representations to be a relevant topic for practical problems, let’s take a moment to define what a graph is. A graph is an abstract concept. Mathematically, it’s generally represented as , where is the graph, which contains a set of vertices, , and a set of edges, . Each element of is a tuple, , where , and represents a connection between the two vertices. That’s all there is to the mathematical definition; how you choose to apply semantics to this is completely up to you.

In the example mentioned in the previous section, the users of the social media platform were represented by the vertices, and the connection between the two users was represented by the edges. Also, vertices and edges need not be so homogeneous. Consider the graph...

Several types of graphs have been identified, each with its unique properties, but we’ll focus on the ones that are most popular. Note that these types need not be mutually exclusive, meaning a graph can be labeled as more than one type at a time.

Directed graphs

Graphs are directed when the edges have a one-way relationship between their connecting nodes. There are many scenarios where the relationship that’s represented is unidirectional. In a graph representing a family tree, an edge might represent the relation “is a parent of,” and another might represent the relation “is a pet of.” Such relationships can’t be inverted between the nodes and hold the same meaning.

Bipartite graphs

A bipartite graph is a type of graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. In other words, there are no edges that...

How should we feed graph data into computer programs so that we can apply graph-based algorithms to solve problems? This will be addressed in this section. Each representation has its advantages and disadvantages, and we’ll explore them from the perspective of the time complexity of determining whether an edge exists and updating the graph.

Adjacency matrix

The adjacency matrix aims to record the graph structure via a matrix. A matrix, say , of size is created (where denotes the number of nodes, or mathematically, ). We start with all entries of being 0. Next, if , , then element of is labeled 1. If the graph is undirected, then if , , then both elements of , , and , are labeled 1.

The time complexity to check whether an edge exists in an adjacency matrix is since it just involves checking a particular cell in the matrix. However, adding a new vertex to the graph would be difficult, and depending on the matrix implementation, it might need...

Many computer scientists have etched their names in history by devising elegant solutions to seemingly complex problems involving graphs. However, graphs aren’t just confined to the algorithm books, and graph-based problems are common in the wild. Lots of business problems and scientific research can be boiled down to graph-based problems, on which existing solutions can be implemented to generate the required output. In this section, we’ll talk about the most popular problems in the domain of graphs, a few approaches to solving them, and where these problems are encountered in practical scenarios.

Searching

There are two fundamental approaches when performing a search over a graph: breadth-first and depth-first. Both are means to traverse a graph from a starting point to all nodes that can be reached from the initial node, but the differentiating factor is their approach.

In BFS, the algorithm explores a graph level by level...

Here, we’ll introduce a new concept called representation learning for graphs. Let’s use a small analogy to understand what this means. A typical corporate organization has several entities: employees, IT equipment, offices, and so on. All these entities maintain different types of relationships with each other: employees can be related to each other based on organizational hierarchy; one employee may use several pieces of IT equipment; several pieces of equipment, such as servers, can be networked with each other; employees and equipment can report physically or be located in a particular office, respectively; and so on.

A graph, quite rightly, seems like a natural way to represent this information, like this:

Figure 1.8 – A graph showing the different entities in an organization interacting with each other

Graphs are very visually intuitive. However, performing algorithmic calculations on graphs...

We won’t dive into the details of what GNNs do or how they differ from other popular neural network architectures in this chapter. Here, we’ll merely attempt to explain why there’s a need to study GNNs separately from other deep learning architectures.

Before talking about the differences, we must discuss the similarities. GNNs are an architecture choice that’s specialized for processing graph data and outputting representations or node embeddings. Similar to how convolutional networks are fundamental for reading pixel data, the set of architectures under GNNs are optimized for reading graph data. GNN-based learning tasks follow the same trajectory as other deep learning solutions: to iteratively optimize the parameters of the model so that a loss function can be minimized. In the case of GNNs, the loss function often tries to capture and preserve meaningful information about the graph structure.

Now, let&...

In this chapter, we covered the foundational concepts in graph learning and representation. We began with motivating examples of how graph structures naturally capture relationships between entities, making them a powerful data representation. Then, formal definitions of graphs, common graph types, and key properties were discussed. We also looked at popular graph algorithms such as searching, partitioning, and path optimization, along with their real-world use cases.

A key idea presented here was the need for representation learning on graphs. Converting graph data into vector embeddings allows us to leverage the capabilities of machine learning models. Benefits such as scalability, flexibility, and robustness make graph embeddings an enabling technique.

Finally, we justified the need for specialized GNN architectures. Factors such as irregular structure, permutation invariance, and complex operations such as aggregation and pooling necessitate tailored solutions. GNNs...