Semi-supervised blockmodelling with pairwise guidance

Mohadeseh Ganji, Jeffrey Chan, Peter J. Stuckey, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, Laurence Park

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Blockmodelling is an important technique for detecting underlying patterns in graphs. Existing blockmodelling algorithms are unsupervised and cannot take advantage of the existing information that might be available about objects that are known to be similar. This background information can help finding complex patterns, such as hierarchical or ring blockmodel structures, which are difficult for traditional blockmodelling algorithms to detect. In this paper, we propose a new semi-supervised framework for blockmodelling, which allows background information to be incorporated in the form of pairwise membership information. Our proposed framework is based on the use of Lagrange multipliers and can be incorporated into existing iterative blockmodelling algorithms, enabling them to find complex blockmodel patterns in graphs. We demonstrate the utility of our framework for discovering complex patterns, via experiments over a range of synthetic and real data sets. Code related to this paper is available at: https://people.eng.unimelb.edu.au/mganji/.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2018 Dublin, Ireland, September 10–14, 2018 Proceedings, Part II
EditorsMichele Berlingerio, Francesco Bonchi, Thomas Gärtner, Neil Hurley, Georgiana Ifrim
Place of PublicationCham Switzerland
PublisherSpringer
Pages158-174
Number of pages17
ISBN (Electronic)9783030109288
ISBN (Print)9783030109271
DOIs
Publication statusPublished - 2019
Externally publishedYes
EventEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases: ECML-PKDD 2018 - Dublin, Ireland
Duration: 10 Sep 201814 Sep 2018
http://www.ecmlpkdd2018.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11052
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning European Conference on Principles and Practice of Knowledge Discovery in Databases: ECML-PKDD 2018
Abbreviated titleECML-PKDD 2018
CountryIreland
CityDublin
Period10/09/1814/09/18
Internet address

Keywords

  • Blockmodelling
  • Lagrange multipliers
  • Pairwise information

Cite this

Ganji, M., Chan, J., Stuckey, P. J., Bailey, J., Leckie, C., Ramamohanarao, K., & Park, L. (2019). Semi-supervised blockmodelling with pairwise guidance. In M. Berlingerio, F. Bonchi, T. Gärtner, N. Hurley, & G. Ifrim (Eds.), Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018 Dublin, Ireland, September 10–14, 2018 Proceedings, Part II (pp. 158-174). (Lecture Notes in Computer Science; Vol. 11052). Springer. https://doi.org/10.1007/978-3-030-10928-8_10