An Analysis of How Hypergraph Spectral Clustering Deals with Higher-order Relationships
Resumo
Spectral clustering has recently been extended to hypergraphs, which are formed by vertices and higher-order relationships between these vertices. In this article, we consider a methodology to qualitatively compare hypergraph spectral clustering against the classical graph spectral clustering. More precisely, we use a graph representation to create a graph from a given hypergraph, thus allowing a comparison between spectral clustering methods. Experiment shows that the hypergraph spectral clustering deals differently with higher-order relationships.Referências
U. Von Luxburg, “A tutorial on spectral clustering,” Statistics and computing, vol. 17, pp. 395–416, 2007.
K. Pena-Pena, D. L. Lau, and G. R. Arce, “t-hgsp: Hypergraph signal processing using t-product tensor decompositions,” IEEE Transactions on Signal and Information Processing over Networks, 2023.
M. T. Schaub, Y. Zhu, J.-B. Seby, T. M. Roddenberry, and S. Segarra, “Signal processing on higher-order networks: Livin’on the edge... and beyond,” Signal Processing, vol. 187, p. 108149, 2021.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEEE signal processing magazine, vol. 30, no. 3, pp. 83–98, 2013.
A. Sandryhaila and J. M. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” IEEE Signal Processing Magazine, vol. 31, no. 5, pp. 80–90, 2014.
A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018.
W. A. Martins, J. B. Lima, C. Richard, and S. Chatzinotas, “A primer on graph signal processing,” in Signal Processing and Machine Learning Theory, P. S. Diniz, Ed. Academic Press, 2023, pp. 961–1008.
A. D. Col, F. Petronetto, J. R. de Oliveira Neto, and J. B. Lima, “Windowed hypergraph Fourier transform and vertex-frequency representation,” Signal Processing, p. 109538, 2024.
M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover, “Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging,” SIAM Journal on Matrix Analysis and Applications, vol. 34, no. 1, pp. 148–172, 2013.
S. Hu, L. Qi, and J.-Y. Shao, “Cored hypergraphs, power hypergraphs and their laplacian h-eigenvalues,” Linear Algebra and Its Applications, vol. 439, no. 10, pp. 2980–2998, 2013.
K. Pena-Pena, D. L. Lau, and G. R. Arce, “t-hgsp: Hypergraph signal processing using t-product tensor decompositions,” IEEE Transactions on Signal and Information Processing over Networks, 2023.
M. T. Schaub, Y. Zhu, J.-B. Seby, T. M. Roddenberry, and S. Segarra, “Signal processing on higher-order networks: Livin’on the edge... and beyond,” Signal Processing, vol. 187, p. 108149, 2021.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” IEEE signal processing magazine, vol. 30, no. 3, pp. 83–98, 2013.
A. Sandryhaila and J. M. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” IEEE Signal Processing Magazine, vol. 31, no. 5, pp. 80–90, 2014.
A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” Proceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018.
W. A. Martins, J. B. Lima, C. Richard, and S. Chatzinotas, “A primer on graph signal processing,” in Signal Processing and Machine Learning Theory, P. S. Diniz, Ed. Academic Press, 2023, pp. 961–1008.
A. D. Col, F. Petronetto, J. R. de Oliveira Neto, and J. B. Lima, “Windowed hypergraph Fourier transform and vertex-frequency representation,” Signal Processing, p. 109538, 2024.
M. E. Kilmer, K. Braman, N. Hao, and R. C. Hoover, “Third-order tensors as operators on matrices: A theoretical and computational framework with applications in imaging,” SIAM Journal on Matrix Analysis and Applications, vol. 34, no. 1, pp. 148–172, 2013.
S. Hu, L. Qi, and J.-Y. Shao, “Cored hypergraphs, power hypergraphs and their laplacian h-eigenvalues,” Linear Algebra and Its Applications, vol. 439, no. 10, pp. 2980–2998, 2013.
Publicado
30/09/2024
Como Citar
CUNHA, Ana Carolina Holzmeister; PETRONETTO, Fabiano; DAL COL, Alcebiades.
An Analysis of How Hypergraph Spectral Clustering Deals with Higher-order Relationships. In: WORKSHOP DE TRABALHOS DA GRADUAÇÃO - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 37. , 2024, Manaus/AM.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 143-146.
DOI: https://doi.org/10.5753/sibgrapi.est.2024.31660.
