Collective Entity Resolution Methods for Network Inference

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Malmi, Eric
dc.date.accessioned 2018-06-12T09:02:52Z
dc.date.available 2018-06-12T09:02:52Z
dc.date.issued 2018
dc.identifier.isbn 978-952-60-7950-9 (electronic)
dc.identifier.isbn 978-952-60-7949-3 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/31841
dc.description.abstract Data 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.abstract Datasta 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.extent 74 + app. 109
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 73/2018
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.subject.other Computer science en
dc.title Collective Entity Resolution Methods for Network Inference en
dc.title Kollektiivisia tietueiden linkitysmenetelmiä verkostojen päättelyyn fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science en
dc.subject.keyword entity resolution en
dc.subject.keyword network alignment en
dc.subject.keyword machine learning en
dc.subject.keyword genealogy en
dc.subject.keyword computational social science en
dc.subject.keyword tietueiden linkitys fi
dc.subject.keyword verkostojen kohdistaminen fi
dc.subject.keyword koneoppiminen fi
dc.subject.keyword sukututkimus fi
dc.subject.keyword laskennallinen yhteiskuntatiede fi
dc.identifier.urn URN:ISBN:978-952-60-7950-9
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Gionis, Aristides, Prof., Aalto University, Department of Computer Science, Finland
dc.opn Gleich, David F., Assoc. Prof., Purdue University, USA
dc.contributor.lab Data Mining Group en
dc.rev Getoor, Lise, Prof., University of California Santa Cruz, USA
dc.rev Klau, Gunnar W., Prof. Heinrich Heine University Düsseldorf, Germany
dc.date.defence 2018-06-20
local.aalto.acrisexportstatus checked 2019-02-25_1154


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account