Graph visualization using latent variable models

Abstract

A graph consists of a set of nodes and a set of edges; each edge connects two nodes so that a network is formed. Many important data sets in various fields can he expressed as graphs. For example, epidemiologists analyze social networks to understand how diseases spread, and biologists study protein-protein interaction networks to gain insight into biological functions and diseases. Graph drawing algorithms that automatically generate drawings of graphs are essential tools for understanding graphs.

Graph visualization is not an easy problem. This thesis is based on the simple observation that it is in general impossihle for a single visualization to capture every aspect of a graph. It follows that the best we can do is to decide what aspects of the graph are most important to us, extract them from the graph, and visualize them as well as we can. We cannot avoid making a compromise, but we can at least make a principled compromise. The main contribution of this thesis is a new graph visualization method that does exactly that. Specifically, the proposed method is a so-called straight-line graph drawing method, which means that it draws nodes as points in the plane and draws any connecting edges as straight lines.

I make explicit my assumptions of what is essential in a graph by postulating a latent variable model for the graph. As a result the important aspects of a graph are in fact captured by the latent variables of the model, which can be estimated using standard Bayesian inference techniques. There is a high-dimensional vector of latent variables for each node in the graphs, so deciding on anode layout based on the latent vectors is actually a dimensionality reduction problem. For this I use NeRV, a state-of-the-art dimensionality reduction method specifically designed for principled visualization. I call the resulting method LDA-NeRV.

A survey of the literature reveals that most existing graph drawing methods are not based on explicit choices of how and what to visualize. Thus the proposed method represents a significant theoretical contribution in the field of graph drawing. Comparisons with three state-of-the-art graph drawing methods on three different graphs show that LDA-NeRV is capable of revealing structure that remains hidden with other methods.

Graafi eli verkko koostuu joukosta solmuja ja joukosta kaaria; jokainen kaari kytkee yhteen kaksi solmua. Verkkomuotoista dataa esiintyy useilla aloilla. Esimerkiksi epidemiologit analysoivat sosiaalisia verkkoja ymmärtääkseen tautien leviämistä, ja biologit tutkivat proteiinivuorovaikutusverkkoja ymmärtääkseen biologisia toimintoja tai sairauksia. Automaattisesti graafeista kuvia tuottavat graafinpiirtomenetelmät ovat tärkeitä työkaluja graafien tutkimisessa.

Graafivisualisointi ei ole helppo ongelma. Tämä työ lähtee siitä yksinkertaisesta havainnosta, että yksittäisen kuvan on yleisesti ottaen mahdotonta esittää graafin kaikkia mahdollisia piirteitä; jokainen kuva edustaa jonkinlaista kompromissia. Näin ollen paras vaihtoehtomme on päättää, mitä piirteitä pidämme tärkeimpinä, ja pyrkiä visualisoimaan ne mahdollisimman tehokkaasti. Työni pääasiallinen kontribuutio on uusi graafinpiirtomenetelmä, joka toimii juuri näin.

Formalisoin oletukseni siitä, mikä graafissa on olennaista, muotoilemalla sille niin sanotun latenttimuuttujamallin. Koska mallin latenttimuuttujat näin ollen vangitsevat graafin minulle olennaiset piirteet, saan graafille olennaisiin piirteisiin keskittyvän esitysmuodon estimoimalla latenttimuuttujat. Estimointi tapahtuu normaalilla Bayesilaisella päättelyllä. Estimoinnin jälkeen jokaista solmua vastaa latenttimuuttujavektori, joten solmujen paikan määrääminen tasossa latenttimuuttujien perusteella on itse asiassa dimensionpienennysongelma. Tähän ongelmaan sovellan NeRViä, nimenomaan periaatteelliseen visualisointiin suunniteltu dimensionpienennysmenetelmä. Kutsun edellä kuvatuista askeleista yhdessä syntyvää menetelmää LDA-NeRViksi.

Kirjallisuuskatsaus paljastaa, ettei valtaosa käytössä olevista graafinpiirtomenetelmistä perustu selkeihin valintoihin sen suhteen, mitä visualisoida ja miten. Näin ollen LDA-NeRV on merkittävä teoreettinen kontribuutio graafinpiirron alalla. Kokeet, joissa vertasin LDA-NeRViä ja kolmea alan parhaimmistoa edustavaa menetelmää kolmen eri graafin piirtämisessä, osoittivat, että LDA-NeRV kykenee tuomaan esiin rakennetta joka jää muilla menetelmillä piiloon.