publication . Preprint . Article . Other literature type . 2017

Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms

Chen, Pin-Yu; Hero, Alfred O.;
Open Access English
  • Published: 08 Aug 2017
Abstract
Multilayer graphs are commonly used for representing different relations between entities and handling heterogeneous data processing tasks. Non-standard multilayer graph clustering methods are needed for assigning clusters to a common multilayer node set and for combining information from each layer. This paper presents a multilayer spectral graph clustering (SGC) framework that performs convex layer aggregation. Under a multilayer signal plus noise model, we provide a phase transition analysis of clustering reliability. Moreover, we use the phase transition criterion to propose a multilayer iterative model order selection algorithm (MIMOSA) for multilayer SGC, ...
Subjects
arXiv: Computer Science::Neural and Evolutionary ComputationCondensed Matter::Materials SciencePhysics::Optics
free text keywords: Statistics - Machine Learning, Computer Science - Social and Information Networks, Cluster (physics), Symmetric matrix, Selection algorithm, Computer science, Regular polygon, Algorithm, Iterative and incremental development, Data processing, Clustering coefficient, Cluster analysis
Related Organizations
62 references, page 1 of 5

[1] B. Oselio, A. Kulesza, and A. O. Hero, “Multi-layer graph analysis for dynamic social networks,” IEEE J. Sel. Topics Signal Process., vol. 8, no. 4, pp. 514-523, Aug 2014.

[2] K. S. Xu and A. O. Hero, “Dynamic stochastic blockmodels for timeevolving social networks,” IEEE J. Sel. Topics Signal Process., vol. 8, no. 4, pp. 552-562, 2014.

[3] M. De Domenico, A. Sole´-Ribalta, E. Cozzo, M. Kivela¨, Y. Moreno, M. A. Porter, S. Go´mez, and A. Arenas, “Mathematical formulation of multilayer networks,” Phys. Rev. X, vol. 3, p. 041022, Dec 2013.

[4] B. Oselio, A. Kulesza, and A. Hero, “Information extraction from large multi-layer social networks,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2015, pp. 5451- 5455. [OpenAIRE]

[5] D. Zhou and C. J. Burges, “Spectral clustering and transductive learning with multiple views,” in International Conference on Machine Learning, 2007, pp. 1159-1166.

[6] N. Leonardi and D. Van De Ville, “Tight wavelet frames on multislice graphs,” IEEE Trans. Signal Process., vol. 61, no. 13, pp. 3357-3367, 2013.

[7] K. Benzi, B. Ricaud, and P. Vandergheynst, “Principal patterns on graphs: Discovering coherent structures in datasets,” IEEE Trans. Signal Inf. Process. Netw., vol. 2, no. 2, pp. 160-173, 2016. [OpenAIRE]

[8] P.-Y. Chen, S. Choudhury, and A. O. Hero, “Multi-centrality graph spectral decompositions and their application to cyber intrusion detection,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 4553-4557. [OpenAIRE]

[9] Y. Park, C. E. Priebe, and A. Youssef, “Anomaly detection in time series of graphs using fusion of graph invariants,” IEEE J. Sel. Topics Signal Process., vol. 7, no. 1, pp. 67-75, 2013. [OpenAIRE]

[10] M. Kivela¨, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” Journal of complex networks, vol. 2, no. 3, pp. 203-271, 2014.

[11] J. Kim and J.-G. Lee, “Community detection in multi-layer graphs: A survey,” ACM SIGMOD Record, vol. 44, no. 3, pp. 37-48, 2015.

[12] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J.-P. Onnela, “Community structure in time-dependent, multiscale, and multiplex networks,” Science, vol. 328, no. 5980, pp. 876-878, 2010.

[13] X. Dong, P. Frossard, P. Vandergheynst, and N. Nefedov, “Clustering on multi-layer graphs via subspace analysis on grassmann manifolds,” IEEE Trans. Signal Process., vol. 62, no. 4, pp. 905-918, 2014.

[14] D. Cai, Z. Shao, X. He, X. Yan, and J. Han, “Community mining from multi-relational networks,” in European Conference on Principles of Data Mining and Knowledge Discovery. Springer, 2005, pp. 445-452.

[15] L. Tang, X. Wang, and H. Liu, “Uncoverning groups via heterogeneous interaction analysis,” in IEEE International Conference on Data Mining. IEEE, 2009, pp. 503-512.

62 references, page 1 of 5
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Article . Other literature type . 2017

Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms

Chen, Pin-Yu; Hero, Alfred O.;