iNet: visual analysis of irregular transition in multivariate dynamic networks

Abstract

Multivariate dynamic networks indicate networks whose topology structure and vertex attributes are evolving along time. They are common in multimedia applications. Anomaly detection is one of the essential tasks in analyzing these networks though it is not well addressed. In this paper, we combine a rare category detection method and visualization techniques to help users to identify and analyze anomalies in multivariate dynamic networks. We conclude features of rare categories and two types of anomalies of rare categories. Then we present a novel rare category detection method, called DIRAD, to detect rare category candidates with anomalies. We develop a prototype system called iNet, which integrates two major visualization components, including a glyph-based rare category identifier, which helps users to identify rare categories among detected substructures, a major view, which assists users to analyze and interpret the anomalies of rare categories in network topology and vertex attributes. Evaluations, including an algorithm performance evaluation, a case study, and a user study, are conducted to test the effectiveness of proposed methods.

Graphical abstract

Keywords

multivariate dynamic networks / rare categories / anomaly detection / visual analysis

References

[1] Zhao Y , Luo X , Lin X , Wang H , Kui X , Zhou F , Wang J , Chen Y , Chen W . Visual analytics for electromagnetic situation awareness in radio monitoring and management. IEEE Transactions on Visualization and Computer Graphics, 2020, 26( 1): 590– 600

[2] Beck F, Burch M, Diehl S, Weiskopf D. The state of the art in visualizing dynamic graphs. In: Proceedings of Eurographics Conference on Visualization. 2014, 83–103

[3] Chandola V , Banerjee A , Kumar V . Anomaly detection: a survey. ACM Computing Surveys, 2009, 41( 3): 1– 58

[4] Ranshous S , Shen S , Koutra D , Harenberg S , Faloutsos C , Samatova N F . Anomaly detection in dynamic networks: a survey. Wiley Interdisciplinary Reviews Computational Statistics, 2015, 7( 3): 223– 247

[5] Zhou D, He J, Cao Y, Seo J S. Bi-level rare temporal pattern detection. In: Proceedings of IEEE International Conference on Data Mining Series. 2016, 719–728

[6] Mei H , Chen W , Wei Y , Hu Y , Zhou S , Lin B , Zhao Y , Xia J . Rsatree: distribution-aware data representation of large-scale tabular datasets for flexible visual query. IEEE Transactions on Visualization and Computer Graphics, 2019, 26( 1): 1161– 1171

[7] Pelleg D, Moore A W. Active learning for anomaly and rare-category detection. In: Proceedings of the 17th International Conference on Neural Information Processing Systems. 2004, 1073–1080

[8] Liu Z , Chiew K , He Q , Huang H , Huang B . Prior-free rare category detection: more effective and efficient solutions. Expert Systems with Applications, 2014, 41( 17): 7691– 7706

[9] He J, Tong H, Carbonell J. Rare category characterization. In: Proceedings of IEEE International Conference on Data Mining. 2010, 226–235

[10] Zhou D, Wang K, Cao N, He J. Rare category detection on timeevolving graphs. In: Proceedings of IEEE International Conference on Data Mining. 2015, 1135–1140

[11] Cheng Z , Chang X , Zhu L , Kanjirathinkal R C , Kankanhalli M . MMALFM: explainable recommendation by leveraging reviews and images. ACM Transactions on Information Systems, 2019, 37( 2): 16–

[12] Liu A A , Nie W Z , Gao Y , Su Y T . Multi-modal clique-graph matching for view-based 3d model retrieval. IEEE Transactions on Image Processing, 2016, 25( 5): 2103– 2116

[13] Liu A A , Su Y T , Nie W Z , Kankanhalli M . Hierarchical clustering multi-task learning for joint human action grouping and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39( 1): 102– 114

[14] Huang H , He Q , Chiew K , Qian F , Ma L . Clover: a faster priorfree approach to rare-category detection. Knowledge and Information Systems, 2013, 35( 3): 713– 736

[15] Zhou D , Karthikeyan A , Wang K , Cao N , He J . Discovering rare categories from graph streams. Data Mining and Knowledge Discovery, 2016, 31( 2): 1– 24

[16] He J, Carbonell J. Prior-free rare category detection. In: Proceedings of SIAM International Conference on Data Mining. 2009, 155–163

[17] Huang H, He Q, He J, Ma L. Radar: rare category detection via computation of boundary degree. In: Proceedings of Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. 2011, 258–269

