Distributed Estimation of Graph 4-Profiles∗

arXiv:1510.02215v2 [cs.SI] 4 Apr 2016

Ethan R. Elenberg, Karthikeyan Shanmugam,
Michael Borokhovich, Alexandros G. Dimakis
The University of Texas at Austin
{elenberg,karthiksh,michaelbor}@utexas.edu
dimakis@austin.utexas.edu
April 5, 2016

Abstract
We present a novel distributed algorithm for counting all four-node induced subgraphs in a big graph.
These counts, called the 4-profile, describe a graph’s connectivity properties and have found several
uses ranging from bioinformatics to spam detection. We also study the more complicated problem of
estimating the local 4-profiles centered at each vertex of the graph. The local 4-profile embeds every
vertex in an 11-dimensional space that characterizes the local geometry of its neighborhood: vertices
that connect different clusters will have different local 4-profiles compared to those that are only part of
one dense cluster.
Our algorithm is a local, distributed message-passing scheme on the graph and computes all the local
4-profiles in parallel. We rely on two novel theoretical contributions: we show that local 4-profiles can
be calculated using compressed two-hop information and also establish novel concentration results that
show that graphs can be substantially sparsified and still retain good approximation quality for the global
4-profile.
We empirically evaluate our algorithm using a distributed GraphLab implementation that we scaled
up to 640 cores. We show that our algorithm can compute global and local 4-profiles of graphs with
millions of edges in a few minutes, significantly improving upon the previous state of the art.

1

Introduction

Graph k-profiles are local statistics that count the number of small subgraphs in a big graph. k-profiles
are a natural generalization of triangle counting and are increasingly popular for several problems in big
graph analytics. Globally, they form a concise graph description that has found several applications for
the web [1, 2] as well as social and biological networks [3, 4]. Furthermore, as we explain, the local profile
of a vertex is an embedding in a low-dimensional feature space that reveals local structural information.
Mathematically, k-profiles are of significant recent interest since they are connected to the emerging theory
of graph homomorphisms, graph limits and graphons [5, 3, 6].
There are 4 possible graphs on 3 vertices, labeled H0 , . . . , H3 , as in Figure 1 (left). The (global) 3-profile
of a graph G(V, E) is a vector having one coordinate for each distinct Hi that counts how many times that
Hi appears as an induced subgraph of G. For example, the graph G = K4 (the complete graph on 4 vertices)
has the 3-profile [0, 0, 0, 4] since it contains 4 triangles and no other (induced) subgraphs. The graph C5
(the cycle on 5 vertices, i.e. a pentagon) has the 3-profile [0, 5, 5, 0]. Note that the sum of the k-profile is

always |Vk | , the total number of subgraphs. Estimating 3-profiles of big graphs is a topic that has received
attention from several communities recently (e.g., see [3, 7, 8, 9] and references therein).
In this paper we are interested in the significantly more challenging problem of estimating 4-profiles.
Figure 1 (right) shows the 11 possible graphs on 4 vertices,1 labeled as Fi , i = 0 . . . 10. Given a big graph
∗ This work will be presented in part at WWW’16, and has been supported by NSF Grants CCF 1344179, 1344364, 1407278,
1422549 and ARO YIP W911NF-14-1-0258.
1 Actually there are 17 local subgraphs when considering vertex automorphisms. This is discussed in Section 2 in detail. For
the purpose of initial exposition, we will ignore vertex automorphisms.

1

G(V, E) we are interested in estimating the global 4-profile, i.e. count how many times each Fi appears as
an induced subgraph of G. In addition to global graph statistics, we are interested in local 4-profiles: given
a specific vertex v0 , the local 4-profile of v0 is an 11-dimensional vector, with each coordinate i counting how
many induced Fi ’s contain v0 . In Figure 2 we show an example of the local 4-profile of a vertex.
F0
H0

H1

H2

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

H3

Figure 1: Left: The 4 possible non-isomorphic graphs on 3 vertices used to calculate the 3-profile of a graph
G. The 3-profile counts how many times each Hi appears in G. Right: The 11 non-isomorphic graphs on 4
vertices used to calculate the 4-profile of a graph.
v1
v0

v2

v4

v3
Figure 2: An example for local profiles. The global 3-profile is [0, 3, 6, 1]. The global 4-profile is
[0, 0, 0, 0, 2, 0, 0, 1, 2, 0, 0]. The local 4-profile of v0 is [0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 0]. The first 1 in the profile
corresponds to the subgraph F4 . Notice that v0 participates in only one F4 , jointly with vertices v2 , v3 , v4 .
The local 4-profile of a vertex can be seen as an embedding in an 11-dimensional space that characterizes
the local geometry of its neighborhood: vertices that connect different clusters will have different local 4profiles compared to those
that are only part of one dense cluster. A very naive estimation of 4-profiles

requires examining n4 possible subgraphs. Furthermore, for estimating each local 4-profile independently,
this computation has to be repeated n times, once for each vertex. Note that the local 4-profiles may
be rescaled and added together to obtain the global 4-profile. Since some of the 4-profile subgraphs are
disconnected (like F0 , F1 , F5 ), local 4-profiles contain information beyond the local neighborhood of a vertex.
Therefore, in a distributed setting, it seems that global communication is required.

1.1

Our contributions

Surprisingly, we show that very limited global information is sufficient to calculate all local 4-profiles and
that it can be re-used to calculate all the local 4-profiles in parallel. Specifically, we introduce a distributed
algorithm to estimate all the local 4-profiles and the global profile of a big graph. This restrictive setting does
not allow communication between nonadjacent vertices, a key component of previous centralized, sharedmemory approaches. Our algorithm relies on two novel theoretical results:
Two-hop histograms are sufficient: Our algorithm operates by having each vertex first perform local
message-passing to its neighbors and then solve a novel system of equations for the local 4-profile. Focusing
on a vertex v0 , the first easy step is to calculate its local 3-profile. It can be shown that the local 3-profile
combined with the full two-hop connectivity information is sufficient to estimate the local 4-profile for each
vertex v0 . This is not immediately obvious, since naively counting the 3-path (an automorphism of F4 ) would
require 3-hop connectivity information. However, we show that less information needs to be communicated.
Specifically, we prove that the triangle list combined with what we call the two-hop histogram is sufficient: for
each vertex vi that is 2-hops from v0 , we only need the number of distinct paths connecting it to v0 , not the
full two hop neighborhood. If the two-hop neighborhood is a tree, this amounts to no compression. However,
for real graphs the two-hop histogram saves a factor of 3x to 5x in communication in our experiments. This

2

enables (Section 4) an even more significant running time speedup of 5 − 10 times on several distributed
experiments using 12 − 20 compute nodes.
Profile Sparsification: One idea that originated from triangle counting [10, 11] is to first perform random
subsampling of edges to create a sparse graph called a triangle sparsifier. Then count the number of triangles
in the sparse graph and re-scale appropriately to estimate the number in the original graph. The main challenge is proving that the randomly sparsified graph has a number of triangles sufficiently concentrated around
its expectation. Recently this idea was generalized to 3-profile sparsifiers in [9], with concentration results
for estimating the full 3-profile. These papers rely on Kim-Vu polynomial concentration techniques [12] that
scale well in theory, but typically the estimated errors are orders of magnitude larger than the measured
quantities for reasonable graph sizes. In this paper, we introduce novel concentration bounds for global
k-profile sparsifiers that use a novel information theoretic technique called read-k functions [13]. Our read-k
bounds allow usable concentration inequalities for sparsification factors of approximately 0.4 or higher (Section 4.1). Note that removing half the edges of the graph does not accelerate the running time by a factor
of 2, but rather by a factor of nearly 8, as shown in our experiments.
System implementation and evaluation: We implemented our algorithm using GraphLab PowerGraph [14] and tested it in multicore and distributed systems scaling up to 640 cores. The benefits of
two-hop histogram compression and sparsification allowed us to compute the global and local 4-profiles of
very large graphs. For example, for a graph with 5 million vertices and 40 million edges we estimated the
global 4-profile in less than 10 seconds. For computing all local 4-profiles on this graph, the previous state
of the art [8] required 1200 seconds while our algorithm required less than 100 seconds.

