## 2 Background and Related Work
### Graph Signal Processing  
Graph signal processing [18] is a way to systematize information propagation in graphs through their edges. In particular, it starts from a similar definition of adjacency matrices as above \(A=\{1\) if edge \(u,v\) exists, \(0\) otherwise\(\}\), which is modified to be applicable to any type of graphs, not only bipartite ones. It then considers normalizations \(\hat{A}\) that reduce the importance of profligately connected nodes' edges. One popular type of normalization is the symmetric expression  
\[\hat{A}=D^{-1/2}AD^{-1/2} \tag{2}\]  
where \(D\) are diagonal matrices of node degrees with elements \(D[u,v]=\{\sum_{v^{\prime}}A[u,v^{\prime}]\) if \(u=v,0\) otherwise\(\}\). This regards edges \((u,v)\) as bidirectional and re-weighs them by considering both endpoint degrees per \(\hat{A}[u,v]=A[u,v]/\sqrt{D[u,u]D[v,v]}\). Given adjacency matrix normalizations \(\hat{A}\), graph signal processing explores information propagation through graphs by considering graph signals \(h_{0}\) whose elements \(h_{0}[u]\) hold values corresponding to nodes \(u\). These values can be propagated to one-hop neighbors through the matrix-vector multiplication operation \(\hat{A}h_{0}\). This is equivalent to the discrete signal processing shift operator (graph signal processing can model discrete signal processing if points in time are expressed as a line graph whose edges connect points with the next points) and is a type of additive aggregation across graph neighbor values, where neighbors \(v\) of nodes \(u\) are weighted by \(\bar{A}[u,v]\). Iterating the shift operator \(k\) times per \(\bar{A}^{k}h_{0}\) yields graph signal propagations \(k\) hops away from original values. Under this formalization, graph filters are defined as a weighted averaging of multi-hop propagation to obtain filtered signals \(h\) per:  
\[ \begin{split} h=F(\bar{A})h_{0}\\ F(\bar{A})=\sum_{k=0}^{\infty}f_{k}\bar{A}^{k}\end{split}  \tag{3}\]  
where \(F(\cdot)\) is the graph filter and \(f_{k}\) are the weights placed on node values \(k\) hops away. Notably, symmetrically normalized adjacency matrices \(\bar{A}\) can be decomposed into \(\hat{A}=U\Lambda U^{-1}\), where \(\Lambda\) are diagonal matrices of eigenvalues \(\lambda\in[-1,1]\) and \(U\) is the orthonormal base of eigenvectors. Applying graph filters on this decomposition yields:  
\[F(\hat{A})=\sum_{k=0}^{\infty}f_{k}(U\Lambda U^{-1})^{k}=\sum_{k=0}^{\infty}f_ {k}U\Lambda^{k}U^{-1}=UF(\Lambda)U^{-1}\]  
Hence, graph filters transform normalized adjacency matrix eigenvalues from \(\lambda\) to:  
\[F(\lambda)=\sum_{k=0}^{\infty}f_{k}\lambda^{k} \tag{4}\]  
Based on the above properties, spectral graph theory generalizes the concept of Fourier transformations to node-domain graph signals \(h_{0}\) as \(\mathcal{F}\{h_{0}\}=U^{-1}h_{0}\) and the inverse transform as \(\mathcal{F}^{-1}\{h_{0}^{\prime}\}=Uh_{0}^{\prime}\). Analogously to traditional signal processing, graph (convolutional) filtering is defined as element-by-element multiplication \(\odot\) in the Fourier domain. The node-domain equivalent of filtering can be written as convolution with a Fourier-domain filter \(F(\bar{\lambda})\) as:  
\[\mathcal{F}^{-1}\{F(\bar{\lambda})\odot\mathcal{F}\{h_{0}\}\}=\mathcal{F}^{-1 }\{F(\Lambda)\mathcal{F}\{h_{0}\}\}=UF(\Lambda)U^{-1}h_{0}=F(\hat{A})h_{0}\]  
where \(\bar{\lambda}\) is the vector of the adjacency matrix eigenvalues and is considered its spectrum, whilst \(F(\bar{\lambda})\) is applied on all spectrum dimensions. Since Fourier-domain operations can be translated into node-domain filtering computations, graph filters are easy to implement [19] and require only an informed assumption of how the normalized adjacency matrix's spectrum needs to be transformed.