[18] Vatturi P, Wong W K. Category detection using hierarchical mean shift. In: Proceedings of International Conference on Knowledge Discovery and Data Mining. 2008, 847–856

[19] Pan J , Han D , Guo F , Zhou D , Cao N , He J , Xu M , Chen W . Rcanalyzer: Visual analytics of rare categories in dynamic networks. Frontiers of Information Technology and Electronic Engineering, 2020, 21( 4): 491– 506

[20] Kind A , Stoecklin M P , Dimitropoulos X . Histogram-based traffic anomaly detection. IEEE Transactions on Network and Service Management, 2009, 6( 2): 110– 121

[21] Luo X , Yuan Y , Zhang K , Xia J , Zhou Z , Chang L , Gu T . Enhancing statistical charts: toward better data visualization and analysis. Journal of Visualization, 2019, 22( 4): 819– 832

[22] Xia J , Ye F , Zhou F , Chen Y , Kui X . Visual identification and extraction of intrinsic axes in high-dimensional data. IEEE Access, 2019, 7( 1): 79565– 79578

[23] Inselberg A. Parallel Coordinates, 1st ed. New York: Springer, 2009

[24] Cao N , Gotz D , Sun J , Qu H . Dicon: interactive visual analysis of multidimensional clusters. IEEE Transactions on Visualization and Computer Graphics, 2011, 17( 12): 2581– 2590

[25] Zhao Y , Wang L , Li S , Zhou F , Lin X , Lu Q , Ren L . A visual analysis approach for understanding durability test data of automotive products. ACM Transactions on Intelligent Systems and Technology, 2019, 10( 6): 70–

[26] Xu P , Mei H , Liu R , Wei C . Vidx: visual diagnostics of assembly line performance in smart factories. IEEE Transactions on Visualization and Computer Graphics, 2017, 23( 1): 291–

[27] Corchado E , Herrero Á . Neural visualization of network traffic data for intrusion detection. Applied Soft Computing, 2011, 11( 2): 2042– 2056

[28] Tsai C F , Hsu Y F , Lin C Y , Lin W Y . Intrusion detection by machine learning: a review. Expert Systems with Applications, 2009, 36( 10): 11994– 12000

[29] Thom D, Bosch H, Koch S, Wörner M, Ertl T. Spatiotemporal anomaly detection through visual analysis of geolocated twitter messages. In: Proceedings of Pacific Visualization Symposium. 2012, 41–48

[30] Zhao J , Cao N , Wen Z , Song Y , Lin Y R , Collins C . Fluxflow: visual analysis of anomalous information spreading on social media. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 12): 1773– 1782

[31] Cao N , Shi C , Lin S , Lu J , Lin Y R , Lin C Y . Targetvue: visual analysis of anomalous user behaviors in online communication systems. IEEE Transactions on Visualization and Computer Graphics, 2016, 22( 1): 280– 289

[32] Rufiange S , McGuffin M J . Diffani: visualizing dynamic graphs with a hybrid of difference maps and animation. IEEE Transactions on Visualization and Computer Graphics, 2013, 19( 12): 2556– 2565

[33] Bach B , Pietriga E , Fekete J D . Graphdiaries: animated transitions andtemporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 5): 740– 754

[34] Frishman Y , Tal A . Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics, 2008, 14( 4): 727– 740

[35] Brandes U , Nick B . Asymmetric relations in longitudinal social networks. IEEE Transactions on Visualization and Computer Graphics, 2011, 17( 12): 2283– 2290

[36] Oelke D, Kokkinakis D, Keim D A. Fingerprint matrices: uncovering the dynamics of social networks in prose literature. In: Proceedings of Computer Graphics Forum. 2013, 371–380

[37] Burch M, Schmidt B, Weiskopf D. A matrix-based visualization for exploring dynamic compound digraphs. In: Proceedings of International Conference on Information Visualisation. 2013, 66–73

[38] Vehlow C, Burch M, Schmauder H, Weiskopf D. Radial layered matrix visualization of dynamic graphs. In: Proceedings of the 17th International Conference on Information Visualisation. 2013, 51–58

[39] Bach B, Pietriga E, Fekete J D. Visualizing dynamic networks with matrix cubes. In: Proceedings of Annual ACM Conference on Human Factors in Computing Systems. 2014, 877–886

[40] Zhao J, Liu Z, Dontcheva M, Hertzmann A, Wilson A. Matrixwave: visual comparison of event sequence data. In: Proceedings of Sigchi Conference on Human Factors in Computing Systems. 2015, 259–268

[41] Li J , Chen S , Zhang K , Andrienko G , Andrienko N . Cope: interactive exploration of co-occurrence patterns in spatial time series. IEEE Transactions on Visualization and Computer Graphics, 2019, 25( 8): 2554– 2567

[42] van den Elzen S , Holten D , Blaas J , van Wijk J J . Reducing snapshots to points: a visual analytics approach to dynamic network exploration. IEEE Transactions on Visualization and Computer Graphics, 2016, 22( 1): 1– 10

[43] Vehlow C , Beck F , Auwärter P , Weiskopf D . Visualizing the evolution of communities in dynamic graphs. Computer Graphics Forum, 2015, 34( 1): 277– 288

[44] Cui W, Wang X, Liu S, Riche N H, Madhyastha T M, Ma K L, Guo B. Let it flow: a static method for exploring dynamic graphs. In: Proceedings of IEEE Pacific Visualization Symposium. 2014, 121–128

[45] Hlawatsch M , Burch M , Weiskopf D . Visual adjacency lists for dynamic graphs. IEEE Transactions on Visualization and Computer Graphics, 2014, 20( 11): 1590– 1603

[46] Ying Z , She Y , Chen W , Yutian L , Xia J , Chen W , Liu J , Zhou F . Eod edge sampling for visualizing dynamic network via massive sequence view. IEEE Access, 2018, 6( 1): 53006– 53018

[47] Zhou D, Weston J, Gretton A, Bousquet O, Schölkopf B. Ranking on data manifolds. In: Proceedings of the 16th International Conference on Neural Information Processing Systems. 2003, 169–176

[48] Woodbury M A . Inverting modified matrices. Memorandum Report, 1950, 42( 106): 336–

[49] Zhu M , Chen W , Xia J , Ma Y , Zhang Y , Luo Y , Huang Z , Liu L . Location2vec: a situation-aware representation for visual exploration of urban locations. IEEE Transactions on Intelligent Transportation Systems, 2019, 20( 10): 3981– 3990

[50] Zhou D, He J, Candan K S, Davulcu H. Muvir: multi-view rare category detection. In: Proceedings of International Joint Conferences on Artificial Intelligence. 2015, 4098–4104

[51] He J, Carbonell J G. Nearest-neighbor-based active learning for rare category detection. In: Proceedings of the 21st Annual Conference on Neural Information Processing Systems. 2007, 633–640

[52] He J, Liu Y, Lawrence R. Graph-based rare category detection. In: Proceedings of Industrial Conference on Data Mining. 2008, 833–838

[53] Silverman B W. Density Estimation for Statistics and Data Analysis, 1st ed. New York: Routledge, 1998

[54] Andersen R, Chung F, Lang K. Local graph partitioning using pagerank vectors. In: Proceedings of IEEE Symposium on Foundations of Computer Science. 2006, 475–486

[55] Guo S , Xu K , Zhao R , Gotz D , Zha H , Cao N . Eventthread: visual summarization and stage analysis of event sequence data. IEEE Transactions on Visualization and Computer Graphics, 2017, 24( 1): 56– 65

[56] Chen W , Guo F , Han D , Pan J , Nie X , Xia J , Zhang X . Structure-based suggestive exploration: a new approach for effective exploration of large networks. IEEE Transactions on Visualization and Computer Graphics, 2018, 25( 1): 555– 565

[57] Cao N , Lin Y R , Gotz D , Du F . Z-Glyph: visualizing outliers in multivariate data. Information Visualization, 2018, 17( 1): 22– 40

[58] Shervashidze N , Schweitzer P , Leeuwen E J V , Mehlhorn K , Borgwardt K M . Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 2011, 12( 3): 2539– 2561

[59] Tversky B , Morrison J B , Betrancourt M . Animation: can it facilitate?. International Journal of Human-Computer Studies, 2002, 57( 4): 247– 262

[60] Ghoniem M, Fekete J D, Castagliola P. A comparison of the readability of graphs using node-link and matrix-based representations. In: Proceedings of IEEE Symposium on Information Visualization. 2005, 17–24

[61] Tang J, Gao H, Liu H. mTrust: discerning multi-faceted trust in a connected world. In: Proceedings of ACM International Conference on Web Search and Data Mining. 2012, 93–102

RIGHTS & PERMISSIONS

Higher Education Press