Visual Analytics via Graph Signal Processing
Resumo
This dissertation presents an overview of the extension of the classical signal processing theory to graph domains. Furthermore, we introduce in this dissertation a novel method for visual analysis of dynamic networks, which relies on the graph wavelet theory. Our method enables the automatic analysis of a signal defined on the nodes of a network. We use a fast approximation of the graph wavelet transform to derive a set of wavelet coefficients, which are then used to identify activity patterns on large networks, including their temporal recurrence. The wavelet coefficients naturally encode spatial and temporal variations of the signal, leading to an efficient and meaningful representation. This method allows for the exploration of the structural evolution of the network and their patterns over time. The effectiveness of our approach is demonstrated using different scenarios and comparisons involving real dynamic networks.
Referências
N. Tremblay and P. Borgnat, “Graph wavelets for multiscale community mining,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5227–5239, 2014. https://doi.org/10.1109/TSP.2014.2345355
P. Valdivia, F. Dias, F. Petronetto, C. T. Silva, and L. Nonato, “Wavelet-based visualization of time-varying data on graphs,” in IEEE Conference on Visual Analytics Science and Technology. Institute of Electrical and Electronics Engineers, 2015. https://doi.org/10.1109/VAST.2015.7347624
D. M. Mohan, M. T. Asif, N. Mitrovic, J. Dauwels, and P. Jaillet, “Wavelets on graphs with application to transportation networks,” in IEEE International Conference on Intelligent Transportation Systems. Institute of Electrical and Electronics Engineers, 2014, pp. 1707–1712. https://doi.org/10.1109/ITSC.2014.6957939
D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011. https://doi.org/10.1016/j.acha.2010.04.005
D. I. Shuman, C. Wiesmeyr, N. Holighaus, and P. Vandergheynst, “Spectrum-adapted tight graph wavelet and vertex-frequency frames,”IEEE Transactions on Signal Processing, vol. 63, no. 16, pp. 4223– 4235, 2015. https://doi.org/10.1109/TSP.2015.2424203
B. Bach, E. Pietriga, and J.-D. Fekete, “GraphDiaries: Animated transitions and temporal navigation for dynamic networks,” IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 5, pp. 740–754, 2014. https://doi.org/10.1109/TVCG.2013.254
B. Bach, N. Henry-Riche, T. Dwyer, T. Madhyastha, J.-D. Fekete, and T. Grabowski, “Small MultiPiles: Piling time to explore temporal patterns in dynamic networks,” Computer Graphics Forum, 2015. https://doi.org/10.1111/cgf.12615
B. Bach, C. Shi, N. Heulot, T. Madhyastha, T. Grabowski, and P. Dragicevic, “Time Curves: Folding Time to Visualize Patterns of Temporal Evolution in Data,” IEEE Transactions on Visualization and Computer Graphics, vol. 22, no. 1, 2016. https://doi.org/10.1109/TVCG.2015.2467851
W. Cui, X. Wang, S. Liu, N. H. Riche, T. M. Madhyastha, K. L. Ma, and B. Guo, “Let it flow: a static method for exploring dynamic graphs,” in IEEE Pacific Visualization Symposium. Institute of Electrical and Electronics Engineers, 2014, pp. 121–128. https://doi.org/10.1109/PacificVis.2014.48
T. N. Dang, N. Pendar, and A. G. Forbes, “Timearcs: Visualizing fluctuations in dynamic networks,” Computer Graphics Forum, vol. 35, no. 3, pp. 61–69, 2016. https://doi.org/10.1111/cgf.12882
S. van den Elzen, D. Holten, J. Blaas, and J. J. van Wijk, “Dynamic network visualization with extended massive sequence views,” IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 8, pp. 1087–1099, 2014. https://doi.org/10.1109/TVCG.2013.263
S. van den Elzen, D. Holten, J. Blaas, and J. J. van Wijk, “Reducing snapshots to points: A visual analytics approach to dynamic network exploration,” IEEE Transactions on Visualization and Computer Graphics, vol. 22, no. 1, pp. 1–10, 2016. https://doi.org/10.1109/TVCG.2015.2468078
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual analysis for data exploration,” Computing in Science & Engineering, vol. 19, no. 5, pp. 85–91, 2017. https://doi.org/10.1109/MCSE.2017.3421553
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual analysis of dynamic networks,” IEEE transactions on visualization and computer graphics, vol. 24, no. 8, pp. 2456–2469, 2018. https://doi.org/10.1109/TVCG.2017.2746080
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual data exploration,” in Vertex-Frequency Analysis of Graph Signals. Springer, 2019, pp. 459–478. https://doi.org/10.1007/978-3-030-03574-7_14
P. Valdivia, F. Dias, F. Petronetto, C. T. Silva, and L. Nonato, “Wavelet-based visualization of time-varying data on graphs,” in IEEE Conference on Visual Analytics Science and Technology. Institute of Electrical and Electronics Engineers, 2015. https://doi.org/10.1109/VAST.2015.7347624
D. M. Mohan, M. T. Asif, N. Mitrovic, J. Dauwels, and P. Jaillet, “Wavelets on graphs with application to transportation networks,” in IEEE International Conference on Intelligent Transportation Systems. Institute of Electrical and Electronics Engineers, 2014, pp. 1707–1712. https://doi.org/10.1109/ITSC.2014.6957939
D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011. https://doi.org/10.1016/j.acha.2010.04.005
D. I. Shuman, C. Wiesmeyr, N. Holighaus, and P. Vandergheynst, “Spectrum-adapted tight graph wavelet and vertex-frequency frames,”IEEE Transactions on Signal Processing, vol. 63, no. 16, pp. 4223– 4235, 2015. https://doi.org/10.1109/TSP.2015.2424203
B. Bach, E. Pietriga, and J.-D. Fekete, “GraphDiaries: Animated transitions and temporal navigation for dynamic networks,” IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 5, pp. 740–754, 2014. https://doi.org/10.1109/TVCG.2013.254
B. Bach, N. Henry-Riche, T. Dwyer, T. Madhyastha, J.-D. Fekete, and T. Grabowski, “Small MultiPiles: Piling time to explore temporal patterns in dynamic networks,” Computer Graphics Forum, 2015. https://doi.org/10.1111/cgf.12615
B. Bach, C. Shi, N. Heulot, T. Madhyastha, T. Grabowski, and P. Dragicevic, “Time Curves: Folding Time to Visualize Patterns of Temporal Evolution in Data,” IEEE Transactions on Visualization and Computer Graphics, vol. 22, no. 1, 2016. https://doi.org/10.1109/TVCG.2015.2467851
W. Cui, X. Wang, S. Liu, N. H. Riche, T. M. Madhyastha, K. L. Ma, and B. Guo, “Let it flow: a static method for exploring dynamic graphs,” in IEEE Pacific Visualization Symposium. Institute of Electrical and Electronics Engineers, 2014, pp. 121–128. https://doi.org/10.1109/PacificVis.2014.48
T. N. Dang, N. Pendar, and A. G. Forbes, “Timearcs: Visualizing fluctuations in dynamic networks,” Computer Graphics Forum, vol. 35, no. 3, pp. 61–69, 2016. https://doi.org/10.1111/cgf.12882
S. van den Elzen, D. Holten, J. Blaas, and J. J. van Wijk, “Dynamic network visualization with extended massive sequence views,” IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 8, pp. 1087–1099, 2014. https://doi.org/10.1109/TVCG.2013.263
S. van den Elzen, D. Holten, J. Blaas, and J. J. van Wijk, “Reducing snapshots to points: A visual analytics approach to dynamic network exploration,” IEEE Transactions on Visualization and Computer Graphics, vol. 22, no. 1, pp. 1–10, 2016. https://doi.org/10.1109/TVCG.2015.2468078
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual analysis for data exploration,” Computing in Science & Engineering, vol. 19, no. 5, pp. 85–91, 2017. https://doi.org/10.1109/MCSE.2017.3421553
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual analysis of dynamic networks,” IEEE transactions on visualization and computer graphics, vol. 24, no. 8, pp. 2456–2469, 2018. https://doi.org/10.1109/TVCG.2017.2746080
A. Dal Col, P. Valdivia, F. Petronetto, F. Dias, C. T. Silva, and L. G. Nonato, “Wavelet-based visual data exploration,” in Vertex-Frequency Analysis of Graph Signals. Springer, 2019, pp. 459–478. https://doi.org/10.1007/978-3-030-03574-7_14
Publicado
28/10/2019
Como Citar
DAL COL, Alcebiades; NONATO, Luis Gustavo.
Visual Analytics via Graph Signal Processing. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 32. , 2019, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 8-14.
DOI: https://doi.org/10.5753/sibgrapi.est.2019.8295.