1.2

Related work

The problem of counting triangles in a graph has been addressed in distributed [15] and streaming [1] settings,
and this is a standard analytics task for graph engines [16]. The Doulion algorithm [10] estimates a graph’s
triangle count via simple edge subsampling. Other recent work analyzes more complex sampling schemes
[17, 18] and extends to approximately counting certain 4-subgraphs [19, 20]. Mapreduce algorithms for clique
counting were introduced by Finocchi et al. [21]. Our approach is similar to that of [9], which calculates
all 3-subgraphs and a subset of 4-subgraphs distributedly using edge pivots. In this work we introduce the
2-hop histogram to compute all 4-subgraphs.
Concentration inequalities for the number of triangles in a random graph have been studied extensively.
The standard method of martingale bounded differences (McDiarmid’s inequality) is known to yield weak
concentrations around the mean for this problem. The breakthrough work of Kim and Vu [12] provides
superior asymptotic bounds by analyzing the concentration of multivariate polynomials. This was later
improved and generalized in [22], and applied to subsampled triangle counting in [11]. Our analysis uses
a different technique called read-k functions [13] that produces sharper concentration results for practical
problem sizes.2
Previous systems of equations relating clique counts to other 4-subgraphs appear in [23], [7], [8], and [24].
However, these are applied in a centralized setting and depend on information collected from nonadjacent
vertices. In this work, we use additional equations to solve the same system by sharing only local information
over adjacent vertices. The connected 4-subgraphs, or graphlets [4], have found applications in fields such
as bioinformatics [25] and computational neuroscience [26]. In [27], authors use all global 4-subgraphs to
analyze neuronal networks. We evaluate our algorithm against Orca [8], a centralized 4-graphlet counting
algorithm, as well as its GPU implementation [28]. Notice that while Orca calculates only connected
4-subgraphs, our algorithm calculates all the connected and the disconnected 4-subgraphs for each vertex.
Concurrent with the writing of this paper, a parallel algorithm for 4-subgraph counting was introduced
in [24]. Our algorithm differs by working within GraphLab PowerGraph’s Gather-Apply-Scatter framework
instead of the native, multithreaded C++ implementation of [24]. In terms of empirical performance, both
our work and [24] show similar running time improvements of one order of magnitude over Orca. A more
detailed comparison would depend on the hardware and datasets used. More importantly, our work focuses
on a distributed (as opposed to multicore parallel) framework, and for our setting minimizing communication
is critical.
2 Even though concentrations using Kim-Vu become tighter asymptotically, this happens for graphs with well over 1013 edges
(see also Figure 6a).

3

F3 (v) F4 (v) F6 (v) F8 (v) F9 (v)
F

F

0

H0 (v) H1e (v) H1d (v) H2c (v) H2e (v) H3 (v)
F

00

(b)

(a)

Figure 3: Unique (a) 3-subgraphs and (b) 4-subgraphs from the perspective of the white vertex is v. F8 is
00
the only subgraph with a third vertex automorphism F8 because no other subgraph contains vertices with
3 different degrees.
Our theoretical results are significantly different from [24] and may be useful in improving that system
also. Specifically, [24] explicitly counts the number of 4-cycles (F7 in Figure 1, Right) whereas our results
show that it is possible to use only two-hop histograms instead. This results in less communication overhead,
but this benefit is perhaps not as significant for shared-memory multicore platforms. Our second theoretical
result, the novel sparsification concentration bounds, can be used for any subgraph estimation algorithm and
quantify a provable tradeoff between speed and accuracy.

2

Distributed Algorithm

In this section, we describe 4-Prof-Dist, our algorithm for computing the exact 4-profiles in a distributed
manner. To the best of our knowledge, this is the first distributed algorithm for calculating 4-profiles. The
key insight is to cast existing and novel equations into the GraphLab PowerGraph framework [14] to get
implicit connectivity information about vertices outside the 1-hop neighborhood. Specifically, we construct
the local 4-profile from local 3-profile, local 4-clique count, and additional histogram information which
describes the number of paths to all 2-hop neighbors.
Theorem 1. There is a distributed algorithm that computes the exact local 4-profile of a graph given each
vertex has stored its local 3-profile, triangle list, and 2-hop histogram.
Note that the local 4-profiles at each vertex can be added and appropriately rescaled (using the symmetries
of each subgraph, also called automorphism orbits [4]) to obtain the global 4-profile.
4-Prof-Dist is implemented in the Gather-Apply-Scatter (GAS) framework [14]. A distributed algorithm in this framework has 3 main phases: Gather, Apply and Scatter. Every vertex and edge has stored
data which is acted upon. During the Gather phase, a vertex can access all its adjacent edges and neighbors and gather data they possess, e.g., neighbor ID, using a custom reduce operation ⊕ (e.g., addition,
concatenation). The accumulated information is available for a vertex at the next phase, Apply, in which it
can change its own data. In the final Scatter phase, every edge sees the data of its (incident) vertices and
operates on it to modify the edge data. All nodes start each phase simultaneously, and if needed, the whole
GAS cycle is repeated until the algorithm’s completion.
4-Prof-Dist solves a slightly larger problem of keeping track of counts of 17 unique subgraphs up to
vertex automorphism (see Figure 3). We will describe a full rank system of equations which is sufficient
to calculate the local 4-profile at every v ∈ V . The following subsections each explain a component of
4-Prof-Dist. These separate routines are combined efficiently in Algorithm 1 to calculate the local 4profile in a small number of GAS cycles.

4

=

v

a

a∈Γ(v)

nc2,va ne2,va

P

+

0

F4 (v)

2F7 (v)

Figure 4: Edge pivot equation for vertex v counting triangles as edges va pivot about their common vertex
0
v. The subgraphs F4 (v) and F7 (v) differ by one edge.

2.1

Edge pivot equations

The majority of our equations relate the local 4-profile to neighboring local 3-profiles with edge pivots [9].
At each vertex v, each combinatorial equation relates a linear combination of the local 4-subgraph counts
to the count of a pair of 3-subgraphs sharing an edge va. Some of these equations appear in a centralized
setting in previous literature ([23], [7], [8], [24]). In our algorithm, the 3-subgraph pair count accumulates at
v as all incident edges va pivot over it. The edges fixed by a specific 3-subgraph pair correspond to common
edges among a subset of 4-subgraphs. Before that, in an initial GAS round, each vertex v must gather the
ID of each vertex in its neighborhood, i.e. a ∈ Γ(v), and the following quantities must be stored at each
edge va during Scatter phase:
ne1,va = |Γ(v) ∪ Γ(a)| = |V | − (|Γ(v)| + |Γ(a)| − |Γ(v) ∩ Γ(a)|),

nc2,va = |Γ(v)\{Γ(a) ∪ a}| = |Γ(v)| − |Γ(v) ∩ Γ(a)| − 1,
ne2,va = nc2,av ,

(1)

n3,va = |Γ(v) ∩ Γ(a)|.
Gather: P
The above quantities are summed at each vertex v to calculate the local 3-profile at v. For example,
n3,v = 21 a n3,va . In addition, we gather the sum of functions of pairs of these quantities forming 13 edge
pivot equations.
X ne 
1,va
= F1 (v) + F2 (v),
2
a∈Γ(v)
X nc 
0
0
2,va
= 3F6 (v) + F8 (v),
2
a∈Γ(v)

X n3,va 
0
= F9 (v) + 3F10 (v),
2
a∈Γ(v)
X
0
0
ne1,va nc2,va = 2F3 (v) + F4 (v),
(2)
a∈Γ(v)
X
00
ne1,va n3,va = 2F5 (v) + F8 (v),
a∈Γ(v)

X

0

nc2,va ne2,va = F4 (v) + 2F7 (v),

a∈Γ(v)

X

0

0

nc2,va n3,va = 2F8 (v) + 2F9 (v),

a∈Γ(v)

nd1,v |Γ(v)| = F2 (v) + F4 (v) + F8 (v).
The primed notation differentiates between subgraphs of different automorphism orbits, as in Figure 3. By
accumulating pairs of 3-profile structures as in (2), we receive aggregate connectivity information about
vertices more than 1 hop away. Consider the sixth equation as an example. The product between n2,va and
ne2,va subgraphs along edge va forms 4-node graphs with the following structural constraints: three vertex
5

0

pairs are connected, two vertex pairs are disjoint, and one pair may be either connected or disjoint. F4 (v)
and F7 (v) satisfy these constraints and differ on the unconstrained edge. Thus, as shown in Figure 4, they
both contribute to the sum of nc2,va ne2,va .
The following edge pivot equations are linearly independent when solving for the local 4-profile only.
Note the last 2 equations require calculating the local 3-profile:
X ne 
2,va
= F6 (v) + F8 (v),
2
a∈Γ(v)
X
ne1,va ne2,va = F3 (v) + F4 (v),
a∈Γ(v)
00

X

ne2,va n3,va = F8 (v) + 2F9 (v),

(3)

a∈Γ(v)

X
a∈Γ(v)

X
a∈Γ(v)

n3,a − n3,va = F8 (v) + 2F9 (v) + 3F10 (v),
00

0

ne2,a − nc2,va = F4 (v) + 2F7 (v) + F8 (v) + 2F9 (v).

Apply: The left hand sides of all such equations are stored at v.

2.2

Clique counting

The aim of this subtask is to count 4-cliques that contain the vertex v. For this, we accumulate a list of
triangles at each vertex v. Then, at the Scatter stage for every va, it is possible to check if neighbors common
to v and a have an edge between them. This implies a 4-clique.
Scatter: In addition to the intersection size |Γ(v) ∩ Γ(a)| at each edge va as before, we now require the
intersection list {b : b ∈ Γ(v), b ∈ Γ(a)} as a starting point.
Gather, Apply: The intersection list is gathered at each vertex v. This produces all pairs of neighbors in
Γ(v) which are adjacent, i.e. all triangles containing v. It is stored as ∆(v) during the Apply stage at v.
Gather, Apply: Each edge va computes the number of 4-cliques by counting how many pairs in ∆(a)
contain exactly two neighbors of v. We use a similar equation to calculate F8 (v) concurrently:
X
|(b, c) ∈ ∆(a) : b ∈ Γ(v), c ∈ Γ(v)| = 3F10 (v),
a∈Γ(v)

X
a∈Γ(v)

(4)
|(b, c) ∈ ∆(a) : b ∈
/ Γ(v), c ∈
/ Γ(v)| = F8 (v).

At the Apply stage, store the left hand sides as vertex data.

2.3

Histogram 2-hop information

Instead of calculating the number of cycles F7 (v) directly, we can simply construct another linearly independent equation and add it to our system. Let each vertex a have a vector of (vertex ID, count) pairs (p, ca [p])
for each of its adjacent vertices p. Initially, ca [p] = 1 and this histogram contains the same information as
Γ(a). For any a ∈ Γ(v) and p ∈
/ Γ(v), ca [p] = 1 ⇔ vap forms a 2-path. Thus, v can collect these vectors
to determine the total number of 2-paths from v to p. This lets us calculate a linear combination involving
cycle subgraph counts with an equation that is linearly independent from the others in our system.
Gather: At each v, take a union of histograms from each neighbor a, resolving duplicate entries with the
reduce operation (p, ca1 ) ⊕ (p, ca2 ) = (p, ca1 + ca2 ).
Apply: Given the gathered histogram vector {⊕a∈Γ(v) ca [p]}p∈Γ(v)
, calculate the number of non-induced
/
4-cycles involving p and two neighbors:
X ⊕a∈Γ(v) ca [p]
= F7 (v) + F9 (v).
(5)
2
p∈Γ(v)
/

6

Next, we upper bound savings from our 2-hop histogram by analyzing the improvement when the only
information transmitted across the network to a vertex v is each non-neighboring vertex and its final count
⊕a∈Γ(v) c[p]. LetPhv = |Γ(Γ(v)) \ {Γ(v) ∪ v}|. For each v, the difference between full and histogram information is at most a∈Γ(v) (|Γ(a)| − 1) − 2hv . The exact benefit of (5) depends on the internal implementation
of the reduce operation ⊕ as pairs of neighbors are gathered.
Counting the number of distinct pairs of 2-paths to each 2-hop neighbor, i.e. 12 (c[p]2 − c[p]), requires
counting the second moment of c taken over hv terms. Due to a result by Alon ([29], Proposition 3.7), the
memory required to count this value exactly (moreover, to approximate it deterministically) is Ω(hv ). Thus,
up to implementation details, our memory use is optimal.

2.4

Normalization and symmetry

Our final local equation comes from summing the local 4-profile across all 17 automorphisms:
17
X


Fi (v) =

i


|V | − 1
.
3

(6)

P
To calculate the global 4-profile, we utilize global symmetry and scaling equations. Let Fi = v∈V Fi (v).
Globally, each subgraph count is in exact proportion with the same subgraph counted from a different vertex
automorphism. The ratio depends on the subgraph’s degree distribution:
0

0

F3 = 2F3 ,
0

F8 = F8 ,

F 4 = F4 ,
00

F8 = 2F8 ,

0

F6 = 3F6 ,
0

(7)

F9 = F9 .

Global symmetry makes the equation for F8 and the system (3) linearly dependent. We sum across verT
tices, inverting a single 11 × 11 system to yield the final global 4-profile [N0 , . . . N10
] by scaling appropriately:
F0
,
4
0
F
N4 = 4 ,
2
N0 =

N8 = F8 ,

0
F1
F2
, N2 =
, N 3 = F3 ,
2
4
0
F5
F7
N5 =
, N 6 = F6 , N 7 =
,
3
4
F9
F10
N9 =
, N10 =
.
2
4

N1 =

(8)

Algorithm 1 4-Prof-Dist
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

3

Input: Graph G(V, E) with |V | vertices, |E| edges.
Gather: For each vertex v union over edges of the ‘other’ vertex in the edge, ∪a∈Γ(v) a = Γ(v).
Apply: Store the gather as vertex data v.nb, size automatically stored.
Scatter: For each edge eva , compute and store scalars in (1).
Gather: For each edge eva , sum edge scalar data of neighbors in (2) - (3) and combine two-hop histograms.
Apply: For each vertex v, sum over p ∈
/ Γ(v) in (5), store other data in array v.u. No Scatter.
Gather: For each vertex v collect pairs of connected neighbors in ∆(v).
Apply: Store connected neighbor (triangle) list as vertex data v.conn. No Scatter.
Gather: For each vertex v sum (4).
Apply: Append data to array v.u. Multiply v.u by a matrix to solve system of equations.
return [v: v.N0 v.N1 v.N2 ... v.N10]

Sparsification and Concentration

In this section, we describe the process for approximating the exact number of subgraphs in a graph G.
Denote the exact counts by [N0 . . . N10 ]T and the estimates by [X0 . . . X10 ]T .
7

