2
$\begingroup$

As a mathematics researcher, I've delved into the intriguing realm of graph signal processing, yet I often find myself tangled in mental conflicts about certain aspects of this field. Any insights you could offer to help me navigate through this dilemma would be greatly appreciated.

For instance, let's consider a scenario where G represents a directed graph with an adjacency matrix that can be diagonalized with distinct non-zero eigenvalues, which is highly valued for network analysis.

Before even considering any specific signals on G, we can glean insights from its structure in two ways: firstly, through measures like centrality and clustering, and secondly, by utilizing diagonalization to access a basis consisting of eigenvectors, which I'd like to refer to as "principal signals/harmonics." In digital signal processing (DSP), these principal harmonics are just frequency vectors.

Unlike digital signal processing (DSP), the concept of principal harmonics in the context of graph signal processing (GSP) can be somewhat nebulous. Nonetheless, it's common to consider classification based on this eigenbasis when confronted with a multitude of signals.

It seems that in many cases, the principal harmonics do not offer meaningful insights. This raises the question: how does the concept of principal harmonics contribute to the analysis of signals on the graph?

I'm keen to investigate real-world network examples where the utilization of principal harmonics can be seamlessly feasible and effectively applied.

$\endgroup$

1 Answer 1

2
$\begingroup$

It seems that in many cases, the principal harmonics do not offer meaningful insights.

Recent work on combinatorial Hodge theory has given us interesting ways to form insights on discrete Laplace spectra.

There are properties of the graph spectrum that we should expect to hold independent of the signal on top of it. These are purely topological aspects of the graph. But we should expect these properties to affect our data also.

The systematic theory for studying, when something is purely topological, when something is metric, and how these things interact in the spectrum of the Laplacian is combinatorial Hodge theory. While the core theory is old (Eckmann (1944)) it has seen a resurgence recently.

Both in graph theory and later in graph signal processing there was a grappling for spectral theories often with experimentation or ad-hoc assumptions.

Let $L_0$ be the graph vertex laplacian and $D$ be the standard degree matrix, and $A$ be the vertex adjacency matrix. It is well known that we can define $L_0$ as follows:

$$L_0:=D-A$$

and it has the interpretation of being the finite difference curvature at each vertex. (This can serve as a first argument why Laplacians are better motivated than adjacency matrix for spectral theories.) However it is also known that $L_0$ can also be defined as:

$$L_0:=\partial^T\partial$$

where $\partial$ is the incidence (or boundry) matrix and $\partial^T$ is its adjoint (here notated as the transpose because we are keeping it real). The notation is meant to suggest that $\partial$ is a combinatorial differential, hence this is just the square-differential (i.e. the thing that the Laplacian is in the continuous case!).

The problem here is that we do not "see" the topology. The first step to get there is follow Poincare's discovery that the incidence (now boundary) matrix is key to describing the number of dimensional voids (in 1D loops) in a simplicial complex (including graphs). Poincare realized that loops have no boundary, but if a loop is filled in it must come from a boundary one dimension higher. Hence we get the definition of homology:

$$H_n=\text{ker}\partial_n/\text{img}\partial_{n+1}$$

here written in the now standard "group" language. But we can read this as the kernel (null space) of our incidence matrix over dimension $n$ counts all $n$-loops, but we "subtract" (in the sense of abelian groups) the boundaries (image of the boundary map) of 1 higher dimensional objects. For example, an area will fill a loop formed by 3 edges. Homology is a topological invariant, and applies to graphs.

Let us now define the combinatorial Hodge Laplacian as follows:

$$L_n=L_n^{\text{up}}+L_n^{\text{down}}=\partial_{n+1} \partial_{n+1}^T+\partial_{n}^T \partial_{n}$$

In the case of a graph we should recognize this as the sum of our vertex Laplacian above with the edge Laplacian (that I haven't written down yet). When derived from homology, this makes a lot of sense, because in homology we learn that the is no boundary of a boundary, so one only has to consider information of two dimensionally adjacent boundary maps to get all the homological information. So we know we got everything, and that it contains the homology as topological invariant.

Hodge theorem and decomposition says:

$$H_n\cong\ker L_n$$ $$\text{img}\partial_{n+1}\oplus\text{ker}L_n\oplus\text{img}\partial^T_n$$

The former says that the kernel of the Hodge Laplacian is exactly the homology (number of dimensional voids) of the graph/simplicial complex. Hodge decomposition says that we can decompose into three linear subspaces, two by the image and one being the homology from the kernel!

The cool thing is that Hodge theory tells us how topological information sits inside the Laplacian! It follows immediately that the zero eigenvalue solutions of the spectrum of the Laplacian are purely topological (they are called "harmonic" in Hodge theory, which might be grounds for some confusion in a musical signal processing context).

Even better is that the interpretation here becomes geometric and potentially physical. One should think of this Laplacian (if appropriate) as indeed a discrete version of the Laplacian on a manifold, which is a building block for partial differential equations, dynamical systems and so fourth. Notice that - without the harmonic part - the Hodge decomposition is just the familiar Helmholtz decomposition generalized to all dimensions, so we have a discrete linear theory that behaves just like its differentiable friend in differential geometry, with a discrete version of the standard linear decompositions!

So one gets the familiar connection between finite differencing, and digital filters back in this more general setting. More importantly for the current discussion, the eigenvectors of the spectrum of the Laplacian again becomes just the eigenshapes of the dynamical system modeled by the Laplacian, hence have a direct interpretation.

Two excellent expositions are:

I have given tutorials on topology in signal processing at two conferences. My latter focused on combinatorial Hodge theory and the lecture notes can be found here, with the intent to explicate these ideas with lots of intuition for a signal processing audience (expect lots of typos etc, corrections very welcome!):

  • Essl, Georg. "Combinatorial Hodge Theory in Simplicial Signal Processing - DAFx2023 Lecture Notes." arXiv preprint arXiv:2311.03469 (2023).

Specifically relevant for the current discussion is the section on the Hodge Laplacian on graphs as well the basic discussion about spectral properties.

$\endgroup$
2
  • $\begingroup$ Your insights are genuinely appreciated, and delving into them promises to provide enriching theoretical knowledge. While I value theoretical insights, I am particularly interested in practical, real-world applications. Therefore, I'm hesitant to fully accept it as the correct answer until I find one that addresses my specific concerns. $\endgroup$
    – ABB
    Commented May 2 at 12:53
  • $\begingroup$ @ABB My response should be read as the following: Ad-hoc theory can get in the way of good practical interpretation and insights. In other words I am suggesting it is problematic to disentangle theory from practice here because it's precisely ad-hoc modeling that causes the lack of interpretability in the first place! For example, if one "ad hoc" picks the adjacency matrix to form a spectral theory, one has chosen to throw out interpretation by that choice, because there is no longer an obvious relationship to finite differencing and curvature. $\endgroup$
    – Georg Essl
    Commented May 2 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.