IBM ResearchMethods for Network Structure Prediction

Hisashi Kashima
IBM Research / Tokyo Research Laboratory© Copyright IBM Corporation 2006

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Methods for network structure prediction
Network-structured data
Link prediction problem (= network structure prediction problem)
Link prediction methods based on node information
Link prediction methods based on structural information[Our contribution] A parameterized model for link prediction

IBM Tokyo Research Laboratory

Network-structured data

© Copyright IBM Corporation 2006

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Network structured data represent relations among data as a graph
Relations among data are represented as a graph structure
A node represents a data
A link represents a relation between two data

⇔ In standard machine learning setting, data are represented as tables (=feature vectors)

Each node can also have an associated vector-structured data
In practice, we use botha datum

nameagesexaddress

…

○○40

male

Tokyo

…

××30

femaleOsaka…

table-structured data

ネットワーク構造データ
Network-structured
dataIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Several network structured data in the real worldNodes represents constituent elements and links represent relations among them
network
structured data

nodes

links

WWW

pages

hyperlinks

SNSpeoplecommunities

friendships
memberships

biologicalnetworks

genes
proteins

regulations
interactions

Not only those static relations, dynamic relations such as
e-mail exchanges
cooperation
can be represented by links

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Network structure analysis is called “link mining” in data mining
Fundamental tasks of link mining defined by Getoor et al.
Node-related tasks• Node ranking• Node classification• Node clustering
Structure-related tasks• Link prediction• Structured-pattern mining

Getoor & Riehl.: Link Mining: A Survey, KDD Exploration, vol. 7, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

We focus on link prediction in this talkFundamental tasks of link mining defined by Getoor et al.
Node-related tasks• Node ranking• Node classification• Node clustering
Structure-related tasks• Link prediction• Structured-pattern mining

Getoor & Riehl.: Link Mining: A Survey, KDD Exploration, vol. 7, 2005

IBM Tokyo Research Laboratory

Link Prediction Problem

How likely does a link exist ?

© Copyright IBM Corporation 2006

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Link prediction problem as semi-supervised learning:
Given partially observed network structure, predict the rest
GivenApplications：
Some node pairs with links:
Some node pairs without links:

Predict
whether links exist or not for theother unknown pairs
an element
in ii

Prediction of biological networks
Recommendation in SNSs
Identifying “hidden links” in terrorist
networks

an elementin ii

prediction

observed structure

predicted structure

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

The link prediction problem can be considered asa ranking problem of node pairs
The link predictor must answer, for a pair of nodes,
how likely a link exits (= ranking problem), orwhether or not a link exists (= classification problem)
between the nodes
Assumption: Existence of link is determined independently
How likely does a link exist ?

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Two types of information are available for link prediction:
Node features and structural features
Node features: information owned by nodes themselves
Combined to define node-pair features
Examples:• In SNSs, each person has his/her own personal information such as address, age, ...
• In protein networks, each protein (= a node) has its own sequence information

Structural features: information owned by link structures around node pairs
Usually, inherently defined for node pairs
Traditionally proposed in the context of social network analysis in sociometrics
Also proposed in information retrieval
structural
Link prediction is done based on them
nodefeatures
nodefeaturesfeaturesIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Link prediction based on node information

structuralfeatures
nodefeaturesnodefeatures

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Link prediction based on node features uses
feature vectors of node pairs
Ordinary classification is based on the node feature vector x(i) for the i-th data

Link prediction is based on the feature vector z(i,j) for node pair （i, j ）z(i,j) is constructed from the pair of node feature vectors (x(i) , x(j) )The simplest way to define z(i,j) is to take concatenation of two vectors,
or to take element-wise product (or whatever)z(i,j) = ( x1(i)・x1(j) , x2(i)・x2(j) , x3(i)・x3(j) , ...

), but this is not sufficient ...
since it can not represent “i has a particular feature and j has a corresponding (another)feature”
node-pair feature vectorz(i,j)

node featurevector

ijx(i)

x(ｊ)IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

A more general feature vector for a pair of nodes
is defined by tensor products of node feature vectors
The feature vector z(i,j) for node pair （i, j ） is defined bytensor product of the pair of node feature vectors (x(i) , x(j) )z(i,j) = x(i)x(j)

