Ilan Newman and Christian Sohler

Report
Every Property of Hyperfinite Graphs is Testable
Ilan Newman and Christian Sohler
Christian Sohler | 03.11.10
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Property Testing
Property Testing [Rubinfeld, Sudan, 96; Goldreich, Goldwasser,
Ron, 98]




Oracle access to huge object O
Decide whether O has a property P or is far-away from P
Goal: Perform this relaxed decision task in sublinear or even constant time
Algorithm may be randomized
Definition

An object is e-far from P, if it differs in more than an e-fraction of its
description from any object with property P
Christian Sohler | Dortmund, 17.02.10
2
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
The Bounded-Degree Graph Model
Bounded degree graph model [Goldreich, Ron, 02]


Graph G=(V,E) with maximum degree d (bounded-degree graph)
Oracle access:
(a) random vertex
(b) i-th edge incident to vertex v
Definition (Graph Property; e-far)


A graph property is a family of graphs P=  P(i), where each P(i) is a set of
graphs on i vertices that is closed under isomorphism.
An n-vertex graph G=(V,E) is e-far from a property P, if it differs from any
bounded-degree graph in P by more than edn edges.
Christian Sohler | Dortmund, 17.02.10
3
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Testable Graph Properties
Definition (testable property)

A graph property P is called non-uniformly testable in the bounded-degree
graph model, if there is a function q=q(e,d) such that for any n there is an
algorithm A(e,d,n) that on input an n-vertex graph G with maximum degree
at most d
(a) makes at most q queries to G,
(b) accepts G with probability at least 2/3, if G has property P, and
(c) rejects G with probability at least 2/3, if G is e-far from P.
Christian Sohler | Dortmund, 17.02.10
4
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Hyperfinite Graphs
Definition (hyperfiniteness)

A graph G is (e,k)-hyperfinite, if one can remove en edges from G such that
only connected components of at most k vertices remain. A family F of
graphs is r-hyperfinite, if for any e>0 every graph GF is (e,r(e))-hyperfinite.
Example

Planar graphs are r-hyperfinite
for some suitable function r by
the planar separator theorem
Christian Sohler | Dortmund, 17.02.10
5
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Property Testing in Hyperfinite Graphs / of
Hyperfinite Properties
Previous work




Every hereditary property is testable in hyperfinite graphs
[Czumaj, Shapira,Sohler ,09]
Every monotone hyperfinite property is testable
[Benjamini, Schramm, Shapira, 08]
Every hereditary hyperfinite property is testable [Hassidim, Kelner,
Nguyen, Onak, 09]
Every property is testable in graphs of bounded growth [Elek 07]
Christian Sohler | Dortmund, 17.02.10
6
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Our results
This work [Newman, S., 11]

Every property is testable in hyperfinite graphs.




Every hyperfinite graph property is testable.
Hyperfinite graph isomorphism is testable.
Many graph parameters are estimable.
The distribution of k-disks of two hyperfinite bounded-degree graphs is close,
iff the graphs are close.
Definition (k-disk)

A k-disk of a vertex v is the subgraph rooted at v that is induced by all vertices
at distance at most k from v.
Christian Sohler | Dortmund, 17.02.10
7
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Some further related work
Motifs


A motif is a subgraph that occurs more frequently than in a random graph.
Can be used to characterize graphs that come from certain domains

„The motifs shared by ecological food webs were distinct from the motifs
shared by the genetic networks of Escherichia coli and Saccharomyces
cerevisiae or from those found in the World Wide Web.” R. Milo, S. Shen-Orr, S.
Itzkovitz, N. Kashtan, D. Chklovskii, U. Alon. Network Motifs: Simple Building
Blocks of Complex Networks. Science, Vol. 298. no. 5594, pp. 824 - 827, 2002.
Christian Sohler | Dortmund, 17.02.10
8
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Constant size graph representations
Definition

For an input graph G, let G‘ be an (e,k)-representative of G, if
(a) G‘ has connected components of size at most k
(b) G‘ can be obtained from G by removing at most edn edges
Observation



If k is independent of n, then G‘ has a constant size representation:
List all D(k) graphs on k vertices H(1), H(2), …, H(D(k))
Take a D(k)-dimensional vector whose i-th entry is the number of
occurences of isomorphic copies of H(i) in G‘
Christian Sohler | Dortmund, 17.02.10
9
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
A Property Tester
Idea:

Reduce property testing in hyperfinite graphs to graphs whose components
have constant size
The Tester:




Let P= P(i) be an arbitrary graph property
Let P‘(n) = {H‘ : HP(n) and H‘ is an (e/2,k)-representative of H}
Assume we know an (e/2,k)-representative G‘ of G
Accept, iff G‘P‘(n)
Christian Sohler | Dortmund, 17.02.10
10
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Local Partitioning oracles
Local Planar Partitioning Oracle [Hassidim, Kelner, Nguyen, Onak, 09]




Provides „local access“ to a partition that
has connected components of size at most k(e) and
has been obtained by removing, say, at most edn/4 edges from G
„Local access“ means that only some k-disks are sampled from G
Christian Sohler | Dortmund, 17.02.10
11
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Local Partitioning oracles
GlobalPartitioning(k,d) [Hassidim, Kelner, Nguyen, Onak, 09]









p = (p1 ,…, pn ) = random permutation of the vertices
P=
while G is not empty do
Let v be the first vertex in G according to p
if there exists a (k,d)-isolated neighborhood of v in G then
S = this neighborhood
(k,d)-isolated neighborhood of v:
else S = {v}
Connected set S of size at most k
P = P  {S}
with vS and at most d|S| edges
remove vertices in S from the graph
between S and V
Christian Sohler | Dortmund, 17.02.10
12
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
How to obtain the representative of a graph?
Algorithm for computing the representative:


Estimate the frequency of connected components by uniform sampling using
the planar partitioning oracle
(take size of component into account)
Analysis:

Chernoff bounds
Christian Sohler | Dortmund, 17.02.10
13
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Second result
Result:

The distribution of k-disks of two hyperfinite bounded-degree graphs is close,
iff the corresponding graphs are close.
Sketch of proof:







„<=“: easy
„=>“: We know that every property of hyperfinite graphs is testable
So, for fixed n-vertex graph consider the property of being H
Let ALG be our property testing algorithm for this property
On input H, ALG must accept w.p. at least 2/3
We claim that, if a graph H‘ has similar distribution of k-disks as H, then the
tester does not reject w.p. > 1/2
=> H‘ is e-close to H
Christian Sohler | Dortmund, 17.02.10
14
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Proof of claim
Claim

If H‘ has a similar distribution on k-disks as H, then the tester on input H‘ does
not reject w.p.>1/2
Sketch of Proof:



The result of the local partitioning algorithm depends on the sampled k-disks
(and internal randomness)
If the distribution of k-disks is similar, then the behaviour of the algorithms
should be similar unless the k-disks intersect
However, as n goes to infinity, this probability tends to 0
Christian Sohler | Dortmund, 17.02.10
15
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Summary
Testable graph properties (bounded-degree model)




Every hyperfinite property
Properties defined by the local structure (for example, triangle freeness)
Certain combinations of the above (e.g. union)
Other properties, like connectivity…
Open Questions


Characterize ‚remaining‘ testable properties
Property testing in expander graphs?
Christian Sohler | Dortmund, 17.02.10
16
Prof. Dr. Christian Sohler
Komplexitätstheorie und
effiziente Algorithmen
Thank you!
Christian Sohler | Dortmund, 17.02.10
17

similar documents