On the stability of polynomial spectral graph filters
Spectral graph filters are a key component in state-of-the-art machine learning models used for graph-based learning, such as graph neural networks. For certain tasks stability of the spectral graph filters is important for learning suitable representations. Understanding the type of structural pert...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
IEEE
2020
|
| _version_ | 1826295758904623104 |
|---|---|
| author | Kenlay, H Thanou, D Dong, X |
| author_facet | Kenlay, H Thanou, D Dong, X |
| author_sort | Kenlay, H |
| collection | OXFORD |
| description | Spectral graph filters are a key component in state-of-the-art machine learning models used for graph-based learning, such as graph neural networks. For certain tasks stability of the spectral graph filters is important for learning suitable representations. Understanding the type of structural perturbation to which spectral graph filters are robust lets us reason as to when we may expect them to be well suited to a learning task. In this work, we first prove that polynomial graph filters are stable with respect to the change in the normalised graph Laplacian matrix. We then show empirically that properties of a structural perturbation, specifically the relative locality of the edges removed in a binary graph, effect the change in the normalised graph Laplacian. Together, our results have implications on designing robust graph filters and representations under structural perturbation. |
| first_indexed | 2024-03-07T04:05:59Z |
| format | Conference item |
| id | oxford-uuid:c629d35b-7102-4daf-a0d1-987ec55673f5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T04:05:59Z |
| publishDate | 2020 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:c629d35b-7102-4daf-a0d1-987ec55673f52022-03-27T06:36:16ZOn the stability of polynomial spectral graph filtersConference itemhttp://purl.org/coar/resource_type/c_5794uuid:c629d35b-7102-4daf-a0d1-987ec55673f5EnglishSymplectic ElementsIEEE2020Kenlay, HThanou, DDong, XSpectral graph filters are a key component in state-of-the-art machine learning models used for graph-based learning, such as graph neural networks. For certain tasks stability of the spectral graph filters is important for learning suitable representations. Understanding the type of structural perturbation to which spectral graph filters are robust lets us reason as to when we may expect them to be well suited to a learning task. In this work, we first prove that polynomial graph filters are stable with respect to the change in the normalised graph Laplacian matrix. We then show empirically that properties of a structural perturbation, specifically the relative locality of the edges removed in a binary graph, effect the change in the normalised graph Laplacian. Together, our results have implications on designing robust graph filters and representations under structural perturbation. |
| spellingShingle | Kenlay, H Thanou, D Dong, X On the stability of polynomial spectral graph filters |
| title | On the stability of polynomial spectral graph filters |
| title_full | On the stability of polynomial spectral graph filters |
| title_fullStr | On the stability of polynomial spectral graph filters |
| title_full_unstemmed | On the stability of polynomial spectral graph filters |
| title_short | On the stability of polynomial spectral graph filters |
| title_sort | on the stability of polynomial spectral graph filters |
| work_keys_str_mv | AT kenlayh onthestabilityofpolynomialspectralgraphfilters AT thanoud onthestabilityofpolynomialspectralgraphfilters AT dongx onthestabilityofpolynomialspectralgraphfilters |