node-pair feature vectorz(i,j)= ( x1(i)・x1(j) , x1(i)・x2(j) , x1(i)・x3(j) , ...
x2(i)・x1(j) , x2(i)・x2(j) , x2(i)・x3(j) , ... ,x3(i)・x1(j) , x3(i)・x2(j) , x3(i)・x3(j) , ...

)node featurevector

ij

x(i)

x(ｊ)

A linear predictor for the node pair (i, j) is given as

prediction(i,j) := sign < w , z(i,j) >w is the parameter
Oyama & Manning: Using Feature Conjunctions across Examples for Learning Pairwise Classifiers, ECML 2004
Ben-Hur & Noble: Kernel methods for predicting protein–protein interactions, Bioinformatics, Vol. 21 Suppl. 1, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Kernelization is simple
Naive computation of the kernel between two node-pair feature vectors z(i,j) andz(k,l) seems to need O(#dimensions2)
(i,j)

z

But it can be efficiently computed in O(#dimensions) by< z(i,j), z(k,l) > = < x(i), x(k) > ・ < x(j), x(l) >ijx(i)x(ｊ)z(k,l)

When there is no ordering in a pair of nodes, symmetrize by< z(i,j), z(k,l) > + < z(i,k), z(j,l) >Then, feed them into SVM, and done

prediction(i,j) := signk,lk,lklx(k)x(l)(< z(i,j), z(k,l) > + < z(i,k), z(j,l) > )is the parameter

Oyama & Manning: Using Feature Conjunctions across Examples for Learning Pairwise Classifiers, ECML 2004
Ben-Hur & Noble: Kernel methods for predicting protein–protein interactions, Bioinformatics, Vol. 21 Suppl. 1, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

The tensor-product-based feature vector outperforms the element-wisefeature vector
Author network [Oyama & Manning]
tensor product（good）

Protein network [Ben-Hur & Noble]
proposed（good）

element-wise（bad）traditional（bad）

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

More efficient alternatives...
The kernel method enables computation in O(#dimensions), but needs
O(#nodes2) parameters

Yamanishi et al. propose more efficient way using kernel canonical correlation
analysis (KCCA) by using only O(#nodes) parameters
Kato et al. incorporate integration of multiple data sources

Yamanishi et al.: Protein Network Inference from Multiple Genomic Data: A Supervised Approach, ISMB 2004
Vert & Yamanishi: Supervised Graph Inference, NIPS 2004
Kato, Tsuda and Asai: Selective Integration of Multiple Biological Data for Supervised Network Inference,
Bioinformatics, Vol. 21, 2005

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Link prediction based on structural information

structuralfeatures
nodefeatures

nodefeatures

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Link metrics define how likely a link exists between two nodes
Link metrics := Degrees of likelihood of a link existing between two nodes
based on the structural information around them
Usually, inherently defined for node pairs
Traditionally proposed in the context of social network analysis in sociometrics
Also proposed in information retrieval
Example:• “the friends of your friends are probably in your friends”⇒ “Two nodes with many common neighbor nodes probably has a link”
How to use the link metrics ?
Prediction only from positive examples : To predict links in descending order ofany link metricSupervised learning: To include as a part of feature vectors for node pairs

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Several existing link metrics
Several link metrics are used in studies of social networks and scale-free networks
Common neighbors: Likelihood of link existence is proportional to the number of common neighbors

Weighted common neighbors:(i) is the set of neighbornodes of node i（used in information retrieval）
Long-distance common neighbors:
pathi,j(l) is the set of pathsof length l from node i to j

- almost identical to the diffusion kernel
Preferential attachment: Nodes with many neighbors will get more neighbors

Most of them are inspired by corresponding evolution models of network structure

Liben-Nowelly & Kleinberg: The Link Prediction Problem for Social Networks, CIKM 2004

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Appendix: Relations among link metrics
Spearman correlations (= correlations of orders) for metabolic network data）
Large coefficients indicate that the corresponding metrics are similar

preferential

Visualization by MDS• preferential attachment andcommon neighbors are most apartproposed

Katz_0.05

Jaccard's
Adamic/AdarcommonIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

“How high can we go only with structural information ?”We parameterized link metrics to improve prediction performance
Motivation: Will parameterized versions of link metrics improve predictive
performance ?
We propose a systematic way of deriving parameterized link metrics
from parameterized network evolution models
As an instance, we parameterized the “copy-and-paste” model
Originally proposed for modeling evolution of WWW structure by Kleinberg et al.
Also makes sense as an evolution model of biological networkskikia copy occurs with prob. wij
jevolutionover time

jH. Kashima and N. Abe: A Parameterized Probabilistic Model of Network Evolution for Supervised Link Prediction,
IEEE International Conference on Data Mining (ICDM), 2006 (To appear).

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Experimental results: Parameterization works well
Task: Structure prediction of two biological networks
The proposed method outperformed over various link metrics（parameterization of the other metrics ... future work）
precision (%)

the proposed method
outperforms

100
90

precision (%)
100

the proposed method
outperforms

90

80

2080
proposed70
Katz_0.0560
preferential50
Adamic/Adar
40
Jaccard's
30
common20

10107060
50
403000501000recall0(%)

proposed
Katz_0.05
preferential
Adamic/Adar
Jaccard'scommon50100

Metabolic network

protein-protein interaction network#nodes：700#nodes： 3000

recall (%)

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

The proposed framework enables to derive parameterized link metrics
from parameterized network evolution models
Our framework offers a systematic way of deriving link metrics
from the parameterized network evolution models
In many cases, enough evolution history of network structures is not available,
so parameter estimation is not possible
Our solution
1. Derive the stationary expected state of the network structure
2. Fit the stationary expected state to the known part of the network

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Step 1. Derive the expected stationary state of the network structure
Definition:link label

network structure at time t:= 1 if a link exists between (i, j):= 0 if not exists
Underlying Markov model of network evolution

fw is the transition function with parameter w
Problem: w can not be identified since the evolution history
is not available
We only know “the partial structure of the current network”) We need a constraint ...
Solution: Consider the “stationary expected state”
as the “representative state”

ijIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

Step 2: Fit the stationary expected state to the known part of thenetwork
We hypothesize the stationary expected state
represents thecurrent network structure
Maximize the following objective function with respect to the parameter w

i.e. Find the most appropriate parameter w* that reproduces the observed partof the networkfor existing links
for non-existing links
for unknown partare the predicted link labels

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

An example:
Our network evolution Markov model fw is the “copy-and-paste” modelAt each step, a link label is copied somewhere in the networkfrom node i to node j with probability wi,j

1.
2.
3.

Procedure
Select a pair of nodes (i,j) with probability wi,jSelect node k uniformly at random (other than j)
Link label
is copied to (j,k)

wi,j is interpreted as node i ’s “influence” on node jj-san’s association is affected by i-san’s association

kikia copy occurs with prob. wijjevolution
over timejIBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

In the “copy-and-paste” model,a link label at the next time step is determined by one of two possibilities
Link label
at time t+1 is determined by one of the following twopossibilities
1. The link label was copied from somewhere at time t
2. A copy occurred somewhere else at time t , so the link label remained the same

wascopied from k to j

2. The copy at time t wasoccurred somewhere else

wascopied from k to i

1. The link label wascopied at time tkikia copy occurs with prob. wijjevolution
over timej

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

The stationary expected state of the “copy-and-paste” model is fed into
the optimization problem
The original “copy-and-paste” network evolution model istake the expectation and t ! 1
The derived stationary expected state is

The optimization problem issubstitute into the optimization problem

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

The resulted optimization problem is solved by using EM algorithm
The stationary expected state has unobserved variables (= link labels to be predicted)
some未知かもunobserved

Our solution: EM algorithm【M-Step】 Fix the unobserved link labels, estimate the parameter• Exponentiated gradient descent solves this efficiently【E-Step】 Fix the parameter, and evaluate the expected value of the unobserved link labels• by solving a system of simultaneous linear equations
In practice, we can do this in a sequential manner, not in a batch manner

IBM Tokyo Research Laboratory© Copyright IBM Corporation 2006

In summary, we proposed a new parametric model for link prediction
We introduced
A link prediction method based on evolution models of network structure
A parameterized evolution model based on the node-copy model
An efficient estimation algorithm

IBM Tokyo Research Laboratory

Methods for link prediction
Network-structured data
Link prediction problem
Link prediction methods based on node information
Link prediction methods based on structural information[Our contribution] A parameterized model for link prediction© Copyright IBM Corporation 2006