To understand how the triangle counting can be represented by a polynomial, which is the form the sum check protocol described in Sum check - overview requires, it would be helpful to understand how the triangles can be represented using a adjacency matrix beforehand. The intuition around its matrix representation is fundamental to understanding its polynomial form from my view.
This post focuses explaining how to counting triangles in adjacency matrix, laying down the connection to the Sum check - benchmarks in which triangle counting will be applied into sum check protocol.
Below outlines the features of triangle counting using operations under matrix structure.
Adjacency matrix is an representation of undirected graph to denote relationship between vertices and edges.
Before we dive into understanding how the graph works at low level, here are some high level implications for the triangle counting use case.
- The graph by an adjacency matrix by itself represents one walk between vertices.
- Having an adjacency matrix multiplied with itself, resulting in
, it is representing two walks between vertices.
- Multiplying itself two times, resulting in
, it is representing three walks between vertices.
- The values in the trace of the resulted matrix
are the number of round trips. Summing them up and divide by 6, equals to the total number of triangles that can be found in the graph. The following will try to explain why it is the number 6.
Firstly, let's take a look at the polynomial representing triangle counting.
But what does this polynomial implies? What does
To clarify these questions, it would be helpful to take a look at the following examples of what they represent for
This represents the counts of trips having one walk.
Corresponding, the following graph illustrates one walk paths.
flowchart LR 1 --> 2 & 3 2 --> 4 2 --> 3 3 --> 4
Since the adjacency matrix is symmetry, so the arrow directions can be reversed.
This represents the counts of trips having two walks.
Round trip example
Corresponding, the following graph illustrates two walk paths for
flowchart LR 1 --> 2 & 3--> 1
The example above also can be represented by
Intermediate trip example
The values other than the ones from the trace of the matrix represent the number intermediate trips, instead of round trips.
flowchart LR 2 --> 1 & 4--> 3
This represents the number of trips having three walks. When it is a count for round trip, the value in the trace of
Round trip example
For the point
flowchart LR 2 --> 1 & 3 & 4--> 2
Seemingly, there only 3 round trips with two walks around vertice 2. But keep in mind the
With the trips represented by
flowchart LR 2 --> 1 --> 3 --> 2
flowchart LR 2 --> 4 --> 3 --> 2
flowchart LR 2 --> 3 --> 1 --> 2
flowchart LR 2 --> 3 --> 4 --> 2
Thus, there are total 4 undirected round trips as the
Based on the method we observed in counting the round trips, to calculate the total number of triangles, it just need to sum up the values in the trace of
Because the adjacency matrix in our example is symmetry, so is undirected. The result
The implication of summing up the trace values of matrix multiplication result
In the Sum check - benchmarks, we will explain how this polynomial can be applied to the sum check protocol.