Mining and learning in graphs -workshopissa oli kiinnostavaa tutustua eri näkökulmiin, joista graafeja ja verkkoja voidaan tutkia. Paikalla oli niin soveltavia tutkijoita, kuin hyvin teoreettisesta näkökulmasta graafeja sivuavia ongelmia lähestyviä.
Menetelmien teoreettisia yksityiskohtia koskevista esityksistä oli välillä hankalaa saada otetta tuntematta tarkemmin tutkimuskenttää ja esitettyjen todistusten merkitystä suhteessa aikaisempaan tutkimukseen. Osa esityksistä olikin kuin olisi alkanut seurata elokuvaa tai tv-sarjaa keskeltä ja yrittänyt sen perusteella ymmärtää juonta.
Tässä alla on joitakin muistiinpanoja satunnaisiin konferenssiesityksiin liittyen, jotka tuskin kiinnostavat muita juurikaan. Muutakin kiinnostavaa tuolla oli, mutta niistä en kirjoitellut muistiin mitään, mitä saisi helposti tänne dokumentoitua. Laitetaan muistiinpanot kuitenkin tänne, ei kai siitä haittaakaan ole…
Pienistä ja isoista verkoista
Niin sanotut graph mining-menetelmät olivat kiinnostavia, tosin on vaikea sanoa, mikä niiden hyöty on esimerkiksi sosiaalisia verkkoja tai ystävyysverkkoja tutkittessa. Niiden ideana on hakea tietyntyyppisiä, yleisesti esiintyviä muodostelmia verkoista.
Graph mining -menetelmiin liittyy myös graafien haku, jossa ajatuksena on, että on iso tietokanta erilaisia, tyypillisesti pieniä graafeja, kuten vaikka kemiallisia yhdisteitä. Tarkoituksena on hakea näiden graafien joukosta tiettyjä kuvioita jotka esiintyvät joko täsmälleen verkoissa tai sitten kuvioita, jotka vastaavat suurin piirtein verkoissa esiintyviä.
On vaikeaa sanoa, löytyisikö graph mining tai hakumenetelmien avulla jotakin kiinnostavaa esimerkiksi ystävyysverkoista. Ehkäpä joitakin kiinnostavia rakenteita, kuten vaikkapa perheitä tai kaveripiirejä, voisi löytyä myös ystävyysverkoista. Haasteena olisi kuitenkin datan sotkuisuus: sosiaaliset verkot ovat harvoin siistejä ja selkeitä, sivuja tai solmuja puuttuu yleensä ja peruskäsitteitä, kuten “ystävyys” ei voi määrittää yksiselitteisesti. Tämä on aika erilaista kuin vaikkapa kemiallisten yhdisteiden verkkokuvauksissa.
Kiinnostavaa onkin, kuinka eri käyttötarkoituksissa graafit ovat hyvin erilaisia. Kemiassa tarvitaan tyypillisesti satoja tai tuhansia graafeja, joista jokaisessa on kuitenkin vain muutama kymmen solmua. Toista ääripäätä edustavat kommunikaatioverkot: verkkoja on usein ainoastaan yksi, mutta siinä voi olla tuhansia solmuja, mikäli tieto on kerätty vaikkapa internetistä.
Luonnollisestikin erityyppisissä verkoissa käytettävät menetelmät ovat hyvin erilaisia: jos pienessä verkossa riittää, että menetelmä on verkon kokoon nähden polynomiaikainen (esim. O(n^3) tai O(n^6)), isoissa verkoissa menetelmien pitäisi olla mielellään lähestulkoon lineaarisia suhteessa verkon kokoon.
Pierre Baldi
Kutsuttujen puhujien esitykset olivat selkeitä ja tarjosivat kaikenlaista pientä ajatuksentynkää.
Workshopin ensimmäinen puhuja keskiviikkona oli Pierre Baldi, joka kertoi kemiallisesta laskennasta ja kemiallisten yhdisteiden kuvaamisesta verkkoina. Baldin mukaan kemiassa ongelmana on toistaiseksi ollut se, että hyviä tietokantoja eri yhdisteistä ei ole ollut käytettävissä tai tieto on ollut upotettuna erilaisten kaupallisten tietokantojen uumeniin. Nyt tavoitteena on kerätä kattava kokoelma kemiallisista yhdisteistä sekä niiden ominaispiirteistä.
Baldi puhui myös etäisyysmitoista, joilla voidaan kertoa, kuinka samanlaisia eri verkot ovat. Näitä mittoja voidaan käyttää apuna esimerkiksi verkkojen haussa tai ryhmittelysssä.
Luc de Raedt
Luc de Raedt puhui loogisesta laskennasta ja Prolog-variantista nimeltään Problog, jossa tarkan logiikan sijaan käytetään todennäköisyyksiä. Tämän kiinnostavuudesta on vaika sanoa kovinkaan paljoa, sillä looginen ohjelmointi ei ole minulle lainkaan tuttua.
Jianwei Han
Torstain aloitti Jianwei Han, ilmeisesti jonkinmoinen tiedonlouhinnan guru, joka on kirjoittanut alan perusteoksen ja ziljardeja artikkeleita. Han puhui ymmärrettävästi graafien hakemisesta, yleisten piirteiden löytämisestä ja rajoitteiden käyttämisestä hauissa. Rajoitteet voivat olla esimerkiksi muotoa “graafin max-degree > 10″, “kuviossa ei ole lenkkejä”, “kuviossa on yli kymmenen sivua” tai “kuvio sisältää muodostelman [x]“. Myös solmujen tai sivujen attribuutteja voidaan käyttää rajoitteina.
Lise Getoor
Myös Lise Getoorin esitys oli kiinnostava. Hän pohti verkkodatan siivoamista, toisin sanoen “datagraafin” muuttamista “informaatiograafiksi”. Vastaavasti voi puhua “kommunikaatioverkon” muuttamisesta “sosiaaliseksi verkoksi”. Tavoitteena on löytää olennaiset piirteet sotkuisesta, virheitä ja puutteita sisältävästä verkkodatasta esimerkiksi samanmerkityksisiä solmuja yhdistämällä ja linkkejä tai niiden atribuutteja/labeleita ennustamalla.
Eräs esimerkki on ns. “entity resolution” ongelma, jossa pyritään löytämään duplikaatit vaikkapa sitaattiverkoista. Sitaattidatassa saman henkilön nimi on usein voitu kirjoittaa erilaisin tavoin, vaikkapa “James Dean”, “J. Dean” tms. toisaalta sama nimi, kuten “J. Dean” voi viitata useaan henkilöön. Tavoitteena on silloin sitaattiverkon avulla päätellä, mitkä nimet viittaavat samaan henkilöön. Ongelmassa tutkitaan yhtä aikaa nimien kirjoitusasun samanlaisuutta ja sosiaalisten naapurustojen samanlaisuutta. Näille voidaan antaa painokertoimet, jotka kertovat, kuinka paljon näitä molempia ominaisuuksia halutaan korostaa. Tiheillä verkoilla Gibbs ja ICA toimivat hyvin.
Eräs linkkien ennustamisen ongelma, jonka Getoor erikseen mainitsi, oli outliereiden ennustaminen. Esimerkiksi jos tietyn henkilön sosiaalisista suhteista yksi poikkeaisi dramaattisesti muista, sen voisi löytää tällaisin menetelmin. Mihinköhän kaikkeen tätä voisi käyttää?
Getoor kertoi, että vähitellen on muodostunut Statistical Relational Learning -yhteisö, joka on keskittynyt nimenomaan tilastollisiin tapoihin tutkia verkkoja. Workshopin osallistujista ainakin Luc de Raedt ja Kristian Kersting ovat SRL-tilaisuuksiin Getoorin lisäksi. Getoor promosi samalla myös ilmeisesti vastikää ilmestynyttä kirjaa jonka aiheena on nimenomaan SRL.
Kysymykseen dynaamisten verkkojen tutkimuksesta Getoor vastasi muistaakseni, että ei ole varsinaisesti siihen paneutunut, mutta että tänä vuonna olisi aiheesta Dymax-niminen workshop.
Alex Smola
Perjantain ainoa kutsuttu puhuja oli Alex Smola, graafien välisiin etäisyyksiin paneutunut tyyppi, joka on kirjoittanut aiheesta myös neljä kirjaa. Aiheena oli “learning graph matching”, siis etäisyysmittojen perustana oli jonkinmoiset koneoppimismenetelmät.
Jotenkin Smola ja kumppanit päätyivät webbisivujen ranking-ongelmasta (mitkä samanlaisia sivuja tms) graph matching -ongelmiin, joissa tässä tapauksessa on ideana on löytää vastinpisteitä solmuille joltakinosin samankaltaisten verkkojen välillä.
Menetelmää voi käyttää esimerkiksi vastinpisteiden löytämiseen kartoista, jotka ovat vaikkapa vähän eri tarkkuisia, tai jopa toinen kartta pikselimuodossa ja toinen vektoreina.
Lähtökohtana oli “unkarilainen avioliitto” (hungarian marriage), jossa joukolle miehiä ja naisia pitäisi löytää vastinparit. Smolan mukaan tässä päädytään helposti neliölliseen approksimaatioon (quadratic approximation), joka on paha asia, sillä sitä muotoa olevat ongelmat ovat tunnettuja siitä, että niiden ratkaisu on hankalaa. Smola totesi, että tämän osoittaa jo se, että ongelmia ratkaistaan muurahaiskolonna-algoritmeilla, geneettisillä menetelmillä ja tabu-search -tekniikoilla, joihin yleensä turvaudutaan vain suurimmassa hädässä, siis silloin, kun ei keksitä mitään parempaa lähestymistapaa.
Jonkinmoisella ovelalla kikalla Smola ja kumppanit saivat kuitenkin ratkaistua ongelman, joka muistaakseni sisälsi suuria määriä matriiseja :)
Muita esityksiä
Kaspar Riesen pohti, kuinka laskea aikaisempaa tehokkaammin “edit distance” kahden graafin välillä, eli kuinka monta operaatiota graafille A pitää tehdä, jotta se saadaan muutettua graafiksi B. Operaatioiden määrää voidaan käyttää etäisyysmittana verkkojen välillä ja esimerkiksi klusteroinnissa. Noodit voivat olla labeloituja. Tarkka menetelmä toimii n. 12 noodin verkoille kun taas approksimatiivinen (?) versio on käyttökelpoinen verkoissa, joissa on n. 150 solmua.
Shawandra Hillin esitys oli kiinnostava, sillä sen aihepiiri oli jossakin määrin tuttu: kuinka käyttää linkkejä ihmisten välillä esimerkiksi tuotteiden markkinoinnissa. Puhelinoperaattorin palvelun markkinointikampanjan perusteella Hill havaitsi, että verkostonaapurit ostivat palvelun viisi kertaa todennäköisemmin kuin käyttäjät, joiden naapurit eivät käyttäneet palvelua.
Toteutuksessa avainsanoja olivat gaussian random field ja iterative relaxation inference. Vain ensimmäisen asteen naapurusto taisi olla käytössä. Ja verkkoa karsittiin puhelun pituuden cutoff-rajoittimella, joka lisäsi tehoa ja poisti epäolennaisia sivuja. Edgejä poistettiin kokoluokan verran (joka kymmenes?), joka myös paransi ennustuskykyä.
Joku kysyi osuvasti Hilliltä yksityisyydestä (privacy), johon Hill vastasi, että tieto anonymisoitiin ja että tuloksia ei hyödynnetty todellisessa kampanjassa.
Nowozinin esitys graafien käyttämisestä tietokonenäössä kuvan vastinpisteiden löytämiseen oli kiinnostava.
Zhao Xu:n menetelmä parametrien estimointiin esimerkiksi tuote-ihminen-suositus -verkossa oli kiinnostava, joskin koska tapa jolla malli oli esitetty ei ollut ennalta tuttu, menetelmä vaatisi vielä tarkempaa paneutumista. Paljon oli testattu mm. kollapsoitua gibbsiä, blokattua gibbsiä, stick breaking -rakennetta, mean field -menetelmiä jne. (Kollapsoitu) Gibbs toimi paremmin, mutta mean field -lähestymistapa oli selvästi nopeampi eikä merkittävästi huonompi.
