Shift-enabled graphs: Graphs where shift-invariant filters are representable as polynomials of shift operations
In digital signal processing, shift-invariant filters can be represented as a polynomial expansion of a shift operation,that is, the Z-transform representation. When extended to graph signal processing (GSP), this would mean that a shift-invariant graph filter can be represented as a polynomial of the adjacency (shift) matrix of the graph. However, the characteristic and minimum polynomials of the adjacency matrix must be identical for the property to hold. While it has been suggested that this condition might be ignored as it is always possible to find a polynomial transform to represent the original adjacency matrix by another adjacency matrix that satisfies the condition, this letter shows that a filter that is shift invariant in terms of the original graph may not be shift invariant anymore under the modified graph and vice versa. We introduce the notion of "shift-enabled graph" for graphs that satisfy the aforementioned condition, and present a concrete example of a graph that is not "shift-enabled" and a shift-invariant filter that is not a polynomial of the shift operation matrix. The result provides a deeper understanding of shift-invariant filters when applied in GSP and shows that further investigation of shift-enabled graphs is needed to make it applicable to practical scenarios.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Undirected graphs: is the shift-enabled condition trivial or necessary?
It has recently been shown that, contrary to the wide belief that a shift-enabled condition (necessary for any shift-invariant filter to be representable by a graph shift matrix) can be ignored because any non-shift-enab…
Discovering Invariant Neighborhood Patterns for Heterophilic Graphs
This paper studies the problem of distribution shifts on non-homophilous graphs Mosting existing graph neural network methods rely on the homophilous assumption that nodes from the same class are more likely to be linked…
Graph LearningGraph Neural NetworkGDDA: Semantic OOD Detection on Graphs under Covariate Shift via Score-Based Diffusion Models
Out-of-distribution (OOD) detection poses a significant challenge for Graph Neural Networks (GNNs), particularly in open-world scenarios with varying distribution shifts. Most existing OOD detection methods on graphs pri…
Out of Distribution (OOD) DetectionA Closer Look at Distribution Shifts and Out-of-Distribution Generalization on Graphs
Distribution shifts, in which the training distribution differs from the testing distribution, can significantly degrade the performance of Graph Neural Networks (GNNs). Although some existing graph classification benchm…
Domain GeneralizationGraph ClassificationOut-of-Distribution GeneralizationTemporal Memory-Aware Online Test-Time Adaptation on Dynamic Graphs
Test-time adaptation (TTA) on graphs aims to adapt a graph neural network (GNN) that is well-trained on the training graph to the test graph, which involves potential distribution shifts that may harm model generalizatio…
Test-time AdaptationGraph Neural Network