Transcript Rethinking semantics

MetaFac: Community Discovery via
Relational Hypergraph Factorization
Tracking Multiple Relations in Social Media
Yu-Ru Lin1, Jimeng Sun2, Paul Castro2,
Ravi Konuru2, Hari Sundaram1 and Aisling Kelliher1
1Arts,
Media and Engineering, Arizona State University
2IBM T.J. Watson Research Center
The problem
raustin
What does s/he like?
(Q1)
History
How to model multirelational social data?
Dugg
Comments
Favorites
tweets
Friends
raustin
Favorites
following
(Q1)
How to model multirelational social data?
(Q2)
How to reveal
communities consistent
across multi-relations?
History
Dugg
Comments
Favorites
tweets
Friends
raustin
(Q3)
Favorites
following
How to track these
communities over time?
Our approach
(Q1)
How to model multi-relational
social data?
Metagraph for modeling
multi-relational social data
G
node: facet
hyperedge: relation
(Q2)
How to reveal communities
consistent across multi-relations?
community := a cluster of people who interact with resource
and each other in a coherent manner
pc
pi|c
i
j
xijk  c pc∙pi|c∙pj|c∙pk|c
k
Clustering as factorization
core tensor
facet factors
G
core tensor
facet factors
U(1)
Factorization on metagraph
U(2)
U(3)
U(4)
Metagraph factorization (MetaFac)
for community extraction on metagraph
data tensor
core tensor
facet factors
objective function
cost(G)= D((r)||[z] m U(m))
rE
m:v(m)~e(r)
KL divergence
z, {U} can be solved with linear time complexity
How to track these communities
over time?
(Q3)
t-1
t-1
t-1
t-1
t
t
t
t
Metagraph factorization
for Time evolving data (MFT)
t-1
t
t
t
objective function
cost(G)
= (1-=)  D((r)||[z] m U(m))
cost(G)
+  {D(zt-1||z)+ D(Ut-1(q)||U(q))}
temporal cost
Results
Dataset: Digg
5 facets, 6 relations
time span:
3 weeks in Aug 2008
Community analysis
C1: gamming
industry news
C2: US election
news
C4: general
political news
Change in community size
C3: world news
Change in community keywords
Prediction performance
Digg prediction
Comment prediction
Summary
Problem:
How to track communities in
dynamic multi-relational data?
Approach:
MetaFac for community
extraction on metagraph
Results:
meaningful mining results
and best prediction quality
Code / data – available online:
http://www.public.asu.edu/~ylin56/kdd09sup.html
Questions? Suggestions?
[email protected]
Thanks!
27