We are sparsifying the original graph G by keeping each edge independently with probability p. Denote
the random subsampled graph by G̃ and its global 4-profile by [Y0 . . . Y10 ]T . Clearly each triangle survives
with probability p3 and each 4-clique survives with p6 . Therefore, in expectation, E[Y10 ] = p6 N10 and
X10 = p16 Y10 is unbiased.
This simple correspondence does not hold for other subgraphs: each triangle in G̃ can only be a triangle
in G that survived edge removals, but other subgraphs of G̃ could be originating from multiple subgraphs
of G depending on the random sparsification process. We can, however, relate the original 4-profile vector
to the expected subsampled 4-profile vector by a matrix multiplication. Let F (abcd) and F̃ (abcd) represent
the induced 4-subgraph on the vertices abcd before and after subsampling, respectively. Then define H by
Hij = P(F̃ (abcd) = Fi | F (abcd) = Fj ). Thus, we form an unbiased estimator, i.e. E[Xi ] = Ni , i = 1, . . . , 10,
by inverting the edge sampling matrix.
For 3-profiles, this process is described by the following system of equations:
 

 
n0
1 1 − p (1 − p)2
(1 − p)3
E[Y0 ]
2  
E[Y1 ] 0
p
2p(1
−
p)
3p(1
−
p)
 n1  .

 
(9)
E[Y2 ] = 0
0
p2
3p2 (1 − p) n2 
n3
0
0
0
p3
E[Y3 ]
For 4-profiles, the vectors are 11 dimensional and a similar linear system can be explicitly computed – we
include the equations in the Appendix. This matrix turns out to be invertible and we can therefore calculate
the 4-profile exactly if we have access to the expected values of the sparsified 4-profile. Of course, we can
only obtain one sample random graph and calculate that 4-profile, which will be an accurate estimate if the
4-profile quantities are sufficiently concentrated around their expectation.

3.1

Graph k-profile concentration

Previous work used this idea of graph sparsification for triangle counting [11] and 3-profiles [9]. The main
concentration tool used was the Kim and Vu polynomial concentration [12, 11] which unfortunately gives
very loose bounds for practical graph sizes. Figure 6a compares the accuracy bound derived in this section
to the bound predicted by [12]. Clearly the Kim-Vu concentration does not provide meaningful bounds for
the experiments in Section 4.1. However, our results match observed sparsifier accuracy much more closely.
Our novel concentration results that exploit the fact that partial derivatives of the desired quantities are
sparse in the number of edge variables. This allows us to use a novel information theoretic concentration
technique called read-k functions [13]. For simplicity, we only explain the concentration of 4-cliques (F10
subgraphs) here. We establish the general result for all 11 4-profile variables in the Appendix. Our main
concentration result is as follows:
Theorem 2. Let G be a graph with N10 4-cliques, and let k10 be the maximum number of 4-cliques sharing
a common edge. Let X10 be the 4-clique estimate obtained from subsampling each edge with probability
0 < p ≤ 1, choose 0 < δ < 1, and choose RK > 0. If

p≥

log(2/δ)k10
22RK N10

1/12
,

then |N10 − X10 | ≤ RK N10 with probability at least 1 − δ.
Proof. Our proof relies on read-k function families [13], a recent characterization of dependencies among
functions of random variables. See the Appendix for full details.
Next, we state conditions under which our method outperforms the Kim and Vu concentration results [12].
Proof can be found in the Appendix:
Corollary 1. Let G be a graph with m edges. If p = Ω(1/ log m) and δ = Ω(1/m), then read-k provides
5/6
better triangle sparsifier accuracy than Kim-Vu. If additionally k10 ≤ N10 , then read-k provides better
4-clique sparsifier accuracy than Kim-Vu.

8

We note that the asymptotic condition on p in Corollary 1 includes a constant term much less than 1.
This implies our concentration result is superior over all p values of practical interest. While these bounds
contain the quantities we wish to estimate, they provide guidelines for the performance of sampling heuristics.
We also investigate this in Section 4.1 for some realistic graphs.

4

Experiments

Let us now describe the implementation and experimental results of our algorithm. We implement 4Prof-Dist on GraphLab v2.2 (PowerGraph) [14] and measure its running time and accuracy on large input
graphs.3 First, we show that edge sampling yields very good approximation results for global 4-profile counts
and achieves substantial execution speedups and network traffic savings when multiple machines are in use.
Due to its distributed nature, we can show 4-Prof-Dist runs substantially faster when using multiple CPU
cores and/or machines. Notice that multicore and multiple machines can not speed up some centralized
algorithms, e.g., Orca [8], which we use as a baseline for our results. Note also that Orca produces only
a partial 4-subgraph count, i.e., it calculates only connected 4-subgraphs, while 4-Prof-Dist calculates all
17 per vertex.
The systems: We perform the experiments on two systems. The first system is a single powerful server,
further referred to as Asterix. The server is equipped with 256 GB of RAM and two Intel Xeon E5-2699 v3
CPUs, 18 cores each. Since each core has two hardware threads, up to 72 logical cores are available to the
GraphLab engine. The second system is an EC2 cluster on AWS4 . The cluster is comprised of 20 c3.8xlarge
machines, each having 60 GB RAM and 32 virtual CPUs.
The data: In our experiments we use two real graphs representing different datasets: social networks
(LiveJournal: 4,846,609 vertices, 42,851,237 edges) and a WWW graph of Notre Dame (WEB-NOTRE:
325,729 vertices, 1,090,108 edges) [30]. Notice that the above graphs are originally directed, but since our
work deals with undirected graphs, all duplicate edges (i.e., bi-directional) were removed and directionality
is ignored.
LiveJournal, Asterix

600

1.10

LiveJournal, Accuracy, 4-profiles
F10
F9

F8
F7

Accuracy: exact/approx

Running time [sec]

500

400

300

200

1.05

1.00

0.95

100

0

p=1

0.90

p=0.9 p=0.8 p=0.7 p=0.6 p=0.5 p=0.4 p=0.3 p=0.2 p=0.1

(a)

p=0.9

p=0.7

p=0.4

p=0.3

p=0.1

(b)

Figure 5: LiveJournal graph, Asterix system. All the results are averaged over 10 iterations. (a) – Running
time as a function of sampling probability. (b) – Accuracy of the F7 − F10 global counts, measured as ratio
of the exact count and the estimated count.

4.1

Results

Accuracy: The first result is that our edge sampling approach greatly improves running time while maintaining a very good approximation of the global 4-profile. In Figure 5a we can see that the running time
3 Available
4 Amazon

at http://github.com/eelenberg/4-profiles
Web Services - http://aws.amazon.com

9

1030

LiveJournal, Sparsifier Accuracy

LiveJournal, Asterix

2500

1027
2000

Accuracy: |exact - approx|

1024

1018

Running time [sec]

1021

Kim-Vu
Read-k
4-cliques
Measured

1015
1012
109
106

Orca: 1288 sec

1500

1000

500

103
100
0.0

0.2

0.4

0.6

0.8

1.0

0

Edge sampling probability

(a)

10 cores

20 cores

30 cores

40 cores

50 cores

60 cores

(b)

Figure 6: LiveJournal graph, Asterix system. All the results are averaged over 10 iterations. (a) – Comparison
of 4-clique sparsifier concentration bounds with accuracy measured in edge sampling experiments. (b)
– Comparison of running times of Orca and our exact 4-Prof-Dist algorithm. Clearly, 4-Prof-Dist
benefits from the use of multiple cores.
decreases drastically when the sampling probability decreases. At the same time, Figure 5b shows that the
mean ratio of true to estimated global 4-profiles is within ±2.5%. Similar to [20], which uses a more complex
sampling scheme to count connected 4-subgraphs, this ratio is usually much less than 1%. We show here only
profiles F7 − F10 since their counts are the smallest and were observed to have the lowest accuracy. In Figure
6a we compare theoretical concentration bounds on a logarithmic scale and show the benefit of Theorem
2. While the guarantees provided by Kim-Vu [12] bounds are very loose (the additive error is bounded by
numbers which are orders of magnitude larger than the true value), the read-k approach is much closer to
the measured values. We can see that for large sampling probabilities (p ≥ 0.5), the measured error at most
2 orders of magnitude smaller than the value prediced by Theorem 2.
2-hop histogram: Now we compare two methods of calculating the left hand side of (5) from Section 2.3.
We show that a simple implementation in which a vertex gathers its full 2-hop neighborhood (i.e., IDs of its
neighbors’ neighbors) is much less efficient than the two-hop histogram approach used in 4-Prof-Dist (see
Section 2.3). In Figures 7a and 7b we can see that the histogram approach is an order of magnitude faster
for various numbers of machines, and that its network requirements are up to 5x less than that of the simple
implementation. Moreover, our algorithm could handle much larger graphs while the simple implementation
ran out of memory.
Running time: Finally, we show that 4-Prof-Dist can run much faster than the current state of the
art graphlet counting implementations. The algorithm and the GraphLab platform on which it runs are
both distributed in nature. The latter allows 4-Prof-Dist to exploit multiple cores on a single machine as
well as a cluster of machines. Figure 6b shows running time as a function of CPU cores. We compare this
result to the running time of a single core, C++ implementation of Orca [8]. Our 4-Prof-Dist algorithm
becomes faster after only 25 cores and is 2x faster using 60 cores. Moreover, 4-Prof-Dist allows scaling
to a large number of machines. In Figure 7c we can see how the running time for the LiveJournal graph
decreases when the number of machines increases. Since Orca cannot benefit from multiple machines, we
see that 4-Prof-Dist runs up to 12x faster than Orca. This gap widens as the cluster grows larger. In
[28], the authors implemented a GPU version of Orca using CUDA. However, the reported speedup is about
2x which is much less than we show here on the AWS cluster (see Figure 7c for p = 1). We also note a
substantial running time benefit of the sampling approach for global 4-profiles. In Figures 7c and 7d, we see
that with p = 0.1 we can achieve order of magnitude improvements in both speed and network traffic. This
sampling probability maintains very good accuracy, as shown in Figure 5b.

10

WEB-NOTRE, AWS
2-hop

50

×1010

2-hop histogram

WEB-NOTRE, AWS
2-hop

2-hop histogram

2.0

Network sent [bytes]

Running time [sec]

40

30

20

1.5

1.0

0.5

10

0

12 nodes

14 nodes

16 nodes

18 nodes

0.0

20 nodes

12 nodes

14 nodes

16 nodes

(a)

20 nodes

(b)

LiveJournal, AWS
200

18 nodes

p=1
p=0.7

×1011

p=0.4
p=0.1

3.5

LiveJournal, AWS
p=1
p=0.7

p=0.4
p=0.1

3.0

Network sent [bytes]

Running time [sec]

150

100

2.5

2.0

1.5

1.0

50

0.5

0

8 nodes

12 nodes

16 nodes

0.0

20 nodes

(c)

8 nodes

12 nodes

16 nodes

20 nodes

(d)

Figure 7: AWS cluster of up to 20 machines (nodes). (a,b) – Running time and network usage comparing
naive 2-hop implementation and 2-hop histogram approach on the Notre Dame web graph. (c,d) – Running
time and network usage of 4-Prof-Dist for various number of compute nodes and sampling probability p,
on the LiveJournal graph. All results are averaged over 10 iterations.

5

Conclusions

We introduced a novel distributed algorithm for estimating 4-profiles of large graphs. We relied on two
theoretical results that can be of independent interest: that 4-profiles can be estimated with limited 2-hop
information and that randomly erasing edges gives sharper approximation compared to previous analysis.
We showed that our scheme outperforms the previous state of the art and can exploit cloud infrastructure
to scale.

References
[1] L. Becchetti, P. Boldi, C. Castillo, and A. Gionis, “Efficient Semi-Streaming Algorithms for Local
Triangle Counting in Massive Graphs,” in KDD, 2008.
[2] D. O’Callaghan, M. Harrigan, J. Carthy, and P. Cunningham, “Identifying Discriminating Network
Motifs in YouTube Spam,” Feb. 2012.

11

[3] J. Ugander, L. Backstrom, and J. Kleinberg, “Subgraph Frequencies: Mapping the Empirical and
Extremal Geography of Large Graph Collections,” in WWW, 2013.
[4] N. Przulj, “Biological Network Comparison Using Graphlet Degree Distribution,” Bioinformatics,
vol. 23, no. 2, pp. 177–183, 2007.
[5] C. Borgs, J. Chayes, and K. Vesztergombi, “Counting Graph Homomorphisms,” Topics in Discrete
Mathematics, pp. 315–371, 2006.
[6] L. Lovász, Large Networks and Graph Limits.

American Mathematical Soc., 2012, vol. 60.

[7] V. V. Williams, J. Wang, R. Williams, and H. Yu, “Finding Four-Node Subgraphs in Triangle Time,”
SODA, pp. 1671–1680, 2014.
[8] T. Hočevar and J. Demšar, “A Combinatorial Approach to Graphlet Counting.” Bioinformatics, vol. 30,
no. 4, pp. 559–65, Feb. 2014.
[9] E. R. Elenberg, K. Shanmugam, M. Borokhovich, and A. G. Dimakis, “Beyond Triangles: A Distributed
Framework for Estimating 3-profiles of Large Graphs,” in KDD, 2015, pp. 229–238.
[10] C. E. Tsourakakis, U. Kang, G. L. Miller, and C. Faloutsos, “DOULION: Counting Triangles in Massive
Graphs with a Coin,” in SIGKDD, 2009.
[11] C. E. Tsourakakis, M. Kolountzakis, and G. L. Miller, “Triangle Sparsifiers,” Journal of Graph Theory
and Applications, vol. 15, no. 6, pp. 703–726, 2011.
[12] J. H. Kim and V. H. Vu, “Concentration of Multivariate Polynomials and Its Applications,” Combinatorica, vol. 20, no. 3, pp. 417–434, 2000.
[13] D. Gavinsky, S. Lovett, M. Saks, and S. Srinivasan, “A Tail Bound for Read-k Families of Functions,”
Random Structures & Algorithms, vol. 47, no. 1, pp. 99–108, 2015.
[14] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed Graph-Parallel
Computation on Natural Graphs,” in 10th USENIX Symposium on Operating Systems Design and
Implementation (OSDI), 2012, pp. 17–30.
[15] T. Schank, “Algorithmic Aspects of Triangle-Based Network Analysis,” Ph.D. dissertation, 2007.
[16] N. Satish, N. Sundaram, M. A. Patwary, J. Seo, J. Park, M. A. Hassaan, S. Sengupta, Z. Yin, and
P. Dubey, “Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets,” in
SIGMOD, 2014, pp. 979–990.
[17] C. Seshadhri, A. Pinar, and T. G. Kolda, “Triadic Measures on Graphs: The Power of Wedge Sampling,”
in Proceedings of the SIAM Conference on Data Mining, 2013, pp. 10–18.
[18] T. Eden, A. Levi, D. Ron, and C. Seshadhri, “Approximately Counting Triangles in Sublinear Time,”
in FOCS, 2015, pp. 614–633.
[19] N. K. Ahmed, N. Duffield, J. Neville, and R. Kompella, “Graph Sample and Hold: A Framework for
Big-Graph Analytics,” in KDD, 2014.
[20] M. Jha, C. Seshadhri, and A. Pinar, “Path Sampling: A Fast and Provable Method for Estimating
4-Vertex Subgraph Counts,” in WWW, 2015, pp. 495–505.
[21] I. Finocchi, M. Finocchi, and E. G. Fusco, “Clique Counting in MapReduce: Algorithms and Experiments,” ACM Journal of Experimental Algorithmics, vol. 20, no. 1, 2015.
[22] S. Janson, K. Oleszkiewicz, and A. Ruciński, “Upper Tails for Subgraph Counts in Random Graphs,”
Israel Journal of Mathematics, vol. 142, no. 1, pp. 61–92, 2004.
[23] M. Kowaluk, A. Lingas, and E.-M. Lundell, “Counting and Detecting Small Subgraphs via Equations,”
SIAM Journal of Discrete Mathematics, vol. 27, no. 2, pp. 892–909, 2013.
12

