Transform-based graph topology similarity metrics

ORCID Identifiers

0000-0002-0975-1877

Document Type

Article

Source of Publication

Neural Computing and Applications

Publication Date

7-9-2021

Abstract

Graph signal processing has recently emerged as a field with applications across a broad spectrum of fields including brain connectivity networks, logistics and supply chains, social media, computational aesthetics, and transportation networks. In this paradigm, signal processing methodologies are applied to the adjacency matrix, seen as a two-dimensional signal. Fundamental operations of this type include graph sampling, the graph Laplace transform, and graph spectrum estimation. In this context, topology similarity metrics allow meaningful and efficient comparisons between pairs of graphs or along evolving graph sequences. In turn, such metrics can be the algorithmic cornerstone of graph clustering schemes. Major advantages of relying on existing signal processing kernels include parallelism, scalability, and numerical stability. This work presents a scheme for training a tensor stack network to estimate the topological correlation coefficient between two graph adjacency matrices compressed with the two-dimensional discrete cosine transform, augmenting thus the indirect decompression with knowledge stored in the network. The results from three benchmark graph sequences are encouraging in terms of mean square error and complexity especially for graph sequences. An additional key point is the independence of the proposed method from the underlying domain semantics. This is primarily achieved by focusing on higher-order structural graph patterns.

ISSN

1433-3058

Publisher

Springer Nature

Disciplines

Computer Sciences

Keywords

Graph signal processing, Graph topology, Signal processing kernels, Discrete cosine transform, Tensor algebra, Tensor stack network, Julia

Scopus ID

85110317571

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS