Collective Entity Resolution Methods for Network Inference

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorMalmi, Eric
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.labData Mining Groupen
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.schoolSchool of Scienceen
dc.contributor.supervisorGionis, Aristides, Prof., Aalto University, Department of Computer Science, Finland
dc.date.accessioned2018-06-12T09:02:52Z
dc.date.available2018-06-12T09:02:52Z
dc.date.defence2018-06-20
dc.date.issued2018
dc.description.abstractData has become an essential resource, which is used to guide decision making across many levels of society. To fully leverage the abundance of data sources, the various sources need to be integrated, which poses difficult computational challenges. Entity resolution techniques address these challenges by trying to identify data records referring to the same underlying entity. Often, relational information about the records (for example, a friendship network between the users of a social networking service) is available, but this information is ignored by the traditional entity resolution techniques. The goal of this thesis is to develop novel collective entity resolution methods which match records by leveraging relational information and produce an entity network. The developed methods are applicable to a wide array of applications - from bioinformatics to ontologies - but the initial motivation for this work has been the problem of integrating genealogical data to infer large-scale genealogical networks (family trees). This thesis makes the following methodological contributions: First, we develop novel methods for linking vital records, such as birth records, to infer genealogical networks. An experimental evaluation of the inferred networks shows that even fully automatic methods can produce fairly accurate networks, and moreover, the estimated link probabilities provide a reliable way to quantify the certainty of the inferred family relationships. Second, we propose methods with theoretical guarantees for aggregating the edges of directed acyclic graphs in the case that the correspondance between input-graph nodes is known. Third, if the correspondance is unknown, an alignment between the nodes has to be found. We study the resulting network alignment problem and propose methods for aligning multiple networks and for aligning networks actively by leveraging human experts. The proposed vital-record linking methods have been employed to automatically link a dataset of five million historical birth records from Finland. To visualize the resulting network and to enable the exploration of the inferred links, we have developed an online tool called AncestryAI, which has been used so far by thousands of genealogists in Finland. In the final part of the thesis, we demonstrate the usefullness of the inferred genealogical network for the field of computational social science by presenting a longitudinal analysis on assortative mating, that is, the tendency to marry someone with a similar socioeconomic status. This phenomenon is quantified by comparing the socioeconomic statuses of the automatically inferred spouses. We find evidence that assortative mating existed in Finland (1735-1885), but interestingly, we do not observe any monotonically decreasing or increasing trend in the strength of assortative mating.en
dc.description.abstractDatasta on tullut tärkeä resurssi, joka ohjaa päätöksentekoa monilla yhteiskunnan tasoilla. Eri datalähteet tulisi kyetä yhdistämään, jotta niitä voisi hyödyntämää tehokkaasti, mikä muodostaa haastavan laskennallisen ongelman. Tietueiden linkitysmenetelmät vastaavat tähän ongelmaan yrittäen tunnistaa samaan entiteettiin viittaavat tietueet. Usein tietueista on saatavissa relationaalista tietoa, kuten esimerkiksi sosiaalisen verkoston käyttäjien välinen ystävyysverkosto, mutta perinteiset linkitysmenetelmät jättävät nämä relationaaliset tiedot huomiotta. Tämän työn tavoitteena on kehittää uusia kollektiivisia tietueiden linkitysmenetelmiä, jotka hyödyntävät relationaalista tietoa ja tuottavat entiteettiverkoston. Kehitettyjä menetelmiä voidaan soveltaa moniin kohteisiin, kuten bioinformatiikkaan tai ontologioihin, mutta työn alkuperäisenä tavoitteena on ollut laajojen sukuverkostojen eli sukupuiden päättely. Väitöskirjassa esitellään seuraavat metodologiset kontribuutiot: 1. Henkilötietojen, kuten kastetapahtumien, linkittämiseen on kehitetty uusia menetelmiä, joilla voidaan päätellä sukuverkostoja. Pääteltyjen verkostojen analyysi osoittaa, että jopa täysin automaattiset menetelmät voivat tuottaa melko tarkkoja verkostoja. Tämän lisäksi menetelmien tuottamat todennäköisyydet tarjoavat luotettavan tavan määrittää löydettyjen perhesuhteiden epävarmuus. 2. Verkostojen yhdistämiseen on kehitetty teoreettisesti perusteltuja menetelmiä, jotka soveltuvat suunnattuihin asyklisiin verkostoihin, joiden solmujen vastaavuudet on tunnettu. 3. Mikäli solmujen vastaavuus on tuntematon, tulee solmut ensin kohdistaa toisiinsa. Työssä on tarkasteltu näin syntyvää verkostojen kohdistamisongelmaa ja kehitetty menetelmiä useiden verkostojen kohdistamiseen automaattisesti sekä kahden verkoston kohdistamiseen interaktiivisesti ihmisasiantuntijoita hyödyntäen. Henkilötietojen linkittämiseen kehitettyjä menetelmiä on sovellettu viiden miljoonan Suomesta kerätyn yli sata vuotta vanhan kastetapahtuman linkittämiseen. Tuloksena saadun verkoston visualisointiin ja pääteltyjen sukulaisuussuhteiden etsintään on kehitetty AncestryAI-niminen verkkotyökalu, jota tuhannet sukututkijat Suomessa ovat tähän mennessä käyttäneet. Pääteltyä sukuverkostoa voidaan soveltaa myös laskennallisen yhteiskuntatieteen alalle. Työn loppuosassa esitellään pitkittäistutkimus liittyen assortatiiviseen parinmuodostukseen, eli ihmisten taipumukseen valikoida puoliso, jolla on samanlainen sosioekonominen asema. Ilmiötä mitataan vertailemalla automaattisesti pääteltyjen puolisoiden sosioekonomista asemaa. Tulokset osoittavat ilmiön esiintyneen Suomessa vuosina 1735-1885, mutta hieman yllättäen ilmiön voimakkuudessa ei havaita monotonista heikkenemistä tai vahvistumista tarkastelujakson aikana.fi
dc.format.extent74 + app. 109
dc.format.mimetypeapplication/pdfen
dc.identifier.isbn978-952-60-7950-9 (electronic)
dc.identifier.isbn978-952-60-7949-3 (printed)
dc.identifier.issn1799-4942 (electronic)
dc.identifier.issn1799-4934 (printed)
dc.identifier.issn1799-4934 (ISSN-L)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/31841
dc.identifier.urnURN:ISBN:978-952-60-7950-9
dc.language.isoenen
dc.opnGleich, David F., Assoc. Prof., Purdue University, USA
dc.publisherAalto Universityen
dc.publisherAalto-yliopistofi
dc.relation.haspart[Publication 1]: Eric Malmi, Marko Rasa, and Aristides Gionis. AncestryAI: A tool for exploring computationally inferred family trees. In Proceedings of the 26th International Conference on World Wide Web Companion (WWW 2017 Companion, Demo Track), Perth, Australia, pages 257–261, 2017. DOI: 10.1145/3041021.3054728
dc.relation.haspart[Publication 2]: Eric Malmi, Aristides Gionis, and Arno Solin. Computationally Inferred Genealogical Networks Uncover Long-Term Trends in Assortative Mating. In Proceedings of The 2018 Web Conference (WWW 2018), Lyon, France, 10 pages, 2018. DOI: 10.1145/3178876.3186136
dc.relation.haspart[Publication 3]: Eric Malmi, Arno Solin, and Aristides Gionis. The blind leading the blind: Network-based location estimation under uncertainty. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2015), Porto, Portugal, pages 406–421, 2015. DOI: 10.1007/978-3-319-23525-7_25
dc.relation.haspart[Publication 4]: Eric Malmi, Nikolaj Tatti, and Aristides Gionis. Beyond rankings: comparing directed acyclic graphs. Data Mining and Knowledge Discovery, 29, pages 1233–1257, 2015. DOI: 10.1007/s10618-015-0406-1.
dc.relation.haspart[Publication 5]: Eric Malmi, Sanjay Chawla, and Aristides Gionis. Lagrangian relaxations for multiple network alignment. Data Mining and Knowledge Discovery, 31, pages 1331–1358, 2017. DOI: 10.1007/s10618-017-0505-2
dc.relation.haspart[Publication 6]: Eric Malmi, Aristides Gionis, and Evimaria Terzi. Active Network Alignment: A Matching-Based Approach. In Proceedings of the International Conference on Information and Knowledge Management (CIKM 2017), Singapore, pages 1687–1696, 2017. DOI: 10.1145/3132847.3132983
dc.relation.ispartofseriesAalto University publication series DOCTORAL DISSERTATIONSen
dc.relation.ispartofseries73/2018
dc.revGetoor, Lise, Prof., University of California Santa Cruz, USA
dc.revKlau, Gunnar W., Prof. Heinrich Heine University Düsseldorf, Germany
dc.subject.keywordentity resolutionen
dc.subject.keywordnetwork alignmenten
dc.subject.keywordmachine learningen
dc.subject.keywordgenealogyen
dc.subject.keywordcomputational social scienceen
dc.subject.keywordtietueiden linkitysfi
dc.subject.keywordverkostojen kohdistaminenfi
dc.subject.keywordkoneoppiminenfi
dc.subject.keywordsukututkimusfi
dc.subject.keywordlaskennallinen yhteiskuntatiedefi
dc.subject.otherComputer scienceen
dc.titleCollective Entity Resolution Methods for Network Inferenceen
dc.titleKollektiivisia tietueiden linkitysmenetelmiä verkostojen päättelyynfi
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotDoctoral dissertation (article-based)en
dc.type.ontasotVäitöskirja (artikkeli)fi
local.aalto.acrisexportstatuschecked 2019-02-25_1154
local.aalto.archiveyes
local.aalto.formfolder2018_06_12_klo_11_22
Files
Original bundle
Now showing 1 - 7 of 7
No Thumbnail Available
Name:
isbn9789526079509.pdf
Size:
2.2 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
article1.pdf
Size:
799.31 KB
Format:
Adobe Portable Document Format
Description:
Final published version
No Thumbnail Available
Name:
article2.pdf
Size:
669.86 KB
Format:
Adobe Portable Document Format
Description:
Final published version
No Thumbnail Available
Name:
article3.pdf
Size:
1.03 MB
Format:
Adobe Portable Document Format
Description:
post print / author accepted version
No Thumbnail Available
Name:
article4.pdf
Size:
734.67 KB
Format:
Adobe Portable Document Format
Description:
Final published version
No Thumbnail Available
Name:
article5.pdf
Size:
1.57 MB
Format:
Adobe Portable Document Format
Description:
Final published version
No Thumbnail Available
Name:
article6.pdf
Size:
574.54 KB
Format:
Adobe Portable Document Format
Description:
Final published version