[24] N. K. Ahmed, J. Neville, R. A. Rossi, and N. Duffield, “Efficient Graphlet Counting for Large Networks,”
in IEEE International Conference on Data Mining, 2015.
[25] N. Shervashidze, K. Mehlhorn, and T. H. Petri, “Efficient Graphlet Kernels for Large Graph Comparison,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2009,
pp. 488–495.
[26] F. Fei, B. Jie, and D. Zhang, “Frequent and Discriminative Subnetwork Mining for Mild Cognitive
Impairment Classification,” Brain Connectivity, vol. 4, no. 5, pp. 347–360, Jun. 2014.
[27] L. R. Varshney, B. L. Chen, E. Paniagua, D. H. Hall, and D. B. Chklovskii, “Structural Properties of
the Caenorhabditis elegans Neuronal Network,” PLoS Computational Biology, vol. 7, no. 2, 2011.
[28] A. Milinković, S. Milinković, and L. Lazicć, “A Contribution to Acceleration of Graphlet Counting,” in
Infoteh Jahorina Symposium, vol. 14, no. March, 2015, pp. 741–745.
[29] N. Alon, Y. Matias, and M. Szegedy, “The Space Complexity of Approximating the Frequency Moments,”
in STOC, 1996, pp. 20–29.
[30] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.
stanford.edu/data, Jun. 2014.

13

A
A.1

Appendix
Proof of Theorem 2

Proof. Rather than Lipschitz bounding the value of each partial derivative, as in [12, 11, 9], our main
technical tool [13] benefits from the fact that each first partial derivative is sparse in the number of edge
variables:
Definition 1 (Read-k Families). Let X1 , . . . , Xm be independent random variables. For j ∈ [r], let Pj ⊆ [m]
and let fj be a Boolean function of {Xi }i∈Pj . Assume that |{j|i ∈ Pj }| ≤ k for every i ∈ [m]. Then the
random variables Zj = fj ({Xi }i∈Pj ) are called a read-k family.
Each variable only affects k of the r Boolean functions. Let G be a graph with N10 4-cliques and a
maximum of k10 4-cliques sharing a common edge. The corresponding 4-clique estimator X10 follows this
exact structure. Each edge sampling variable appears in at most k10 of the N10 terms. We now state the
main result required for our analysis. Note that when applied to estimating the number of 4-cliques, the
bound is a function of k10 and N10 independent of the number of edges. Therefore, it is much stronger than
arguments involving Lipschitz bounded functions such as McDiarmid’s inequality.
Proposition 1 (Concentration of Read-k Sums [13]). Let Z1 , . . . , Zr be a family of read-k indicator variables
with P(Zi = 1) = pi , and let p be the average of p1 , . . . , pr . Then for any  > 0,
!
r


X
r
r
≤ exp −22
P
Zi ≥ (p + )r ≤ exp −D(p +  k p)
k
k
i=1
!
r


X
r
r
P
Zi ≤ (p − )r ≤ exp −D(p −  k p)
≤ exp −22
,
k
k
i=1
 


where D(x k y) = x log xy + (1 − x) log 1−x
is the Kullback-Leibler divergence of x and y.
1−y
P
Let Y10 = (a,b,c,d)∈H10 tab tbc tcd tda tac tbd . Then
6

P |Y10 − p N10 | ≥ RK N10



22 N10
≤ 2 exp − RK
k10




6

6

⇒ P (|X10 − N10 | ≥ RK N10 ) = P |Y10 − p N10 | ≥ p RK N10





2p12 2RK N10
≤ 2 exp −
.
k10

The claim follows by setting the right hand side less than δ and solving for p.

A.2

Proof of Corollary 1

Proof. We prove this result for the case of 4-cliques only because the case for triangles is similar. First we
must derive a similar 4-clique concentration bound using the techniques in [12, 11].
Lemma 1. Let G be a graph with m
√ edges and N10 cliques, and k10 be the maximum number of 4-cliques
sharing a common edge. Let a6 = 86 6!, 0 < p ≤ 1, and KV > 0. Let X10 be the 4-clique estimate obtained
from subsampling each edge with probability p. If
p

max

np
6

o≥
p
1/N10 , 3 k10 /N10

then |N10 − X10 | ≤ KV N10 with probability at least 1 −

14

1
mγ .

a26 log12 (m5+γ )
,
2KV

(10)

Proof. This proof is a straightforward application of the main result in [12], repeated below for completeness.
α
Let α = (α1 , α2 , . . . , αm ) ∈ Zm
+ and define E≥1 [X] = maxα:kαk1 ≥1 E(∂ X), where


∂ αm
∂ α1
E(∂ α X) = E (
(11)
) ...(
) [X(t1 , . . . , tm )] .
∂t1
∂tm
Further, we call a polynomial totally positive if the coefficients of all the monomials involved are non-negative.
Proposition 2 (Kim-Vu concentration of multivariate polynomials [12]). Let Y be a random totally positive
Boolean polynomial in m Boolean random variables with degree at most k. If E[Y ] ≥ E≥1 [Y ], then


q
(12)
P |Y − E[Y ]| > ak E[Y ]E≥1 [Y ]λk = O (exp (−λ + (k − 1) log m))
for any λ > 1, where ak = 8k k!1/2 .
P
Let Y10 = (a,b,c,d)∈H10 tab tbc tcd tda tac tbd . Clearly Y10 is totally positive. Let k10,ab , σabc , and νabc be
the maximum number of 4-cliques sharing a common edge tab , wedge Λabc , and triangle ∆abc , respectively.
Taking repeated partial derivatives,


∂Y10
E
= p5 k10,ab ,
∂tab




∂Y10
∂Y10
= p4 σabc , E
= p4 ,
E
∂tab tbc
∂tab tcd




∂Y10
∂Y10
E
= p3 νabc , E
= p3 ,
∂tab tbc tac
∂tab tbc tcd




∂Y10
∂Y10
=E
= p2 ,
E
∂tab tbc tac tda
∂tab tbc tcd tda




∂Y10
∂Y10
E
= p, E
= 1.
∂tab tbc tcd tda tac
∂tab tbc tcd tda tac tbd
Noting that σabc ≤ min{k10,ab , k10,bc } ≤ k10 , similarly νabc ≤ k10 , and p5 ≤ p4 . . . ≤ 1, we have E≥1 [Y1 ] ≤
max{1, p3 k10 }. E≥1 [Y10 ] ≤ E[Y10 ] = p6 N10 implies
p
p
(13)
p ≥ max{ 6 1/N10 , 3 k10 /N10 }.
p
Choose KV ≥ 0 and let KV E[Y10 ] = a6 E[Y10 ]E≥1 [Y10 ]λ6 . Applying Proposition 2 to Y10 given (10)
and (13), the right hand side of (12) is O(exp(−γ log m)) = O(1/mγ ). Therefore, the error of the 4-clique
estimator X10 is
δX10 =
with probability greater than 1 −

1
1
δY10 = 6 (KV p6 N10 ) = N10
6
p
p

1
mγ .

Now we are ready to prove the corollary by comparing Theorem 2 and Lemma 1. Fix p, δ, > 0 and γ > 1
such that p = Ω(1/ log m) and δ = m−γ = Ω(1/m). Now we analyze the bounds KV and RK . For any
graph and a6 defined in Lemma 1,
1
≤ 1,
a26

γ
≤ 1,
(5 + γ)12

log(21/γ m) ≤ 2 log m,



k10
N10

2/3
≤ 1.

5/6

We further require k10 ≤ N10 . Then the condition on p with (14) implies
p11 ≥ 1/ log11 (m) ≥

n
o
γ log(21/γ m)
5/6
2/3
min
k
/N
,
(k
/N
)
.
10
10
10
10
2a26 (5 + γ)12 log12 (m)
15

(14)

Rearranging terms,
a26 log12 (m5+γ ) max

np
6

1/N10 ,

p
3

k10 /N10

o

p

≥

log(2mγ )k10 /N10
⇒ 2KV ≥ 2RK .
2p12

