Extended Adjacency and Scale-dependent Graph Fourier Transform via Diffusion Distances

Vitor Rosa Meireles Elias, Wallace Alves Martins, Stefan Werner

Research output: Contribution to journalArticleScientificpeer-review

38 Downloads (Pure)

Abstract

This paper proposes the augmentation of the adjacency model of networks for graph signal processing. It is assumed that no information about the network is available, apart from the initial adjacency matrix. In the proposed model, additional edges are created according to a Markov relation imposed between nodes. This information is incorporated into the extended-adjacency matrix as a function of the diffusion distance between nodes. The diffusion distance measures similarities between nodes at a certain diffusion scale or time, and is a metric adopted from diffusion maps. Similarly, the proposed extended-adjacency matrix depends on the diffusion scale, which enables the definition of a scale-dependent graph Fourier transform. We conduct theoretical analyses of both the extended adjacency and the corresponding graph Fourier transform and show that different diffusion scales lead to different graph-frequency perspectives. At different scales, the transform discriminates shifted ranges of signal variations across the graph, revealing more information on the graph signal when compared to traditional approaches. The scale-dependent graph Fourier transform is applied for anomaly detection and is shown to outperform the conventional graph Fourier transform.

Original languageEnglish
Pages (from-to)592 - 604
Number of pages13
JournalIEEE Transactions on Signal and Information Processing over Networks
Volume6
DOIs
Publication statusPublished - 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • diffusion distances
  • diffusion maps
  • extended adjacency
  • Fourier transforms
  • graph signal processing
  • Laplace equations
  • Markov processes
  • scale-dependent graph Fourier transform
  • Sensors
  • Signal processing
  • Symmetric matrices
  • Tools

Fingerprint Dive into the research topics of 'Extended Adjacency and Scale-dependent Graph Fourier Transform via Diffusion Distances'. Together they form a unique fingerprint.

Cite this