Linear Algebra Explained Through Graph Theory
Explaining the fundamentals of linear algebra intuitively through graph theory
Mathematics is a difficult subject to learn: it is very broad and has a variety of applications across many domains. Linear algebra, a subsection of mathematics, in particular can be very tricky to understand and apply. In my opinion, many of the courses and open source tools teaching linear algebra are very computationally intensive, which can become very difficult to understand for visual learners like myself. For new individuals who are getting into mathematics or data in general, this can be problematic because linear algebra has a variety of applications in data science and machine learning—to name a few: natural language processing, recommendation systems, dimensionality reduction, neural networks, etc. Having a strong foundational understanding of linear algebra would aid their understanding of commonly used methods of machine learning.
This article will focus on a visual understanding of the computations of linear algebra through the use of graphs. I will cover many of the core concepts like matrix addition, subtraction, multiplication, division, transpose etc. These are very fundamental and common concepts of linear algebra, these concepts also come up quite often when it comes to machine learning. The following is the outline of the article :
Table of Contents
- Introduction to Graphs and Linear Algebra
- Adjacency Matrix of a Graph
- Arithmetic
- Addition / Subtraction
- Multiplication / Division
- Transpose
- Linear Combinations
- Applications of Linear Algebra in Machine Learning
- Concluding Remarks
- Resources
Introduction to Graphs and Linear Algebra
Graph theory and linear algebra are used hand in hand, there’s an entire subcategory of mathematics denoted algebraic graph theory which uses algebraic methods to solve problems regarding graphs. These algebraic methods often include a variety of linear algebra.
Adjacency Matrix of a Graph
The core concept used throughout this article will be the adjacency matrix. An adjacency matrix is one where you are able to convert a graph G into a matrix and vice versa. The adjacency matrix is always symmetric, and consists of elements which indicate the connection between pairs of adjacent vertices in the graph G. The conversion of a graph to its associated adjacency matrix can easily be illustrated in the diagram below.
There would be values on the diagonal of the matrix in the image shown above if the graph G had any self loops. Adjacency matrices encapsulate the structure and relationships of a graph. The adjacency matrix can be represented as a sparse or dense matrix, making it very computationally efficient to run experiments on the graph. For this reason, adjacency matrices are one of the most common ways of representing graphs [1]. Throughout this article, I will apply basic concepts covered in linear algebra to the adjacency matrix and show how the graph associated to that matrix changes accordingly.
Arithmetics
Conducting arithmetics on matrices are quite simple and intuitive to understand for most individuals. The simplest way to understand graph based arithmetic would be through a weighted graph. Through generic arithmetics covered in linear algebra, the graphs associated with those arithmetics could drastically change. New edges could be formed or removed, the impact associated with those edges would increase or decrease in significance. The graph could go from being a connected network to a disconnected one. The examples illustrated below might provide a better visual understanding of matrix arithmetics on graphs.
Addition / Subtraction
Although this example only covered addition, it should be quite intuitively simple to see how subtraction would impact the graph.
Multiplication / Division
Dot Product
The dot product is a difficult concept to visually understand, especially when the dimensions of the matrices you are multiplying are large. When investigating the image shown below, keep in mind that when taking the dot product of two graphs it almost surely becomes a directed graph. The image below you will see the result of taking the dot product of two graphs (adjacency matrices) which are undirected and its resulting directed graph. In the simplest form, a graph is undirected if it contains no duplicate edges and loops. This implies that the adjacency matrix of undirected graphs will have a zero diagonal and the transpose of the matrix M^T is equivalent to M.
As you will see, directed graphs are very different. A directed graph is one which consists of directed edges, implying that you can only go from one node to another if there is a directed edge going to that node. The directions are generally indicated through with an arrow on the edge.
The resulting graph from the dot product completely changes how one might interpret the graph. The dot product of two (relatively) simple graphs results in something quite messy. As you can see you can traverse through various nodes with different weights.
Transpose
Traditionally, when individuals state to transpose a matrix, all you’re doing is flipping the matrix over it’s diagonal. But how does this impact the associated graph?
The simplest visual understanding behind what transposing does is through looking at a directed graph. As covered above, a graph G is directed when one node points to another via an edge, then the transpose of that graph G would simply indicate that the direction is swapped. This might be a bit more of an intuitive understanding of how transposing a matrix impacts a network.
Linear Combinations
Linear combinations of graphs are very similar to the linear combinations of vectors. A linear combination can be outlined by the following definition:
An expression which consists of a set of terms and constants. The expression is the sum of the product of each term multiplied by its associated constant. It can be mathematically represented by the following formulation:
Constants : a, b, c, ... z
Terms : G1, G2, G3, ... Gn
LC = a*G1 + b*G2 + c*G3 + ... + z*GnNow, when thinking of linear combinations in the context of graphs, assume each vector is now a symmetric matrix corresponding to a graph. Then we can visually see the impact each change is making when combining networks. It can be visually seen below:
Applications of Linear Algebra in Machine Learning
There are a variety of applications of linear algebra in machine learning. Linear algebra comes up in most steps of the data science pipeline, from data preprocessing and feature engineering to modelling. Concepts such as one hot encoding, and a variety of dimensionality reduction models fundamentally stem from linear algebra. Models like PCA intuitively use the ideas behind linear combinations and eigenvectors to reduce the input data while trying to minimize the information lost.
More complicated applications of linear algebra in machine learning come in the forms of recommendation systems and deep learning. All forms of recommendation systems use a variety of linear algebra to solve the given problem proposed. Content-based, collaborative filtering and hybrid approaches to solving problems in recommendation systems use common concepts in linear algebra like dot products, cosine similarity, euclidean distance, matrix factorization, etc. Even complex approaches in recommendation systems like link prediction fundamentally use a large amount of linear algebra to identify missing edges in a network (what pairs of nodes in a network should have an edge but currently do not?).
Deep learning in its nature is linear algebra, from the data structures used to define neural networks to its approaches in training & testing data. A common term in deep learning is a tensor where a tensor is essentially a matrix with more than 2 dimensions.
Concluding Remarks
I hoped that this article provided you more insights, intuition and connection behind the mathematics of graph theory and linear algebra. These are concepts which often come up behind the scenes in a variety of machine learning and data science applications. Having a more rigid and foundational understanding of these concepts would most likely aid you in learning a variety of machine learning related concepts.
Resources
- [1] http://www.math.utah.edu/~gustafso/s2017/2270/projects-2017/dylanJohnson/Dylan%20Johnson%20Graph%20Theory%20and%20Linear%20Algebra.pdf
- [2] Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and Its Applications, 218: 213–224, doi:10.1016/0024–3795(93)00173-W, MR 1324059. See in particular the discussion on p. 218.
If you enjoyed this article, here is a list of other articles I’ve written which you might also enjoy.
Recommendation Systems Explained
Dynamic Time Warping Explained
Share This Article
Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program.
Write for TDS