We note that the asymptotic condition p = Ω(1/ log m), includes a constant much smaller than 1. This
is due to the looseness of inequalities in (14) and implies that Theorem 2 is superior to Lemma 1 over all p
values of practical interest.

A.3

Implementation details

To improve the practical performance of 4-Prof-Dist (see Algorithm 1 for pseudocode), we handle low
and high degree vertices differently. As in GraphLab PowerGraph’s standard triangle counting, cuckoo hash
tables are used if the vertex degree is above a threshold. Now, we also threshold vertices to determine
whether the 2-hop histogram in Section 2.3 will be either a vector or an unordered map. This is because
sorting and merging operations on a vector scale poorly with increasing degree size, while an unordered map
has constant lookup time. We found that this approach successfully trades off processing time and memory
consumption.

A.4

Extension to global 4-profile sparsifier

Another advantage to read-k function families is that they are simpler to extend to more complex subgraphs.
We now state concentration results for the full 4-profile sparsifier evaluated experimentally in Section 4
Using the notation in Section 3, the edge sampling matrix H is defined by the relations

 





Y0
X0
N0
E[Y0 ]
 .. 
 .. 
 .. 
−1  .. 
=
H
where
⇒
=
H
 . ,
 . 
 . 
 . 
E[Y10 ]

1 1 − p (1 − p)2 (1 − p)2
0 p 2p(1 − p) 2p(1 − p)

p2
0
0 0
0 0
2
0
p

0 0
0
0

0
0
0
0
H=

0 0
0
0

0 0
0
0

0
0
0 0
0 0
0
0
0 0
0
0



N10

X10

Y10

(1 − p)3
(1 − p)3
(1 − p)3
(1 − p)4
2
2
2
3p(1 − p) 3p(1 − p) 3p(1 − p) 4p(1 − p)3
p2 (1 − p)
0
0
2p2 (1 − p)2
2p2 (1 − p) 3p2 (1 − p) 3p2 (1 − p) 4p2 (1 − p)2
p3
0
0
4p3 (1 − p)
3
0
p
0
0
0
0
p3
0
0
0
0
p4
0
0
0
0
0
0
0
0
0
0
0
0

16

(1 − p)4
4p(1 − p)3
p2 (1 − p)2
5p2 (1 − p)2
2p3 (1 − p)
p3 (1 − p)
p3 (1 − p)
0
p4
0
0

(1 − p)5
5p(1 − p)4
2p2 (1 − p)3
8p2 (1 − p)3
6p3 (1 − p)2
2p3 (1 − p)2
2p3 (1 − p)2
p4 (1 − p)
4p4 (1 − p)
p5
0

(1 − p)6
6p(1 − p)5 

3p2 (1 − p)4 
2
4
12p (1 − p) 
12p3 (1 − p)3 

4p3 (1 − p)3 
.
3
3 
4p (1 − p)

3p4 (1 − p)2 
4
2
12p (1 − p) 
6p5 (1 − p) 
p6



Let t =

p−1
p .

Then the inverse sampling matrix is given by

H−1


1
0


0

0


0

=
0

0

0


0

0
0

t

t2

t2

t3

t3

t3

t4

t4

t5

1
p

2t
p
1
p2

2t
p

3t2
p

3t2
p

0
0
0
0
0
0
0
0

1
p2

3t2
p
t
p2
2t
p2
1
p3

4t3
p
2t2
p2
4t2
p2
4t
p3

0
0
0
0
0
0

1
p3

0
0

4t3
p
t2
p2
5t2
p2
2t
p3
t
p3
t
p3

1
p4

0

0
0
0

1
p4

5t4
p
2t3
p2
8t3
p2
6t2
p3
2t2
p3
2t2
p3
t
p4
4t
p4
1
p5

0
0
0
0
0
0
0
0
0

0
0
0
0
0
0
0
0

0

0

3t
p2

3t
p2

0

0
0

0
0
0
0
0

1
p3

0
0
0
0

0
0

0

t6



6t5 
p 
3t4 
p2 

12t4 
p2 
12t3 
p3 

4t3 
.
p3 
4t3 
p3 

3t2 
p4 
12t2 
p4 
6t 

p5
1
p6

(15)

The binomial coefficients in these matrices influence our concentration bounds, which we now state:
Theorem 3 (4-profile sparsifier estimators). Consider the sampling process described above and in Section
3. Let Xi , 0 ≤ i ≤ 10 (and X be a vector of these estimates), be the actual estimates of 4-profiles. Let ki be
the maximum number of subgraphs Fi sharing a common edge. Let Yi , 0 ≤ i ≤ 10, be the 4 profile counts
of the sparsified graph. Then let Ni , 0 ≤ i ≤ 10, be the actual counts. Choose 0 < δ < 1 and  > 0. Let
C = (192)2 /2. If
1/10

1/8
C log(2/δ)(k9 + 6k10 )
C log(2/δ)(k8 + 4k9 + 12k10 )
,
p
≥
2 (N9 + 6N10 )
2 (N8 + 4N9 + 12N10 )
1/8

1/6

C log(2/δ)(k6 + k8 + 2k9 + 4k10 )
C log(2/δ)(k7 + k9 + 3k10 )
,
p
≥
p≥
2 (N7 + N9 + 3N10 )
2 (N6 + N8 + 2N9 + 4N10 )

1/6

1/6
C log(2/δ)(k5 + k8 + 2k9 + 4k10 )
C log(2/δ)(k4 + 4k7 + 2k8 + 6k9 + 12k10 )
p≥
, p≥
2 (N5 + N8 + 2N9 + 4N10 )
2 (N4 + 4N7 + 2N8 + 6N9 + 12N10 )

1/4
C log(2/δ)(k3 + 2k4 + 3k5 + 3k6 + 4k7 + 5k8 + 8k9 + 12k10 )
p≥
2 (N3 + 2N4 + 3N5 + 3N6 + 4N7 + 5N8 + 8N9 + 12N10 )
1/4

C log(2/δ)(k2 + k4 + 2k7 + k8 + 2k9 + 3k10 )
p≥
2 (N2 + N4 + 2N7 + N8 + 2N9 + 3N10 )

1/2
C log(2/δ)(k1 + 2k2 + 2k3 + 3k4 + 3k5 + 3k6 + 4k7 + 4k8 + 5k9 + 6k10 )
p≥
2 (N1 + 2N2 + 2N3 + 3N4 + 3N5 + 3N6 + 4N7 + 4N8 + 5N9 + 6N10 )


C log(2/δ)
2
2
n0 ≤ |V | |V | −
,
2


p≥

C log(2/δ)k10
2 N10

then kδXk∞ ≤ 

|V |
4



1/12



,

p≥

with probability at least 1 − δ.

Proof. We apply Proposition 1 a total of 11 times to the sampling-estimator system defined above by H
and H−1 . In our context, each sampled subgraph count Yi is a sum of functions in a read-kYi family, where
kYi ≤ min{|V | − 2, Ni }. Let ki,e be the maximum number of subgraphs Fi sharing a common edge e, and

17

let ki = maxe ki,e , for i = 0, . . . , 10. The Yi ’s have the following parameters:
 
|V |
rY0 =
, kY0 = |V |
4
rY1 = N1 + 2N2 + 2N3 + 3N4 + 3N5 + 3N6 + 4N7 + 4N8 + 5N9 + 6N10
kY1 = k1 + 2k2 + 2k3 + 3k4 + 3k5 + 3k6 + 4k7 + 4k8 + 5k9 + 6k10
rY2 = N2 + N4 + 2N7 + N8 + 2N9 + 3N10
kY2 = k2 + k4 + 2k7 + k8 + 2k9 + 3k10
rY3 = N3 + 2N4 + 3N5 + 3N6 + 4N7 + 5N8 + 8N9 + 12N10
kY3 = k3 + 2k4 + 3k5 + 3k6 + 4k7 + 5k8 + 8k9 + 12k10
rY4 = N4 + 4N7 + 2N8 + 6N9 + 12N10 ,
rY5 = N5 + N8 + 2N9 + 4N10 ,

