Why Q Knowledge Graph Runs on Sparse Matrices

Q Knowledge Graph (QKG) can rank nodes, reshape graphs into perspectives, and grow neighborhoods around seed entities on graphs with billions of nodes and edges. QKG can manage this at scale because it treats the knowledge graph as sparse matrices, rather than as objects and pointers. Underneath the friendly Python API, this architectural choice turns large-scale graph analytics into linear algebra in a format that computers can store compactly, optimize aggressively, and execute at scale.

You don't need to be an expert in sparse matrices to use QKG. However, understanding makes use of sparse matrices explains why QKG scales so well, and why it's built differently from a traditional graph database. It will also help you use QKG effectively and make the most out of it.

The problem: Graphs don't scale neatly

What is a graph? You could picture it as a big bag of node objects, each holding a list of pointers to its neighbors. This works for a few thousand nodes, but it falls apart at real world scale.

A network resolved from customer data, corporate registries and transaction records can easily reach hundreds of millions - even billions - of nodes. Holding that many objects in memory on one machine can be inefficient, and "walking the graph" by chasing pointers becomes painfully slow when each step is a random jump around memory. Handling big graphs means storing them in a form a computer can process efficiently and at scale. Using linear algebra, it is possible to represent graphs in a matrix form.

For example, take a small graph with four nodes and the edges .

Figure 1 - Example graph with edges (0,1),(0,2),(1,2),(2,3)

The undirected graph with four nodes and edges shown in Fig. 1 can be represented by the following adjacency matrix.

The adjacency matrix is a grid with one row and one column per node, where a 1 in row i, column j means "there's an edge from i to j".

This fully represents the graph structure, i.e. nodes and edges - no information is lost. And once a graph is a matrix, the whole toolbox of linear algebra opens up. Multiplying this matrix by a vector, for instance, is the same as taking one step along every edge at once - a single, batch operation instead of millions of individual pointers.

Many node and relationship types, many matrices

Real knowledge graphs are heterogeneous - they might mix individual, business and account nodes, connected by different relationships like owner, director and transaction. QKG handles this by storing multiple matrices, each representing a specific relationship between two nodes, also known as triplet. A triplet is a typed, directed relationship written as (source type, relationship, target type): individual-owner-account and account-transaction-account are two different triplets, and each gets its own adjacency matrix.

Why sparse is the whole trick

A graph with a million nodes has a million-by-million adjacency matrix, which is a trillion cells in total. Storing a normal (dense, filled with 0s and 1s) matrix in memory is simply too expensive.

In real networks, however, the absence of edges (the 0s in the adjacency matrix) outnumbers their presence (the 1s). Each person knows hundreds of others, not millions. In transaction networks, each account is likely to transact with a small number of counterparties, rather than most accounts worldwide. The number of actual edges is tiny compared to the number of possible ones. In other words, the adjacency matrix is sparse - the majority of its entries are zero.

A sparse matrix exploits this feature by storing only the non-zero entries - the connections that actually exist - and simply assuming everything else is zero. For a realistic graph that's a reduction of several orders of magnitude: from a trillion cells down to the relationships that are actually in your data. The same trick that shrinks the memory also speeds up the maths, because operations only touch the entries that are actually there.

For example, if we consider the star shaped graph below, its adjacency matrix 𝐷, stored in a dense format, would be filled mostly with 0s.

Figure 2 - Star graph with edges (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9), (0,10)

Figure 3 - The adjacency matrix of the graph shown in Figure 2

This representation needs 11 x 11 cells stored, hence 121 entries, mostly filled with 0s. As you can see, the storage cost is quadratic with the number of nodes of the graph.

In a sparse matrix format, for example CSR (Compressed Sparse Row), we would store instead 3 arrays:

𝑆 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

𝐼 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

