Local blog for Italian speaking developers
Innovazioni nell'apprendimento delle rappresentazioni grafiche
5 luglio 2019
Pubblicato da Alessandro Epasto, Senior Research Scientist e Bryan Perozzi, Senior Research Scientist, Graph Mining Team
I dati relazionali che rappresentano le relazioni tra entità sono onnipresenti sul Web (ad esempio, i social network online) e nel mondo fisico (ad esempio, nelle reti di interazione proteica). Tali dati possono essere rappresentati come un
grafo
con
nodi
(ad es. utenti, proteine) e
spigoli
che li collegano (es.
rapporti di amicizia
, interazioni proteiche). Data la diffusa prevalenza dei grafi, l'
analisi dei grafi
svolge un ruolo fondamentale nel machine learning e trova applicazioni in
clustering
,
previsione dei legami
,
privacy
e
altro ancora
. Per applicare i metodi di machine learning ai grafi (ad esempio, predire nuove amicizie o scoprire interazioni proteiche sconosciute) è necessario
apprendere
una rappresentazione del grafo che può essere utilizzata negli algoritmi ML
.
Tuttavia, i grafi sono strutture intrinsecamente combinatorie costituite da parti discrete come nodi e spigoli, mentre molti metodi comuni ML, come le reti neurali, favoriscono le strutture continue, in particolare le rappresentazioni vettoriali.
Le rappresentazioni vettoriali sono particolarmente importanti nelle reti neurali, in quanto possono essere utilizzate direttamente come livelli di input. Per aggirare le difficoltà nell'utilizzo di rappresentazioni grafiche discrete in ML,
i metodi di
graph embedding
apprendono uno spazio vettoriale continuo per il grafo, assegnando ciascun nodo (e/o spigolo) nel grafo a una posizione specifica in uno spazio vettoriale. Un approccio popolare in quest'area è quello dell'apprendimento delle rappresentazioni basato sulla passeggiata aleatoria (o random walk), come descritto in
DeepWalk
.
A sinistra:
La nota rete di
Karate
che rappresenta un social network.
A destra:
Embedding di uno spazio continuo dei nodi nel grafo usando
DeepWalk
.
Qui presentiamo i risultati di due paper recenti sul graph embedding: "
Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
" presentato al
WWW’19
e "
Watch Your Step: Learning Node Embeddings via Graph Attention
" al
NeurIPS’18
. Il primo paper introduce una nuova tecnica per l'apprendimento di più embedding per nodo, consentendo una migliore caratterizzazione delle reti con comunità sovrapposte. Il secondo affronta il problema fondamentale dell'ottimizzazione degli iperparametri nei graph embedding, consentendo di implementare facilmente metodi di graph embedding con meno sforzo. Siamo inoltre lieti di annunciare che abbiamo rilasciato il codice per entrambi i paper nel repository github Google Research per i
graph embedding
.
Apprendimento di rappresentazioni di nodi che catturano molteplici contesti sociali
In quasi tutti i casi, il presupposto chiave dei metodi di graph embedding standard è che un
singolo
embedding deve essere appreso per ogni nodo. Pertanto, si può affermare che il metodo di embedding cerca di identificare il
singolo
ruolo o la singola posizione che caratterizza ciascun nodo nella geometria del grafo. Lavori recenti hanno osservato, tuttavia, che i nodi nelle reti reali appartengono a più comunità
sovrapposte
e svolgono
più
ruoli: pensa al tuo social network, in cui partecipi sia alla comunità della tua famiglia sia a quella lavorativa. Questa osservazione motiva la seguente domanda di ricerca: è possibile sviluppare metodi in cui i nodi sono embedded in più vettori, rappresentando la loro partecipazione in comunità sovrapposte?
Nel
paper del WWW’19
, abbiamo sviluppato
Splitter
, un metodo di embedding non supervisionato che consente ai nodi di un grafo di disporre di più embedding per meglio codificare la partecipazione a più comunità. Il nostro metodo si basa sulle recenti innovazioni nel clustering sovrapposto basato sull'
analisi delle reti egocentrate
, usando nello specifico il
concetto di persona graph
. Questo metodo prende un grafo
G
e crea un nuovo grafo
P
(chiamato
persona graph
), dove ogni nodo in
G
è rappresentato da una serie di repliche chiamate i nodi
persona
. Ogni persona di un nodo rappresenta un'istanza del nodo in una comunità locale a cui appartiene. Per ogni nodo U nel grafo, analizziamo la rete egocentrata del nodo (cioè il grafo che collega il nodo ai suoi vicini, in questo esempio A, B, C, D) per scoprire le comunità locali a cui appartiene il nodo. Ad esempio, nella figura seguente, il nodo U appartiene a due comunità: Cluster 1 (con gli amici A e B, ipotizziamo i membri della famiglia di U) e Cluster 2 (con C e D, ipotizziamo i colleghi di U).
Rete egocentrata del nodo U
Quindi, usiamo queste informazioni per "dividere" il nodo U nelle sue due
persona
U1 (la persona "famiglia") e U2 (la persona "lavoro"). Questo districa le due comunità, in modo che non siano più sovrapposte.
Il metodo di scissione dell'ego che separa i nodi U in 2 persona.
Questa tecnica è stata utilizzata per migliorare i risultati allo stato dell'arte nei metodi di graph embedding, mostrando una
riduzione fino al 90%
nell'errore di previsione dei legami (ovvero, prevedendo quale legame si formerà in futuro) su una varietà di grafi. La ragione principale di questo miglioramento è la capacità del metodo di disambiguare comunità altamente sovrapposte presenti nei social network e in altri grafi del mondo reale. Convalidiamo ulteriormente questo risultato con un'analisi approfondita dei grafi in co-paternità, in cui gli autori appartengono a comunità di ricerca sovrapposte (ad es., machine learning e data mining).
In alto a sinistra:
Un tipico grafo con comunità fortemente sovrapposte.
In alto a destra:
Un embedding tradizionale del grafo a sinistra usando
node2vec
.
In basso a sinistra:
Un grafo persona del grafo precedente.
In basso a destra:
L'embedding Splitter
del persona graph. Nota come il persona graph distingue chiaramente le comunità sovrapposte del grafo originale e Splitter
restituisce embedding ben separati.
Ottimizzazione automatica degli iperparametri tramite l'attenzione al grafo.
I metodi di graph embedding hanno mostrato prestazioni eccezionali su varie applicazioni basate su ML, come ad esempio
previsione dei legami e classificazione dei nodi
, ma hanno alcuni iperparametri che devono essere impostati manualmente. Ad esempio, quando si apprendono gli embedding, i nodi vicini sono più importanti da catturare rispetto ai nodi più lontani? Anche se gli esperti possono essere in grado di ottimizzare questi iperparametri, è necessario farlo indipendentemente per ciascun grafo. Per ovviare a questo lavoro manuale, nel nostro
secondo paper
, abbiamo proposto un metodo per apprendere automaticamente gli iperparametri ottimali
.
Nello specifico, molti metodi di graph embedding, come
DeepWalk
, utilizzano random walk per esplorare il contesto attorno a un dato nodo (ad es. i vicini diretti, i vicini dei vicini, ecc.). Tali random walk possono avere molti iperparametri che consentono di ottimizzare l'esplorazione locale del grafo, regolando così l'attenzione prestata dagli embedding ai nodi vicini. Grafi diversi possono presentare differenti modelli di attenzione ottimale e quindi diversi iperparametri ottimali (vedi l'immagine sotto, dove mostriamo due diverse distribuzioni di attenzione). Watch Your Step formula un modello per l'esecuzione dei metodi di embedding basati sugli iperparametri sopra menzionati. Quindi, ottimizziamo gli iperparametri per massimizzare le prestazioni previste dal modello, usando la
backpropagation
(retropropagazione) standard. Abbiamo scoperto che i valori appresi mediante backpropagation concordano con gli iperparametri ottimali ottenuti dalla ricerca della griglia.
Il nostro nuovo metodo per l'ottimizzazione automatica degli iperparametri, Watch Your Step, utilizza un modello di attenzione per apprendere diverse distribuzioni di contesto nei grafi. Sopra sono mostrati due esempi di vicinanze locali relative a un nodo centrale (in giallo) e le distribuzioni di contesto (gradiente rosso) apprese dal modello. Il grafo a sinistra mostra un modello di attenzione più diffuso, mentre la distribuzione a destra ne mostra uno concentrato sui vicini diretti.
Questo lavoro rientra nella crescente famiglia dell'
AutoML
, il cui scopo è quello di ridurre l'onere dell'ottimizzazione degli iperparametri, un problema comune nel machine learning pratico. Molti metodi AutoML utilizzano
la ricerca dell'architettura neurale
. Questo paper mostra invece una variante, in cui utilizziamo la connessione matematica tra gli iperparametri negli embedding e le formulazioni della matrice della teoria dei grafi. La parte "Auto" corrisponde all'apprendimento degli iperparametri del grafo mediante backpropagation.
Riteniamo che i nostri contributi miglioreranno ulteriormente lo stato della ricerca nel graph embedding in varie direzioni. Il nostro metodo per l'apprendimento degli embedding di nodi multipli traccia una connessione tra il campo ricco e ben studiato del rilevamento delle comunità sovrapposte e quello più recente di graph embedding, che riteniamo possa essere oggetto di fruttuose ricerche future. Un problema aperto in quest'area è l'uso di metodi di embedding multipli per la classificazione. Inoltre, il nostro contributo all'apprendimento degli iperparametri favorirà l'adozione del graph embedding, riducendo la necessità di costose ottimizzazioni manuali. Speriamo che il rilascio di questi paper e di questo
codice
aiuterà la comunità di ricerca a continuare in questa direzione.
Ringraziamenti
Ringraziamo Sami Abu-el-Haija che ha contribuito a questo lavoro e ora sta seguendo un dottorato di ricerca presso la USC. Per maggiori informazioni sul
team di Graph Mining
(parte di
Algorithm and Optimization
), visita le nostre pagine.
Etichette
Android
Firebase
machine learning
Google Cloud Platform
GDL
Eventi
Google Developers Live
Google Play
TensorFlow
App
Chrome
Cloud
api
GDLItalia
GDE
GDG
Google Assistant
iOS
Kotlin
Actions on Google
Deep Learning
AppEngine
AMP
BigQuery
Cloud Functions
Flutter
Android Studio
Google Developers Expert
Università
Google AppEngine
JavaScript
AI
Android Wear
GAE
Google Play Store
HTML5
Maps
security
Android App Development
AngularJS
IoT
Kubernetes
Annunci
Cloud Firestore
Cloud Machine Learning
Google I/O
Polymer
Android Things
Community
DevTools
Google App Engine
intelligenza artificiale
Entrepreneurship
Firebase Analytics
GSoC
Games
Google Cast
ML
open source
Crashlytics
Dart
Diversity
Drive
Google Data Studio
Google Play Games
TensorFlow Lite
Android Developers
Android O
Cloud Spanner
Cloud TPU
Compute Engine
DevFest
Google Compute Engine
Google Developers
Material Design
Mobile
PWA
Python
Startup
AIY Project
ARCore
Android Jetpack
AndroidDev
Androidq
Apps Script
Artificial Intelligence
Augmented Reality
Firebase Cloud Messaging
Google Cloud
Google Maps
Gsuite
IO19
ML kit
Research
VR
coding
unity
#io19
AR
Android Dev Summit
Android Developer
Android Q
Cardboard
Cloud AI
Coral
Developers
Dialogflow
Firebase Realtime Database
Gmail
Google AI
Google Cloud Messaging
Google ContainerEngine
Google Play Console
Kotlin Coroutines
NLP
Programming
Responsive Design
TensorFlowjs
Testing
WTM
Women
beacons
cloud storage
developer
node JS
student programs
women techmakers
API Cloud Vision
Add-ons
Android P
AndroidDevStory
Animation
AutoML
Brillo
Classroom
DSC
Database
Developer Student Clubs
Edge TPU
Fabric
Featured
Flutter Web
G Suite
GWT
GoLang
Google
Google Brain
Google Cloud Next
Google Container Engine
Google Developer Groups
Google I/O Extended
Graph
Hosting
Instant Apps
Keras
Livedata
Mobile Sites
Prediction
Privacy
Project Tango
SDK
Stackdriver
Tales
UI
Udacity
Virtual Reality
Web
Web Development
YouTube
analytics
android security
api.ai
courses
google io
indies
natural language processing
reti neurali
sign-in
young developers
2d Animation
3d
AIY
ARkit
Adversarial Learning
Alpha
Android App
Android App Developmen
Android App bundle
Android Architecture
Android Architecture Components
Android Auto
Android Automotive OS
Android Dev Summit Android Developer
Android Developer Challenge
Android Developers GooglePlayAwards
Android Development
Android Go
Android Instant App
Android Pie
Android Q Scoped Storage
Android Q audio
Android Styles
Android audio playback capture
Android codelabs
AndroidTV
AndroidX
Angular
Aogdevs
Api Design
App Development
App Distribution
Apps
Architecture
Architecture Components
Arduino
Best Practices
Betatesting
Bugs
C++
Certification
Cloud Anchors
Cloud Next
Cloud Run
Cloud Service Platform
Cloud Shell
Cloud Study Jam
Coached Conversational Preference Elicitation
Commerce
Community Connector
Computer Science
Consistency
Containers
Converge
Conversation Design
Crash Reporting
DLS Design
Dagger
Data Science
Databases
Dependency Injection
Design
Developer Communities
Developer Community
Developer Culture
Developer Story
Developing Media Apps
Development
Eager
Edge TPU Dev Board
Education
Emulatore Android
Error Message
Eslint
Europe
Firebase Extensions
Firebase Summit 2019
Firebasehosting
Flutter 1.5
Flutter at IO
FlutterDark
GCE
GDD
Game Development
Gboard
Gesture Navigation
Glass
Go
Google AI Quantum
Google App Script
Google Cloud Functions
Google Cloud billing
Google Coral
Google Developer Days
Google Home Hub
Google IOS Android
Google Identity Platform
Google Launchpad
Google Lens
Google Now
Google Photos
Google Play Devs
Google Play Indie Games Festival
Google Play Instant
Google Plus
Google codelabs
Google+
GoogleDevWeekly
GoogleLaunchpad
GooglePlay
Graphics
Healthcare
I/O
IO
IO19 Flutter
In-app Billing
Indie Games
Indie Games Festival
Indie games showcase
Indie showcase
Ingress
Instant Games
Issues
Java
Jetpack
Knative
Kotlin Beginners
Kotlin Everywhere
Kotlin codelabs
Lighthouse
Live Caption
Live Streaming
Localization
Location
M-Theory
Mondaygram
Monetization
NYT
NativeScript
Navigation
Neural Graph Learning
Neural Structured
Nodejs
OS
OS Updates
Olivex
One Time Codes
Online Education
PHA
Performance Monitoring
Policy
Posenet
Project Mainline
Project Treble
Quantum Computing Theory
Reactive Programming
Regression
Remote Config
Resonance Audio
Room
Scoped Storage
Semantics
Semi Supervised Learning
Serverless
Sms Retriever Api
Sms Verification
Speech Recognition
Swift
Tensorflow Core
Tensorflow Hub
Test Lab
Text
Tokenizer
Tpu
Transformers
UX
UX Design
UX Research
Universal Sentence Encoder
Unsupervised Data Augmentation
Unsupervised Learning
User Experience
Viewmodel
Voice
WWW
Wear OS
WebAssembly
Widget
Women in Tech
WomenTechmakers
android kotlin
app stability
assistant
audio recording
augmented faces
authsub
best practices and updates
billing
botnet
business
c++ games
cancer
chatbot
chrome privacy
codelab
codelabs
competition
daydream
designer
dominio .dev
error handling
event
firebase games
firebase gdc
firebase hosting
firebase unity
game center authentication
game testing
games authentication
gdc
google summer of code
googledevelopers
grow
hashcode
indie
indie developers
internship
kids
machine intelligence
machine learning accelerator
maker
multi-platform
nearby
oauth
openid
performance
persistent AR
privacy sandbox
prizes
prototype
purchase flows
queries
realtime
responsible AI
security rules
showcase
solutions challenge
startup africa roadtrip
startup times
students
summer of code
unity crashlytics
verify apps
win
Archivio Blog
2020
feb
gen
2019
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2018
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2017
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2016
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2015
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2014
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
2013
dic
nov
ott
set
ago
lug
giu
mag
apr
mar
feb
gen
Feed
Follow @GoogleDevsItaly
