Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

PRO-HEAPS_Talk_public

No description
by

JIONGQIAN LIANG

on 9 July 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PRO-HEAPS_Talk_public

Motivations
What Links Alice and Bob?
Jiongqian (Albert) Liang, Deepak Ajwani, Patrick Nicholson, Alessandra Sala and Srinivasan Parthasarathy
Matching and Ranking Semantic Patterns in Heterogeneous Networks
Our world is
heterogeneous
and
interconnected
, with interactions and relations between entities.
They can be represented as a
H
eterogeneous
I
nformation
N
etwork (
HIN
).
Motivations
Problem Formulation
Motivations
Problem Formulation
Motivations
We are often interested in the
relationships
between entities.
However, there might be too many relations.
Solution:
prioritize
the relationship mining.
In a weighted HIN
G = (V, E, Φ, Ψ, W)
, given
Goal
: find out
k

lightest
paths
following the
pattern

between
s
and
t
(without loops).

Top-
k
Lightest Path Problem.
PRO
phetic
HE
uristic
A
lgorithm for
P
ath
S
earching
(PRO-HEAPS)
Experimental Results
Prophet Graph
Baselines
:
1)
Basic
: DFM, BFM, Bidir-BFM, DijkstraM;
2)
Using distance oracle
: DFM+
oracle
, BFM+
oracle
, Bidir-BFM+
oracle
, DijkstraM+
oracle
;
3)
Using Prophet graph
:
PRO
-Bidir-BFM,
PRO
-DijkstraM.
Experimental Results
Real world example
Query Time
Search Space
Results on DBLP
"Realize that everything connects to everything else."
Leonardo da Vinci

Problem and Challenges
Q1: What is the most
popular
question that expert
A
and expert
B
answered together?
A1:
Query
: User-->Answer-->Question-->Answer-->User.
(marc_s, Gordon Linoff) ; weights on # views.
What is the most
popular
question that
marc_s
and
Gordon Linoff
answered together?
Q2: Who most
recently
answered questions on both topic
C
and topic
D
?
A2:
Who most
recently
answered questions on both
Machine Learning
and
IPV6 network
?
Query
: Topic-->Question-->Answer-->User-->Answer-->User-->Topic.
(machine-learning, ipv6) ; weights on recency.
A* Search
Conclusions
Motivation & Intro.
Methodology
Experiments
Conclusion
Q&A
P1
P3
two entities
s
and
t
:
relationship type
P
:
What is the most
recent

paper
that author
A
and
B
collaborated?
What is the most
influential

venue
where author A and B both published papers?
Calculate Priority
Search for Paths
For each intermediate path

p

ending at

x,

its priority

Relationship mining considering users' preference.
Formulate it as top-
k
lightest path problem and propose PRO-HEAPS.

Experiment shows PRO-HEAPS outperforms other baselines with large speedup.

PRO-HEAPS has practical applications.
AK: NSF-EAR-1520870 and NSF-DMS-1418265.
Bi-BFS
If graph is homogeneous, the problem becomes
Minimum-Weight Path
problem (Scott et al. 2005).
The problem is inherently hard.
For general length of pattern
|p|
, the problem is NP-hard (reducible to Hamiltonian path).
A* algorithm
:
1) best-first search algorithm.
2) is useful for finding shortest path in the graph.
3) it first explores
most promising
paths that might lead to shortest path (assign priority based on heuristics).
Preprocess
the graph to build a
level-wise
graph:
Possible nodes to visit in each step when searching.
Candidate nodes of 1st step are on level 1. Candidate nodes of 2nd step are on level 2.
Prune search space!
f(
p, x
)=g(
p, x
)+h(
x
)

Proved to be
monotone
(consistent).

g(
p, x
):
the weight of the path
p
from
s
to
x
matching the prefix of the pattern.

h(
x
):
the weight of the lightest path from
x
to
t
matching the pattern
(allow loops)
.


h(
x
)
can be Efficiently obtained when constructing Prophet Graph (
propagate from bottom
).
From the start node.
Keep maintaining a priority queue with
p
a
s value,
f(
p, x
)=g(
p, x
)+h(
x
)
as keys.
Pop out the path with
min
key value
f(
p, x
)
in the PQ and further explore it.

Check loop and add explored paths into the PQ.
Full transcript