Top

Published in:

2022 | OriginalPaper | Chapter

Selecting Informative Features for Post-hoc Community Explanation

Authors : Sophie Sadler, Derek Greene, Daniel Archambault

Published in: Complex Networks & Their Applications X

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Community finding algorithms are complex, often stochastic algorithms used to detect highly-connected groups of nodes in a graph. As with “black-box” machine learning models, these algorithms typically provide little in the way of explanation or insight into their outputs. In this research paper, inspired by recent work in explainable artificial intelligence (XAI), we look to develop post-hoc explanations for community finding, which are agnostic of the choice of algorithm. Specifically, we propose a new approach to identify features that indicate whether a set of nodes comprises a coherent community or not. We evaluate our methodology, which selects interpretable features from a longlist of candidates, in the context of three well-known community finding algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter An Extension of K-Means for Least-Squares Community Detection in Feature-Rich Networks

next chapter Community Detection by Resistance Distance: Automation and Benchmark Testing

A non-proceedings poster on this topic was presented at the GEM workshop at ECML-PKDD 2021.

Results and implementations for the statistical analysis process are available on OSF: https://osf.io/g4bwt/.

Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008(10), P10008 (2008)CrossRefMATH

Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (2001). https://doi.org/10.1023/A:1010933404324CrossRefMATH

Brown, R.C., Fischer, T., Goldwich, A.D., Keller, F., Young, R., Plener, P.L.: #cutting: non-suicidal self-injury (NSSI) on Instagram. Psychol. Med. 48(2), 337–346 (2017)CrossRef

Chakraborty, T., Srinivasan, S., Ganguly, N., Bhowmick, S., Mukherjee, A.: Constant communities in complex networks. Sci. Rep. 3(1), 1–9 (2013)CrossRef

Dao, V.L., Bothorel, C., Lenca, P.: Community structures evaluation in complex networks: a descriptive approach. In: Shmueli E., Barzel B., Puzis R. (eds) 3rd International Winter School and Conference on Network Science. NetSci-X 2017. Springer Proceedings in Complexity, pp. 11–19. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55471-6_2 (2017)

Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)MathSciNetCrossRef

Francisco, A.P., Oliveira, A.L.: On community detection in very large networks. In: da F. Costa, L., Evsukoff, A., Mangioni, G., Menezes, R. (eds.) Complex Networks. CCIS, vol. 116, pp. 208–216. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25501-4_21

Hagberg, A., Swart, P.S., Chult, D.: Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab., NM (2008)

Keane, M.T., Kenny, E.M.: How case-based reasoning explains neural networks: a theoretical analysis of XAI using Post-Hoc explanation-by-example from a survey of ANN-CBR twin-systems. In: Bach, K., Marling, C. (eds) Case-Based Reasoning Research and Development. ICCBR 2019. LNCS, vol. 11680, pp. 155–171. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29249-2_11

10.

Keane, M.T., Kenny, E.M.: The Twin-System Approach as One Generic Solution for XAI: An Overview of ANN-CBR Twins for Explaining Deep Learning. arXiv 1905.08069 (2019)

11.

Lancichinetti, A., Fortunato, S.: Community detection algorithms: a comparative analysis. Phys. Rev. E Stat. Nonlinear Soft Matter Phys. 80(5), 1–12 (2009)CrossRef

12.

Lancichinetti, A., Fortunato, S.: Consensus clustering in complex networks. Sci. Rep. 2(1), 1–7 (2012)CrossRef

13.

Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E Stat. Nonlinear Soft Matter Physics 78(4), 1–6 (2008)CrossRef

14.

Lee, A., Archambault, D.: Communities found by Users – not algorithms. In: Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems, pp. 2396–2400 (2016)

15.

Loyola-Gonzalez, O., Gutierrez-Rodríguez, A.E., Medina-Pérez, M.A., Monroy, R., Martínez-Trinidad, J.F., Carrasco-Ochoa, J.A., Garcia-Borroto, M.: An explainable artificial intelligence model for clustering numerical databases. IEEE Access 8, 52370–52384 (2020)CrossRef

16.

Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4768–4777 (2017)

17.

Molnar, C.: Interpretable machine learning. Lulu.com (2020)

18.

Morichetta, A., Casas, P., Mellia, M.: EXPLAIN-IT: towards explainable AI for unsupervised network traffic analysis. In: Proceedings of the 3rd ACM CoNEXT Workshop on Big DAta, Machine Learning and Artificial Intelligence for Data Communication Networks, pp. 22–28 (2019)

19.

Newman, M., Clauset, A.: Structure and inference in annotated networks. Nat. Commun. 7, 1–11 (2016)CrossRef

20.

Orman, G., Labatut, V., Cherifi, H.: Comparative evaluation of community detection algorithms: a topological approach. J. Stat. Mech. Theory Exp. 2012(08), P08001 (2012)CrossRef

21.

Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)CrossRef

22.

Ribeiro, M.T., Singh, S., Guestrin, C.: “Why should I trust you?” Explaining the predictions of any classifier. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135–1144 (2016)

23.

Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc Natl. Acad. Sci. USA 105(4), 1118–1123 (2008)CrossRef

24.

Valente, T.W.: Network interventions. Science 337(6090), 49–53 (2012)CrossRef

25.

Valente, T.W., Yon, G.G.V.: Diffusion/contagion processes on social networks. Health Educ. Beha. 47(2), 235–248 (2020)CrossRef

26.

Wachter, S., Mittelstadt, B., Russell, C.: Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard J. Law Technol. 31, 841 (2017)

27.

Watts, D.J., Strogatz, S.H.: Collective dynamics of “small-world’’ networks. Nature 393, 440–442 (1998)CrossRefMATH

28.

Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst. 42(1), 181–213 (2013). https://doi.org/10.1007/s10115-013-0693-zCrossRef

Title: Selecting Informative Features for Post-hoc Community Explanation
Authors: Sophie Sadler
Derek Greene
Daniel Archambault
Publisher: Springer International Publishing
Book: Complex Networks & Their Applications X
Print ISBN: 978-3-030-93408-8

Electronic ISBN: 978-3-030-93409-5

Copyright Year: 2022
DOI: https://doi.org/10.1007/978-3-030-93409-5_25

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner