Collective Entity Resolution Methods for Network Inference
Loading...
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2018-06-20
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2018
Major/Subject
Mcode
Degree programme
Language
en
Pages
74 + app. 109
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 73/2018
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.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.Description
Supervising professor
Gionis, Aristides, Prof., Aalto University, Department of Computer Science, FinlandKeywords
entity resolution, network alignment, machine learning, genealogy, computational social science, tietueiden linkitys, verkostojen kohdistaminen, koneoppiminen, sukututkimus, laskennallinen yhteiskuntatiede
Other note
Parts
-
[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 View at publisher
-
[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 View at publisher
-
[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 View at publisher
-
[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. View at publisher
-
[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 View at publisher
-
[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 View at publisher