kY5 = k5 + k8 + 2k9 + 4k10

rY6 = N6 + N8 + 2N9 + 4N10 ,

kY6 = k6 + k8 + 2k9 + 4k10

rY7 = N7 + N9 + 3N10 ,
rY8 = N8 + 4N9 + 12N10 ,
rY9 = N9 + 6N10 ,
rY10 = N10 ,

(16)

kY4 = k4 + 4k7 + 2k8 + 6k9 + 12k10

kY7 = k7 + k9 + 3k10
kY8 = k8 + 4k9 + 12k10

kY9 = k9 + 6k10

kY10 = k10

We show the application of Proposition 1 for Y7 through Y9 because Y10 was shown in the proof of
Theorem 2 and the other cases are similar:



2p8 2 (N7 + N9 + 3N10 )
P |Y7 − (p4 N7 + p4 (1 − p)N9 + 3p4 (1 − p)2 N10 )| ≥ p4 (N7 + N9 + 3N10 ) ≤ 2 exp −
k7 + k9 + 3k10


8 2

2p  (N8 + 4N9 + 12N10 )
P |Y8 − (p4 N8 + 4p4 (1 − p)N9 + 12p4 (1 − p)2 N10 )| ≥ p4 (N8 + 4N9 + 12N10 ) ≤ 2 exp −
k8 + 4k9 + 12k10


2

2 (N9 + 6N10 )
P |Y9 − (p5 N9 + 6p5 (1 − p)N10 )| ≥ (N9 + 6N10 ) ≤ 2 exp −
k9 + 6k10




10 2
2p  (N9 + 6N10 )
1
⇒ P | 5 Y9 − (N9 + 6(1 − p)N10 )| ≥ (N9 + 6N10 ) ≤ 2 exp −
p
k9 + 6k10


2

2 N10
6
P |Y10 − p N10 | ≥ N10 ≤ 2 exp −
k10



2p12 2 N10
6
6
⇒ P (|X10 − N10 | ≥ N10 ) = P |Y3 − p N10 | ≥ p N10 ≤ 2 exp −
k10
Rearranging to solve for p, we have

1/12

1/10

1/8
log(2/δ)k10
log(2/δ)(k9 + 6k10 )
log(2/δ)(k8 + 4k9 + 12k10 )
p≥
, p≥
, p≥
22 N10
22 (N9 + 6N10 )
22 (N8 + 4N9 + 12N10 )

1/8

1/6
log(2/δ)(k7 + k9 + 3k10 )
log(2/δ)(k6 + k7 + 2k9 + 4k10 )
p≥
,
p
≥
22 (N7 + N9 + 3N10 )
22 (N6 + N8 + 2N9 + 4N10 )

1/6

1/6
log(2/δ)(k5 + k7 + 2k9 + 4k10 )
log(2/δ)(k4 + 4k7 + 2k8 + 6k9 + 12k10 )
p≥
,
p
≥
22 (N5 + N8 + 2N9 + 4N10 )
22 (N4 + 4N7 + 2N8 + 6N9 + 12N10 )

1/4 (17)
log(2/δ)(k3 + 2k4 + 3k5 + 3k6 + 4k7 + 5k8 + 8k9 + 12k10 )
p≥
22 (N3 + 2N4 + 3N5 + 3N6 + 4N7 + 5N8 + 8N9 + 12N10 )

1/4
log(2/δ)(k2 + k4 + 2k7 + k8 + 2k9 + 3k10 )
p≥
22 (N2 + N4 + 2N7 + N8 + 2N9 + 3N10 )

1/2
log(2/δ)(k1 + 2k2 + 2k3 + 3k4 + 3k5 + 3k6 + 4k7 + 4k8 + 5k9 + 6k10 )
p≥
22 (N1 + 2N2 + 2N3 + 3N4 + 3N5 + 3N6 + 4N7 + 4N8 + 5N9 + 6N10 )
18

The final condition comes from the result for Y0 :
 


|V |
log(2/δ)|V |2
log(2/δ)
2
2
n0 ≤
−
≤ |V | |V | −
4
22
22

(18)

Plugging into our estimators (given by H−1 ), we get the following error bounds:
δX0 ≤ (n1 + n2 + n3 ) + (n1 + 2n2 + 3n3 + n2 + 3n3 + n3 )
 
|V |
≤ (2n1 + 4n2 + 8n3 ) ≤ 8
3
δX1 ≤ (N1 + 2N2 + 2N3 + 3N4 + 3N5 + 3N6 + 4N7 + 4N8 + 5N9 + 6N10 ) + 2(N2 + N4 + 2N7 + N8 + 2N9 + 3N10 )
+ 2(N3 + 2N4 + 3N5 + 3N6 + 4N7 + 5N8 + 8N9 + 12N10 ) + 3(N4 + 4N7 + 2N8 + 6N9 + 12N10 )
+ 3(N5 + N8 + 2N9 + 4N10 ) + 3(N6 + N8 + 2N9 + 4N10 ) + 4(N7 + N9 + 3N10 )
+ 4(N8 + 4N9 + 12N10 ) + 5(N9 + 6N10 ) + 6(N10 )
 
|V |
≤ (N1 + . . . + 192N10 ) ≤ 192
4
δX2 ≤ (N2 + N4 + 2N7 + N8 + 2N9 + 3N10 ) + (N4 + 4N7 + 2N8 + 6N9 + 12N10 ) + 2(N7 + N9 + 3N10 )
+ (N8 + 4N9 + 12N10 ) + 2(N9 + 6N10 ) + 3(N10 )
 
|V |
≤ (N2 + . . . + 48N10 ) ≤ 48
4

δX3 ≤ (N3 + 2N4 + 3N5 + 3N6 + 4N7 + 5N8 + 8N9 + 12N10 ) + 2(N4 + 4N7 + 2N8 + 6N9 + 12N10 )

+ 3(N5 + N8 + 2N9 + 4N10 ) + 3(N6 + N8 + 2N9 + 4N10 ) + 4(N7 + N9 + 3N10 ) + 5(N8 + 4N9 + 12N10 )
+ 8(N9 + 6N10 ) + 12(N10 )

≤ (N3 + 4N4 + 6N5 + . . . + 192N10 ) ≤ 192

 
|V |
4

δX4 ≤ (N4 + 4N7 + 2N8 + 6N9 + 12N10 ) + 4(N7 + N9 + 3N10 ) + 2(N8 + 4N9 + 12N10 ) + 6(N9 + 6N10 ) + 12(N10 )
 
|V |
≤ (N4 + . . . + 96N10 ) ≤ 96
4
δX5 ≤ (N5 + N8 + 2N9 + 4N10 ) + (N8 + 4N9 + 12N10 ) + 2(N9 + 6N10 ) + 4(N10 )
 
|V |
≤ (N5 + . . . + 32N10 ) ≤ 32
4
δX6 ≤ (N6 + N8 + 2N9 + 4N10 ) + (N8 + 4N9 + 12N10 ) + 2(N9 + 6N10 ) + 4(N10 )
 
|V |
≤ (N6 + . . . + 32N10 ) ≤ 32
4
δX7 ≤ (N7 + N9 + 3N10 ) + (N9 + 6N10 ) + 3(N10 )
 
|V |
≤ (N7 + 2N9 + 12N10 ) ≤ 12
4
δX8 ≤ (N8 + 4N9 + 12N10 ) + 4(N9 + 6N10 ) + 12(N10 )
 
|V |
≤ (N8 + 8N9 + 48N10 ) ≤ 48
4
δX9 ≤ (N9 + 6N10 ) + 6(N10 )
 
|V |
≤ (N9 + 12N10 ) ≤ 12
4
δX10 ≤ N10 .
Thus the maximum deviation in any estimator is less than 192
completes the proof.

19

|V |
4



. Substituting ˜2 = 2 /(192)2 = 2 /2C