𝑅 = [0, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

𝑆 represents the non-zero values of the matrix (20 ones); I represents the column indices where these values are stored; 𝑅 represents the row pointers: for each row, it indicates where that row's values begin in the S and I arrays. The entries of row i occupy positions R[i] up to (but not including) R[i+1], so the number of non-zero values in row i is R[i+1] - R[i]. Its length is n + 1 (one entry per row plus a final entry equal to the total number of non-zeros, 20 here).

For example, row 0 spans R[0]=0 to R[1]=10, so its non-zeros are the first 10 entries of S/I (columns 1 to 10); row 1 spans R[1]=10 to R[2]=11, a single entry at column 0.

The storage cost using the sparse format is (2 x nnz + n + 1), where nnz is the number of non-zero values and n is the number of nodes in the graph. Compared to the quadratic cost of the dense format, the sparse format is linear in the number of nodes and non-zero values. In the example above, we only needed to store 52 values instead of 121, but this difference will be more extreme as the graph size increases.

Similarly, and symmetrically to the CSR format, there is the CSC (Compressed Sparse Column) format, which stores the matrix by columns instead of rows. It also holds 3 arrays:

• S holds the non-zero values, read column by column;
• I now holds the row indices of those values (rather than the column indices);
• The pointer array R marks where each column begins in S and I.

CSC is efficient for column-based operations, just as CSR is efficient for row-based ones. QKG handles these formats automatically, hence you don’t have to specify anything.

This is the engine behind Q Knowledge Graph. Representing graphs as sparse matrices is what lets QKG hold enormous networks and run real algorithms over them efficiently, instead of storing graph objects with pointers that would result in out of memory errors.

Algorithms become arithmetic

Once your graph is a set of sparse matrices, many classic graph algorithms turn into short sequences of matrix operations.

Perspectives - Using linear algebra, for example, it’s possible to reshape the graph by collapsing a multi-hop path into a single derived relationship. Chaining individual → owner → account → transaction → account → owner → individual into a direct individual-transaction-individual edge is a sequence of matrix multiplications (one per hop), with the results aggregated together. This lets the same underlying data foundation be reshaped for different business challenges, from large-scale analytics to graph machine learning, without ever duplicating the data. This process is detailed in the following Quantexa patent: Method and System for Generating at Least One Perspective of Knowledge Graph (No. US US18781012), which describes a scalable way of resolving perspectives from even the largest datasets by using lazy evaluation to chain operations together efficiently.

Other QKG algorithms rely on sparse matrices, for example:

Neighborhood expansion - growing outward from a set of seed nodes – this is a matrix operation: by multiplying the seeds’ neighbours vector by the adjacency matrix it’s possible to get all nodes one hop away; doing it twice will yield the nodes two hops away (the neighbors’ neighbors), and so on. The path queries defined in EgoBuilder do exactly this.

PageRank – one of the best known centrality algorithms, originally developed by Google's founders to rank web pages. It works by imagining a random walker hopping along edges, and asking where they spend most of their time. PageRank simply measures where this walker spends most of their time, and ranks the nodes accordingly. Behind the scenes, working this out comes down to repeatedly multiplying a matrix by a vector - and because our matrix is sparse, each of those steps is fast and cheap.

In general with QKG, instead of writing bespoke traversal code for each algorithm, whenever possible, it’s faster and more efficient to express algorithms using matrix-vector operations.

Making it fast: switching backends

Expressing algorithms as linear algebra has one more advantage: you can swap in whatever engine computes that linear algebra fastest, without changing the algorithm.

QKG uses a pluggable backend for its matrix operations:

• SciPy (the default) - a mature, reliable sparse-matrix library, perfect for development and mid-sized graphs.
• GraphBLAS - a specification and library purpose-built for expressing graph algorithms as sparse linear algebra, offering serious acceleration on larger graphs.

Summary

 To put all this together:

• A graph is an adjacency matrix, and a heterogeneous graph is a set of them, one per relationship type.
• Real networks are sparse, so storing only the edges that exist cuts memory by orders of magnitude.
• Algorithms like PageRank, neighborhood expansion and Perspective generation become sequences of sparse matrix operations.
• Those operations can run on an optimised backend, and distribute over Spark, so the same code scales from a laptop to a cluster.

QKG's sparse-matrix architecture is designed for real-world data at enormous scales.  This design is what lets the same graph logic run on a laptop or across a cluster, doing network operations at a scale that would overwhelm a traditional in-memory graph.

If you'd like to see these ideas in action rather than in theory, head back to Creating and exploring a Q Knowledge Graph to run PageRank and generate Perspectives on a graph of your own.