Graph Property Testing and Algorithms Overview
Testable Bounded Degree
Graph Properties Are Random
Order Streamable
Morteza Monemizadeh
Rutgers , Amazon
Joint work with: S. Muthukrishnan, Pan Peng, Christian Sohler
Sparse Graphs
Given a graph G(V,E) where n=|V| and m = |E| = O(n).
Examples
d-Bounded Degree Graphs
Given a graph G(V,E) whose maximum degree d is
constant, where n=|V| and 0 ≤ m = |E| ≤ nd.
(Ɛ,k,d)-Hyperfinite G(V,E)
G is (
Ɛ
,k,d)-hyperfinite graph if we remove a set of at
most
Ɛ
dn edges of G s.t. the remaining graph has
connected components of size at most k.
☛
Is a way to quantify the density of a graph G(V,E).
☛
c = max
U
{|E(U)|/(|U|-1)} where U is a subset of V.☛
G can be partitioned into at most c forests.
☛
Planar graphs have arboricity c = 3.
Arboricity
Maximum Matching
Given a graph
G(V,E)
, find a set of pairwise
non-adjacent of maximum size, i.e., no two
edges share a common edge.
Example
Maximum Matching
☛
30-years-old algorithm due to Micali and Vazirani with
running time
m√n
.
☛
Greedy algorithm returns maximal matching (2-
approximation of maximum matching).
Big Data Models for Graphs
☞
Data Streams: Graph Streams
☞
Property Testing: Testing Graph Properties.
☞
Sublinear Time Approximation Algorithms
Streaming Model
1
2
3
4
5
6
7
8
Stream S =
Graph Streams
☞
Adverserial or Random Order Model
☞
O(c)-approximate the size of matching in c-
bounded arboricity graphs using O(clog
2
n)
space in adversarial model.
☞
O(polylog n)-approximate the size of matching
in general graphs using O(polylog n) space in
random order model.
Graph Streams
☞
Adverserial or Random Order Model
In general, it is not clear which graph problems
can be solved with much smaller space in the
random order stream than in the adversary order
stream.
Graph Streams
☞
Semi-Streaming Model: O(n polylog(n)) space
☞
Sparse Graphs: m=O(n)
☞
O(polylog(n)) or even better O(1) space
Constant Query Property Testing
d-Bounded Graph
Given a graph G(V,E) whose maximum degree d is
constant, where n=|V| and 0 ≤ m = |E| ≤ nd.
Adjacency List Model
Query access to the adjacency list of G:
For any vertex v and index i one can query the i-th
neighbor (if exists) of v in constant time.
Property Testing
A property ∏
n
for d-bounded n-vertex graphs is testable
with query complexity q, if for every 𝞮, d and n, there
exists an algorithm that performs q(n,d, 𝞮) queries to the
adjacency list of the graph and with probability 2/3
❑
Accepts any n-vertex d-bounded graph G satisfying ∏
n
,
❑
Rejects any n-vertex d-bounded graph G that is 𝞮-far from satisfying
∏
n
,
❑
If q(d, 𝞮) is independent of n, we call ∏
n
constant query testable.
Property Testing
Theorem:
Any d-bounded graph property that is
constant-query testable in the adjacency list model can
be tested in random order streaming model with constant
space.
Examples
Adversary Order Model:
Testing k-edge connectivity, k-vertex connectivity and
cycle-freeness of d-bounded degree graphs needs
𝝮(n
1-O(
ε
)
)
space.
Dynamic graph stream algorithms in o(n) space.
Huang and Peng, ICALP 2016.
Random Order Model:
k-edge connectivity, k-vertex connectivity and cycle-
freeness of d-bounded degree graphs are testable
in
constant space in the random order stream model, since they
are constant-query testable in the adjacency list model.
Examples
Property testing in bounded degree graphs.
Oded Goldreich and Dana Ron, Algorithmica 2002
Property Testing
Proof (sketch):
Every constant query property
tester
❑
Samples a constant number of vertices
❑
Explores the k-discs of these vertices?
❑
Makes deterministic decisions based on the explored
graph.
k-disc
The local neighborhood of depth k of a vertex is the
subgraph induced by all vertices of distance at most k.
A k-disc has at most d
k+1
vertices and d
k+2
edges.
v
Constant-Time Approximation
Algorithms
Adjacency List Model
Query access to the adjacency list of G:
For any vertex v index i one can query the the i-th
neighbor (if exists) of v in constant time.
(x,y)-Approximation
We call a value t an (x,y)-approximation for the problem
P, if for any instance I, we have
OPT(I) ≤ t ≤ x
⋅
OPT(I)+y
For a minimization optimization problem P and an instance I, we let OPT(I) denote
the value of some optimal solution of I.
Theorem:
There exists an algorithm that uses
constant space in the random order model, and with
probability 2/3, (1,ɛn)-approximates the size of a
maximal matching.
O(1)-time Approximation Algorithm
Based on Locality Lemma due to Nguyen and Onak, FOCS’08
O(1)-time Approximation Algorithm
Similar result holds for minimum vertex cover,
maximum matching, the number of connected
components.
O(1)-time Approximation Algorithm
Theorem:
There exists an algorithm that uses
constant space in the random order model, and with
probability 2/3, (1±ɛ)-approximates the size of a
maximal matching.
e
1
e
2
e
3
e
4
e
i
…
O(1)-time Approximation Algorithm
Stream :
…
Greedy Matching
Current Matching
M
e
1
e
2
e
3
e
4
e
i
…
O(1)-time Approximation Algorithm
Stream :
…
Greedy Matching
Current Matching
M
Is e
i
in M?
…
O(1)-time Approximation Algorithm
k-Disc Primitive in Data Streams
k-disc Primitive
Given a random order stream S of edges of an
underlying d-bounded degree graph G(V,E).
Sample the full k-disc of a vertex v (almost) uniformly
at random.
2-Pass Streaming Algorithm
2-Pass Algorithm
Sample a set S of (d
k+2
)! vertices and collect their
observed k-discs in S.
In expectation, there exists at least one vertex in S
whose full k-disc is observed.
First Pass:
2-Pass Algorithm
Find the degree of vertices in (partially explored) k-discs
of the vertices in S.
Report the k-disc of a vertex in S that is fully explored.
Second Pass:
1-Pass Streaming Algorithm
Partial Order
Δ
i
≽
Δ
j
: Δ
j
is root-preserving isomorphic to some
subgraph of Δ
i
.
≽
H
d,k
={Δ1
,…,Δ
x
} : The set of all k-disc isomorphism
types.
Ordering
Order all the k-disc types Δ
1
,…, Δ
x
such that
if Δ
i
≽
Δ
j
, then i ≤ j.
…
…
…
Ordering
Order all the k-disc types Δ
1
,…, Δ
x
such that
if Δ
i
≽
Δ
j
, then i ≤ j.
G
(j): All the indices i, except j itself, such that Δ
i
≽
Δ
j
.
…
…
…
Frequency Vector F(G,d)
V
i
: The set of vertices with k-disc isomorphic to Δ
i ,
V
i
={v ∈
V: disc
k,G
(v)
≅
Δ
i
}
|V
i
|
f
i
=|V
i
|/n
…
…
…
Marginal Probability
Let S be a random order Stream.
Let v be a vertex with k-disc isomorphic to Δ
i
.
Marginal Probability:
The probability λ(Δ
j
|Δ
i
) that the observed
k-disc of v in S is disc
k
(v,S)
≅
Δ
j
for any j such that Δ
i
≽
Δ
j
.
Stream S:
…, e’,…, e’’, …, e,…
≽
1-Pass Algorithm
Sample a set T of O(2
(d
k+2
)
! /
Ɛ
2
) vertices.
Preprocssing:
☞
Let H
v
be disc
k
(v,S).
☞
Collect the observed k-disc disc
k
(v,S) from
the stream S.
1-Pass Algorithm
Sample a set T of O(2
(d
k+2
)!
/
Ɛ
2
) vertices.
Preprocssing:
Streaming:
For each vertex v
∈
T:
1-Pass Algorithm
Let H=
∪
v
∈
T
H
v
.
Postprocessing:
1-Pass Algorithm
Let H=
∪
v
∈
T
H
v
.
Postprocessing:
For i =1 to x where x=|F(G,d)|
☞
Y
i
=|{v ∈
T: disc
k,H
(v)
≅
Δ
i
}|/|T|
1-Pass Algorithm
Let H=
∪
v
∈
T
H
v
.
Postprocessing:
For i =1 to x where x=|F(G,d)|
☞
X
i
=(Y
i
-∑
j
∈
G
(i)
X
j
∙ λ(Δ
i
|Δ
j
))∙ λ
-1
(Δ
i
|Δ
i
)
☞
Y
i
=|{v ∈
T: disc
k,H
(v)
≅
Δ
i
}|/|T|
1-Pass Algorithm
Let H=
∪
v
∈
T
H
v
.
Postprocessing:
For i =1 to x where x=|F(G,d)|
G
(i): All the indices j, except i itself, such that Δ
j
≽
Δ
i
.
☞
X
i
=(Y
i
-∑
j
∈
G
(i)
X
j
∙ λ(Δ
i
|Δ
j
))∙ λ
-1
(Δ
i
|Δ
i
)
☞
Y
i
=|{v ∈
T: disc
k,H
(v)
≅
Δ
i
}|/|T|
1-Pass Algorithm
Let H=
∪
v
∈
T
H
v
.
Postprocessing:
For i =1 to x where x=|F(G,d)|
G
(i): All the indices j, except i itself, such that Δ
j
≽
Δ
i
.
Return X
1
,…, X
x
.
Open Problems
☞
In general, it is not clear which graph problems can be
solved with much smaller space in the random order stream
than in the adversary order stream.
☞
What can we say about testing graph properties of
unbounded planar (or minor-free) graphs in data streams?
Thank You
(Almost) Isomorphic Graphs
Benjamini, Shapira, and Schramm, STOC’08
Newman and Sohler, STOC’11
If |F(G
1
,d)-F(G
2
,d)|
1
≤ Ɛdn, then G
1
and G
2
are Ɛ-close.
If we insert/delete at most Ɛdn edges from G
1
, then G
1
and
G
2
becomes isomorphic.
G
1
and G
2
are Ɛ-close:
G
1
and G
2
: (Ɛ,k,d)-hyperfinite graphs.
Explore testable bounded degree graph properties, sparse graphs, d-bounded degree graphs, hyperfinite graphs, arboricity, maximum matching algorithms, and sublinear time approximation algorithms in graph data streams. Learn about various graph models and properties with examples, showcasing the important concepts and algorithms in graph theory research.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Testable Bounded Degree Graph Properties Are Random Order Streamable Morteza Monemizadeh Rutgers , Amazon Joint work with: S. Muthukrishnan, Pan Peng, Christian Sohler
Sparse Graphs Given a graph G(V,E) where n=|V| and m = |E| = O(n).
d-Bounded Degree Graphs Given a graph G(V,E) whose maximum degree d is constant, where n=|V| and 0 m = |E| nd.
(,k,d)-Hyperfinite G(V,E) G is ( ,k,d)-hyperfinite graph if we remove a set of at most dn edges of G s.t. the remaining graph has connected components of size at most k.
Arboricity Is a way to quantify the density of a graph G(V,E). c = maxU {|E(U)|/(|U|-1)} where U is a subset of V. G can be partitioned into at most c forests. Planar graphs have arboricity c = 3.
Maximum Matching Given a graph G(V,E), find a set of pairwise non-adjacent of maximum size, i.e., no two edges share a common edge.
Maximum Matching 30-years-old algorithm due to Micali and Vazirani with running time m n. Greedy algorithm returns maximal matching (2- approximation of maximum matching).
Big Data Models for Graphs Data Streams: Graph Streams Property Testing: Testing Graph Properties. Sublinear Time Approximation Algorithms
Streaming Model 3 2 1 7 4 5 6 8 Stream S =(2,4) , (3,6), (2,7), (4,6), ...
Graph Streams Adverserial or Random Order Model O(c)-approximate the size of matching in c- bounded arboricity graphs using O(clog2 n) space in adversarial model. O(polylog n)-approximate the size of matching in general graphs using O(polylog n) space in random order model.
Graph Streams Adverserial or Random Order Model In general, it is not clear which graph problems can be solved with much smaller space in the random order stream than in the adversary order stream.
Graph Streams Semi-Streaming Model: O(n polylog(n)) space Sparse Graphs: m=O(n) O(polylog(n)) or even better O(1) space
d-Bounded Graph Given a graph G(V,E) whose maximum degree d is constant, where n=|V| and 0 m = |E| nd.
Adjacency List Model Query access to the adjacency list of G: For any vertex v and index i one can query the i-th neighbor (if exists) of v in constant time.
Property Testing A property n for d-bounded n-vertex graphs is testable with query complexity q, if for every ?, d and n, there exists an algorithm that performs q(n,d, ?) queries to the adjacency list of the graph and with probability 2/3 Accepts any n-vertex d-bounded graph G satisfying n, Rejects any n-vertex d-bounded graph G that is ?-far from satisfying n, If q(d, ?) is independent of n, we call n constant query testable.
Property Testing Theorem: Any d-bounded graph property that is constant-query testable in the adjacency list model can be tested in random order streaming model with constant space.
Examples Adversary Order Model: Testing k-edge connectivity, k-vertex connectivity and cycle-freeness of d-bounded degree graphs needs ? Dynamic graph stream algorithms in o(n) space. Huang and Peng, ICALP 2016.
Examples Random Order Model: k-edge connectivity, k-vertex connectivity and cycle- freeness of d-bounded degree graphs are testable in constant space in the random order stream model, since they are constant-query testable in the adjacency list model. Property testing in bounded degree graphs. Oded Goldreich and Dana Ron, Algorithmica 2002
Property Testing Proof (sketch): Every constant query property tester Samples a constant number of vertices Explores the k-discs of these vertices? Makes deterministic decisions based on the explored graph.
k-disc The local neighborhood of depth k of a vertex is the subgraph induced by all vertices of distance at most k. v A k-disc has at most dk+1 vertices and dk+2 edges.
Constant-Time Approximation Algorithms
Adjacency List Model Query access to the adjacency list of G: For any vertex v index i one can query the the i-th neighbor (if exists) of v in constant time.
(x,y)-Approximation We call a value t an (x,y)-approximation for the problem P, if for any instance I, we have OPT(I) t x OPT(I)+y For a minimization optimization problem P and an instance I, we let OPT(I) denote the value of some optimal solution of I.
O(1)-time Approximation Algorithm Theorem: There exists an algorithm that uses constant space in the random order model, and with probability 2/3, (1, n)-approximates the size of a maximal matching. Based on Locality Lemma due to Nguyen and Onak, FOCS 08
O(1)-time Approximation Algorithm Similar result holds for minimum vertex cover, maximum matching, the number of connected components.
O(1)-time Approximation Algorithm Theorem: There exists an algorithm that uses constant space in the random order model, and with probability 2/3, (1 )-approximates the size of a maximal matching.
O(1)-time Approximation Algorithm Greedy Matching e1e2 e3e4 Stream : ei Current Matching M
O(1)-time Approximation Algorithm Greedy Matching e1e2 e3e4 Stream : ei Is ei in M? Current Matching M
O(1)-time Approximation Algorithm .4 .3 .4 .7 .5 v .6 .6 .2
k-disc Primitive Given a random order stream S of edges of an underlying d-bounded degree graph G(V,E). Sample the full k-disc of a vertex v (almost) uniformly at random.
2-Pass Algorithm First Pass: Sample a set S of (dk+2)! vertices and collect their observed k-discs in S. In expectation, there exists at least one vertex in S whose full k-disc is observed.
2-Pass Algorithm Second Pass: Find the degree of vertices in (partially explored) k-discs of the vertices in S. Report the k-disc of a vertex in S that is fully explored.
Partial Order Hd,k={ 1, , x} : The set of all k-disc isomorphism types. i j: j is root-preserving isomorphic to some subgraph of i. j i
Ordering Order all the k-disc types 1, , x such that if i j, then i j. i j
Ordering Order all the k-disc types 1, , x such that if i j, then i j. i j G(j): All the indices i, except j itself, such that i j.
Frequency Vector F(G,d) Vi: The set of vertices with k-disc isomorphic to i , Vi={v V: disck,G(v) i} i j 10010 10 2324 8273 9744 |Vi| fi=|Vi|/n
Marginal Probability Let S be a random order Stream. Let v be a vertex with k-disc isomorphic to i. Marginal Probability: The probability ( j| i) that the observed k-disc of v in S is disck(v,S) j for any j such that i j. e e e e j i Stream S: , e , , e , , e,
1-Pass Algorithm Preprocssing: Sample a set T of O(2(dk+2)! / 2) vertices.
1-Pass Algorithm Preprocssing: Sample a set T of O(2(dk+2)! / 2) vertices. Streaming: For each vertex v T: Collect the observed k-disc disck(v,S) from the stream S. Let Hv be disck(v,S).
1-Pass Algorithm Postprocessing: Let H= v T Hv .
1-Pass Algorithm Postprocessing: Let H= v T Hv . For i =1 to x where x=|F(G,d)|
1-Pass Algorithm Postprocessing: Let H= v T Hv . For i =1 to x where x=|F(G,d)| Yi=|{v T: disck,H(v) i}|/|T|
1-Pass Algorithm Postprocessing: Let H= v T Hv . For i =1 to x where x=|F(G,d)| Yi=|{v T: disck,H(v) i}|/|T| Xi=(Yi- j G(i) Xj ( i| j)) -1( i| i) G(i): All the indices j, except i itself, such that j i.
1-Pass Algorithm Postprocessing: Let H= v T Hv . For i =1 to x where x=|F(G,d)| Yi=|{v T: disck,H(v) i}|/|T| Xi=(Yi- j G(i) Xj ( i| j)) -1( i| i) Return X1, , Xx. G(i): All the indices j, except i itself, such that j i.
