Active network alignment: a matching-based approach

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorMalmi, Ericen_US
dc.contributor.authorTerzi, Evimariaen_US
dc.contributor.authorGionis, Aristidesen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorAdj. Prof. Gionis Aris groupen
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.date.accessioned2018-08-21T13:42:57Z
dc.date.available2018-08-21T13:42:57Z
dc.date.issued2017en_US
dc.description| openaire: EC/H2020/654024/EU//SoBigData
dc.description.abstractNetwork alignment is the problem of matching the nodes of two graphs, maximizing the similarity of the matched nodes and the edges between them. This problem is encountered in a wide array of applications---from biological networks to social networks to ontologies---where multiple networked data sources need to be integrated. Due to the difficulty of the task, an accurate alignment can rarely be found without human assistance. Thus, it is of great practical importance to develop network alignment algorithms that can optimally leverage experts who are able to provide the correct alignment for a small number of nodes. Yet, only a handful of existing works address this active network alignment setting. The majority of the existing active methods focus on absolute queries ("are nodes a and b the same or not?"), whereas we argue that it is generally easier for a human expert to answer relative queries ("which node in the set b1,...,bn is the most similar to node a?"). This paper introduces two novel relative-query strategies, TopMatchings and GibbsMatchings, which can be applied on top of any network alignment method that constructs and solves a bipartite matching problem. Our methods identify the most informative nodes to query by sampling the matchings of the bipartite graph associated to the network-alignment instance. We compare the proposed approaches to several commonly-used query strategies and perform experiments on both synthetic and real-world datasets. Our sampling-based strategies yield the highest overall performance, outperforming all the baseline methods by more than 15 percentage points in some cases. In terms of accuracy, TopMatchings and GibbsMatchings perform comparably. However, GibbsMatchings is significantly more scalable, but it also requires hyperparameter tuning for a temperature parameter.en
dc.description.versionPeer revieweden
dc.format.extent1687-1696
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationMalmi, E, Terzi, E & Gionis, A 2017, Active network alignment: a matching-based approach . in Proceedings of the 2017 ACM on Conference on Information and Knowledge Management . ACM, pp. 1687-1696, ACM International Conference on Information and Knowledge Management, Singapore, Singapore, 06/11/2017 . https://doi.org/10.1145/3132847.3132983en
dc.identifier.doi10.1145/3132847.3132983en_US
dc.identifier.isbn978-1-4503-4918-5
dc.identifier.otherPURE UUID: 0f35df7c-92ce-47e3-900c-6c346f384005en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/0f35df7c-92ce-47e3-900c-6c346f384005en_US
dc.identifier.otherPURE LINK: https://dl.acm.org/citation.cfm?id=3132847en_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/26625711/1610.05516.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/33461
dc.identifier.urnURN:NBN:fi:aalto-201808214594
dc.language.isoenen
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigDataen_US
dc.relation.ispartofACM International Conference on Information & Knowledge Managementen
dc.relation.ispartofseriesProceedings of the 2017 ACM on Conference on Information and Knowledge Managementen
dc.rightsrestrictedAccessen
dc.titleActive network alignment: a matching-based approachen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpreprint
Files